1 /* 2 * Flexible B-tree implementation. Supports reference counting for 3 * copy-on-write, user-defined node properties, and variable 4 * degree. 5 * 6 * This file is copyright 2001,2004 Simon Tatham. 7 * 8 * Permission is hereby granted, free of charge, to any person 9 * obtaining a copy of this software and associated documentation 10 * files (the "Software"), to deal in the Software without 11 * restriction, including without limitation the rights to use, 12 * copy, modify, merge, publish, distribute, sublicense, and/or 13 * sell copies of the Software, and to permit persons to whom the 14 * Software is furnished to do so, subject to the following 15 * conditions: 16 * 17 * The above copyright notice and this permission notice shall be 18 * included in all copies or substantial portions of the Software. 19 * 20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 22 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 23 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR 24 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 25 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 26 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 27 * SOFTWARE. 28 */ 29 30 #ifndef BTREE_H 31 #define BTREE_H 32 33 #include <stddef.h> /* for offsetof */ 34 35 #ifndef alignof 36 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) ) 37 #endif 38 39 typedef struct btree btree; 40 typedef void *bt_element_t; 41 42 typedef int (*cmpfn_t)(void *state, bt_element_t, bt_element_t); 43 typedef bt_element_t (*copyfn_t)(void *state, bt_element_t); 44 typedef void (*freefn_t)(void *state, bt_element_t); 45 typedef void (*propmakefn_t)(void *state, bt_element_t, void *dest); 46 /* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */ 47 typedef void (*propmergefn_t)(void *state, void *s1, void *s2, void *dest); 48 typedef int (*searchfn_t)(void *tstate, void *sstate, int ntrees, 49 void **props, int *counts, 50 bt_element_t *elts, int *is_elt); 51 52 enum { 53 BT_REL_EQ, BT_REL_LT, BT_REL_LE, BT_REL_GT, BT_REL_GE 54 }; 55 56 btree *bt_new(cmpfn_t cmp, copyfn_t copy, freefn_t freeelt, 57 int propsize, int propalign, propmakefn_t propmake, 58 propmergefn_t propmerge, void *state, int mindegree); 59 void bt_free(btree *bt); 60 btree *bt_clone(btree *bt); 61 int bt_count(btree *bt); 62 bt_element_t bt_index(btree *bt, int index); 63 bt_element_t bt_index_w(btree *bt, int index); 64 bt_element_t bt_findrelpos(btree *bt, bt_element_t element, cmpfn_t cmp, 65 int relation, int *index); 66 bt_element_t bt_findrel(btree *bt, bt_element_t element, cmpfn_t cmp, 67 int relation); 68 bt_element_t bt_findpos(btree *bt, bt_element_t element, cmpfn_t cmp, 69 int *index); 70 bt_element_t bt_find(btree *bt, bt_element_t element, cmpfn_t cmp); 71 bt_element_t bt_propfind(btree *bt, searchfn_t search, void *sstate, 72 int *index); 73 bt_element_t bt_replace(btree *bt, bt_element_t element, int index); 74 void bt_addpos(btree *bt, bt_element_t element, int pos); 75 bt_element_t bt_add(btree *bt, bt_element_t element); 76 bt_element_t bt_delpos(btree *bt, int pos); 77 bt_element_t bt_del(btree *bt, bt_element_t element); 78 btree *bt_join(btree *bt1, btree *bt2); 79 btree *bt_joinr(btree *bt1, btree *bt2); 80 btree *bt_splitpos(btree *bt, int index, int before); 81 btree *bt_split(btree *bt, bt_element_t element, cmpfn_t cmp, int rel); 82 83 #endif /* BTREE_H */ 84