flix

0.67.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, the thread has a lock on node.
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 computeHeight(node: Node[k, v, r]): Int32 \ r Source

Compute the height of the tree rooted in node.

Not thread-safe.

def exists(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 node or to the right of node satisfying f.

Not thread-safe.

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

Optionally returns the first mapping satisfying the function f in node and to the right of node.

Not thread-safe.

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.

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 leftMostChild(node: Node[k, v, r]): Node[k, v, r] \ r Source

Returns the left-most leaf node rooted in node.

Not thread-safe.

def minimumKey(t: Node[k, v, r]): Option[(k, v)] \ r Source

Optionally returns k => v where k is the minimum key.

Not thread-safe.

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

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.

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

Traverse down through the tree while keeping the invariant that there is a lock on cur. If acquiring a lock at any point fails release the locks you hold and retry from the root.

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.

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.