KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > hsqldb > store > BaseHashMap


1 /* Copyright (c) 2001-2005, The HSQL Development Group
2  * All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * Redistributions of source code must retain the above copyright notice, this
8  * list of conditions and the following disclaimer.
9  *
10  * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  *
14  * Neither the name of the HSQL Development Group nor the names of its
15  * contributors may be used to endorse or promote products derived from this
16  * software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */

30
31
32 package org.hsqldb.store;
33
34 import java.util.NoSuchElementException JavaDoc;
35
36 import org.hsqldb.lib.ArrayCounter;
37
38 public class BaseHashMap {
39
40 /**
41  * Base class for hash tables or sets. The exact type of the structure is
42  * defined by the constructor. Each instance has at least a keyTable array
43  * and a HashIndex instance for looking up the keys into this table. Instances
44  * that are maps also have a valueTable the same size as the keyTable.
45  *
46  * Special getOrAddXXX() methods are used for object maps in some subclasses.
47  *
48  * @author fredt@users
49  * @version 1.8.0
50  * @since 1.7.2
51  */

52 /*
53
54     data store:
55     keys: {array of primitive | array of object}
56     values: {none | array of primitive | array of object} same size as keys
57     objects support : hashCode(), equals()
58
59     implemented types of keyTable:
60     {objectKeyTable: variable size Object[] array for keys |
61     intKeyTable: variable size int[] for keys |
62     longKeyTable: variable size long[] for keys }
63
64     implemented types of valueTable:
65     {objectValueTable: variable size Object[] array for values |
66     intValueTable: variable size int[] for values |
67     longValueTable: variable size long[] for values}
68
69     valueTable does not exist for sets or for object pools
70
71     hash index:
72     hashTable: fixed size int[] array for hash lookup into keyTable
73     linkTable: pointer to the next key ; size equal or larger than hashTable
74     but equal to the valueTable
75
76     access count table:
77     {none |
78     variable size int[] array for access count} same size as xxxKeyTable
79 */

80
81     //
82
boolean isIntKey;
83     boolean isLongKey;
84     boolean isObjectKey;
85     boolean isNoValue;
86     boolean isIntValue;
87     boolean isLongValue;
88     boolean isObjectValue;
89
90     //
91
protected HashIndex hashIndex;
92
93     //
94
protected int[] intKeyTable;
95     protected Object JavaDoc[] objectKeyTable;
96     protected long[] longKeyTable;
97
98     //
99
protected int[] intValueTable;
100     protected Object JavaDoc[] objectValueTable;
101     protected long[] longValueTable;
102
103     //
104
int accessMin;
105     int accessCount;
106     int[] accessTable;
107
108     //
109
final float loadFactor;
110     final int initialCapacity;
111     int threshold;
112     int maxCapacity;
113     protected int purgePolicy = NO_PURGE;
114     protected boolean minimizeOnEmpty;
115
116     //
117
boolean hasZeroKey;
118     int zeroKeyIndex = -1;
119
120     // keyOrValueTypes
121
protected static final int noKeyOrValue = 0;
122     protected static final int intKeyOrValue = 1;
123     protected static final int longKeyOrValue = 2;
124     protected static final int objectKeyOrValue = 3;
125
126     // purgePolicy
127
protected static final int NO_PURGE = 0;
128     protected static final int PURGE_ALL = 1;
129     protected static final int PURGE_HALF = 2;
130     protected static final int PURGE_QUARTER = 3;
131
132     protected BaseHashMap(int initialCapacity, float loadFactor, int keyType,
133                           int valueType,
134                           boolean hasAccessCount)
135                           throws IllegalArgumentException JavaDoc {
136
137         if (initialCapacity <= 0 || loadFactor <= 0.0) {
138             throw new IllegalArgumentException JavaDoc();
139         }
140
141         this.loadFactor = loadFactor;
142         this.initialCapacity = initialCapacity;
143         threshold = initialCapacity;
144
145         if (threshold < 3) {
146             threshold = 3;
147         }
148
149         int hashtablesize = (int) (initialCapacity * loadFactor);
150
151         if (hashtablesize < 3) {
152             hashtablesize = 3;
153         }
154
155         hashIndex = new HashIndex(hashtablesize, initialCapacity, true);
156
157         int arraySize = threshold;
158
159         if (keyType == BaseHashMap.intKeyOrValue) {
160             isIntKey = true;
161             intKeyTable = new int[arraySize];
162         } else if (keyType == BaseHashMap.objectKeyOrValue) {
163             isObjectKey = true;
164             objectKeyTable = new Object JavaDoc[arraySize];
165         } else {
166             isLongKey = true;
167             longKeyTable = new long[arraySize];
168         }
169
170         if (valueType == BaseHashMap.intKeyOrValue) {
171             isIntValue = true;
172             intValueTable = new int[arraySize];
173         } else if (valueType == BaseHashMap.objectKeyOrValue) {
174             isObjectValue = true;
175             objectValueTable = new Object JavaDoc[arraySize];
176         } else if (valueType == BaseHashMap.longKeyOrValue) {
177             isLongValue = true;
178             longValueTable = new long[arraySize];
179         } else {
180             isNoValue = true;
181         }
182
183         if (hasAccessCount) {
184             accessTable = new int[arraySize];
185         }
186     }
187
188     protected int getLookup(Object JavaDoc key, int hash) {
189
190         int lookup = hashIndex.getLookup(hash);
191         Object JavaDoc tempKey;
192
193         for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
194             tempKey = objectKeyTable[lookup];
195
196             if (key.equals(tempKey)) {
197                 return lookup;
198             }
199         }
200
201         return lookup;
202     }
203
204     protected int getLookup(int key) {
205
206         int lookup = hashIndex.getLookup(key);
207         int tempKey;
208
209         for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
210             tempKey = intKeyTable[lookup];
211
212             if (key == tempKey) {
213                 return lookup;
214             }
215         }
216
217         return lookup;
218     }
219
220     protected int getLookup(long key) {
221
222         int lookup = hashIndex.getLookup((int) key);
223         long tempKey;
224
225         for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
226             tempKey = longKeyTable[lookup];
227
228             if (key == tempKey) {
229                 return lookup;
230             }
231         }
232
233         return lookup;
234     }
235
236     /**
237      * generic method for adding or removing keys
238      */

