flix

0.78.0
Prelude / BPlusTree

BPlusTree

struct BPlusTree[k: Type, v: Type, r: Eff]Source
mut root: Node[k, v, r]arity: Int32rootLock: Lock[r]rc: Region[r]counter: AtomicCounter[r]search: Search

Type of mutable concurrent B+ trees.

The tree maps keys of type k to values of type v.

A B+ Tree is an m-ary self-balancing search tree where each node is either an internal node or a leaf node. In contrast to binary search trees, a B+ Tree of arity m only allows nodes with at most m children and m-1 keys. A B+ Tree stores its keys in a sorted order in its internal nodes, which are used to guide searches to leaf nodes that store the keys' corresponding values.

See below for more details:

  • The Ubiquitous B-Tree (1979) by Douglas Comer (https://dl.acm.org/doi/10.1145/356770.356776)

A BPlusTree satisfies the following.

root is the root node of the tree, which upon creation of the tree is a leaf node. Through insertion into the tree, a new node may be created and propagated up to become the new root of the tree.

arity or m is the arity of the tree which determines the maximum number of children a node may have. The arity must be at least 3.

rootLock is a lock on the root pointer, which a thread must first acquire before accessing the root node. It must also be acquired before changing root. The node root has a separate lock concerning the contents of the node. The lock of root must first be acquired after successfully acquiring rootLock.

rc is the region for the tree.

search is only used internally within the Fixpoint module where keys are of type Vector[Int64]. A search describes the order in which elements should be compared. E.g. [0, 1, 2, ..., n] is the natural order. A search may only be used when using Vector[Int64] as keys.

counter is used for keeping track of the number of inserted elements.

For all other usages search will be a vector of size 0.

Concurrency: thread-safe operations use optimistic stamps and validation. Functions marked "Not thread-safe" traverse or mutate the live tree without a stable snapshot, so concurrent writes may affect the observed result.

Type of mutable concurrent B+ trees, and its functions.

Instances

instance ForEach[BPlusTree[k, v, r]]Source
type Elm = (k, v)type Aef = r

Type Aliases

Definitions

def adjust(f: v -> v \ ef, k: k, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k]§ Source

Updates t with k => f(v) if k => v is in t.

Otherwise, t is unchanged.

Thread-safe.

def adjustWithKey(f: k -> (v -> v \ ef), k: k, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k]§ Source

Updates t with k => f(k, v) if k => v is in t.

Otherwise, t is unchanged.

Thread-safe.

def arity(t: BPlusTree[k, v, r]): Int32§ Source

Returns the arity of t.

def assertTreeInvariant(t: BPlusTree[k, v, r]): Bool \ r with Order[k]§ Source

Returns true if and only if t is a structurally correct tree.

Only used for internal testing.

def computeIfAbsent(f: Unit -> v \ ef, k: k, t: BPlusTree[k, v, r]): v \ ef + r with Order[k]§ Source

Returns v if k => v is in t. Otherwise, computes v = f(), inserts k => v and returns v. That is, f is only evaluated if k is not in t.

This operation is atomic.

Thread-safe.

@Parallel
def count(f: k -> (v -> Bool), t: BPlusTree[k, v, r]): Int32 \ r with Order[k]§ Source

Returns the number of mappings in t that satisfy the predicate function f.

This method unsafely removes the effect r when spawning threads.

Not thread-safe: Traverses the live leaf chain of t in parallel.

def empty(rc: Region[r]): BPlusTree[k, v, r] \ r§ Source

Returns a fresh empty BPlusTree tree of standard arity.

def emptyWithArity(rc: Region[r], m: Int32): BPlusTree[k, v, r] \ r§ Source

Returns a fresh empty BPlusTree with arity m. A node may have at most m children and m - 1 keys. The arity must be at least 3.

def emptyWithArityAndSearch(rc: Region[r], m: Int32, search: Search): BPlusTree[k, v, r] \ r§ Source

Returns a fresh empty BPlusTree with arity m. A node may have at most m children and m - 1 keys. The arity must be at least 3.

search decides the comparison order for the stored vectors.

def emptyWithSearch(rc: Region[r], search: Search): BPlusTree[k, v, r] \ r§ Source

Returns a fresh empty BPlusTree of standard arity.

search decided the comparison order for the stored vectors.

def exists(f: k -> (v -> Bool \ ef), t: BPlusTree[k, v, r]): Bool \ ef + r§ Source

Returns true if and only if there exists k => v in t such that f(k, v) == true.

Not thread-safe: Traverses the live leaf chain of t.

def find(f: k -> (v -> Bool \ ef), t: BPlusTree[k, v, r]): Option[(k, v)] \ ef + r§ Source

Alias for findLeft.

Not thread-safe: Traverses the live leaf chain of t.

def findLeft(f: k -> (v -> Bool \ ef), t: BPlusTree[k, v, r]): Option[(k, v)] \ ef + r§ Source

Optionally returns the first mapping in t satisfying the function f.

Not thread-safe: Traverses the live leaf chain of t.

def foldLeft(f: b -> (v -> b \ ef), i: b, t: BPlusTree[k, v, r]): b \ ef + r with Order[k]§ Source

Applies f to a start value i and all values in t going from left to right.

Not thread-safe: Traverses the live leaf chain of t.

def foldLeftWithKey(f: b -> (k -> (v -> b \ ef)), i: b, t: BPlusTree[k, v, r]): b \ ef + r with Order[k]§ Source

Applies f to a start value i and all mappings k => v in t going from left to right.

Not thread-safe: Traverses the live leaf chain of t.

def foldWithKey(f: b -> (k -> (v -> b \ ef)), i: b, t: BPlusTree[k, v, r]): b \ r + ef with Order[k]§ Source

Alias for foldLeftWithKey

def forAll(f: k -> (v -> Bool \ ef), t: BPlusTree[k, v, r]): Bool \ ef + r§ Source

Returns true if and only if for all k => v in t, f(k, v) == true.

Not thread-safe: Traverses the live leaf chain of t.

def forEach(f: k -> (v -> Unit \ ef), t: BPlusTree[k, v, r]): Unit \ ef + r§ Source

Applies f to all mappings k => v in t.

Not thread-safe: Traverses the live leaf chain of t.

def forEachWithIndex(f: Int32 -> (k -> (v -> Unit \ ef)), t: BPlusTree[k, v, r]): Unit \ ef + r§ Source

Applies f to all mappings k => v in t, passing an index as the first argument.

Not thread-safe: Traverses the live leaf chain of t.

def get(k: k, t: BPlusTree[k, v, r]): Option[v] \ r with Order[k]§ Source

Returns Some(v) if k => v is in t. Otherwise, returns None.

Thread-safe.

def getKeyAndValue(k: k, t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k]§ Source

Returns Some((k, v)) if k => v is in t. Otherwise, returns None.

Thread-safe.

def getOrAbort(k: k, t: BPlusTree[k, v, r]): v \ Abort + r with Order[k]§ Source

Returns v if k => v is in t. Aborts with a trace message if k is not in t.

Thread-safe.

def getOrElsePut(k: k, d: v, t: BPlusTree[k, v, r]): v \ r with Order[k]§ Source

Returns v if k => v is in t.

Otherwise updates t with a new mapping k => d and returns d.

Atomic and thread-safe

def getWithDefault(k: k, d: v, t: BPlusTree[k, v, r]): v \ r with Order[k]§ Source

Returns v if k => v is in t. Otherwise, returns d.

Thread-safe.

def isEmpty(t: BPlusTree[k, v, r]): Bool \ r§ Source

Returns true if and only if t is the empty tree.

Thread-safe.

def isProperSubmapOf(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v]§ Source

Returns true if t1 is a proper submap of t2, i.e. t1 is a submap of t2 and there exists a key in t2 that is not in t1.

Not thread-safe: Traverses the live leaf chains of t1 and t2.

def isSubmapOf(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v]§ Source

Returns true if t1 is a submap of t2, i.e. for every key in t1, t2 contains the same key with the same value.

Not thread-safe: Traverses the live leaf chains of t1 and t2.

def iterator(rc1: Region[r1], t: BPlusTree[k, v, r]): Iterator[(k, v), r + r1, r1] \ r + r1§ Source

Returns an iterator over all key-value pairs in t,

Not thread-safe: The iterator reads from the live leaf chain of t.

def iteratorValues(rc1: Region[r1], t: BPlusTree[k, v, r2]): Iterator[v, r1 + r2, r1] \ r1 + r2§ Source

Returns an iterator over values in t.

Not thread-safe: The iterator reads from the live leaf chain of t.

def iteratorWithKeys(rc1: Region[r1], t: BPlusTree[k, v, r2]): Iterator[k, r1 + r2, r1] \ r1 + r2§ Source

Returns an iterator over keys in t.

Not thread-safe: The iterator reads from the live leaf chain of t.

def joinKeys(sep: String, t: BPlusTree[k, v, r]): String \ r with ToString[k]§ Source

Returns a string containing all keys in t, in key order, with each key formatted by its ToString instance and separated by sep.

Not thread-safe.

Builds the result by traversing the live leaf chain of t.

def joinValues(sep: String, t: BPlusTree[k, v, r]): String \ r with ToString[v]§ Source

Returns a string containing all values in t, in key order, with each value formatted by its ToString instance and separated by sep.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def joinWith(f: k -> (v -> String \ ef), sep: String, t: BPlusTree[k, v, r]): String \ r + ef§ Source

Applies f to each key-value pair in t, in key order, to obtain a string and returns all results joined together using sep.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def keysOf(t: BPlusTree[k, v, r]): Set[k] \ r with Order[k]§ Source

Returns the set of keys in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def map(rc1: Region[r1], f: v1 -> v2 \ ef, t: BPlusTree[k, v1, r]): BPlusTree[k, v2, r1] \ ef + r + r1 with Order[k]§ Source

Returns a BPlusTree with mappings k => f(v) for every k => v in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def mapWithKey(rc1: Region[r1], f: k -> (v1 -> v2 \ ef), t: BPlusTree[k, v1, r]): BPlusTree[k, v2, r1] \ ef + r + r1 with Order[k]§ Source

Returns a BPlusTree with mappings k => f(k, v) for every k => v in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def maximumKey(t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k]§ Source

Optionally returns k => v where k is the largest key in t according to the Order instance on k.

Returns None if t is empty.

Thread-safe.

def memberOf(k: k, t: BPlusTree[k, v, r]): Bool \ r with Order[k]§ Source

Returns true if and only if t contains the key k.

Thread-safe.

def memberOfPair(k: k, v: v, t: BPlusTree[k, v, r]): Bool \ r with Order[k], Eq[v]§ Source

Returns true if and only if t contains the mapping k => v.

Thread-safe.

def merge(src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 with Order[k]§ Source

Merge src into dst, modifying dst in a left-biased manner.

That is, key collisions are resolved by taking the mapping from src.

Not thread-safe: Traverses the live leaf chain of src.

def mergeWith(f: v -> (v -> v \ ef), src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 + ef with Order[k]§ Source

Merges src into dst, modifying dst. If k => v1 is in src and k => v2 is in dst, updates dst with k => f(v1, v2).

Not thread-safe: Traverses the live leaf chain of src.

def mergeWithKey(f: k -> (v -> (v -> v \ ef)), src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 + ef with Order[k]§ Source

Merges src into dst, modifying dst in-place. If k => v1 is in src and k => v2 is in dst, then dst is updated with k => f(k, v1, v2).

Not thread-safe: Traverses the live leaf chain of src.

def minimumKey(t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k]§ Source

Optionally returns k => v where k is the smallest key in t according to the Order instance on k.

Returns None if t is empty.

Thread-safe.

def nonEmpty(t: BPlusTree[k, v, r]): Bool \ r§ Source

Returns true if and only if t contains at least one mapping.

Thread-safe.

@Parallel
def parForEach(f: k -> (v -> Unit \ r), t: BPlusTree[k, v, r]): Unit \ r§ Source

Applies f to all mappings k => v in t in parallel. f must not modify t.

This method unsafe removes the r effect when spawning threads.

Not thread-safe: Traverses the live leaf chain of t in parallel.

@Parallel
def parForEachWhen(f1: k -> (v -> Unit \ r), f2: k -> (v -> Unit \ r), parLimit: Int32, t: BPlusTree[k, v, r]): Unit \ r§ Source

Applies f1 to all mappings k => v in t sequentially if t contains strictly less than parLimit elements. If t contains parLimit or more elements f2 is applied in parallel to all mappings.

f1 and f2 must not modify t.

This method unsafe removes the r effect when spawning threads in case 2.

Not thread-safe: Traverses the live leaf chain of t, potentially in parallel.

def put(k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r with Order[k]§ Source

Updates the tree t with the mapping k => v, replacing any existing mapping.

Thread-safe.

def putAll(kvs: f[(k, v)], t: BPlusTree[k, v, r]): Unit \ r + Aef[f] with Order[k], Foldable[f]§ Source

Updates the tree t with all mappings k => v in kvs, replacing any existing mappings.

Thread-safe.

def putIf(decider: k -> (v -> (k -> (v -> Bool))), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r with Order[k]§ Source

Updates the tree t with the mapping k => v, replacing any existing mapping, k2 => v2, if decider(k, v, k2, v2) == true.

Thread-safe and atomic.

def putWith(f: v -> (v -> v \ ef), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k]§ Source

Updates t with k => f(v, v1) if k => v1 is in t.

Otherwise, updates t with k => v.

Thread-safe.

def putWithKey(f: k -> (v -> (v -> v \ ef)), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k]§ Source

Updates t with the mapping k => f(k, v, v1) if k => v1 is in t.

Otherwise, updates t with the mapping k => v.

Thread-safe.

def rangeQuery(min: k, max: k, t: BPlusTree[k, v, r]): List[(k, v)] \ r with Order[k]§ Source

Returns the list of mappings k => v in t where min <= k <= max according to the Order instance on k.

Not thread-safe: Builds the result by traversing the live leaf chain of t in range order.

def rangeQueryWith(f: k -> (v -> Unit \ ef), min: k, max: k, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k]§ Source

Applies f in ascending order to all mappings k => v in t where min <= k <= max.

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

def rc(t: BPlusTree[k, v, r]): Region[r]§ Source

Returns the region of t.

def sameElements(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v]§ Source

Returns true if t1 and t2 contain the same keys and values, regardless of each individual tree's internal structure.

Not thread-safe: Compares the live leaf chains of t1 and t2.

def size(t: BPlusTree[k, v, r]): Int32 \ r§ Source

Returns the size of t. This operation is O(1).

Not atomic.

Thread-safe.

def toList(t: BPlusTree[k, v, r]): List[(k, v)] \ r§ Source

Returns a list of the key-value pairs in t. Elements are ordered from smallest (left) to largest (right).

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toMap(t: BPlusTree[k, v, r]): Map[k, v] \ r with Order[k]§ Source

Returns t as an immutable map.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toSet(t: BPlusTree[k, v, r]): Set[(k, v)] \ r with Order[k], Order[v]§ Source

Returns t as a set of key-value pairs.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toString(t: BPlusTree[k, v, r]): String \ r with ToString[k], ToString[v]§ Source

Returns a string representation of t.

Not thread-safe: Traverses the live tree without synchronization.

def toVector(t: BPlusTree[k, v, r]): Vector[(k, v)] \ r§ Source

Returns t as a vector of key-value pairs.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def transform(f: v -> v \ ef, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k]§ Source

Applies the function f to every value in t.

Not thread-safe: Mutates the live leaf chain of t in place.

def transformWithKey(f: k -> (v -> v \ ef), t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k]§ Source

Applies the function f to every mapping k => v in t, replacing it with k => f(k, v).

Not thread-safe: Mutates the live leaf chain of t in place.

def valuesOf(t: BPlusTree[k, v, r]): List[v] \ r with Order[k]§ Source

Returns the list of values in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.