ConcurrentSkipListMap source code solution
Previously we learned about the implementation of ConcurrentHashMap. In this article we will learn about Map combination based on skip table implementation.
Introduction of core members
private static final Object BASE_HEADER = new Object(); // Special value of the head of the data linked list
private transient volatile HeadIndex<K,V> head; // Points to the top index node of the jump table
final Comparator<? super K> comparator; // Comparator used to compare keys
public ConcurrentSkipListMap() {<!-- -->
this. comparator = null;
initialize();
}
private void initialize() {<!-- -->
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
// Initialize the head index node
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null, null, 1);
}
// Encapsulate key-value node class
static final class Node<K,V> {<!-- -->
final K key;
volatile Object value;
volatile Node<K,V> next; // one-way linked list structure
Node(K key, Object value, Node<K,V> next) {<!-- -->
this.key = key;
this.value = value;
this. next = next;
}
//Create a mark node, at this time key == null, value points to itself
Node(Node<K,V> next) {<!-- -->
this.key = null;
this.value = this;
this. next = next;
}
}
// The head node of each layer Index index node
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;
}
}
// Jump table index node, jump table hierarchical structure implementation
static class Index<K,V> {<!-- -->
final Node<K,V> node; // current data node
final Index<K,V> down;// next layer index node
volatile Index<K,V> right;//The index node that jumps forward
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {<!-- -->
this.node = node;
this.down = down;
this.right = right;
}
}
Introduction to core methods
put add data
1. Insert data into the data node linked list. If it is found that the node is deleted during the insertion process, it will help to delete the node from the linked list. If it is found that the key already exists, judge whether to update the value value according to onlyIfAbsent
2. Use random numbers to control whether to add index nodes and index levels. Up to one level can be added each time. The effect is as shown in the figure.
public V put(K key, V value) {<!-- -->
return doPut(key, value, false);
}
private V doPut(K key, V value, boolean onlyIfAbsent) {<!-- -->
Node<K,V> z; // added node
Comparator<? super K> cmp = comparator; // Default comparator = null
outer: for (;;) {<!-- -->// guarantee successful insertion
//Call the findPredecessor method to find node nodes smaller than the given key
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {<!-- -->
if (n != null) {<!-- -->// The current node b has a next node
Object v; int c;
Node<K,V> f = n.next; // Take out the next node of n
// The node has changed, exit the current loop, and repeat the outer loop
if (n != b. next) break;
if ((v = n.value) == null) {<!-- --> // n node is deleted to help remove the jump table
/* helpDelete method
if (f == next & amp; & amp; this == b.next) { // The f node has not changed
if (f == null // The current node is the last node, that is, n is the last node
|| f.value != f) // Determine whether node f has been deleted
casNext(f, new Node<K,V>(f)); // CAS updates n node next to point to a marked node
else
b.casNext(this, f.next); // Executing to this step means that the f node has also been deleted, then point b.next to f.next
}
*/
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // Indicates that the current node has been deleted, exit the current loop, and repeat the outer loop
break;
if ((c = cpr(cmp, key, n.key)) > 0) {<!-- -->// If the current key is greater than n.key, then update b and n to continue searching
b = n;
n = f;
continue;
}
if (c == 0) {<!-- --> // Indicates that there is a node with the same key in the jump table, and CAS updates the value of the node
if (onlyIfAbsent || n.casValue(v, value)) {<!-- -->
V vv = (V)v;
return vv;//updated successfully return value
}
break;
}
}
z = new Node<K,V>(key, value, n);// Create a new node node, z.next = n
if (!b.casNext(n, z)) // cas update b.next = z
break;
break outer;
}
}
// Create an index node through a random number & amp; 0x80000001 to see if the high and low bits are 0. When both the high and low bits are 0, create an index node
int rnd = ThreadLocalRandom. nextSecondarySeed();
if ((rnd & amp; 0x80000001) == 0) {<!-- -->
int level = 1, max; // initial index level level = 1
while (((rnd >>>= 1) & amp; 1) != 0) // random number unsigned right shift 1 bit to check whether the last bit is 0, exit the loop if it is 0, otherwise level + 1
+ + level;
Index<K,V> idx = null;
HeadIndex<K,V> h = head;//Get the index head node
// The default head.level == 1 of the head node, the first layer index, when level == 1, create an index node for the current node z
if (level <= (max = h.level)) {<!-- -->
for (int i = 1; i <= level; + + i)
idx = new Index<K,V>(z, idx, null);
}
else {<!-- --> // Add a layer of index
level = max + 1; // current index level + 1
Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level + 1];
// Create the index node of the z node, and the index nodes corresponding to the upper and lower layers are associated through down
// The effect after the first cycle is as follows | index2 | --down--> | index1 |
for (int i = 1; i <= level; + + i)
idxs[i] = idx = new Index<K,V>(z, idx, null);
for (;;) {<!-- -->
h = head;
int oldLevel = h.level;
if (level <= oldLevel) break;// other threads have increased the number of index layers and exit the current loop, that is, inconsistent reads have occurred
HeadIndex<K,V> newh = h;// save the current head node
Node<K,V> oldbase = h.node;//Get the node node of the head node, that is, the BASE_HEADER pseudo-node
// Create an index head node, whose node points to the BASE_HEADER pseudo-node, down points to the original head node, and right points to the idx[j] index node
for (int j = oldLevel + 1; j <= level; + + j)
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) {<!-- -->// cas updates head and executes new head node
h = newh;// Get the latest head node for h
idx = idxs[level = oldLevel]; // save oldLevel to level, get the index node of the next level to idx
break;
}
}
}
splice: for (int insertionLevel = level;;) {<!-- -->// Start traversing from the bottom index node
int j = h.level;// Get the latest index level level value
// Each splice loop will traverse from the equal layer index to find the insertion position of the index node
for (Index<K,V> q = h, r = q.right, t = idx;;) {<!-- -->
if (q == null || t == null) break splice; // insertion is complete
if (r != null) {<!-- -->// the right index node is not empty
Node<K,V> n = r.node;// Get the data node of the index node Node
int c = cpr(cmp, key, n.key);//Compare the size of the key of the current node and the key to be inserted through compareTo
if (n.value == null) {<!-- -->// indicates that the node has been deleted
if (!q.unlink(r)) break;// remove the index node from the linked list
r = q.right;// Get the right node again and search again
continue;
}
if (c > 0) {<!-- -->// The key to be inserted is greater than the currently searched key, update q, r continue to search
q = r;
r = r.right;
continue;
}
}
// The above judgment helped us find the insertion point, and the insertion operation starts below
if (j == insertionLevel) {<!-- -->// The level of the head node is equal to the level to be inserted
if (!q.link(r, t)) break; // try to insert t between q and r
if (t.node.value == null) {<!-- -->// The node is deleted, call the findNode method to delete the node, and then exit the loop
findNode(key);
break splice;
}
if (--insertionLevel == 0) break splice;// insertionLevel == 0 means index node insertion is complete
}
// Search down from the index head node to find the correct insertion level node
if (--j >= insertionLevel & amp; & amp; j < level)
t = t.down;
q = q.down; // level down
r = q.right;
}
}
}
return null;
}
findPredecessor Find
Find the data node node node smaller than the given key, that is, find the starting position to be inserted; during the search process, it is found that the right node is in the deleted state, but it has not been removed from the linked list, so help it complete the deletion operation
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {<!-- -->
for (;;) {<!-- -->
for (Index<K,V> q = head, r = q.right, d;;) {<!-- -->
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 (cpr(cmp, key, k) > 0) {<!-- -->
q = r;
r = r.right;
continue;
}
}
if ((d = q.down) == null)
return q.node;
q = d;
r = d.right;
}
}
}
get lookup data
Quickly find the starting position of the data search through the index node, and traverse the search backward through next until the key is found.
public V get(Object key) {<!-- -->
return doGet(key);
}
private V doGet(Object key) {<!-- -->
Comparator<? super K> cmp = comparator;
outer: for (;;) {<!-- -->
//Call findPredecessor to find the starting position of data search
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {<!-- -->
Object v; int c;
if (n == null) break outer;
Node<K,V> f = n.next;
if (n != b.next) break; // Inconsistent reading occurred
if ((v = n.value) == null) {<!-- --> // n node is deleted, help complete the deletion action
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) break; // b node is deleted and exits the current loop
if ((c = cpr(cmp, key, n.key)) == 0) {<!-- -->// If found, just return
V vv = (V)v;
return vv;
}
if (c < 0) break outer; // Not found, return null
b = n;
n = f;
}
}
return null;
}
remove delete data
Use the index node to quickly find the starting position of the data search, and traverse the search backwards through next until the data to be deleted is found. After the deletion is successful, point the next of the current node to a marked node to mark that the node has been deleted
public V remove(Object key) {<!-- -->
return doRemove(key, null);
}
final V doRemove(Object key, Object value) {<!-- -->
Comparator<? super K> cmp = comparator;
outer: for (;;) {<!-- -->
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {<!-- -->
Object v; int c;
if (n == null) break outer;
Node<K,V> f = n. next;
if (n != b.next) break; // inconsistent read
if ((v = n.value) == null) {<!-- --> // n node is deleted, help complete the deletion action
n. helpDelete(b, f);
break;
}
if (b.value == null || v == n) break; // b node is deleted, help complete the deletion action
if ((c = cpr(cmp, key, n.key)) < 0) break outer; // Node not found
if (c > 0) {<!-- --> // Update b and n to continue searching
b = n;
n = f;
continue;
}
if (value != null & amp; & amp; !value.equals(v)) break outer;
if (!n.casValue(v, null)) break; // Find data, CAS delete
// appendMarker method casNext(f, new Node<K,V>(f)); CAS deletion failed in the previous step, try to point the next of n to a marker node to mark the node is deleted, if the marker is successful, update b.next point to f
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // Call findNode to delete the node
else {<!-- -->
findPredecessor(key, cmp); // Delete index node
if (head.right == null) // If there is no index node behind the head node, try to reduce the index level
tryReduceLevel();
}
V vv = (V)v;
return vv; // Return the value of the deleted node
}
}
return null;
}
delete node
else {<!-- -->
findPredecessor(key, cmp); // Delete index node
if (head.right == null) // If there is no index node behind the head node, try to reduce the index level
tryReduceLevel();
}
V vv = (V)v;
return vv; // Return the value of the deleted node
}
}
return null;
}