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

Comparison Stuff

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 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.