radix.h
Go to the documentation of this file.
1 /*
2  * radix.h -- generic radix tree
3  *
4  * Copyright (c) 2012, NLnet Labs. All rights reserved.
5  *
6  * This software is open source.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  *
15  * Redistributions in binary form must reproduce the above copyright notice,
16  * this list of conditions and the following disclaimer in the documentation
17  * and/or other materials provided with the distribution.
18  *
19  * Neither the name of the NLNET LABS nor the names of its contributors may
20  * be used to endorse or promote products derived from this software without
21  * specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  *
35  */
36 
43 #ifndef LDNS_RADIX_H_
44 #define LDNS_RADIX_H_
45 
46 #include <ldns/error.h>
47 
48 #ifdef __cplusplus
49 extern "C" {
50 #endif
51 
52 typedef uint16_t radix_strlen_t;
55 typedef struct ldns_radix_t ldns_radix_t;
56 
60  uint8_t* str;
65 };
66 
70  uint8_t* key;
74  void* data;
78  uint8_t parent_index;
80  uint16_t len;
82  uint16_t offset;
84  uint16_t capacity;
87 };
88 
90 struct ldns_radix_t {
94  size_t count;
95 };
96 
103 
109 void ldns_radix_init(ldns_radix_t* tree);
110 
116 void ldns_radix_free(ldns_radix_t* tree);
117 
127 ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key,
128  radix_strlen_t len, void* data);
129 
138 void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len);
139 
148 ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, const uint8_t* key,
149  radix_strlen_t len);
150 
162 int ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key,
163  radix_strlen_t len, ldns_radix_node_t** result);
164 
172 
180 
188 
196 
205 ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num,
206  ldns_radix_t** tree2);
207 
216 
226  void (*func)(ldns_radix_node_t*, void*), void* arg);
227 
234 void ldns_radix_printf(FILE* fd, const ldns_radix_t* tree);
235 
236 #ifdef __cplusplus
237 }
238 #endif
239 
240 #endif /* LDNS_RADIX_H_ */
Defines error numbers and functions to translate those to a readable string.
enum ldns_enum_status ldns_status
Definition: error.h:148
ldns_radix_node_t * ldns_radix_prev(ldns_radix_node_t *node)
Previous element.
Definition: radix.c:554
void ldns_radix_init(ldns_radix_t *tree)
Initialize radix tree.
Definition: radix.c:134
void ldns_radix_traverse_postorder(ldns_radix_node_t *node, void(*func)(ldns_radix_node_t *, void *), void *arg)
Call function for all nodes in the tree, such that leaf nodes are called before parent nodes.
Definition: radix.c:740
ldns_status ldns_radix_join(ldns_radix_t *tree1, ldns_radix_t *tree2)
Join two radix trees.
Definition: radix.c:643
void ldns_radix_free(ldns_radix_t *tree)
Free the radix tree.
Definition: radix.c:150
ldns_status ldns_radix_split(ldns_radix_t *tree1, size_t num, ldns_radix_t **tree2)
Split radix tree intwo.
Definition: radix.c:682
ldns_radix_node_t * ldns_radix_last(const ldns_radix_t *tree)
Get the last element in the tree.
Definition: radix.c:499
uint16_t radix_strlen_t
Definition: radix.h:52
ldns_radix_t * ldns_radix_create(void)
Create a new radix tree.
Definition: radix.c:114
ldns_radix_node_t * ldns_radix_search(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Search data in the tree.
Definition: radix.c:334
ldns_radix_node_t * ldns_radix_next(ldns_radix_node_t *node)
Next element.
Definition: radix.c:513
ldns_status ldns_radix_insert(ldns_radix_t *tree, uint8_t *key, radix_strlen_t len, void *data)
Insert data into the tree.
Definition: radix.c:168
ldns_radix_node_t * ldns_radix_first(const ldns_radix_t *tree)
Get the first element in the tree.
Definition: radix.c:480
int ldns_radix_find_less_equal(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len, ldns_radix_node_t **result)
Search data in the tree, and if not found, find the closest smaller element in the tree.
Definition: radix.c:380
void ldns_radix_printf(FILE *fd, const ldns_radix_t *tree)
Print radix tree (for debugging purposes).
Definition: radix.c:624
void * ldns_radix_delete(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Delete data from the tree.
Definition: radix.c:314
Radix node select edge array.
Definition: radix.h:58
ldns_radix_node_t * edge
Node that deals with byte+str.
Definition: radix.h:64
radix_strlen_t len
Length of additional string for this edge.
Definition: radix.h:62
uint8_t * str
Additional string after the selection byte for this edge.
Definition: radix.h:60
A node in a radix tree.
Definition: radix.h:68
ldns_radix_node_t * parent
Parent node.
Definition: radix.h:76
uint16_t offset
Offset of the array.
Definition: radix.h:82
radix_strlen_t klen
Key length corresponding to this node.
Definition: radix.h:72
ldns_radix_array_t * array
Select edge array.
Definition: radix.h:86
uint16_t len
Length of the array.
Definition: radix.h:80
uint16_t capacity
Capacity of the array.
Definition: radix.h:84
void * data
Data corresponding to this node.
Definition: radix.h:74
uint8_t parent_index
Index in the parent node select edge array.
Definition: radix.h:78
uint8_t * key
Key corresponding to this node.
Definition: radix.h:70
An entire radix tree.
Definition: radix.h:90
ldns_radix_node_t * root
Root.
Definition: radix.h:92
size_t count
Number of nodes in tree.
Definition: radix.h:94