rbtree.h revision 256281
142421Syokota/* 242421Syokota * rbtree.h -- generic red-black tree 342421Syokota * 442421Syokota * Copyright (c) 2001-2007, NLnet Labs. All rights reserved. 542421Syokota * 642421Syokota * This software is open source. 742421Syokota * 842421Syokota * Redistribution and use in source and binary forms, with or without 942421Syokota * modification, are permitted provided that the following conditions 1042421Syokota * are met: 1142421Syokota * 1242421Syokota * Redistributions of source code must retain the above copyright notice, 1342421Syokota * this list of conditions and the following disclaimer. 1442421Syokota * 1542421Syokota * Redistributions in binary form must reproduce the above copyright notice, 1642421Syokota * this list of conditions and the following disclaimer in the documentation 1742421Syokota * and/or other materials provided with the distribution. 1842421Syokota * 1942421Syokota * Neither the name of the NLNET LABS nor the names of its contributors may 2042421Syokota * be used to endorse or promote products derived from this software without 2142421Syokota * specific prior written permission. 2242421Syokota * 2342421Syokota * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2442421Syokota * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 2542421Syokota * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 2642421Syokota * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 2742421Syokota * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28119418Sobrien * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29119418Sobrien * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30119418Sobrien * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 3142421Syokota * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 3242421Syokota * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 3342421Syokota * POSSIBILITY OF SUCH DAMAGE. 3442421Syokota * 3542421Syokota */ 3642421Syokota 3742421Syokota/** 38139193Sphk * \file 3942421Syokota * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use 40164033Srwatson * in unbound (memory allocation, logging and so on). 41112050Sdwmalone */ 42180777Sed 43112050Sdwmalone#ifndef UTIL_RBTREE_H_ 4442421Syokota#define UTIL_RBTREE_H_ 4542421Syokota 4666834Sphk/** 4742421Syokota * This structure must be the first member of the data structure in 4842421Syokota * the rbtree. This allows easy casting between an rbnode_t and the 4942421Syokota * user data (poor man's inheritance). 50183397Sed */ 5150154Syokotatypedef struct rbnode_t rbnode_t; 52193512Sed/** 53193512Sed * The rbnode_t struct definition. 54193512Sed */ 5550154Syokotastruct rbnode_t { 5650154Syokota /** parent in rbtree, RBTREE_NULL for root */ 5750154Syokota rbnode_t *parent; 5850154Syokota /** left node (smaller items) */ 59193512Sed rbnode_t *left; 60193512Sed /** right node (larger items) */ 61193512Sed rbnode_t *right; 6250154Syokota /** pointer to sorting key */ 6350154Syokota const void *key; 6460938Sjake /** colour of this node */ 65127751Sdes uint8_t color; 6654545Syokota}; 6778161Speter 6878161Speter/** The nullpointer, points to empty node */ 6942421Syokota#define RBTREE_NULL &rbtree_null_node 7042421Syokota/** the global empty node */ 7142421Syokotaextern rbnode_t rbtree_null_node; 7242421Syokota 7342421Syokota/** An entire red black tree */ 7442421Syokotatypedef struct rbtree_t rbtree_t; 7542421Syokota/** definition for tree struct */ 7642564Syokotastruct rbtree_t { 7742564Syokota /** The root of the red-black tree */ 7842421Syokota rbnode_t *root; 7942564Syokota 8042421Syokota /** The number of the nodes in the tree */ 8142421Syokota size_t count; 8242421Syokota 83112050Sdwmalone /** 84248085Smarius * Key compare function. <0,0,>0 like strcmp. 85112050Sdwmalone * Return 0 on two NULL ptrs. 86112050Sdwmalone */ 87112050Sdwmalone int (*cmp) (const void *, const void *); 8842421Syokota}; 8942421Syokota 9044628Syokota/** 9142421Syokota * Create new tree (malloced) with given key compare function. 9242421Syokota * @param cmpf: compare function (like strcmp) takes pointers to two keys. 9342421Syokota * @return: new tree, empty. 9442421Syokota */ 9542421Syokotarbtree_t *rbtree_create(int (*cmpf)(const void *, const void *)); 9642421Syokota 9742421Syokota/** 9842421Syokota * Init a new tree (malloced by caller) with given key compare function. 9942421Syokota * @param rbtree: uninitialised memory for new tree, returned empty. 10069781Sdwmalone * @param cmpf: compare function (like strcmp) takes pointers to two keys. 10144628Syokota */ 10244628Syokotavoid rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); 103127752Sdes 10444628Syokota/** 10569781Sdwmalone * Insert data into the tree. 10669781Sdwmalone * @param rbtree: tree to insert to. 10744628Syokota * @param data: element to insert. 10844628Syokota * @return: data ptr or NULL if key already present. 10944628Syokota */ 110127752Sdesrbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); 11144628Syokota 11242421Syokota/** 11342421Syokota * Delete element from tree. 11442421Syokota * @param rbtree: tree to delete from. 11542421Syokota * @param key: key of item to delete. 11642421Syokota * @return: node that is now unlinked from the tree. User to delete it. 11742421Syokota * returns 0 if node not present 11842421Syokota */ 11942421Syokotarbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); 12042421Syokota 12142421Syokota/** 12242421Syokota * Find key in tree. Returns NULL if not found. 12342421Syokota * @param rbtree: tree to find in. 12442421Syokota * @param key: key that must match. 12544628Syokota * @return: node that fits or NULL. 126127752Sdes */ 12742421Syokotarbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); 12842421Syokota 12942421Syokota/** 13042421Syokota * Find, but match does not have to be exact. 13142421Syokota * @param rbtree: tree to find in. 13242421Syokota * @param key: key to find position of. 13342421Syokota * @param result: set to the exact node if present, otherwise to element that 13442421Syokota * precedes the position of key in the tree. NULL if no smaller element. 13542421Syokota * @return: true if exact match in result. Else result points to <= element, 13642421Syokota * or NULL if key is smaller than the smallest key. 13742421Syokota */ 13842421Syokotaint rbtree_find_less_equal(rbtree_t *rbtree, const void *key, 13942421Syokota rbnode_t **result); 14042421Syokota 14142421Syokota/** 14242421Syokota * Returns first (smallest) node in the tree 14342421Syokota * @param rbtree: tree 14442421Syokota * @return: smallest element or NULL if tree empty. 14544628Syokota */ 14642421Syokotarbnode_t *rbtree_first(rbtree_t *rbtree); 14742421Syokota 14842421Syokota/** 14942421Syokota * Returns last (largest) node in the tree 15042421Syokota * @param rbtree: tree 15142421Syokota * @return: largest element or NULL if tree empty. 15242421Syokota */ 15342421Syokotarbnode_t *rbtree_last(rbtree_t *rbtree); 15444628Syokota 15544628Syokota/** 15654382Syokota * Returns next larger node in the tree 15780040Syokota * @param rbtree: tree 15842421Syokota * @return: next larger element or NULL if no larger in tree. 15942421Syokota */ 16042421Syokotarbnode_t *rbtree_next(rbnode_t *rbtree); 16142421Syokota 16242421Syokota/** 16342421Syokota * Returns previous smaller node in the tree 16442421Syokota * @param rbtree: tree 16542421Syokota * @return: previous smaller element or NULL if no previous in tree. 16642421Syokota */ 16742421Syokotarbnode_t *rbtree_previous(rbnode_t *rbtree); 16842421Syokota 16942421Syokota/** 17054545Syokota * Call with node=variable of struct* with rbnode_t as first element. 17154545Syokota * with type is the type of a pointer to that struct. 17254545Syokota */ 17354545Syokota#define RBTREE_FOR(node, type, rbtree) \ 17454545Syokota for(node=(type)rbtree_first(rbtree); \ 175127752Sdes (rbnode_t*)node != RBTREE_NULL; \ 17654545Syokota node = (type)rbtree_next((rbnode_t*)node)) 177127752Sdes 17854545Syokota/** 17954545Syokota * Call function for all elements in the redblack tree, such that 18054545Syokota * leaf elements are called before parent elements. So that all 18154545Syokota * elements can be safely free()d. 18254545Syokota * Note that your function must not remove the nodes from the tree. 18360938Sjake * Since that may trigger rebalances of the rbtree. 18454545Syokota * @param tree: the tree 185127752Sdes * @param func: function called with element and user arg. 18654545Syokota * The function must not alter the rbtree. 18754545Syokota * @param arg: user argument. 18842421Syokota */ 18942421Syokotavoid traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), 19042421Syokota void* arg); 19142421Syokota 19247295Syokota#endif /* UTIL_RBTREE_H_ */ 19347295Syokota