239     protected Object JavaDoc addOrRemove(long longKey, long longValue,
240                                  Object JavaDoc objectKey, Object JavaDoc objectValue,
241                                  boolean remove) {
242
243         int hash = (int) longKey;
244
245         if (isObjectKey) {
246             if (objectKey == null) {
247                 return null;
248             }
249
250             hash = objectKey.hashCode();
251         }
252
253         int index = hashIndex.getHashIndex(hash);
254         int lookup = hashIndex.hashTable[index];
255         int lastLookup = -1;
256         Object JavaDoc returnValue = null;
257
258         for (; lookup >= 0;
259                 lastLookup = lookup,
260                 lookup = hashIndex.getNextLookup(lookup)) {
261             if (isObjectKey) {
262                 if (objectKeyTable[lookup].equals(objectKey)) {
263                     break;
264                 }
265             } else if (isIntKey) {
266                 if (longKey == intKeyTable[lookup]) {
267                     break;
268                 }
269             } else if (isLongKey) {
270                 if (longKey == longKeyTable[lookup]) {
271                     break;
272                 }
273             }
274         }
275
276         if (lookup >= 0) {
277             if (remove) {
278                 if (isObjectKey) {
279                     objectKeyTable[lookup] = null;
280                 } else {
281                     if (longKey == 0) {
282                         hasZeroKey = false;
283                         zeroKeyIndex = -1;
284                     }
285
286                     if (isIntKey) {
287                         intKeyTable[lookup] = 0;
288                     } else {
289                         longKeyTable[lookup] = 0;
290                     }
291                 }
292
293                 if (isObjectValue) {
294                     returnValue = objectValueTable[lookup];
295                     objectValueTable[lookup] = null;
296                 } else if (isIntValue) {
297                     intValueTable[lookup] = 0;
298                 } else if (isLongValue) {
299                     longValueTable[lookup] = 0;
300                 }
301
302                 hashIndex.unlinkNode(index, lastLookup, lookup);
303
304                 if (accessTable != null) {
305                     accessTable[lookup] = 0;
306                 }
307
308                 if (minimizeOnEmpty && hashIndex.elementCount == 0) {
309                     rehash(initialCapacity);
310                 }
311
312                 return returnValue;
313             }
314
315             if (isObjectValue) {
316                 returnValue = objectValueTable[lookup];
317                 objectValueTable[lookup] = objectValue;
318             } else if (isIntValue) {
319                 intValueTable[lookup] = (int) longValue;
320             } else if (isLongValue) {
321                 longValueTable[lookup] = longValue;
322             }
323
324             if (accessTable != null) {
325                 accessTable[lookup] = accessCount++;
326             }
327
328             return returnValue;
329         }
330
331         // not found
332
if (remove) {
333             return null;
334         }
335
336         if (hashIndex.elementCount >= threshold) {
337
338             // should throw maybe, if reset returns false?
339
if (reset()) {
340                 return addOrRemove(longKey, longValue, objectKey,
341                                    objectValue, remove);
342             } else {
343                 return null;
344             }
345         }
346
347         lookup = hashIndex.linkNode(index, lastLookup);
348
349         // type dependent block
350
if (isObjectKey) {
351             objectKeyTable[lookup] = objectKey;
352         } else if (isIntKey) {
353             intKeyTable[lookup] = (int) longKey;
354
355             if (longKey == 0) {
356                 hasZeroKey = true;
357                 zeroKeyIndex = lookup;
358             }
359         } else if (isLongKey) {
360             longKeyTable[lookup] = longKey;
361
362             if (longKey == 0) {
363                 hasZeroKey = true;
364                 zeroKeyIndex = lookup;
365             }
366         }
367
368         if (isObjectValue) {
369             objectValueTable[lookup] = objectValue;
370         } else if (isIntValue) {
371             intValueTable[lookup] = (int) longValue;
372         } else if (isLongValue) {
373             longValueTable[lookup] = longValue;
374         }
375
376         //
377
if (accessTable != null) {
378             accessTable[lookup] = accessCount++;
379         }
380
381         return returnValue;
382     }
383
384     /**
385      * type-specific method for adding or removing keys in int->Object maps
386      */

