librb/include/rb_radixtree.h

   1 /*
   2  * Solanum: a slightly advanced ircd
   3  * rb_radixtree.h: Dictionary-based storage.
   4  *
   5  * Copyright (c) 2007-2016 Ariadne Conill <ariadne -at- dereferenced.org>
   6  * Copyright (c) 2007-2016 Jilles Tjoelker <jilles -at- stack.nl>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are
  10  * met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright notice,
  13  *    this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * 3. The name of the author may not be used to endorse or promote products
  20  *    derived from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  24  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  25  * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  26  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  27  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  28  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  30  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  31  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #ifndef __rb_radixtree_H__
  36 #define __rb_radixtree_H__
  37
  38 struct rb_radixtree;            /* defined in src/rb_radixtree.c */
  39
  40 struct rb_radixtree_leaf;       /* defined in src/rb_radixtree.c */
  41
  42 typedef struct rb_radixtree rb_radixtree;
  43 typedef struct rb_radixtree_leaf rb_radixtree_leaf;
  44 typedef struct rb_radixtree_iteration_state rb_radixtree_iteration_state;
  45
  46 /*
  47  * struct rb_radixtree_iteration_state, private.
  48  */
  49 struct rb_radixtree_iteration_state
  50 {
  51         rb_radixtree_leaf *cur, *next;
  52         void *pspare[4];
  53         int ispare[4];
  54 };
  55
  56 /*
  57  * this is a convenience macro for inlining iteration of dictionaries.
  58  */
  59 #define RB_RADIXTREE_FOREACH(element, state, dict) \
  60         for (rb_radixtree_foreach_start((dict), (state)); (element = rb_radixtree_foreach_cur((dict), (state))); rb_radixtree_foreach_next((dict), (state)))
  61
  62 #define RB_RADIXTREE_FOREACH_FROM(element, state, dict, key) \
  63         for (rb_radixtree_foreach_start_from((dict), (state), (key)); (element = rb_radixtree_foreach_cur((dict), (state))); rb_radixtree_foreach_next((dict), (state)))
  64
  65 /*
  66  * rb_radixtree_create() creates a new patricia tree of the defined resolution.
  67  * compare_cb is the canonizing function.
  68  */
  69
  70 extern rb_radixtree *rb_radixtree_create(const char *name, void (*canonize_cb)(char *key));
  71
  72 /*
  73  * rb_radixtree_shutdown() deallocates all heaps used in patricia trees. This is
  74  * useful on embedded devices with little memory, and/or when you know you won't need
  75  * any more patricia trees.
  76  */
  77 extern void rb_radixtree_shutdown(void);
  78
  79 /*
  80  * rb_radixtree_destroy() destroys all entries in a dtree, and also optionally calls
  81  * a defined callback function to destroy any data attached to it.
  82  */
  83 extern void rb_radixtree_destroy(rb_radixtree *dtree, void (*destroy_cb)(const char *key, void *data, void *privdata), void *privdata);
  84
  85 /*
  86  * rb_radixtree_foreach() iterates all entries in a dtree, and also optionally calls
  87  * a defined callback function to use any data attached to it.
  88  *
  89  * To shortcircuit iteration, return non-zero from the callback function.
  90  */
  91 extern void rb_radixtree_foreach(rb_radixtree *dtree, int (*foreach_cb)(const char *key, void *data, void *privdata), void *privdata);
  92
  93 /*
  94  * rb_radixtree_search() iterates all entries in a dtree, and also optionally calls
  95  * a defined callback function to use any data attached to it.
  96  *
  97  * When the object is found, a non-NULL is returned from the callback, which results
  98  * in that object being returned to the user.
  99  */
 100 extern void *rb_radixtree_search(rb_radixtree *dtree, void *(*foreach_cb)(const char *key, void *data, void *privdata), void *privdata);
 101
 102 /*
 103  * rb_radixtree_foreach_start() begins an iteration over all items
 104  * keeping state in the given struct. If there is only one iteration
 105  * in progress at a time, it is permitted to remove the current element
 106  * of the iteration (but not any other element).
 107  */
 108 extern void rb_radixtree_foreach_start(rb_radixtree *dtree, rb_radixtree_iteration_state *state);
 109
 110 /*
 111  * rb_radixtree_foreach_start_from() begins an iteration over all items,
 112  * starting with the item specified by `key`.  If there is only one iteration
 113  * in progress at a time, it is permitted to remove the current element
 114  * of the iteration (but not any other element).
 115  * Use NULL as a key to have it start at the beginning.
 116  */
 117 extern void rb_radixtree_foreach_start_from(rb_radixtree *dtree, rb_radixtree_iteration_state *state, const char *key);
 118
 119 /*
 120  * rb_radixtree_foreach_cur() returns the current element of the iteration,
 121  * or NULL if there are no more elements.
 122  */
 123 extern void *rb_radixtree_foreach_cur(rb_radixtree *dtree, rb_radixtree_iteration_state *state);
 124
 125 /*
 126  * rb_radixtree_foreach_next() moves to the next element.
 127  */
 128 extern void rb_radixtree_foreach_next(rb_radixtree *dtree, rb_radixtree_iteration_state *state);
 129
 130 /*
 131  * rb_radixtree_add() adds a key->value entry to the patricia tree.
 132  */
 133 extern int rb_radixtree_add(rb_radixtree *dtree, const char *key, void *data);
 134
 135 /*
 136  * rb_radixtree_find() returns data from a dtree for key 'key'.
 137  */
 138 extern void *rb_radixtree_retrieve(rb_radixtree *dtree, const char *key);
 139
 140 /*
 141  * rb_radixtree_delete() deletes a key->value entry from the patricia tree.
 142  */
 143 extern void *rb_radixtree_delete(rb_radixtree *dtree, const char *key);
 144
 145 /* Low-level functions */
 146 rb_radixtree_leaf *rb_radixtree_elem_add(rb_radixtree *dtree, const char *key, void *data);
 147 rb_radixtree_leaf *rb_radixtree_elem_find(rb_radixtree *dtree, const char *key, int fuzzy);
 148 void rb_radixtree_elem_delete(rb_radixtree *dtree, rb_radixtree_leaf *elem);
 149 const char *rb_radixtree_elem_get_key(rb_radixtree_leaf *elem);
 150 void rb_radixtree_elem_set_data(rb_radixtree_leaf *elem, void *data);
 151 void *rb_radixtree_elem_get_data(rb_radixtree_leaf *elem);
 152
 153 unsigned int rb_radixtree_size(rb_radixtree *dict);
 154 void rb_radixtree_stats(rb_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata);
 155 void rb_radixtree_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata);
 156
 157 #endif