{
  "id": "enwiki-001321686798",
  "slug": "ctrie",
  "title": "Ctrie",
  "qid": "",
  "lead": "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.",
  "body": "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.",
  "categories": [
    "100993157",
    "26851625"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1321686798",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1762908116.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001321686798",
    "type": "webpage",
    "title": "Ctrie",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/ctrie",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001321686798",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1321686798",
    "note": "Immutable snapshot enwiki-001321686798"
  }
}