387     protected Object JavaDoc addOrRemove(int intKey, Object JavaDoc objectValue,
388                                  boolean remove) {
389
390         int hash = intKey;
391         int index = hashIndex.getHashIndex(hash);
392         int lookup = hashIndex.hashTable[index];
393         int lastLookup = -1;
394         Object JavaDoc returnValue = null;
395
396         for (; lookup >= 0;
397                 lastLookup = lookup,
398                 lookup = hashIndex.getNextLookup(lookup)) {
399             if (intKey == intKeyTable[lookup]) {
400                 break;
401             }
402         }
403
404         if (lookup >= 0) {
405             if (remove) {
406                 if (intKey == 0) {
407                     hasZeroKey = false;
408                     zeroKeyIndex = -1;
409                 }
410
411                 intKeyTable[lookup] = 0;
412                 returnValue = objectValueTable[lookup];
413                 objectValueTable[lookup] = null;
414
415                 hashIndex.unlinkNode(index, lastLookup, lookup);
416
417                 if (accessTable != null) {
418                     accessTable[lookup] = 0;
419                 }
420
421                 return returnValue;
422             }
423
424             if (isObjectValue) {
425                 returnValue = objectValueTable[lookup];
426                 objectValueTable[lookup] = objectValue;
427             }
428
429             if (accessTable != null) {
430                 accessTable[lookup] = accessCount++;
431             }
432
433             return returnValue;
434         }
435
436         // not found
437
if (remove) {
438             return returnValue;
439         }
440
441         if (hashIndex.elementCount >= threshold) {
442             if (reset()) {
443                 return addOrRemove(intKey, objectValue, remove);
444             } else {
445                 return null;
446             }
447         }
448
449         lookup = hashIndex.linkNode(index, lastLookup);
450         intKeyTable[lookup] = intKey;
451
452         if (intKey == 0) {
453             hasZeroKey = true;
454             zeroKeyIndex = lookup;
455         }
456
457         objectValueTable[lookup] = objectValue;
458
459         if (accessTable != null) {
460             accessTable[lookup] = accessCount++;
461         }
462
463         return returnValue;
464     }
465
466     /**
467      * type specific method for Object sets or Object->Object maps
468      */

