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  ;
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  [] objectKeyTable;
96      protected long[]   longKeyTable;
97  
98      //
99      protected int[]    intValueTable;
100     protected Object  [] 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   {
136 
137         if (initialCapacity <= 0 || loadFactor <= 0.0) {
138             throw new IllegalArgumentException  ();
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  [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  [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   key, int hash) {
189 
190         int    lookup = hashIndex.getLookup(hash);
191         Object   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   addOrRemove(long longKey, long longValue,
240                                  Object   objectKey, Object   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   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   addOrRemove(int intKey, Object   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   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   removeObject(Object   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   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   objectKey   = null;
556             Object   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   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  [newLength];
624 
625             System.arraycopy(temp, 0, objectKeyTable, 0, usedLength);
626         }
627 
628         if (isObjectValue) {
629             temp             = objectValueTable;
630             objectValueTable = new Object  [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   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   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   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   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   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   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   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   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   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   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   next() throws NoSuchElementException   {
1010
1011            if ((keys &&!isObjectKey) || (!keys &&!isObjectValue)) {
1012                throw new NoSuchElementException  ("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  ("Hash Iterator");
1030        }
1031
1032        public int nextInt() throws NoSuchElementException   {
1033
1034            if ((keys &&!isIntKey) || (!keys &&!isIntValue)) {
1035                throw new NoSuchElementException  ("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  ("Hash Iterator");
1053        }
1054
1055        public long nextLong() throws NoSuchElementException   {
1056
1057            if ((!isLongKey ||!keys)) {
1058                throw new NoSuchElementException  ("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  ("Hash Iterator");
1076        }
1077
1078        public void remove() throws NoSuchElementException   {
1079
1080            if (removed) {
1081                throw new NoSuchElementException  ("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  ();
1095            }
1096
1097            return accessTable[lookup];
1098        }
1099    }
1100}
1101
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags