ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java
(Generate patch)

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.4 by jsr166, Tue Aug 30 07:23:35 2011 UTC vs.
Revision 1.11 by jsr166, Tue Aug 30 18:31:25 2011 UTC

# Line 54 | Line 54 | import java.io.Serializable;
54   * <p> Resizing this or any other kind of hash table is a relatively
55   * slow operation, so, when possible, it is a good idea to provide
56   * estimates of expected table sizes in constructors. Also, for
57 < * compatability with previous versions of this class, constructors
57 > * compatibility with previous versions of this class, constructors
58   * may optionally specify an expected {@code concurrencyLevel} as an
59   * additional hint for internal sizing.
60   *
# Line 83 | Line 83 | public class ConcurrentHashMapV8<K, V>
83  
84      /**
85       * A function computing a mapping from the given key to a value,
86 <     *  or <code>null</code> if there is no mapping. This is a
87 <     * place-holder for an upcoming JDK8 interface.
86 >     * or {@code null} if there is no mapping. This is a place-holder
87 >     * for an upcoming JDK8 interface.
88       */
89      public static interface MappingFunction<K, V> {
90          /**
# Line 139 | Line 139 | public class ConcurrentHashMapV8<K, V>
139       * that it is still the first node, and retry if not. (Because new
140       * nodes are always appended to lists, once a node is first in a
141       * bin, it remains first until deleted or the bin becomes
142 <     * invalidated.)  However, update operations can and usually do
142 >     * invalidated.)  However, update operations can and sometimes do
143       * still traverse the bin until the point of update, which helps
144       * reduce cache misses on retries.  This is a converse of sorts to
145       * the lazy locking technique described by Herlihy & Shavit. If
146       * there is no existing node during a put operation, then one can
147       * be CAS'ed in (without need for lock except in computeIfAbsent);
148       * the CAS serves as validation. This is on average the most
149 <     * common case for put operations. The expected number of locks
150 <     * covering different elements (i.e., bins with 2 or more nodes)
151 <     * is approximately 10% at steady state under default settings.
152 <     * Lock contention probability for two threads accessing arbitrary
153 <     * distinct elements is thus less than 1% even for small tables.
149 >     * common case for put operations -- under random hash codes, the
150 >     * distribution of nodes in bins follows a Poisson distribution
151 >     * (see http://en.wikipedia.org/wiki/Poisson_distribution) with a
152 >     * parameter of 0.5 on average under the default loadFactor of
153 >     * 0.75.  The expected number of locks covering different elements
154 >     * (i.e., bins with 2 or more nodes) is approximately 10% at
155 >     * steady state under default settings.  Lock contention
156 >     * probability for two threads accessing arbitrary distinct
157 >     * elements is, roughly, 1 / (8 * #elements).
158       *
159       * The table is resized when occupancy exceeds a threshold.  Only
160       * a single thread performs the resize (using field "resizing", to
# Line 188 | Line 192 | public class ConcurrentHashMapV8<K, V>
192       * in 8 puts check threshold (and after resizing, many fewer do
193       * so). But this approximation has high variance for small table
194       * sizes, so we check on any collision for sizes <= 64.  Further,
195 <     * to increase the probablity that a resize occurs soon enough, we
195 >     * to increase the probability that a resize occurs soon enough, we
196       * offset the threshold (see THRESHOLD_OFFSET) by the expected
197       * number of puts between checks. This is currently set to 8, in
198       * accord with the default load factor. In practice, this is
199       * rarely overridden, and in any case is close enough to other
200 <     * plausible values not to waste dynamic probablity computation
200 >     * plausible values not to waste dynamic probability computation
201       * for more precision.
202       */
203  
# Line 213 | Line 217 | public class ConcurrentHashMapV8<K, V>
217  
218      /**
219       * The default initial table capacity.  Must be a power of 2, at
220 <     * least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY
220 >     * least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY.
221       */
222      static final int DEFAULT_CAPACITY = 16;
223  
# Line 230 | Line 234 | public class ConcurrentHashMapV8<K, V>
234      static final int DEFAULT_CONCURRENCY_LEVEL = 16;
235  
236      /**
237 <     * The count value to offset thesholds to compensate for checking
237 >     * The count value to offset thresholds to compensate for checking
238       * for resizing only when inserting into bins with two or more
239       * elements. See above for explanation.
240       */
# Line 267 | Line 271 | public class ConcurrentHashMapV8<K, V>
271      transient Set<Map.Entry<K,V>> entrySet;
272      transient Collection<V> values;
273  
274 <    /** For serialization compatability. Null unless serialized; see below */
274 >    /** For serialization compatibility. Null unless serialized; see below */
275      Segment<K,V>[] segments;
276  
277      /**
# Line 305 | Line 309 | public class ConcurrentHashMapV8<K, V>
309      }
310  
311      /*
312 <     * Volatile access nethods are used for table elements as well as
312 >     * Volatile access methods are used for table elements as well as
313       * elements of in-progress next table while resizing.  Uses in
314       * access and update methods are null checked by callers, and
315       * implicitly bounds-checked, relying on the invariants that tab
# Line 338 | Line 342 | public class ConcurrentHashMapV8<K, V>
342  
343      /* ---------------- Access and update operations -------------- */
344  
345 <    /** Implementation for get and containsKey **/
345 >   /** Implementation for get and containsKey */
346      private final Object internalGet(Object k) {
347          int h = spread(k.hashCode());
348          Node[] tab = table;
# Line 362 | Line 366 | public class ConcurrentHashMapV8<K, V>
366          return null;
367      }
368  
369 <    /** Implementation for put and putIfAbsent **/
369 >
370 >    /** Implementation for put and putIfAbsent */
371      private final Object internalPut(Object k, Object v, boolean replace) {
372          int h = spread(k.hashCode());
373          Object oldVal = null;  // the previous value or null if none
# Line 381 | Line 386 | public class ConcurrentHashMapV8<K, V>
386                  boolean validated = false;
387                  boolean checkSize = false;
388                  synchronized (e) {
389 <                    Node first = e;
390 <                    for (;;) {
391 <                        Object ek, ev;
392 <                        if ((ev = e.val) == null)
393 <                            break;
394 <                        if (e.hash == h && (ek = e.key) != null &&
395 <                            (k == ek || k.equals(ek))) {
396 <                            if (tabAt(tab, i) == first) {
392 <                                validated = true;
389 >                    if (tabAt(tab, i) == e) {
390 >                        validated = true;
391 >                        for (Node first = e;;) {
392 >                            Object ek, ev;
393 >                            if (e.hash == h &&
394 >                                (ek = e.key) != null &&
395 >                                (ev = e.val) != null &&
396 >                                (k == ek || k.equals(ek))) {
397                                  oldVal = ev;
398                                  if (replace)
399                                      e.val = v;
400 +                                break;
401                              }
402 <                            break;
403 <                        }
399 <                        Node last = e;
400 <                        if ((e = e.next) == null) {
401 <                            if (tabAt(tab, i) == first) {
402 <                                validated = true;
402 >                            Node last = e;
403 >                            if ((e = e.next) == null) {
404                                  last.next = new Node(h, k, v, null);
405                                  if (last != first || tab.length <= 64)
406                                      checkSize = true;
407 +                                break;
408                              }
407 –                            break;
409                          }
410                      }
411                  }
# Line 422 | Line 423 | public class ConcurrentHashMapV8<K, V>
423      }
424  
425      /**
426 <     * Covers the four public remove/replace methods: Replaces node
427 <     * value with v, conditional upon match of cv if non-null.  If
428 <     * resulting value is null, delete.
426 >     * Implementation for the four public remove/replace methods:
427 >     * Replaces node value with v, conditional upon match of cv if
428 >     * non-null.  If resulting value is null, delete.
429       */
430      private final Object internalReplace(Object k, Object v, Object cv) {
431          int h = spread(k.hashCode());
# Line 439 | Line 440 | public class ConcurrentHashMapV8<K, V>
440                  boolean validated = false;
441                  boolean deleted = false;
442                  synchronized (e) {
443 <                    Node pred = null;
444 <                    Node first = e;
445 <                    for (;;) {
446 <                        Object ek, ev;
447 <                        if ((ev = e.val) == null)
448 <                            break;
449 <                        if (e.hash == h && (ek = e.key) != null &&
450 <                            (k == ek || k.equals(ek))) {
451 <                            if (tabAt(tab, i) == first) {
451 <                                validated = true;
443 >                    if (tabAt(tab, i) == e) {
444 >                        validated = true;
445 >                        Node pred = null;
446 >                        do {
447 >                            Object ek, ev;
448 >                            if (e.hash == h &&
449 >                                (ek = e.key) != null &&
450 >                                (ev = e.val) != null &&
451 >                                (k == ek || k.equals(ek))) {
452                                  if (cv == null || cv == ev || cv.equals(ev)) {
453                                      oldVal = ev;
454                                      if ((e.val = v) == null) {
# Line 460 | Line 460 | public class ConcurrentHashMapV8<K, V>
460                                              setTabAt(tab, i, en);
461                                      }
462                                  }
463 +                                break;
464                              }
465 <                            break;
466 <                        }
466 <                        pred = e;
467 <                        if ((e = e.next) == null) {
468 <                            if (tabAt(tab, i) == first)
469 <                                validated = true;
470 <                            break;
471 <                        }
465 >                            pred = e;
466 >                        } while ((e = e.next) != null);
467                      }
468                  }
469                  if (validated) {
# Line 489 | Line 484 | public class ConcurrentHashMapV8<K, V>
484          int h = spread(k.hashCode());
485          V val = null;
486          boolean added = false;
492 –        boolean validated = false;
487          Node[] tab = table;
488 <        do {
488 >        for(;;) {
489              Node e; int i;
490              if (tab == null)
491                  tab = grow(0);
492              else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
493                  Node node = new Node(h, k, null, null);
494 +                boolean validated = false;
495                  synchronized (node) {
496                      if (casTabAt(tab, i, null, node)) {
497                          validated = true;
# Line 512 | Line 507 | public class ConcurrentHashMapV8<K, V>
507                          }
508                      }
509                  }
510 +                if (validated)
511 +                    break;
512              }
513              else if (e.hash < 0)
514                  tab = (Node[])e.key;
515 +            else if (Thread.holdsLock(e))
516 +                throw new IllegalStateException("Recursive map computation");
517              else {
518 +                boolean validated = false;
519                  boolean checkSize = false;
520                  synchronized (e) {
521 <                    Node first = e;
522 <                    for (;;) {
523 <                        Object ek, ev;
524 <                        if ((ev = e.val) == null)
525 <                            break;
526 <                        if (e.hash == h && (ek = e.key) != null &&
527 <                            (k == ek || k.equals(ek))) {
528 <                            if (tabAt(tab, i) == first) {
529 <                                validated = true;
530 <                                if (replace && (ev = f.map(k)) != null)
531 <                                    e.val = ev;
521 >                    if (tabAt(tab, i) == e) {
522 >                        validated = true;
523 >                        for (Node first = e;;) {
524 >                            Object ek, ev, fv;
525 >                            if (e.hash == h &&
526 >                                (ek = e.key) != null &&
527 >                                (ev = e.val) != null &&
528 >                                (k == ek || k.equals(ek))) {
529 >                                if (replace && (fv = f.map(k)) != null)
530 >                                    ev = e.val = fv;
531                                  val = (V)ev;
532 +                                break;
533                              }
534 <                            break;
535 <                        }
536 <                        Node last = e;
537 <                        if ((e = e.next) == null) {
538 <                            if (tabAt(tab, i) == first) {
539 <                                validated = true;
534 >                            Node last = e;
535 >                            if ((e = e.next) == null) {
536                                  if ((val = f.map(k)) != null) {
537                                      last.next = new Node(h, k, val, null);
538                                      added = true;
539                                      if (last != first || tab.length <= 64)
540                                          checkSize = true;
541                                  }
542 +                                break;
543                              }
547 –                            break;
544                          }
545                      }
546                  }
547 <                if (checkSize && tab.length < MAXIMUM_CAPACITY &&
548 <                    resizing == 0 && counter.sum() >= threshold)
549 <                    grow(0);
547 >                if (validated) {
548 >                    if (checkSize && tab.length < MAXIMUM_CAPACITY &&
549 >                        resizing == 0 && counter.sum() >= threshold)
550 >                        grow(0);
551 >                    break;
552 >                }
553              }
554 <        } while (!validated);
554 >        }
555          if (added)
556              counter.increment();
557          return val;
# Line 585 | Line 584 | public class ConcurrentHashMapV8<K, V>
584                          break;
585                  }
586                  else {
587 +                    int idx = e.hash & mask;
588                      boolean validated = false;
589                      synchronized (e) {
590 –                        int idx = e.hash & mask;
591 –                        Node lastRun = e;
592 –                        for (Node p = e.next; p != null; p = p.next) {
593 –                            int j = p.hash & mask;
594 –                            if (j != idx) {
595 –                                idx = j;
596 –                                lastRun = p;
597 –                            }
598 –                        }
590                          if (tabAt(tab, i) == e) {
591                              validated = true;
592 +                            Node lastRun = e;
593 +                            for (Node p = e.next; p != null; p = p.next) {
594 +                                int j = p.hash & mask;
595 +                                if (j != idx) {
596 +                                    idx = j;
597 +                                    lastRun = p;
598 +                                }
599 +                            }
600                              relaxedSetTabAt(nextTab, idx, lastRun);
601                              for (Node p = e; p != lastRun; p = p.next) {
602                                  int h = p.hash;
# Line 657 | Line 656 | public class ConcurrentHashMapV8<K, V>
656                          transfer(tab, nextTab);
657                      table = nextTab;
658                      if (tab == null || cap >= MAXIMUM_CAPACITY ||
659 <                        (sizeHint > 0 && cap >= sizeHint) ||
660 <                        counter.sum() < threshold)
659 >                        ((sizeHint > 0) ? cap >= sizeHint :
660 >                         counter.sum() < threshold))
661                          break;
662                  }
663              } finally {
# Line 903 | Line 902 | public class ConcurrentHashMapV8<K, V>
902       * nonpositive.
903       */
904      public ConcurrentHashMapV8(int initialCapacity,
905 <                             float loadFactor, int concurrencyLevel) {
905 >                               float loadFactor, int concurrencyLevel) {
906          if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
907              throw new IllegalArgumentException();
908          this.initCap = initialCapacity;
# Line 983 | Line 982 | public class ConcurrentHashMapV8<K, V>
982       */
983      public int size() {
984          long n = counter.sum();
985 <        return (n <= 0L) ? 0 :
987 <            (n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE :
988 <            (int)n;
985 >        return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE;
986      }
987  
988      /**
# Line 1119 | Line 1116 | public class ConcurrentHashMapV8<K, V>
1116       * </pre>
1117       *
1118       * except that the action is performed atomically.  Some attempted
1119 <     * operations on this map by other threads may be blocked while
1120 <     * computation is in progress, so the computation should be short
1121 <     * and simple, and must not attempt to update any other mappings
1122 <     * of this Map. The most common usage is to construct a new object
1123 <     * serving as an initial mapped value, or memoized result.
1119 >     * update operations on this map by other threads may be blocked
1120 >     * while computation is in progress, so the computation should be
1121 >     * short and simple, and must not attempt to update any other
1122 >     * mappings of this Map. The most appropriate usage is to
1123 >     * construct a new object serving as an initial mapped value, or
1124 >     * memoized result, as in:
1125 >     * <pre>{@code
1126 >     * map.computeIfAbsent(key, new MappingFunction<K, V>() {
1127 >     *   public V map(K k) { return new Value(f(k)); }};
1128 >     * }</pre>
1129       *
1130       * @param key key with which the specified value is to be associated
1131       * @param mappingFunction the function to compute a value
# Line 1132 | Line 1134 | public class ConcurrentHashMapV8<K, V>
1134       *         returned {@code null}.
1135       * @throws NullPointerException if the specified key or mappingFunction
1136       *         is null,
1137 +     * @throws IllegalStateException if the computation detectably
1138 +     *         attempts a recursive update to this map that would
1139 +     *         otherwise never complete.
1140       * @throws RuntimeException or Error if the mappingFunction does so,
1141       *         in which case the mapping is left unestablished.
1142       */
# Line 1142 | Line 1147 | public class ConcurrentHashMapV8<K, V>
1147      }
1148  
1149      /**
1150 <     * Computes the value associated with he given key using the given
1150 >     * Computes the value associated with the given key using the given
1151       * mappingFunction, and if non-null, enters it into the map.  This
1152       * is equivalent to
1153       *
# Line 1151 | Line 1156 | public class ConcurrentHashMapV8<K, V>
1156       *   if (value != null)
1157       *      map.put(key, value);
1158       *   else
1159 <     *      return map.get(key);
1159 >     *      value = map.get(key);
1160 >     *   return value;
1161       * </pre>
1162       *
1163       * except that the action is performed atomically.  Some attempted
1164 <     * operations on this map by other threads may be blocked while
1165 <     * computation is in progress, so the computation should be short
1166 <     * and simple, and must not attempt to update any other mappings
1167 <     * of this Map.
1164 >     * update operations on this map by other threads may be blocked
1165 >     * while computation is in progress, so the computation should be
1166 >     * short and simple, and must not attempt to update any other
1167 >     * mappings of this Map.
1168       *
1169       * @param key key with which the specified value is to be associated
1170       * @param mappingFunction the function to compute a value
# Line 1167 | Line 1173 | public class ConcurrentHashMapV8<K, V>
1173       *         returned {@code null} and the value was not otherwise present.
1174       * @throws NullPointerException if the specified key or mappingFunction
1175       *         is null,
1176 +     * @throws IllegalStateException if the computation detectably
1177 +     *         attempts a recursive update to this map that would
1178 +     *         otherwise never complete.
1179       * @throws RuntimeException or Error if the mappingFunction does so,
1180       *         in which case the mapping is unchanged.
1181       */
# Line 1534 | Line 1543 | public class ConcurrentHashMapV8<K, V>
1543      }
1544  
1545      /**
1546 <     * Reconstitutes the  instance from a
1538 <     * stream (i.e., deserializes it).
1546 >     * Reconstitutes the instance from a stream (that is, deserializes it).
1547       * @param s the stream
1548       */
1549      @SuppressWarnings("unchecked")

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines