File	Doc	Category	Size	Date	Package
ConcurrentSkipListMap.java	API Doc	Java SE 6 API	113780	Tue Jun 10 00:25:56 BST 2008	java.util.concurrent

ConcurrentSkipListMap

• java.lang.Object
  • java.util.AbstractMap

Fields Summary
private static final long	serialVersionUID
private static final Random	seedGenerator Generates the initial random seed for the cheaper per-instance random number generators used in randomLevel.
private static final Object	BASE_HEADER Special value used to identify base-level header
private volatile transient HeadIndex	head The topmost head index of the skiplist.
private final Comparator	comparator The comparator used to maintain order in this map, or null if using natural ordering.
private transient int	randomSeed Seed for simple random number generator. Not volatile since it doesn't matter too much if different threads don't see updates.
private transient KeySet	keySet Lazily initialized key set
private transient EntrySet	entrySet Lazily initialized entry set
private transient Values	values Lazily initialized values collection
private transient ConcurrentNavigableMap	descendingMap Lazily initialized descending key set
private static final AtomicReferenceFieldUpdater	headUpdater Updater for casHead
private static final int	EQ
private static final int	LT
private static final int	GT

Constructors Summary
public ConcurrentSkipListMap() Constructs a new, empty map, sorted according to the {@linkplain Comparable natural ordering} of the keys. this.comparator = null; initialize();
public ConcurrentSkipListMap(Comparator comparator) Constructs a new, empty map, sorted according to the specified comparator. param comparator the comparator that will be used to order this map. If null, the {@linkplain Comparable natural ordering} of the keys will be used. this.comparator = comparator; initialize();
public ConcurrentSkipListMap(Map m) Constructs a new map containing the same mappings as the given map, sorted according to the {@linkplain Comparable natural ordering} of the keys. param m the map whose mappings are to be placed in this map throws ClassCastException if the keys in m are not {@link Comparable}, or are not mutually comparable throws NullPointerException if the specified map or any of its keys or values are null this.comparator = null; initialize(); putAll(m);
public ConcurrentSkipListMap(SortedMap m) Constructs a new map containing the same mappings and using the same ordering as the specified sorted map. param m the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map throws NullPointerException if the specified sorted map or any of its keys or values are null this.comparator = m.comparator(); initialize(); buildFromSorted(m);