469     protected Object JavaDoc removeObject(Object JavaDoc objectKey) {
470
471         if (objectKey == null) {
472             return null;
473         }
474
475         int hash = objectKey.hashCode();
476         int index = hashIndex.getHashIndex(hash);
477         int lookup = hashIndex.hashTable[index];
478         int lastLookup = -1;
479         Object JavaDoc returnValue = null;
480
481         for (; lookup >= 0;
482                 lastLookup = lookup,
483                 lookup = hashIndex.getNextLookup(lookup)) {
484             if (objectKeyTable[lookup].equals(objectKey)) {
485                 objectKeyTable[lookup] = null;
486
487                 hashIndex.unlinkNode(index, lastLookup, lookup);
488
489                 if (isObjectValue) {
490                     returnValue = objectValueTable[lookup];
491                     objectValueTable[lookup] = null;
492                 }
493
494                 return returnValue;
495             }
496         }
497
498         // not found
499
return returnValue;
500     }
501
502     protected boolean reset() {
503
504         if (maxCapacity == 0 || maxCapacity > threshold) {
505             rehash(hashIndex.hashTable.length * 2);
506
507             return true;
508         } else if (purgePolicy == PURGE_ALL) {
509             clear();
510
511             return true;
512         } else if (purgePolicy == PURGE_QUARTER) {
513             clear(threshold / 4, threshold >> 8);
514
515             return true;
516         } else if (purgePolicy == PURGE_HALF) {
517             clear(threshold / 2, threshold >> 8);
518
519             return true;
520         } else if (purgePolicy == NO_PURGE) {
521             return false;
522         }
523
524         return false;
525     }
526
527     /**
528      * rehash uses existing key and element arrays. key / value pairs are
529      * put back into the arrays from the top, removing any gaps. any redundant
530      * key / value pairs duplicated at the end of the array are then cleared.
531      *
532      * newCapacity must be larger or equal to existing number of elements.
533      */

534     protected void rehash(int newCapacity) {
535
536         int limitLookup = hashIndex.newNodePointer;
537         boolean oldZeroKey = hasZeroKey;
538         int oldZeroKeyIndex = zeroKeyIndex;
539
540         if (newCapacity < hashIndex.elementCount) {
541             return;
542         }
543
544         hashIndex.reset((int) (newCapacity * loadFactor), newCapacity);
545
546         hasZeroKey = false;
547         zeroKeyIndex = -1;
548         threshold = newCapacity;
549
550         for (int lookup = -1;
551                 (lookup = nextLookup(lookup, limitLookup, oldZeroKey, oldZeroKeyIndex))
552                 < limitLookup; ) {
553             long longKey = 0;
554             long longValue = 0;
555             Object JavaDoc objectKey = null;
556             Object JavaDoc objectValue = null;
557
558             if (isObjectKey) {
559                 objectKey = objectKeyTable[lookup];
560             } else if (isIntKey) {
561                 longKey = intKeyTable[lookup];
562             } else {
563                 longKey = longKeyTable[lookup];
564             }
565
566             if (isObjectValue) {
567                 objectValue = objectValueTable[lookup];
568             } else if (isIntValue) {
569                 longValue = intValueTable[lookup];
570             } else if (isLongValue) {
571                 longValue = longValueTable[lookup];
572             }
573
574             addOrRemove(longKey, longValue, objectKey, objectValue, false);
575
576             if (accessTable != null) {
577                 accessTable[hashIndex.elementCount - 1] = accessTable[lookup];
578             }
579         }
580
581         resizeElementArrays(hashIndex.newNodePointer, newCapacity);
582     }
583
584     /**
585      * resize the arrays contianing the key / value data
586      */

