addrtree.h

Go to the documentation of this file.

/*
 * edns-subnet/addrtree.h -- radix tree for edns subnet cache.
 *
 * Copyright (c) 2013, 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 ADDRTREE_H
#define ADDRTREE_H
 
typedef uint8_t addrlen_t;
typedef uint8_t addrkey_t;
#define KEYWIDTH 8
 
struct addrtree {
    struct addrnode *root;
    unsigned int node_count;
    unsigned int max_node_count;
    size_t size_bytes;
    addrlen_t max_depth;
    void (*delfunc)(void *, void *);
    void *env;
    size_t (*sizefunc)(void *);
    struct addrnode* first;
    struct addrnode *last;
};
 
struct addrnode {
    void *elem;
    time_t ttl;
    addrlen_t scope;
    struct addredge *edge[2];
    struct addredge *parent_edge;
    struct addrnode *prev;
    struct addrnode *next;
};
 
struct addredge {
    addrkey_t *str;
    addrlen_t len;
    struct addrnode *node;
    struct addrnode *parent_node;
    int parent_index;
};

size_t addrtree_size(const struct addrtree *tree);

struct addrtree * 
addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *), 
    size_t (*sizefunc)(void *), void *env, unsigned int max_node_count);

void addrtree_delete(struct addrtree *tree);

void addrtree_insert(struct addrtree *tree, const addrkey_t *addr, 
    addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, 
    time_t now);

struct addrnode * addrtree_find(struct addrtree *tree, 
    const addrkey_t *addr, addrlen_t sourcemask, time_t now);

int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1, 
    const addrkey_t *key2, addrlen_t n);
addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1, 
    addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip);
int unittest_wrapper_addrtree_getbit(const addrkey_t *addr, 
    addrlen_t addrlen, addrlen_t n);
int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1, 
    const addrkey_t *s2, addrlen_t l2,  addrlen_t skip);
#endif /* ADDRTREE_H */