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/22 21:04:25 UTC
svn commit: r498772 - 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 22 12:04:25 2007
New Revision: 498772
URL: http://svn.apache.org/viewvc?view=rev&rev=498772
Log:
DERBY-2191: Cleanup of FormatableBitSet
Changed the bitset operator methods or(), and() and xor() so that they
follow the same pattern. All are now performing the operation
bytewise, and there is no special handling of the last partial
byte. The patch also adds a method called invariantHolds() that checks
if the class' invariant is maintained (for use in the unit test).
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=498772&r1=498771&r2=498772
==============================================================================
--- 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 22 12:04:25 2007
@@ -149,6 +149,45 @@
return new FormatableBitSet(this);
}
+ /**
+ * This method returns true if the following conditions hold:
+ * 1. The number of bits in the bitset will fit into the allocated
+ * byte array. 2. 'lengthAsBits' and 'bitsInLastByte' are
+ * consistent. 3. All unused bits in the byte array are
+ * unset. This represents an invariant for the class, so this
+ * method should always return true.
+ *
+ * The method is public, but is primarily intended for testing and
+ * ASSERTS.
+ * @returns true if invariant holds, false otherwise
+ */
+ public boolean invariantHolds() {
+ // Check that all bits will fit in byte array
+ final int arrayLengthAsBits = value.length*8;
+ if (lengthAsBits > arrayLengthAsBits) { return false; }
+
+ // Check consistency of 'lengthAsBits' and 'bitsInLastByte'
+ final int partialByteIndex = (lengthAsBits-1)/8;
+ if (bitsInLastByte != (lengthAsBits - (8*partialByteIndex))) {
+ return false;
+ }
+ // Special case for empty bitsets since they will have
+ // 'partialByteIndex'==0, but this isn't a legal index into
+ // the byte array
+ if (value.length==0) { return true; }
+
+ // Check that the last used (possibly partial) byte doesn't
+ // contain any unused bit positions that are set.
+ byte partialByte = value[partialByteIndex];
+ partialByte <<= bitsInLastByte; // must be zero after shift
+
+ // Check the remaining completely unused bytes (if any)
+ for (int i = partialByteIndex+1; i < value.length; ++i) {
+ partialByte |= value[i];
+ }
+ return (partialByte==0);
+ }
+
/**
* Get the length in bytes of a Bit value
@@ -724,101 +763,97 @@
}
/**
- * Bitwise OR this Bit with another Bit.
+ * Bitwise OR this FormatableBitSet with another
+ * FormatableBitSet. The result is stored in this bitset. The
+ * operand is unaffected. A null operand is treated as an empty
+ * bitset (i.e. a noop). A bitset that is smaller than its operand
+ * is expanded to the same size.
*
- * @param otherBit the other Bit
+ * @param otherBit bitset operand
*/
public void or(FormatableBitSet otherBit)
{
- if (otherBit == null || otherBit.getLength() == 0)
+ if (otherBit == null) {
return;
-
+ }
int otherLength = otherBit.getLength();
- if (otherLength > getLength())
- grow(otherLength); // expand this bit
+ if (otherLength > getLength()) {
+ grow(otherLength);
+ }
int obByteLen = otherBit.getLengthInBytes();
- for (int i = 0; i < obByteLen-1; i++)
+ for (int i = 0; i < obByteLen; ++i) {
value[i] |= otherBit.value[i];
-
- // do the last byte bit by bit
- for (int i = (obByteLen-1)*8; i < otherLength; i++)
- if (otherBit.isSet(i))
- set(i);
+ }
+ if (SanityManager.DEBUG) {
+ SanityManager.ASSERT(invariantHolds(),"or() broke invariant");
+ }
}
/**
- * Bitwise AND this Bit with another Bit.
- *
- * @param otherBit the other Bit
+ * Bitwise AND this FormatableBitSet with another
+ * FormatableBitSet. The result is stored in this bitset. The
+ * operand is unaffected. A null operand is treated as an empty
+ * bitset (i.e. clearing this bitset). A bitset that is smaller
+ * than its operand is expanded to the same size.
+ * @param otherBit bitset operand
*/
public void and(FormatableBitSet otherBit)
{
- if (SanityManager.DEBUG)
- SanityManager.ASSERT(otherBit != null, "cannot AND null with a FormatableBitSet");
-
+ if (otherBit == null) {
+ clear();
+ return;
+ }
int otherLength = otherBit.getLength();
- // Supposedly cannot happen, but handle it just in case.
- if (otherLength > getLength())
- grow(otherLength); // expand this bit
-
- if (otherLength < getLength())
- {
- // clear all bits that are not in the other bit
- int startingByte = (otherLength * 8) + 1;
- int len = getLengthInBytes();
- for (int i = startingByte; i < len; i++)
- value[i] = 0;
-
- for (int i = otherLength; i < startingByte*8; i++)
- {
- if (i < getLength())
- clear(i);
- else
- break;
- }
+ if (otherLength > getLength()) {
+ grow(otherLength);
}
- if (otherLength == 0)
- return;
-
- int length = otherBit.getLengthInBytes() < getLengthInBytes() ?
- otherBit.getLengthInBytes() : getLengthInBytes();
-
- for (int i = 0; i < length; i++)
+ // Since this bitset is at least as large as the other bitset,
+ // one can use the length of the other bitset in the iteration
+ int byteLength = otherBit.getLengthInBytes();
+ int i = 0;
+ for (; i < byteLength; ++i) {
value[i] &= otherBit.value[i];
+ }
+
+ // If the other bitset is shorter the excess bytes in this
+ // bitset must be cleared
+ byteLength = getLengthInBytes();
+ for (; i < byteLength; ++i) {
+ value[i] = 0;
+ }
+ if (SanityManager.DEBUG) {
+ SanityManager.ASSERT(invariantHolds(),"and() broke invariant");
+ }
}
/**
- * Logically XORs this FormatableBitSet with the specified FormatableBitSet.
- * @param set The FormatableBitSet to be XORed with.
+ * Bitwise XOR this FormatableBitSet with another
+ * FormatableBitSet. The result is stored in this bitset. The
+ * operand is unaffected. A null operand is treated as an empty
+ * bitset (i.e. a noop). A bitset that is smaller than its operand
+ * is expanded to the same size.
+ * @param otherBit bitset operand
*/
- public void xor(FormatableBitSet set)
+ public void xor(FormatableBitSet otherBit)
{
- if (SanityManager.DEBUG)
- {
- if (getLength() != set.getLength())
- {
- SanityManager.THROWASSERT("getLength() (" + getLength() +
- ") and set.getLength() (" +
- set.getLength() +
- ") expected to be the same");
- }
+ if (otherBit == null) {
+ return;
+ }
+ int otherLength = otherBit.getLength();
+ if (otherLength > getLength()) {
+ grow(otherLength);
}
- int setLength = set.getLength();
- for (int i = setLength; i-- > 0; )
- {
- if (isSet(i) && set.isSet(i))
- {
- clear(i);
- }
- else if (isSet(i) || set.isSet(i))
- {
- set(i);
- }
+ int obByteLen = otherBit.getLengthInBytes();
+ for (int i = 0; i < obByteLen; ++i) {
+ value[i] ^= otherBit.value[i];
+ }
+ if (SanityManager.DEBUG) {
+ SanityManager.ASSERT(invariantHolds(),"xor() broke invariant");
}
}
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=498772&r1=498771&r2=498772
==============================================================================
--- 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 22 12:04:25 2007
@@ -103,16 +103,19 @@
assertEquals(0,empty.getLengthInBytes());
assertEquals(0,empty.getByteArray().length);
assertEquals(0,empty.getNumBitsSet());
+ assertTrue(empty.invariantHolds());
assertEquals(18,bitset18.getLength());
assertEquals(3,bitset18.getLengthInBytes());
assertEquals(bits24,bitset18.getByteArray());
assertEquals(9,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
assertEquals(18,bitset18C.getLength());
assertEquals(3,bitset18C.getLengthInBytes());
assertEquals(bits24C,bitset18C.getByteArray());
assertEquals(9,bitset18C.getNumBitsSet());
+ assertTrue(bitset18C.invariantHolds());
}
// Test cases for single arg constructor
@@ -122,6 +125,7 @@
assertEquals(0,zeroBits.getLengthInBytes());
assertEquals(0,zeroBits.getByteArray().length);
assertEquals(0,zeroBits.getNumBitsSet());
+ assertTrue(zeroBits.invariantHolds());
}
public void testIntCtor1() {
FormatableBitSet oneBit = new FormatableBitSet(1);
@@ -129,6 +133,7 @@
assertEquals(1,oneBit.getLengthInBytes());
assertEquals(1,oneBit.getByteArray().length);
assertEquals(0,oneBit.getNumBitsSet());
+ assertTrue(oneBit.invariantHolds());
}
public void testIntCtor8() {
FormatableBitSet eightBits = new FormatableBitSet(8);
@@ -136,6 +141,7 @@
assertEquals(1,eightBits.getLengthInBytes());
assertEquals(1,eightBits.getByteArray().length);
assertEquals(0,eightBits.getNumBitsSet());
+ assertTrue(eightBits.invariantHolds());
}
public void testIntCtor9() {
FormatableBitSet nineBits = new FormatableBitSet(9);
@@ -143,6 +149,7 @@
assertEquals(2,nineBits.getLengthInBytes());
assertEquals(2,nineBits.getByteArray().length);
assertEquals(0,nineBits.getNumBitsSet());
+ assertTrue(nineBits.invariantHolds());
}
public void testIntCtorNeg() {
// Should throw an exception?
@@ -151,6 +158,7 @@
assertEquals(0,negBits.getLengthInBytes());
assertEquals(0,negBits.getByteArray().length);
assertEquals(0,negBits.getNumBitsSet());
+ assertTrue(negBits.invariantHolds());
}
// Test cases for the copy constructor
@@ -161,6 +169,7 @@
// FAILURE - the byte array of the copy is not null
//assertEquals(null,emptyCpy.getByteArray());
assertEquals(0,emptyCpy.getNumBitsSet());
+ assertTrue(emptyCpy.invariantHolds());
}
public void testCpyCtor() {
FormatableBitSet cpy = new FormatableBitSet(bitset18);
@@ -170,6 +179,7 @@
assertEquals(9,cpy.getNumBitsSet());
assertEquals(0,cpy.compare(bitset18));
assertTrue(cpy.equals(bitset18));
+ assertTrue(cpy.invariantHolds());
}
// Test cases for grow(int)
@@ -179,6 +189,7 @@
assertEquals(3,empty.getLengthInBytes());
assertEquals(3,empty.getByteArray().length);
assertEquals(0,empty.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testGrow() {
bitset18.grow(25);
@@ -186,16 +197,19 @@
assertEquals(4,bitset18.getLengthInBytes());
assertEquals(4,bitset18.getByteArray().length);
assertEquals(9,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
// OK - should fail?
public void testGrowSmaller() {
bitset18.grow(9);
assertEquals(18,bitset18.getLength());
+ assertTrue(bitset18.invariantHolds());
}
// OK - should fail?
public void testGrowNeg() {
bitset18.grow(-9);
assertEquals(18,bitset18.getLength());
+ assertTrue(bitset18.invariantHolds());
}
// Test cases for shrink(int)
@@ -205,6 +219,7 @@
assertEquals(0,empty.getLengthInBytes());
assertEquals(0,empty.getByteArray().length);
assertEquals(0,empty.getNumBitsSet());
+ assertTrue(empty.invariantHolds());
}
public void testShrink() {
bitset18.shrink(9);
@@ -212,11 +227,13 @@
assertEquals(2,bitset18.getLengthInBytes());
assertEquals(2,bitset18.getByteArray().length);
assertEquals(5,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
// OK - should fail?
public void testShrinkLarger() {
bitset18.shrink(25);
assertEquals(18,bitset18.getLength());
+ assertTrue(bitset18.invariantHolds());
}
public void testShrinkNeg() {
try {
@@ -259,9 +276,12 @@
public void testCompareDifferentArray() {
FormatableBitSet small = new FormatableBitSet(bitset18);
small.shrink(9);
+ assertTrue(small.invariantHolds());
FormatableBitSet large = new FormatableBitSet(bitset18);
large.grow(100);
+ assertTrue(large.invariantHolds());
large.shrink(9);
+ assertTrue(large.invariantHolds());
assertEquals(0,small.compare(large));
}
@@ -312,7 +332,9 @@
try { bitset18.set(-1); fail(); }
catch (IllegalArgumentException iae) {}
bitset18.set(0);
+ assertTrue(bitset18.invariantHolds());
bitset18.set(1);
+ assertTrue(bitset18.invariantHolds());
try { bitset18.set(18); fail(); }
catch (IllegalArgumentException iae) {}
}
@@ -329,7 +351,9 @@
try { bitset18.clear(-1); fail(); }
catch (IllegalArgumentException iae) {}
bitset18.clear(0);
+ assertTrue(bitset18.invariantHolds());
bitset18.clear(1);
+ assertTrue(bitset18.invariantHolds());
try { bitset18.clear(18); fail(); }
catch (IllegalArgumentException iae) {}
}
@@ -372,6 +396,7 @@
// Test cases for or(FormatableBitSet)
public void testORWithNull() {
FormatableBitSet cpy = new FormatableBitSet(bitset18);
+ assertTrue(cpy.invariantHolds());
bitset18.or(null);
assertEquals(9,bitset18.getNumBitsSet());
assertTrue(cpy.equals(bitset18));
@@ -381,69 +406,75 @@
bitset18.or(empty);
assertEquals(9,bitset18.getNumBitsSet());
assertTrue(cpy.equals(bitset18));
+ assertTrue(bitset18.invariantHolds());
}
public void testORWithComplement() {
bitset18.or(bitset18C);
assertEquals(bitset18.getNumBitsSet(),18);
+ assertTrue(bitset18.invariantHolds());
}
public void testORWithSmaller() {
bitset18C.shrink(9);
bitset18.or(bitset18C);
assertEquals(13,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testORWithLarger() {
bitset18.shrink(9);
bitset18.or(bitset18C);
assertEquals(14,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
// Test cases for and(FormatableBitSet)
public void testANDWithNull() {
- if (SanityManager.DEBUG) {
- try { bitset18.and(null); fail(); } catch (AssertFailure af) {}
- }
- else {
- try { bitset18.and(null); fail(); }
- catch (NullPointerException npe) {}
- }
+ bitset18.and(null);
+ assertEquals(18,bitset18.getLength());
+ assertEquals(3,bitset18.getLengthInBytes());
+ assertEquals(3,bitset18.getByteArray().length);
+ assertEquals(0,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testANDWithEmpty() {
bitset18.and(new FormatableBitSet());
assertEquals(0,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testANDWithComplement() {
bitset18.and(bitset18C);
assertEquals(0,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testANDWithSmaller() {
bitset18C.shrink(9);
bitset18.and(bitset18C);
assertEquals(0,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testANDWithLarger() {
bitset18.shrink(9);
bitset18.and(bitset18C);
assertEquals(0,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
// Test cases for xor(FormatableBitSet)
public void testXORWithNull() {
- try { bitset18.xor(null); fail(); } catch (NullPointerException npe) {}
+ FormatableBitSet cpy = new FormatableBitSet(bitset18);
+ bitset18.xor(null);
+ assertEquals(9,bitset18.getNumBitsSet());
+ assertTrue(cpy.equals(bitset18));
+ assertTrue(bitset18.invariantHolds());
}
public void testXORWithEmpty() {
FormatableBitSet cpy = new FormatableBitSet(bitset18);
- if (SanityManager.DEBUG) {
- try { bitset18.xor(empty); fail(); } catch (AssertFailure af) {}
- }
- else {
- bitset18.xor(empty);
- assertEquals(0,empty.getLength());
- assertEquals(0,empty.getLengthInBytes());
- assertEquals(0,empty.getByteArray().length);
- assertEquals(0,empty.getNumBitsSet());
- }
- //assertEquals(9,bitset18.getNumBitsSet());
- //assertTrue(cpy.equals(bitset18));
+ bitset18.xor(empty);
+ assertEquals(18,bitset18.getLength());
+ assertEquals(3,bitset18.getLengthInBytes());
+ assertEquals(3,bitset18.getByteArray().length);
+ assertEquals(9,bitset18.getNumBitsSet());
+ assertTrue(cpy.equals(bitset18));
+ assertTrue(bitset18.invariantHolds());
}
public void testXORWithComplement() {
bitset18.set(2);
@@ -452,32 +483,22 @@
assertEquals(16,bitset18.getNumBitsSet());
assertFalse(bitset18.isSet(2));
assertFalse(bitset18.isSet(3));
+ assertTrue(bitset18.invariantHolds());
}
public void testXORWithSmaller() {
bitset18C.shrink(9);
- if (SanityManager.DEBUG) {
- try { bitset18.xor(bitset18C); fail(); } catch (AssertFailure af) {}
- }
- else {
- bitset18.xor(bitset18C);
- assertEquals(18,bitset18.getLength());
- assertEquals(3,bitset18.getLengthInBytes());
- assertEquals(3,bitset18.getByteArray().length);
- assertEquals(13,bitset18.getNumBitsSet());
-
- }
- //assertEquals(13,bitset18.getNumBitsSet());
+ bitset18.xor(bitset18C);
+ assertEquals(18,bitset18.getLength());
+ assertEquals(3,bitset18.getLengthInBytes());
+ assertEquals(3,bitset18.getByteArray().length);
+ assertEquals(13,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
public void testXORWithLarger() {
bitset18.shrink(9);
- if (SanityManager.DEBUG) {
- try { bitset18.xor(bitset18C); fail(); } catch (AssertFailure af) {}
- }
- else {
- try { bitset18.xor(bitset18C); fail(); }
- catch (IllegalArgumentException iae) {}
- }
- //assertEquals(14,bitset18.getNumBitsSet());
+ bitset18.xor(bitset18C);
+ assertEquals(14,bitset18.getNumBitsSet());
+ assertTrue(bitset18.invariantHolds());
}
// Test case for writeExternal(ObjectOut) and readExternal(ObjectOut)
@@ -487,18 +508,10 @@
bitset18.writeExternal(oos);
oos.flush();
- empty.readExternal(new ObjectInputStream(new ByteArrayInputStream(buf.toByteArray())));
+ empty.readExternal
+ (new ObjectInputStream(new ByteArrayInputStream
+ (buf.toByteArray())));
assertTrue(empty.equals(bitset18));
+ assertTrue(empty.invariantHolds());
}
-
- // ERROR - Negative array size argument
- // Not covered by other tests
- // public void testReadExternalFromArray() throws IOException {
- // ByteArrayOutputStream buf = new ByteArrayOutputStream();
- // ObjectOutput oos = new ObjectOutputStream(buf);
- // bitset18.writeExternal(oos);
- // oos.flush();
- // empty.readExternalFromArray(new ArrayInputStream(buf.toByteArray()));
- // assertTrue(empty.equals(bitset18));
- // }
}