Java/ConcurrentSkipList

Notes on the ConcurrentSkipList class implementation in Java.

Link: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

Opening

This class is basically concerned with concurrent skip lists for use in multi-threaded programs. This implements lock/protection mechanisms to make it thread-safe.

The opening comment of the file is quite extensive. It gives several references, and explains the overall logic of the class design.

Helpfully, it gives a notation guide for variable names:

     * Notation guide for local variables
     * Node:         b, n, f    for  predecessor, node, successor
     * Index:        q, r, d    for index node, right, down.
     *               t          for another index node
     * Head:         h
     * Levels:       j
     * Keys:         k, key
     * Values:       v, value
     * Comparisons:  c

Helpful because, when you're writing these algorithms, there are lots of nodes and pointers flying around, and no obvious names for any of them.

Fields

The field declarations for the class start around line 320: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L323

The class uses a random number generator to generate an overall (per-instance) random number.

The class implements the head pointer as a HeadIndex<K,V> object.

There is a Comparator object used to compare keys, that takes inputs of type K or derived from K:

 private final Comparator<? super K> comparator;

Methods

After defining the fields that are part of this class, it moves into defining some utility classes, the first of which is a key-value Node class that takes two generic types, K and V.

The Node class stores a key, stores a value, and stores a next pointer. It's like a simple Linked List node. Link: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L394

Next is an index class to represent the various levels of the skip list: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L540

Here is the HeadIndex item, which extends the index class and is the type of the ConcurrentSkipList's "head" pointer: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L614

The ComparableUsingComparator class, confusingly named, is basically a class to hold a Key-Comparator pair.

What makes it confusing is, the class holding the Key object and the Comparator object then implement the Comparable<K> interface, which means this object can be directly compared with other objects. Further confusing matters, the comparable interface that is defined allows this object (of type ComparableUsingComparator) to be compared to Key objects (not the same type). These comparisons are performed, no surprise, with the Comparator that the class stores.

This is an interesting pattern - the ComparableUsingComparator<K> class doesn't, strictly speaking, look like or work like a key, but it provides a bundle (that contains a key) that can be compared with keys using customizable comparison criteria.

Here's that last class:

    /**
     * Represents a key with a comparator as a Comparable.
     *
     * Because most sorted collections seem to use natural ordering on
     * Comparables (Strings, Integers, etc), most internal methods are
     * geared to use them. This is generally faster than checking
     * per-comparison whether to use comparator or comparable because
     * it doesn't require a (Comparable) cast for each comparison.
     * (Optimizers can only sometimes remove such redundant checks
     * themselves.) When Comparators are used,
     * ComparableUsingComparators are created so that they act in the
     * same way as natural orderings. This penalizes use of
     * Comparators vs Comparables, which seems like the right
     * tradeoff.
     */
    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);
        }
}

Comparisons

More comparison stuff:

• The ComparableUsingComparator class above is only used in some cases by the skip list, specifically, when the user specifies a Comparator to use to compare keys.
• There is a comparable(Object key) method that attempts to return a comparable object - if the user has specified a key Comparator, it returns a ComparableUsingComparator object; otherwise it attempts to cast the key object as a Comparable: return (Comparable<? super K>)key;
• A compare(Key k1, Key k2) method is implemented, which takes two keys, performs a comparison (again, using a Comparator if one was provided at construction) and returns an integer.

Further comparisons:

• Two additional methods, called inHalfOpenRange and inOpenRange, take boundary keys as arguments and return whether a key of interest is between those key boundaries. These enable the creation of sub-maps. This type of operation would be extremely useful if implementing timestamp or date information as keys.

Traversal

Traversal section of the ConcurrentSkipListMap class: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L701

The principal (private) method implemented by this class is the findPredecessor method. This method takes a Comparable<K> object as an argument - hence the reason for the comparable method defined above, which takes a Key object and returns a Comparable version of that key.

(Note the notation convention listed above.)

    private Node<K,V> findPredecessor(Comparable<? super K> key) {
        if (key == null)
            throw new NullPointerException(); // don't postpone errors

Before reviewing the body of the method, let's review a comment from the beginning, which explains the difference between an Index and a Node object. Namely, the Node object holds the key-value pair, and is singly-linked, but the Index class has a comment that explains why:

     * This class implements a tree-like two-dimensionally linked skip
     * list in which the index levels are represented in separate
     * nodes from the base nodes holding data.  There are two reasons
     * for taking this approach instead of the usual array-based
     * structure: 1) Array based implementations seem to encounter
     * more complexity and overhead 2) We can use cheaper algorithms
     * for the heavily-traversed index lists than can be used for the
     * base lists.  Here's a picture of some of the basics for a
     * possible list with 2 levels of index:
     *
     * Head nodes          Index nodes
     * +-+    right        +-+                      +-+
     * |2|---------------->| |--------------------->| |->null
     * +-+                 +-+                      +-+
     *  | down              |                        |
     *  v                   v                        v
     * +-+            +-+  +-+       +-+            +-+       +-+
     * |1|----------->| |->| |------>| |----------->| |------>| |->null
     * +-+            +-+  +-+       +-+            +-+       +-+
     *  v              |    |         |              |         |
     * Nodes  next     v    v         v              v         v
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
     * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+

The Index class and the Node class are separate because of their "forward-pointing" fields, which have different types:

     * Index nodes represent the levels of the skip list.  Note that
     * even though both Nodes and Indexes have forward-pointing
     * fields, they have different types and are handled in different
     * ways, that can't nicely be captured by placing field in a
     * shared abstract class.

What follows is the loop. The letter q represents the current Index, r represents the next Index to the right (null if we are at the right side of the list). We declare q and r as the main operational pointers that we'll use in the algorithm.

        for (;;) {
            Index<K,V> q = head;
            Index<K,V> r = q.right;

The main operation we are doing in this algorithm is getting the Node (the object that stores the key-value pair) associated with a particular Index (the Index to the right, in particular) and compare it to the key that was passed in. If the Index+Node we're looking at has a key that's larger than us, we stop moving to the right and move down. Otherwise, we keep moving 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;
                    }
                }

Above is the part of the code where we keep moving right until we find an Index+Node whose key is greater than the key passed in.

Once that Index is found, q is pointing to the right-most node smaller than our key, and we move the pointer down. If we can't move down any further, we're at the very bottom of the skip list, and we should return the node at the Index q.

                Index<K,V> d = q.down;
                if (d != null) {
                    q = d;
                    r = d.right;
                } else
                    return q.node;
            }
        }
    }