rbtree.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00043 #ifndef LDNS_RBTREE_H_
00044 #define LDNS_RBTREE_H_
00045
00051 typedef struct ldns_rbnode_t ldns_rbnode_t;
00055 struct ldns_rbnode_t {
00057 ldns_rbnode_t *parent;
00059 ldns_rbnode_t *left;
00061 ldns_rbnode_t *right;
00063 const void *key;
00065 const void *data;
00067 uint8_t color;
00068 };
00069
00071 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node
00072
00073 extern ldns_rbnode_t ldns_rbtree_null_node;
00074
00076 typedef struct ldns_rbtree_t ldns_rbtree_t;
00078 struct ldns_rbtree_t {
00080 ldns_rbnode_t *root;
00081
00083 size_t count;
00084
00089 int (*cmp) (const void *, const void *);
00090 };
00091
00097 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
00098
00103 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
00104
00110 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
00111
00118 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
00119
00126 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
00127
00135 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
00136
00143 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
00144
00154 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
00155 ldns_rbnode_t **result);
00156
00162 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
00163
00169 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
00170
00176 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
00177
00183 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
00184
00190 ldns_rbtree_t *ldns_dnssec_rbtree_split(ldns_rbtree_t *tree,
00191 size_t elements);
00192
00197 void ldns_dnssec_rbtree_join(ldns_rbtree_t *tree1,
00198 ldns_rbtree_t *tree2);
00199
00204 #define LDNS_RBTREE_FOR(node, type, rbtree) \
00205 for(node=(type)ldns_rbtree_first(rbtree); \
00206 (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
00207 node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
00208
00220 void ldns_traverse_postorder(ldns_rbtree_t* tree,
00221 void (*func)(ldns_rbnode_t*, void*), void* arg);
00222
00223 #endif