1238106Sdes/* 2238106Sdes * rbtree.h -- generic red-black tree 3238106Sdes * 4238106Sdes * Copyright (c) 2001-2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes * 35238106Sdes */ 36238106Sdes 37238106Sdes/** 38238106Sdes * \file 39238106Sdes * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use 40238106Sdes * in unbound (memory allocation, logging and so on). 41238106Sdes */ 42238106Sdes 43238106Sdes#ifndef UTIL_RBTREE_H_ 44238106Sdes#define UTIL_RBTREE_H_ 45238106Sdes 46238106Sdes/** 47238106Sdes * This structure must be the first member of the data structure in 48238106Sdes * the rbtree. This allows easy casting between an rbnode_t and the 49238106Sdes * user data (poor man's inheritance). 50238106Sdes */ 51238106Sdestypedef struct rbnode_t rbnode_t; 52238106Sdes/** 53238106Sdes * The rbnode_t struct definition. 54238106Sdes */ 55238106Sdesstruct rbnode_t { 56238106Sdes /** parent in rbtree, RBTREE_NULL for root */ 57238106Sdes rbnode_t *parent; 58238106Sdes /** left node (smaller items) */ 59238106Sdes rbnode_t *left; 60238106Sdes /** right node (larger items) */ 61238106Sdes rbnode_t *right; 62238106Sdes /** pointer to sorting key */ 63238106Sdes const void *key; 64238106Sdes /** colour of this node */ 65238106Sdes uint8_t color; 66238106Sdes}; 67238106Sdes 68238106Sdes/** The nullpointer, points to empty node */ 69238106Sdes#define RBTREE_NULL &rbtree_null_node 70238106Sdes/** the global empty node */ 71238106Sdesextern rbnode_t rbtree_null_node; 72238106Sdes 73238106Sdes/** An entire red black tree */ 74238106Sdestypedef struct rbtree_t rbtree_t; 75238106Sdes/** definition for tree struct */ 76238106Sdesstruct rbtree_t { 77238106Sdes /** The root of the red-black tree */ 78238106Sdes rbnode_t *root; 79238106Sdes 80238106Sdes /** The number of the nodes in the tree */ 81238106Sdes size_t count; 82238106Sdes 83238106Sdes /** 84238106Sdes * Key compare function. <0,0,>0 like strcmp. 85238106Sdes * Return 0 on two NULL ptrs. 86238106Sdes */ 87238106Sdes int (*cmp) (const void *, const void *); 88238106Sdes}; 89238106Sdes 90238106Sdes/** 91238106Sdes * Create new tree (malloced) with given key compare function. 92238106Sdes * @param cmpf: compare function (like strcmp) takes pointers to two keys. 93238106Sdes * @return: new tree, empty. 94238106Sdes */ 95238106Sdesrbtree_t *rbtree_create(int (*cmpf)(const void *, const void *)); 96238106Sdes 97238106Sdes/** 98238106Sdes * Init a new tree (malloced by caller) with given key compare function. 99238106Sdes * @param rbtree: uninitialised memory for new tree, returned empty. 100238106Sdes * @param cmpf: compare function (like strcmp) takes pointers to two keys. 101238106Sdes */ 102238106Sdesvoid rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); 103238106Sdes 104238106Sdes/** 105238106Sdes * Insert data into the tree. 106238106Sdes * @param rbtree: tree to insert to. 107238106Sdes * @param data: element to insert. 108238106Sdes * @return: data ptr or NULL if key already present. 109238106Sdes */ 110238106Sdesrbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); 111238106Sdes 112238106Sdes/** 113238106Sdes * Delete element from tree. 114238106Sdes * @param rbtree: tree to delete from. 115238106Sdes * @param key: key of item to delete. 116238106Sdes * @return: node that is now unlinked from the tree. User to delete it. 117238106Sdes * returns 0 if node not present 118238106Sdes */ 119238106Sdesrbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); 120238106Sdes 121238106Sdes/** 122238106Sdes * Find key in tree. Returns NULL if not found. 123238106Sdes * @param rbtree: tree to find in. 124238106Sdes * @param key: key that must match. 125238106Sdes * @return: node that fits or NULL. 126238106Sdes */ 127238106Sdesrbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); 128238106Sdes 129238106Sdes/** 130238106Sdes * Find, but match does not have to be exact. 131238106Sdes * @param rbtree: tree to find in. 132238106Sdes * @param key: key to find position of. 133238106Sdes * @param result: set to the exact node if present, otherwise to element that 134238106Sdes * precedes the position of key in the tree. NULL if no smaller element. 135238106Sdes * @return: true if exact match in result. Else result points to <= element, 136238106Sdes * or NULL if key is smaller than the smallest key. 137238106Sdes */ 138238106Sdesint rbtree_find_less_equal(rbtree_t *rbtree, const void *key, 139238106Sdes rbnode_t **result); 140238106Sdes 141238106Sdes/** 142238106Sdes * Returns first (smallest) node in the tree 143238106Sdes * @param rbtree: tree 144238106Sdes * @return: smallest element or NULL if tree empty. 145238106Sdes */ 146238106Sdesrbnode_t *rbtree_first(rbtree_t *rbtree); 147238106Sdes 148238106Sdes/** 149238106Sdes * Returns last (largest) node in the tree 150238106Sdes * @param rbtree: tree 151238106Sdes * @return: largest element or NULL if tree empty. 152238106Sdes */ 153238106Sdesrbnode_t *rbtree_last(rbtree_t *rbtree); 154238106Sdes 155238106Sdes/** 156238106Sdes * Returns next larger node in the tree 157238106Sdes * @param rbtree: tree 158238106Sdes * @return: next larger element or NULL if no larger in tree. 159238106Sdes */ 160238106Sdesrbnode_t *rbtree_next(rbnode_t *rbtree); 161238106Sdes 162238106Sdes/** 163238106Sdes * Returns previous smaller node in the tree 164238106Sdes * @param rbtree: tree 165238106Sdes * @return: previous smaller element or NULL if no previous in tree. 166238106Sdes */ 167238106Sdesrbnode_t *rbtree_previous(rbnode_t *rbtree); 168238106Sdes 169238106Sdes/** 170238106Sdes * Call with node=variable of struct* with rbnode_t as first element. 171238106Sdes * with type is the type of a pointer to that struct. 172238106Sdes */ 173238106Sdes#define RBTREE_FOR(node, type, rbtree) \ 174238106Sdes for(node=(type)rbtree_first(rbtree); \ 175238106Sdes (rbnode_t*)node != RBTREE_NULL; \ 176238106Sdes node = (type)rbtree_next((rbnode_t*)node)) 177238106Sdes 178238106Sdes/** 179238106Sdes * Call function for all elements in the redblack tree, such that 180238106Sdes * leaf elements are called before parent elements. So that all 181238106Sdes * elements can be safely free()d. 182238106Sdes * Note that your function must not remove the nodes from the tree. 183238106Sdes * Since that may trigger rebalances of the rbtree. 184238106Sdes * @param tree: the tree 185238106Sdes * @param func: function called with element and user arg. 186238106Sdes * The function must not alter the rbtree. 187238106Sdes * @param arg: user argument. 188238106Sdes */ 189238106Sdesvoid traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), 190238106Sdes void* arg); 191238106Sdes 192238106Sdes#endif /* UTIL_RBTREE_H_ */ 193