rbtree.h

Go to the documentation of this file.
00001 /*
00002  * rbtree.h -- generic red-black tree
00003  *
00004  * Copyright (c) 2001-2008, 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 
00046 #ifdef __cplusplus
00047 extern "C" {
00048 #endif
00049 
00056 typedef struct ldns_rbnode_t ldns_rbnode_t;
00060 struct ldns_rbnode_t {
00062         ldns_rbnode_t   *parent;
00064         ldns_rbnode_t   *left;
00066         ldns_rbnode_t   *right;
00068         const void *key;
00070         const void *data;
00072         uint8_t     color;
00073 };
00074 
00076 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node
00077 
00078 extern  ldns_rbnode_t   ldns_rbtree_null_node;
00079 
00081 typedef struct ldns_rbtree_t ldns_rbtree_t;
00083 struct ldns_rbtree_t {
00085         ldns_rbnode_t    *root;
00086 
00088         size_t       count;
00089 
00094         int (*cmp) (const void *, const void *);
00095 };
00096 
00102 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
00103 
00108 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
00109 
00115 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
00116 
00123 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
00124 
00131 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
00132 
00140 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
00141 
00148 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
00149 
00159 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
00160         ldns_rbnode_t **result);
00161 
00167 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
00168 
00174 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
00175 
00181 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
00182 
00188 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
00189 
00195 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
00196 
00201 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
00202 
00207 #define LDNS_RBTREE_FOR(node, type, rbtree) \
00208         for(node=(type)ldns_rbtree_first(rbtree); \
00209                 (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
00210                 node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
00211 
00223 void ldns_traverse_postorder(ldns_rbtree_t* tree,
00224         void (*func)(ldns_rbnode_t*, void*), void* arg);
00225 
00226 #ifdef __cplusplus
00227 }
00228 #endif
00229 
00230 #endif /* UTIL_RBTREE_H_ */

Generated on 22 Sep 2015 for ldns by  doxygen 1.6.1