rbtree.h
Go to the documentation of this file.
1 /*
2  * rbtree.h -- generic red-black tree
3  *
4  * Copyright (c) 2001-2008, 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 LIMITED
25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  */
36 
43 #ifndef LDNS_RBTREE_H_
44 #define LDNS_RBTREE_H_
45 
46 #ifdef __cplusplus
47 extern "C" {
48 #endif
49 
60 struct ldns_rbnode_t {
68  const void *key;
70  const void *data;
72  uint8_t color;
73 };
74 
76 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node
77 
79 
83 struct ldns_rbtree_t {
86 
88  size_t count;
89 
94  int (*cmp) (const void *, const void *);
95 };
96 
102 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
103 
108 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
109 
115 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
116 
124 
131 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
132 
140 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
141 
148 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
149 
159 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
160  ldns_rbnode_t **result);
161 
168 
175 
182 
189 
195 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
196 
201 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
202 
207 #define LDNS_RBTREE_FOR(node, type, rbtree) \
208  for(node=(type)ldns_rbtree_first(rbtree); \
209  (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
210  node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
211 
224  void (*func)(ldns_rbnode_t*, void*), void* arg);
225 
226 #ifdef __cplusplus
227 }
228 #endif
229 
230 #endif /* UTIL_RBTREE_H_ */