radix.h
Go to the documentation of this file.
/*
* radix.h -- generic radix tree
*
* Copyright (c) 2012, NLnet Labs. All rights reserved.
*
* This software is open source.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the NLNET LABS nor the names of its contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
#ifndef LDNS_RADIX_H_
#define LDNS_RADIX_H_
#include <ldns/error.h>
#ifdef __cplusplus
extern "C" {
#endif
typedef uint16_t radix_strlen_t;
typedef struct ldns_radix_array_t ldns_radix_array_t;
typedef struct ldns_radix_node_t ldns_radix_node_t;
typedef struct ldns_radix_t ldns_radix_t;
struct ldns_radix_array_t {
uint8_t* str;
radix_strlen_t len;
ldns_radix_node_t* edge;
};
struct ldns_radix_node_t {
uint8_t* key;
radix_strlen_t klen;
void* data;
ldns_radix_node_t* parent;
uint8_t parent_index;
uint16_t len;
uint16_t offset;
uint16_t capacity;
ldns_radix_array_t* array;
};
struct ldns_radix_t {
ldns_radix_node_t* root;
size_t count;
};
ldns_radix_t* ldns_radix_create(void);
void ldns_radix_init(ldns_radix_t* tree);
void ldns_radix_free(ldns_radix_t* tree);
ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key,
radix_strlen_t len, void* data);
void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len);
ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, const uint8_t* key,
radix_strlen_t len);
int ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key,
radix_strlen_t len, ldns_radix_node_t** result);
ldns_radix_node_t* ldns_radix_first(const ldns_radix_t* tree);
ldns_radix_node_t* ldns_radix_last(const ldns_radix_t* tree);
ldns_radix_node_t* ldns_radix_next(ldns_radix_node_t* node);
ldns_radix_node_t* ldns_radix_prev(ldns_radix_node_t* node);
ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num,
ldns_radix_t** tree2);
ldns_status ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2);
void ldns_radix_traverse_postorder(ldns_radix_node_t* node,
void (*func)(ldns_radix_node_t*, void*), void* arg);
void ldns_radix_printf(FILE* fd, const ldns_radix_t* tree);
#ifdef __cplusplus
}
#endif
#endif /* LDNS_RADIX_H_ */
error.h
Defines error numbers and functions to translate those to a readable string.
ldns_status
enum ldns_enum_status ldns_status
Definition error.h:152
ldns_radix_create
ldns_radix_t * ldns_radix_create(void)
Create a new radix tree.
Definition radix.c:114
ldns_radix_init
void ldns_radix_init(ldns_radix_t *tree)
Initialize radix tree.
Definition radix.c:134
ldns_radix_next
ldns_radix_node_t * ldns_radix_next(ldns_radix_node_t *node)
Next element.
Definition radix.c:513
ldns_radix_traverse_postorder
void ldns_radix_traverse_postorder(ldns_radix_node_t *node, void(*func)(ldns_radix_node_t *, void *), void *arg)
Call function for all nodes in the tree, such that leaf nodes are called before parent nodes.
Definition radix.c:740
ldns_radix_join
ldns_status ldns_radix_join(ldns_radix_t *tree1, ldns_radix_t *tree2)
Join two radix trees.
Definition radix.c:643
ldns_radix_first
ldns_radix_node_t * ldns_radix_first(const ldns_radix_t *tree)
Get the first element in the tree.
Definition radix.c:480
ldns_radix_delete
void * ldns_radix_delete(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Delete data from the tree.
Definition radix.c:314
ldns_radix_free
void ldns_radix_free(ldns_radix_t *tree)
Free the radix tree.
Definition radix.c:150
ldns_radix_split
ldns_status ldns_radix_split(ldns_radix_t *tree1, size_t num, ldns_radix_t **tree2)
Split radix tree intwo.
Definition radix.c:682
ldns_radix_search
ldns_radix_node_t * ldns_radix_search(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len)
Search data in the tree.
Definition radix.c:334
radix_strlen_t
uint16_t radix_strlen_t
Definition radix.h:52
ldns_radix_last
ldns_radix_node_t * ldns_radix_last(const ldns_radix_t *tree)
Get the last element in the tree.
Definition radix.c:499
ldns_radix_insert
ldns_status ldns_radix_insert(ldns_radix_t *tree, uint8_t *key, radix_strlen_t len, void *data)
Insert data into the tree.
Definition radix.c:168
ldns_radix_find_less_equal
int ldns_radix_find_less_equal(ldns_radix_t *tree, const uint8_t *key, radix_strlen_t len, ldns_radix_node_t **result)
Search data in the tree, and if not found, find the closest smaller element in the tree.
Definition radix.c:380
ldns_radix_printf
void ldns_radix_printf(FILE *fd, const ldns_radix_t *tree)
Print radix tree (for debugging purposes).
Definition radix.c:624
ldns_radix_prev
ldns_radix_node_t * ldns_radix_prev(ldns_radix_node_t *node)
Previous element.
Definition radix.c:554
ldns_radix_array_t
Radix node select edge array.
Definition radix.h:58
ldns_radix_array_t::edge
ldns_radix_node_t * edge
Node that deals with byte+str.
Definition radix.h:64
ldns_radix_array_t::len
radix_strlen_t len
Length of additional string for this edge.
Definition radix.h:62
ldns_radix_array_t::str
uint8_t * str
Additional string after the selection byte for this edge.
Definition radix.h:60
ldns_radix_node_t
A node in a radix tree.
Definition radix.h:68
ldns_radix_node_t::parent
ldns_radix_node_t * parent
Parent node.
Definition radix.h:76
ldns_radix_node_t::offset
uint16_t offset
Offset of the array.
Definition radix.h:82
ldns_radix_node_t::klen
radix_strlen_t klen
Key length corresponding to this node.
Definition radix.h:72
ldns_radix_node_t::array
ldns_radix_array_t * array
Select edge array.
Definition radix.h:86
ldns_radix_node_t::len
uint16_t len
Length of the array.
Definition radix.h:80
ldns_radix_node_t::capacity
uint16_t capacity
Capacity of the array.
Definition radix.h:84
ldns_radix_node_t::data
void * data
Data corresponding to this node.
Definition radix.h:74
ldns_radix_node_t::parent_index
uint8_t parent_index
Index in the parent node select edge array.
Definition radix.h:78
ldns_radix_node_t::key
uint8_t * key
Key corresponding to this node.
Definition radix.h:70
ldns_radix_t
An entire radix tree.
Definition radix.h:90
ldns_radix_t::root
ldns_radix_node_t * root
Root.
Definition radix.h:92
ldns_radix_t::count
size_t count
Number of nodes in tree.
Definition radix.h:94