X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fbtree%2Fbtree.h;h=fdf198d3c7c4853eb9dd31e5a713d3348f283e49;hb=7141adfed692b149bfbaccf19e2ab258774810fb;hp=babfea763f14fda65794866c2699c65800deb030;hpb=8f7447e48f6405a083919f3d6b591eb7dfbc6a9f;p=ccan

diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h
index babfea76..fdf198d3 100644
--- a/ccan/btree/btree.h
+++ b/ccan/btree/btree.h
@@ -1,29 +1,24 @@
 /*
-	Copyright (c) 2010  Joseph A. Adams
-	All rights reserved.
-	
-	Redistribution and use in source and binary forms, with or without
-	modification, are permitted provided that the following conditions
-	are met:
-	1. Redistributions of source code must retain the above copyright
-	   notice, this list of conditions and the following disclaimer.
-	2. Redistributions in binary form must reproduce the above copyright
-	   notice, this list of conditions and the following disclaimer in the
-	   documentation and/or other materials provided with the distribution.
-	3. The name of the author may not be used to endorse or promote products
-	   derived from this software without specific prior written permission.
-	
-	THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
-	IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
-	OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
-	IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
-	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
-	NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-	DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-	THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-	(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
-	THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
+ * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
 
 #ifndef CCAN_BTREE_H
 #define CCAN_BTREE_H
@@ -33,10 +28,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 +89,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 +107,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 +125,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);