/*
 * udbradtree -- radix tree for binary strings for in udb file.
 *
 * Copyright (c) 2011, NLnet Labs.  See LICENSE for license.
 */
#ifndef UDB_RADTREE_H
#define UDB_RADTREE_H
#include "udb.h"
struct udb_radnode;

/** length of the binary string */
typedef uint16_t udb_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.
 *
 * This is the tree on disk representation.  It has _d suffix in the name
 * to help delineate disk structures from normal structures.
 */
struct udb_radtree_d {
	/** root node in tree, to udb_radnode_d */
	struct udb_rel_ptr root;
	/** count of number of elements */
	uint64_t count;
};

/**
 * A radix tree lookup node.  It is stored on disk, and the lookup array
 * is allocated.
 */
struct udb_radnode_d {
	/** data element associated with the binary string up to this node */
	struct udb_rel_ptr elem;
	/** parent node (NULL for the root), to udb_radnode_d */
	struct udb_rel_ptr parent;
	/** the  array structure, for lookup by [byte-offset]. udb_radarray_d */
	struct udb_rel_ptr lookup;
	/** index in the parent lookup array */
	uint8_t pidx;
	/** offset of the lookup array, add to [i] for lookups */
	uint8_t offset;
};

/**
 * radix select edge in array
 * The string for this element is the Nth string in the stringarray.
 */
struct udb_radsel_d {
	/** length of the additional string for this edge,
	 * additional string after the selection-byte for this edge.*/
	udb_radstrlen_type len;
	/** padding for non64bit compilers to 64bit boundaries, to make
	 * the udb file more portable, without this the file would work
	 * on the system it is created on (which is what we promise), but
	 * with this, you have a chance of it working on other platforms */
	uint16_t padding16;
	uint32_t padding32;
	/** node that deals with byte+str, to udb_radnode_d */
	struct udb_rel_ptr node;
};

/**
 * Array of radsel elements.
 * This is the header, the array is allocated contiguously behind it.
 * The strings (often very short) are allocated behind the array.
 * All strings are given the same amount of space (str_cap),
 * so there is capacity*str_cap bytes at the end.
 */
struct udb_radarray_d {
	/** length of the lookup array */
	uint16_t len;
	/** capacity of the lookup array (can be larger than length) */
	uint16_t capacity;
	/** space capacity of for every string */
	udb_radstrlen_type str_cap;
	/** padding to 64bit alignment, just in case compiler goes mad */
	uint16_t padding;
	/** the elements (allocated contiguously after this structure) */
	struct udb_radsel_d array[0];
};

/**
 * Create new radix tree on udb storage
 * @param udb: the udb to allocate space on.
 * @param ptr: ptr to the udbradtree is returned here.  Pass uninitialised.
 * 	type is udb_radtree_d.
 * @return 0 on alloc failure.
 */
int udb_radix_tree_create(udb_base* udb, udb_ptr* ptr);

/**
 * Delete intermediate nodes from radix tree
 * @param udb: the udb.
 * @param rt: radix tree to be cleared. type udb_radtree_d.
 */
void udb_radix_tree_clear(udb_base* udb, udb_ptr* rt);

/**
 * Delete radix tree.
 * You must have deleted the elements, this deletes the nodes.
 * @param udb: the udb.
 * @param rt: radix tree to be deleted. type udb_radtree_d.
 */
void udb_radix_tree_delete(udb_base* udb, udb_ptr* rt);

/**
 * Insert element into radix tree.
 * @param udb: the udb.
 * @param rt: the radix tree, type udb_radtree_d.
 * @param key: key string.
 * @param len: length of key.
 * @param elem: pointer to element data, on the udb store.
 * @param result: the inserted node is set to this value.  Pass uninitialised.
	Not set if the routine fails.
 * @return NULL on failure - out of memory.
 * 	NULL on failure - duplicate entry.
 * 	On success the new radix node for this element (udb_radnode_d).
 */
udb_void udb_radix_insert(udb_base* udb, udb_ptr* rt, uint8_t* k,
	udb_radstrlen_type len, udb_ptr* elem, udb_ptr* result);

