Electroneum
addrtree.h
Go to the documentation of this file.
1 /*
2  * edns-subnet/addrtree.h -- radix tree for edns subnet cache.
3  *
4  * Copyright (c) 2013, 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 
58 #ifndef ADDRTREE_H
59 #define ADDRTREE_H
60 
63 #define KEYWIDTH 8
64 
65 struct addrtree {
66  struct addrnode *root;
69  unsigned int node_count;
72  unsigned int max_node_count;
74  size_t size_bytes;
79  void (*delfunc)(void *, void *);
81  void *env;
84  size_t (*sizefunc)(void *);
86  struct addrnode* first;
88  struct addrnode *last;
89 };
90 
91 struct addrnode {
93  void *elem;
95  time_t ttl;
99  struct addredge *edge[2];
103  struct addrnode *prev;
105  struct addrnode *next;
106 };
107 
108 struct addredge {
114  struct addrnode *node;
119 };
120 
126 size_t addrtree_size(const struct addrtree *tree);
127 
138 struct addrtree *
139 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
140  size_t (*sizefunc)(void *), void *env, unsigned int max_node_count);
141 
146 void addrtree_delete(struct addrtree *tree);
147 
162 void addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
163  addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
164  time_t now);
165 
175 struct addrnode * addrtree_find(struct addrtree *tree,
176  const addrkey_t *addr, addrlen_t sourcemask, time_t now);
177 
180  const addrkey_t *key2, addrlen_t n);
182  addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip);
184  addrlen_t addrlen, addrlen_t n);
186  const addrkey_t *s2, addrlen_t l2, addrlen_t skip);
187 #endif /* ADDRTREE_H */
struct addrnode * root
Definition: addrtree.h:66
int unittest_wrapper_addrtree_getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
time_t ttl
Definition: addrtree.h:95
uint8_t addrkey_t
Definition: addrtree.h:62
addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
void * elem
Definition: addrtree.h:93
struct addredge * parent_edge
Definition: addrtree.h:101
unsigned char uint8_t
Definition: stdint.h:124
int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
struct addrtree * addrtree_create(addrlen_t max_depth, void(*delfunc)(void *, void *), size_t(*sizefunc)(void *), void *env, unsigned int max_node_count)
size_t addrtree_size(const struct addrtree *tree)
void addrtree_delete(struct addrtree *tree)
unsigned int max_node_count
Definition: addrtree.h:72
void addrtree_insert(struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, time_t now)
addrlen_t scope
Definition: addrtree.h:97
uint8_t addrlen_t
Definition: addrtree.h:61
struct addrnode * node
Definition: addrtree.h:114
struct addredge * edge[2]
Definition: addrtree.h:99
addrlen_t max_depth
Definition: addrtree.h:76
struct addrnode * first
Definition: addrtree.h:86
void * env
Definition: addrtree.h:81
addrlen_t len
Definition: addrtree.h:112
struct addrnode * next
Definition: addrtree.h:105
unsigned int node_count
Definition: addrtree.h:69
void(* delfunc)(void *, void *)
Definition: addrtree.h:79
size_t size_bytes
Definition: addrtree.h:74
addrkey_t * str
Definition: addrtree.h:110
struct addrnode * addrtree_find(struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, time_t now)
struct addrnode * parent_node
Definition: addrtree.h:116
struct addrnode * prev
Definition: addrtree.h:103
struct addrnode * last
Definition: addrtree.h:88
int parent_index
Definition: addrtree.h:118
int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
size_t(* sizefunc)(void *)
Definition: addrtree.h:84