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 2b81dafbe4e0cd6f7f3e016e24ca186ad7470876..46877229b9e015944d9b6cf56d289ad4a78165a0 100644 (file)
--- 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).
  *
  * 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
  * 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 31982ec80efc6669aed259cef9c0c80202cad78e..4e7782fdd9e66a91517eba89bfc479830d264dce 100644 (file)
--- 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;
                node->depth = 0;
        btree->root = node;
        btree->search = search;

+       btree->multi = false;

        return btree;
 }
 
        return btree;
 }
 


@@ -86,6 +87,43 @@ void btree_delete(struct btree *btree)
        free(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;
 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;
 }
 
        return 0;
 }
 

+/********************* Built-in ordering functions *******************/
+
+btree_search_implement
+(
+       btree_strcmp,
+       char*,
+       int c = strcmp(a, b),
+       c == 0,
+       c < 0
+)
+

 
 /************************* Private functions *************************/
 
 
 /************************* Private functions *************************/
 

diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h
index babfea763f14fda65794866c2699c65800deb030..7415ca5923422aefdcac6dca357f7346252f1774 100644 (file)
--- 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_walk...
 btree_cmp_iters

+btree_insert
+btree_remove
+btree_lookup

 */
 
 */
 

+#include <stdbool.h>

 #include <stdint.h>
 #include <stdint.h>

-#include <stddef.h>
+#include <string.h>

 
 /*
  * Maximum number of items per node.
 
 /*
  * Maximum number of items per node.


@@ -90,6 +94,8 @@ typedef unsigned int btree_search_proto(
 );
 typedef btree_search_proto *btree_search_t;
 
 );
 typedef btree_search_proto *btree_search_t;
 

+btree_search_proto btree_strcmp;
+

 /*
  * Callback used by btree_delete() and btree_walk...().
  *
 /*
  * 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;
        size_t count; /* Total number of items in B-tree */
        
        btree_search_t search;

+       bool multi;

        
        /*
         * These are set to NULL by default.
        
        /*
         * 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);
 
 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);
 
 /* lr must be 0 or 1, nothing else. */
 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr);