001: /**
002: *
003: */package org.drools.util;
004:
005: import java.io.Serializable;
006:
007: import org.drools.common.InternalFactHandle;
008: import org.drools.reteoo.ReteTuple;
009: import org.drools.rule.Declaration;
010: import org.drools.spi.Evaluator;
011: import org.drools.spi.FieldExtractor;
012:
013: public abstract class AbstractHashTable implements Serializable {
014: static final int MAX_CAPACITY = 1 << 30;
015:
016: protected int size;
017: protected int threshold;
018: protected float loadFactor;
019:
020: protected ObjectComparator comparator;
021:
022: protected Entry[] table;
023:
024: private HashTableIterator iterator;
025:
026: public AbstractHashTable() {
027: this (16, 0.75f);
028: }
029:
030: public AbstractHashTable(final int capacity, final float loadFactor) {
031: this .loadFactor = loadFactor;
032: this .threshold = (int) (capacity * loadFactor);
033: this .table = new Entry[capacity];
034: this .comparator = EqualityEquals.getInstance();
035: }
036:
037: public AbstractHashTable(final Entry[] table) {
038: this (0.75f, table);
039: }
040:
041: public AbstractHashTable(final float loadFactor, final Entry[] table) {
042: this .loadFactor = loadFactor;
043: this .threshold = (int) (table.length * loadFactor);
044: this .table = table;
045: this .comparator = EqualityEquals.getInstance();
046: }
047:
048: public Iterator iterator() {
049: if (this .iterator == null) {
050: this .iterator = new HashTableIterator(this );
051: }
052:
053: this .iterator.reset();
054: return this .iterator;
055: }
056:
057: public Iterator newIterator() {
058: HashTableIterator iterator = new HashTableIterator(this );
059: iterator.reset();
060: return iterator;
061:
062: }
063:
064: public void setComparator(final ObjectComparator comparator) {
065: this .comparator = comparator;
066: }
067:
068: protected void resize(final int newCapacity) {
069: final Entry[] oldTable = this .table;
070: final int oldCapacity = oldTable.length;
071: if (oldCapacity == AbstractHashTable.MAX_CAPACITY) {
072: this .threshold = Integer.MAX_VALUE;
073: return;
074: }
075:
076: final Entry[] newTable = new Entry[newCapacity];
077:
078: for (int i = 0; i < this .table.length; i++) {
079: Entry entry = this .table[i];
080: if (entry == null) {
081: continue;
082: }
083: this .table[i] = null;
084: Entry next = null;
085: while (entry != null) {
086: next = entry.getNext();
087:
088: final int index = indexOf(entry.hashCode(),
089: newTable.length);
090: entry.setNext(newTable[index]);
091: newTable[index] = entry;
092:
093: entry = next;
094: }
095: }
096:
097: this .table = newTable;
098: this .threshold = (int) (newCapacity * this .loadFactor);
099: }
100:
101: public Entry[] toArray() {
102: Entry[] result = new Entry[this .size];
103: int index = 0;
104: for (int i = 0; i < this .table.length; i++) {
105: Entry entry = this .table[i];
106: while (entry != null) {
107: result[index++] = entry;
108: entry = entry.getNext();
109: }
110: }
111: return result;
112: }
113:
114: // public void add(Entry entry) {
115: // int index = indexOf( entry.hashCode(), table.length );
116: //
117: //
118: // boolean exists = false;
119: //
120: // // scan the linked entries to see if it exists
121: // if ( !checkExists ) {
122: // Entry current = this.table[index];
123: // int hashCode = entry.hashCode();
124: // while ( current != null ) {
125: // if ( hashCode == current.hashCode() && entry.equals( current ) ) {
126: // exists = true;
127: // }
128: // }
129: // }
130: //
131: // if( exists == false ) {
132: // entry.setNext( this.table[index] );
133: // this.table[index] = entry;
134: //
135: // if ( this.size++ >= this.threshold ) {
136: // resize( 2 * this.table.length );
137: // }
138: // }
139: //
140: // }
141: //
142: // public Entry get(Entry entry) {
143: // int index = indexOf( entry.hashCode(), table.length );
144: // Entry current = this.table[index];
145: // while ( current != null ) {
146: // if ( entry.hashCode() == current.hashCode() && entry.equals( current ) ) {
147: // return current;
148: // }
149: // current = current.getNext();
150: // }
151: // return null;
152: // }
153: //
154: // public Entry remove(Entry entry) {
155: // int index = indexOf( entry.hashCode(), table.length );
156: // Entry previous = this.table[index];
157: // Entry current = previous;
158: // int hashCode = entry.hashCode();
159: // while ( current != null ) {
160: // Entry next = current.getNext();
161: // if ( hashCode == current.hashCode() && entry.equals( current ) ) {
162: // if( previous == current ) {
163: // this.table[index] = next;
164: // previous.setNext( next );
165: // }
166: // current.setNext( null );
167: // this.size--;
168: // return current;
169: // }
170: // previous = current;
171: // current = next;
172: // }
173: // return current;
174: // }
175:
176: protected Entry getBucket(final int hashCode) {
177: return this .table[indexOf(hashCode, this .table.length)];
178: }
179:
180: public Entry[] getTable() {
181: return this .table;
182: }
183:
184: public int size() {
185: return this .size;
186: }
187:
188: public boolean isEmpty() {
189: return this .size == 0;
190: }
191:
192: // protected int indexOf(int hashCode,
193: // int dataSize) {
194: // int index = hashCode % dataSize;
195: // if ( index < 0 ) {
196: // index = index * -1;
197: // }
198: // return index;
199: // }
200:
201: protected int indexOf(final int hashCode, final int dataSize) {
202: return hashCode & (dataSize - 1);
203: }
204:
205: public abstract Entry getBucket(Object object);
206:
207: public interface ObjectComparator extends Serializable {
208: public int hashCodeOf(Object object);
209:
210: public int rehash(int hashCode);
211:
212: public boolean equal(Object object1, Object object2);
213: }
214:
215: /**
216: * Fast re-usable iterator
217: *
218: */
219: public static class HashTableIterator implements Iterator {
220:
221: private static final long serialVersionUID = 400L;
222:
223: private AbstractHashTable hashTable;
224: private Entry[] table;
225: private int row;
226: private int length;
227: private Entry entry;
228:
229: public HashTableIterator(final AbstractHashTable hashTable) {
230: this .hashTable = hashTable;
231: }
232:
233: /* (non-Javadoc)
234: * @see org.drools.util.Iterator#next()
235: */
236: public Object next() {
237: if (this .entry == null) {
238: // keep skipping rows until we come to the end, or find one that is populated
239: while (this .entry == null) {
240: this .row++;
241: if (this .row == this .length) {
242: return null;
243: }
244: this .entry = this .table[this .row];
245: }
246: } else {
247: this .entry = this .entry.getNext();
248: if (this .entry == null) {
249: this .entry = (Entry) next();
250: }
251: }
252:
253: return this .entry;
254: }
255:
256: /* (non-Javadoc)
257: * @see org.drools.util.Iterator#reset()
258: */
259: public void reset() {
260: this .table = this .hashTable.getTable();
261: this .length = this .table.length;
262: this .row = -1;
263: this .entry = null;
264: }
265: }
266:
267: public static class InstanceEquals implements ObjectComparator {
268:
269: private static final long serialVersionUID = 400L;
270: public static ObjectComparator INSTANCE = new InstanceEquals();
271:
272: public static ObjectComparator getInstance() {
273: return InstanceEquals.INSTANCE;
274: }
275:
276: public int hashCodeOf(final Object key) {
277: return rehash(key.hashCode());
278: }
279:
280: public int rehash(int h) {
281: h += ~(h << 9);
282: h ^= (h >>> 14);
283: h += (h << 4);
284: h ^= (h >>> 10);
285: return h;
286: }
287:
288: private InstanceEquals() {
289:
290: }
291:
292: public boolean equal(final Object object1, final Object object2) {
293: return object1 == object2;
294: }
295: }
296:
297: public static class EqualityEquals implements ObjectComparator {
298:
299: private static final long serialVersionUID = 400L;
300: public static ObjectComparator INSTANCE = new EqualityEquals();
301:
302: public static ObjectComparator getInstance() {
303: return EqualityEquals.INSTANCE;
304: }
305:
306: public int hashCodeOf(final Object key) {
307: return rehash(key.hashCode());
308: }
309:
310: public int rehash(int h) {
311: h += ~(h << 9);
312: h ^= (h >>> 14);
313: h += (h << 4);
314: h ^= (h >>> 10);
315: return h;
316: }
317:
318: private EqualityEquals() {
319:
320: }
321:
322: public boolean equal(final Object object1, final Object object2) {
323: if (object1 == null) {
324: return object2 == null;
325: }
326: return object1.equals(object2);
327: }
328: }
329:
330: public static class FactEntryImpl implements FactEntry, Entry {
331:
332: private static final long serialVersionUID = 400L;
333:
334: public InternalFactHandle handle;
335:
336: public int hashCode;
337:
338: public Entry next;
339:
340: // private LinkedList list;
341:
342: public FactEntryImpl(final InternalFactHandle handle) {
343: this .handle = handle;
344: this .hashCode = handle.hashCode();
345: // this.list = new LinkedList();
346: }
347:
348: public FactEntryImpl(final InternalFactHandle handle,
349: final int hashCode) {
350: this .handle = handle;
351: this .hashCode = hashCode;
352: // this.list = new LinkedList();
353: }
354:
355: public InternalFactHandle getFactHandle() {
356: return this .handle;
357: }
358:
359: public Entry getNext() {
360: return this .next;
361: }
362:
363: public void setNext(final Entry next) {
364: this .next = next;
365: }
366:
367: //
368: // void add(final LinkedListEntry tupleMatchEntry) {
369: // this.list.add( tupleMatchEntry );
370: // }
371: // void remove(final LinkedListEntry tupleMatchEntry) {
372: // this.list.remove( tupleMatchEntry );
373: // }
374:
375: public int hashCode() {
376: return this .hashCode;
377: }
378:
379: public boolean equals(final Object object) {
380: return (object == this )
381: || (this .handle == ((FactEntryImpl) object).handle);
382: }
383:
384: public String toString() {
385: return "FactEntry( handle=" + this .handle + " hashcode="
386: + this .hashCode + " next=" + this .next + " )";
387: }
388: }
389:
390: public static class FieldIndex {
391: FieldExtractor extractor;
392: Declaration declaration;
393: public Evaluator evaluator;
394:
395: public FieldIndex(final FieldExtractor extractor,
396: final Declaration declaration, final Evaluator evaluator) {
397: super ();
398: this .extractor = extractor;
399: this .declaration = declaration;
400: this .evaluator = evaluator;
401: }
402:
403: public Declaration getDeclaration() {
404: return this .declaration;
405: }
406:
407: public FieldExtractor getExtractor() {
408: return this .extractor;
409: }
410:
411: public Evaluator getEvaluator() {
412: return this .evaluator;
413: }
414: }
415:
416: public static interface Index {
417: public FieldIndex getFieldIndex(int index);
418:
419: public int hashCodeOf(ReteTuple tuple);
420:
421: public int hashCodeOf(Object object);
422:
423: public boolean equal(Object object, ReteTuple tuple);
424:
425: public boolean equal(ReteTuple tuple1, ReteTuple tuple2);
426:
427: public boolean equal(Object object1, Object object2);
428: }
429:
430: public static class SingleIndex implements Index {
431:
432: private FieldExtractor extractor;
433: private Declaration declaration;
434: private Evaluator evaluator;
435:
436: private int startResult;
437:
438: public SingleIndex(final FieldIndex[] indexes,
439: final int startResult) {
440: this .startResult = startResult;
441:
442: this .extractor = indexes[0].extractor;
443: this .declaration = indexes[0].declaration;
444: this .evaluator = indexes[0].evaluator;
445: }
446:
447: public FieldIndex getFieldIndex(int index) {
448: if (index > 0) {
449: throw new IllegalArgumentException("Index position "
450: + index + " does not exist");
451: }
452: return new FieldIndex(extractor, declaration, evaluator);
453: }
454:
455: public int hashCodeOf(final Object object) {
456: int hashCode = this .startResult;
457: hashCode = TupleIndexHashTable.PRIME * hashCode
458: + this .extractor.getHashCode(null, object);
459: return rehash(hashCode);
460: }
461:
462: public int hashCodeOf(final ReteTuple tuple) {
463: int hashCode = this .startResult;
464: hashCode = TupleIndexHashTable.PRIME
465: * hashCode
466: + this .declaration.getHashCode(null, tuple.get(
467: this .declaration).getObject());
468: return rehash(hashCode);
469: }
470:
471: public boolean equal(final Object right, final ReteTuple tuple) {
472: final Object left = tuple.get(this .declaration).getObject();
473:
474: return this .evaluator.evaluate(null, this .declaration
475: .getExtractor(), left, this .extractor, right);
476: }
477:
478: public boolean equal(final Object object1, final Object object2) {
479:
480: return this .evaluator.evaluate(null, this .extractor,
481: object1, this .extractor, object2);
482: }
483:
484: public boolean equal(final ReteTuple tuple1,
485: final ReteTuple tuple2) {
486: final Object object1 = tuple1.get(this .declaration)
487: .getObject();
488: final Object object2 = tuple2.get(this .declaration)
489: .getObject();
490: return this .evaluator.evaluate(null, this .declaration
491: .getExtractor(), object1, this .declaration
492: .getExtractor(), object2);
493: }
494:
495: public int rehash(int h) {
496: h += ~(h << 9);
497: h ^= (h >>> 14);
498: h += (h << 4);
499: h ^= (h >>> 10);
500: return h;
501: }
502:
503: }
504:
505: public static class DoubleCompositeIndex implements Index {
506: private FieldIndex index0;
507: private FieldIndex index1;
508:
509: private int startResult;
510:
511: public DoubleCompositeIndex(final FieldIndex[] indexes,
512: final int startResult) {
513: this .startResult = startResult;
514:
515: this .index0 = indexes[0];
516: this .index1 = indexes[1];
517: }
518:
519: public FieldIndex getFieldIndex(int index) {
520: switch (index) {
521: case 0:
522: return index0;
523: case 1:
524: return index1;
525: default:
526: throw new IllegalArgumentException("Index position "
527: + index + " does not exist");
528: }
529: }
530:
531: public int hashCodeOf(final Object object) {
532: int hashCode = this .startResult;
533:
534: hashCode = TupleIndexHashTable.PRIME * hashCode
535: + this .index0.extractor.getHashCode(null, object);
536: hashCode = TupleIndexHashTable.PRIME * hashCode
537: + this .index1.extractor.getHashCode(null, object);
538:
539: return rehash(hashCode);
540: }
541:
542: public int hashCodeOf(final ReteTuple tuple) {
543: int hashCode = this .startResult;
544:
545: hashCode = TupleIndexHashTable.PRIME
546: * hashCode
547: + this .index0.declaration.getHashCode(null, tuple
548: .get(this .index0.declaration).getObject());
549: hashCode = TupleIndexHashTable.PRIME
550: * hashCode
551: + this .index1.declaration.getHashCode(null, tuple
552: .get(this .index1.declaration).getObject());
553:
554: return rehash(hashCode);
555: }
556:
557: public boolean equal(final Object right, final ReteTuple tuple) {
558: final Object left1 = tuple.get(this .index0.declaration)
559: .getObject();
560: final Object left2 = tuple.get(this .index1.declaration)
561: .getObject();
562:
563: return this .index0.evaluator.evaluate(null,
564: this .index0.declaration.getExtractor(), left1,
565: this .index0.extractor, right)
566: && this .index1.evaluator.evaluate(null,
567: this .index1.declaration.getExtractor(),
568: left2, this .index1.extractor, right);
569: }
570:
571: public boolean equal(final ReteTuple tuple1,
572: final ReteTuple tuple2) {
573: final Object object11 = tuple1.get(this .index0.declaration)
574: .getObject();
575: final Object object12 = tuple2.get(this .index0.declaration)
576: .getObject();
577:
578: final Object object21 = tuple1.get(this .index1.declaration)
579: .getObject();
580: final Object object22 = tuple2.get(this .index1.declaration)
581: .getObject();
582:
583: return this .index0.evaluator.evaluate(null,
584: this .index0.declaration.getExtractor(), object11,
585: this .index0.declaration.getExtractor(), object12)
586: && this .index1.evaluator.evaluate(null,
587: this .index1.declaration.getExtractor(),
588: object21, this .index1.declaration
589: .getExtractor(), object22);
590: }
591:
592: public boolean equal(final Object object1, final Object object2) {
593: return this .index0.evaluator.evaluate(null,
594: this .index0.extractor, object1,
595: this .index0.extractor, object2)
596: && this .index1.evaluator.evaluate(null,
597: this .index1.extractor, object1,
598: this .index1.extractor, object2);
599: }
600:
601: public int rehash(int h) {
602: h += ~(h << 9);
603: h ^= (h >>> 14);
604: h += (h << 4);
605: h ^= (h >>> 10);
606: return h;
607: }
608: }
609:
610: public static class TripleCompositeIndex implements Index {
611: private FieldIndex index0;
612: private FieldIndex index1;
613: private FieldIndex index2;
614:
615: private int startResult;
616:
617: public TripleCompositeIndex(final FieldIndex[] indexes,
618: final int startResult) {
619: this .startResult = startResult;
620:
621: this .index0 = indexes[0];
622: this .index1 = indexes[1];
623: this .index2 = indexes[2];
624: }
625:
626: public FieldIndex getFieldIndex(int index) {
627: switch (index) {
628: case 0:
629: return index0;
630: case 1:
631: return index1;
632: case 2:
633: return index2;
634: default:
635: throw new IllegalArgumentException("Index position "
636: + index + " does not exist");
637: }
638: }
639:
640: public int hashCodeOf(final Object object) {
641: int hashCode = this .startResult;
642:
643: hashCode = TupleIndexHashTable.PRIME * hashCode
644: + this .index0.extractor.getHashCode(null, object);
645: ;
646: hashCode = TupleIndexHashTable.PRIME * hashCode
647: + this .index1.extractor.getHashCode(null, object);
648: ;
649: hashCode = TupleIndexHashTable.PRIME * hashCode
650: + this .index2.extractor.getHashCode(null, object);
651: ;
652:
653: return rehash(hashCode);
654: }
655:
656: public int hashCodeOf(final ReteTuple tuple) {
657: int hashCode = this .startResult;
658:
659: hashCode = TupleIndexHashTable.PRIME
660: * hashCode
661: + this .index0.declaration.getHashCode(null, tuple
662: .get(this .index0.declaration).getObject());
663: hashCode = TupleIndexHashTable.PRIME
664: * hashCode
665: + this .index1.declaration.getHashCode(null, tuple
666: .get(this .index1.declaration).getObject());
667: hashCode = TupleIndexHashTable.PRIME
668: * hashCode
669: + this .index2.declaration.getHashCode(null, tuple
670: .get(this .index2.declaration).getObject());
671:
672: return rehash(hashCode);
673: }
674:
675: public boolean equal(final Object right, final ReteTuple tuple) {
676: final Object left1 = tuple.get(this .index0.declaration)
677: .getObject();
678: final Object left2 = tuple.get(this .index1.declaration)
679: .getObject();
680: final Object left3 = tuple.get(this .index2.declaration)
681: .getObject();
682:
683: return this .index0.evaluator.evaluate(null,
684: this .index0.declaration.getExtractor(), left1,
685: this .index0.extractor, right)
686: && this .index1.evaluator.evaluate(null,
687: this .index1.declaration.getExtractor(),
688: left2, this .index1.extractor, right)
689: && this .index2.evaluator.evaluate(null,
690: this .index2.declaration.getExtractor(),
691: left3, this .index2.extractor, right);
692: }
693:
694: public boolean equal(final ReteTuple tuple1,
695: final ReteTuple tuple2) {
696: final Object object11 = tuple1.get(this .index0.declaration)
697: .getObject();
698: final Object object12 = tuple2.get(this .index0.declaration)
699: .getObject();
700: final Object object21 = tuple1.get(this .index1.declaration)
701: .getObject();
702: final Object object22 = tuple2.get(this .index1.declaration)
703: .getObject();
704: final Object object31 = tuple1.get(this .index2.declaration)
705: .getObject();
706: final Object object32 = tuple2.get(this .index2.declaration)
707: .getObject();
708:
709: return this .index0.evaluator.evaluate(null,
710: this .index0.declaration.getExtractor(), object11,
711: this .index0.declaration.getExtractor(), object12)
712: && this .index1.evaluator.evaluate(null,
713: this .index1.declaration.getExtractor(),
714: object21, this .index1.declaration
715: .getExtractor(), object22)
716: && this .index2.evaluator.evaluate(null,
717: this .index2.declaration.getExtractor(),
718: object31, this .index2.declaration
719: .getExtractor(), object32);
720: }
721:
722: public boolean equal(final Object object1, final Object object2) {
723: return this .index0.evaluator.evaluate(null,
724: this .index0.extractor, object1,
725: this .index0.extractor, object2)
726: && this .index1.evaluator.evaluate(null,
727: this .index1.extractor, object1,
728: this .index1.extractor, object2)
729: && this .index2.evaluator.evaluate(null,
730: this .index2.extractor, object1,
731: this .index2.extractor, object2);
732: }
733:
734: public int rehash(int h) {
735: h += ~(h << 9);
736: h ^= (h >>> 14);
737: h += (h << 4);
738: h ^= (h >>> 10);
739: return h;
740: }
741:
742: }
743: }
|