implements ConcurrentNavigableMap<K,V>,

Cloneable,

java.io.Serializable {

/*

private static final long serialVersionUID = -8627078645895051609L;

/**

private static final Random seedGenerator = new Random();

/**

private static final Object BASE_HEADER = new Object();

/**

private transient volatile HeadIndex<K,V> head;

/**

private final Comparator<? super K> comparator;

/**

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;

/**

final void initialize() {

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);

}

/** Updater for casHead */

private static final

AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>

headUpdater = AtomicReferenceFieldUpdater.newUpdater

(ConcurrentSkipListMap.class, HeadIndex.class, "head");

/**

private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {

return headUpdater.compareAndSet(this, cmp, val);

}

/* ---------------- Nodes -------------- */

/**

static final class Node<K,V> {

final K key;

volatile Object value;

volatile Node<K,V> next;

/**

Node(K key, Object value, Node<K,V> next) {

this.key = key;

this.value = value;

this.next = next;

}

/**

Node(Node<K,V> next) {

this.key = null;

this.value = this;

this.next = next;

}

/** Updater for casNext */

static final AtomicReferenceFieldUpdater<Node, Node>

nextUpdater = AtomicReferenceFieldUpdater.newUpdater

(Node.class, Node.class, "next");

/** Updater for casValue */

static final AtomicReferenceFieldUpdater<Node, Object>

valueUpdater = AtomicReferenceFieldUpdater.newUpdater

(Node.class, Object.class, "value");

/**

boolean casValue(Object cmp, Object val) {

return valueUpdater.compareAndSet(this, cmp, val);

}

/**

boolean casNext(Node<K,V> cmp, Node<K,V> val) {

return nextUpdater.compareAndSet(this, cmp, val);

}

/**

boolean isMarker() {

return value == this;

}

/**

boolean isBaseHeader() {

return value == BASE_HEADER;

}

/**

boolean appendMarker(Node<K,V> f) {

return casNext(f, new Node<K,V>(f));

}

/**

void helpDelete(Node<K,V> b, Node<K,V> f) {

/*

if (f == next && this == b.next) {

if (f == null || f.value != f) // not already marked

appendMarker(f);

else

b.casNext(this, f.next);

}

}

/**

V getValidValue() {

Object v = value;

if (v == this || v == BASE_HEADER)

return null;

return (V)v;

}

/**

AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {

V v = getValidValue();

if (v == null)

return null;

return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);

}

}

/* ---------------- Indexing -------------- */

/**

static class Index<K,V> {

final Node<K,V> node;

final Index<K,V> down;

volatile Index<K,V> right;

/**

Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {

this.node = node;

this.down = down;

this.right = right;

}

/** Updater for casRight */

static final AtomicReferenceFieldUpdater<Index, Index>

rightUpdater = AtomicReferenceFieldUpdater.newUpdater

(Index.class, Index.class, "right");

/**

final boolean casRight(Index<K,V> cmp, Index<K,V> val) {

return rightUpdater.compareAndSet(this, cmp, val);

}

/**

final boolean indexesDeletedNode() {

return node.value == null;

}

/**

final boolean link(Index<K,V> succ, Index<K,V> newSucc) {

Node<K,V> n = node;

newSucc.right = succ;

return n.value != null && casRight(succ, newSucc);

}

/**

final boolean unlink(Index<K,V> succ) {

return !indexesDeletedNode() && casRight(succ, succ.right);

}

}

/* ---------------- Head nodes -------------- */

/**

static final class HeadIndex<K,V> extends Index<K,V> {

final int level;

HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {

super(node, down, right);

this.level = level;

}

}

/* ---------------- Comparison utilities -------------- */

/**

static final class ComparableUsingComparator<K> implements Comparable<K> {

final K actualKey;

final Comparator<? super K> cmp;

ComparableUsingComparator(K key, Comparator<? super K> cmp) {

this.actualKey = key;

this.cmp = cmp;

}

public int compareTo(K k2) {

return cmp.compare(actualKey, k2);

}

}

/**

private Comparable<? super K> comparable(Object key) throws ClassCastException {

if (key == null)

throw new NullPointerException();

if (comparator != null)

return new ComparableUsingComparator<K>((K)key, comparator);

else

return (Comparable<? super K>)key;

}

/**

int compare(K k1, K k2) throws ClassCastException {

Comparator<? super K> cmp = comparator;

if (cmp != null)

return cmp.compare(k1, k2);

else

return ((Comparable<? super K>)k1).compareTo(k2);

}

/**

boolean inHalfOpenRange(K key, K least, K fence) {

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) {

if (key == null)

throw new NullPointerException();

return ((least == null || compare(key, least) >= 0) &&

(fence == null || compare(key, fence) <= 0));

}

/* ---------------- Traversal -------------- */

/**

private Node<K,V> findPredecessor(Comparable<? super K> 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 Node<K,V> findNode(Comparable<? super K> key) {

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 V doGet(Object okey) {

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 getUsingFindNode(Comparable<? super K> key) {

/*

for (;;) {

Node<K,V> n = findNode(key);

if (n == null)

return null;

Object v = n.value;

if (v != null)

return (V)v;

}

}

/* ---------------- Insertion -------------- */

/**

private V doPut(K kkey, V value, boolean onlyIfAbsent) {

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;

}

}

}

/**

private int randomLevel() {

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 insertIndex(Node<K,V> z, int level) {

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

/*

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);

}

}

/**

private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {

// 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;