FormatableBitSet is implemented as a packed array of bytes.
| Method from org.apache.derby.iapi.services.io.FormatableBitSet Detail: |
|---|
 public void and(FormatableBitSet otherBit) {
if (otherBit == null) {
clear();
return;
}
int otherLength = otherBit.getLength();
if (otherLength > getLength()) {
grow(otherLength);
}
// 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");
}
}
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. |
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;
} 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. |
public int anySetBit(int beyondBit) {
if (SanityManager.DEBUG) {
SanityManager.ASSERT(invariantHolds(), "broken invariant");
}
if (++beyondBit >= lengthAsBits) {
return -1;
}
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;
} Like anySetBit(), but return any set bit whose number is bigger than
beyondBit. If no bit is set after beyondBit, -1 is returned.
By using anySetBit() and anySetBit(beyondBit), one can quickly go
thru the entire bit array to return all set bit. |
public void clear() {
int byteLength = getLengthInBytes();
for (int ix=0; ix < byteLength; ix++)
value[ix] = 0;
} Clear all the bits in this FormatableBitSet |
public void clear(int position) {
checkPosition(position);
final int byteIndex = udiv8(position);
final byte bitIndex = umod8(position);
value[byteIndex] &= ~(0x80 > >bitIndex);
} |
public Object clone() {
return new FormatableBitSet(this);
} |
public int compare(FormatableBitSet other) {
int otherCount, thisCount;
int otherLen, thisLen;
byte[] otherb;
otherb = other.value;
otherLen = other.getLengthInBytes();
thisLen = getLengthInBytes();
for (otherCount = 0, thisCount = 0;
otherCount < otherLen && thisCount < thisLen;
otherCount++, thisCount++)
{
if (otherb[otherCount] != this.value[thisCount])
break;
}
/*
** '==' if byte by byte comparison is identical and
** exact same length in bits (not bytes).
*/
if ((otherCount == otherLen) && (thisCount == thisLen))
{
if (this.getLength() == other.getLength())
{
return 0;
}
/*
** If subset of bits is identical, return 1
** if other.getLength() > this.getLength(); otherwise,
** -1
*/
return (other.getLength() < this.getLength()) ? 1 : -1;
}
if (otherCount == otherLen)
{
return 1;
}
else if (thisCount == thisLen)
{
return -1;
}
else
{
/*
** Ok, we have a difference somewhere. Now
** we have to go to the trouble of converting
** to a int and masking out the sign to get
** a valid comparision because bytes are signed.
*/
int otherInt, thisInt;
otherInt = (int)otherb[otherCount];
otherInt &= (0x100 - 1);
thisInt = (int)this.value[thisCount];
thisInt &= (0x100 - 1);
return (thisInt > otherInt) ? 1 : -1;
}
} Bit comparison. Compare this with other.
Will always do a byte by byte compare.
Given 2 similar bits of unequal lengths (x and y),
where x.getLength() < y.getLength() but where:
x[0..x.getLength()] == y[0..x.getLength()]
then x < y. |
public boolean equals(FormatableBitSet other) {
if (this.getLength() != other.getLength())
{
return false;
}
return (this.compare(other) == 0);
} Bit equivalence. Compare this with other.
If the length is different, then cannot be
equal so short circuit. Otherwise, rely on
compare(). Note that two zero length bits are
considered equal. |
public final boolean get(int position) {
return isSet(position);
} Bit get -- alias for isSet() |
public byte[] getByteArray() {
// In some cases the array is bigger than the actual number
// of valid bytes.
int realByteLength = getLengthInBytes();
// Currently the case is that the return from this
// call only includes the valid bytes.
if (value.length != realByteLength) {
byte[] data = new byte[realByteLength];
System.arraycopy(value, 0, data, 0, realByteLength);
value = data;
}
return value;
} Get the value of the byte array |
public int getLength() {
return lengthAsBits;
} |
public int getLengthInBytes() {
return FormatableBitSet.numBytesFromBits(lengthAsBits);
} Get the length in bytes of a Bit value |
public int getNumBitsSet() {
if (SanityManager.DEBUG) {
SanityManager.ASSERT(invariantHolds(),"broken invariant");
}
int bitsSet = 0;
final int numbytes = getLengthInBytes();
for (int i = 0; i < numbytes; ++i) {
byte v = value[i];
// "Truth table", bits set in half-nibble (2 bits):
// A | A > >1 | A-=A > >1 | bits set
// ------------------------------
// 00 | 00 | 0 | 0
// 01 | 00 | 1 | 1
// 10 | 01 | 1 | 1
// 11 | 01 | 2 | 2
// Calculate bits set in each half-nibble in parallel
// |ab|cd|ef|gh|
// - | >a|&c|&e|&g| >
// ----------------
// = |ij|kl|mn|op|
v -= ((v > > 1) & 0x55);
// Add the upper and lower half-nibbles together and store
// in each nibble
// |&&|kl|&&|op|
//+ | > >|ij|&&|mn| > >
//-----------------
//= |0q|rs|0t|uv|
v = (byte)((v & 0x33) + ((v > > 2) & 0x33));
// Add the nibbles together
// |&&&&|&tuv|
//+ | > > > >|0qrs| > > > >
//-----------------
//= |0000|wxyz|
v = (byte)((v & 0x7) + (v > > 4));
bitsSet += v;
}
return bitsSet;
} Get a count of the number of bits that are set. |
public int getTypeFormatId() {
return StoredFormatIds.BITIMPL_V01_ID;
} Get the formatID which corresponds to this class. |
public void grow(int n) {
if (SanityManager.DEBUG) {
SanityManager.ASSERT(invariantHolds(), "broken invariant");
}
if (n < 0) {
throw new IllegalArgumentException("Bit set cannot grow from "+
lengthAsBits+" to "+n+" bits");
}
if (n < = lengthAsBits) {
return;
}
int newNumBytes = FormatableBitSet.numBytesFromBits(n);
// is there enough room in the existing array
if (newNumBytes > value.length) {
/*
** We didn't have enough bytes in value, so we need
** to create a bigger byte array and use that.
*/
byte[] newValue = new byte[newNumBytes];
int oldNumBytes = getLengthInBytes();
System.arraycopy(value, 0, newValue, 0, oldNumBytes);
value = newValue;
}
bitsInLastByte = numBitsInLastByte(n);
lengthAsBits = n;
} Grow (widen) a FormatableBitSet so that it contains at least N
bits. If the bitset already has more than n bits, this is a
noop. Negative values of n are not allowed.
ASSUMPTIONS: that all extra bits in the last byte are
zero. |
public int hashCode() {
int code = 0;
int i;
int shift = 0;
int byteLength = getLengthInBytes();
for( i = 0; i < byteLength; i++)
{
code ^= (value[i] & 0xff)< < shift;
shift += 8;
if( 32 < = shift)
shift = 0;
}
return code;
} Produce a hash code by putting the value bytes into an int, exclusive OR'ing
if there are more than 4 bytes. |
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);
} 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. |
public final boolean isSet(int position) {
checkPosition(position);
final int byteIndex = udiv8(position);
final byte bitIndex = umod8(position);
return ((value[byteIndex] & (0x80 > >bitIndex)) != 0);
} |
public static int maxBitsForSpace(int numBytes) {
return (numBytes - 4)*8;
} Statically calculates how many bits can fit into the number of
bytes if this Bit object is externalized. Only valid for this
implementation of Bit. |
public void or(FormatableBitSet otherBit) {
if (otherBit == null) {
return;
}
int otherLength = otherBit.getLength();
if (otherLength > getLength()) {
grow(otherLength);
}
int obByteLen = otherBit.getLengthInBytes();
for (int i = 0; i < obByteLen; ++i) {
value[i] |= otherBit.value[i];
}
if (SanityManager.DEBUG) {
SanityManager.ASSERT(invariantHolds(),"or() broke invariant");
}
} 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. |
public void readExternal(ObjectInput in) throws IOException {
int lenInBits;
int lenInBytes;
lenInBits = in.readInt();
lenInBytes = FormatableBitSet.numBytesFromBits(lenInBits);
/*
** How can lenInBytes be zero? The implication is
** that lenInBits is zero. Well, the reason this can
** happen is that the store will reset our stream
** out from underneath us if we are a Bit column that
** overflows onto another page because it assumes that
** we want to stream it in specially. Because of this warped
** API, our readInt() will return 0 even though our
** writeExternal() did a writeInt(xxx). The upshot
** is that you should leave the following alone.
*/
value = new byte[lenInBytes];
in.readFully(value);
bitsInLastByte = numBitsInLastByte(lenInBits);
lengthAsBits = lenInBits;
} Note: gracefully handles zero length
bits -- will create a zero length array
with no bits being used. Fortunately
in.read() is ok with a zero length array
so no special code.
WARNING: this method cannot be changed w/o
changing SQLBit because SQLBit calls this
directly w/o calling read/writeObject(), so
the format id is not stored in that case. |
public void set(int position) {
checkPosition(position);
final int byteIndex = udiv8(position);
final byte bitIndex = umod8(position);
value[byteIndex] |= (0x80 > >bitIndex);
} |
public void shrink(int n) {
if (SanityManager.DEBUG) {
SanityManager.ASSERT(invariantHolds(), "broken invariant");
}
if (n < 0 || n > lengthAsBits) {
throw new
IllegalArgumentException("Bit set cannot shrink from "+
lengthAsBits+" to "+n+" bits");
}
final int firstUnusedByte = numBytesFromBits(n);
bitsInLastByte = numBitsInLastByte(n);
lengthAsBits = n;
for (int i = firstUnusedByte; i < value.length; ++i) {
value[i] = 0;
}
if (firstUnusedByte > 0) {
// Mask out any left over bits in the
// last byte. Retain the highest bits.
value[firstUnusedByte-1] &= 0xff00 > > bitsInLastByte;
}
} Shrink (narrow) a FormatableBitSet to N bits. N may not be
larger than the current bitset size, or negative. |
public int size() {
return getLength();
} Get the length in bits -- alias for getLength() |
public String toString() {
{
// give it a reasonable size
StringBuffer str = new StringBuffer(getLength()*8*3);
str.append("{");
boolean first = true;
for (int inPosition = 0; inPosition < getLength(); inPosition++)
{
if (isSet(inPosition))
{
if (!first)
str.append(", ");
first = false;
str.append(inPosition);
}
}
str.append("}");
return new String(str);
}
} Format the string into BitSet format: {0, 2, 4, 8} if bits 0, 2, 4, 8
are set. |
public void writeExternal(ObjectOutput out) throws IOException {
// never called when value is null
if (SanityManager.DEBUG)
SanityManager.ASSERT(value != null);
out.writeInt(getLength());
int byteLen = getLengthInBytes();
if (byteLen > 0)
{
out.write(value, 0, byteLen);
}
} Format:
- int length in bits
- byte[]
|
public void xor(FormatableBitSet otherBit) {
if (otherBit == null) {
return;
}
int otherLength = otherBit.getLength();
if (otherLength > getLength()) {
grow(otherLength);
}
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");
}
} 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. |
org.apache.derby.iapi.services.io.FormatableBitSet