587     private void resizeElementArrays(int dataLength, int newLength) {
588
589         Object JavaDoc temp;
590         int usedLength = newLength > dataLength ? dataLength
591                                                    : newLength;
592
593         if (isIntKey) {
594             temp = intKeyTable;
595             intKeyTable = new int[newLength];
596
597             System.arraycopy(temp, 0, intKeyTable, 0, usedLength);
598         }
599
600         if (isIntValue) {
601             temp = intValueTable;
602             intValueTable = new int[newLength];
603
604             System.arraycopy(temp, 0, intValueTable, 0, usedLength);
605         }
606
607         if (isLongKey) {
608             temp = longKeyTable;
609             longKeyTable = new long[newLength];
610
611             System.arraycopy(temp, 0, longKeyTable, 0, usedLength);
612         }
613
614         if (isLongValue) {
615             temp = longValueTable;
616             longValueTable = new long[newLength];
617
618             System.arraycopy(temp, 0, longValueTable, 0, usedLength);
619         }
620
621         if (isObjectKey) {
622             temp = objectKeyTable;
623             objectKeyTable = new Object JavaDoc[newLength];
624
625             System.arraycopy(temp, 0, objectKeyTable, 0, usedLength);
626         }
627
628         if (isObjectValue) {
629             temp = objectValueTable;
630             objectValueTable = new Object JavaDoc[newLength];
631
632             System.arraycopy(temp, 0, objectValueTable, 0, usedLength);
633         }
634
635         if (accessTable != null) {
636             temp = accessTable;
637             accessTable = new int[newLength];
638
639             System.arraycopy(temp, 0, accessTable, 0, usedLength);
640         }
641     }
642
643     /**
644      * clear all the key / value data in a range.
645      */

646     private void clearElementArrays(final int from, final int to) {
647
648         if (isIntKey) {
649             int counter = to;
650
651             while (--counter >= from) {
652                 intKeyTable[counter] = 0;
653             }
654         }
655
656         if (isLongKey) {
657             int counter = to;
658
659             while (--counter >= from) {
660                 longKeyTable[counter] = 0;
661             }
662         }
663
664         if (isObjectKey) {
665             int counter = to;
666
667             while (--counter >= from) {
668                 objectKeyTable[counter] = null;
669             }
670         }
671
672         if (isIntValue) {
673             int counter = to;
674
675             while (--counter >= from) {
676                 intValueTable[counter] = 0;
677             }
678         }
679
680         if (isLongValue) {
681             int counter = to;
682
683             while (--counter >= from) {
684                 longValueTable[counter] = 0;
685             }
686         }
687
688         if (isObjectValue) {
689             int counter = to;
690
691             while (--counter >= from) {
692                 objectValueTable[counter] = null;
693             }
694         }
695
696         if (accessTable != null) {
697             int counter = to;
698
699             while (--counter >= from) {
700                 accessTable[counter] = 0;
701             }
702         }
703     }
704
705     /**
706      * move the elements after a removed key / value pair to fill the gap
707      */

708     void removeFromElementArrays(int lookup) {
709
710         int arrayLength = hashIndex.linkTable.length;
711
712         if (isIntKey) {
713             Object JavaDoc array = intKeyTable;
714
715             System.arraycopy(array, lookup + 1, array, lookup,
716                              arrayLength - lookup - 1);
717
718             intKeyTable[arrayLength - 1] = 0;
719         }
720
721         if (isLongKey) {
722             Object JavaDoc array = longKeyTable;
723
724             System.arraycopy(array, lookup + 1, array, lookup,
725                              arrayLength - lookup - 1);
726
727             longKeyTable[arrayLength - 1] = 0;
728         }
729
730         if (isObjectKey) {
731             Object JavaDoc array = objectKeyTable;
732
733             System.arraycopy(array, lookup + 1, array, lookup,
734                              arrayLength - lookup - 1);
735
736             objectKeyTable[arrayLength - 1] = null;
737         }
738
739         if (isIntValue) {
740             Object JavaDoc array = intValueTable;
741
742             System.arraycopy(array, lookup + 1, array, lookup,
743                              arrayLength - lookup - 1);
744
745             intValueTable[arrayLength - 1] = 0;
746         }
747
748         if (isLongValue) {
749             Object JavaDoc array = longValueTable;
750
751             System.arraycopy(array, lookup + 1, array, lookup,
752                              arrayLength - lookup - 1);
753
754             longValueTable[arrayLength - 1] = 0;
755         }
756
757         if (isObjectValue) {
758             Object JavaDoc array = objectValueTable;
759
760             System.arraycopy(array, lookup + 1, array, lookup,
761                              arrayLength - lookup - 1);
762
763             objectValueTable[arrayLength - 1] = null;
764         }
765     }
766
767     /**
768      * find the next lookup in the key/value tables with an entry
769      * allows the use of old limit and zero int key attributes
770      */

