rbtree.h

Go to the documentation of this file.
00001 /*
00002  * rbtree.h -- generic red-black tree
00003  *
00004  * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
00005  * 
00006  * This software is open source.
00007  * 
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 
00012  * Redistributions of source code must retain the above copyright notice,
00013  * this list of conditions and the following disclaimer.
00014  * 
00015  * Redistributions in binary form must reproduce the above copyright notice,
00016  * this list of conditions and the following disclaimer in the documentation
00017  * and/or other materials provided with the distribution.
00018  * 
00019  * Neither the name of the NLNET LABS nor the names of its contributors may
00020  * be used to endorse or promote products derived from this software without
00021  * specific prior written permission.
00022  * 
00023  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00024  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
00025  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00026  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
00027  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00028  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00029  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00030  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00031  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00032  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00033  * POSSIBILITY OF SUCH DAMAGE.
00034  *
00035  */
00036 
00043 #ifndef LDNS_RBTREE_H_
00044 #define LDNS_RBTREE_H_
00045 
00051 typedef struct ldns_rbnode_t ldns_rbnode_t;
00055 struct ldns_rbnode_t {
00057         ldns_rbnode_t   *parent;
00059         ldns_rbnode_t   *left;
00061         ldns_rbnode_t   *right;
00063         const void *key;
00065         const void *data;
00067         uint8_t     color;
00068 };
00069 
00071 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node
00072 
00073 extern  ldns_rbnode_t   ldns_rbtree_null_node;
00074 
00076 typedef struct ldns_rbtree_t ldns_rbtree_t;
00078 struct ldns_rbtree_t {
00080         ldns_rbnode_t    *root;
00081 
00083         size_t       count;
00084 
00089         int (*cmp) (const void *, const void *);
00090 };
00091 
00097 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
00098 
00103 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
00104 
00110 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
00111 
00118 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
00119 
00126 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
00127 
00135 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
00136 
00143 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
00144 
00154 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, 
00155         ldns_rbnode_t **result);
00156 
00162 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
00163 
00169 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
00170 
00176 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
00177 
00183 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
00184 
00190 ldns_rbtree_t *ldns_dnssec_rbtree_split(ldns_rbtree_t *tree, 
00191                                                                 size_t elements);
00192 
00197 void ldns_dnssec_rbtree_join(ldns_rbtree_t *tree1,
00198                                             ldns_rbtree_t *tree2);
00199 
00204 #define LDNS_RBTREE_FOR(node, type, rbtree) \
00205         for(node=(type)ldns_rbtree_first(rbtree); \
00206                 (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
00207                 node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
00208 
00220 void ldns_traverse_postorder(ldns_rbtree_t* tree, 
00221         void (*func)(ldns_rbnode_t*, void*), void* arg);
00222 
00223 #endif /* UTIL_RBTREE_H_ */

Generated on Fri Aug 8 02:52:40 2008 for ldns by  doxygen 1.5.6