View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5    * "License"); you may not use this file except in compliance with the License. You may obtain a
6    * copy of the License at:
7    *
8    * https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software distributed under the License
11   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12   * or implied. See the License for the specific language governing permissions and limitations under
13   * the License.
14   */
15  
16  package io.netty.util.collection;
17  
18  import static io.netty.util.internal.MathUtil.safeFindNextPositivePowerOfTwo;
19  
20  import java.util.AbstractCollection;
21  import java.util.AbstractSet;
22  import java.util.Arrays;
23  import java.util.Collection;
24  import java.util.Iterator;
25  import java.util.Map;
26  import java.util.NoSuchElementException;
27  import java.util.Set;
28  
29  /**
30   * A hash map implementation of {@link CharObjectMap} that uses open addressing for keys.
31   * To minimize the memory footprint, this class uses open addressing rather than chaining.
32   * Collisions are resolved using linear probing. Deletions implement compaction, so cost of
33   * remove can approach O(N) for full maps, which makes a small loadFactor recommended.
34   *
35   * @param <V> The value type stored in the map.
36   */
37  public class CharObjectHashMap<V> implements CharObjectMap<V> {
38  
39      /** Default initial capacity. Used if not specified in the constructor */
40      public static final int DEFAULT_CAPACITY = 8;
41  
42      /** Default load factor. Used if not specified in the constructor */
43      public static final float DEFAULT_LOAD_FACTOR = 0.5f;
44  
45      /**
46       * Placeholder for null values, so we can use the actual null to mean available.
47       * (Better than using a placeholder for available: less references for GC processing.)
48       */
49      private static final Object NULL_VALUE = new Object();
50  
51      /** The maximum number of elements allowed without allocating more space. */
52      private int maxSize;
53  
54      /** The load factor for the map. Used to calculate {@link #maxSize}. */
55      private final float loadFactor;
56  
57      private char[] keys;
58      private V[] values;
59      private int size;
60      private int mask;
61  
62      private final Set<Character> keySet = new KeySet();
63      private final Set<Entry<Character, V>> entrySet = new EntrySet();
64      private final Iterable<PrimitiveEntry<V>> entries = new Iterable<PrimitiveEntry<V>>() {
65          @Override
66          public Iterator<PrimitiveEntry<V>> iterator() {
67              return new PrimitiveIterator();
68          }
69      };
70  
71      public CharObjectHashMap() {
72          this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
73      }
74  
75      public CharObjectHashMap(int initialCapacity) {
76          this(initialCapacity, DEFAULT_LOAD_FACTOR);
77      }
78  
79      public CharObjectHashMap(int initialCapacity, float loadFactor) {
80          if (loadFactor <= 0.0f || loadFactor > 1.0f) {
81              // Cannot exceed 1 because we can never store more than capacity elements;
82              // using a bigger loadFactor would trigger rehashing before the desired load is reached.
83              throw new IllegalArgumentException("loadFactor must be > 0 and <= 1");
84          }
85  
86          this.loadFactor = loadFactor;
87  
88          // Adjust the initial capacity if necessary.
89          int capacity = safeFindNextPositivePowerOfTwo(initialCapacity);
90          mask = capacity - 1;
91  
92          // Allocate the arrays.
93          keys = new char[capacity];
94          @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
95          V[] temp = (V[]) new Object[capacity];
96          values = temp;
97  
98          // Initialize the maximum size value.
99          maxSize = calcMaxSize(capacity);
100     }
101 
102     private static <T> T toExternal(T value) {
103         assert value != null : "null is not a legitimate internal value. Concurrent Modification?";
104         return value == NULL_VALUE ? null : value;
105     }
106 
107     @SuppressWarnings("unchecked")
108     private static <T> T toInternal(T value) {
109         return value == null ? (T) NULL_VALUE : value;
110     }
111 
112     @Override
113     public V get(char key) {
114         int index = indexOf(key);
115         return index == -1 ? null : toExternal(values[index]);
116     }
117 
118     @Override
119     public V put(char key, V value) {
120         int startIndex = hashIndex(key);
121         int index = startIndex;
122 
123         for (;;) {
124             if (values[index] == null) {
125                 // Found empty slot, use it.
126                 keys[index] = key;
127                 values[index] = toInternal(value);
128                 growSize();
129                 return null;
130             }
131             if (keys[index] == key) {
132                 // Found existing entry with this key, just replace the value.
133                 V previousValue = values[index];
134                 values[index] = toInternal(value);
135                 return toExternal(previousValue);
136             }
137 
138             // Conflict, keep probing ...
139             if ((index = probeNext(index)) == startIndex) {
140                 // Can only happen if the map was full at MAX_ARRAY_SIZE and couldn't grow.
141                 throw new IllegalStateException("Unable to insert");
142             }
143         }
144     }
145 
146     @Override
147     public void putAll(Map<? extends Character, ? extends V> sourceMap) {
148         if (sourceMap instanceof CharObjectHashMap) {
149             // Optimization - iterate through the arrays.
150             @SuppressWarnings("unchecked")
151             CharObjectHashMap<V> source = (CharObjectHashMap<V>) sourceMap;
152             for (int i = 0; i < source.values.length; ++i) {
153                 V sourceValue = source.values[i];
154                 if (sourceValue != null) {
155                     put(source.keys[i], sourceValue);
156                 }
157             }
158             return;
159         }
160 
161         // Otherwise, just add each entry.
162         for (Entry<? extends Character, ? extends V> entry : sourceMap.entrySet()) {
163             put(entry.getKey(), entry.getValue());
164         }
165     }
166 
167     @Override
168     public V remove(char key) {
169         int index = indexOf(key);
170         if (index == -1) {
171             return null;
172         }
173 
174         V prev = values[index];
175         removeAt(index);
176         return toExternal(prev);
177     }
178 
179     @Override
180     public int size() {
181         return size;
182     }
183 
184     @Override
185     public boolean isEmpty() {
186         return size == 0;
187     }
188 
189     @Override
190     public void clear() {
191         Arrays.fill(keys, (char) 0);
192         Arrays.fill(values, null);
193         size = 0;
194     }
195 
196     @Override
197     public boolean containsKey(char key) {
198         return indexOf(key) >= 0;
199     }
200 
201     @Override
202     public boolean containsValue(Object value) {
203         @SuppressWarnings("unchecked")
204         V v1 = toInternal((V) value);
205         for (V v2 : values) {
206             // The map supports null values; this will be matched as NULL_VALUE.equals(NULL_VALUE).
207             if (v2 != null && v2.equals(v1)) {
208                 return true;
209             }
210         }
211         return false;
212     }
213 
214     @Override
215     public Iterable<PrimitiveEntry<V>> entries() {
216         return entries;
217     }
218 
219     @Override
220     public Collection<V> values() {
221         return new AbstractCollection<V>() {
222             @Override
223             public Iterator<V> iterator() {
224                 return new Iterator<V>() {
225                     final PrimitiveIterator iter = new PrimitiveIterator();
226 
227                     @Override
228                     public boolean hasNext() {
229                         return iter.hasNext();
230                     }
231 
232                     @Override
233                     public V next() {
234                         return iter.next().value();
235                     }
236 
237                     @Override
238                     public void remove() {
239                         iter.remove();
240                     }
241                 };
242             }
243 
244             @Override
245             public int size() {
246                 return size;
247             }
248         };
249     }
250 
251     @Override
252     public int hashCode() {
253         // Hashcode is based on all non-zero, valid keys. We have to scan the whole keys
254         // array, which may have different lengths for two maps of same size(), so the
255         // capacity cannot be used as input for hashing but the size can.
256         int hash = size;
257         for (char key : keys) {
258             // 0 can be a valid key or unused slot, but won't impact the hashcode in either case.
259             // This way we can use a cheap loop without conditionals, or hard-to-unroll operations,
260             // or the devastatingly bad memory locality of visiting value objects.
261             // Also, it's important to use a hash function that does not depend on the ordering
262             // of terms, only their values; since the map is an unordered collection and
263             // entries can end up in different positions in different maps that have the same
264             // elements, but with different history of puts/removes, due to conflicts.
265             hash ^= hashCode(key);
266         }
267         return hash;
268     }
269 
270     @Override
271     public boolean equals(Object obj) {
272         if (this == obj) {
273             return true;
274         }
275         if (!(obj instanceof CharObjectMap)) {
276             return false;
277         }
278         @SuppressWarnings("rawtypes")
279         CharObjectMap other = (CharObjectMap) obj;
280         if (size != other.size()) {
281             return false;
282         }
283         for (int i = 0; i < values.length; ++i) {
284             V value = values[i];
285             if (value != null) {
286                 char key = keys[i];
287                 Object otherValue = other.get(key);
288                 if (value == NULL_VALUE) {
289                     if (otherValue != null) {
290                         return false;
291                     }
292                 } else if (!value.equals(otherValue)) {
293                     return false;
294                 }
295             }
296         }
297         return true;
298     }
299 
300     @Override
301     public boolean containsKey(Object key) {
302         return containsKey(objectToKey(key));
303     }
304 
305     @Override
306     public V get(Object key) {
307         return get(objectToKey(key));
308     }
309 
310     @Override
311     public V put(Character key, V value) {
312         return put(objectToKey(key), value);
313     }
314 
315     @Override
316     public V remove(Object key) {
317         return remove(objectToKey(key));
318     }
319 
320     @Override
321     public Set<Character> keySet() {
322         return keySet;
323     }
324 
325     @Override
326     public Set<Entry<Character, V>> entrySet() {
327         return entrySet;
328     }
329 
330     private char objectToKey(Object key) {
331         return (char) ((Character) key).charValue();
332     }
333 
334     /**
335      * Locates the index for the given key. This method probes using double hashing.
336      *
337      * @param key the key for an entry in the map.
338      * @return the index where the key was found, or {@code -1} if no entry is found for that key.
339      */
340     private int indexOf(char key) {
341         int startIndex = hashIndex(key);
342         int index = startIndex;
343 
344         for (;;) {
345             if (values[index] == null) {
346                 // It's available, so no chance that this value exists anywhere in the map.
347                 return -1;
348             }
349             if (key == keys[index]) {
350                 return index;
351             }
352 
353             // Conflict, keep probing ...
354             if ((index = probeNext(index)) == startIndex) {
355                 return -1;
356             }
357         }
358     }
359 
360     /**
361      * Returns the hashed index for the given key.
362      */
363     private int hashIndex(char key) {
364         // The array lengths are always a power of two, so we can use a bitmask to stay inside the array bounds.
365         return hashCode(key) & mask;
366     }
367 
368     /**
369      * Returns the hash code for the key.
370      */
371     private static int hashCode(char key) {
372        return (int) key;
373     }
374 
375     /**
376      * Get the next sequential index after {@code index} and wraps if necessary.
377      */
378     private int probeNext(int index) {
379         // The array lengths are always a power of two, so we can use a bitmask to stay inside the array bounds.
380         return (index + 1) & mask;
381     }
382 
383     /**
384      * Grows the map size after an insertion. If necessary, performs a rehash of the map.
385      */
386     private void growSize() {
387         size++;
388 
389         if (size > maxSize) {
390             if(keys.length == Integer.MAX_VALUE) {
391                 throw new IllegalStateException("Max capacity reached at size=" + size);
392             }
393 
394             // Double the capacity.
395             rehash(keys.length << 1);
396         }
397     }
398 
399     /**
400      * Removes entry at the given index position. Also performs opportunistic, incremental rehashing
401      * if necessary to not break conflict chains.
402      *
403      * @param index the index position of the element to remove.
404      * @return {@code true} if the next item was moved back. {@code false} otherwise.
405      */
406     private boolean removeAt(final int index) {
407         --size;
408         // Clearing the key is not strictly necessary (for GC like in a regular collection),
409         // but recommended for security. The memory location is still fresh in the cache anyway.
410         keys[index] = 0;
411         values[index] = null;
412 
413         // In the interval from index to the next available entry, the arrays may have entries
414         // that are displaced from their base position due to prior conflicts. Iterate these
415         // entries and move them back if possible, optimizing future lookups.
416         // Knuth Section 6.4 Algorithm R, also used by the JDK's IdentityHashMap.
417 
418         int nextFree = index;
419         int i = probeNext(index);
420         for (V value = values[i]; value != null; value = values[i = probeNext(i)]) {
421             char key = keys[i];
422             int bucket = hashIndex(key);
423             if (i < bucket && (bucket <= nextFree || nextFree <= i) ||
424                 bucket <= nextFree && nextFree <= i) {
425                 // Move the displaced entry "back" to the first available position.
426                 keys[nextFree] = key;
427                 values[nextFree] = value;
428                 // Put the first entry after the displaced entry
429                 keys[i] = 0;
430                 values[i] = null;
431                 nextFree = i;
432             }
433         }
434         return nextFree != index;
435     }
436 
437     /**
438      * Calculates the maximum size allowed before rehashing.
439      */
440     private int calcMaxSize(int capacity) {
441         // Clip the upper bound so that there will always be at least one available slot.
442         int upperBound = capacity - 1;
443         return Math.min(upperBound, (int) (capacity * loadFactor));
444     }
445 
446     /**
447      * Rehashes the map for the given capacity.
448      *
449      * @param newCapacity the new capacity for the map.
450      */
451     private void rehash(int newCapacity) {
452         char[] oldKeys = keys;
453         V[] oldVals = values;
454 
455         keys = new char[newCapacity];
456         @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
457         V[] temp = (V[]) new Object[newCapacity];
458         values = temp;
459 
460         maxSize = calcMaxSize(newCapacity);
461         mask = newCapacity - 1;
462 
463         // Insert to the new arrays.
464         for (int i = 0; i < oldVals.length; ++i) {
465             V oldVal = oldVals[i];
466             if (oldVal != null) {
467                 // Inlined put(), but much simpler: we don't need to worry about
468                 // duplicated keys, growing/rehashing, or failing to insert.
469                 char oldKey = oldKeys[i];
470                 int index = hashIndex(oldKey);
471 
472                 for (;;) {
473                     if (values[index] == null) {
474                         keys[index] = oldKey;
475                         values[index] = oldVal;
476                         break;
477                     }
478 
479                     // Conflict, keep probing. Can wrap around, but never reaches startIndex again.
480                     index = probeNext(index);
481                 }
482             }
483         }
484     }
485 
486     @Override
487     public String toString() {
488         if (isEmpty()) {
489             return "{}";
490         }
491         StringBuilder sb = new StringBuilder(4 * size);
492         sb.append('{');
493         boolean first = true;
494         for (int i = 0; i < values.length; ++i) {
495             V value = values[i];
496             if (value != null) {
497                 if (!first) {
498                     sb.append(", ");
499                 }
500                 sb.append(keyToString(keys[i])).append('=').append(value == this ? "(this Map)" :
501                     toExternal(value));
502                 first = false;
503             }
504         }
505         return sb.append('}').toString();
506     }
507 
508     /**
509      * Helper method called by {@link #toString()} in order to convert a single map key into a string.
510      * This is protected to allow subclasses to override the appearance of a given key.
511      */
512     protected String keyToString(char key) {
513         return Character.toString(key);
514     }
515 
516     /**
517      * Set implementation for iterating over the entries of the map.
518      */
519     private final class EntrySet extends AbstractSet<Entry<Character, V>> {
520         @Override
521         public Iterator<Entry<Character, V>> iterator() {
522             return new MapIterator();
523         }
524 
525         @Override
526         public int size() {
527             return CharObjectHashMap.this.size();
528         }
529     }
530 
531     /**
532      * Set implementation for iterating over the keys.
533      */
534     private final class KeySet extends AbstractSet<Character> {
535         @Override
536         public int size() {
537             return CharObjectHashMap.this.size();
538         }
539 
540         @Override
541         public boolean contains(Object o) {
542             return CharObjectHashMap.this.containsKey(o);
543         }
544 
545         @Override
546         public boolean remove(Object o) {
547             return CharObjectHashMap.this.remove(o) != null;
548         }
549 
550         @Override
551         public boolean retainAll(Collection<?> retainedKeys) {
552             boolean changed = false;
553             for(Iterator<PrimitiveEntry<V>> iter = entries().iterator(); iter.hasNext(); ) {
554                 PrimitiveEntry<V> entry = iter.next();
555                 if (!retainedKeys.contains(entry.key())) {
556                     changed = true;
557                     iter.remove();
558                 }
559             }
560             return changed;
561         }
562 
563         @Override
564         public void clear() {
565             CharObjectHashMap.this.clear();
566         }
567 
568         @Override
569         public Iterator<Character> iterator() {
570             return new Iterator<Character>() {
571                 private final Iterator<Entry<Character, V>> iter = entrySet.iterator();
572 
573                 @Override
574                 public boolean hasNext() {
575                     return iter.hasNext();
576                 }
577 
578                 @Override
579                 public Character next() {
580                     return iter.next().getKey();
581                 }
582 
583                 @Override
584                 public void remove() {
585                     iter.remove();
586                 }
587             };
588         }
589     }
590 
591     /**
592      * Iterator over primitive entries. Entry key/values are overwritten by each call to {@link #next()}.
593      */
594     private final class PrimitiveIterator implements Iterator<PrimitiveEntry<V>>, PrimitiveEntry<V> {
595         private int prevIndex = -1;
596         private int nextIndex = -1;
597         private int entryIndex = -1;
598 
599         private void scanNext() {
600             while (++nextIndex != values.length && values[nextIndex] == null) {
601             }
602         }
603 
604         @Override
605         public boolean hasNext() {
606             if (nextIndex == -1) {
607                 scanNext();
608             }
609             return nextIndex != values.length;
610         }
611 
612         @Override
613         public PrimitiveEntry<V> next() {
614             if (!hasNext()) {
615                 throw new NoSuchElementException();
616             }
617 
618             prevIndex = nextIndex;
619             scanNext();
620 
621             // Always return the same Entry object, just change its index each time.
622             entryIndex = prevIndex;
623             return this;
624         }
625 
626         @Override
627         public void remove() {
628             if (prevIndex == -1) {
629                 throw new IllegalStateException("next must be called before each remove.");
630             }
631             if (removeAt(prevIndex)) {
632                 // removeAt may move elements "back" in the array if they have been displaced because their spot in the
633                 // array was occupied when they were inserted. If this occurs then the nextIndex is now invalid and
634                 // should instead point to the prevIndex which now holds an element which was "moved back".
635                 nextIndex = prevIndex;
636             }
637             prevIndex = -1;
638         }
639 
640         // Entry implementation. Since this implementation uses a single Entry, we coalesce that
641         // into the Iterator object (potentially making loop optimization much easier).
642 
643         @Override
644         public char key() {
645             return keys[entryIndex];
646         }
647 
648         @Override
649         public V value() {
650             return toExternal(values[entryIndex]);
651         }
652 
653         @Override
654         public void setValue(V value) {
655             values[entryIndex] = toInternal(value);
656         }
657     }
658 
659     /**
660      * Iterator used by the {@link Map} interface.
661      */
662     private final class MapIterator implements Iterator<Entry<Character, V>> {
663         private final PrimitiveIterator iter = new PrimitiveIterator();
664 
665         @Override
666         public boolean hasNext() {
667             return iter.hasNext();
668         }
669 
670         @Override
671         public Entry<Character, V> next() {
672             if (!hasNext()) {
673                 throw new NoSuchElementException();
674             }
675 
676             iter.next();
677 
678             return new MapEntry(iter.entryIndex);
679         }
680 
681         @Override
682         public void remove() {
683             iter.remove();
684         }
685     }
686 
687     /**
688      * A single entry in the map.
689      */
690     final class MapEntry implements Entry<Character, V> {
691         private final int entryIndex;
692 
693         MapEntry(int entryIndex) {
694             this.entryIndex = entryIndex;
695         }
696 
697         @Override
698         public Character getKey() {
699             verifyExists();
700             return keys[entryIndex];
701         }
702 
703         @Override
704         public V getValue() {
705             verifyExists();
706             return toExternal(values[entryIndex]);
707         }
708 
709         @Override
710         public V setValue(V value) {
711             verifyExists();
712             V prevValue = toExternal(values[entryIndex]);
713             values[entryIndex] = toInternal(value);
714             return prevValue;
715         }
716 
717         private void verifyExists() {
718             if (values[entryIndex] == null) {
719                 throw new IllegalStateException("The map entry has been removed");
720             }
721         }
722     }
723 }