flix

0.69.2

BPlusTree.Node

Definitions

def adjustWithKey(f: k -> (v -> v \ ef), key: k, stamp: Int64, t: BPlusTree[k, v, r], node: Node[k, v, r]): Unit \ ef + r with Order[k] Source

Internal method to update the leaf node with key => f(key, val) if key => val is in node.

Otherwise, node is unchanged.

Thread-safe.

Lock invariant:

  • On invocation, stamp is an optimistic stamp on node->lock.
def assertNodeInvariant(node: Node[k, v, r], arity: Int32, isRightMost: Bool, shouldBeBiggerThan: Option[k], search: Search): Bool \ r with Order[k] Source

Returns true if and only if node is structurally correct.

Only used for internal testing.

def childForKey(key: k, search: Search, node: Node[k, v, r]): Node[k, v, r] \ r with Order[k] Source

Returns the child of the internal node whose subtree should be searched for key.

def computeHeight(node: Node[k, v, r]): Int32 \ r Source

Compute the height of the tree rooted in node.

Not thread-safe: Traverses the live tree rooted at node.

def existsFromLeaf(f: k -> (v -> Bool \ ef), index: Int32, node: Node[k, v, r]): Bool \ ef + r Source

Returns true if and only if there exists mappings in the leaf chain that starts at node satisfying f.

The input node must be a leaf.

Not thread-safe: Traverses the live leaf chain that starts at node.

def findLeftFromLeaf(f: k -> (v -> Bool \ ef), index: Int32, node: Node[k, v, r]): Option[(k, v)] \ ef + r Source

Optionally returns the first mapping satisfying f in the leaf chain that starts at node.

The input node must be a leaf.

Not thread-safe: Traverses the live leaf chain that starts at node.

def foldLeftWithKeyFromLeaf(f: b -> (k -> (v -> b \ ef)), acc: b, index: Int32, node: Node[k, v, r]): b \ ef + r Source

Folds over the leaf chain that starts at node, from left to right.

The input node must be a leaf.

Not thread-safe: Traverses the live leaf chain that starts at node.

def get(key: k, stamp: Int64, node: Node[k, v, r], tree: BPlusTree[k, v, r]): Option[v] \ r with Order[k] Source

Returns Some(val) if key => val is in tree. Otherwise return None.

def getKeyAndValue(key: k, stamp: Int64, node: Node[k, v, r], tree: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k] Source

Returns Some((key, value)) if key => val is in tree. Otherwise return None.

def getKeyAndValueAt(index: Int32, node: Node[k, v, r]): (k, v) \ r Source

Return the mapping k => v at position index in node. Crashes if index >= node->size.

def getLock(node: Node[k, v, r]): Lock[r] Source

Provides access to the lock field of node.

def getWithDefault(key: k, stamp: Int64, d: v, node: Node[k, v, r], tree: BPlusTree[k, v, r]): v \ r with Order[k] Source

Returns val if key => val is in tree. Otherwise return d.

def insertIntoLeaf(key: k, val: v, node: Node[k, v, r], stamp: Int64, tree: BPlusTree[k, v, r]): Option[(Node[k, v, r], Int64)] \ r with Order[k] Source

Inserts the mapping key => val into the leaf node, potentially causing a split and returning a new root.

Lock invariants:

  • On invocation, stamp is an optimistic stamp on node->lock.

  • On return, the thread has no lock on the tree if the returned value is None. Otherwise it has a write-lock on tree->rootLock and p where Some(p) is returned

def insertIntoLeafIf(decider: k -> (v -> (k -> (v -> Bool))), key: k, val: v, node: Node[k, v, r], stamp: Int64, tree: BPlusTree[k, v, r]): Option[(Node[k, v, r], Int64)] \ r with Order[k] Source

Inserts the mapping key => val into the leaf node if it is not already present Otherwise if the mapping key2 => val2 is presents overwrite the mapping by key => val, if decider(key, val, key2, val2) == true. If a split is caused return the new root.

Lock invariants:

  • On invocation, stamp is an optimistic stamp on node->lock.

  • On return, the thread has no lock on the tree if the returned value is None. Otherwise it has a write-lock on tree->rootLock and p where Some(p) is returned

def isEmpty(node: Node[k, v, r]): Bool \ r Source

Returns true if node is empty.

Not thread-safe: Reads the live node without synchronization.

def leafMemberOf(key: k, search: Search, node: Node[k, v, r]): Bool \ r with Order[k] Source

Returns true if key is contained in the leaf node.

def leafMemberOfPair(key: k, val: v, search: Search, node: Node[k, v, r]): Bool \ r with Order[k], Eq[v] Source

Returns true if the mapping key => val is contained in the leaf node.

def leftMostLeaf(n: Node[k, v, r], stamp: Int64, t: BPlusTree[k, v, r]): (Node[k, v, r], Int64) \ r with Order[k] Source

