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.27 by dl, Sun Oct 2 22:01:06 2011 UTC vs.
Revision 1.37 by dl, Sun Mar 4 20:34:27 2012 UTC

# Line 20 | Line 20 | import java.util.Enumeration;
20   import java.util.ConcurrentModificationException;
21   import java.util.NoSuchElementException;
22   import java.util.concurrent.ConcurrentMap;
23 + import java.util.concurrent.ThreadLocalRandom;
24   import java.util.concurrent.locks.LockSupport;
25   import java.io.Serializable;
26  
# Line 71 | Line 72 | import java.io.Serializable;
72   * versions of this class, constructors may optionally specify an
73   * expected {@code concurrencyLevel} as an additional hint for
74   * internal sizing.  Note that using many keys with exactly the same
75 < * {@code hashCode{}} is a sure way to slow down performance of any
75 > * {@code hashCode()} is a sure way to slow down performance of any
76   * hash table.
77   *
78   * <p>This class and its views and iterators implement all of the
# Line 351 | Line 352 | public class ConcurrentHashMapV8<K, V>
352       * Encodings for special uses of Node hash fields. See above for
353       * explanation.
354       */
355 <    static final int MOVED     = 0x80000000; // hash field for fowarding nodes
355 >    static final int MOVED     = 0x80000000; // hash field for forwarding nodes
356      static final int LOCKED    = 0x40000000; // set/tested only as a bit
357      static final int WAITING   = 0xc0000000; // both bits set/tested together
358      static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
# Line 391 | Line 392 | public class ConcurrentHashMapV8<K, V>
392      /**
393       * Key-value entry. Note that this is never exported out as a
394       * user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry
395 <     * below). Nodes with a negative hash field are special, and do
395 >     * below). Nodes with a hash field of MOVED are special, and do
396       * not contain user keys or values.  Otherwise, keys are never
397       * null, and null val fields indicate that a node is in the
398       * process of being deleted or created. For purposes of read-only
# Line 435 | Line 436 | public class ConcurrentHashMapV8<K, V>
436           */
437          final void tryAwaitLock(Node[] tab, int i) {
438              if (tab != null && i >= 0 && i < tab.length) { // bounds check
439 +                int r = ThreadLocalRandom.current().nextInt(); // randomize spins
440                  int spins = MAX_SPINS, h;
441                  while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
442                      if (spins >= 0) {
443 <                        if (--spins == MAX_SPINS >>> 1)
444 <                            Thread.yield();  // heuristically yield mid-way
443 >                        r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
444 >                        if (r >= 0 && --spins == 0)
445 >                            Thread.yield();  // yield before block
446                      }
447                      else if (casHash(h, h | WAITING)) {
448                          synchronized (this) {
# Line 595 | Line 598 | public class ConcurrentHashMapV8<K, V>
598                  } finally {
599                      if (!f.casHash(fh | LOCKED, fh)) {
600                          f.hash = fh;
601 <                        synchronized(f) { f.notifyAll(); };
601 >                        synchronized (f) { f.notifyAll(); };
602                      }
603                  }
604                  if (validated) {
# Line 752 | Line 755 | public class ConcurrentHashMapV8<K, V>
755                      } finally {
756                          if (!f.casHash(fh | LOCKED, fh)) {
757                              f.hash = fh;
758 <                            synchronized(f) { f.notifyAll(); };
758 >                            synchronized (f) { f.notifyAll(); };
759                          }
760                      }
761                      if (validated) {
# Line 789 | Line 792 | public class ConcurrentHashMapV8<K, V>
792                              setTabAt(tab, i, null);
793                          if (!node.casHash(fh, h)) {
794                              node.hash = h;
795 <                            synchronized(node) { node.notifyAll(); };
795 >                            synchronized (node) { node.notifyAll(); };
796                          }
797                      }
798                  }
# Line 843 | Line 846 | public class ConcurrentHashMapV8<K, V>
846                      } finally {
847                          if (!f.casHash(fh | LOCKED, fh)) {
848                              f.hash = fh;
849 <                            synchronized(f) { f.notifyAll(); };
849 >                            synchronized (f) { f.notifyAll(); };
850                          }
851                      }
852                      if (validated)
# Line 934 | Line 937 | public class ConcurrentHashMapV8<K, V>
937                      break;
938              }
939          }
940 +        if (val == null)
941 +            throw new NullPointerException();
942          if (added) {
943              counter.add(1L);
944              if (checkSize)
945                  checkForResize();
946          }
942 –        else if (val == null)
943 –            throw new NullPointerException();
947          return val;
948      }
949  
# Line 1002 | Line 1005 | public class ConcurrentHashMapV8<K, V>
1005                          } finally {
1006                              if (!f.casHash(fh | LOCKED, fh)) {
1007                                  f.hash = fh;
1008 <                                synchronized(f) { f.notifyAll(); };
1008 >                                synchronized (f) { f.notifyAll(); };
1009                              }
1010                          }
1011                          if (validated) {
# Line 1099 | Line 1102 | public class ConcurrentHashMapV8<K, V>
1102          while ((sc = sizeCtl) >= 0) {
1103              Node[] tab = table; int n;
1104              if (tab == null || (n = tab.length) == 0) {
1105 <                n = (sc > c)? sc : c;
1105 >                n = (sc > c) ? sc : c;
1106                  if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1107                      try {
1108                          if (table == tab) {
# Line 1150 | Line 1153 | public class ConcurrentHashMapV8<K, V>
1153                          continue;
1154                  }
1155                  else {             // transiently use a locked forwarding node
1156 <                    Node g =  new Node(MOVED|LOCKED, nextTab, null, null);
1156 >                    Node g = new Node(MOVED|LOCKED, nextTab, null, null);
1157                      if (!casTabAt(tab, i, f, g))
1158                          continue;
1159                      setTabAt(nextTab, i, null);
# Line 1271 | Line 1274 | public class ConcurrentHashMapV8<K, V>
1274                  } finally {
1275                      if (!f.casHash(fh | LOCKED, fh)) {
1276                          f.hash = fh;
1277 <                        synchronized(f) { f.notifyAll(); };
1277 >                        synchronized (f) { f.notifyAll(); };
1278                      }
1279                  }
1280                  if (validated)
# Line 1291 | Line 1294 | public class ConcurrentHashMapV8<K, V>
1294       *
1295       * At each step, the iterator snapshots the key ("nextKey") and
1296       * value ("nextVal") of a valid node (i.e., one that, at point of
1297 <     * snapshot, has a nonnull user value). Because val fields can
1297 >     * snapshot, has a non-null user value). Because val fields can
1298       * change (including to null, indicating deletion), field nextVal
1299       * might not be accurate at point of use, but still maintains the
1300       * weak consistency property of holding a value that was once
# Line 1460 | Line 1463 | public class ConcurrentHashMapV8<K, V>
1463          if (initialCapacity < concurrencyLevel)   // Use at least as many bins
1464              initialCapacity = concurrencyLevel;   // as estimated threads
1465          long size = (long)(1.0 + (long)initialCapacity / loadFactor);
1466 <        int cap =  ((size >= (long)MAXIMUM_CAPACITY) ?
1467 <                    MAXIMUM_CAPACITY: tableSizeFor((int)size));
1466 >        int cap = ((size >= (long)MAXIMUM_CAPACITY) ?
1467 >                   MAXIMUM_CAPACITY: tableSizeFor((int)size));
1468          this.counter = new LongAdder();
1469          this.sizeCtl = cap;
1470      }
# Line 1678 | Line 1681 | public class ConcurrentHashMapV8<K, V>
1681       * final String msg = ...;
1682       * map.compute(key, new RemappingFunction<Key, String>() {
1683       *   public String remap(Key k, String v) {
1684 <     *    return (v == null) ? msg : v + msg;});}</pre>
1684 >     *    return (v == null) ? msg : v + msg;});}}</pre>
1685       *
1686       * @param key key with which the specified value is to be associated
1687       * @param remappingFunction the function to compute a value
# Line 1689 | Line 1692 | public class ConcurrentHashMapV8<K, V>
1692       * @throws IllegalStateException if the computation detectably
1693       *         attempts a recursive update to this map that would
1694       *         otherwise never complete
1695 <     * @throws RuntimeException or Error if the mappingFunction does so,
1695 >     * @throws RuntimeException or Error if the remappingFunction does so,
1696       *         in which case the mapping is unchanged
1697       */
1698      @SuppressWarnings("unchecked")
# Line 2187 | Line 2190 | public class ConcurrentHashMapV8<K, V>
2190              return true;
2191          }
2192  
2193 <        public final boolean removeAll(Collection c) {
2193 >        public final boolean removeAll(Collection<?> c) {
2194              boolean modified = false;
2195              for (Iterator<?> it = iter(); it.hasNext();) {
2196                  if (c.contains(it.next())) {
# Line 2237 | Line 2240 | public class ConcurrentHashMapV8<K, V>
2240      }
2241  
2242      static final class Values<K,V> extends MapView<K,V>
2243 <        implements Collection<V>  {
2243 >        implements Collection<V> {
2244          Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
2245          public final boolean contains(Object o) { return map.containsValue(o); }
2246  
# Line 2267 | Line 2270 | public class ConcurrentHashMapV8<K, V>
2270          }
2271      }
2272  
2273 <    static final class EntrySet<K,V>  extends MapView<K,V>
2273 >    static final class EntrySet<K,V> extends MapView<K,V>
2274          implements Set<Map.Entry<K,V>> {
2275          EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
2276  
# Line 2401 | Line 2404 | public class ConcurrentHashMapV8<K, V>
2404                          }
2405                          table = tab;
2406                          counter.add(size);
2407 <                        sc = n - (n >>> 2) - 1;
2407 >                        sc = n - (n >>> 2);
2408                      }
2409                  } finally {
2410                      sizeCtl = sc;

Diff Legend

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