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_ */