771     int nextLookup(int lookup, int limitLookup, boolean hasZeroKey,
772                    int zeroKeyIndex) {
773
774         for (++lookup; lookup < limitLookup; lookup++) {
775             if (isObjectKey) {
776                 if (objectKeyTable[lookup] != null) {
777                     return lookup;
778                 }
779             } else if (isIntKey) {
780                 if (intKeyTable[lookup] != 0) {
781                     return lookup;
782                 } else if (hasZeroKey && lookup == zeroKeyIndex) {
783                     return lookup;
784                 }
785             } else {
786                 if (longKeyTable[lookup] != 0) {
787                     return lookup;
788                 } else if (hasZeroKey && lookup == zeroKeyIndex) {
789                     return lookup;
790                 }
791             }
792         }
793
794         return lookup;
795     }
796
797     /**
798      * find the next lookup in the key/value tables with an entry
799      * uses current limits and zero integer key state
800      */

801     protected int nextLookup(int lookup) {
802
803         for (++lookup; lookup < hashIndex.newNodePointer; lookup++) {
804             if (isObjectKey) {
805                 if (objectKeyTable[lookup] != null) {
806                     return lookup;
807                 }
808             } else if (isIntKey) {
809                 if (intKeyTable[lookup] != 0) {
810                     return lookup;
811                 } else if (hasZeroKey && lookup == zeroKeyIndex) {
812                     return lookup;
813                 }
814             } else {
815                 if (longKeyTable[lookup] != 0) {
816                     return lookup;
817                 } else if (hasZeroKey && lookup == zeroKeyIndex) {
818                     return lookup;
819                 }
820             }
821         }
822
823         return lookup;
824     }
825
826     /**
827      * row must already been freed of key / element
828      */

829     protected void removeRow(int lookup) {
830         hashIndex.removeEmptyNode(lookup);
831         removeFromElementArrays(lookup);
832     }
833
834     protected Object JavaDoc removeLookup(int lookup) {
835
836         if (isObjectKey) {
837             return addOrRemove(0, 0, objectKeyTable[lookup], null, true);
838         } else {
839             return addOrRemove(intKeyTable[lookup], 0, null, null, true);
840         }
841     }
842
843     /**
844      * Clear the map completely.
845      */

846     public void clear() {
847
848         accessCount = 0;
849         accessMin = accessCount;
850         hasZeroKey = false;
851         zeroKeyIndex = -1;
852
853         clearElementArrays(0, hashIndex.linkTable.length);
854         hashIndex.clear();
855
856         if (minimizeOnEmpty) {
857             rehash(initialCapacity);
858         }
859     }
860
861     /**
862      * Return the max accessCount value for count elements with the lowest
863      * access count. Always return at least accessMin + 1
864      */

865     protected int getAccessCountCeiling(int count, int margin) {
866         return ArrayCounter.rank(accessTable, hashIndex.newNodePointer,
867                                  count, accessMin + 1, accessCount, margin);
868     }
869
870     /**
871      * Clear approximately count elements from the map, starting with
872      * those with low accessTable ranking.
873      *
874      * Only for maps with Object key table
875      */

876     protected void clear(int count, int margin) {
877
878         if (margin < 64) {
879             margin = 64;
880         }
881
882         int maxlookup = hashIndex.newNodePointer;
883         int accessBase = getAccessCountCeiling(count, margin);
884
885         for (int lookup = 0; lookup < maxlookup; lookup++) {
886             Object JavaDoc o = objectKeyTable[lookup];
887
888             if (o != null && accessTable[lookup] < accessBase) {
889                 removeObject(o);
890             }
891         }
892
893         accessMin = accessBase;
894     }
895
896     void resetAccessCount() {
897
898         if (accessCount < Integer.MAX_VALUE) {
899             return;
900         }
901
902         accessMin >>= 2;
903         accessCount >>= 2;
904
905         int i = accessTable.length;
906
907         while (--i >= 0) {
908             accessTable[i] >>= 2;
909         }
910     }
911
912     public int size() {
913         return hashIndex.elementCount;
914     }
915
916     public boolean isEmpty() {
917         return hashIndex.elementCount == 0;
918     }
919
920     protected boolean containsKey(Object JavaDoc key) {
921
922         if (key == null) {
923             return false;
924         }
925
926         int lookup = getLookup(key, key.hashCode());
927
928         return lookup == -1 ? false
929                             : true;
930     }
931
932     protected boolean containsKey(int key) {
933
934         int lookup = getLookup(key);
935
936         return lookup == -1 ? false
937                             : true;
938     }
939
940     protected boolean containsKey(long key) {
941
942         int lookup = getLookup(key);
943
944         return lookup == -1 ? false
945                             : true;
946     }
947
948     protected boolean containsValue(Object JavaDoc value) {
949
950         int lookup = 0;
951
952         if (value == null) {
953             for (; lookup < hashIndex.newNodePointer; lookup++) {
954                 if (objectValueTable[lookup] == null) {
955                     if (isObjectKey) {
956                         if (objectKeyTable[lookup] != null) {
957                             return true;
958                         }
959                     } else if (isIntKey) {
960                         if (intKeyTable[lookup] != 0) {
961                             return true;
962                         } else if (hasZeroKey && lookup == zeroKeyIndex) {
963                             return true;
964                         }
965                     } else {
966                         if (longKeyTable[lookup] != 0) {
967                             return true;
968                         } else if (hasZeroKey && lookup == zeroKeyIndex) {
969                             return true;
970                         }
971                     }
972                 }
973             }
974         } else {
975             for (; lookup < hashIndex.newNodePointer; lookup++) {
976                 if (value.equals(objectValueTable[lookup])) {
977                     return true;
978                 }
979             }
980         }
981
982         return false;
983     }
984
985     /**
986      * Iterator returns Object, int or long and is used both for keys and
987      * values
988      */

