Hi Yonik, I wrote atestcase that checks how prevSetBit behaves, if I add you
patch with optimization. It still had a bug, if the index is beyond last
word but not at a multiple of bitsPerWord. The following code is correct:
public int prevSetBit(int index) {
int i = index >> 6;
final int subIndex;
if (i >= wlen) {
i = wlen - 1;
if (i < 0) return -1;
subIndex = 0x3f; // last possible bit
} else {
if (i < 0) return -1;
subIndex = index & 0x3f; // index within the word
}
long word = (bits[i] << (63-subIndex)); // skip all the bits to the
left of index
if (word != 0) {
return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See
LUCENE-3197
}
while (--i >= 0) {
word = bits[i];
if (word !=0 ) {
return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
}
}
return -1;
}
Your additional optimization with negative indexes is invalid, because on
negative indexes prevSetBit() must be negative. If we dont do this, a
typical loop like would AIOOBE:
for (int i = bs.prevSetBit(0); i >= 0; i = bs.prevSetBit(i-1)) {
// operate on index i here
}
Uwe
-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: [email protected]
> -----Original Message-----
> From: [email protected] [mailto:[email protected]] On Behalf Of Yonik
> Seeley
> Sent: Friday, June 24, 2011 6:29 PM
> To: [email protected]
> Subject: Re: [VOTE] release 3.3
>
> On Fri, Jun 24, 2011 at 12:14 PM, Yonik Seeley
<[email protected]>
> wrote:
> > All that needs to be done is to move the negative index check to the
> > bottom (the first index<0 is not needed since we do a signed shift).
> >
> > public int prevSetBit(int index) {
> > int i = index>>6;
> > if (i >= wlen) {
> > i = wlen - 1;
> > }
> > if (i < 0) return -1;
> > final int subIndex = index & 0x3f; // index within the word
> > long word = (bits[i] << (63-subIndex)); // skip all the bits to
> > the left of index
>
> And a further minor optimization, if we assume that negative indexes are
not
> legal, is to move the (i<0) check inside the if (i>=wlen) block (and just
let a
> negative index passed by the user to cause a natural AIOOB).
>
> -Yonik
> http://www.lucidimagination.com
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [email protected] For additional
> commands, e-mail: [email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
