001: /**
002: *
003: */package org.drools.util;
004:
005: import org.drools.common.InternalFactHandle;
006: import org.drools.reteoo.ReteTuple;
007: import org.drools.reteoo.TupleMemory;
008:
009: public class TupleIndexHashTable extends AbstractHashTable implements
010: TupleMemory {
011:
012: private static final long serialVersionUID = 400L;
013:
014: public static final int PRIME = 31;
015:
016: private int startResult;
017:
018: private FieldIndexHashTableIterator tupleValueIterator;
019: private FieldIndexHashTableFullIterator tupleValueFullIterator;
020:
021: private int factSize;
022:
023: private Index index;
024:
025: public TupleIndexHashTable(final FieldIndex[] index) {
026: this (16, 0.75f, index);
027: }
028:
029: public TupleIndexHashTable(final int capacity,
030: final float loadFactor, final FieldIndex[] index) {
031: super (capacity, loadFactor);
032:
033: this .startResult = TupleIndexHashTable.PRIME;
034: for (int i = 0, length = index.length; i < length; i++) {
035: this .startResult += TupleIndexHashTable.PRIME
036: * this .startResult
037: + index[i].getExtractor().getIndex();
038: }
039:
040: switch (index.length) {
041: case 0:
042: throw new IllegalArgumentException(
043: "FieldIndexHashTable cannot use an index[] of length 0");
044: case 1:
045: this .index = new SingleIndex(index, this .startResult);
046: break;
047: case 2:
048: this .index = new DoubleCompositeIndex(index,
049: this .startResult);
050: break;
051: case 3:
052: this .index = new TripleCompositeIndex(index,
053: this .startResult);
054: break;
055: default:
056: throw new IllegalArgumentException(
057: "FieldIndexHashTable cannot use an index[] of length great than 3");
058: }
059: }
060:
061: public Iterator iterator() {
062: if (this .tupleValueFullIterator == null) {
063: this .tupleValueFullIterator = new FieldIndexHashTableFullIterator(
064: this );
065: }
066: this .tupleValueFullIterator.reset();
067: return this .tupleValueFullIterator;
068: }
069:
070: public Iterator iterator(final InternalFactHandle handle) {
071: if (this .tupleValueIterator == null) {
072: this .tupleValueIterator = new FieldIndexHashTableIterator();
073: }
074: final FieldIndexEntry entry = get(handle);
075: this .tupleValueIterator.reset((entry != null) ? entry.first
076: : null);
077: return this .tupleValueIterator;
078: }
079:
080: public boolean isIndexed() {
081: return true;
082: }
083:
084: public Index getIndex() {
085: return this .index;
086: }
087:
088: public Entry getBucket(final Object object) {
089: final int hashCode = this .index.hashCodeOf(object);
090: final int index = indexOf(hashCode, this .table.length);
091:
092: return this .table[index];
093: }
094:
095: /**
096: * Fast re-usable iterator
097: *
098: */
099: public static class FieldIndexHashTableIterator implements Iterator {
100: private Entry entry;
101:
102: public FieldIndexHashTableIterator() {
103:
104: }
105:
106: /* (non-Javadoc)
107: * @see org.drools.util.Iterator#next()
108: */
109: public Object next() {
110: final Entry current = this .entry;
111: this .entry = (this .entry != null) ? this .entry.getNext()
112: : null;
113: return current;
114: }
115:
116: /* (non-Javadoc)
117: * @see org.drools.util.Iterator#reset()
118: */
119: public void reset(final Entry entry) {
120: this .entry = entry;
121: }
122: }
123:
124: public static class FieldIndexHashTableFullIterator implements
125: Iterator {
126: private AbstractHashTable hashTable;
127: private Entry[] table;
128: private int row;
129: private int length;
130: private Entry entry;
131:
132: public FieldIndexHashTableFullIterator(
133: final AbstractHashTable hashTable) {
134: this .hashTable = hashTable;
135: }
136:
137: /* (non-Javadoc)
138: * @see org.drools.util.Iterator#next()
139: */
140: public Object next() {
141: if (this .entry == null) {
142: // keep skipping rows until we come to the end, or find one that is populated
143: while (this .entry == null) {
144: this .row++;
145: if (this .row == this .length) {
146: return null;
147: }
148: this .entry = (this .table[this .row] != null) ? ((FieldIndexEntry) this .table[this .row]).first
149: : null;
150: }
151: } else {
152: this .entry = this .entry.getNext();
153: if (this .entry == null) {
154: this .entry = (Entry) next();
155: }
156: }
157:
158: return this .entry;
159: }
160:
161: /* (non-Javadoc)
162: * @see org.drools.util.Iterator#reset()
163: */
164: public void reset() {
165: this .table = this .hashTable.getTable();
166: this .length = this .table.length;
167: this .row = -1;
168: this .entry = null;
169: }
170: }
171:
172: public Entry[] toArray() {
173: Entry[] result = new Entry[this .factSize];
174: int index = 0;
175: for (int i = 0; i < this .table.length; i++) {
176: FieldIndexEntry fieldIndexEntry = (FieldIndexEntry) this .table[i];
177: while (fieldIndexEntry != null) {
178: Entry entry = fieldIndexEntry.getFirst();
179: while (entry != null) {
180: result[index++] = entry;
181: entry = entry.getNext();
182: }
183: fieldIndexEntry = (FieldIndexEntry) fieldIndexEntry
184: .getNext();
185: }
186: }
187: return result;
188: }
189:
190: public void add(final ReteTuple tuple) {
191: final FieldIndexEntry entry = getOrCreate(tuple);
192: entry.add(tuple);
193: this .factSize++;
194: }
195:
196: public boolean add(final ReteTuple tuple, final boolean checkExists) {
197: throw new UnsupportedOperationException(
198: "FieldIndexHashTable does not support add(ReteTuple tuple, boolean checkExists)");
199: }
200:
201: public ReteTuple remove(final ReteTuple tuple) {
202: final int hashCode = this .index.hashCodeOf(tuple);
203:
204: final int index = indexOf(hashCode, this .table.length);
205:
206: // search the table for the Entry, we need to track previous and next, so if the
207: // Entry is empty after its had the FactEntry removed, we must remove it from the table
208: FieldIndexEntry previous = (FieldIndexEntry) this .table[index];
209: FieldIndexEntry current = previous;
210: while (current != null) {
211: final FieldIndexEntry next = (FieldIndexEntry) current.next;
212: if (current.matches(tuple, hashCode)) {
213: final ReteTuple old = current.remove(tuple);
214: this .factSize--;
215: // If the FactEntryIndex is empty, then remove it from the hash table
216: if (current.first == null) {
217: if (previous == current) {
218: this .table[index] = next;
219: } else {
220: previous.next = next;
221: }
222: current.next = null;
223: this .size--;
224: }
225: return old;
226: }
227: previous = current;
228: current = next;
229: }
230: return null;
231: }
232:
233: public boolean contains(final ReteTuple tuple) {
234: final int hashCode = this .index.hashCodeOf(tuple);
235:
236: final int index = indexOf(hashCode, this .table.length);
237:
238: FieldIndexEntry current = (FieldIndexEntry) this .table[index];
239: while (current != null) {
240: if (current.matches(tuple, hashCode)) {
241: return true;
242: }
243: current = (FieldIndexEntry) current.next;
244: }
245: return false;
246: }
247:
248: public FieldIndexEntry get(final InternalFactHandle handle) {
249: final Object object = handle.getObject();
250: final int hashCode = this .index.hashCodeOf(handle.getObject());
251:
252: final int index = indexOf(hashCode, this .table.length);
253: FieldIndexEntry entry = (FieldIndexEntry) this .table[index];
254:
255: while (entry != null) {
256: if (entry.matches(object, hashCode)) {
257: return entry;
258: }
259: entry = (FieldIndexEntry) entry.getNext();
260: }
261:
262: return entry;
263: }
264:
265: /**
266: * We use this method to aviod to table lookups for the same hashcode; which is what we would have to do if we did
267: * a get and then a create if the value is null.
268: *
269: * @param value
270: * @return
271: */
272: private FieldIndexEntry getOrCreate(final ReteTuple tuple) {
273: final int hashCode = this .index.hashCodeOf(tuple);
274:
275: final int index = indexOf(hashCode, this .table.length);
276: FieldIndexEntry entry = (FieldIndexEntry) this .table[index];
277:
278: // search to find an existing entry
279: while (entry != null) {
280: if (entry.matches(tuple, hashCode)) {
281: return entry;
282: }
283: entry = (FieldIndexEntry) entry.next;
284: }
285:
286: // entry does not exist, so create
287: if (entry == null) {
288: entry = new FieldIndexEntry(this .index, hashCode);
289: entry.next = this .table[index];
290: this .table[index] = entry;
291:
292: if (this .size++ >= this .threshold) {
293: resize(2 * this .table.length);
294: }
295: }
296: return entry;
297: }
298:
299: public int size() {
300: return this .factSize;
301: }
302:
303: public static class FieldIndexEntry implements Entry {
304:
305: private static final long serialVersionUID = 400L;
306: private Entry next;
307: private ReteTuple first;
308: private final int hashCode;
309: private Index index;
310:
311: public FieldIndexEntry(final Index index, final int hashCode) {
312: this .index = index;
313: this .hashCode = hashCode;
314: }
315:
316: public Entry getNext() {
317: return this .next;
318: }
319:
320: public void setNext(final Entry next) {
321: this .next = next;
322: }
323:
324: public ReteTuple getFirst() {
325: return this .first;
326: }
327:
328: public void add(final ReteTuple tuple) {
329: tuple.setNext(this .first);
330: this .first = tuple;
331: }
332:
333: public ReteTuple get(final ReteTuple tuple) {
334: ReteTuple current = this .first;
335: while (current != null) {
336: if (tuple.equals(current)) {
337: return current;
338: }
339: current = (ReteTuple) current.getNext();
340: }
341: return null;
342: }
343:
344: public ReteTuple remove(final ReteTuple tuple) {
345: ReteTuple previous = this .first;
346: ReteTuple current = previous;
347: while (current != null) {
348: final ReteTuple next = (ReteTuple) current.getNext();
349: if (tuple.equals(current)) {
350: if (this .first == current) {
351: this .first = next;
352: } else {
353: previous.setNext(next);
354: }
355: current.setNext(null);
356: return current;
357: }
358: previous = current;
359: current = next;
360: }
361: return current;
362: }
363:
364: public boolean matches(final Object object,
365: final int objectHashCode) {
366: return this .hashCode == objectHashCode
367: && this .index.equal(object, this .first);
368: }
369:
370: public boolean matches(final ReteTuple tuple,
371: final int tupleHashCode) {
372: return this .hashCode == tupleHashCode
373: && this .index.equal(this .first, tuple);
374: }
375:
376: public int hashCode() {
377: return this .hashCode;
378: }
379:
380: public boolean equals(final Object object) {
381: final FieldIndexEntry other = (FieldIndexEntry) object;
382: return this.hashCode == other.hashCode
383: && this.index == other.index;
384: }
385: }
386:
387: }
|