989     protected class BaseHashIterator implements org.hsqldb.lib.Iterator {
990
991         boolean keys;
992         int lookup = -1;
993         int counter;
994         boolean removed;
995
996         /**
997          * default is iterator for values
998          */

999         public BaseHashIterator() {}
1000
1001        public BaseHashIterator(boolean keys) {
1002            this.keys = keys;
1003        }
1004
1005        public boolean hasNext() {
1006            return counter < hashIndex.elementCount;
1007        }
1008
1009        public Object JavaDoc next() throws NoSuchElementException JavaDoc {
1010
1011            if ((keys &&!isObjectKey) || (!keys &&!isObjectValue)) {
1012                throw new NoSuchElementException JavaDoc("Hash Iterator");
1013            }
1014
1015            removed = false;
1016
1017            if (hasNext()) {
1018                counter++;
1019
1020                lookup = nextLookup(lookup);
1021
1022                if (keys) {
1023                    return objectKeyTable[lookup];
1024                } else {
1025                    return objectValueTable[lookup];
1026                }
1027            }
1028
1029            throw new NoSuchElementException JavaDoc("Hash Iterator");
1030        }
1031
1032        public int nextInt() throws NoSuchElementException JavaDoc {
1033
1034            if ((keys &&!isIntKey) || (!keys &&!isIntValue)) {
1035                throw new NoSuchElementException JavaDoc("Hash Iterator");
1036            }
1037
1038            removed = false;
1039
1040            if (hasNext()) {
1041                counter++;
1042
1043                lookup = nextLookup(lookup);
1044
1045                if (keys) {
1046                    return intKeyTable[lookup];
1047                } else {
1048                    return intValueTable[lookup];
1049                }
1050            }
1051
1052            throw new NoSuchElementException JavaDoc("Hash Iterator");
1053        }
1054
1055        public long nextLong() throws NoSuchElementException JavaDoc {
1056
1057            if ((!isLongKey ||!keys)) {
1058                throw new NoSuchElementException JavaDoc("Hash Iterator");
1059            }
1060
1061            removed = false;
1062
1063            if (hasNext()) {
1064                counter++;
1065
1066                lookup = nextLookup(lookup);
1067
1068                if (keys) {
1069                    return longKeyTable[lookup];
1070                } else {
1071                    return longValueTable[lookup];
1072                }
1073            }
1074
1075            throw new NoSuchElementException JavaDoc("Hash Iterator");
1076        }
1077
1078        public void remove() throws NoSuchElementException JavaDoc {
1079
1080            if (removed) {
1081                throw new NoSuchElementException JavaDoc("Hash Iterator");
1082            }
1083
1084            counter--;
1085
1086            removed = true;
1087
1088            BaseHashMap.this.removeLookup(lookup);
1089        }
1090
1091        public int getAccessCount() {
1092
1093            if (removed || accessTable == null) {
1094                throw new NoSuchElementException JavaDoc();
1095            }
1096
1097            return accessTable[lookup];
1098        }
1099    }
1100}
1101
Popular Tags