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
00046 #ifdef __cplusplus
00047 extern "C" {
00048 #endif
00049
00056 typedef struct ldns_rbnode_t ldns_rbnode_t;
00060 struct ldns_rbnode_t {
00062 ldns_rbnode_t *parent;
00064 ldns_rbnode_t *left;
00066 ldns_rbnode_t *right;
00068 const void *key;
00070 const void *data;
00072 uint8_t color;
00073 };
00074
00076 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node
00077
00078 extern ldns_rbnode_t ldns_rbtree_null_node;
00079
00081 typedef struct ldns_rbtree_t ldns_rbtree_t;
00083 struct ldns_rbtree_t {
00085 ldns_rbnode_t *root;
00086
00088 size_t count;
00089
00094 int (*cmp) (const void *, const void *);
00095 };
00096
00102 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
00103
00108 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
00109
00115 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
00116
00123 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
00124
00131 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
00132
00140 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
00141
00148 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
00149
00159 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
00160 ldns_rbnode_t **result);
00161
00167 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
00168
00174 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
00175
00181 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
00182
00188 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
00189
00195 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
00196
00201 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
00202
00207 #define LDNS_RBTREE_FOR(node, type, rbtree) \
00208 for(node=(type)ldns_rbtree_first(rbtree); \
00209 (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
00210 node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
00211
00223 void ldns_traverse_postorder(ldns_rbtree_t* tree,
00224 void (*func)(ldns_rbnode_t*, void*), void* arg);
00225
00226 #ifdef __cplusplus
00227 }
00228 #endif
00229
00230 #endif