source/modules/lilv/sord-0.16.0/src/zix/btree.h

   1 /*
   2   Copyright 2011-2016 David Robillard <http://drobilla.net>
   3
   4   Permission to use, copy, modify, and/or distribute this software for any
   5   purpose with or without fee is hereby granted, provided that the above
   6   copyright notice and this permission notice appear in all copies.
   7
   8   THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9   WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10   MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11   ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12   WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13   ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15 */
  16
  17 #ifndef ZIX_BTREE_H
  18 #define ZIX_BTREE_H
  19
  20 #include <stddef.h>
  21
  22 #include "zix/common.h"
  23
  24 #ifdef __cplusplus
  25 extern "C" {
  26 #else
  27 #    include <stdbool.h>
  28 #endif
  29
  30 /**
  31    @addtogroup zix
  32    @{
  33    @name BTree
  34    @{
  35 */
  36
  37 /**
  38    A B-Tree.
  39 */
  40 typedef struct ZixBTreeImpl ZixBTree;
  41
  42 /**
  43    A B-Tree node (opaque).
  44 */
  45 typedef struct ZixBTreeNodeImpl ZixBTreeNode;
  46
  47 /**
  48    An iterator over a B-Tree.
  49
  50    Note that modifying the trees invalidates all iterators, so all iterators
  51    are const iterators.
  52 */
  53 typedef struct ZixBTreeIterImpl ZixBTreeIter;
  54
  55 /**
  56    Create a new (empty) B-Tree.
  57 */
  58 ZIX_API ZixBTree*
  59 zix_btree_new(ZixComparator  cmp,
  60               void*          cmp_data,
  61               ZixDestroyFunc destroy);
  62
  63 /**
  64    Free `t`.
  65 */
  66 ZIX_API void
  67 zix_btree_free(ZixBTree* t);
  68
  69 /**
  70    Return the number of elements in `t`.
  71 */
  72 ZIX_API size_t
  73 zix_btree_size(const ZixBTree* t);
  74
  75 /**
  76    Insert the element `e` into `t`.
  77 */
  78 ZIX_API ZixStatus
  79 zix_btree_insert(ZixBTree* t, void* e);
  80
  81 /**
  82    Remove the value `e` from `t`.
  83
  84    @param t Tree to remove from.
  85
  86    @param e Value to remove.
  87
  88    @param out Set to point to the removed pointer (which may not equal `e`).
  89
  90    @param next If non-NULL, pointed to the value following `e`.  If *next is
  91    also non-NULL, the iterator is reused, otherwise a new one is allocated.  To
  92    reuse an iterator, no items may have been added since its creation.
  93 */
  94 ZIX_API ZixStatus
  95 zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next);
  96
  97 /**
  98    Set `ti` to an element equal to `e` in `t`.
  99    If no such item exists, `ti` is set to NULL.
 100 */
 101 ZIX_API ZixStatus
 102 zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
 103
 104 /**
 105    Set `ti` to the smallest element in `t` that is not less than `e`.
 106
 107    Wildcards are supported, so if the search key `e` compares equal to many
 108    values in the tree, `ti` will be set to the least such element.  The search
 109    key `e` is always passed as the second argument to the comparator.
 110 */
 111 ZIX_API ZixStatus
 112 zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
 113
 114 /**
 115    Return the data associated with the given tree item.
 116 */
 117 ZIX_API void*
 118 zix_btree_get(const ZixBTreeIter* ti);
 119
 120 /**
 121    Return an iterator to the first (smallest) element in `t`.
 122
 123    The returned iterator must be freed with zix_btree_iter_free().
 124 */
 125 ZIX_API ZixBTreeIter*
 126 zix_btree_begin(const ZixBTree* t);
 127
 128 /**
 129    Return true iff `i` is an iterator to the end of its tree.
 130 */
 131 ZIX_API bool
 132 zix_btree_iter_is_end(const ZixBTreeIter* i);
 133
 134 /**
 135    Increment `i` to point to the next element in the tree.
 136 */
 137 ZIX_API void
 138 zix_btree_iter_increment(ZixBTreeIter* i);
 139
 140 /**
 141    Free `i`.
 142 */
 143 ZIX_API void
 144 zix_btree_iter_free(ZixBTreeIter* i);
 145
 146 /**
 147    @}
 148    @}
 149 */
 150
 151 #ifdef __cplusplus
 152 }  /* extern "C" */
 153 #endif
 154
 155 #endif  /* ZIX_BTREE_H */