cannam@226: /*
cannam@226:   Copyright 2011-2014 David Robillard <http://drobilla.net>
cannam@226: 
cannam@226:   Permission to use, copy, modify, and/or distribute this software for any
cannam@226:   purpose with or without fee is hereby granted, provided that the above
cannam@226:   copyright notice and this permission notice appear in all copies.
cannam@226: 
cannam@226:   THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
cannam@226:   WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
cannam@226:   MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
cannam@226:   ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
cannam@226:   WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
cannam@226:   ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
cannam@226:   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
cannam@226: */
cannam@226: 
cannam@226: #include <assert.h>
cannam@226: #include <stdint.h>
cannam@226: #include <stdio.h>
cannam@226: #include <stdlib.h>
cannam@226: #include <string.h>
cannam@226: 
cannam@245: #include "btree.h"
cannam@226: 
cannam@226: // #define ZIX_BTREE_DEBUG 1
cannam@226: 
cannam@226: #define ZIX_BTREE_PAGE_SIZE  4096
cannam@226: #define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))
cannam@226: #define ZIX_BTREE_LEAF_VALS  ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)
cannam@226: #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
cannam@226: 
cannam@226: struct ZixBTreeImpl {
cannam@226: 	ZixBTreeNode*  root;
cannam@226: 	ZixDestroyFunc destroy;
cannam@226: 	ZixComparator  cmp;
cannam@226: 	void*          cmp_data;
cannam@226: 	size_t         size;
cannam@226: 	unsigned       height;  ///< Number of levels, i.e. root only has height 1
cannam@226: };
cannam@226: 
cannam@226: struct ZixBTreeNodeImpl {
cannam@226: 	uint16_t      is_leaf;
cannam@226: 	uint16_t      n_vals;
cannam@226: 	// On 64-bit we rely on some padding here to get page-sized nodes
cannam@226: 	void*         vals[ZIX_BTREE_INODE_VALS];  // ZIX_BTREE_LEAF_VALS for leaves
cannam@226: 	ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1];  // Nonexistent for leaves
cannam@226: };
cannam@226: 
cannam@226: typedef struct {
cannam@226: 	ZixBTreeNode* node;
cannam@226: 	unsigned      index;
cannam@226: } ZixBTreeIterFrame;
cannam@226: 
cannam@226: struct ZixBTreeIterImpl {
cannam@226: 	unsigned          level;    ///< Current level in stack
cannam@226: 	ZixBTreeIterFrame stack[];  ///< Position stack
cannam@226: };
cannam@226: 
cannam@226: #ifdef ZIX_BTREE_DEBUG
cannam@226: 
cannam@226: ZIX_PRIVATE void
cannam@226: print_node(const ZixBTreeNode* n, const char* prefix)
cannam@226: {
cannam@226: 	printf("%s[", prefix);
cannam@226: 	for (uint16_t v = 0; v < n->n_vals; ++v) {
cannam@226: 		printf(" %lu", (uintptr_t)n->vals[v]);
cannam@226: 	}
cannam@226: 	printf(" ]\n");
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE void
cannam@226: print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
cannam@226: {
cannam@226: 	if (node) {
cannam@226: 		if (!parent) {
cannam@226: 			printf("TREE {\n");
cannam@226: 		}
cannam@226: 		for (int i = 0; i < level + 1; ++i) {
cannam@226: 			printf("  ");
cannam@226: 		}
cannam@226: 		print_node(node, "");
cannam@226: 		if (!node->is_leaf) {
cannam@226: 			for (uint16_t i = 0; i < node->n_vals + 1; ++i) {
cannam@226: 				print_tree(node, node->children[i], level + 1);
cannam@226: 			}
cannam@226: 		}
cannam@226: 		if (!parent) {
cannam@226: 			printf("}\n");
cannam@226: 		}
cannam@226: 	}
cannam@226: }
cannam@226: 
cannam@226: #endif  // ZIX_BTREE_DEBUG
cannam@226: 
cannam@226: ZIX_PRIVATE ZixBTreeNode*
cannam@226: zix_btree_node_new(const bool leaf)
cannam@226: {
cannam@226: 	assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
cannam@226: 	ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
cannam@226: 	if (node) {
cannam@226: 		node->is_leaf = leaf;
cannam@226: 		node->n_vals  = 0;
cannam@226: 	}
cannam@226: 	return node;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixBTree*
cannam@226: zix_btree_new(const ZixComparator  cmp,
cannam@226:               void* const          cmp_data,
cannam@226:               const ZixDestroyFunc destroy)
cannam@226: {
cannam@226: 	ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
cannam@226: 	if (t) {
cannam@226: 		t->root     = zix_btree_node_new(true);
cannam@226: 		t->destroy  = destroy;
cannam@226: 		t->cmp      = cmp;
cannam@226: 		t->cmp_data = cmp_data;
cannam@226: 		t->size     = 0;
cannam@226: 		t->height   = 1;
cannam@226: 		if (!t->root) {
cannam@226: 			free(t);
cannam@226: 			return NULL;
cannam@226: 		}
cannam@226: 	}
cannam@226: 	return t;
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE void
cannam@226: zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
cannam@226: {
cannam@226: 	if (n) {
cannam@226: 		if (t->destroy) {
cannam@226: 			for (uint16_t i = 0; i < n->n_vals; ++i) {
cannam@226: 				t->destroy(n->vals[i]);
cannam@226: 			}
cannam@226: 		}
cannam@226: 		if (!n->is_leaf) {
cannam@226: 			for (uint16_t i = 0; i < n->n_vals + 1; ++i) {
cannam@226: 				zix_btree_free_rec(t, n->children[i]);
cannam@226: 			}
cannam@226: 		}
cannam@226: 		free(n);
cannam@226: 	}
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void
cannam@226: zix_btree_free(ZixBTree* const t)
cannam@226: {
cannam@226: 	if (t) {
cannam@226: 		zix_btree_free_rec(t, t->root);
cannam@226: 		free(t);
cannam@226: 	}
cannam@226: }
cannam@226: 
cannam@226: ZIX_API size_t
cannam@226: zix_btree_size(const ZixBTree* const t)
cannam@226: {
cannam@226: 	return t->size;
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE uint16_t
cannam@226: zix_btree_max_vals(const ZixBTreeNode* const node)
cannam@226: {
cannam@226: 	return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE uint16_t
cannam@226: zix_btree_min_vals(const ZixBTreeNode* const node)
cannam@226: {
cannam@226: 	return ((zix_btree_max_vals(node) + 1) / 2) - 1;
cannam@226: }
cannam@226: 
cannam@226: /** Shift pointers in `array` of length `n` right starting at `i`. */
cannam@226: ZIX_PRIVATE void
cannam@226: zix_btree_ainsert(void** const   array,
cannam@226:                   const uint16_t n,
cannam@226:                   const uint16_t i,
cannam@226:                   void* const    e)
cannam@226: {
cannam@226: 	memmove(array + i + 1, array + i, (n - i) * sizeof(e));
cannam@226: 	array[i] = e;
cannam@226: }
cannam@226: 
cannam@226: /** Erase element `i` in `array` of length `n` and return erased element. */
cannam@226: ZIX_PRIVATE void*
cannam@226: zix_btree_aerase(void** const array, const uint16_t n, const uint16_t i)
cannam@226: {
cannam@226: 	void* const ret = array[i];
cannam@226: 	memmove(array + i, array + i + 1, (n - i) * sizeof(ret));
cannam@226: 	return ret;
cannam@226: }
cannam@226: 
cannam@226: /** Split lhs, the i'th child of `n`, into two nodes. */
cannam@226: ZIX_PRIVATE ZixBTreeNode*
cannam@226: zix_btree_split_child(ZixBTreeNode* const n,
cannam@226:                       const uint16_t      i,
cannam@226:                       ZixBTreeNode* const lhs)
cannam@226: {
cannam@226: 	assert(lhs->n_vals == zix_btree_max_vals(lhs));
cannam@226: 	assert(n->n_vals < ZIX_BTREE_INODE_VALS);
cannam@226: 	assert(i < n->n_vals + 1);
cannam@226: 	assert(n->children[i] == lhs);
cannam@226: 
cannam@226: 	const uint16_t max_n_vals = zix_btree_max_vals(lhs);
cannam@226: 	ZixBTreeNode*  rhs        = zix_btree_node_new(lhs->is_leaf);
cannam@226: 	if (!rhs) {
cannam@226: 		return NULL;
cannam@226: 	}
cannam@226: 
cannam@226: 	// LHS and RHS get roughly half, less the middle value which moves up
cannam@226: 	lhs->n_vals = max_n_vals / 2;
cannam@226: 	rhs->n_vals = max_n_vals - lhs->n_vals - 1;
cannam@226: 
cannam@226: 	// Copy large half of values from LHS to new RHS node
cannam@226: 	memcpy(rhs->vals,
cannam@226: 	       lhs->vals + lhs->n_vals + 1,
cannam@226: 	       rhs->n_vals * sizeof(void*));
cannam@226: 
cannam@226: 	// Copy large half of children from LHS to new RHS node
cannam@226: 	if (!lhs->is_leaf) {
cannam@226: 		memcpy(rhs->children,
cannam@226: 		       lhs->children + lhs->n_vals + 1,
cannam@226: 		       (rhs->n_vals + 1) * sizeof(ZixBTreeNode*));
cannam@226: 	}
cannam@226: 
cannam@226: 	// Move middle value up to parent
cannam@226: 	zix_btree_ainsert(n->vals, n->n_vals, i, lhs->vals[lhs->n_vals]);
cannam@226: 
cannam@226: 	// Insert new RHS node in parent at position i
cannam@226: 	zix_btree_ainsert((void**)n->children, ++n->n_vals, i + 1, rhs);
cannam@226: 
cannam@226: 	return rhs;
cannam@226: }
cannam@226: 
cannam@226: /** Find the first value in `n` that is not less than `e` (lower bound). */
cannam@226: ZIX_PRIVATE uint16_t
cannam@226: zix_btree_node_find(const ZixBTree* const     t,
cannam@226:                     const ZixBTreeNode* const n,
cannam@226:                     const void* const         e,
cannam@226:                     bool* const               equal)
cannam@226: {
cannam@226: 	uint16_t first = 0;
cannam@226: 	uint16_t len   = n->n_vals;
cannam@226: 	while (len > 0) {
cannam@226: 		const uint16_t half = len >> 1;
cannam@226: 		const uint16_t i    = first + half;
cannam@226: 		const int      cmp  = t->cmp(n->vals[i], e, t->cmp_data);
cannam@226: 		if (cmp == 0) {
cannam@226: 			*equal = true;
cannam@226: 			len    = half;  // Keep searching for wildcard matches
cannam@226: 		} else if (cmp < 0) {
cannam@226: 			const uint16_t chop = half + 1;
cannam@226: 			first += chop;
cannam@226: 			len   -= chop;
cannam@226: 		} else {
cannam@226: 			len = half;
cannam@226: 		}
cannam@226: 	}
cannam@226: 	assert(!*equal || t->cmp(n->vals[first], e, t->cmp_data) == 0);
cannam@226: 	return first;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_insert(ZixBTree* const t, void* const e)
cannam@226: {
cannam@226: 	ZixBTreeNode* parent = NULL;     // Parent of n
cannam@226: 	ZixBTreeNode* n      = t->root;  // Current node
cannam@226: 	uint16_t      i      = 0;        // Index of n in parent
cannam@226: 	while (n) {
cannam@226: 		if (n->n_vals == zix_btree_max_vals(n)) {
cannam@226: 			// Node is full, split to ensure there is space for a leaf split
cannam@226: 			if (!parent) {
cannam@226: 				// Root is full, grow tree upwards
cannam@226: 				if (!(parent = zix_btree_node_new(false))) {
cannam@226: 					return ZIX_STATUS_NO_MEM;
cannam@226: 				}
cannam@226: 				t->root             = parent;
cannam@226: 				parent->children[0] = n;
cannam@226: 				++t->height;
cannam@226: 			}
cannam@226: 
cannam@226: 			ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
cannam@226: 			if (!rhs) {
cannam@226: 				return ZIX_STATUS_NO_MEM;
cannam@226: 			}
cannam@226: 
cannam@226: 			const int cmp = t->cmp(parent->vals[i], e, t->cmp_data);
cannam@226: 			if (cmp == 0) {
cannam@226: 				return ZIX_STATUS_EXISTS;
cannam@226: 			} else if (cmp < 0) {
cannam@226: 				// Move to new RHS
cannam@226: 				n = rhs;
cannam@226: 				++i;
cannam@226: 			}
cannam@226: 		}
cannam@226: 
cannam@226: 		assert(!parent || parent->children[i] == n);
cannam@226: 
cannam@226: 		bool equal = false;
cannam@226: 		i          = zix_btree_node_find(t, n, e, &equal);
cannam@226: 		if (equal) {
cannam@226: 			return ZIX_STATUS_EXISTS;
cannam@226: 		} else if (!n->is_leaf) {
cannam@226: 			// Descend to child node left of value
cannam@226: 			parent = n;
cannam@226: 			n      = n->children[i];
cannam@226: 		} else {
cannam@226: 			// Insert into internal node
cannam@226: 			zix_btree_ainsert(n->vals, n->n_vals++, i, e);
cannam@226: 			break;
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	++t->size;
cannam@226: 
cannam@226: 	return ZIX_STATUS_SUCCESS;
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE ZixBTreeIter*
cannam@226: zix_btree_iter_new(const ZixBTree* const t)
cannam@226: {
cannam@226: 	const size_t        s = t->height * sizeof(ZixBTreeIterFrame);
cannam@226: 	ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
cannam@226: 	if (i) {
cannam@226: 		i->level = 0;
cannam@226: 	}
cannam@226: 	return i;
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE void
cannam@226: zix_btree_iter_set_frame(ZixBTreeIter* const ti,
cannam@226:                          ZixBTreeNode* const n,
cannam@226:                          const uint16_t      i)
cannam@226: {
cannam@226: 	if (ti) {
cannam@226: 		ti->stack[ti->level].node  = n;
cannam@226: 		ti->stack[ti->level].index = i;
cannam@226: 	}
cannam@226: }
cannam@226: 
cannam@226: ZIX_PRIVATE bool
cannam@226: zix_btree_node_is_minimal(ZixBTreeNode* const n)
cannam@226: {
cannam@226: 	assert(n->n_vals >= zix_btree_min_vals(n));
cannam@226: 	return n->n_vals == zix_btree_min_vals(n);
cannam@226: }
cannam@226: 
cannam@226: /** Enlarge left child by stealing a value from its right sibling. */
cannam@226: ZIX_PRIVATE ZixBTreeNode*
cannam@226: zix_btree_rotate_left(ZixBTreeNode* const parent, const uint16_t i)
cannam@226: {
cannam@226: 	ZixBTreeNode* const lhs = parent->children[i];
cannam@226: 	ZixBTreeNode* const rhs = parent->children[i + 1];
cannam@226: 
cannam@226: 	// Move parent value to end of LHS
cannam@226: 	lhs->vals[lhs->n_vals++] = parent->vals[i];
cannam@226: 
cannam@226: 	// Move first child pointer from RHS to end of LHS
cannam@226: 	if (!lhs->is_leaf) {
cannam@226: 		lhs->children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase(
cannam@226: 			(void**)rhs->children, rhs->n_vals, 0);
cannam@226: 	}
cannam@226: 
cannam@226: 	// Move first value in RHS to parent
cannam@226: 	parent->vals[i] = zix_btree_aerase(rhs->vals, --rhs->n_vals, 0);
cannam@226: 
cannam@226: 	return lhs;
cannam@226: }
cannam@226: 
cannam@226: /** Enlarge right child by stealing a value from its left sibling. */
cannam@226: ZIX_PRIVATE ZixBTreeNode*
cannam@226: zix_btree_rotate_right(ZixBTreeNode* const parent, const uint16_t i)
cannam@226: {
cannam@226: 	ZixBTreeNode* const lhs = parent->children[i - 1];
cannam@226: 	ZixBTreeNode* const rhs = parent->children[i];
cannam@226: 
cannam@226: 	// Prepend parent value to RHS
cannam@226: 	zix_btree_ainsert(rhs->vals, rhs->n_vals++, 0, parent->vals[i - 1]);
cannam@226: 
cannam@226: 	// Move last child pointer from LHS and prepend to RHS
cannam@226: 	if (!lhs->is_leaf) {
cannam@226: 		zix_btree_ainsert((void**)rhs->children,
cannam@226: 		                  rhs->n_vals,
cannam@226: 		                  0,
cannam@226: 		                  lhs->children[lhs->n_vals]);
cannam@226: 	}
cannam@226: 
cannam@226: 	// Move last value from LHS to parent
cannam@226: 	parent->vals[i - 1] = lhs->vals[--lhs->n_vals];
cannam@226: 
cannam@226: 	return rhs;
cannam@226: }
cannam@226: 
cannam@226: /** Move n[i] down, merge the left and right child, return the merged node. */
cannam@226: ZIX_PRIVATE ZixBTreeNode*
cannam@226: zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const uint16_t i)
cannam@226: {
cannam@226: 	ZixBTreeNode* const lhs = n->children[i];
cannam@226: 	ZixBTreeNode* const rhs = n->children[i + 1];
cannam@226: 
cannam@226: 	assert(zix_btree_node_is_minimal(n->children[i]));
cannam@226: 	assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
cannam@226: 
cannam@226: 	// Move parent value to end of LHS
cannam@226: 	lhs->vals[lhs->n_vals++] = zix_btree_aerase(n->vals, n->n_vals, i);
cannam@226: 
cannam@226: 	// Erase corresponding child pointer (to RHS) in parent
cannam@226: 	zix_btree_aerase((void**)n->children, n->n_vals, i + 1);
cannam@226: 
cannam@226: 	// Add everything from RHS to end of LHS
cannam@226: 	memcpy(lhs->vals + lhs->n_vals, rhs->vals, rhs->n_vals * sizeof(void*));
cannam@226: 	if (!lhs->is_leaf) {
cannam@226: 		memcpy(lhs->children + lhs->n_vals,
cannam@226: 		       rhs->children,
cannam@226: 		       (rhs->n_vals + 1) * sizeof(void*));
cannam@226: 	}
cannam@226: 	lhs->n_vals += rhs->n_vals;
cannam@226: 
cannam@226: 	if (--n->n_vals == 0) {
cannam@226: 		// Root is now empty, replace it with its only child
cannam@226: 		assert(n == t->root);
cannam@226: 		t->root = lhs;
cannam@226: 		free(n);
cannam@226: 	}
cannam@226: 
cannam@226: 	free(rhs);
cannam@226: 	return lhs;
cannam@226: }
cannam@226: 
cannam@226: /** Remove and return the min value from the subtree rooted at `n`. */
cannam@226: ZIX_PRIVATE void*
cannam@226: zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n)
cannam@226: {
cannam@226: 	while (!n->is_leaf) {
cannam@226: 		if (zix_btree_node_is_minimal(n->children[0])) {
cannam@226: 			// Leftmost child is minimal, must expand
cannam@226: 			if (!zix_btree_node_is_minimal(n->children[1])) {
cannam@226: 				// Child's right sibling has at least one key to steal
cannam@226: 				n = zix_btree_rotate_left(n, 0);
cannam@226: 			} else {
cannam@226: 				// Both child and right sibling are minimal, merge
cannam@226: 				n = zix_btree_merge(t, n, 0);
cannam@226: 			}
cannam@226: 		} else {
cannam@226: 			n = n->children[0];
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	return zix_btree_aerase(n->vals, --n->n_vals, 0);
cannam@226: }
cannam@226: 
cannam@226: /** Remove and return the max value from the subtree rooted at `n`. */
cannam@226: ZIX_PRIVATE void*
cannam@226: zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
cannam@226: {
cannam@226: 	while (!n->is_leaf) {
cannam@226: 		if (zix_btree_node_is_minimal(n->children[n->n_vals])) {
cannam@226: 			// Leftmost child is minimal, must expand
cannam@226: 			if (!zix_btree_node_is_minimal(n->children[n->n_vals - 1])) {
cannam@226: 				// Child's left sibling has at least one key to steal
cannam@226: 				n = zix_btree_rotate_right(n, n->n_vals);
cannam@226: 			} else {
cannam@226: 				// Both child and left sibling are minimal, merge
cannam@226: 				n = zix_btree_merge(t, n, n->n_vals - 1);
cannam@226: 			}
cannam@226: 		} else {
cannam@226: 			n = n->children[n->n_vals];
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	return n->vals[--n->n_vals];
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_remove(ZixBTree* const      t,
cannam@226:                  const void* const    e,
cannam@226:                  void** const         out,
cannam@226:                  ZixBTreeIter** const next)
cannam@226: {
cannam@226: 	ZixBTreeNode* n         = t->root;
cannam@226: 	ZixBTreeIter* ti        = NULL;
cannam@226: 	const bool    user_iter = next && *next;
cannam@226: 	if (next) {
cannam@226: 		if (!*next && !(*next = zix_btree_iter_new(t))) {
cannam@226: 			return ZIX_STATUS_NO_MEM;
cannam@226: 		}
cannam@226: 		ti        = *next;
cannam@226: 		ti->level = 0;
cannam@226: 	}
cannam@226: 
cannam@226: 	while (true) {
cannam@226: 		/* To remove in a single walk down, the tree is adjusted along the way
cannam@226: 		   so that the current node always has at least one more value than the
cannam@226: 		   minimum required in general. Thus, there is always room to remove
cannam@226: 		   without adjusting on the way back up. */
cannam@226: 		assert(n == t->root || !zix_btree_node_is_minimal(n));
cannam@226: 
cannam@226: 		bool           equal = false;
cannam@226: 		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
cannam@226: 		zix_btree_iter_set_frame(ti, n, i);
cannam@226: 		if (n->is_leaf) {
cannam@226: 			if (equal) {
cannam@226: 				// Found in leaf node
cannam@226: 				*out = zix_btree_aerase(n->vals, --n->n_vals, i);
cannam@226: 				if (ti && i == n->n_vals) {
cannam@226: 					if (i == 0) {
cannam@226: 						ti->stack[ti->level = 0].node = NULL;
cannam@226: 					} else {
cannam@226: 						--ti->stack[ti->level].index;
cannam@226: 						zix_btree_iter_increment(ti);
cannam@226: 					}
cannam@226: 				}
cannam@226: 				--t->size;
cannam@226: 				return ZIX_STATUS_SUCCESS;
cannam@226: 			} else {
cannam@226: 				// Not found in leaf node, or tree
cannam@226: 				if (ti && !user_iter) {
cannam@226: 					zix_btree_iter_free(ti);
cannam@226: 					*next = NULL;
cannam@226: 				}
cannam@226: 				return ZIX_STATUS_NOT_FOUND;
cannam@226: 			}
cannam@226: 		} else if (equal) {
cannam@226: 			// Found in internal node
cannam@226: 			if (!zix_btree_node_is_minimal(n->children[i])) {
cannam@226: 				// Left child can remove without merge
cannam@226: 				*out = n->vals[i];
cannam@226: 				n->vals[i] = zix_btree_remove_max(t, n->children[i]);
cannam@226: 				--t->size;
cannam@226: 				return ZIX_STATUS_SUCCESS;
cannam@226: 			} else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
cannam@226: 				// Right child can remove without merge
cannam@226: 				*out = n->vals[i];
cannam@226: 				n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
cannam@226: 				--t->size;
cannam@226: 				return ZIX_STATUS_SUCCESS;
cannam@226: 			} else {
cannam@226: 				// Both preceding and succeeding child are minimal
cannam@226: 				n = zix_btree_merge(t, n, i);
cannam@226: 			}
cannam@226: 		} else {
cannam@226: 			// Not found in internal node, key is in/under children[i]
cannam@226: 			if (zix_btree_node_is_minimal(n->children[i])) {
cannam@226: 				if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
cannam@226: 					// Steal a key from child's left sibling
cannam@226: 					n = zix_btree_rotate_right(n, i);
cannam@226: 				} else if (i < n->n_vals &&
cannam@226: 				           !zix_btree_node_is_minimal(n->children[i + 1])) {
cannam@226: 					// Steal a key from child's right sibling
cannam@226: 					n = zix_btree_rotate_left(n, i);
cannam@226: 				} else {
cannam@226: 					// Both child's siblings are minimal, merge them
cannam@226: 					if (i < n->n_vals) {
cannam@226: 						n = zix_btree_merge(t, n, i);
cannam@226: 					} else {
cannam@226: 						n = zix_btree_merge(t, n, i - 1);
cannam@226: 						if (ti) {
cannam@226: 							--ti->stack[ti->level].index;
cannam@226: 						}
cannam@226: 					}
cannam@226: 				}
cannam@226: 			} else {
cannam@226: 				n = n->children[i];
cannam@226: 			}
cannam@226: 		}
cannam@226: 		if (ti) {
cannam@226: 			++ti->level;
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	assert(false);  // Not reached
cannam@226: 	return ZIX_STATUS_ERROR;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_find(const ZixBTree* const t,
cannam@226:                const void* const     e,
cannam@226:                ZixBTreeIter** const  ti)
cannam@226: {
cannam@226: 	ZixBTreeNode* n = t->root;
cannam@226: 	if (!(*ti = zix_btree_iter_new(t))) {
cannam@226: 		return ZIX_STATUS_NO_MEM;
cannam@226: 	}
cannam@226: 
cannam@226: 	while (n) {
cannam@226: 		bool           equal = false;
cannam@226: 		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
cannam@226: 
cannam@226: 		zix_btree_iter_set_frame(*ti, n, i);
cannam@226: 
cannam@226: 		if (equal) {
cannam@226: 			return ZIX_STATUS_SUCCESS;
cannam@226: 		} else if (n->is_leaf) {
cannam@226: 			break;
cannam@226: 		} else {
cannam@226: 			++(*ti)->level;
cannam@226: 			n = n->children[i];
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	zix_btree_iter_free(*ti);
cannam@226: 	*ti = NULL;
cannam@226: 	return ZIX_STATUS_NOT_FOUND;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_lower_bound(const ZixBTree* const t,
cannam@226:                       const void* const     e,
cannam@226:                       ZixBTreeIter** const  ti)
cannam@226: {
cannam@226: 	if (!t) {
cannam@226: 		*ti = NULL;
cannam@226: 		return ZIX_STATUS_BAD_ARG;
cannam@226: 	}
cannam@226: 
cannam@226: 	ZixBTreeNode* n           = t->root;
cannam@226: 	bool          found       = false;
cannam@226: 	unsigned      found_level = 0;
cannam@226: 	if (!(*ti = zix_btree_iter_new(t))) {
cannam@226: 		return ZIX_STATUS_NO_MEM;
cannam@226: 	}
cannam@226: 
cannam@226: 	while (n) {
cannam@226: 		bool           equal = false;
cannam@226: 		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
cannam@226: 
cannam@226: 		zix_btree_iter_set_frame(*ti, n, i);
cannam@226: 
cannam@226: 		if (equal) {
cannam@226: 			found_level = (*ti)->level;
cannam@226: 			found       = true;
cannam@226: 		}
cannam@226: 
cannam@226: 		if (n->is_leaf) {
cannam@226: 			break;
cannam@226: 		} else {
cannam@226: 			++(*ti)->level;
cannam@226: 			n = n->children[i];
cannam@226: 			assert(n);
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
cannam@226: 	if (frame->index == frame->node->n_vals) {
cannam@226: 		if (found) {
cannam@226: 			// Found on a previous level but went too far
cannam@226: 			(*ti)->level = found_level;
cannam@226: 		} else {
cannam@226: 			// Reached end (key is greater than everything in tree)
cannam@226: 			(*ti)->stack[0].node = NULL;
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	return ZIX_STATUS_SUCCESS;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void*
cannam@226: zix_btree_get(const ZixBTreeIter* const ti)
cannam@226: {
cannam@226: 	const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
cannam@226: 	assert(frame->index < frame->node->n_vals);
cannam@226: 	return frame->node->vals[frame->index];
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixBTreeIter*
cannam@226: zix_btree_begin(const ZixBTree* const t)
cannam@226: {
cannam@226: 	ZixBTreeIter* const i = zix_btree_iter_new(t);
cannam@226: 	if (!i) {
cannam@226: 		return NULL;
cannam@226: 	} else if (t->size == 0) {
cannam@226: 		i->stack[0].node = NULL;
cannam@226: 	} else {
cannam@226: 		ZixBTreeNode* n = t->root;
cannam@226: 		i->stack[0].node  = n;
cannam@226: 		i->stack[0].index = 0;
cannam@226: 		while (!n->is_leaf) {
cannam@226: 			n = n->children[0];
cannam@226: 			++i->level;
cannam@226: 			i->stack[i->level].node  = n;
cannam@226: 			i->stack[i->level].index = 0;
cannam@226: 		}
cannam@226: 	}
cannam@226: 	return i;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API bool
cannam@226: zix_btree_iter_is_end(const ZixBTreeIter* const i)
cannam@226: {
cannam@226: 	return !i || i->stack[0].node == NULL;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void
cannam@226: zix_btree_iter_increment(ZixBTreeIter* const i)
cannam@226: {
cannam@226: 	ZixBTreeIterFrame* f = &i->stack[i->level];
cannam@226: 	if (f->node->is_leaf) {
cannam@226: 		// Leaf, move right
cannam@226: 		assert(f->index < f->node->n_vals);
cannam@226: 		if (++f->index == f->node->n_vals) {
cannam@226: 			// Reached end of leaf, move up
cannam@226: 			f = &i->stack[i->level];
cannam@226: 			while (i->level > 0 && f->index == f->node->n_vals) {
cannam@226: 				f = &i->stack[--i->level];
cannam@226: 				assert(f->index <= f->node->n_vals);
cannam@226: 			}
cannam@226: 
cannam@226: 			if (f->index == f->node->n_vals) {
cannam@226: 				// Reached end of tree
cannam@226: 				assert(i->level == 0);
cannam@226: 				f->node  = NULL;
cannam@226: 				f->index = 0;
cannam@226: 			}
cannam@226: 		}
cannam@226: 	} else {
cannam@226: 		// Internal node, move down to next child
cannam@226: 		assert(f->index < f->node->n_vals);
cannam@226: 		ZixBTreeNode* child = f->node->children[++f->index];
cannam@226: 
cannam@226: 		f        = &i->stack[++i->level];
cannam@226: 		f->node  = child;
cannam@226: 		f->index = 0;
cannam@226: 
cannam@226: 		// Move down and left until we hit a leaf
cannam@226: 		while (!f->node->is_leaf) {
cannam@226: 			child    = f->node->children[0];
cannam@226: 			f        = &i->stack[++i->level];
cannam@226: 			f->node  = child;
cannam@226: 			f->index = 0;
cannam@226: 		}
cannam@226: 	}
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void
cannam@226: zix_btree_iter_free(ZixBTreeIter* const i)
cannam@226: {
cannam@226: 	free(i);
cannam@226: }