Ctrie
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots.
A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots. bit = bmp & (1 > level) & 0x1F)) pos = bitcount((bit - 1) & bmp) Note that the operations treat only the I-nodes as mutable nodes - all other nodes are never changed after being created and added to the Ctrie. Below is an illustration of the pseudocode of the insert operation: def insert(k, v) r = READ(root) if iinsert(r, k, v, 0, null) = RESTART insert(k, v) def iinsert(i, k, v, lev, parent) cn = READ(i.main) flag, pos = flagpos(k.hc, lev, cn.bmp) if cn.bmp & flag = 0 { ncn = cn.inserted(pos, flag, SNode(k, v)) if CAS(i.main, cn, ncn) return OK else return RESTART } cn.array(pos) match { case sin: INode => { return iinsert(sin, k, v, lev + W, i) case sn: SNode => if sn.k ≠ k { nsn = SNode(k, v) nin = INode(CNode(sn, nsn, lev + W)) ncn = cn.updated(pos, nin) if CAS(i.main, cn, ncn) return OK else return RESTART } else { ncn = cn.updated(pos, SNode(k, v)) if CAS(i.main, cn, ncn) return OK else return RESTART } } The inserted and updated methods on nodes return new versions of the C-node with a value inserted or updated at the specified position, respectively. Note that the insert operation above is tail-recursive, so it can be rewritten as a while loop. Other operations are described in more detail in the original paper on Ctries. The data-structure has been proven to be correct - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties. The lookup operation can be modified to guarantee wait-freedom.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1321686798 under CC BY-SA 4.0; modifications have been made.