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_RADIX_H_
00044 #define LDNS_RADIX_H_
00045
00046 #include <ldns/error.h>
00047
00048 #ifdef __cplusplus
00049 extern "C" {
00050 #endif
00051
00052 typedef uint16_t radix_strlen_t;
00053 typedef struct ldns_radix_array_t ldns_radix_array_t;
00054 typedef struct ldns_radix_node_t ldns_radix_node_t;
00055 typedef struct ldns_radix_t ldns_radix_t;
00056
00058 struct ldns_radix_array_t {
00060 uint8_t* str;
00062 radix_strlen_t len;
00064 ldns_radix_node_t* edge;
00065 };
00066
00068 struct ldns_radix_node_t {
00070 uint8_t* key;
00072 radix_strlen_t klen;
00074 void* data;
00076 ldns_radix_node_t* parent;
00078 uint8_t parent_index;
00080 uint16_t len;
00082 uint16_t offset;
00084 uint16_t capacity;
00086 ldns_radix_array_t* array;
00087 };
00088
00090 struct ldns_radix_t {
00092 ldns_radix_node_t* root;
00094 size_t count;
00095 };
00096
00102 ldns_radix_t* ldns_radix_create(void);
00103
00109 void ldns_radix_init(ldns_radix_t* tree);
00110
00116 void ldns_radix_free(ldns_radix_t* tree);
00117
00127 ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key,
00128 radix_strlen_t len, void* data);
00129
00138 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len);
00139
00148 ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, uint8_t* key,
00149 radix_strlen_t len);
00150
00162 int ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
00163 radix_strlen_t len, ldns_radix_node_t** result);
00164
00171 ldns_radix_node_t* ldns_radix_first(ldns_radix_t* tree);
00172
00179 ldns_radix_node_t* ldns_radix_last(ldns_radix_t* tree);
00180
00187 ldns_radix_node_t* ldns_radix_next(ldns_radix_node_t* node);
00188
00195 ldns_radix_node_t* ldns_radix_prev(ldns_radix_node_t* node);
00196
00205 ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num,
00206 ldns_radix_t** tree2);
00207
00215 ldns_status ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2);
00216
00225 void ldns_radix_traverse_postorder(ldns_radix_node_t* node,
00226 void (*func)(ldns_radix_node_t*, void*), void* arg);
00227
00234 void ldns_radix_printf(FILE* fd, ldns_radix_t* tree);
00235
00236 #ifdef __cplusplus
00237 }
00238 #endif
00239
00240 #endif