/*
- 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
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.
);
typedef btree_search_proto *btree_search_t;
+btree_search_proto btree_strcmp;
+
/*
* Callback used by btree_delete() and btree_walk...().
*
size_t count; /* Total number of items in B-tree */
btree_search_t search;
+ bool multi;
/*
* These are set to NULL by default.
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);