Skip to content

Instantly share code, notes, and snippets.

@pervognsen
Last active September 19, 2022 04:04
Show Gist options
  • Save pervognsen/e7883b3de183fcd601c1edf7f7e9508b to your computer and use it in GitHub Desktop.
Save pervognsen/e7883b3de183fcd601c1edf7f7e9508b to your computer and use it in GitHub Desktop.
enum { BMAX = 32, BCUT = BMAX / 2, BHEIGHT = 6 };
typedef uint8_t BIndex;
struct BNode {
BIndex length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value values[BMAX];
};
};
struct BLeafNode {
BIndex length;
Key keys[BMAX];
union {
Value values[BMAX];
BNode *alignment_padding;
};
};
struct BInteriorNode {
BIndex length;
Key keys[BMAX];
union {
BNode *children[BMAX];
Value alignment_padding;
};
};
static BNode *BLeafNode_Create(BIndex length, Key *keys, Value *values) {
BNode *leaf = (BNode *)Allocate(sizeof(BLeafNode));
leaf->length = length;
CopyMemory(leaf->keys, keys, length * sizeof(Key));
CopyMemory(leaf->values, values, length * sizeof(Value));
return leaf;
}
static void BInteriorNode_Initialize(BNode *node, BIndex length, Key *keys, BNode **children) {
node->length = length;
CopyMemory(node->keys, keys, length * sizeof(Key));
CopyMemory(node->children, children, length * sizeof(BNode *));
}
static BNode *BInteriorNode_Create(BIndex length, Key *keys, BNode **children) {
BNode *node = (BNode *)Allocate(sizeof(BInteriorNode));
BInteriorNode_Initialize(node, length, keys, children);
return node;
}
static void BInteriorNode_Destroy(BNode *node, BIndex height) {
for (BIndex index = 0; index < node->length; index++) {
if (height > 1) {
BInteriorNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
}
}
static Key BNode_GetGreatestKey(BNode *node) {
Assert(node->length > 0);
return node->keys[node->length - 1];
}
static BNode *BLeafNode_Add(BNode *leaf, Key key, Value value) {
BIndex index = Array_Search(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
leaf->values[index] = value;
return 0;
}
BNode *new_sibling = 0;
if (leaf->length == BMAX) {
new_sibling = BLeafNode_Create(BMAX - BCUT, leaf->keys + BCUT, leaf->values + BCUT);
leaf->length = BCUT;
if (index >= BCUT) {
leaf = new_sibling;
index -= BCUT;
}
}
Array_Add(leaf->keys, leaf->length, index, key);
Array_Add(leaf->values, leaf->length, index, value);
leaf->length++;
return new_sibling;
}
static BNode *BInteriorNode_Add(BNode *node, Key key, Value value, BIndex height) {
Assert(height > 0);
Assert(node->length > 0);
BIndex index = Array_Search(node->keys, node->length, key);
if (index == node->length) {
index--;
node->keys[index] = key;
}
BNode *new_child;
if (height == 1) {
new_child = BLeafNode_Add(node->children[index], key, value);
} else {
new_child = BInteriorNode_Add(node->children[index], key, value, height - 1);
}
BNode *new_sibling = 0;
if (new_child) {
if (node->length == BMAX) {
new_sibling = BInteriorNode_Create(BMAX - BCUT, node->keys + BCUT, node->children + BCUT);
node->length = BCUT;
if (index >= BCUT) {
node = new_sibling;
index -= BCUT;
}
}
node->keys[index] = BNode_GetGreatestKey(node->children[index]);
Array_Add(node->keys, node->length, index + 1, BNode_GetGreatestKey(new_child));
Array_Add(node->children, node->length, index + 1, new_child);
node->length++;
}
return new_sibling;
}
static bool BLeafNode_Remove(BNode *leaf, Key key) {
BIndex index = Array_Search(leaf->keys, leaf->length, key);
if (index < leaf->length && leaf->keys[index] == key) {
Array_Remove(leaf->keys, leaf->length, index);
Array_Remove(leaf->values, leaf->length, index);
leaf->length--;
return leaf->length == 0;
}
return false;
}
static bool BInteriorNode_Remove(BNode *node, Key key, BIndex height) {
Assert(height > 0);
BIndex index = Array_Search(node->keys, node->length, key);
if (index == node->length) {
return false;
}
bool child_empty;
if (height == 1) {
child_empty = BLeafNode_Remove(node->children[index], key);
} else {
child_empty = BInteriorNode_Remove(node->children[index], key, height - 1);
}
if (child_empty) {
if (node->length == 1) {
return true;
} else {
if (height > 1) {
BInteriorNode_Destroy(node->children[index], height - 1);
}
Free(node->children[index]);
Array_Remove(node->keys, node->length, index);
Array_Remove(node->children, node->length, index);
node->length--;
}
}
return false;
}
struct BTree {
BIndex height;
BNode root;
};
void BTree_Initialize(BTree *tree) {
Assert(BMAX >= 4);
tree->height = 0;
tree->root.length = 0;
}
void BTree_Destroy(BTree *tree) {
if (tree->height > 0) {
BInteriorNode_Destroy(&tree->root, tree->height);
}
}
Value *BTree_Get(BTree *tree, Key key) {
BIndex height = tree->height;
BNode *node = &tree->root;
for (;;) {
BIndex index = Array_Search(node->keys, node->length, key);
if (index == node->length) {
return 0;
}
if (height == 0) {
return (node->keys[index] == key) ? (node->values + index) : 0;
}
height--;
node = node->children[index];
}
}
void BTree_Add(BTree *tree, Key key, Value value) {
BNode *root = &tree->root;
BNode *new_root_sibling;
if (tree->height == 0) {
new_root_sibling = BLeafNode_Add(root, key, value);
} else {
new_root_sibling = BInteriorNode_Add(root, key, value, tree->height);
}
if (new_root_sibling) {
Assert(tree->height != BHEIGHT);
BNode *old_root = BInteriorNode_Create(root->length, root->keys, root->children);
Key keys[2] = {BNode_GetGreatestKey(old_root), BNode_GetGreatestKey(new_root_sibling)};
BNode *children[2] = {old_root, new_root_sibling};
BInteriorNode_Initialize(root, 2, keys, children);
tree->height++;
}
}
void BTree_Remove(BTree *tree, Key key) {
if (tree->height == 0) {
BLeafNode_Remove(&tree->root, key);
} else {
if (BInteriorNode_Remove(&tree->root, key, tree->height)) {
BInteriorNode_Destroy(&tree->root, tree->height);
tree->height = 0;
tree->root.length = 0;
}
}
}
struct BPathNode {
BNode *node;
BIndex index;
};
struct BIterator {
Key *key;
Key *key_start;
Key *key_end;
Value *value;
Value *value_start;
Value *value_end;
BIndex height;
BPathNode path[BHEIGHT];
BPathNode *head;
};
static void BIterator_SetLeafIndex(BIterator *iterator, BIndex index) {
Assert(iterator->height == 0);
BIndex length = iterator->head->node->length;
Assert(index <= length);
iterator->key = iterator->head->node->keys + index;
iterator->key_start = iterator->head->node->keys;
iterator->key_end = iterator->head->node->keys + length;
iterator->value = iterator->head->node->values + index;
iterator->value_start = iterator->head->node->values;
iterator->value_end = iterator->head->node->values + length;
}
void BIterator_Copy(BIterator *iterator, BIterator *source) {
CopyMemory(iterator, source, sizeof(BIterator));
}
bool BIterator_Equals(BIterator *iterator1, BIterator *iterator2) {
return iterator1->key == iterator2->key;
}
bool BIterator_HasItem(BIterator *iterator) {
return iterator->key != iterator->key_end;
}
bool BIterator_HasPreviousItem(BIterator *iterator) {
return iterator->key != iterator->key_start;
}
void BIterator_FindStart(BIterator *iterator) {
while (iterator->height > 0) {
BPathNode *parent = iterator->head;
iterator->head++;
iterator->head->node = parent->node->children[parent->index];
iterator->head->index = 0;
iterator->height--;
}
BIterator_SetLeafIndex(iterator, 0);
}
void BIterator_FindEnd(BIterator *iterator) {
while (iterator->height > 0) {
BPathNode *parent = iterator->head;
parent->index = parent->node->length - 1;
iterator->head++;
iterator->head->node = parent->node->children[parent->index];
iterator->height--;
}
BIterator_SetLeafIndex(iterator, iterator->head->node->length);
}
void BIterator_FindPrevious(BIterator *iterator) {
while (iterator->head->index == 0) {
if (iterator->head == iterator->path) {
BIterator_FindStart(iterator);
return;
}
iterator->head--;
iterator->height++;
}
iterator->head->index--;
BNode *node = iterator->head->node->children[iterator->head->index];
iterator->head++;
iterator->head->node = node;
iterator->height--;
BIterator_FindEnd(iterator);
}
void BIterator_FindNext(BIterator *iterator) {
while (iterator->head->index == iterator->head->node->length) {
if (iterator->head == iterator->path) {
BIterator_FindEnd(iterator);
return;
}
iterator->head--;
iterator->head->index++;
iterator->height++;
}
BIterator_FindStart(iterator);
}
void BIterator_FindNextLeaf(BIterator *iterator) {
iterator->head->index = iterator->head->node->length;
BIterator_FindNext(iterator);
}
void BIterator_FindPreviousLeaf(BIterator *iterator) {
iterator->head->index = 0;
BIterator_FindPrevious(iterator);
}
void BIterator_FindNextItem(BIterator *iterator) {
iterator->key++;
iterator->value++;
if (!BIterator_HasItem(iterator)) {
BIterator_FindNextLeaf(iterator);
}
}
void BIterator_FindPreviousItem(BIterator *iterator) {
iterator->key--;
iterator->value--;
if (!BIterator_HasPreviousItem(iterator)) {
BIterator_FindPreviousLeaf(iterator);
}
}
void BIterator_FindEqualOrGreaterItem(BIterator *iterator, Key key) {
for (;;) {
BNode *node = iterator->head->node;
BIndex index = Array_Search(node->keys, node->length, key);
iterator->head->index = index;
if (index == node->length) {
BIterator_FindNext(iterator);
break;
}
if (iterator->height == 0) {
BIterator_SetLeafIndex(iterator, index);
break;
}
iterator->height--;
iterator->head++;
iterator->head->node = node->children[index];
}
Assert(!BIterator_HasItem(iterator) || key <= *iterator->key);
}
void BIterator_SetToRoot(BIterator *iterator, BTree *tree) {
iterator->head = iterator->path;
iterator->head->node = &tree->root;
iterator->head->index = 0;
iterator->height = tree->height;
}
void BTree_FindEnd(BTree *tree, BIterator *iterator) {
BIterator_SetToRoot(iterator, tree);
BIterator_FindEnd(iterator);
}
void BTree_FindStart(BTree *tree, BIterator *iterator) {
BIterator_SetToRoot(iterator, tree);
BIterator_FindStart(iterator);
}
void BTree_FindEqualOrGreaterItem(BTree *tree, BIterator *iterator, Key key) {
BIterator_SetToRoot(iterator, tree);
BIterator_FindEqualOrGreaterItem(iterator, key);
}
void BTree_FindItemsInRange(BTree *tree, BIterator *iterator_start, BIterator *iterator_end, Key key_start, Key key_end) {
BTree_FindEqualOrGreaterItem(tree, iterator_start, key_start);
if (key_start < key_end) {
BTree_FindEqualOrGreaterItem(tree, iterator_end, key_end);
} else {
BIterator_Copy(iterator_end, iterator_start);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment