View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.collections4.map;
18  
19  import java.util.AbstractCollection;
20  import java.util.AbstractSet;
21  import java.util.ArrayList;
22  import java.util.Collection;
23  import java.util.Iterator;
24  import java.util.Map;
25  import java.util.NoSuchElementException;
26  import java.util.Set;
27  
28  import org.apache.commons.collections4.KeyValue;
29  
30  /**
31   * A StaticBucketMap is an efficient, thread-safe implementation of
32   * <code>java.util.Map</code> that performs well in in a highly
33   * thread-contentious environment.  The map supports very efficient
34   * {@link #get(Object) get}, {@link #put(Object,Object) put},
35   * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
36   * operations, assuming (approximate) uniform hashing and
37   * that the number of entries does not exceed the number of buckets.  If the
38   * number of entries exceeds the number of buckets or if the hash codes of the
39   * objects are not uniformly distributed, these operations have a worst case
40   * scenario that is proportional to the number of elements in the map
41   * (<i>O(n)</i>).<p>
42   *
43   * Each bucket in the hash table has its own monitor, so two threads can
44   * safely operate on the map at the same time, often without incurring any
45   * monitor contention.  This means that you don't have to wrap instances
46   * of this class with {@link java.util.Collections#synchronizedMap(Map)};
47   * instances are already thread-safe.  Unfortunately, however, this means
48   * that this map implementation behaves in ways you may find disconcerting.
49   * Bulk operations, such as {@link #putAll(Map) putAll} or the
50   * {@link Collection#retainAll(Collection) retainAll} operation in collection
51   * views, are <i>not</i> atomic.  If two threads are simultaneously
52   * executing
53   *
54   * <pre>
55   *   staticBucketMapInstance.putAll(map);
56   * </pre>
57   *
58   * and
59   *
60   * <pre>
61   *   staticBucketMapInstance.entrySet().removeAll(map.entrySet());
62   * </pre>
63   *
64   * then the results are generally random.  Those two statement could cancel
65   * each other out, leaving <code>staticBucketMapInstance</code> essentially
66   * unchanged, or they could leave some random subset of <code>map</code> in
67   * <code>staticBucketMapInstance</code>.<p>
68   *
69   * Also, much like an encyclopedia, the results of {@link #size()} and
70   * {@link #isEmpty()} are out-of-date as soon as they are produced.<p>
71   *
72   * The iterators returned by the collection views of this class are <i>not</i>
73   * fail-fast.  They will <i>never</i> raise a
74   * {@link java.util.ConcurrentModificationException}.  Keys and values
75   * added to the map after the iterator is created do not necessarily appear
76   * during iteration.  Similarly, the iterator does not necessarily fail to
77   * return keys and values that were removed after the iterator was created.<p>
78   *
79   * Finally, unlike {@link java.util.HashMap}-style implementations, this
80   * class <i>never</i> rehashes the map.  The number of buckets is fixed
81   * at construction time and never altered.  Performance may degrade if
82   * you do not allocate enough buckets upfront.<p>
83   *
84   * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
85   * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
86   * will basically result in a map that's slower than an ordinary synchronized
87   * {@link java.util.HashMap}.
88   *
89   * Use this class if you do not require reliable bulk operations and
90   * iterations, or if you can make your own guarantees about how bulk
91   * operations will affect the map.<p>
92   *
93   * @param <K> the type of the keys in this map
94   * @param <V> the type of the values in this map
95   * @since 3.0 (previously in main package v2.1)
96   */
97  public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> {
98  
99      /** The default number of buckets to use */
100     private static final int DEFAULT_BUCKETS = 255;
101     /** The array of buckets, where the actual data is held */
102     private final Node<K, V>[] buckets;
103     /** The matching array of locks */
104     private final Lock[] locks;
105 
106     /**
107      * Initializes the map with the default number of buckets (255).
108      */
109     public StaticBucketMap() {
110         this(DEFAULT_BUCKETS);
111     }
112 
113     /**
114      * Initializes the map with a specified number of buckets.  The number
115      * of buckets is never below 17, and is always an odd number (StaticBucketMap
116      * ensures this). The number of buckets is inversely proportional to the
117      * chances for thread contention.  The fewer buckets, the more chances for
118      * thread contention.  The more buckets the fewer chances for thread
119      * contention.
120      *
121      * @param numBuckets  the number of buckets for this map
122      */
123     @SuppressWarnings("unchecked")
124     public StaticBucketMap(final int numBuckets) {
125         int size = Math.max(17, numBuckets);
126 
127         // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
128         if (size % 2 == 0) {
129             size--;
130         }
131 
132         buckets = new Node[size];
133         locks = new Lock[size];
134 
135         for (int i = 0; i < size; i++) {
136             locks[i] = new Lock();
137         }
138     }
139 
140     //-----------------------------------------------------------------------
141     /**
142      * Determine the exact hash entry for the key.  The hash algorithm
143      * is rather simplistic, but it does the job:
144      *
145      * <pre>
146      *   He = |Hk mod n|
147      * </pre>
148      *
149      * <p>
150      *   He is the entry's hashCode, Hk is the key's hashCode, and n is
151      *   the number of buckets.
152      * </p>
153      */
154     private int getHash(final Object key) {
155         if (key == null) {
156             return 0;
157         }
158         int hash = key.hashCode();
159         hash += ~(hash << 15);
160         hash ^= (hash >>> 10);
161         hash += (hash << 3);
162         hash ^= (hash >>> 6);
163         hash += ~(hash << 11);
164         hash ^= (hash >>> 16);
165         hash %= buckets.length;
166         return (hash < 0) ? hash * -1 : hash;
167     }
168 
169     /**
170      * Gets the current size of the map.
171      * The value is computed fresh each time the method is called.
172      *
173      * @return the current size
174      */
175     @Override
176     public int size() {
177         int cnt = 0;
178 
179         for (int i = 0; i < buckets.length; i++) {
180             synchronized(locks[i]) {
181                 cnt += locks[i].size;
182             }
183         }
184         return cnt;
185     }
186 
187     /**
188      * Checks if the size is currently zero.
189      *
190      * @return true if empty
191      */
192     @Override
193     public boolean isEmpty() {
194         return (size() == 0);
195     }
196 
197     /**
198      * Gets the value associated with the key.
199      *
200      * @param key  the key to retrieve
201      * @return the associated value
202      */
203     @Override
204     public V get(final Object key) {
205         final int hash = getHash(key);
206 
207         synchronized (locks[hash]) {
208             Node<K, V> n = buckets[hash];
209 
210             while (n != null) {
211                 if (n.key == key || (n.key != null && n.key.equals(key))) {
212                     return n.value;
213                 }
214 
215                 n = n.next;
216             }
217         }
218         return null;
219     }
220 
221     /**
222      * Checks if the map contains the specified key.
223      *
224      * @param key  the key to check
225      * @return true if found
226      */
227     @Override
228     public boolean containsKey(final Object key) {
229         final int hash = getHash(key);
230 
231         synchronized (locks[hash]) {
232             Node<K, V> n = buckets[hash];
233 
234             while (n != null) {
235                 if (n.key == key || (n.key != null && n.key.equals(key))) {
236                     return true;
237                 }
238 
239                 n = n.next;
240             }
241         }
242         return false;
243     }
244 
245     /**
246      * Checks if the map contains the specified value.
247      *
248      * @param value  the value to check
249      * @return true if found
250      */
251     @Override
252     public boolean containsValue(final Object value) {
253         for (int i = 0; i < buckets.length; i++) {
254             synchronized (locks[i]) {
255                 Node<K, V> n = buckets[i];
256 
257                 while (n != null) {
258                     if (n.value == value || (n.value != null && n.value.equals(value))) {
259                         return true;
260                     }
261 
262                     n = n.next;
263                 }
264             }
265         }
266         return false;
267     }
268 
269     //-----------------------------------------------------------------------
270     /**
271      * Puts a new key value mapping into the map.
272      *
273      * @param key  the key to use
274      * @param value  the value to use
275      * @return the previous mapping for the key
276      */
277     @Override
278     public V put(final K key, final V value) {
279         final int hash = getHash(key);
280 
281         synchronized (locks[hash]) {
282             Node<K, V> n = buckets[hash];
283 
284             if (n == null) {
285                 n = new Node<>();
286                 n.key = key;
287                 n.value = value;
288                 buckets[hash] = n;
289                 locks[hash].size++;
290                 return null;
291             }
292 
293             // Set n to the last node in the linked list.  Check each key along the way
294             //  If the key is found, then change the value of that node and return
295             //  the old value.
296             for (Node<K, V> next = n; next != null; next = next.next) {
297                 n = next;
298 
299                 if (n.key == key || (n.key != null && n.key.equals(key))) {
300                     final V returnVal = n.value;
301                     n.value = value;
302                     return returnVal;
303                 }
304             }
305 
306             // The key was not found in the current list of nodes, add it to the end
307             //  in a new node.
308             final Node<K, V> newNode = new Node<>();
309             newNode.key = key;
310             newNode.value = value;
311             n.next = newNode;
312             locks[hash].size++;
313         }
314         return null;
315     }
316 
317     /**
318      * Removes the specified key from the map.
319      *
320      * @param key  the key to remove
321      * @return the previous value at this key
322      */
323     @Override
324     public V remove(final Object key) {
325         final int hash = getHash(key);
326 
327         synchronized (locks[hash]) {
328             Node<K, V> n = buckets[hash];
329             Node<K, V> prev = null;
330 
331             while (n != null) {
332                 if (n.key == key || (n.key != null && n.key.equals(key))) {
333                     // Remove this node from the linked list of nodes.
334                     if (null == prev) {
335                         // This node was the head, set the next node to be the new head.
336                         buckets[hash] = n.next;
337                     } else {
338                         // Set the next node of the previous node to be the node after this one.
339                         prev.next = n.next;
340                     }
341                     locks[hash].size--;
342                     return n.value;
343                 }
344 
345                 prev = n;
346                 n = n.next;
347             }
348         }
349         return null;
350     }
351 
352     //-----------------------------------------------------------------------
353     /**
354      * Gets the key set.
355      *
356      * @return the key set
357      */
358     @Override
359     public Set<K> keySet() {
360         return new KeySet();
361     }
362 
363     /**
364      * Gets the values.
365      *
366      * @return the values
367      */
368     @Override
369     public Collection<V> values() {
370         return new Values();
371     }
372 
373     /**
374      * Gets the entry set.
375      *
376      * @return the entry set
377      */
378     @Override
379     public Set<Map.Entry<K, V>> entrySet() {
380         return new EntrySet();
381     }
382 
383     //-----------------------------------------------------------------------
384     /**
385      * Puts all the entries from the specified map into this map.
386      * This operation is <b>not atomic</b> and may have undesired effects.
387      *
388      * @param map  the map of entries to add
389      */
390     @Override
391     public void putAll(final Map<? extends K, ? extends V> map) {
392         for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
393             put(entry.getKey(), entry.getValue());
394         }
395     }
396 
397     /**
398      * Clears the map of all entries.
399      */
400     @Override
401     public void clear() {
402         for (int i = 0; i < buckets.length; i++) {
403             final Lock lock = locks[i];
404             synchronized (lock) {
405                 buckets[i] = null;
406                 lock.size = 0;
407             }
408         }
409     }
410 
411     /**
412      * Compares this map to another, as per the Map specification.
413      *
414      * @param obj  the object to compare to
415      * @return true if equal
416      */
417     @Override
418     public boolean equals(final Object obj) {
419         if (obj == this) {
420             return true;
421         }
422         if (obj instanceof Map<?, ?> == false) {
423             return false;
424         }
425         final Map<?, ?> other = (Map<?, ?>) obj;
426         return entrySet().equals(other.entrySet());
427     }
428 
429     /**
430      * Gets the hash code, as per the Map specification.
431      *
432      * @return the hash code
433      */
434     @Override
435     public int hashCode() {
436         int hashCode = 0;
437 
438         for (int i = 0; i < buckets.length; i++) {
439             synchronized (locks[i]) {
440                 Node<K, V> n = buckets[i];
441 
442                 while (n != null) {
443                     hashCode += n.hashCode();
444                     n = n.next;
445                 }
446             }
447         }
448         return hashCode;
449     }
450 
451     //-----------------------------------------------------------------------
452     /**
453      * The Map.Entry for the StaticBucketMap.
454      */
455     private static final class Node<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
456         protected K key;
457         protected V value;
458         protected Node<K, V> next;
459 
460         @Override
461         public K getKey() {
462             return key;
463         }
464 
465         @Override
466         public V getValue() {
467             return value;
468         }
469 
470         @Override
471         public int hashCode() {
472             return ((key == null ? 0 : key.hashCode()) ^
473                     (value == null ? 0 : value.hashCode()));
474         }
475 
476         @Override
477         public boolean equals(final Object obj) {
478             if (obj == this) {
479                 return true;
480             }
481             if (obj instanceof Map.Entry<?, ?> == false) {
482                 return false;
483             }
484 
485             final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj;
486             return (
487                 (key == null ? e2.getKey() == null : key.equals(e2.getKey())) &&
488                 (value == null ? e2.getValue() == null : value.equals(e2.getValue())));
489         }
490 
491         @Override
492         public V setValue(final V obj) {
493             final V retVal = value;
494             value = obj;
495             return retVal;
496         }
497     }
498 
499     /**
500      * The lock object, which also includes a count of the nodes in this lock.
501      */
502     private final static class Lock {
503         public int size;
504     }
505 
506     //-----------------------------------------------------------------------
507     private class BaseIterator {
508         private final ArrayList<Map.Entry<K, V>> current = new ArrayList<>();
509         private int bucket;
510         private Map.Entry<K, V> last;
511 
512         public boolean hasNext() {
513             if (current.size() > 0) {
514                 return true;
515             }
516             while (bucket < buckets.length) {
517                 synchronized (locks[bucket]) {
518                     Node<K, V> n = buckets[bucket];
519                     while (n != null) {
520                         current.add(n);
521                         n = n.next;
522                     }
523                     bucket++;
524                     if (current.size() > 0) {
525                         return true;
526                     }
527                 }
528             }
529             return false;
530         }
531 
532         protected Map.Entry<K, V> nextEntry() {
533             if (!hasNext()) {
534                 throw new NoSuchElementException();
535             }
536             last = current.remove(current.size() - 1);
537             return last;
538         }
539 
540         public void remove() {
541             if (last == null) {
542                 throw new IllegalStateException();
543             }
544             StaticBucketMap.this.remove(last.getKey());
545             last = null;
546         }
547     }
548 
549     private class EntryIterator extends BaseIterator implements Iterator<Map.Entry<K, V>> {
550 
551         @Override
552         public Map.Entry<K, V> next() {
553             return nextEntry();
554         }
555 
556     }
557 
558     private class ValueIterator extends BaseIterator implements Iterator<V> {
559 
560         @Override
561         public V next() {
562             return nextEntry().getValue();
563         }
564 
565     }
566 
567     private class KeyIterator extends BaseIterator implements Iterator<K> {
568 
569         @Override
570         public K next() {
571             return nextEntry().getKey();
572         }
573 
574     }
575 
576     private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
577 
578         @Override
579         public int size() {
580             return StaticBucketMap.this.size();
581         }
582 
583         @Override
584         public void clear() {
585             StaticBucketMap.this.clear();
586         }
587 
588         @Override
589         public Iterator<Map.Entry<K, V>> iterator() {
590             return new EntryIterator();
591         }
592 
593         @Override
594         public boolean contains(final Object obj) {
595             final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
596             final int hash = getHash(entry.getKey());
597             synchronized (locks[hash]) {
598                 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
599                     if (n.equals(entry)) {
600                         return true;
601                     }
602                 }
603             }
604             return false;
605         }
606 
607         @Override
608         public boolean remove(final Object obj) {
609             if (obj instanceof Map.Entry<?, ?> == false) {
610                 return false;
611             }
612             final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
613             final int hash = getHash(entry.getKey());
614             synchronized (locks[hash]) {
615                 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
616                     if (n.equals(entry)) {
617                         StaticBucketMap.this.remove(n.getKey());
618                         return true;
619                     }
620                 }
621             }
622             return false;
623         }
624 
625     }
626 
627     private class KeySet extends AbstractSet<K> {
628 
629         @Override
630         public int size() {
631             return StaticBucketMap.this.size();
632         }
633 
634         @Override
635         public void clear() {
636             StaticBucketMap.this.clear();
637         }
638 
639         @Override
640         public Iterator<K> iterator() {
641             return new KeyIterator();
642         }
643 
644         @Override
645         public boolean contains(final Object obj) {
646             return StaticBucketMap.this.containsKey(obj);
647         }
648 
649         @Override
650         public boolean remove(final Object obj) {
651             final int hash = getHash(obj);
652             synchronized (locks[hash]) {
653                 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
654                     final Object k = n.getKey();
655                     if ((k == obj) || ((k != null) && k.equals(obj))) {
656                         StaticBucketMap.this.remove(k);
657                         return true;
658                     }
659                 }
660             }
661             return false;
662         }
663 
664     }
665 
666 
667     private class Values extends AbstractCollection<V> {
668 
669         @Override
670         public int size() {
671             return StaticBucketMap.this.size();
672         }
673 
674         @Override
675         public void clear() {
676             StaticBucketMap.this.clear();
677         }
678 
679         @Override
680         public Iterator<V> iterator() {
681             return new ValueIterator();
682         }
683 
684     }
685 
686     /**
687      *  Prevents any operations from occurring on this map while the
688      *  given {@link Runnable} executes.  This method can be used, for
689      *  instance, to execute a bulk operation atomically:
690      *
691      *  <pre>
692      *    staticBucketMapInstance.atomic(new Runnable() {
693      *        public void run() {
694      *            staticBucketMapInstance.putAll(map);
695      *        }
696      *    });
697      *  </pre>
698      *
699      *  It can also be used if you need a reliable iterator:
700      *
701      *  <pre>
702      *    staticBucketMapInstance.atomic(new Runnable() {
703      *        public void run() {
704      *            Iterator iterator = staticBucketMapInstance.iterator();
705      *            while (iterator.hasNext()) {
706      *                foo(iterator.next();
707      *            }
708      *        }
709      *    });
710      *  </pre>
711      *
712      *  <b>Implementation note:</b> This method requires a lot of time
713      *  and a ton of stack space.  Essentially a recursive algorithm is used
714      *  to enter each bucket's monitor.  If you have twenty thousand buckets
715      *  in your map, then the recursive method will be invoked twenty thousand
716      *  times.  You have been warned.
717      *
718      *  @param r  the code to execute atomically
719      */
720     public void atomic(final Runnable r) {
721         if (r == null) {
722             throw new NullPointerException();
723         }
724         atomic(r, 0);
725     }
726 
727     private void atomic(final Runnable r, final int bucket) {
728         if (bucket >= buckets.length) {
729             r.run();
730             return;
731         }
732         synchronized (locks[bucket]) {
733             atomic(r, bucket + 1);
734         }
735     }
736 
737 }