Add sord_erase() for erasing statements via an iterator.

git-svn-id: http://svn.drobilla.net/sord/trunk@310 3d64ff67-21c5-427c-a301-fe4f08042e5a

1 files changed, 112 insertions, 82 deletions

diff --git a/src/zix/btree.c b/src/zix/btree.c
index b03a6c5..e7912d0 100644
--- a/src/zix/btree.c
+++ b/src/zix/btree.c
@@ -317,6 +317,28 @@ zix_btree_insert(ZixBTree* const t, void* const e)
 	return ZIX_STATUS_SUCCESS;
 }
 
+ZIX_PRIVATE ZixBTreeIter*
+zix_btree_iter_new(const ZixBTree* const t)
+{
+	const size_t        s = t->height * sizeof(ZixBTreeIterFrame);
+	ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
+	if (i) {
+		i->level = 0;
+	}
+	return i;
+}
+
+ZIX_PRIVATE void
+zix_btree_iter_set_frame(ZixBTreeIter* const ti,
+                         ZixBTreeNode* const n,
+                         const uint16_t      i)
+{
+	if (ti) {
+		ti->stack[ti->level].node  = n;
+		ti->stack[ti->level].index = i;
+	}
+}
+
 ZIX_PRIVATE bool
 zix_btree_node_is_minimal(ZixBTreeNode* const n)
 {
@@ -450,67 +472,100 @@ zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
 	return n->vals[--n->n_vals];
 }
 
-ZIX_PRIVATE ZixStatus
-zix_btree_remove_rec(ZixBTree* const     t,
-                     ZixBTreeNode* const n,
-                     const void* const   e,
-                     void** const        removed)
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* const      t,
+                 const void* const    e,
+                 void** const         out,
+                 ZixBTreeIter** const next)
 {
-	/* To remove in a single walk down, the tree is adjusted along the way so
-	   that the current node always has at least one more value than the
-	   minimum required in general. Thus, there is always room to remove
-	   without adjusting on the way back up. */
-	assert(n == t->root || !zix_btree_node_is_minimal(n));
+	ZixBTreeNode* n         = t->root;
+	ZixBTreeIter* ti        = NULL;
+	const bool    user_iter = next && *next;
+	if (next) {
+		if (!*next && !(*next = zix_btree_iter_new(t))) {
+			return ZIX_STATUS_NO_MEM;
+		}
+		ti        = *next;
+		ti->level = 0;
+	}
 
-	bool           equal = false;
-	const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
+	while (true) {
+		/* To remove in a single walk down, the tree is adjusted along the way
+		   so that the current node always has at least one more value than the
+		   minimum required in general. Thus, there is always room to remove
+		   without adjusting on the way back up. */
+		assert(n == t->root || !zix_btree_node_is_minimal(n));
 
-	if (n->is_leaf) {
-		if (equal) {
-			// Found in leaf node
-			*removed = zix_btree_aerase(n->vals, --n->n_vals, i);
-			return ZIX_STATUS_SUCCESS;
-		} else {
-			// Not found in leaf node, or tree
-			return ZIX_STATUS_NOT_FOUND;
-		}
-	} else if (equal) {
-		// Found in internal node
-		if (!zix_btree_node_is_minimal(n->children[i])) {
-			// Left child can remove without merge
-			*removed = n->vals[i];
-			n->vals[i] = zix_btree_remove_max(t, n->children[i]);
-			return ZIX_STATUS_SUCCESS;
-		} else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
-			// Right child can remove without merge
-			*removed = n->vals[i];
-			n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
-			return ZIX_STATUS_SUCCESS;
-		} else {
-			// Both preceding and succeeding child are minimal
-			ZixBTreeNode* const merged = zix_btree_merge(t, n, i);
-			return zix_btree_remove_rec(t, merged, e, removed);
-		}
-	} else {
-		// Not found in internal node, key is in/under children[i]
-		if (zix_btree_node_is_minimal(n->children[i])) {
-			if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
-				// Child's left sibling has at least one key to steal
-				ZixBTreeNode* const rhs = zix_btree_rotate_right(n, i);
-				return zix_btree_remove_rec(t, rhs, e, removed);
-			} else if (i < n->n_vals &&
-			           !zix_btree_node_is_minimal(n->children[i + 1])) {
-				// Child's right sibling has at least one key to steal
-				ZixBTreeNode* const lhs = zix_btree_rotate_left(n, i);
-				return zix_btree_remove_rec(t, lhs, e, removed);
+		bool           equal = false;
+		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
+		zix_btree_iter_set_frame(ti, n, i);
+		if (n->is_leaf) {
+			if (equal) {
+				// Found in leaf node
+				*out = zix_btree_aerase(n->vals, --n->n_vals, i);
+				if (ti && i == n->n_vals) {
+					if (i == 0) {
+						ti->stack[ti->level = 0].node = NULL;
+					} else {
+						--ti->stack[ti->level].index;
+						zix_btree_iter_increment(ti);
+					}
+				}
+				--t->size;
+				return ZIX_STATUS_SUCCESS;
+			} else {
+				// Not found in leaf node, or tree
+				if (ti && !user_iter) {
+					zix_btree_iter_free(ti);
+					*next = NULL;
+				}
+				return ZIX_STATUS_NOT_FOUND;
+			}
+		} else if (equal) {
+			// Found in internal node
+			if (!zix_btree_node_is_minimal(n->children[i])) {
+				// Left child can remove without merge
+				*out = n->vals[i];
+				n->vals[i] = zix_btree_remove_max(t, n->children[i]);
+				--t->size;
+				return ZIX_STATUS_SUCCESS;
+			} else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
+				// Right child can remove without merge
+				*out = n->vals[i];
+				n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
+				--t->size;
+				return ZIX_STATUS_SUCCESS;
 			} else {
-				// Both child's siblings are minimal, merge them
-				const uint16_t m = (i < n->n_vals) ? i : i - 1;
-				ZixBTreeNode* const merged = zix_btree_merge(t, n, m);
-				return zix_btree_remove_rec(t, merged, e, removed);
+				// Both preceding and succeeding child are minimal
+				n = zix_btree_merge(t, n, i);
 			}
 		} else {
-			return zix_btree_remove_rec(t, n->children[i], e, removed);
+			// Not found in internal node, key is in/under children[i]
+			if (zix_btree_node_is_minimal(n->children[i])) {
+				if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
+					// Steal a key from child's left sibling
+					n = zix_btree_rotate_right(n, i);
+				} else if (i < n->n_vals &&
+				           !zix_btree_node_is_minimal(n->children[i + 1])) {
+					// Steal a key from child's right sibling
+					n = zix_btree_rotate_left(n, i);
+				} else {
+					// Both child's siblings are minimal, merge them
+					if (i < n->n_vals) {
+						n = zix_btree_merge(t, n, i);
+					} else {
+						n = zix_btree_merge(t, n, i - 1);
+						if (ti) {
+							--ti->stack[ti->level].index;
+						}
+					}
+				}
+			} else {
+				n = n->children[i];
+			}
+		}
+		if (ti) {
+			++ti->level;
 		}
 	}
 
