2  * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
36  * addrtree -- radix tree for edns subnet cache.
83  * @param tree: Tree the node lives in.
90 node_create(struct addrtree *tree, void *elem, addrlen_t scope,   in node_create()  argument
97 	tree->node_count++;  in node_create()
110  * @param tree: tree the node lives in
115 node_size(const struct addrtree *tree, const struct addrnode *n)  in node_size()  argument
118 		(n->elem?tree->sizefunc(n->elem):0);  in node_size()
125 	struct addrtree *tree;  in addrtree_create()  local
128 	tree = (struct addrtree *)calloc(1, sizeof(*tree));  in addrtree_create()
129 	if (!tree)  in addrtree_create()
131 	tree->root = node_create(tree, NULL, 0, 0);  in addrtree_create()
132 	if (!tree->root) {  in addrtree_create()
133 		free(tree);  in addrtree_create()
136 	tree->size_bytes = sizeof *tree + sizeof *tree->root;  in addrtree_create()
137 	tree->first = NULL;  in addrtree_create()
138 	tree->last = NULL;  in addrtree_create()
139 	tree->max_depth = max_depth;  in addrtree_create()
140 	tree->delfunc = delfunc;  in addrtree_create()
141 	tree->sizefunc = sizefunc;  in addrtree_create()
142 	tree->env = env;  in addrtree_create()
143 	tree->node_count = 0;  in addrtree_create()
144 	tree->max_node_count = max_node_count;  in addrtree_create()
145 	return tree;  in addrtree_create()
150  * @param tree: tree the node lives in.
154 clean_node(struct addrtree *tree, struct addrnode *node)  in clean_node()  argument
157 	tree->size_bytes -= tree->sizefunc(node->elem);  in clean_node()
158 	tree->delfunc(tree->env, node->elem);  in clean_node()
165 lru_pop(struct addrtree *tree, struct addrnode *node)  in lru_pop()  argument
167 	if (node == tree->first) {  in lru_pop()
169 			tree->first = NULL;  in lru_pop()
170 			tree->last = NULL;  in lru_pop()
172 			tree->first = node->next;  in lru_pop()
173 			tree->first->prev = NULL;  in lru_pop()
175 	} else if (node == tree->last) { /* but not the first */  in lru_pop()
176 		tree->last = node->prev;  in lru_pop()
177 		tree->last->next = NULL;  in lru_pop()
186 lru_push(struct addrtree *tree, struct addrnode *node)  in lru_push()  argument
188 	if (!tree->first) {  in lru_push()
189 		tree->first = node;  in lru_push()
192 		tree->last->next = node;  in lru_push()
193 		node->prev = tree->last;  in lru_push()
195 	tree->last = node;  in lru_push()
201 lru_update(struct addrtree *tree, struct addrnode *node)  in lru_update()  argument
203 	if (tree->root == node) return;  in lru_update()
204 	lru_pop(tree, node);  in lru_update()
205 	lru_push(tree, node);  in lru_update()
209  * Purge a node from the tree. Node and parentedge are cleaned and 
211  * @param tree: Tree the node lives in.
215 purge_node(struct addrtree *tree, struct addrnode *node)  in purge_node()  argument
221 	clean_node(tree, node);  in purge_node()
224 	tree->node_count--;  in purge_node()
232 	tree->size_bytes -= node_size(tree, node);  in purge_node()
235 	lru_pop(tree, node);  in purge_node()
241  * @param tree: Tree to be cleaned up.
244 lru_cleanup(struct addrtree *tree)  in lru_cleanup()  argument
248 	if (tree->max_node_count == 0) return;  in lru_cleanup()
249 	while (tree->node_count > tree->max_node_count) {  in lru_cleanup()
250 		n = tree->first;  in lru_cleanup()
256 			lru_update(tree, n);  in lru_cleanup()
260 		purge_node(tree, n);  in lru_cleanup()
266 			purge_node(tree, p);  in lru_cleanup()
272 addrtree_size(const struct addrtree *tree)  in addrtree_size()  argument
274 	return tree?tree->size_bytes:0;  in addrtree_size()
277 void addrtree_delete(struct addrtree *tree)  in addrtree_delete()  argument
280 	if (!tree) return;  in addrtree_delete()
281 	clean_node(tree, tree->root);  in addrtree_delete()
282 	free(tree->root);  in addrtree_delete()
283 	tree->size_bytes -= sizeof(struct addrnode);  in addrtree_delete()
284 	while ((n = tree->first)) {  in addrtree_delete()
285 		tree->first = n->next;  in addrtree_delete()
286 		clean_node(tree, n);  in addrtree_delete()
287 		tree->size_bytes -= node_size(tree, n);  in addrtree_delete()
292 	log_assert(sizeof *tree == addrtree_size(tree));  in addrtree_delete()
293 	free(tree);  in addrtree_delete()
361 addrtree_insert(struct addrtree *tree, const addrkey_t *addr,   in addrtree_insert()  argument
370 	node = tree->root;  in addrtree_insert()
374 	if (tree->max_depth < scope) scope = tree->max_depth;  in addrtree_insert()
384 			clean_node(tree, node);  in addrtree_insert()
389 			tree->size_bytes += tree->sizefunc(elem);  in addrtree_insert()
399 			purge_node(tree, edge->node);  in addrtree_insert()
404 			newnode = node_create(tree, elem, scope, ttl);  in addrtree_insert()
408 				clean_node(tree, newnode);  in addrtree_insert()
409 				tree->node_count--;  in addrtree_insert()
413 			tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
414 			lru_push(tree, newnode);  in addrtree_insert()
415 			lru_cleanup(tree);  in addrtree_insert()
431 		if (!(newnode = node_create(tree, NULL, 0, 0)))  in addrtree_insert()
436 			clean_node(tree, newnode);  in addrtree_insert()
437 			tree->node_count--;  in addrtree_insert()
441 		lru_push(tree, newnode);  in addrtree_insert()
456 		tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
461 			newnode = node_create(tree, elem, scope, ttl);  in addrtree_insert()
464 				clean_node(tree, newnode);  in addrtree_insert()
465 				tree->node_count--;  in addrtree_insert()
469 			tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
470 			lru_push(tree, newnode);  in addrtree_insert()
472 		lru_cleanup(tree);  in addrtree_insert()
478 addrtree_find(struct addrtree *tree, const addrkey_t *addr,   in addrtree_find()  argument
481 	struct addrnode *node = tree->root;  in addrtree_find()
500 				lru_update(tree, node);  in addrtree_find()