mdw@git.distorted.org.uk Git - sgt/library/blob - btree.h

   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 */