@@ -519,27 +574,6 @@ zix_btree_remove_rec(ZixBTree* const     t,
 }
 
 ZIX_API ZixStatus
-zix_btree_remove(ZixBTree* const t, const void* const e, void** const removed)
-{
-	const ZixStatus st = zix_btree_remove_rec(t, t->root, e, removed);
-	if (!st) {
-		--t->size;
-	}
-	return st;
-}
-
-ZIX_PRIVATE ZixBTreeIter*
-zix_btree_iter_new(const ZixBTree* const t)
-{
-	const size_t        s = t->height * sizeof(ZixBTreeIterFrame);
-	ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
-	if (i) {
-		i->level = 0;
-	}
-	return i;
-}
-
-ZIX_API ZixStatus
 zix_btree_find(const ZixBTree* const t,
                const void* const     e,
                ZixBTreeIter** const  ti)
@@ -553,9 +587,7 @@ zix_btree_find(const ZixBTree* const t,
 		bool           equal = false;
 		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
 
-		// Update iterator stack
-		(*ti)->stack[(*ti)->level].node  = n;
-		(*ti)->stack[(*ti)->level].index = i;
+		zix_btree_iter_set_frame(*ti, n, i);
 
 		if (equal) {
 			return ZIX_STATUS_SUCCESS;
@@ -588,9 +620,7 @@ zix_btree_lower_bound(const ZixBTree* const t,
 		bool           equal = false;
 		const uint16_t i     = zix_btree_node_find(t, n, e, &equal);
 
-		// Update iterator stack
-		(*ti)->stack[(*ti)->level].node  = n;
-		(*ti)->stack[(*ti)->level].index = i;
+		zix_btree_iter_set_frame(*ti, n, i);
 
 		if (equal) {
 			found_level = (*ti)->level;