/*
 * radtree -- generic radix tree for binary strings.
 *
 * Copyright (c) 2010, NLnet Labs.  See LICENSE for license.
 */
#ifndef RADTREE_H
#define RADTREE_H

struct radnode;
struct region;

/** length of the binary string */
typedef uint16_t radstrlen_type;

/**
 * The radix tree
 *
 * The elements are stored based on binary strings(0-255) of a given length.
 * They are sorted, a prefix is sorted before its suffixes.
 * If you want to know the key string, you should store it yourself, the
 * tree stores it in the parts necessary for lookup.
 * For binary strings for domain names see the radname routines.
 */
struct radtree {
        /** root node in tree */
        struct radnode* root;
        /** count of number of elements */
        size_t count;
        /** region for allocation */
        struct region* region;
};

/**
 * A radix tree lookup node.
 * The array is malloced separately from the radnode.
 */
struct radnode {
        /** data element associated with the binary string up to this node */
        void* elem;
        /** parent node (NULL for the root) */
        struct radnode* parent;
        /** index in the parent lookup array */
        uint8_t pidx;
        /** offset of the lookup array, add to [i] for lookups */
        uint8_t offset;
        /** length of the lookup array */
        uint16_t len;
        /** capacity of the lookup array (can be larger than length) */
        uint16_t capacity;
        /** the lookup array by [byte-offset] */
        struct radsel* array; 
} ATTR_PACKED;

/**
 * radix select edge in array
 */
struct radsel {
        /** additional string after the selection-byte for this edge. */
        uint8_t* str;
        /** length of the additional string for this edge */
        radstrlen_type len;
        /** node that deals with byte+str */
        struct radnode* node;
} ATTR_PACKED;

/**
 * Create new radix tree
 * @param region: where to allocate the tree.
 * @return new tree or NULL on alloc failure.
 */
struct radtree* radix_tree_create(struct region* region);

/**
 * Init new radix tree.
 * @param rt: radix tree to be initialized.
 */
void radix_tree_init(struct radtree* rt);

/**
 * Delete intermediate nodes from radix tree
 * @param rt: radix tree to be initialized.
 */
void radix_tree_clear(struct radtree* rt);

/**
 * Delete radix tree.
 * @param rt: radix tree to be deleted.
 */
void radix_tree_delete(struct radtree* rt);


/**
 * Insert element into radix tree.
 * @param rt: the radix tree.
 * @param key: key string.
 * @param len: length of key.
 * @param elem: pointer to element data.
 * @return NULL on failure - out of memory.
 *      NULL on failure - duplicate entry.
 *      On success the new radix node for this element.
 */
struct radnode* radix_insert(struct radtree* rt, uint8_t* k,
        radstrlen_type len, void* elem);

/**
 * Delete element from radix tree.
 * @param rt: the radix tree.
 * @param n: radix node for that element.
 *      if NULL, nothing is deleted.
 */
void radix_delete(struct radtree* rt, struct radnode* n);

/**
 * Find radix element in tree.
 * @param rt: the radix tree.
 * @param key: key string.
 * @param len: length of key.
 * @return the radix node or NULL if not found.
 */
struct radnode* radix_search(struct radtree* rt, uint8_t* k,
        radstrlen_type len);

/**
 * Find radix element in tree, and if not found, find the closest smaller or
 * equal element in the tree.
 * @param rt: the radix tree.
 * @param key: key string.
 * @param len: length of key.
 * @param result: returns the radix node or closest match (NULL if key is
 *      smaller than the smallest key in the tree).
 * @return true if exact match, false if no match.
 */
int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_type len,
        struct radnode** result);

/**
 * Return the first (smallest) element in the tree.
 * @param rt: the radix tree.
 * @return: first node or NULL if none.
 */
struct radnode* radix_first(struct radtree* rt);

/**
 * Return the last (largest) element in the tree.
 * @param rt: the radix tree.
 * @return: last node or NULL if none.
 */
struct radnode* radix_last(struct radtree* rt);

/**
 * Return the next element.
 * @param n: the element to go from.
 * @return: next node or NULL if none.
 */
struct radnode* radix_next(struct radnode* n);

/**
 * Return the previous element.
 * @param n: the element to go from.
 * @return: prev node or NULL if none.
 */
struct radnode* radix_prev(struct radnode* n);

/*
 * Perform a walk through all elements of the tree.
 * node: variable of type struct radnode*.
 * tree: pointer to the tree.
 *      for(node=radix_first(tree); node; node=radix_next(node))
*/

/**
 * Create a binary string to represent a domain name
 * @param k: string buffer to store into
 * @param len: output length, initially, the max, output the result.
 * @param dname: the domain name to convert, in wireformat.
 * @param dlen: length of space for dname.
 */
void radname_d2r(uint8_t* k, radstrlen_type* len, const uint8_t* dname,
        size_t dlen);

/**
 * Convert a binary string back to a domain name.
 * @param k: the binary string.
 * @param len: length of k.
 * @param dname: buffer to store domain name into.
 * @param dlen: length of dname (including root label).
 */
void radname_r2d(uint8_t* k, radstrlen_type len, uint8_t* dname, size_t* dlen);

/**
 * Search the radix tree using a domain name.
 * The name is internally converted to a radname.
 * @param rt: tree
 * @param d: domain name, no compression pointers allowed.
 * @param max: max length to go from d.
 * @return NULL on parse error or if not found.
 */
struct radnode* radname_search(struct radtree* rt, const uint8_t* d,
        size_t max);

/**
 * Find radix element in tree by domain name, and if not found,
 * find the closest smaller or equal element in the tree.
 * The name is internally converted to a radname (same sorting order).
 * @param rt: the radix tree.
 * @param d: domain name, no compression pointers allowed.
 * @param max: max length to go from d.
 * @param result: returns the radix node or closest match (NULL if key is
 *      smaller than the smallest key in the tree).
 *      could result in NULL on a parse error as well (with return false).
 * @return true if exact match, false if no match.
 */
int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max,
        struct radnode** result);

/**
 * Insert radix element by domain name.
 * @param rt: the radix tree
 * @param d: domain name, no compression pointers.
 * @param max: max length from d.
 * @param elem: the element pointer to insert.
 * @return NULL on failure - out of memory.
 *      NULL on failure - duplicate entry.
 *      NULL on failure - parse error.
 *      On success the radix node for this element.
 */
struct radnode* radname_insert(struct radtree* rt, const uint8_t* d,
        size_t max, void* elem);

/**
 * Delete element by domain name from radix tree.
 * @param rt: the radix tree.
 * @param d: the domain name.  If it is not in the tree nothing happens.
 * @param max: max length.
 */
void radname_delete(struct radtree* rt, const uint8_t* d, size_t max);

/** number of bytes in common in strings */
radstrlen_type bstr_common_ext(uint8_t* x, radstrlen_type xlen, uint8_t* y,
        radstrlen_type ylen);
/** true if one is prefix of the other */
int bstr_is_prefix_ext(uint8_t* p, radstrlen_type plen, uint8_t* x,
        radstrlen_type xlen);

#endif /* RADTREE_H */