From: Rusty Russell <rusty@rustcorp.com.au>
Date: Fri, 9 Apr 2010 01:24:31 +0000 (+0930)
Subject: From: Joseph Adams <joeyadams3.14159@gmail.com>
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=7b877620c687786bb5b2b4bb3daffc61ca4322cf

From: Joseph Adams <joeyadams3.14159@gmail.com>

The btree patch gives the btree module an intuitive frontend
(btree_insert, btree_remove, btree_lookup) and a built-in ordering
function for strings.  Together, these make it easy to use the btree
module as a dynamic string map.
---

diff --git a/ccan/btree/_info b/ccan/btree/_info
index 2b81dafb..46877229 100644
--- a/ccan/btree/_info
+++ b/ccan/btree/_info
@@ -12,14 +12,6 @@
  * invalidate all iterators pointing to it (including the one passed to the
  * insertion or removal function).
  *
- * btree currently doesn't have convenience functions for the simple tasks of
- * "look up by key", "insert a key", and "remove a key".  To insert or remove,
- * you first have use btree_find* to position an iterator on the
- * insertion/removal point, then call btree_insert_at or btree_remove_at using
- * that iterator.  Since a btree can hold multiple items with the same key,
- * it isn't clear how the convenience functions should work yet.  I'm open to
- * suggestions.
- *
  * A B-tree (not to be confused with a binary tree) is a data structure that
  * performs insertion, removal, and lookup in O(log n) time per operation.
  * Although B-trees are typically used for databases and filesystems, this is
diff --git a/ccan/btree/btree.c b/ccan/btree/btree.c
index 31982ec8..4e7782fd 100644
--- a/ccan/btree/btree.c
+++ b/ccan/btree/btree.c
@@ -77,6 +77,7 @@ struct btree *btree_new(btree_search_t search)
 		node->depth = 0;
 	btree->root = node;
 	btree->search = search;
+	btree->multi = false;
 	return btree;
 }
 
@@ -86,6 +87,43 @@ void btree_delete(struct btree *btree)
 	free(btree);
 }
 
+bool btree_insert(struct btree *btree, const void *item)
+{
+	btree_iterator iter;
+	
+	if (btree_find_last(btree, item, iter) && !btree->multi)
+		return false;
+	
+	btree_insert_at(iter, item);
+	return true;
+}
+
+bool btree_remove(struct btree *btree, const void *key)
+{
+	btree_iterator iter;
+	bool success = false;
+	bool multi = btree->multi;
+	
+	do {
+		if (btree_find_first(btree, key, iter)) {
+			btree_remove_at(iter);
+			success = true;
+		}
+	} while (multi);
+	
+	return success;
+}
+
+void *btree_lookup(struct btree *btree, const void *key)
+{
+	btree_iterator iter;
+	
+	if (btree_find_first(btree, key, iter))
+		return iter->item;
+	
+	return NULL;
+}
+
 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
 {
 	struct btree_node *node;
@@ -374,6 +412,17 @@ int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
 	return 0;
 }
 
+/********************* Built-in ordering functions *******************/
+
+btree_search_implement
+(
+	btree_strcmp,
+	char*,
+	int c = strcmp(a, b),
+	c == 0,
+	c < 0
+)
+
 
 /************************* Private functions *************************/
 
diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h
index babfea76..7415ca59 100644
--- a/ccan/btree/btree.h
+++ b/ccan/btree/btree.h
@@ -33,10 +33,14 @@ Note:  The following should work but are not well-tested yet:
 
 btree_walk...
 btree_cmp_iters
+btree_insert
+btree_remove
+btree_lookup
 */
 
+#include <stdbool.h>
 #include <stdint.h>
-#include <stddef.h>
+#include <string.h>
 
 /*
  * Maximum number of items per node.
@@ -90,6 +94,8 @@ typedef unsigned int btree_search_proto(
 );
 typedef btree_search_proto *btree_search_t;
 
+btree_search_proto btree_strcmp;
+
 /*
  * Callback used by btree_delete() and btree_walk...().
  *
@@ -106,6 +112,7 @@ struct btree {
 	size_t count; /* Total number of items in B-tree */
 	
 	btree_search_t search;
+	bool multi;
 	
 	/*
 	 * These are set to NULL by default.
@@ -123,6 +130,30 @@ struct btree {
 struct btree *btree_new(btree_search_t search);
 void btree_delete(struct btree *btree);
 
+/* Inserts an item into the btree.  If an item already exists that is equal
+ * to this one (as determined by the search function), behavior depends on the
+ * btree->multi setting.
+ *   If btree->multi is false (default), returns false, and no item
+ *      is inserted (because it would be a duplicate).
+ *   If btree->multi is true, returns true, putting the item after
+ *      its duplicates.
+ */
+bool btree_insert(struct btree *btree, const void *item);
+
+/* Removes an item from the btree.  If an item exists that is equal to the
+ * key (as determined by the search function), it is removed.
+ *
+ * If btree->multi is set, all matching items are removed.
+ *
+ * Returns true if item was found and deleted, false if not found. */
+bool btree_remove(struct btree *btree, const void *key);
+
+/* Finds the requested item.
+ * Returns the item pointer on success, NULL on failure.
+ * Note that NULL is a valid item value.  If you need to put
+ * NULLs in a btree, use btree_find instead. */
+void *btree_lookup(struct btree *btree, const void *key);
+
 
 /* lr must be 0 or 1, nothing else. */
 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr);