BTreeMapImplementation

Internal (non-user facing) implementation of BTreeMap.

package

struct BTreeMapImplementation (

KeyType

ValueType

int tree_degree

) {

import ocean.core.array.Mutation;;

import ocean.core.array.Search;;

import ocean.core.Enforce;;

import ocean.meta.types.Function;;

import ocean.core.Verify;;

import ocean.util.container.mem.MemManager;;

struct BTreeMapNode;

BTreeMapNode* root;

IMemManager allocator;

ulong content_version;

void initialize(IMemManager allocator);

ValueType* insert(KeyType key, ValueType el, bool added);

bool remove(KeyType key);

bool empty();

ValueType get(KeyType key, bool found_element);

ValueType* get(KeyType key);

int inorder(int delegate(ref KeyType key, ref ValueType value) dg);

int inorder(int delegate(ref ValueType value) dg);

}

Members

Functions

empty bool empty()
get ValueType get(KeyType key, bool found_element): Searches the tree for the element with the given key and returns its value if found.
get ValueType* get(KeyType key): Searches the tree for the element with the given key and returns pointer to it's value, or null if not found.
initialize void initialize(IMemManager allocator): Constructor-like method (as a workaround of a fact that D1 doesn't provide struct constructors).
inorder int inorder(int delegate(ref KeyType key, ref ValueType value) dg): Visits the tree in the inorder order.
inorder int inorder(int delegate(ref ValueType value) dg): Visits the tree in the inorder order.
insert ValueType* insert(KeyType key, ValueType el, bool added): Inserts the element in the tree.
remove bool remove(KeyType key): Removes the element with the given key from the BTreeMap.

Structs

BTreeMapNode struct BTreeMapNode: Node of the tree. Contains at most (degree * 2 - 1) elements and (degree * 2) subtrees.

Variables

allocator IMemManager allocator;: Memory manager used for allocating and deallocating memory. Refer to ocean.util.container.mem.MemManager for potential options.
content_version ulong content_version;: "version" of the tree's state. Will be incremented on any removal/adding the element. On the iteration's start, range will record the current "version" of the tree, and, and before proceeding with the iteration, it will check if any changes were performed on the tree, to prevent iteration over an undefined region.
root BTreeMapNode* root;: Root of the tree.

Parameters

KeyType: type of the key
ValueType: type of the value
tree_degree: degree of the tree.

Meta

Source

See Implementation

ocean util container btree Implementation functions

check_invariants

structs

BTreeMapImplementation