/**
 * Delete element from radix tree.
 * @param udb: the udb.
 * @param rt: the radix tree. type udb_radtree_d
 * @param n: radix node for that element. type udb_radnode_d
 * 	if NULL, nothing is deleted.
 */
void udb_radix_delete(udb_base* udb, udb_ptr* rt, udb_ptr* n);

/**
 * Find radix element in tree.
 * @param rt: the radix tree, type udb_radtree_d.
 * @param key: key string.
 * @param len: length of key.
 * @return the radix node or NULL if not found. type udb_radnode_d
 */
udb_void udb_radix_search(udb_ptr* rt, uint8_t* k,
	udb_radstrlen_type len);

/**
 * Find radix element in tree, and if not found, find the closest smaller or
 * equal element in the tree.
 * @param udb: the udb.
 * @param rt: the radix tree, type udb_radtree_d.
 * @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). type udb_radnode_d.
 * 	you can pass an uninitialized ptr, an unlinked or a zeroed one.
 * @return true if exact match, false if no match.
 */
int udb_radix_find_less_equal(udb_base* udb, udb_ptr* rt, uint8_t* k,
	udb_radstrlen_type len, udb_ptr* result);

/**
 * Return the first (smallest) element in the tree.
 * @param udb: the udb.
 * @param rt: the radix tree, type udb_radtree_d.
 * @param p: set to the first node in the tree, or NULL if none.
 * 	type udb_radnode_d.
 * 	pass uninitialised, zero or unlinked udb_ptr.
 */
void udb_radix_first(udb_base* udb, udb_ptr* rt, udb_ptr* p);

/**
 * Return the last (largest) element in the tree.
 * @param udb: the udb.
 * @param rt: the radix tree, type udb_radtree_d.
 * @param p: last node or NULL if none, type udb_radnode_d.
 * 	pass uninitialised, zero or unlinked udb_ptr.
 */
void udb_radix_last(udb_base* udb, udb_ptr* rt, udb_ptr* p);

/**
 * Return the next element.
 * @param udb: the udb.
 * @param n: adjusted to the next element, or NULL if none. type udb_radnode_d.
 */
void udb_radix_next(udb_base* udb, udb_ptr* n);

/**
 * Return the previous element.
 * @param udb: the udb.
 * @param n: adjusted to the prev node or NULL if none. type udb_radnode_d.
 */
void udb_radix_prev(udb_base* udb, udb_ptr* n);

/*
 * Perform a walk through all elements of the tree.
 * node: variable of type struct radnode*.
 * tree: pointer to the tree.
 * for(udb_radix_first(tree, node); node->data; udb_radix_next(node))
*/

/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radtree */
void udb_radix_tree_walk_chunk(void* base, void* d, uint64_t s,
	udb_walk_relptr_cb* cb, void* arg);

/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radnode */
void udb_radix_node_walk_chunk(void* base, void* d, uint64_t s,
	udb_walk_relptr_cb* cb, void* arg);

/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radarray */
void udb_radix_array_walk_chunk(void* base, void* d, uint64_t s,
	udb_walk_relptr_cb* cb, void* arg);

/** get the memory used by the lookup structure for a radnode */
size_t size_of_lookup_ext(udb_ptr* node);

/** insert radtree element, key is a domain name
 * @param udb: udb.
 * @param rt: the tree.
 * @param dname: domain name in uncompressed wireformat.
 * @param dlen: length of k.
 * @param elem: element to store
 * @param result: the inserted node is set to this value.  Pass uninitialised.
	Not set if the routine fails.
 * @return 0 on failure
 */
udb_void udb_radname_insert(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
	size_t dlen, udb_ptr* elem, udb_ptr* result);

/** search for a radname element, key is a domain name.
 * @param udb: udb
 * @param rt: the tree
 * @param dname: domain name in uncompressed wireformat.
 * @param dlen: length of k.
 * @param result: result ptr to store the node into.
 *    may be uninitialized.
 * @return 0 if not found.
 */
int udb_radname_search(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
	size_t dlen, udb_ptr* result);

#define RADNODE(ptr) ((struct udb_radnode_d*)UDB_PTR(ptr))
#define RADTREE(ptr) ((struct udb_radtree_d*)UDB_PTR(ptr))

#endif /* UDB_RADTREE_H */