001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026:
027: package org.cougaar.core.blackboard;
028:
029: import java.io.IOException;
030: import java.io.ObjectInputStream;
031: import java.io.ObjectOutputStream;
032: import java.io.Serializable;
033:
034: /**
035: * A bit set for keeping track of sequence numbers, used by
036: * the {@link MessageManager}.
037: * <p>
038: * This is similar to a BitSet, but has a shifting base index. The
039: * position of the first zero bit in the set can be queried and the
040: * representation shifted so that the one bits prior to that first
041: * zero don't require storage.
042: */
043: class AckSet implements Serializable {
044: /** The sequence number of the first zero bit. */
045: private int minSequence = 0;
046:
047: /** The sequence number corresponding to bit 0 of the bits array */
048: private int baseSequence = 0;
049:
050: /** The index of the last word with bits */
051: private transient int maxIndex = 0;
052:
053: /** The values of the bits */
054: private transient long[] bits = new long[4];
055:
056: /** Computed index in bits of a given sequence number */
057: private transient int index;
058:
059: /** Computed bit of a given sequence number */
060: private transient long bit;
061:
062: /**
063: * Construct with sequence numbers starting at zero.
064: */
065: public AckSet() {
066: }
067:
068: /**
069: * Construct with sequence numbers starting at a specified position.
070: * @param initialSequenceNumber the position of the first zero in
071: * the bit set.
072: */
073: public AckSet(int initialSequenceNumber) {
074: computeIndexInfo(initialSequenceNumber);
075: baseSequence = index * 64;
076: minSequence = initialSequenceNumber;
077: bits[0] = bit - 1L;
078: }
079:
080: /**
081: * Compute the index into the bits array and the bit corresponding
082: * to a given sequence number.
083: * @param sequenceNumber
084: */
085: private void computeIndexInfo(int sequenceNumber) {
086: sequenceNumber -= baseSequence;
087: index = (int) (sequenceNumber / 64);
088: int bitIndex = (int) (sequenceNumber % 64);
089: bit = 1L << bitIndex;
090: }
091:
092: /**
093: * Find the first zero in the bitset, advance minSequence to that
094: * position, and return that sequence number.
095: * @return the position of the first bit that has not be set.
096: */
097: public synchronized int advance() {
098: try {
099: computeIndexInfo(minSequence);
100: if (index >= bits.length) { // Beyond the end
101: return minSequence;
102: }
103: if ((bits[index] & bit) == 0L)
104: return minSequence;
105: while (index <= maxIndex) { // Check all the words in the array
106: long word = bits[index];
107: if (word == 0xffffffffffffffffL) {
108: bit = 1L; // All ones, advance to first bit
109: ++index; // of the next word
110: minSequence = baseSequence + index * 64;
111: } else { // Some zeros here
112: while (bit != 0x8000000000000000L
113: && (word & bit) != 0L) {
114: ++minSequence;
115: bit <<= 1;
116: }
117: return minSequence; // That's the answer
118: }
119: }
120: // All ones everywhere we looked
121: return minSequence;
122: } catch (Exception e) {
123: e.printStackTrace();
124: System.exit(13);
125: return 0;
126: }
127: }
128:
129: /**
130: * Get the current minSequence value. This is always the same as the
131: * last value returned from advance.
132: * @return the position of first zero in the set as of the last call
133: * to advance.
134: */
135: public int getMinSequence() {
136: return minSequence;
137: }
138:
139: /**
140: * Set the bit corresponding to a particular sequence number. If the
141: * word containing the bit falls beyond the end of the array, first
142: * discard the words before the word containing minSequence. Then
143: * expand the array if necessary.
144: */
145: public synchronized void set(int sequenceNumber) {
146: computeIndexInfo(sequenceNumber);
147: if (index < 0)
148: return; // These bits are already set.
149: if (index >= bits.length) { // Beyond the end
150: computeIndexInfo(minSequence); // Find out where the min is
151: if (index > 0) { // There is room to shift down
152: int nw = maxIndex - index + 1; // The number of words to retain
153: System.arraycopy(bits, index, bits, 0, nw);
154: while (nw < bits.length) {
155: bits[nw++] = 0L; // Zero vacated words
156: }
157: baseSequence += index * 64; // Advance by bits shifted
158: maxIndex -= index; // Decrease by words shifted
159: }
160: computeIndexInfo(sequenceNumber); // Re-evaluate
161: }
162: if (index >= bits.length) { // Still beyond the end?
163: long[] oldBits = bits; // Need to expand
164: bits = new long[index + 4]; // Make it a little bigger
165: // than necessary
166: System.arraycopy(oldBits, 0, bits, 0, maxIndex + 1);
167: }
168: bits[index] |= bit;
169: if (index > maxIndex) {
170: maxIndex = index;
171: }
172: }
173:
174: /**
175: * Test if a particular bit is set.
176: * @param sequenceNumber the bit to test.
177: * @return true if the specified bit has been set.
178: */
179: public boolean isSet(int sequenceNumber) {
180: if (sequenceNumber < minSequence) {
181: return true; // No need to test these
182: }
183: computeIndexInfo(sequenceNumber);
184: if (index > maxIndex) {
185: return false; // These are always zero
186: }
187: return ((bits[index] & bit) != 0L);
188: }
189:
190: /**
191: * Write this object. We only write the active portion of the bits
192: * array
193: */
194: private synchronized void writeObject(ObjectOutputStream os)
195: throws IOException {
196: os.defaultWriteObject();
197: os.writeInt(maxIndex);
198: for (int i = 0; i <= maxIndex; i++) {
199: os.writeLong(bits[i]);
200: }
201: }
202:
203: /**
204: * Read this object. The bits array is restored.
205: */
206: private void readObject(ObjectInputStream is) throws IOException,
207: ClassNotFoundException {
208: is.defaultReadObject();
209: maxIndex = is.readInt();
210: bits = new long[maxIndex + 1];
211: for (int i = 0; i <= maxIndex; i++) {
212: bits[i] = is.readLong();
213: }
214: }
215:
216: public String toString() {
217: StringBuffer buf = new StringBuffer();
218: buf.append(0);
219: boolean inRange = false;
220: int prevSeq = minSequence - 1;
221: for (int seq = minSequence;; seq++) {
222: if (isSet(seq)) {
223: if (seq != prevSeq + 1) {
224: if (inRange) {
225: buf.append(prevSeq);
226: inRange = false;
227: }
228: buf.append(",");
229: buf.append(seq);
230: prevSeq = seq;
231: } else {
232: if (!inRange) {
233: buf.append("..");
234: inRange = true;
235: }
236: prevSeq = seq;
237: }
238: } else if (index > maxIndex) {
239: break;
240: }
241: }
242: if (inRange) {
243: buf.append(prevSeq);
244: }
245: return buf.substring(0);
246: }
247: }
|