Methods Summary
private void	addIndex(java.util.concurrent.ConcurrentSkipListMap$Index idx, java.util.concurrent.ConcurrentSkipListMap$HeadIndex h, int indexLevel) Adds given index nodes from given level down to 1. param idx the topmost index node being inserted param h the value of head to use to insert. This must be snapshotted by callers to provide correct insertion level param indexLevel the level of the index // Track next level to insert in case of retries int insertionLevel = indexLevel; Comparable<? super K> key = comparable(idx.node.key); if (key == null) throw new NullPointerException(); // Similar to findPredecessor, but adding index nodes along // path to key. for (;;) { int j = h.level; Index<K,V> q = h; Index<K,V> r = q.right; Index<K,V> t = idx; for (;;) { if (r != null) { Node<K,V> n = r.node; // compare before deletion check avoids needing recheck int c = key.compareTo(n.key); if (n.value == null) { if (!q.unlink(r)) break; r = q.right; continue; } if (c > 0) { q = r; r = r.right; continue; } } if (j == insertionLevel) { // Don't insert index if node already deleted if (t.indexesDeletedNode()) { findNode(key); // cleans up return; } if (!q.link(r, t)) break; // restart if (--insertionLevel == 0) { // need final deletion check before return if (t.indexesDeletedNode()) findNode(key); return; } } if (--j >= insertionLevel && j < indexLevel) t = t.down; q = q.down; r = q.right; } }
private void	buildFromSorted(java.util.SortedMap map) Streamlined bulk insertion to initialize from elements of given sorted map. Call only from constructor or clone method. if (map == null) throw new NullPointerException(); HeadIndex<K,V> h = head; Node<K,V> basepred = h.node; // Track the current rightmost node at each level. Uses an // ArrayList to avoid committing to initial or maximum level. ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); // initialize for (int i = 0; i <= h.level; ++i) preds.add(null); Index<K,V> q = h; for (int i = h.level; i > 0; --i) { preds.set(i, q); q = q.down; } Iterator<? extends Map.Entry<? extends K, ? extends V>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<? extends K, ? extends V> e = it.next(); int j = randomLevel(); if (j > h.level) j = h.level + 1; K k = e.getKey(); V v = e.getValue(); if (k == null || v == null) throw new NullPointerException(); Node<K,V> z = new Node<K,V>(k, v, null); basepred.next = z; basepred = z; if (j > 0) { Index<K,V> idx = null; for (int i = 1; i <= j; ++i) { idx = new Index<K,V>(z, idx, null); if (i > h.level) h = new HeadIndex<K,V>(h.node, h, idx, i); if (i < preds.size()) { preds.get(i).right = idx; preds.set(i, idx); } else preds.add(idx); } } } head = h;
private boolean	casHead(java.util.concurrent.ConcurrentSkipListMap$HeadIndex cmp, java.util.concurrent.ConcurrentSkipListMap$HeadIndex val) compareAndSet head node return headUpdater.compareAndSet(this, cmp, val);
public java.util.Map$Entry	ceilingEntry(K key) Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method. throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null return getNear(key, GT|EQ);
public K	ceilingKey(K key) throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null Node<K,V> n = findNear(key, GT|EQ); return (n == null)? null : n.key;
public void	clear() Removes all of the mappings from this map. initialize();
private void	clearIndexToFirst() Clears out index nodes associated with deleted first entry. for (;;) { Index<K,V> q = head; for (;;) { Index<K,V> r = q.right; if (r != null && r.indexesDeletedNode() && !q.unlink(r)) break; if ((q = q.down) == null) { if (head.right == null) tryReduceLevel(); return; } } }
public java.util.concurrent.ConcurrentSkipListMap	clone() Returns a shallow copy of this ConcurrentSkipListMap instance. (The keys and values themselves are not cloned.) return a shallow copy of this map ConcurrentSkipListMap<K,V> clone = null; try { clone = (ConcurrentSkipListMap<K,V>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.initialize(); clone.buildFromSorted(this); return clone;
private java.lang.Comparable	comparable(java.lang.Object key) If using comparator, return a ComparableUsingComparator, else cast key as Comparable, which may cause ClassCastException, which is propagated back to caller. if (key == null) throw new NullPointerException(); if (comparator != null) return new ComparableUsingComparator<K>((K)key, comparator); else return (Comparable<? super K>)key;
public java.util.Comparator	comparator() return comparator;
int	compare(K k1, K k2) Compares using comparator or natural ordering. Used when the ComparableUsingComparator approach doesn't apply. Comparator<? super K> cmp = comparator; if (cmp != null) return cmp.compare(k1, k2); else return ((Comparable<? super K>)k1).compareTo(k2);
public boolean	containsKey(java.lang.Object key) Returns true if this map contains a mapping for the specified key. param key key whose presence in this map is to be tested return true if this map contains a mapping for the specified key throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key is null return doGet(key) != null;
public boolean	containsValue(java.lang.Object value) Returns true if this map maps one or more keys to the specified value. This operation requires time linear in the map size. param value value whose presence in this map is to be tested return true if a mapping to value exists; false otherwise throws NullPointerException if the specified value is null if (value == null) throw new NullPointerException(); for (Node<K,V> n = findFirst(); n != null; n = n.next) { V v = n.getValidValue(); if (v != null && value.equals(v)) return true; } return false;
public java.util.NavigableSet	descendingKeySet() return descendingMap().navigableKeySet();
public java.util.concurrent.ConcurrentNavigableMap	descendingMap() ConcurrentNavigableMap<K,V> dm = descendingMap; return (dm != null) ? dm : (descendingMap = new SubMap<K,V> (this, null, false, null, false, true));
private V	doGet(java.lang.Object okey) Specialized variant of findNode to perform Map.get. Does a weak traversal, not bothering to fix any deleted index nodes, returning early if it happens to see key in index, and passing over any deleted base nodes, falling back to getUsingFindNode only if it would otherwise return value from an ongoing deletion. Also uses "bound" to eliminate need for some comparisons (see Pugh Cookbook). Also folds uses of null checks and node-skipping because markers have null keys. param okey the key return the value, or null if absent Comparable<? super K> key = comparable(okey); Node<K,V> bound = null; Index<K,V> q = head; Index<K,V> r = q.right; Node<K,V> n; K k; int c; for (;;) { Index<K,V> d; // Traverse rights if (r != null && (n = r.node) != bound && (k = n.key) != null) { if ((c = key.compareTo(k)) > 0) { q = r; r = r.right; continue; } else if (c == 0) { Object v = n.value; return (v != null)? (V)v : getUsingFindNode(key); } else bound = n; } // Traverse down if ((d = q.down) != null) { q = d; r = d.right; } else break; } // Traverse nexts for (n = q.node.next; n != null; n = n.next) { if ((k = n.key) != null) { if ((c = key.compareTo(k)) == 0) { Object v = n.value; return (v != null)? (V)v : getUsingFindNode(key); } else if (c < 0) break; } } return null;
private V	doPut(K kkey, V value, boolean onlyIfAbsent) Main insertion method. Adds element if not present, or replaces value if present and onlyIfAbsent is false. param kkey the key param value the value that must be associated with key param onlyIfAbsent if should not insert if already present return the old value, or null if newly inserted Comparable<? super K> key = comparable(kkey); for (;;) { Node<K,V> b = findPredecessor(key); Node<K,V> n = b.next; for (;;) { if (n != null) { Node<K,V> f = n.next; if (n != b.next) // inconsistent read break;; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; int c = key.compareTo(n.key); if (c > 0) { b = n; n = f; continue; } if (c == 0) { if (onlyIfAbsent || n.casValue(v, value)) return (V)v; else break; // restart if lost race to replace value } // else c < 0; fall through } Node<K,V> z = new Node<K,V>(kkey, value, n); if (!b.casNext(n, z)) break; // restart if lost race to append to b int level = randomLevel(); if (level > 0) insertIndex(z, level); return null; } }
final V	doRemove(java.lang.Object okey, java.lang.Object value) Main deletion method. Locates node, nulls value, appends a deletion marker, unlinks predecessor, removes associated index nodes, and possibly reduces head index level. Index nodes are cleared out simply by calling findPredecessor. which unlinks indexes to deleted nodes found along path to key, which will include the indexes to this node. This is done unconditionally. We can't check beforehand whether there are index nodes because it might be the case that some or all indexes hadn't been inserted yet for this node during initial search for it, and we'd like to ensure lack of garbage retention, so must call to be sure. param okey the key param value if non-null, the value that must be associated with key return the node, or null if not found Comparable<? super K> key = comparable(okey); for (;;) { Node<K,V> b = findPredecessor(key); Node<K,V> n = b.next; for (;;) { if (n == null) return null; Node<K,V> f = n.next; if (n != b.next) // inconsistent read break; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; int c = key.compareTo(n.key); if (c < 0) return null; if (c > 0) { b = n; n = f; continue; } if (value != null && !value.equals(v)) return null; if (!n.casValue(v, null)) break; if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(key); // Retry via findNode else { findPredecessor(key); // Clean index if (head.right == null) tryReduceLevel(); } return (V)v; } }
java.util.Map$Entry	doRemoveFirstEntry() Removes first entry; returns its snapshot. return null if empty, else snapshot of first entry for (;;) { Node<K,V> b = head.node; Node<K,V> n = b.next; if (n == null) return null; Node<K,V> f = n.next; if (n != b.next) continue; Object v = n.value; if (v == null) { n.helpDelete(b, f); continue; } if (!n.casValue(v, null)) continue; if (!n.appendMarker(f) || !b.casNext(n, f)) findFirst(); // retry clearIndexToFirst(); return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v); }
java.util.Map$Entry	doRemoveLastEntry() Removes last entry; returns its snapshot. Specialized variant of doRemove. return null if empty, else snapshot of last entry for (;;) { Node<K,V> b = findPredecessorOfLast(); Node<K,V> n = b.next; if (n == null) { if (b.isBaseHeader()) // empty return null; else continue; // all b's successors are deleted; retry } for (;;) { Node<K,V> f = n.next; if (n != b.next) // inconsistent read break; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; if (f != null) { b = n; n = f; continue; } if (!n.casValue(v, null)) break; K key = n.key; Comparable<? super K> ck = comparable(key); if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(ck); // Retry via findNode else { findPredecessor(ck); // Clean index if (head.right == null) tryReduceLevel(); } return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v); } }
java.util.Iterator	entryIterator() return new EntryIterator();
public java.util.Set	entrySet() Returns a {@link Set} view of the mappings contained in this map. The set's iterator returns the entries in ascending key order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction. The Map.Entry elements returned by iterator.next() do not support the setValue operation. return a set view of the mappings contained in this map, sorted in ascending key order EntrySet es = entrySet; return (es != null) ? es : (entrySet = new EntrySet(this));
public boolean	equals(java.lang.Object o) Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This operation may return misleading results if either map is concurrently modified during execution of this method. param o object to be compared for equality with this map return true if the specified object is equal to this map if (o == this) return true; if (!(o instanceof Map)) return false; Map<?,?> m = (Map<?,?>) o; try { for (Map.Entry<K,V> e : this.entrySet()) if (! e.getValue().equals(m.get(e.getKey()))) return false; for (Map.Entry<?,?> e : m.entrySet()) { Object k = e.getKey(); Object v = e.getValue(); if (k == null || v == null || !v.equals(get(k))) return false; } return true; } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; }
java.util.concurrent.ConcurrentSkipListMap$Node	findFirst() Specialized variant of findNode to get first valid node. return first node or null if empty for (;;) { Node<K,V> b = head.node; Node<K,V> n = b.next; if (n == null) return null; if (n.value != null) return n; n.helpDelete(b, n.next); }
java.util.concurrent.ConcurrentSkipListMap$Node	findLast() Specialized version of find to get last valid node. return last node or null if empty /* * findPredecessor can't be used to traverse index level * because this doesn't use comparisons. So traversals of * both levels are folded together. */ Index<K,V> q = head; for (;;) { Index<K,V> d, r; if ((r = q.right) != null) { if (r.indexesDeletedNode()) { q.unlink(r); q = head; // restart } else q = r; } else if ((d = q.down) != null) { q = d; } else { Node<K,V> b = q.node; Node<K,V> n = b.next; for (;;) { if (n == null) return (b.isBaseHeader())? null : b; Node<K,V> f = n.next; // inconsistent read if (n != b.next) break; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; b = n; n = f; } q = head; // restart } }
java.util.concurrent.ConcurrentSkipListMap$Node	findNear(K kkey, int rel) Utility for ceiling, floor, lower, higher methods. param kkey the key param rel the relation -- OR'ed combination of EQ, LT, GT return nearest node fitting relation, or null if no such // Actually checked as !LT Comparable<? super K> key = comparable(kkey); for (;;) { Node<K,V> b = findPredecessor(key); Node<K,V> n = b.next; for (;;) { if (n == null) return ((rel & LT) == 0 || b.isBaseHeader())? null : b; Node<K,V> f = n.next; if (n != b.next) // inconsistent read break; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; int c = key.compareTo(n.key); if ((c == 0 && (rel & EQ) != 0) || (c < 0 && (rel & LT) == 0)) return n; if ( c <= 0 && (rel & LT) != 0) return (b.isBaseHeader())? null : b; b = n; n = f; } }
private java.util.concurrent.ConcurrentSkipListMap$Node	findNode(java.lang.Comparable key) Returns node holding key or null if no such, clearing out any deleted nodes seen along the way. Repeatedly traverses at base-level looking for key starting at predecessor returned from findPredecessor, processing base-level deletions as encountered. Some callers rely on this side-effect of clearing deleted nodes. Restarts occur, at traversal step centered on node n, if: (1) After reading n's next field, n is no longer assumed predecessor b's current successor, which means that we don't have a consistent 3-node snapshot and so cannot unlink any subsequent deleted nodes encountered. (2) n's value field is null, indicating n is deleted, in which case we help out an ongoing structural deletion before retrying. Even though there are cases where such unlinking doesn't require restart, they aren't sorted out here because doing so would not usually outweigh cost of restarting. (3) n is a marker or n's predecessor's value field is null, indicating (among other possibilities) that findPredecessor returned a deleted node. We can't unlink the node because we don't know its predecessor, so rely on another call to findPredecessor to notice and return some earlier predecessor, which it will do. This check is only strictly needed at beginning of loop, (and the b.value check isn't strictly needed at all) but is done each iteration to help avoid contention with other threads by callers that will fail to be able to change links, and so will retry anyway. The traversal loops in doPut, doRemove, and findNear all include the same three kinds of checks. And specialized versions appear in findFirst, and findLast and their variants. They can't easily share code because each uses the reads of fields held in locals occurring in the orders they were performed. param key the key return node holding key, or null if no such for (;;) { Node<K,V> b = findPredecessor(key); Node<K,V> n = b.next; for (;;) { if (n == null) return null; Node<K,V> f = n.next; if (n != b.next) // inconsistent read break; Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; int c = key.compareTo(n.key); if (c == 0) return n; if (c < 0) return null; b = n; n = f; } }
private java.util.concurrent.ConcurrentSkipListMap$Node	findPredecessor(java.lang.Comparable key) Returns a base-level node with key strictly less than given key, or the base-level header if there is no such node. Also unlinks indexes to deleted nodes found along the way. Callers rely on this side-effect of clearing indices to deleted nodes. param key the key return a predecessor of key if (key == null) throw new NullPointerException(); // don't postpone errors for (;;) { Index<K,V> q = head; Index<K,V> r = q.right; for (;;) { if (r != null) { Node<K,V> n = r.node; K k = n.key; if (n.value == null) { if (!q.unlink(r)) break; // restart r = q.right; // reread r continue; } if (key.compareTo(k) > 0) { q = r; r = r.right; continue; } } Index<K,V> d = q.down; if (d != null) { q = d; r = d.right; } else return q.node; } }
private java.util.concurrent.ConcurrentSkipListMap$Node	findPredecessorOfLast() Specialized variant of findPredecessor to get predecessor of last valid node. Needed when removing the last entry. It is possible that all successors of returned node will have been deleted upon return, in which case this method can be retried. return likely predecessor of last node for (;;) { Index<K,V> q = head; for (;;) { Index<K,V> d, r; if ((r = q.right) != null) { if (r.indexesDeletedNode()) { q.unlink(r); break; // must restart } // proceed as far across as possible without overshooting if (r.node.next != null) { q = r; continue; } } if ((d = q.down) != null) q = d; else return q.node; } }
public java.util.Map$Entry	firstEntry() Returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method. for (;;) { Node<K,V> n = findFirst(); if (n == null) return null; AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); if (e != null) return e; }
public K	firstKey() throws NoSuchElementException {@inheritDoc} Node<K,V> n = findFirst(); if (n == null) throw new NoSuchElementException(); return n.key;
public java.util.Map$Entry	floorEntry(K key) Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method. param key the key throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null return getNear(key, LT|EQ);
public K	floorKey(K key) param key the key throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null Node<K,V> n = findNear(key, LT|EQ); return (n == null)? null : n.key;
public V	get(java.lang.Object key) Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key. More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that {@code key} compares equal to {@code k} according to the map's ordering, then this method returns {@code v}; otherwise it returns {@code null}. (There can be at most one such mapping.) throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key is null return doGet(key);
java.util.AbstractMap$SimpleImmutableEntry	getNear(K key, int rel) Returns SimpleImmutableEntry for results of findNear. param key the key param rel the relation -- OR'ed combination of EQ, LT, GT return Entry fitting relation, or null if no such for (;;) { Node<K,V> n = findNear(key, rel); if (n == null) return null; AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); if (e != null) return e; }
private V	getUsingFindNode(java.lang.Comparable key) Performs map.get via findNode. Used as a backup if doGet encounters an in-progress deletion. param key the key return the value, or null if absent /* * Loop needed here and elsewhere in case value field goes * null just as it is about to be returned, in which case we * lost a race with a deletion, so must retry. */ for (;;) { Node<K,V> n = findNode(key); if (n == null) return null; Object v = n.value; if (v != null) return (V)v; }
public java.util.concurrent.ConcurrentNavigableMap	headMap(K toKey, boolean inclusive) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code toKey} is null throws IllegalArgumentException {@inheritDoc} if (toKey == null) throw new NullPointerException(); return new SubMap<K,V> (this, null, false, toKey, inclusive, false);
public java.util.concurrent.ConcurrentNavigableMap	headMap(K toKey) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code toKey} is null throws IllegalArgumentException {@inheritDoc} return headMap(toKey, false);
public java.util.Map$Entry	higherEntry(K key) Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method. param key the key throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null return getNear(key, GT);
public K	higherKey(K key) param key the key throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null Node<K,V> n = findNear(key, GT); return (n == null)? null : n.key;
boolean	inHalfOpenRange(K key, K least, K fence) Returns true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence are null. Needed mainly in submap operations. if (key == null) throw new NullPointerException(); return ((least == null || compare(key, least) >= 0) && (fence == null || compare(key, fence) < 0));
boolean	inOpenRange(K key, K least, K fence) Returns true if given key greater than or equal to least and less or equal to fence. Needed mainly in submap operations. if (key == null) throw new NullPointerException(); return ((least == null || compare(key, least) >= 0) && (fence == null || compare(key, fence) <= 0));
final void	initialize() Initializes or resets state. Needed by constructors, clone, clear, readObject. and ConcurrentSkipListSet.clone. (Note that comparator must be separately initialized.) keySet = null; entrySet = null; values = null; descendingMap = null; randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null), null, null, 1);
private void	insertIndex(java.util.concurrent.ConcurrentSkipListMap$Node z, int level) Creates and adds index nodes for the given node. param z the node param level the level of the index HeadIndex<K,V> h = head; int max = h.level; if (level <= max) { Index<K,V> idx = null; for (int i = 1; i <= level; ++i) idx = new Index<K,V>(z, idx, null); addIndex(idx, h, level); } else { // Add a new level /* * To reduce interference by other threads checking for * empty levels in tryReduceLevel, new levels are added * with initialized right pointers. Which in turn requires * keeping levels in an array to access them while * creating new head index nodes from the opposite * direction. */ level = max + 1; Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; Index<K,V> idx = null; for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index<K,V>(z, idx, null); HeadIndex<K,V> oldh; int k; for (;;) { oldh = head; int oldLevel = oldh.level; if (level <= oldLevel) { // lost race to add level k = level; break; } HeadIndex<K,V> newh = oldh; Node<K,V> oldbase = oldh.node; for (int j = oldLevel+1; j <= level; ++j) newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); if (casHead(oldh, newh)) { k = oldLevel; break; } } addIndex(idxs[k], oldh, k); }
public boolean	isEmpty() Returns true if this map contains no key-value mappings. return true if this map contains no key-value mappings return findFirst() == null;
java.util.Iterator	keyIterator() return new KeyIterator();
public java.util.NavigableSet	keySet() Returns a {@link NavigableSet} view of the keys contained in this map. The set's iterator returns the keys in ascending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations. The view's {@code iterator} is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction. This method is equivalent to method {@code navigableKeySet}. return a navigable set view of the keys in this map KeySet ks = keySet; return (ks != null) ? ks : (keySet = new KeySet(this));
public java.util.Map$Entry	lastEntry() Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method. for (;;) { Node<K,V> n = findLast(); if (n == null) return null; AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot(); if (e != null) return e; }
public K	lastKey() throws NoSuchElementException {@inheritDoc} Node<K,V> n = findLast(); if (n == null) throw new NoSuchElementException(); return n.key;
public java.util.Map$Entry	lowerEntry(K key) Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method. throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null return getNear(key, LT);
public K	lowerKey(K key) throws ClassCastException {@inheritDoc} throws NullPointerException if the specified key is null Node<K,V> n = findNear(key, LT); return (n == null)? null : n.key;
public java.util.NavigableSet	navigableKeySet() KeySet ks = keySet; return (ks != null) ? ks : (keySet = new KeySet(this));
public java.util.Map$Entry	pollFirstEntry() Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method. return doRemoveFirstEntry();
public java.util.Map$Entry	pollLastEntry() Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method. return doRemoveLastEntry();
public V	put(K key, V value) Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. param key key with which the specified value is to be associated param value value to be associated with the specified key return the previous value associated with the specified key, or null if there was no mapping for the key throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key or value is null if (value == null) throw new NullPointerException(); return doPut(key, value, false);
public V	putIfAbsent(K key, V value) {@inheritDoc} return the previous value associated with the specified key, or null if there was no mapping for the key throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key or value is null if (value == null) throw new NullPointerException(); return doPut(key, value, true);
private int	randomLevel() Returns a random level for inserting a new node. Hardwired to k=1, p=0.5, max 31 (see above and Pugh's "Skip List Cookbook", sec 3.4). This uses the simplest of the generators described in George Marsaglia's "Xorshift RNGs" paper. This is not a high-quality generator but is acceptable here. int x = randomSeed; x ^= x << 13; x ^= x >>> 17; randomSeed = x ^= x << 5; if ((x & 0x8001) != 0) // test highest and lowest bits return 0; int level = 1; while (((x >>>= 1) & 1) != 0) ++level; return level;
private void	readObject(java.io.ObjectInputStream s) Reconstitute the map from a stream. // Read in the Comparator and any hidden stuff s.defaultReadObject(); // Reset transients initialize(); /* * This is nearly identical to buildFromSorted, but is * distinct because readObject calls can't be nicely adapted * as the kind of iterator needed by buildFromSorted. (They * can be, but doing so requires type cheats and/or creation * of adaptor classes.) It is simpler to just adapt the code. */ HeadIndex<K,V> h = head; Node<K,V> basepred = h.node; ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>(); for (int i = 0; i <= h.level; ++i) preds.add(null); Index<K,V> q = h; for (int i = h.level; i > 0; --i) { preds.set(i, q); q = q.down; } for (;;) { Object k = s.readObject(); if (k == null) break; Object v = s.readObject(); if (v == null) throw new NullPointerException(); K key = (K) k; V val = (V) v; int j = randomLevel(); if (j > h.level) j = h.level + 1; Node<K,V> z = new Node<K,V>(key, val, null); basepred.next = z; basepred = z; if (j > 0) { Index<K,V> idx = null; for (int i = 1; i <= j; ++i) { idx = new Index<K,V>(z, idx, null); if (i > h.level) h = new HeadIndex<K,V>(h.node, h, idx, i); if (i < preds.size()) { preds.get(i).right = idx; preds.set(i, idx); } else preds.add(idx); } } } head = h;
public V	remove(java.lang.Object key) Removes the mapping for the specified key from this map if present. param key key for which mapping should be removed return the previous value associated with the specified key, or null if there was no mapping for the key throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key is null return doRemove(key, null);
public boolean	remove(java.lang.Object key, java.lang.Object value) {@inheritDoc} throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key is null if (key == null) throw new NullPointerException(); if (value == null) return false; return doRemove(key, value) != null;
public boolean	replace(K key, V oldValue, V newValue) {@inheritDoc} throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if any of the arguments are null if (oldValue == null || newValue == null) throw new NullPointerException(); Comparable<? super K> k = comparable(key); for (;;) { Node<K,V> n = findNode(k); if (n == null) return false; Object v = n.value; if (v != null) { if (!oldValue.equals(v)) return false; if (n.casValue(v, newValue)) return true; } }
public V	replace(K key, V value) {@inheritDoc} return the previous value associated with the specified key, or null if there was no mapping for the key throws ClassCastException if the specified key cannot be compared with the keys currently in the map throws NullPointerException if the specified key or value is null if (value == null) throw new NullPointerException(); Comparable<? super K> k = comparable(key); for (;;) { Node<K,V> n = findNode(k); if (n == null) return null; Object v = n.value; if (v != null && n.casValue(v, value)) return (V)v; }
public int	size() Returns the number of key-value mappings in this map. If this map contains more than Integer.MAX_VALUE elements, it returns Integer.MAX_VALUE. Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires traversing them all to count them. Additionally, it is possible for the size to change during execution of this method, in which case the returned result will be inaccurate. Thus, this method is typically not very useful in concurrent applications. return the number of elements in this map long count = 0; for (Node<K,V> n = findFirst(); n != null; n = n.next) { if (n.getValidValue() != null) ++count; } return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
public java.util.concurrent.ConcurrentNavigableMap	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code fromKey} or {@code toKey} is null throws IllegalArgumentException {@inheritDoc} if (fromKey == null || toKey == null) throw new NullPointerException(); return new SubMap<K,V> (this, fromKey, fromInclusive, toKey, toInclusive, false);
public java.util.concurrent.ConcurrentNavigableMap	subMap(K fromKey, K toKey) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code fromKey} or {@code toKey} is null throws IllegalArgumentException {@inheritDoc} return subMap(fromKey, true, toKey, false);
public java.util.concurrent.ConcurrentNavigableMap	tailMap(K fromKey, boolean inclusive) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code fromKey} is null throws IllegalArgumentException {@inheritDoc} if (fromKey == null) throw new NullPointerException(); return new SubMap<K,V> (this, fromKey, inclusive, null, false, false);
public java.util.concurrent.ConcurrentNavigableMap	tailMap(K fromKey) throws ClassCastException {@inheritDoc} throws NullPointerException if {@code fromKey} is null throws IllegalArgumentException {@inheritDoc} return tailMap(fromKey, true);
static final java.util.List	toList(java.util.Collection c) // Using size() here would be a pessimization. List<E> list = new ArrayList<E>(); for (E e : c) list.add(e); return list;
private void	tryReduceLevel() Possibly reduce head level if it has no nodes. This method can (rarely) make mistakes, in which case levels can disappear even though they are about to contain index nodes. This impacts performance, not correctness. To minimize mistakes as well as to reduce hysteresis, the level is reduced by one only if the topmost three levels look empty. Also, if the removed level looks non-empty after CAS, we try to change it back quick before anyone notices our mistake! (This trick works pretty well because this method will practically never make mistakes unless current thread stalls immediately before first CAS, in which case it is very unlikely to stall again immediately afterwards, so will recover.) We put up with all this rather than just let levels grow because otherwise, even a small map that has undergone a large number of insertions and removals will have a lot of levels, slowing down access more than would an occasional unwanted reduction. HeadIndex<K,V> h = head; HeadIndex<K,V> d; HeadIndex<K,V> e; if (h.level > 3 && (d = (HeadIndex<K,V>)h.down) != null && (e = (HeadIndex<K,V>)d.down) != null && e.right == null && d.right == null && h.right == null && casHead(h, d) && // try to set h.right != null) // recheck casHead(d, h); // try to backout
java.util.Iterator	valueIterator() return new ValueIterator();
public java.util.Collection	values() Returns a {@link Collection} view of the values contained in this map. The collection's iterator returns the values in ascending order of the corresponding keys. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations. The view's iterator is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction. Values vs = values; return (vs != null) ? vs : (values = new Values(this));
private void	writeObject(java.io.ObjectOutputStream s) Save the state of this map to a stream. serialData The key (Object) and value (Object) for each key-value mapping represented by the map, followed by null. The key-value mappings are emitted in key-order (as determined by the Comparator, or by the keys' natural ordering if no Comparator). // Write out the Comparator and any hidden stuff s.defaultWriteObject(); // Write out keys and values (alternating) for (Node<K,V> n = findFirst(); n != null; n = n.next) { V v = n.getValidValue(); if (v != null) { s.writeObject(n.key); s.writeObject(v); } } s.writeObject(null);