radix.h

Go to the documentation of this file.
00001 /*
00002  * radix.h -- generic radix tree
00003  *
00004  * Copyright (c) 2012, 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_RADIX_H_
00044 #define LDNS_RADIX_H_
00045 
00046 #include <ldns/error.h>
00047 
00048 #ifdef __cplusplus
00049 extern "C" {
00050 #endif
00051 
00052 typedef uint16_t radix_strlen_t;
00053 typedef struct ldns_radix_array_t ldns_radix_array_t;
00054 typedef struct ldns_radix_node_t ldns_radix_node_t;
00055 typedef struct ldns_radix_t ldns_radix_t;
00056 
00058 struct ldns_radix_array_t {
00060         uint8_t* str;
00062         radix_strlen_t len;
00064         ldns_radix_node_t* edge;
00065 };
00066 
00068 struct ldns_radix_node_t {
00070         uint8_t* key;
00072         radix_strlen_t klen;
00074         void* data;
00076         ldns_radix_node_t* parent;
00078         uint8_t parent_index;
00080         uint16_t len;
00082         uint16_t offset;
00084         uint16_t capacity;
00086         ldns_radix_array_t* array;
00087 };
00088 
00090 struct ldns_radix_t {
00092         ldns_radix_node_t* root;
00094         size_t count;
00095 };
00096 
00102 ldns_radix_t* ldns_radix_create(void);
00103 
00109 void ldns_radix_init(ldns_radix_t* tree);
00110 
00116 void ldns_radix_free(ldns_radix_t* tree);
00117 
00127 ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key,
00128         radix_strlen_t len, void* data);
00129 
00138 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len);
00139 
00148 ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, uint8_t* key,
00149         radix_strlen_t len);
00150 
00162 int ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
00163         radix_strlen_t len, ldns_radix_node_t** result);
00164 
00171 ldns_radix_node_t* ldns_radix_first(ldns_radix_t* tree);
00172 
00179 ldns_radix_node_t* ldns_radix_last(ldns_radix_t* tree);
00180 
00187 ldns_radix_node_t* ldns_radix_next(ldns_radix_node_t* node);
00188 
00195 ldns_radix_node_t* ldns_radix_prev(ldns_radix_node_t* node);
00196 
00205 ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num,
00206         ldns_radix_t** tree2);
00207 
00215 ldns_status ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2);
00216 
00225 void ldns_radix_traverse_postorder(ldns_radix_node_t* node,
00226         void (*func)(ldns_radix_node_t*, void*), void* arg);
00227 
00234 void ldns_radix_printf(FILE* fd, ldns_radix_t* tree);
00235 
00236 #ifdef __cplusplus
00237 }
00238 #endif
00239 
00240 #endif /* LDNS_RADIX_H_ */

Generated on 21 Apr 2016 for ldns by  doxygen 1.6.1