You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-commits@db.apache.org by ka...@apache.org on 2007/01/29 17:36:06 UTC
svn commit: r501095 - in /db/derby/code/trunk/java:
engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java
Author: kahatlen
Date: Mon Jan 29 08:36:05 2007
New Revision: 501095
URL: http://svn.apache.org/viewvc?view=rev&rev=501095
Log:
DERBY-2191: Cleanup of FormatableBitSet
Re-wrote anySetBit and anySetBit(int beyondBit) to use a single loop
and removed special handling of the last byte.
Patch contributed by Dyre Tjeldvoll.
Modified:
db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
db/derby/code/trunk/java/testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java
Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java?view=diff&rev=501095&r1=501094&r2=501095
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/services/io/FormatableBitSet.java Mon Jan 29 08:36:05 2007
@@ -93,6 +93,7 @@
// will be inlined by the compiler.
private static int udiv8(int i) { return (i>>3); }
private static byte umod8(int i) { return (byte)(i&0x7); }
+ private static int umul8(int i) { return (i<<3); }
/**
* Niladic Constructor
@@ -642,42 +643,56 @@
}
/**
- * If any bit is set, return the bit number of a bit that is set.
- * If no bit is set, return -1;
- *
- * @return the bit number of a bit that is set, or -1 if no bit is set
+ * A utility method which treats the byte argument as an 8-bit
+ * bitset and finds the first set bit in that byte. Assumes that
+ * at least one bit in v is set (v!=0).
+ * @param a non-zero byte to check for set bits
+ * @return the zero-based index of the first set bit in the argument byte
*/
- public int anySetBit()
- {
- int numbytes = getLengthInBytes();
- int bitpos;
-
- for (int i = 0; i < numbytes-1; i++)
- {
- if (value[i] != 0)
- {
- for (int j = 0; j < 8; j++)
- {
- bitpos = 7-j;
- if (((1 << bitpos) & value[i]) != 0)
- return ((i*8)+j);
- }
- }
+ private static byte firstSet(byte v) {
+ if ((v & 0x80) != 0) {
+ return 0;
}
-
-
- // only the top part of the last byte is relevant
- byte mask = (byte)(0xFF << (8-bitsInLastByte));
- if ((value[numbytes-1] & mask) != 0)
- {
- for (int j = 0; j < bitsInLastByte; j++)
- {
- bitpos = 7-j;
- if (((1 << bitpos) & value[numbytes-1]) != 0)
- return ((numbytes-1)*8)+j;
- }
+ if ((v & 0x40) != 0) {
+ return 1;
+ }
+ if ((v & 0x20) != 0) {
+ return 2;
+ }
+ if ((v & 0x10) != 0) {
+ return 3;
+ }
+ if ((v & 0x8) != 0) {
+ return 4;
+ }
+ if ((v & 0x4) != 0) {
+ return 5;
+ }
+ if ((v & 0x2) != 0) {
+ return 6;
}
+ return 7;
+ }
+ /**
+ * If any bit is set, return the zero-based bit index of the first
+ * bit that is set. If no bit is set, return -1. By using
+ * anySetBit() and anySetBit(beyondBit), one can quickly go thru
+ * the entire bit array to return all set bit.
+ *
+ * @return the zero-based index of the first bit that is set, or
+ * -1 if no bit is set
+ */
+ public int anySetBit() {
+ if (SanityManager.DEBUG) {
+ SanityManager.ASSERT(invariantHolds(), "broken invariant");
+ }
+ final int numbytes = getLengthInBytes();
+ for (int i = 0; i < numbytes; ++i) {
+ final byte v = value[i];
+ if (v == 0) continue;
+ return (umul8(i) + firstSet(v));
+ }
return -1;
}
@@ -691,91 +706,25 @@
* @return the bit number of a bit that is set, or -1 if no bit after
* beyondBit is set
*/
- public int anySetBit(int beyondBit)
- {
- if (SanityManager.DEBUG)
- {
- if (beyondBit >= this.getLength())
- SanityManager.THROWASSERT(
- "Attempt to access bit position that exceeds the max length ("
- + this.getLength() + ")");
+ public int anySetBit(int beyondBit) {
+ if (SanityManager.DEBUG) {
+ SanityManager.ASSERT(invariantHolds(), "broken invariant");
}
-
- int startingBit = (beyondBit+1);
-
- // we have seen the last bit.
- if (startingBit >= this.getLength())
+ if (++beyondBit >= lengthAsBits) {
return -1;
-
- int numbytes = getLengthInBytes();
- int startingByte = startingBit / 8;
- int startingBitpos = startingBit % 8;
- int bitpos;
- byte mask;
-
- // see if any bits in this byte is set, only the bottom part of the
- // first byte is relevant
- mask = (byte)(0xFF >> startingBitpos);
-
- if (startingByte == numbytes-1) // starting byte == last byte
- mask &= (byte)(0xFF << (8-bitsInLastByte));
-
- if ((value[startingByte] & mask ) != 0)
- {
- // I know we will see the bit before bitsInLastByte even if we are
- // at the last byte, no harm in going up to 8 in the loop
- for (int j = startingBitpos; j < 8; j++)
- {
- if (SanityManager.DEBUG)
- {
- if (startingByte == numbytes-1)
- SanityManager.ASSERT(j < bitsInLastByte,
- "going beyond the last bit");
- }
- bitpos = 7-j;
- if (((1 << bitpos) & value[startingByte]) != 0)
- {
- return (startingByte*8+j);
- }
- }
- }
-
- for (int i = (startingByte+1); i < numbytes-1; i++)
- {
- if (value[i] != 0)
- {
- for (int j = 0; j < 8; j++)
- {
- bitpos = 7-j;
- if (((1 << bitpos) & value[i]) != 0)
- {
- return ((i*8)+j);
- }
- }
- }
}
-
- // Last byte if there are more than one bytes. Only the top part of
- // the last byte is relevant
- if (startingByte != numbytes-1)
- {
- mask = (byte)(0xFF << (8-bitsInLastByte));
-
- if ((value[numbytes-1] & mask) != 0)
- {
- for (int j = 0; j < bitsInLastByte; j++)
- {
- bitpos = 7-j;
- if (((1 << bitpos) & value[numbytes-1]) != 0)
- {
- return ((numbytes-1)*8)+j;
- }
- }
- }
+ int i = udiv8(beyondBit);
+ byte v = (byte)(value[i] << umod8(beyondBit));
+ if (v != 0) {
+ return (beyondBit + firstSet(v));
+ }
+ final int numbytes = getLengthInBytes();
+ for (++i; i < numbytes; ++i) {
+ v = value[i];
+ if (v == 0) continue;
+ return (umul8(i) + firstSet(v));
}
-
return -1;
-
}
/**
Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java?view=diff&rev=501095&r1=501094&r2=501095
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java (original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/unitTests/junit/FormatableBitSetTest.java Mon Jan 29 08:36:05 2007
@@ -355,10 +355,7 @@
// Test cases for anySetBit()
public void testAnySetBitEmpty() {
- // More reasonable to return -1 here ?
- try { empty.anySetBit(); fail(); }
- catch (ArrayIndexOutOfBoundsException e) {}
- //assertEquals(empty.anySetBit(),-1);
+ assertEquals(empty.anySetBit(),-1);
}
public void testAnySetBit() {
assertEquals(2,bitset18C.anySetBit());
@@ -373,19 +370,13 @@
public void testAnySetBitBeyondBitNeg() {
assertEquals(1,bitset18.anySetBit(0));
assertEquals(0,bitset18.anySetBit(-1));
-
- // Should be 0 or failure?
- assertEquals(10,bitset18.anySetBit(-2));
- // Should be 0 or failure?
- assertEquals(10,bitset18.anySetBit(-3));
+ try { bitset18.anySetBit(-2); fail(); }
+ catch (ArrayIndexOutOfBoundsException e) {}
+ try { bitset18.anySetBit(-3); fail(); }
+ catch (ArrayIndexOutOfBoundsException e) {}
}
public void testAnySetBitBeyondBitPastEnd() {
- if (SanityManager.DEBUG) {
- try { bitset18.anySetBit(18); fail(); } catch (AssertFailure af) {}
- }
- else {
- assertEquals(-1, bitset18.anySetBit(18));
- }
+ assertEquals(-1, bitset18.anySetBit(18));
}
// Test cases for or(FormatableBitSet)