0001: /*
0002:
0003: Derby - Class org.apache.derby.iapi.services.io.FormatableBitSet
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.iapi.services.io;
0023:
0024: import org.apache.derby.iapi.services.sanity.SanityManager;
0025:
0026: import java.io.InputStream;
0027: import java.io.ObjectOutput;
0028: import java.io.ObjectInput;
0029: import java.io.IOException;
0030:
0031: /**
0032: * FormatableBitSet is implemented as a packed array of bytes.
0033: *
0034: * @author Jamie -- originally coded by Jeff
0035: */
0036:
0037: public final class FormatableBitSet implements Formatable, Cloneable {
0038:
0039: /********************************************************
0040: **
0041: ** This class implements Formatable. That means that it
0042: ** can write itself to and from a formatted stream. If
0043: ** you add more fields to this class, make sure that you
0044: ** also write/read them with the writeExternal()/readExternal()
0045: ** methods.
0046: **
0047: ** If, inbetween releases, you add more fields to this class,
0048: ** then you should bump the version number emitted by the getTypeFormatId()
0049: ** method.
0050: **
0051: ********************************************************/
0052:
0053: /**
0054: ** Bits are stored as an array of bytes.
0055: ** Bits are numbered starting at 0. Bits
0056: ** 0..7 go in byte[0], 8..15 in byte[1] and so on.
0057: ** The number of bytes is tracked as part
0058: ** of the byte array. The number of bits
0059: ** being used is derived by the number of
0060: ** bytes being used and the number of bits
0061: ** being used by the last byte. The partially
0062: ** unused byte is always byte[byte.length] with the
0063: ** lowest bits being unused.
0064: **
0065: ** Zero length bits are stored using a
0066: ** zero length byte array, with all bits
0067: ** marked as unused.
0068: */
0069: private byte[] value;
0070: private short bitsInLastByte;
0071:
0072: private transient int lengthAsBits;
0073:
0074: /**
0075: * Niladic Constructor
0076: */
0077: public FormatableBitSet() {
0078: }
0079:
0080: /**
0081: * Constructs a Bit with the initial number of bits
0082: */
0083: public FormatableBitSet(int numBits) {
0084: initializeBits(numBits);
0085: }
0086:
0087: private void initializeBits(int numBits) {
0088: int numBytes = numBytesFromBits(numBits);
0089:
0090: // the byte array is zero'ed out by the new operator
0091: value = new byte[numBytes];
0092: bitsInLastByte = numBitsInLastByte(numBits);
0093: lengthAsBits = numBits;
0094: }
0095:
0096: /**
0097: * Constructs a Bit from an array of bytes. Assume
0098: * bytes are all being used.
0099: *
0100: * @param newValue The array of bytes to make up the new Bit
0101: */
0102: public FormatableBitSet(byte[] newValue) {
0103: value = newValue;
0104: bitsInLastByte = 8;
0105: lengthAsBits = calculateLength(newValue.length);
0106: }
0107:
0108: /**
0109: * Constructs a Bit from an array of bytes.
0110: *
0111: * @param newValue The array of bytes to make up the new Bit
0112: * @param numBits The number of bits
0113: */
0114: public FormatableBitSet(byte[] newValue, int numBits) {
0115: bitsInLastByte = numBitsInLastByte(numBits);
0116: lengthAsBits = numBits;
0117:
0118: int lenInBytes = numBytesFromBits(numBits);
0119:
0120: if (lenInBytes == newValue.length) {
0121: value = newValue;
0122: } else {
0123: value = new byte[lenInBytes];
0124: System.arraycopy(newValue, 0, value, 0, newValue.length);
0125: }
0126: }
0127:
0128: /**
0129: * Copy constructor
0130: *
0131: * @param original the FormatableBitSet to make a copy from
0132: */
0133: public FormatableBitSet(FormatableBitSet original) {
0134: if (SanityManager.DEBUG)
0135: SanityManager.ASSERT(original != null,
0136: "cannot make copy from a null FormatableBitSet");
0137:
0138: bitsInLastByte = original.bitsInLastByte;
0139: lengthAsBits = original.lengthAsBits;
0140:
0141: int lenInBytes = FormatableBitSet
0142: .numBytesFromBits(original.lengthAsBits);
0143: value = new byte[lenInBytes];
0144: if (lenInBytes > 0)
0145: System.arraycopy(original.value, 0, value, 0, lenInBytes);
0146: }
0147:
0148: /*
0149: * Cloneable
0150: */
0151: public Object clone() {
0152: return new FormatableBitSet(this );
0153: }
0154:
0155: /**
0156: * Get the length in bytes of a Bit value
0157: *
0158: * @return The length in bytes of this value
0159: */
0160: public int getLengthInBytes() {
0161: if (value == null) {
0162: return 0;
0163: }
0164:
0165: return FormatableBitSet.numBytesFromBits(lengthAsBits);
0166: }
0167:
0168: /**
0169: ** Get the length in bits
0170: **
0171: ** @return The length in bits for this value
0172: **
0173: ** NOTE: could possibly be changed to a long. As is
0174: ** we are restricted to 2^(31-3) -> 256meg instead
0175: ** of 2^31 (Integer.MAX_VALUE) like other datatypes
0176: ** (or 2 gig). If it is ever changed to a long
0177: ** be sure to change read/writeExternal which write
0178: ** out the length in bits.
0179: */
0180: public int getLength() {
0181: return lengthAsBits;
0182: }
0183:
0184: private int calculateLength(int realByteLength) {
0185: if (realByteLength == 0) {
0186: return 0;
0187: }
0188:
0189: return ((realByteLength - 1) * 8) + bitsInLastByte;
0190: }
0191:
0192: /**
0193: * Get the length in bits -- alias for getLength()
0194: *
0195: * @return The length in bits for this value
0196: */
0197: public int size() {
0198: return getLength();
0199: }
0200:
0201: /**
0202: * Get the value of the byte array
0203: *
0204: * @return The value of the byte array
0205: */
0206:
0207: public byte[] getByteArray() {
0208: if (value == null)
0209: return null;
0210:
0211: // In some cases the array is bigger than the actual number
0212: // of valid bytes.
0213: int realByteLength = getLengthInBytes();
0214:
0215: // Currently the case is that the return from this
0216: // call only includes the valid bytes.
0217: if (value.length != realByteLength) {
0218: byte[] data = new byte[realByteLength];
0219: System.arraycopy(value, 0, data, 0, realByteLength);
0220:
0221: value = data;
0222: }
0223:
0224: return value;
0225: }
0226:
0227: /**
0228: * Set the value of the byte array
0229: *
0230: * @return The value of the byte array
0231: */
0232: public boolean isNull() {
0233: return this .value == null;
0234: }
0235:
0236: /**
0237: * Grow (widen) a FormatableBitSet to N bis
0238: *
0239: * @param n The number of bits you want. The bits are
0240: * always added as 0 and are appended to the
0241: * least significant end of the bit array.
0242: *
0243: * ASSUMPTIONS: that all extra bits in the last byte
0244: * are zero.
0245: */
0246: public void grow(int n) {
0247: if (n <= this .getLength())
0248: return;
0249:
0250: if (value == null) {
0251: initializeBits(n);
0252: return;
0253: }
0254:
0255: int delta = n - this .getLength();
0256:
0257: int oldNumBytes = getLengthInBytes();
0258:
0259: /*
0260: ** If we have enough space in the left over bits,
0261: ** then all we need to do is change the modulo.
0262: */
0263: if ((oldNumBytes != 0) && (8 - this .bitsInLastByte) >= delta) {
0264: this .bitsInLastByte += delta;
0265: lengthAsBits = n;
0266: return;
0267: }
0268:
0269: int newNumBytes = FormatableBitSet.numBytesFromBits(n);
0270:
0271: // is there enough room in the existing array
0272: if (newNumBytes <= value.length) {
0273: // ensure the bits are zeroed
0274: for (int i = oldNumBytes; i < newNumBytes; i++)
0275: value[i] = 0;
0276: } else {
0277:
0278: /*
0279: ** We didn't have enough bytes in value, so we need
0280: ** to create a bigger byte array and use that.
0281: */
0282: byte[] newValue = new byte[newNumBytes];
0283:
0284: System.arraycopy(value, 0, newValue, 0, oldNumBytes);
0285:
0286: value = newValue;
0287: }
0288: bitsInLastByte = numBitsInLastByte(n);
0289: lengthAsBits = n;
0290: }
0291:
0292: /**
0293: * Shrink (narrow) a FormatableBitSet to N bits
0294: *
0295: * @param n The number of bits the caller wants. The
0296: * bits are always removed from the
0297: * least significant end of the bit array.
0298: */
0299: public FormatableBitSet shrink(int n) {
0300: int numBytes;
0301: int lastByteNum;
0302:
0303: /*
0304: ** Sanity check: we shouldn't shrink down to
0305: ** nothing.
0306: */
0307: if (SanityManager.DEBUG) {
0308: if (value == null) {
0309: SanityManager
0310: .THROWASSERT("Attempt to shrink a null Bit"
0311: + " -- caller should have known better probably");
0312: return null;
0313: }
0314: }
0315:
0316: if (n >= this .getLength()) {
0317: return this ;
0318: }
0319:
0320: lastByteNum = numBytesFromBits(n) - 1;
0321: bitsInLastByte = numBitsInLastByte(n);
0322: lengthAsBits = n;
0323:
0324: /*
0325: ** Mask out any left over bits in the
0326: ** last byte. Retain the highest bits.
0327: */
0328: if (bitsInLastByte != 8) {
0329: value[lastByteNum] &= 0xFF00 >> bitsInLastByte;
0330: }
0331:
0332: return this ;
0333: }
0334:
0335: /*
0336: ** Some of the operators required by SQL. These could alternatively
0337: ** be in SQLBit, but since they are so tightly bound to the implementation
0338: ** rather than return something that undermines the encapsulation
0339: ** of this type, i have chosen to put them in here.
0340: */
0341:
0342: /**
0343: * Bit equivalence. Compare this with other.
0344: * If the length is different, then cannot be
0345: * equal so short circuit. Otherwise, rely on
0346: * compare(). Note that two zero length bits are
0347: * considered equal.
0348: *
0349: * @param other the other bit to compare to
0350: *
0351: * @return TRUE|FALSE
0352: */
0353: public boolean equals(FormatableBitSet other) {
0354: if (this .getLength() != other.getLength()) {
0355: return false;
0356: }
0357:
0358: return (this .compare(other) == 0);
0359: }
0360:
0361: /**
0362: * Bit comparison. Compare this with other.
0363: * Will always do a byte by byte compare.
0364: *
0365: * Given 2 similar bits of unequal lengths (x and y),
0366: * where x.getLength() < y.getLength() but where:
0367: *
0368: * x[0..x.getLength()] == y[0..x.getLength()]
0369: *
0370: * then x < y.
0371: *
0372: *
0373: * @param other the other bit to compare to
0374: *
0375: * @return -1 - if other < this
0376: * 0 - if other == this
0377: * 1 - if other > this
0378: *
0379: */
0380: public int compare(FormatableBitSet other) {
0381:
0382: int otherCount, this Count;
0383: int otherLen, this Len;
0384: byte[] otherb;
0385:
0386: otherb = other.value;
0387: /*
0388: ** By convention, nulls sort low, and null == null
0389: */
0390: if (this .value == null || otherb == null) {
0391: if (this .value != null) // otherb == null
0392: return 1;
0393: if (otherb != null) // this.value == null
0394: return -1;
0395: return 0; // both null
0396: }
0397:
0398: otherLen = other.getLengthInBytes();
0399: this Len = getLengthInBytes();
0400: for (otherCount = 0, this Count = 0; otherCount < otherLen
0401: && this Count < this Len; otherCount++, this Count++) {
0402: if (otherb[otherCount] != this .value[this Count])
0403: break;
0404: }
0405:
0406: /*
0407: ** '==' if byte by byte comparison is identical and
0408: ** exact same length in bits (not bytes).
0409: */
0410: if ((otherCount == otherLen) && (this Count == this Len)) {
0411: if (this .getLength() == other.getLength()) {
0412: return 0;
0413: }
0414:
0415: /*
0416: ** If subset of bits is identical, return 1
0417: ** if other.getLength() > this.getLength(); otherwise,
0418: ** -1
0419: */
0420: return (other.getLength() < this .getLength()) ? 1 : -1;
0421: }
0422:
0423: if (otherCount == otherLen) {
0424: return 1;
0425: } else if (this Count == this Len) {
0426: return -1;
0427: } else {
0428: /*
0429: ** Ok, we have a difference somewhere. Now
0430: ** we have to go to the trouble of converting
0431: ** to a int and masking out the sign to get
0432: ** a valid comparision because bytes are signed.
0433: */
0434: int otherInt, this Int;
0435:
0436: otherInt = (int) otherb[otherCount];
0437: otherInt &= (0x100 - 1);
0438:
0439: this Int = (int) this .value[this Count];
0440: this Int &= (0x100 - 1);
0441:
0442: return (this Int > otherInt) ? 1 : -1;
0443:
0444: }
0445: }
0446:
0447: /**
0448: * Bit concatenation.
0449: *
0450: * @param other the other bit to append to this
0451: *
0452: * @return Bit -- the newly concatenated bit
0453: *
0454: */
0455: public FormatableBitSet concatenate(FormatableBitSet other) {
0456: int newLen;
0457: int otherLen;
0458: int prevLen;
0459: int prevLenBytes;
0460: int newLenBytes;
0461: int otherLenBytes;
0462: int i, j;
0463: byte[] newValue;
0464: byte[] otherValue;
0465: int shiftBits;
0466: int inByte;
0467:
0468: prevLen = this .getLength();
0469: prevLenBytes = this .getLengthInBytes();
0470: otherLen = other.getLength();
0471: otherValue = other.getByteArray();
0472: otherLenBytes = other.getLengthInBytes();
0473: newLen = prevLen + otherLen;
0474: newLenBytes = numBytesFromBits(newLen);
0475: newValue = new byte[newLenBytes];
0476:
0477: /*
0478: ** Copy over the entire array in this.value
0479: ** to newLenBytes.
0480: */
0481: for (i = 0; i < prevLenBytes; i++) {
0482: newValue[i] = this .value[i];
0483: }
0484:
0485: /*
0486: ** Now if we have any bits left over
0487: ** we need to shift them, and keep
0488: ** shifting everything down. Be careful
0489: ** to handle the case where the bit
0490: ** used to have length 0.
0491: */
0492: shiftBits = (prevLen == 0) ? 8 : this .bitsInLastByte;
0493: for (j = 0; j < otherLenBytes; j++, i++) {
0494: if (shiftBits == 8) {
0495: newValue[i] = otherValue[j];
0496: } else {
0497: /*
0498: ** Convert to an int because it will get converted
0499: ** on the shift anyway.
0500: */
0501: inByte = (int) otherValue[j];
0502:
0503: /*
0504: ** Mask off the high bits in case they are now
0505: ** turned on if we had the sign bit on.
0506: */
0507: inByte &= (0x100 - 1);
0508:
0509: /*
0510: ** Use the high order bits to finish off
0511: ** the last byte
0512: */
0513: newValue[i - 1] |= (inByte >>> shiftBits);
0514:
0515: /*
0516: ** Start the next one with whatever is left, unless
0517: ** there is nothing left.
0518: */
0519: if (i < newLenBytes) {
0520: newValue[i] |= (inByte << (8 - shiftBits));
0521: }
0522: }
0523: }
0524:
0525: return new FormatableBitSet(newValue, newLen);
0526: }
0527:
0528: /**
0529: * Produce a hash code by putting the value bytes into an int, exclusive OR'ing
0530: * if there are more than 4 bytes.
0531: *
0532: * @return the hash code
0533: */
0534: public int hashCode() {
0535: if (null == value)
0536: return 0;
0537:
0538: int code = 0;
0539: int i;
0540: int shift = 0;
0541:
0542: int byteLength = getLengthInBytes();
0543: for (i = 0; i < byteLength; i++) {
0544: code ^= (value[i] & 0xff) << shift;
0545: shift += 8;
0546: if (32 <= shift)
0547: shift = 0;
0548: }
0549: return code;
0550: }
0551:
0552: /**
0553: * Bit isSet
0554: *
0555: * @param position the bit to check
0556: *
0557: */
0558: public final boolean isSet(int position) {
0559: if (SanityManager.DEBUG) {
0560: if (position >= this .getLength()) {
0561: SanityManager
0562: .THROWASSERT("Attempt to get a bit position ("
0563: + position + ")"
0564: + "that exceeds the max length ("
0565: + this .getLength() + ")");
0566: }
0567: }
0568:
0569: try {
0570:
0571: int bytepos = position / 8;
0572: int bitpos = 7 - (position % 8);
0573:
0574: return ((value[bytepos] & (1 << bitpos)) != 0);
0575:
0576: } catch (ArrayIndexOutOfBoundsException e) {
0577: // Should not happen, handle it just in case not all cases are tested
0578: // by insane server.
0579: return false;
0580: }
0581: }
0582:
0583: /**
0584: * Bit get -- alias for isSet()
0585: *
0586: * @param position the bit to check
0587: *
0588: */
0589: public final boolean get(int position) {
0590: return isSet(position);
0591: }
0592:
0593: /**
0594: * Bit set
0595: *
0596: * @param position the bit to set
0597: *
0598: */
0599: public void set(int position) {
0600:
0601: if (SanityManager.DEBUG) {
0602: if (position >= this .getLength()) {
0603: SanityManager
0604: .THROWASSERT("Attempt to set a bit position that exceeds the max length ("
0605: + this .getLength() + ")");
0606: }
0607: }
0608:
0609: // Should not happen, handle it just in case not all cases are tested
0610: // by insane server.
0611: if (position >= getLength())
0612: grow(position);
0613:
0614: int bytepos = position / 8;
0615: int bitpos = 7 - (position % 8);
0616:
0617: value[bytepos] |= (1 << bitpos);
0618: }
0619:
0620: /**
0621: * Bit clear
0622: *
0623: * @param position the bit to clear
0624: *
0625: */
0626: public void clear(int position) {
0627: int bytepos;
0628: int bitpos;
0629:
0630: if (SanityManager.DEBUG) {
0631: if (position >= this .getLength()) {
0632: SanityManager
0633: .THROWASSERT("Attempt to set a bit position that exceeds the max length ("
0634: + this .getLength() + ")");
0635: }
0636: }
0637:
0638: // Should not happen, handle it just in case not all cases are tested
0639: // by insane server.
0640: if (position >= getLength())
0641: grow(position);
0642:
0643: bytepos = position / 8;
0644: bitpos = 7 - (position % 8);
0645:
0646: value[bytepos] &= ~(1 << bitpos);
0647: }
0648:
0649: /**
0650: Clear all the bits in this FormatableBitSet
0651: */
0652: public void clear() {
0653: if (value == null)
0654: return;
0655:
0656: int byteLength = getLengthInBytes();
0657: for (int ix = 0; ix < byteLength; ix++)
0658: value[ix] = 0;
0659: }
0660:
0661: /**
0662: * Figure out how many bytes are needed to
0663: * store the input number of bits.
0664: *
0665: * @param bits bits
0666: *
0667: * @return the number of bytes
0668: */
0669: protected static int numBytesFromBits(int bits) {
0670: return (bits == 0) ? 0 : ((bits - 1) / 8) + 1;
0671: }
0672:
0673: /**
0674: * Figure out how many bits are in the last
0675: * byte from the total number of bits.
0676: *
0677: * @param bits bits
0678: *
0679: * @return the number of bits
0680: */
0681: private static short numBitsInLastByte(int bits) {
0682: int modulo = bits % 8;
0683: return (short) ((modulo == 0) ? ((bits == 0) ? 0 : 8) : modulo);
0684: }
0685:
0686: /**
0687: * Translate a hex character to a byte.
0688: *
0689: * @param hexChar A character with the value [0-9a-fA-F].
0690: *
0691: * @return A byte with the numeric value corresponding to the hex character
0692: */
0693: private static byte hexCharToByte(char hexChar) {
0694: byte byteValue;
0695:
0696: switch (hexChar) {
0697: case '0':
0698: byteValue = 0;
0699: break;
0700:
0701: case '1':
0702: byteValue = 1;
0703: break;
0704:
0705: case '2':
0706: byteValue = 2;
0707: break;
0708:
0709: case '3':
0710: byteValue = 3;
0711: break;
0712:
0713: case '4':
0714: byteValue = 4;
0715: break;
0716:
0717: case '5':
0718: byteValue = 5;
0719: break;
0720:
0721: case '6':
0722: byteValue = 6;
0723: break;
0724:
0725: case '7':
0726: byteValue = 7;
0727: break;
0728:
0729: case '8':
0730: byteValue = 8;
0731: break;
0732:
0733: case '9':
0734: byteValue = 9;
0735: break;
0736:
0737: case 'a':
0738: case 'A':
0739: byteValue = 0xA;
0740: break;
0741:
0742: case 'b':
0743: case 'B':
0744: byteValue = 0xB;
0745: break;
0746:
0747: case 'c':
0748: case 'C':
0749: byteValue = 0xC;
0750: break;
0751:
0752: case 'd':
0753: case 'D':
0754: byteValue = 0xD;
0755: break;
0756:
0757: case 'e':
0758: case 'E':
0759: byteValue = 0xE;
0760: break;
0761:
0762: case 'f':
0763: case 'F':
0764: byteValue = 0xF;
0765: break;
0766:
0767: default:
0768: if (SanityManager.DEBUG) {
0769: SanityManager.THROWASSERT("illegal char = " + hexChar);
0770: }
0771: throw new IllegalArgumentException();
0772: }
0773:
0774: return byteValue;
0775: }
0776:
0777: private static char[] decodeArray = { '0', '1', '2', '3', '4', '5',
0778: '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
0779:
0780: /**
0781: * Format the string into BitSet format: {0, 2, 4, 8} if bits 0, 2, 4, 8
0782: * are set.
0783: *
0784: * @return A new String containing the formatted Bit value
0785: */
0786: public String toString() {
0787: char[] outChars;
0788: int inPosition;
0789: int outPosition;
0790: int inByte;
0791:
0792: if (value == null) {
0793: return null;
0794: }
0795: {
0796: // give it a reasonable size
0797: StringBuffer str = new StringBuffer(getLength() * 8 * 3);
0798: str.append("{");
0799: boolean first = true;
0800: for (inPosition = 0; inPosition < getLength(); inPosition++) {
0801: if (isSet(inPosition)) {
0802: if (!first)
0803: str.append(", ");
0804: first = false;
0805: str.append(inPosition);
0806: }
0807: }
0808: str.append("}");
0809: return new String(str);
0810: }
0811: }
0812:
0813: /**
0814: * Statically calculates how many bits can fit into the number of
0815: * bytes if this Bit object is externalized. Only valid for this
0816: * implementation of Bit.
0817: */
0818: public static int maxBitsForSpace(int numBytes) {
0819: return (numBytes - 4) * 8;
0820:
0821: }
0822:
0823: /**
0824: * If any bit is set, return the bit number of a bit that is set.
0825: * If no bit is set, return -1;
0826: *
0827: * @return the bit number of a bit that is set, or -1 if no bit is set
0828: */
0829: public int anySetBit() {
0830: int numbytes = getLengthInBytes();
0831: int bitpos;
0832:
0833: for (int i = 0; i < numbytes - 1; i++) {
0834: if (value[i] != 0) {
0835: for (int j = 0; j < 8; j++) {
0836: bitpos = 7 - j;
0837: if (((1 << bitpos) & value[i]) != 0)
0838: return ((i * 8) + j);
0839: }
0840: }
0841: }
0842:
0843: // only the top part of the last byte is relevant
0844: byte mask = (byte) (0xFF << (8 - bitsInLastByte));
0845: if ((value[numbytes - 1] & mask) != 0) {
0846: for (int j = 0; j < bitsInLastByte; j++) {
0847: bitpos = 7 - j;
0848: if (((1 << bitpos) & value[numbytes - 1]) != 0)
0849: return ((numbytes - 1) * 8) + j;
0850: }
0851: }
0852:
0853: return -1;
0854: }
0855:
0856: /**
0857: * Like anySetBit(), but return any set bit whose number is bigger than
0858: * beyondBit. If no bit is set after beyondBit, -1 is returned.
0859: * By using anySetBit() and anySetBit(beyondBit), one can quickly go
0860: * thru the entire bit array to return all set bit.
0861: *
0862: * @param beyondBit only look at bit that is greater than this bit number
0863: * @return the bit number of a bit that is set, or -1 if no bit after
0864: * beyondBit is set
0865: */
0866: public int anySetBit(int beyondBit) {
0867: if (SanityManager.DEBUG) {
0868: if (beyondBit >= this .getLength())
0869: SanityManager
0870: .THROWASSERT("Attempt to access bit position that exceeds the max length ("
0871: + this .getLength() + ")");
0872: }
0873:
0874: int startingBit = (beyondBit + 1);
0875:
0876: // we have seen the last bit.
0877: if (startingBit >= this .getLength())
0878: return -1;
0879:
0880: int numbytes = getLengthInBytes();
0881: int startingByte = startingBit / 8;
0882: int startingBitpos = startingBit % 8;
0883: int bitpos;
0884: byte mask;
0885:
0886: // see if any bits in this byte is set, only the bottom part of the
0887: // first byte is relevant
0888: mask = (byte) (0xFF >> startingBitpos);
0889:
0890: if (startingByte == numbytes - 1) // starting byte == last byte
0891: mask &= (byte) (0xFF << (8 - bitsInLastByte));
0892:
0893: if ((value[startingByte] & mask) != 0) {
0894: // I know we will see the bit before bitsInLastByte even if we are
0895: // at the last byte, no harm in going up to 8 in the loop
0896: for (int j = startingBitpos; j < 8; j++) {
0897: if (SanityManager.DEBUG) {
0898: if (startingByte == numbytes - 1)
0899: SanityManager.ASSERT(j < bitsInLastByte,
0900: "going beyond the last bit");
0901: }
0902: bitpos = 7 - j;
0903: if (((1 << bitpos) & value[startingByte]) != 0) {
0904: return (startingByte * 8 + j);
0905: }
0906: }
0907: }
0908:
0909: for (int i = (startingByte + 1); i < numbytes - 1; i++) {
0910: if (value[i] != 0) {
0911: for (int j = 0; j < 8; j++) {
0912: bitpos = 7 - j;
0913: if (((1 << bitpos) & value[i]) != 0) {
0914: return ((i * 8) + j);
0915: }
0916: }
0917: }
0918: }
0919:
0920: // Last byte if there are more than one bytes. Only the top part of
0921: // the last byte is relevant
0922: if (startingByte != numbytes - 1) {
0923: mask = (byte) (0xFF << (8 - bitsInLastByte));
0924:
0925: if ((value[numbytes - 1] & mask) != 0) {
0926: for (int j = 0; j < bitsInLastByte; j++) {
0927: bitpos = 7 - j;
0928: if (((1 << bitpos) & value[numbytes - 1]) != 0) {
0929: return ((numbytes - 1) * 8) + j;
0930: }
0931: }
0932: }
0933: }
0934:
0935: return -1;
0936:
0937: }
0938:
0939: /**
0940: * Bitwise OR this Bit with another Bit.
0941: *
0942: * @param otherBit the other Bit
0943: */
0944: public void or(FormatableBitSet otherBit) {
0945: if (otherBit == null || otherBit.getLength() == 0)
0946: return;
0947:
0948: int otherLength = otherBit.getLength();
0949:
0950: if (otherLength > getLength())
0951: grow(otherLength); // expand this bit
0952:
0953: if (otherBit instanceof FormatableBitSet) {
0954: // we know the bit ordering, optimize this
0955: FormatableBitSet ob = (FormatableBitSet) otherBit;
0956: int obByteLen = ob.getLengthInBytes();
0957: for (int i = 0; i < obByteLen - 1; i++)
0958: value[i] |= ob.value[i];
0959:
0960: // do the last byte bit by bit
0961: for (int i = (obByteLen - 1) * 8; i < otherLength; i++)
0962: if (otherBit.isSet(i))
0963: set(i);
0964: } else {
0965: // we don't know the bit ordering, call thru the interface and go
0966: // thru bit by bit
0967: // this bit impl's length >= other bit's length
0968:
0969: for (int i = 0; i < otherLength; i++) {
0970: if (otherBit.isSet(i))
0971: set(i);
0972: }
0973: }
0974: }
0975:
0976: /**
0977: * Bitwise AND this Bit with another Bit.
0978: *
0979: * @param otherBit the other Bit
0980: */
0981: public void and(FormatableBitSet otherBit) {
0982: if (SanityManager.DEBUG)
0983: SanityManager.ASSERT(otherBit != null,
0984: "cannot AND null with a FormatableBitSet");
0985:
0986: int otherLength = otherBit.getLength();
0987:
0988: // Supposedly cannot happen, but handle it just in case.
0989: if (otherLength > getLength())
0990: grow(otherLength); // expand this bit
0991:
0992: if (otherLength < getLength()) {
0993: // clear all bits that are not in the other bit
0994: int startingByte = (otherLength * 8) + 1;
0995: int len = getLengthInBytes();
0996: for (int i = startingByte; i < len; i++)
0997: value[i] = 0;
0998:
0999: for (int i = otherLength; i < startingByte * 8; i++) {
1000: if (i < getLength())
1001: clear(i);
1002: else
1003: break;
1004: }
1005: }
1006:
1007: if (otherLength == 0)
1008: return;
1009:
1010: int length = otherBit.getLengthInBytes() < getLengthInBytes() ? otherBit
1011: .getLengthInBytes()
1012: : getLengthInBytes();
1013:
1014: for (int i = 0; i < length; i++)
1015: value[i] &= otherBit.value[i];
1016: }
1017:
1018: /**
1019: * Logically XORs this FormatableBitSet with the specified FormatableBitSet.
1020: * @param set The FormatableBitSet to be XORed with.
1021: */
1022: public void xor(FormatableBitSet set) {
1023: if (SanityManager.DEBUG) {
1024: if (getLength() != set.getLength()) {
1025: SanityManager.THROWASSERT("getLength() (" + getLength()
1026: + ") and set.getLength() (" + set.getLength()
1027: + ") expected to be the same");
1028: }
1029: }
1030:
1031: int setLength = set.getLength();
1032: for (int i = setLength; i-- > 0;) {
1033: if (isSet(i) && set.isSet(i)) {
1034: clear(i);
1035: } else if (isSet(i) || set.isSet(i)) {
1036: set(i);
1037: }
1038: }
1039: }
1040:
1041: /**
1042: * Get a count of the number of bits that are set.
1043: *
1044: * @return The number of bits that are set.
1045: */
1046: public int getNumBitsSet() {
1047: int count = 0;
1048:
1049: for (int index = getLength() - 1; index >= 0; index--) {
1050: if (isSet(index)) {
1051: count++;
1052: }
1053: }
1054:
1055: return count;
1056: }
1057:
1058: /////////////////////////////////////////////////////////
1059: //
1060: // EXTERNALIZABLE
1061: //
1062: /////////////////////////////////////////////////////////
1063: /**
1064: * Format: <UL>
1065: * <LI>int length in bits </LI>
1066: * <LI>byte[] </LI></UL>
1067: *
1068: * @see java.io.Externalizable#writeExternal
1069: */
1070: public void writeExternal(ObjectOutput out) throws IOException {
1071: // never called when value is null
1072: if (SanityManager.DEBUG)
1073: SanityManager.ASSERT(value != null);
1074:
1075: out.writeInt(getLength());
1076: int byteLen = getLengthInBytes();
1077: if (byteLen > 0) {
1078: out.write(value, 0, byteLen);
1079: }
1080: }
1081:
1082: /**
1083: * Note: gracefully handles zero length
1084: * bits -- will create a zero length array
1085: * with no bits being used. Fortunately
1086: * in.read() is ok with a zero length array
1087: * so no special code.
1088: * <p>
1089: * WARNING: this method cannot be changed w/o
1090: * changing SQLBit because SQLBit calls this
1091: * directly w/o calling read/writeObject(), so
1092: * the format id is not stored in that case.
1093: *
1094: * @see java.io.Externalizable#readExternal
1095: */
1096: public void readExternal(ObjectInput in) throws IOException {
1097: int lenInBits;
1098: int lenInBytes;
1099:
1100: lenInBits = in.readInt();
1101:
1102: lenInBytes = FormatableBitSet.numBytesFromBits(lenInBits);
1103:
1104: /*
1105: ** How can lenInBytes be zero? The implication is
1106: ** that lenInBits is zero. Well, the reason this can
1107: ** happen is that the store will reset our stream
1108: ** out from underneath us if we are a Bit column that
1109: ** overflows onto another page because it assumes that
1110: ** we want to stream it in specially. Because of this warped
1111: ** API, our readInt() will return 0 even though our
1112: ** writeExternal() did a writeInt(xxx). The upshot
1113: ** is that you should leave the following alone.
1114: */
1115:
1116: value = new byte[lenInBytes];
1117:
1118: in.readFully(value);
1119:
1120: bitsInLastByte = numBitsInLastByte(lenInBits);
1121:
1122: lengthAsBits = lenInBits;
1123: }
1124:
1125: public void readExternalFromArray(ArrayInputStream in)
1126: throws IOException {
1127: int lenInBits = in.readInt();
1128:
1129: int lenInBytes = FormatableBitSet.numBytesFromBits(lenInBits);
1130:
1131: value = new byte[lenInBytes];
1132:
1133: in.readFully(value);
1134:
1135: bitsInLastByte = numBitsInLastByte(lenInBits);
1136:
1137: lengthAsBits = lenInBits;
1138: }
1139:
1140: /**
1141: * Get the formatID which corresponds to this class.
1142: *
1143: * @return the formatID of this class
1144: */
1145: public int getTypeFormatId() {
1146: return StoredFormatIds.BITIMPL_V01_ID;
1147: }
1148: }
|