src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

Print this page

        

*** 33,43 **** * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent; import java.util.*; - import java.util.concurrent.atomic.*; /** * A scalable concurrent {@link ConcurrentNavigableMap} implementation. * The map is sorted according to the {@linkplain Comparable natural * ordering} of its keys, or by a {@link Comparator} provided at map --- 33,42 ----
*** 88,97 **** --- 87,97 ---- * @author Doug Lea * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values * @since 1.6 */ + @SuppressWarnings("unchecked") public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V>, Cloneable, java.io.Serializable { /*
*** 350,364 **** * doesn't matter too much if different threads don't see updates. */ private transient int randomSeed; /** Lazily initialized key set */ ! private transient KeySet keySet; /** Lazily initialized entry set */ ! private transient EntrySet entrySet; /** Lazily initialized values collection */ ! private transient Values values; /** Lazily initialized descending key set */ private transient ConcurrentNavigableMap<K,V> descendingMap; /** * Initializes or resets state. Needed by constructors, clone, --- 350,364 ---- * doesn't matter too much if different threads don't see updates. */ private transient int randomSeed; /** Lazily initialized key set */ ! private transient KeySet<K> keySet; /** Lazily initialized entry set */ ! private transient EntrySet<K,V> entrySet; /** Lazily initialized values collection */ ! private transient Values<V> values; /** Lazily initialized descending key set */ private transient ConcurrentNavigableMap<K,V> descendingMap; /** * Initializes or resets state. Needed by constructors, clone,
*** 515,525 **** private static final long nextOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class k = Node.class; valueOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("value")); nextOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("next")); } catch (Exception e) { --- 515,525 ---- private static final long nextOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class<?> k = Node.class; valueOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("value")); nextOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("next")); } catch (Exception e) {
*** 595,605 **** private static final sun.misc.Unsafe UNSAFE; private static final long rightOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class k = Index.class; rightOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("right")); } catch (Exception e) { throw new Error(e); } --- 595,605 ---- private static final sun.misc.Unsafe UNSAFE; private static final long rightOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class<?> k = Index.class; rightOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("right")); } catch (Exception e) { throw new Error(e); }
*** 931,941 **** * 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; --- 931,941 ---- * 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;
*** 1434,1454 **** * instance. (The keys and values themselves are not cloned.) * * @return a shallow copy of this map */ public ConcurrentSkipListMap<K,V> clone() { - 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; } /** * Streamlined bulk insertion to initialize from elements of * given sorted map. Call only from constructor or clone * method. --- 1434,1454 ---- * instance. (The keys and values themselves are not cloned.) * * @return a shallow copy of this map */ public ConcurrentSkipListMap<K,V> clone() { try { ! @SuppressWarnings("unchecked") ! ConcurrentSkipListMap<K,V> clone = ! (ConcurrentSkipListMap<K,V>) super.clone(); clone.initialize(); clone.buildFromSorted(this); return clone; + } catch (CloneNotSupportedException e) { + throw new InternalError(); } + } /** * Streamlined bulk insertion to initialize from elements of * given sorted map. Call only from constructor or clone * method.
*** 1505,1515 **** } /* ---------------- Serialization -------------- */ /** ! * 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 * <tt>null</tt>. The key-value mappings are emitted in key-order * (as determined by the Comparator, or by the keys' natural --- 1505,1515 ---- } /* ---------------- Serialization -------------- */ /** ! * Saves the state of this map to a stream (that is, serializes it). * * @serialData The key (Object) and value (Object) for each * key-value mapping represented by the map, followed by * <tt>null</tt>. The key-value mappings are emitted in key-order * (as determined by the Comparator, or by the keys' natural
*** 1530,1540 **** } s.writeObject(null); } /** ! * Reconstitute the map from a stream. */ private void readObject(final java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in the Comparator and any hidden stuff s.defaultReadObject(); --- 1530,1542 ---- } s.writeObject(null); } /** ! * Reconstitutes the map from a stream (that is, deserializes it). ! * ! * @param s the stream */ private void readObject(final java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in the Comparator and any hidden stuff s.defaultReadObject();
*** 1753,1769 **** * <p>This method is equivalent to method {@code navigableKeySet}. * * @return a navigable set view of the keys in this map */ public NavigableSet<K> keySet() { ! KeySet ks = keySet; ! return (ks != null) ? ks : (keySet = new KeySet(this)); } public NavigableSet<K> navigableKeySet() { ! KeySet ks = keySet; ! return (ks != null) ? ks : (keySet = new KeySet(this)); } /** * Returns a {@link Collection} view of the values contained in this map. * The collection's iterator returns the values in ascending order --- 1755,1771 ---- * <p>This method is equivalent to method {@code navigableKeySet}. * * @return a navigable set view of the keys in this map */ public NavigableSet<K> keySet() { ! KeySet<K> ks = keySet; ! return (ks != null) ? ks : (keySet = new KeySet<K>(this)); } public NavigableSet<K> navigableKeySet() { ! KeySet<K> ks = keySet; ! return (ks != null) ? ks : (keySet = new KeySet<K>(this)); } /** * Returns a {@link Collection} view of the values contained in this map. * The collection's iterator returns the values in ascending order
*** 1781,1792 **** * 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. */ public Collection<V> values() { ! Values vs = values; ! return (vs != null) ? vs : (values = new Values(this)); } /** * Returns a {@link Set} view of the mappings contained in this map. * The set's iterator returns the entries in ascending key order. --- 1783,1794 ---- * 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. */ public Collection<V> values() { ! Values<V> vs = values; ! return (vs != null) ? vs : (values = new Values<V>(this)); } /** * Returns a {@link Set} view of the mappings contained in this map. * The set's iterator returns the entries in ascending key order.
*** 1810,1821 **** * * @return a set view of the mappings contained in this map, * sorted in ascending key order */ public Set<Map.Entry<K,V>> entrySet() { ! EntrySet es = entrySet; ! return (es != null) ? es : (entrySet = new EntrySet(this)); } public ConcurrentNavigableMap<K,V> descendingMap() { ConcurrentNavigableMap<K,V> dm = descendingMap; return (dm != null) ? dm : (descendingMap = new SubMap<K,V> --- 1812,1823 ---- * * @return a set view of the mappings contained in this map, * sorted in ascending key order */ public Set<Map.Entry<K,V>> entrySet() { ! EntrySet<K,V> es = entrySet; ! return (es != null) ? es : (entrySet = new EntrySet<K,V>(this)); } public ConcurrentNavigableMap<K,V> descendingMap() { ConcurrentNavigableMap<K,V> dm = descendingMap; return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
*** 2302,2313 **** return list; } static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { ! private final ConcurrentNavigableMap<E,Object> m; ! KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; } public int size() { return m.size(); } public boolean isEmpty() { return m.isEmpty(); } public boolean contains(Object o) { return m.containsKey(o); } public boolean remove(Object o) { return m.remove(o) != null; } public void clear() { m.clear(); } --- 2304,2315 ---- return list; } static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { ! private final ConcurrentNavigableMap<E,?> m; ! KeySet(ConcurrentNavigableMap<E,?> map) { m = map; } public int size() { return m.size(); } public boolean isEmpty() { return m.isEmpty(); } public boolean contains(Object o) { return m.containsKey(o); } public boolean remove(Object o) { return m.remove(o) != null; } public void clear() { m.clear(); }
*** 2317,2331 **** public E higher(E e) { return m.higherKey(e); } public Comparator<? super E> comparator() { return m.comparator(); } public E first() { return m.firstKey(); } public E last() { return m.lastKey(); } public E pollFirst() { ! Map.Entry<E,Object> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } public E pollLast() { ! Map.Entry<E,Object> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } public Iterator<E> iterator() { if (m instanceof ConcurrentSkipListMap) return ((ConcurrentSkipListMap<E,Object>)m).keyIterator(); --- 2319,2333 ---- public E higher(E e) { return m.higherKey(e); } public Comparator<? super E> comparator() { return m.comparator(); } public E first() { return m.firstKey(); } public E last() { return m.lastKey(); } public E pollFirst() { ! Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } public E pollLast() { ! Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } public Iterator<E> iterator() { if (m instanceof ConcurrentSkipListMap) return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
*** 2372,2395 **** } public NavigableSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } public NavigableSet<E> descendingSet() { ! return new KeySet(m.descendingMap()); } } static final class Values<E> extends AbstractCollection<E> { ! private final ConcurrentNavigableMap<Object, E> m; ! Values(ConcurrentNavigableMap<Object, E> map) { m = map; } public Iterator<E> iterator() { if (m instanceof ConcurrentSkipListMap) ! return ((ConcurrentSkipListMap<Object,E>)m).valueIterator(); else ! return ((SubMap<Object,E>)m).valueIterator(); } public boolean isEmpty() { return m.isEmpty(); } public int size() { --- 2374,2397 ---- } public NavigableSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } public NavigableSet<E> descendingSet() { ! return new KeySet<E>(m.descendingMap()); } } static final class Values<E> extends AbstractCollection<E> { ! private final ConcurrentNavigableMap<?, E> m; ! Values(ConcurrentNavigableMap<?, E> map) { m = map; } public Iterator<E> iterator() { if (m instanceof ConcurrentSkipListMap) ! return ((ConcurrentSkipListMap<?,E>)m).valueIterator(); else ! return ((SubMap<?,E>)m).valueIterator(); } public boolean isEmpty() { return m.isEmpty(); } public int size() {
*** 2419,2436 **** } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; ! Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o; V1 v = m.get(e.getKey()); return v != null && v.equals(e.getValue()); } public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; ! Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o; return m.remove(e.getKey(), e.getValue()); } public boolean isEmpty() { return m.isEmpty(); --- 2421,2438 ---- } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; ! Map.Entry<?,?> e = (Map.Entry<?,?>)o; V1 v = m.get(e.getKey()); return v != null && v.equals(e.getValue()); } public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; ! Map.Entry<?,?> e = (Map.Entry<?,?>)o; return m.remove(e.getKey(), e.getValue()); } public boolean isEmpty() { return m.isEmpty();
*** 2566,2578 **** */ private ConcurrentSkipListMap.Node<K,V> loNode() { if (lo == null) return m.findFirst(); else if (loInclusive) ! return m.findNear(lo, m.GT|m.EQ); else ! return m.findNear(lo, m.GT); } /** * Returns highest node. This node might not be in range, so * most usages need to check bounds --- 2568,2580 ---- */ private ConcurrentSkipListMap.Node<K,V> loNode() { if (lo == null) return m.findFirst(); else if (loInclusive) ! return m.findNear(lo, GT|EQ); else ! return m.findNear(lo, GT); } /** * Returns highest node. This node might not be in range, so * most usages need to check bounds
*** 2579,2591 **** */ private ConcurrentSkipListMap.Node<K,V> hiNode() { if (hi == null) return m.findLast(); else if (hiInclusive) ! return m.findNear(hi, m.LT|m.EQ); else ! return m.findNear(hi, m.LT); } /** * Returns lowest absolute key (ignoring directonality) */ --- 2581,2593 ---- */ private ConcurrentSkipListMap.Node<K,V> hiNode() { if (hi == null) return m.findLast(); else if (hiInclusive) ! return m.findNear(hi, LT|EQ); else ! return m.findNear(hi, LT); } /** * Returns lowest absolute key (ignoring directonality) */
*** 2663,2681 **** /** * Submap version of ConcurrentSkipListMap.getNearEntry */ private Map.Entry<K,V> getNearEntry(K key, int rel) { if (isDescending) { // adjust relation for direction ! if ((rel & m.LT) == 0) ! rel |= m.LT; else ! rel &= ~m.LT; } if (tooLow(key)) ! return ((rel & m.LT) != 0) ? null : lowestEntry(); if (tooHigh(key)) ! return ((rel & m.LT) != 0) ? highestEntry() : null; for (;;) { Node<K,V> n = m.findNear(key, rel); if (n == null || !inBounds(n.key)) return null; K k = n.key; --- 2665,2683 ---- /** * Submap version of ConcurrentSkipListMap.getNearEntry */ private Map.Entry<K,V> getNearEntry(K key, int rel) { if (isDescending) { // adjust relation for direction ! if ((rel & LT) == 0) ! rel |= LT; else ! rel &= ~LT; } if (tooLow(key)) ! return ((rel & LT) != 0) ? null : lowestEntry(); if (tooHigh(key)) ! return ((rel & LT) != 0) ? highestEntry() : null; for (;;) { Node<K,V> n = m.findNear(key, rel); if (n == null || !inBounds(n.key)) return null; K k = n.key;
*** 2686,2710 **** } // Almost the same as getNearEntry, except for keys private K getNearKey(K key, int rel) { if (isDescending) { // adjust relation for direction ! if ((rel & m.LT) == 0) ! rel |= m.LT; else ! rel &= ~m.LT; } if (tooLow(key)) { ! if ((rel & m.LT) == 0) { ConcurrentSkipListMap.Node<K,V> n = loNode(); if (isBeforeEnd(n)) return n.key; } return null; } if (tooHigh(key)) { ! if ((rel & m.LT) != 0) { ConcurrentSkipListMap.Node<K,V> n = hiNode(); if (n != null) { K last = n.key; if (inBounds(last)) return last; --- 2688,2712 ---- } // Almost the same as getNearEntry, except for keys private K getNearKey(K key, int rel) { if (isDescending) { // adjust relation for direction ! if ((rel & LT) == 0) ! rel |= LT; else ! rel &= ~LT; } if (tooLow(key)) { ! if ((rel & LT) == 0) { ConcurrentSkipListMap.Node<K,V> n = loNode(); if (isBeforeEnd(n)) return n.key; } return null; } if (tooHigh(key)) { ! if ((rel & LT) != 0) { ConcurrentSkipListMap.Node<K,V> n = hiNode(); if (n != null) { K last = n.key; if (inBounds(last)) return last;
*** 2732,2742 **** } public V get(Object key) { if (key == null) throw new NullPointerException(); K k = (K)key; ! return ((!inBounds(k)) ? null : m.get(k)); } public V put(K key, V value) { checkKeyBounds(key); return m.put(key, value); --- 2734,2744 ---- } public V get(Object key) { if (key == null) throw new NullPointerException(); K k = (K)key; ! return (!inBounds(k)) ? null : m.get(k); } public V put(K key, V value) { checkKeyBounds(key); return m.put(key, value);
*** 2899,2937 **** } /* ---------------- Relational methods -------------- */ public Map.Entry<K,V> ceilingEntry(K key) { ! return getNearEntry(key, (m.GT|m.EQ)); } public K ceilingKey(K key) { ! return getNearKey(key, (m.GT|m.EQ)); } public Map.Entry<K,V> lowerEntry(K key) { ! return getNearEntry(key, (m.LT)); } public K lowerKey(K key) { ! return getNearKey(key, (m.LT)); } public Map.Entry<K,V> floorEntry(K key) { ! return getNearEntry(key, (m.LT|m.EQ)); } public K floorKey(K key) { ! return getNearKey(key, (m.LT|m.EQ)); } public Map.Entry<K,V> higherEntry(K key) { ! return getNearEntry(key, (m.GT)); } public K higherKey(K key) { ! return getNearKey(key, (m.GT)); } public K firstKey() { return isDescending ? highestKey() : lowestKey(); } --- 2901,2939 ---- } /* ---------------- Relational methods -------------- */ public Map.Entry<K,V> ceilingEntry(K key) { ! return getNearEntry(key, GT|EQ); } public K ceilingKey(K key) { ! return getNearKey(key, GT|EQ); } public Map.Entry<K,V> lowerEntry(K key) { ! return getNearEntry(key, LT); } public K lowerKey(K key) { ! return getNearKey(key, LT); } public Map.Entry<K,V> floorEntry(K key) { ! return getNearEntry(key, LT|EQ); } public K floorKey(K key) { ! return getNearKey(key, LT|EQ); } public Map.Entry<K,V> higherEntry(K key) { ! return getNearEntry(key, GT); } public K higherKey(K key) { ! return getNearKey(key, GT); } public K firstKey() { return isDescending ? highestKey() : lowestKey(); }
*** 2958,2983 **** /* ---------------- Submap Views -------------- */ public NavigableSet<K> keySet() { KeySet<K> ks = keySetView; ! return (ks != null) ? ks : (keySetView = new KeySet(this)); } public NavigableSet<K> navigableKeySet() { KeySet<K> ks = keySetView; ! return (ks != null) ? ks : (keySetView = new KeySet(this)); } public Collection<V> values() { Collection<V> vs = valuesView; ! return (vs != null) ? vs : (valuesView = new Values(this)); } public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es = entrySetView; ! return (es != null) ? es : (entrySetView = new EntrySet(this)); } public NavigableSet<K> descendingKeySet() { return descendingMap().navigableKeySet(); } --- 2960,2985 ---- /* ---------------- Submap Views -------------- */ public NavigableSet<K> keySet() { KeySet<K> ks = keySetView; ! return (ks != null) ? ks : (keySetView = new KeySet<K>(this)); } public NavigableSet<K> navigableKeySet() { KeySet<K> ks = keySetView; ! return (ks != null) ? ks : (keySetView = new KeySet<K>(this)); } public Collection<V> values() { Collection<V> vs = valuesView; ! return (vs != null) ? vs : (valuesView = new Values<V>(this)); } public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es = entrySetView; ! return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this)); } public NavigableSet<K> descendingKeySet() { return descendingMap().navigableKeySet(); }
*** 3107,3117 **** private static final sun.misc.Unsafe UNSAFE; private static final long headOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class k = ConcurrentSkipListMap.class; headOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("head")); } catch (Exception e) { throw new Error(e); } --- 3109,3119 ---- private static final sun.misc.Unsafe UNSAFE; private static final long headOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); ! Class<?> k = ConcurrentSkipListMap.class; headOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("head")); } catch (Exception e) { throw new Error(e); }