1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
|
/*!
* \file zone-tree.h
*
* \author Lubos Slovak <lubos.slovak@nic.cz>
*
* \brief Zone tree structure and API for manipulating it.
*
* Implemented as AVL tree.
*
* \addtogroup libknot
* @{
*/
/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef _KNOT_ZONE_TREE_H_
#define _KNOT_ZONE_TREE_H_
#include "common/tree.h"
#include "zone/node.h"
/*----------------------------------------------------------------------------*/
typedef struct knot_zone_tree_node {
/*! \brief Structure for connecting this node to an AVL tree. */
TREE_ENTRY(knot_zone_tree_node) avl;
/*! \brief Zone tree data. */
knot_node_t *node;
} knot_zone_tree_node_t;
/*----------------------------------------------------------------------------*/
typedef TREE_HEAD(knot_zone_tree, knot_zone_tree_node) knot_zone_tree_t;
/*----------------------------------------------------------------------------*/
/*!
* \brief Initializes the zone tree.
*
* Does not allocate the structure. Must be called before any use of the tree.
*
* \param tree Zone tree structure to initialize.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
*/
int knot_zone_tree_init(knot_zone_tree_t *tree);
/*!
* \brief Inserts the given node into the zone tree.
*
* \param tree Zone tree to insert the node into.
* \param node Node to insert.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_insert(knot_zone_tree_t *tree, knot_node_t *node);
/*!
* \brief Finds node with the given owner in the zone tree.
*
* \param tree Zone tree to search in.
* \param owner Owner of the node to find.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_find(knot_zone_tree_t *tree,
const knot_dname_t *owner,
const knot_node_t **found);
/*!
* \brief Finds node with the given owner in the zone tree.
*
* \note This function is identical to knot_zone_tree_find() except that it
* returns non-const node.
*
* \param tree Zone tree to search in.
* \param owner Owner of the node to find.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_get(knot_zone_tree_t *tree,
const knot_dname_t *owner,
knot_node_t **found);
/*!
* \brief Tries to find the given domain name in the zone tree and returns the
* associated node and previous node in canonical order.
*
* \param zone Zone to search in.
* \param owner Owner of the node to find.
* \param found Found node.
* \param previous Previous node in canonical order (i.e. the one directly
* preceding \a owner in canonical order, regardless if the name
* is in the zone or not).
*
* \retval > 0 if the domain name was found. In such case \a found holds the
* zone node with \a owner as its owner.
* \a previous is set properly.
* \retval 0 if the domain name was not found. \a found may hold any (or none)
* node. \a previous is set properly.
* \retval KNOT_EINVAL
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_find_less_or_equal(knot_zone_tree_t *tree,
const knot_dname_t *owner,
const knot_node_t **found,
const knot_node_t **previous);
/*!
* \brief Tries to find the given domain name in the zone tree and returns the
* associated node and previous node in canonical order.
*
* \note This function is identical to knot_zone_tree_find_less_or_equal()
* except that it returns non-const nodes.
*
* \param zone Zone to search in.
* \param owner Owner of the node to find.
* \param found Found node.
* \param previous Previous node in canonical order (i.e. the one directly
* preceding \a owner in canonical order, regardless if the name
* is in the zone or not).
*
* \retval > 0 if the domain name was found. In such case \a found holds the
* zone node with \a owner as its owner.
* \a previous is set properly.
* \retval 0 if the domain name was not found. \a found may hold any (or none)
* node. \a previous is set properly.
* \retval KNOT_EINVAL
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_get_less_or_equal(knot_zone_tree_t *tree,
const knot_dname_t *owner,
knot_node_t **found,
knot_node_t **previous);
/*!
* \brief Removes node with the given owner from the zone tree and returns it.
*
* \param tree Zone tree to remove the node from.
* \param owner Owner of the node to find.
* \param removed The removed node.
*
* \retval The removed node.
*/
int knot_zone_tree_remove(knot_zone_tree_t *tree,
const knot_dname_t *owner,
knot_zone_tree_node_t **removed);
/*!
* \brief Applies the given function to each node in the zone.
*
* This function uses in-order depth-first forward traversal, i.e. the function
* is first recursively applied to left subtree, then to the root and then to
* the right subtree.
*
* \note This implies that the zone is stored in a binary tree. Is there a way
* to make this traversal independent on the underlying structure?
*
* \param tree Zone tree to apply the function to.
* \param function Function to be applied to each node of the zone.
* \param data Arbitrary data to be passed to the function.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
*/
int knot_zone_tree_forward_apply_inorder(knot_zone_tree_t *tree,
void (*function)(
knot_zone_tree_node_t *node,
void *data),
void *data);
/*!
* \brief Applies the given function to each node in the zone.
*
* This function uses post-order depth-first forward traversal, i.e. the
* function is first recursively applied to subtrees and then to the root.
*
* \note This implies that the zone is stored in a binary tree. Is there a way
* to make this traversal independent on the underlying structure?
*
* \param tree Zone tree to apply the function to.
* \param function Function to be applied to each node of the zone.
* \param data Arbitrary data to be passed to the function.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
*/
int knot_zone_tree_forward_apply_postorder(knot_zone_tree_t *tree,
void (*function)(
knot_zone_tree_node_t *node,
void *data),
void *data);
/*!
* \brief Applies the given function to each node in the zone.
*
* This function uses in-order depth-first reverse traversal, i.e. the function
* is first recursively applied to right subtree, then to the root and then to
* the left subtree.
*
* \note This implies that the zone is stored in a binary tree. Is there a way
* to make this traversal independent on the underlying structure?
*
* \param tree Zone tree to apply the function to.
* \param function Function to be applied to each node of the zone.
* \param data Arbitrary data to be passed to the function.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
*/
int knot_zone_tree_reverse_apply_inorder(knot_zone_tree_t *tree,
void (*function)(
knot_zone_tree_node_t *node,
void *data),
void *data);
/*!
* \brief Applies the given function to each node in the zone.
*
* This function uses post-order depth-first reverse traversal, i.e. the
* function is first recursively applied to right subtree, then to the
* left subtree and then to the root.
*
* \note This implies that the zone is stored in a binary tree. Is there a way
* to make this traversal independent on the underlying structure?
*
* \param tree Zone tree to apply the function to.
* \param function Function to be applied to each node of the zone.
* \param data Arbitrary data to be passed to the function.
*
* \retval KNOT_EOK
* \retval KNOT_EINVAL
*/
int knot_zone_tree_reverse_apply_postorder(knot_zone_tree_t *tree,
void (*function)(
knot_zone_tree_node_t *node,
void *data),
void *data);
/*!
* \brief Copies the whole zone tree structure (but not the data contained
* within).
*
* \warning This function does not check if the target zone tree is empty,
* it just replaces the root pointer.
*
* \param from Original zone tree.
* \param to Zone tree to copy the original one into.
*
* \retval KNOT_EOK
* \retval KNOT_ENOMEM
*/
int knot_zone_tree_shallow_copy(knot_zone_tree_t *from,
knot_zone_tree_t *to);
int knot_zone_tree_deep_copy(knot_zone_tree_t *from,
knot_zone_tree_t *to);
/*!
* \brief Destroys the zone tree, not touching the saved data.
*
* \param tree Zone tree to be destroyed.
*/
void knot_zone_tree_free(knot_zone_tree_t **tree);
/*!
* \brief Destroys the zone tree, together with the saved data.
*
* \param tree Zone tree to be destroyed.
* \param free_owners Set to <> 0 if owners of the nodes should be destroyed
* as well. Set to 0 otherwise.
*/
void knot_zone_tree_deep_free(knot_zone_tree_t **tree);
/*----------------------------------------------------------------------------*/
#endif // _KNOT_ZONE_TREE_H_
/*! @} */
|
