www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - binary searches in phobos

reply Karen Lanrap <karen digitaldaemon.com> writes:
At least the searches in phobos/internal/switch.d fail when the 
length of the searched list reaches int.max/2, because a signed shift 
is executed instead of an unsigned shift to compute the new "mid" 
index for checking.

Should this considered to be a bug---or as an academic detection 
only?
Dec 07 2006
next sibling parent Thomas Kuehne <thomas-dloop kuehne.cn> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Karen Lanrap schrieb am 2006-12-07:
 At least the searches in phobos/internal/switch.d fail when the 
 length of the searched list reaches int.max/2, because a signed shift 
 is executed instead of an unsigned shift to compute the new "mid" 
 index for checking.

 Should this considered to be a bug---or as an academic detection 
 only?

I haven't takten a closer look, but using "int" instead of "size_t" is most likely a bug. Please file all bugs, even if they might seem "academic only". Those are usualy the bugs that are hard to track down and often show up while porting or using generated code. Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFFeAXBLK5blCcjpWoRAruHAKCgUIKgqGoAoLzshv4gvAtSwSagzQCggt4l mw3a5rlI5UwRTr+gv5Hf4sA= =mBqr -----END PGP SIGNATURE-----
Dec 07 2006
prev sibling parent "Andrey Khropov" <andkhropov_nosp m_mtu-net.ru> writes:
Karen Lanrap wrote:

 At least the searches in phobos/internal/switch.d fail when the 
 length of the searched list reaches int.max/2, because a signed shift 
 is executed instead of an unsigned shift to compute the new "mid" 
 index for checking.
 
 Should this considered to be a bug---or as an academic detection 
 only?

It's actually a very famous bug: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly. html -- 'non-optimal' is a politically correct term for s**t
Dec 07 2006