001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.modules.cnd.repository.util;
043:
044: import java.io.*;
045: import java.util.*;
046:
047: /**
048: * Hash table based implementation of the <tt>Map</tt> interface. This
049: * implementation provides all of the optional map operations, and permits
050: * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>LongHashMap</tt>
051: * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
052: * unsynchronized and permits nulls.) This class makes no guarantees as to
053: * the order of the map; in particular, it does not guarantee that the order
054: * will remain constant over time.
055: *
056: * <p>This implementation provides constant-time performance for the basic
057: * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
058: * disperses the elements properly among the buckets. Iteration over
059: * collection views requires time proportional to the "capacity" of the
060: * <tt>LongHashMap</tt> instance (the number of buckets) plus its size (the number
061: * of key-value mappings). Thus, it's very important not to set the initial
062: * capacity too high (or the load factor too low) if iteration performance is
063: * important.
064: *
065: * <p>An instance of <tt>LongHashMap</tt> has two parameters that affect its
066: * performance: <i>initial capacity</i> and <i>load factor</i>. The
067: * <i>capacity</i> is the number of buckets in the hash table, and the initial
068: * capacity is simply the capacity at the time the hash table is created. The
069: * <i>load factor</i> is a measure of how full the hash table is allowed to
070: * get before its capacity is automatically increased. When the number of
071: * entries in the hash table exceeds the product of the load factor and the
072: * current capacity, the capacity is roughly doubled by calling the
073: * <tt>rehash</tt> method.
074: *
075: * <p>As a general rule, the default load factor (.75) offers a good tradeoff
076: * between time and space costs. Higher values decrease the space overhead
077: * but increase the lookup cost (reflected in most of the operations of the
078: * <tt>LongHashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
079: * expected number of entries in the map and its load factor should be taken
080: * into account when setting its initial capacity, so as to minimize the
081: * number of <tt>rehash</tt> operations. If the initial capacity is greater
082: * than the maximum number of entries divided by the load factor, no
083: * <tt>rehash</tt> operations will ever occur.
084: *
085: * <p>If many mappings are to be stored in a <tt>LongHashMap</tt> instance,
086: * creating it with a sufficiently large capacity will allow the mappings to
087: * be stored more efficiently than letting it perform automatic rehashing as
088: * needed to grow the table.
089: *
090: * <p><b>Note that this implementation is not synchronized.</b> If multiple
091: * threads access this map concurrently, and at least one of the threads
092: * modifies the map structurally, it <i>must</i> be synchronized externally.
093: * (A structural modification is any operation that adds or deletes one or
094: * more mappings; merely changing the value associated with a key that an
095: * instance already contains is not a structural modification.) This is
096: * typically accomplished by synchronizing on some object that naturally
097: * encapsulates the map. If no such object exists, the map should be
098: * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
099: * best done at creation time, to prevent accidental unsynchronized access to
100: * the map: <pre> Map m = Collections.synchronizedMap(new LongHashMap(...));
101: * </pre>
102: *
103: * <p>The iterators returned by all of this class's "collection view methods"
104: * are <i>fail-fast</i>: if the map is structurally modified at any time after
105: * the iterator is created, in any way except through the iterator's own
106: * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
107: * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
108: * modification, the iterator fails quickly and cleanly, rather than risking
109: * arbitrary, non-deterministic behavior at an undetermined time in the
110: * future.
111: *
112: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
113: * as it is, generally speaking, impossible to make any hard guarantees in the
114: * presence of unsynchronized concurrent modification. Fail-fast iterators
115: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
116: * Therefore, it would be wrong to write a program that depended on this
117: * exception for its correctness: <i>the fail-fast behavior of iterators
118: * should be used only to detect bugs.</i>
119: *
120: * <p>This class is a member of the
121: * <a href="{@docRoot}/../guide/collections/index.html">
122: * Java Collections Framework</a>.
123: *
124: * @author Doug Lea
125: * @author Josh Bloch
126: * @author Arthur van Hoff
127: * @author Neal Gafter
128: * @version 1.65, 03/03/05
129: * @see Object#hashCode()
130: * @see Collection
131: * @see Map
132: * @see TreeMap
133: * @see Hashtable
134: * @since 1.2
135: */
136:
137: public class LongHashMap<K>
138: //extends AbstractMap<K>
139: //implements Map<K>, Cloneable, Serializable
140: {
141:
142: public static final long NO_VALUE = Long.MIN_VALUE;
143:
144: /**
145: * The default initial capacity - MUST be a power of two.
146: */
147: static final int DEFAULT_INITIAL_CAPACITY = 16;
148:
149: /**
150: * The maximum capacity, used if a higher value is implicitly specified
151: * by either of the constructors with arguments.
152: * MUST be a power of two <= 1<<30.
153: */
154: static final int MAXIMUM_CAPACITY = 1 << 30;
155:
156: /**
157: * The load factor used when none specified in constructor.
158: **/
159: static final float DEFAULT_LOAD_FACTOR = 0.75f;
160:
161: /**
162: * The table, resized as necessary. Length MUST Always be a power of two.
163: */
164: transient Entry<K>[] table;
165:
166: /**
167: * The number of key-value mappings contained in this identity hash map.
168: */
169: transient int size;
170:
171: /**
172: * The next size value at which to resize (capacity * load factor).
173: * @serial
174: */
175: int threshold;
176:
177: /**
178: * The load factor for the hash table.
179: *
180: * @serial
181: */
182: final float loadFactor;
183:
184: /**
185: * The number of times this LongHashMap has been structurally modified
186: * Structural modifications are those that change the number of mappings in
187: * the LongHashMap or otherwise modify its internal structure (e.g.,
188: * rehash). This field is used to make iterators on Collection-views of
189: * the LongHashMap fail-fast. (See ConcurrentModificationException).
190: */
191: transient volatile int modCount;
192:
193: /**
194: * Constructs an empty <tt>LongHashMap</tt> with the specified initial
195: * capacity and load factor.
196: *
197: * @param initialCapacity The initial capacity.
198: * @param loadFactor The load factor.
199: * @throws IllegalArgumentException if the initial capacity is negative
200: * or the load factor is nonpositive.
201: */
202: public LongHashMap(int initialCapacity, float loadFactor) {
203: if (initialCapacity < 0)
204: throw new IllegalArgumentException(
205: "Illegal initial capacity: " + // NOI18N
206: initialCapacity);
207: if (initialCapacity > MAXIMUM_CAPACITY)
208: initialCapacity = MAXIMUM_CAPACITY;
209: if (loadFactor <= 0 || Float.isNaN(loadFactor))
210: throw new IllegalArgumentException("Illegal load factor: " + // NOI18N
211: loadFactor);
212:
213: // Find a power of 2 >= initialCapacity
214: int capacity = 1;
215: while (capacity < initialCapacity)
216: capacity <<= 1;
217:
218: this .loadFactor = loadFactor;
219: threshold = (int) (capacity * loadFactor);
220: table = new Entry[capacity];
221: init();
222: }
223:
224: /**
225: * Constructs an empty <tt>LongHashMap</tt> with the specified initial
226: * capacity and the default load factor (0.75).
227: *
228: * @param initialCapacity the initial capacity.
229: * @throws IllegalArgumentException if the initial capacity is negative.
230: */
231: public LongHashMap(int initialCapacity) {
232: this (initialCapacity, DEFAULT_LOAD_FACTOR);
233: }
234:
235: /**
236: * Constructs an empty <tt>LongHashMap</tt> with the default initial capacity
237: * (16) and the default load factor (0.75).
238: */
239: public LongHashMap() {
240: this .loadFactor = DEFAULT_LOAD_FACTOR;
241: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
242: table = new Entry[DEFAULT_INITIAL_CAPACITY];
243: init();
244: }
245:
246: // internal utilities
247:
248: /**
249: * Initialization hook for subclasses. This method is called
250: * in all constructors and pseudo-constructors (clone, readObject)
251: * after LongHashMap has been initialized but before any entries have
252: * been inserted. (In the absence of this method, readObject would
253: * require explicit knowledge of subclasses.)
254: */
255: void init() {
256: }
257:
258: /**
259: * Value representing null keys inside tables.
260: */
261: static final Object NULL_KEY = new Object();
262:
263: /**
264: * Returns internal representation for key. Use NULL_KEY if key is null.
265: */
266: static <T> T maskNull(T key) {
267: return key == null ? (T) NULL_KEY : key;
268: }
269:
270: /**
271: * Returns key represented by specified internal representation.
272: */
273: static <T> T unmaskNull(T key) {
274: return (key == NULL_KEY ? null : key);
275: }
276:
277: /**
278: * Whether to prefer the old supplemental hash function, for
279: * compatibility with broken applications that rely on the
280: * internal hashing order.
281: *
282: * Set to true only by hotspot when invoked via
283: * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
284: */
285: private static final boolean useNewHash;
286: static {
287: useNewHash = false;
288: }
289:
290: private static int oldHash(int h) {
291: h += ~(h << 9);
292: h ^= (h >>> 14);
293: h += (h << 4);
294: h ^= (h >>> 10);
295: return h;
296: }
297:
298: private static int newHash(int h) {
299: // This function ensures that hashCodes that differ only by
300: // constant multiples at each bit position have a bounded
301: // number of collisions (approximately 8 at default load factor).
302: h ^= (h >>> 20) ^ (h >>> 12);
303: return h ^ (h >>> 7) ^ (h >>> 4);
304: }
305:
306: /**
307: * Applies a supplemental hash function to a given hashCode, which
308: * defends against poor quality hash functions. This is critical
309: * because LongHashMap uses power-of-two length hash tables, that
310: * otherwise encounter collisions for hashCodes that do not differ
311: * in lower bits.
312: */
313: static int hash(int h) {
314: return useNewHash ? newHash(h) : oldHash(h);
315: }
316:
317: static int hash(Object key) {
318: return hash(key.hashCode());
319: }
320:
321: /**
322: * Check for equality of non-null reference x and possibly-null y.
323: */
324: static boolean eq(Object x, Object y) {
325: return x == y || x.equals(y);
326: }
327:
328: /**
329: * Returns index for hash code h.
330: */
331: static int indexFor(int h, int length) {
332: return h & (length - 1);
333: }
334:
335: /**
336: * Returns the number of key-value mappings in this map.
337: *
338: * @return the number of key-value mappings in this map.
339: */
340: public int size() {
341: return size;
342: }
343:
344: /**
345: * Returns <tt>true</tt> if this map contains no key-value mappings.
346: *
347: * @return <tt>true</tt> if this map contains no key-value mappings.
348: */
349: public boolean isEmpty() {
350: return size == 0;
351: }
352:
353: /**
354: * Returns the value to which the specified key is mapped in this identity
355: * hash map, or <tt>null</tt> if the map contains no mapping for this key.
356: * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
357: * that the map contains no mapping for the key; it is also possible that
358: * the map explicitly maps the key to <tt>null</tt>. The
359: * <tt>containsKey</tt> method may be used to distinguish these two cases.
360: *
361: * @param key the key whose associated value is to be returned.
362: * @return the value to which this map maps the specified key, or
363: * <tt>null</tt> if the map contains no mapping for this key.
364: * @see #put(Object, Object)
365: */
366: public long get(Object key) {
367: if (key == null)
368: return getForNullKey();
369: int hash = hash(key.hashCode());
370: for (Entry<K> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
371: Object k;
372: if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
373: return e.value;
374: }
375: return NO_VALUE;
376: }
377:
378: private long getForNullKey() {
379: int hash = hash(NULL_KEY.hashCode());
380: int i = indexFor(hash, table.length);
381: Entry<K> e = table[i];
382: while (true) {
383: if (e == null)
384: return NO_VALUE;
385: if (e.key == NULL_KEY)
386: return e.value;
387: e = e.next;
388: }
389: }
390:
391: /**
392: * Returns <tt>true</tt> if this map contains a mapping for the
393: * specified key.
394: *
395: * @param key The key whose presence in this map is to be tested
396: * @return <tt>true</tt> if this map contains a mapping for the specified
397: * key.
398: */
399: public boolean containsKey(Object key) {
400: Object k = maskNull(key);
401: int hash = hash(k.hashCode());
402: int i = indexFor(hash, table.length);
403: Entry e = table[i];
404: while (e != null) {
405: if (e.hash == hash && eq(k, e.key))
406: return true;
407: e = e.next;
408: }
409: return false;
410: }
411:
412: /**
413: * Returns the entry associated with the specified key in the
414: * LongHashMap. Returns null if the LongHashMap contains no mapping
415: * for this key.
416: */
417: public Entry<K> getEntry(Object key) {
418: Object k = maskNull(key);
419: int hash = hash(k.hashCode());
420: int i = indexFor(hash, table.length);
421: Entry<K> e = table[i];
422: while (e != null && !(e.hash == hash && eq(k, e.key)))
423: e = e.next;
424: return e;
425: }
426:
427: /**
428: * Associates the specified value with the specified key in this map.
429: * If the map previously contained a mapping for this key, the old
430: * value is replaced.
431: *
432: * @param key key with which the specified value is to be associated.
433: * @param value value to be associated with the specified key.
434: * @return previous value associated with specified key, or <tt>null</tt>
435: * if there was no mapping for key. A <tt>null</tt> return can
436: * also indicate that the LongHashMap previously associated
437: * <tt>null</tt> with the specified key.
438: */
439: public long put(K key, long value) {
440: if (key == null)
441: return putForNullKey(value);
442: int hash = hash(key.hashCode());
443: int i = indexFor(hash, table.length);
444: for (Entry<K> e = table[i]; e != null; e = e.next) {
445: Object k;
446: if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
447: long oldValue = e.value;
448: e.value = value;
449: e.recordAccess(this );
450: return oldValue;
451: }
452: }
453:
454: modCount++;
455: addEntry(hash, key, value, i);
456: return NO_VALUE;
457: }
458:
459: private long putForNullKey(long value) {
460: int hash = hash(NULL_KEY.hashCode());
461: int i = indexFor(hash, table.length);
462:
463: for (Entry<K> e = table[i]; e != null; e = e.next) {
464: if (e.key == NULL_KEY) {
465: long oldValue = e.value;
466: e.value = value;
467: e.recordAccess(this );
468: return oldValue;
469: }
470: }
471:
472: modCount++;
473: addEntry(hash, (K) NULL_KEY, value, i);
474: return NO_VALUE;
475: }
476:
477: /**
478: * This method is used instead of put by constructors and
479: * pseudoconstructors (clone, readObject). It does not resize the table,
480: * check for comodification, etc. It calls createEntry rather than
481: * addEntry.
482: */
483: // private void putForCreate(K key, long value) {
484: // K k = maskNull(key);
485: // int hash = hash(k.hashCode());
486: // int i = indexFor(hash, table.length);
487: //
488: // /**
489: // * Look for preexisting entry for key. This will never happen for
490: // * clone or deserialize. It will only happen for construction if the
491: // * input Map is a sorted map whose ordering is inconsistent w/ equals.
492: // */
493: // for (Entry<K> e = table[i]; e != null; e = e.next) {
494: // if (e.hash == hash && eq(k, e.key)) {
495: // e.value = value;
496: // return;
497: // }
498: // }
499: //
500: // createEntry(hash, k, value, i);
501: // }
502: /**
503: * Rehashes the contents of this map into a new array with a
504: * larger capacity. This method is called automatically when the
505: * number of keys in this map reaches its threshold.
506: *
507: * If current capacity is MAXIMUM_CAPACITY, this method does not
508: * resize the map, but sets threshold to Integer.MAX_VALUE.
509: * This has the effect of preventing future calls.
510: *
511: * @param newCapacity the new capacity, MUST be a power of two;
512: * must be greater than current capacity unless current
513: * capacity is MAXIMUM_CAPACITY (in which case value
514: * is irrelevant).
515: */
516: void resize(int newCapacity) {
517: Entry<K>[] oldTable = table;
518: int oldCapacity = oldTable.length;
519: if (oldCapacity == MAXIMUM_CAPACITY) {
520: threshold = Integer.MAX_VALUE;
521: return;
522: }
523:
524: Entry<K>[] newTable = new Entry[newCapacity];
525: transfer(newTable);
526: table = newTable;
527: threshold = (int) (newCapacity * loadFactor);
528: }
529:
530: /**
531: * Transfer all entries from current table to newTable.
532: */
533: void transfer(Entry[] newTable) {
534: Entry<K>[] src = table;
535: int newCapacity = newTable.length;
536: for (int j = 0; j < src.length; j++) {
537: Entry<K> e = src[j];
538: if (e != null) {
539: src[j] = null;
540: do {
541: Entry<K> next = e.next;
542: int i = indexFor(e.hash, newCapacity);
543: e.next = newTable[i];
544: newTable[i] = e;
545: e = next;
546: } while (e != null);
547: }
548: }
549: }
550:
551: public long remove(Object key) {
552: Entry<K> e = removeEntryForKey(key);
553: return (e == null ? NO_VALUE : e.value);
554: }
555:
556: /**
557: * Removes and returns the entry associated with the specified key
558: * in the LongHashMap. Returns null if the LongHashMap contains no mapping
559: * for this key.
560: */
561: Entry<K> removeEntryForKey(Object key) {
562: Object k = maskNull(key);
563: int hash = hash(k.hashCode());
564: int i = indexFor(hash, table.length);
565: Entry<K> prev = table[i];
566: Entry<K> e = prev;
567:
568: while (e != null) {
569: Entry<K> next = e.next;
570: if (e.hash == hash && eq(k, e.key)) {
571: modCount++;
572: size--;
573: if (prev == e)
574: table[i] = next;
575: else
576: prev.next = next;
577: e.recordRemoval(this );
578: return e;
579: }
580: prev = e;
581: e = next;
582: }
583:
584: return e;
585: }
586:
587: /**
588: * Special version of remove for EntrySet.
589: */
590: Entry<K> removeMapping(Object o) {
591: if (!(o instanceof Map.Entry))
592: return null;
593:
594: LongHashMap.Entry<K> entry = (LongHashMap.Entry<K>) o;
595: Object k = maskNull(entry.getKey());
596: int hash = hash(k.hashCode());
597: int i = indexFor(hash, table.length);
598: Entry<K> prev = table[i];
599: Entry<K> e = prev;
600:
601: while (e != null) {
602: Entry<K> next = e.next;
603: if (e.hash == hash && e.equals(entry)) {
604: modCount++;
605: size--;
606: if (prev == e)
607: table[i] = next;
608: else
609: prev.next = next;
610: e.recordRemoval(this );
611: return e;
612: }
613: prev = e;
614: e = next;
615: }
616:
617: return e;
618: }
619:
620: /**
621: * Removes all mappings from this map.
622: */
623: public void clear() {
624: modCount++;
625: Entry[] tab = table;
626: for (int i = 0; i < tab.length; i++)
627: tab[i] = null;
628: size = 0;
629: }
630:
631: /**
632: * Returns <tt>true</tt> if this map maps one or more keys to the
633: * specified value.
634: *
635: * @param value value whose presence in this map is to be tested.
636: * @return <tt>true</tt> if this map maps one or more keys to the
637: * specified value.
638: */
639: public boolean containsValue(Object value) {
640: if (value == null)
641: return containsNullValue();
642:
643: Entry[] tab = table;
644: for (int i = 0; i < tab.length; i++)
645: for (Entry e = tab[i]; e != null; e = e.next)
646: if (value.equals(e.value))
647: return true;
648: return false;
649: }
650:
651: /**
652: * Special-case code for containsValue with null argument
653: **/
654: private boolean containsNullValue() {
655: Entry[] tab = table;
656: for (int i = 0; i < tab.length; i++)
657: for (Entry e = tab[i]; e != null; e = e.next)
658: if (e.value == NO_VALUE)
659: return true;
660: return false;
661: }
662:
663: public static class Entry<K> /*implements Map.Entry<K>*/{
664: final K key;
665: long value;
666: final int hash;
667: Entry<K> next;
668:
669: /**
670: * Create new entry.
671: */
672: Entry(int h, K k, long v, Entry<K> n) {
673: value = v;
674: next = n;
675: key = k;
676: hash = h;
677: }
678:
679: public K getKey() {
680: return LongHashMap.<K> unmaskNull(key);
681: }
682:
683: public long getValue() {
684: return value;
685: }
686:
687: public long setValue(long newValue) {
688: long oldValue = value;
689: value = newValue;
690: return oldValue;
691: }
692:
693: public boolean equals(Object o) {
694: if (!(o instanceof Map.Entry))
695: return false;
696: Map.Entry e = (Map.Entry) o;
697: Object k1 = getKey();
698: Object k2 = e.getKey();
699: if (k1 == k2 || (k1 != null && k1.equals(k2))) {
700: Object v1 = getValue();
701: Object v2 = e.getValue();
702: if (v1 == v2 || (v1 != null && v1.equals(v2)))
703: return true;
704: }
705: return false;
706: }
707:
708: public int hashCode() {
709: return (int) (value ^ (value >>> 32));
710: }
711:
712: public String toString() {
713: return getKey() + "=" + getValue(); // NOI18N
714: }
715:
716: /**
717: * This method is invoked whenever the value in an entry is
718: * overwritten by an invocation of put(k,v) for a key k that's already
719: * in the LongHashMap.
720: */
721: void recordAccess(LongHashMap<K> m) {
722: }
723:
724: /**
725: * This method is invoked whenever the entry is
726: * removed from the table.
727: */
728: void recordRemoval(LongHashMap<K> m) {
729: }
730: }
731:
732: /**
733: * Add a new entry with the specified key, value and hash code to
734: * the specified bucket. It is the responsibility of this
735: * method to resize the table if appropriate.
736: *
737: * Subclass overrides this to alter the behavior of put method.
738: */
739: void addEntry(int hash, K key, long value, int bucketIndex) {
740: Entry<K> e = table[bucketIndex];
741: table[bucketIndex] = new Entry<K>(hash, key, value, e);
742: if (size++ >= threshold)
743: resize(2 * table.length);
744: }
745:
746: /**
747: * Like addEntry except that this version is used when creating entries
748: * as part of Map construction or "pseudo-construction" (cloning,
749: * deserialization). This version needn't worry about resizing the table.
750: *
751: * Subclass overrides this to alter the behavior of LongHashMap(Map),
752: * clone, and readObject.
753: */
754: void createEntry(int hash, K key, long value, int bucketIndex) {
755: Entry<K> e = table[bucketIndex];
756: table[bucketIndex] = new Entry<K>(hash, key, value, e);
757: size++;
758: }
759:
760: private abstract class HashIterator<E> implements Iterator<E> {
761: Entry<K> next; // next entry to return
762: int expectedModCount; // For fast-fail
763: int index; // current slot
764: Entry<K> current; // current entry
765:
766: HashIterator() {
767: expectedModCount = modCount;
768: Entry[] t = table;
769: int i = t.length;
770: Entry<K> n = null;
771: if (size != 0) { // advance to first entry
772: while (i > 0 && (n = t[--i]) == null)
773: ;
774: }
775: next = n;
776: index = i;
777: }
778:
779: public boolean hasNext() {
780: return next != null;
781: }
782:
783: Entry<K> nextEntry() {
784: if (modCount != expectedModCount)
785: throw new ConcurrentModificationException();
786: Entry<K> e = next;
787: if (e == null)
788: throw new NoSuchElementException();
789:
790: Entry<K> n = e.next;
791: Entry[] t = table;
792: int i = index;
793: while (n == null && i > 0)
794: n = t[--i];
795: index = i;
796: next = n;
797: return current = e;
798: }
799:
800: public void remove() {
801: if (current == null)
802: throw new IllegalStateException();
803: if (modCount != expectedModCount)
804: throw new ConcurrentModificationException();
805: Object k = current.key;
806: current = null;
807: LongHashMap.this .removeEntryForKey(k);
808: expectedModCount = modCount;
809: }
810:
811: }
812:
813: private class KeyIterator extends HashIterator<K> {
814: public K next() {
815: return nextEntry().getKey();
816: }
817: }
818:
819: private class EntryIterator extends
820: HashIterator<LongHashMap.Entry<K>> {
821: public LongHashMap.Entry<K> next() {
822: return nextEntry();
823: }
824: }
825:
826: // Subclass overrides these to alter behavior of views' iterator() method
827: Iterator<K> newKeyIterator() {
828: return new KeyIterator();
829: }
830:
831: Iterator<LongHashMap.Entry<K>> newEntryIterator() {
832: return new EntryIterator();
833: }
834:
835: // Views
836:
837: private transient Set<LongHashMap.Entry<K>> entrySet = null;
838:
839: /**
840: * Each of these fields are initialized to contain an instance of the
841: * appropriate view the first time this view is requested. The views are
842: * stateless, so there's no reason to create more than one of each.
843: */
844: transient volatile Set<K> keySet = null;
845:
846: /**
847: * Returns a set view of the keys contained in this map. The set is
848: * backed by the map, so changes to the map are reflected in the set, and
849: * vice-versa. The set supports element removal, which removes the
850: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
851: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
852: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
853: * <tt>addAll</tt> operations.
854: *
855: * @return a set view of the keys contained in this map.
856: */
857: public Set<K> keySet() {
858: Set<K> ks = keySet;
859: return (ks != null ? ks : (keySet = new KeySet()));
860: }
861:
862: private class KeySet extends AbstractSet<K> {
863: public Iterator<K> iterator() {
864: return newKeyIterator();
865: }
866:
867: public int size() {
868: return size;
869: }
870:
871: public boolean contains(Object o) {
872: return containsKey(o);
873: }
874:
875: public boolean remove(Object o) {
876: return LongHashMap.this .removeEntryForKey(o) != null;
877: }
878:
879: public void clear() {
880: LongHashMap.this .clear();
881: }
882: }
883:
884: /**
885: * Returns a collection view of the mappings contained in this map. Each
886: * element in the returned collection is a <tt>Map.Entry</tt>. The
887: * collection is backed by the map, so changes to the map are reflected in
888: * the collection, and vice-versa. The collection supports element
889: * removal, which removes the corresponding mapping from the map, via the
890: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
891: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
892: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
893: *
894: * @return a collection view of the mappings contained in this map.
895: * @see Map.Entry
896: */
897: public Set<LongHashMap.Entry<K>> entrySet() {
898: Set<LongHashMap.Entry<K>> es = entrySet;
899: return (es != null ? es
900: : (entrySet = (Set<LongHashMap.Entry<K>>) (Set) new EntrySet()));
901: }
902:
903: private class EntrySet extends AbstractSet/*<Map.Entry<K>>*/{
904: public Iterator/*<Map.Entry<K>>*/iterator() {
905: return newEntryIterator();
906: }
907:
908: public boolean contains(Object o) {
909: if (!(o instanceof Map.Entry))
910: return false;
911: LongHashMap.Entry<K> e = (LongHashMap.Entry<K>) o;
912: Entry<K> candidate = getEntry(e.getKey());
913: return candidate != null && candidate.equals(e);
914: }
915:
916: public boolean remove(Object o) {
917: return removeMapping(o) != null;
918: }
919:
920: public int size() {
921: return size;
922: }
923:
924: public void clear() {
925: LongHashMap.this .clear();
926: }
927: }
928:
929: // These methods are used when serializing HashSets
930: int capacity() {
931: return table.length;
932: }
933:
934: float loadFactor() {
935: return loadFactor;
936: }
937: }
|