Returns the leftmost leaf of the tree rooted at node together with an optimistic stamp on that leaf.

Traverses down the leftmost path of the tree, acquiring locks along the way. If a lock is invalid, yields and retries from the root of t.

def leftMostLeafUnconditional(node: Node[k, v, r]): Node[k, v, r] \ r Source

Returns the left-most leaf node rooted in node.

Not thread-safe: Traverses the live tree rooted at node.

def mkLeaf(rc: Region[r], keys: Array[k, r], values: Array[v, r], size: Int32, parent: Option[Node[k, v, r]], next: Option[Node[k, v, r]]): Node[k, v, r] \ r Source

Create a new leaf node.

def next(node: Node[k, v, r]): Option[Node[k, v, r]] \ r Source

Optionally return the node to the right of node.

def parent(node: Node[k, v, r]): Option[Node[k, v, r]] \ r Source

Provides access to the parent field of node.

def putWith(f: v -> (v -> v \ ef), key: k, val: v, tree: BPlusTree[k, v, r], node: Node[k, v, r], stamp: Int64): Option[(Node[k, v, r], Int64)] \ r + ef with Order[k] Source

Inserts the mapping key => f(val, val1) if key => val1 is in node. Otherwise, inserts key => val into node.

Returns Some(newRoot, stamp) if the root was split.

Thread-safe.

def putWithKey(f: k -> (v -> (v -> v \ ef)), key: k, val: v, tree: BPlusTree[k, v, r], stamp: Int64, node: Node[k, v, r]): Option[(Node[k, v, r], Int64)] \ r + ef with Order[k] Source

Inserts the mapping key => f(key, val, val1) if key => val1 is in node. Otherwise, inserts key => val into node.

Returns Some(newRoot, stamp) if the root was split.

Thread-safe.

def rangeQueryWith(f: k -> (v -> Unit \ r0), min: k, max: k, stamp: Int64, node: Node[k, v, r], tree: BPlusTree[k, v, r]): Unit \ r0 + r with Order[k] Source

Applies f in ascending order to all mappings k => v in the tree rooted in node where min <= k <= max.

Not thread-safe: Traverses the live leaf chain in range order.

def rightMostLeaf(n: Node[k, v, r], stamp: Int64, t: BPlusTree[k, v, r]): (Node[k, v, r], Int64) \ r with Order[k] Source

Returns the rightmost leaf of the tree rooted at node together with an optimistic stamp on that leaf.

Traverses down the rightmost path of the tree, acquiring locks along the way. If a lock is invalid, yields and retries from the root of t.

def sameElementsFromLeaf(i1: Int32, n1: Node[k, v, r1], i2: Int32, n2: Node[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v] Source

Compares two leaf chains from left to right in lockstep.

The input nodes must be leaves.

Not thread-safe: Reads the live leaf chains of both inputs.

def size(node: Node[k, v, r]): Int32 \ r Source

Returns the size of node.

def toString(indent: Int32, rc: Region[r], node: Node[k, v, r]): String \ r with ToString[k], ToString[v] Source

Returns a string representation of the given Node node starting with indent spaces.

Not thread-safe: Traverses the live tree rooted at node.

def transformWithKeyFromLeaf(f: k -> (v -> v \ ef), i: Int32, n: Node[k, v, r]): Unit \ r + ef with Order[k] Source

Applies f to every mapping in the leaf chain that starts at n.

The input node must be a leaf.

Not thread-safe: Mutates the live leaf chain that starts at n.

def traverseRightUnconditional(f: k -> (v -> Unit \ ef), index: Int32, node: Node[k, v, r]): Unit \ ef + r Source

Apply f to all mappings in node and all nodes to the right of node.

Not thread-safe: Traverses the live leaf chain.

def traverseRightUnconditionalInc(f: k -> (v -> Unit \ ef), index: Int32, stepSize: Int32, node: Node[k, v, r]): Unit \ ef + r Source

Apply f to every stepSize mapping in node and continues in right of node.

Not thread-safe: Traverses the live leaf chain.

def traverseToLeaf(cur: Node[k, v, r], stamp: Int64, pickChild: Node[k, v, r] -> Node[k, v, r] \ r, restart: Unit -> (Node[k, v, r], Int64) \ r): (Node[k, v, r], Int64) \ r with Order[k] Source

Traverses down the tree according to pickChild, acquiring locks along the way. If a lock is invalid, yields and retries from the root using restart.

pickChild should pick a child of cur if cur is an internal node and is not called if cur is a leaf.

Caution: Because invalid locks trigger restart, pickChild and restart may be called an unknown number of times before traversal succeeds.

stamp should be an optimistic stamp on cur.

The returned stamp is an optimistic stamp on the returned leaf. Callers must still validate or upgrade it before relying on data read from that leaf.