/*====================================================================* - Copyright (C) 2001 Leptonica. All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - 1. Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - 2. 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. - - 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 ANY - 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. *====================================================================*/ /* * Modified from the excellent code here: * http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 * which has been placed in the public domain under the Creative Commons * CC0 1.0 waiver (http://creativecommons.org/publicdomain/zero/1.0/). */ /*! * \file rbtree.c *
* * Basic functions for using red-black trees. These are "nearly" balanced * sorted trees with ordering by key that allows insertion, lookup and * deletion of key/value pairs in log(n) time. * * We use red-black trees to implement our version of: * * a map: a function that maps keys to values (e.g., int64 --> int64). * * a set: a collection that is sorted by unique keys (without * associated values) * * There are 5 invariant properties of RB trees: * (1) Each node is either red or black. * (2) The root node is black. * (3) All leaves are black and contain no data (null). * (4) Every red node has two children and both are black. This is * equivalent to requiring the parent of every red node to be black. * (5) All paths from any given node to its leaf nodes contain the * same number of black nodes. * * Interface to red-black tree * L_RBTREE *l_rbtreeCreate() * RB_TYPE *l_rbtreeLookup() * void l_rbtreeInsert() * void l_rbtreeDelete() * void l_rbtreeDestroy() * L_RBTREE_NODE *l_rbtreeGetFirst() * L_RBTREE_NODE *l_rbtreeGetNext() * L_RBTREE_NODE *l_rbtreeGetLast() * L_RBTREE_NODE *l_rbtreeGetPrev() * l_int32 l_rbtreeGetCount() * void l_rbtreePrint() * * General comparison function * static l_int32 compareKeys() **/ #include "allheaders.h" /* The node color enum is only needed in the rbtree implementation */ enum { L_RED_NODE = 1, L_BLACK_NODE = 2 }; /* This makes it simpler to read the code */ typedef L_RBTREE_NODE node; /* Lots of static helper functions */ static void destroy_helper(node *n); static void count_helper(node *n, l_int32 *pcount); static void print_tree_helper(FILE *fp, node *n, l_int32 keytype, l_int32 indent); static l_int32 compareKeys(l_int32 keytype, RB_TYPE left, RB_TYPE right); static node *grandparent(node *n); static node *sibling(node *n); static node *uncle(node *n); static l_int32 node_color(node *n); static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color, node *left, node *right); static node *lookup_node(L_RBTREE *t, RB_TYPE key); static void rotate_left(L_RBTREE *t, node *n); static void rotate_right(L_RBTREE *t, node *n); static void replace_node(L_RBTREE *t, node *oldn, node *newn); static void insert_case1(L_RBTREE *t, node *n); static void insert_case2(L_RBTREE *t, node *n); static void insert_case3(L_RBTREE *t, node *n); static void insert_case4(L_RBTREE *t, node *n); static void insert_case5(L_RBTREE *t, node *n); static node *maximum_node(node *root); static void delete_case1(L_RBTREE *t, node *n); static void delete_case2(L_RBTREE *t, node *n); static void delete_case3(L_RBTREE *t, node *n); static void delete_case4(L_RBTREE *t, node *n); static void delete_case5(L_RBTREE *t, node *n); static void delete_case6(L_RBTREE *t, node *n); static void verify_properties(L_RBTREE *t); #ifndef NO_CONSOLE_IO #define VERIFY_RBTREE 0 /* only for debugging */ #endif /* ~NO_CONSOLE_IO */ /* ------------------------------------------------------------- * * Interface to Red-black Tree * * ------------------------------------------------------------- */ /*! * \brief l_rbtreeCreate() * * \param[in] keytype defined by an enum for an RB_TYPE union * \return rbtree container with empty ptr to the root */ L_RBTREE * l_rbtreeCreate(l_int32 keytype) { PROCNAME("l_rbtreeCreate"); if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE && keytype != L_FLOAT_TYPE && keytype) return (L_RBTREE *)ERROR_PTR("invalid keytype", procName, NULL); L_RBTREE *t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE)); t->keytype = keytype; verify_properties(t); return t; } /*! * \brief l_rbtreeLookup() * * \param[in] t rbtree, including root node * \param[in] key find a node with this key * \return &value a pointer to a union, if the node exists; else NULL */ RB_TYPE * l_rbtreeLookup(L_RBTREE *t, RB_TYPE key) { PROCNAME("l_rbtreeLookup"); if (!t) return (RB_TYPE *)ERROR_PTR("tree is null\n", procName, NULL); node *n = lookup_node(t, key); return n == NULL ? NULL : &n->value; } /*! * \brief l_rbtreeInsert() * * \param[in] t rbtree, including root node * \param[in] key insert a node with this key, if the key does not * already exist in the tree * \param[in] value typically an int, used for an index * \return void * *
* Notes: * (1) If a node with the key already exists, this just updates the value. **/ void l_rbtreeInsert(L_RBTREE *t, RB_TYPE key, RB_TYPE value) { node *n, *inserted_node; PROCNAME("l_rbtreeInsert"); if (!t) { L_ERROR("tree is null\n", procName); return; } inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL); if (t->root == NULL) { t->root = inserted_node; } else { n = t->root; while (1) { int comp_result = compareKeys(t->keytype, key, n->key); if (comp_result == 0) { n->value = value; LEPT_FREE(inserted_node); return; } else if (comp_result < 0) { if (n->left == NULL) { n->left = inserted_node; break; } else { n = n->left; } } else { /* comp_result > 0 */ if (n->right == NULL) { n->right = inserted_node; break; } else { n = n->right; } } } inserted_node->parent = n; } insert_case1(t, inserted_node); verify_properties(t); } /*! * \brief l_rbtreeDelete() * * \param[in] t rbtree, including root node * \param[in] key delete the node with this key * \return void */ void l_rbtreeDelete(L_RBTREE *t, RB_TYPE key) { node *n, *child; PROCNAME("l_rbtreeDelete"); if (!t) { L_ERROR("tree is null\n", procName); return; } n = lookup_node(t, key); if (n == NULL) return; /* Key not found, do nothing */ if (n->left != NULL && n->right != NULL) { /* Copy key/value from predecessor and then delete it instead */ node *pred = maximum_node(n->left); n->key = pred->key; n->value = pred->value; n = pred; } /* n->left == NULL || n->right == NULL */ child = n->right == NULL ? n->left : n->right; if (node_color(n) == L_BLACK_NODE) { n->color = node_color(child); delete_case1(t, n); } replace_node(t, n, child); if (n->parent == NULL && child != NULL) /* root should be black */ child->color = L_BLACK_NODE; LEPT_FREE(n); verify_properties(t); } /*! * \brief l_rbtreeDestroy() * * \param[in] pt pointer to tree; will be wet to null before returning * \return void * *
* Notes: * (1) Destroys the tree and nulls the input tree ptr. **/ void l_rbtreeDestroy(L_RBTREE **pt) { node *n; if (!pt) return; if (*pt == NULL) return; n = (*pt)->root; destroy_helper(n); LEPT_FREE(*pt); *pt = NULL; return; } /* postorder DFS */ static void destroy_helper(node *n) { if (!n) return; destroy_helper(n->left); destroy_helper(n->right); LEPT_FREE(n); } /*! * \brief l_rbtreeGetFirst() * * \param[in] t rbtree, including root node * \return void * *
* Notes: * (1) This is the first node in an in-order traversal. **/ L_RBTREE_NODE * l_rbtreeGetFirst(L_RBTREE *t) { node *n; PROCNAME("l_rbtreeGetFirst"); if (!t) return (L_RBTREE_NODE *)ERROR_PTR("tree is null", procName, NULL); if (t->root == NULL) { L_INFO("tree is empty\n", procName); return NULL; } /* Just go down the left side as far as possible */ n = t->root; while (n && n->left) n = n->left; return n; } /*! * \brief l_rbtreeGetNext() * * \param[in] n current node * \return next node, or NULL if it's the last node * *
* Notes: * (1) This finds the next node, in an in-order traversal, from * the current node. * (2) It is useful as an iterator for a map. * (3) Call l_rbtreeGetFirst() to get the first node. **/ L_RBTREE_NODE * l_rbtreeGetNext(L_RBTREE_NODE *n) { PROCNAME("l_rbtreeGetNext"); if (!n) return (L_RBTREE_NODE *)ERROR_PTR("n not defined", procName, NULL); /* If there is a right child, go to it, and then go left all the * way to the end. Otherwise go up to the parent; continue upward * as long as you're on the right branch, but stop at the parent * when you hit it from the left branch. */ if (n->right) { n = n->right; while (n->left) n = n->left; return n; } else { while (n->parent && n->parent->right == n) n = n->parent; return n->parent; } } /*! * \brief l_rbtreeGetLast() * * \param[in] t rbtree, including root node * \return void * *
* Notes: * (1) This is the last node in an in-order traversal. **/ L_RBTREE_NODE * l_rbtreeGetLast(L_RBTREE *t) { node *n; PROCNAME("l_rbtreeGetLast"); if (!t) return (L_RBTREE_NODE *)ERROR_PTR("tree is null", procName, NULL); if (t->root == NULL) { L_INFO("tree is empty\n", procName); return NULL; } /* Just go down the right side as far as possible */ n = t->root; while (n && n->right) n = n->right; return n; } /*! * \brief l_rbtreeGetPrev() * * \param[in] n current node * \return next node, or NULL if it's the first node * *
* Notes: * (1) This finds the previous node, in an in-order traversal, from * the current node. * (2) It is useful as an iterator for a map. * (3) Call l_rbtreeGetLast() to get the last node. **/ L_RBTREE_NODE * l_rbtreeGetPrev(L_RBTREE_NODE *n) { PROCNAME("l_rbtreeGetPrev"); if (!n) return (L_RBTREE_NODE *)ERROR_PTR("n not defined", procName, NULL); /* If there is a left child, go to it, and then go right all the * way to the end. Otherwise go up to the parent; continue upward * as long as you're on the left branch, but stop at the parent * when you hit it from the right branch. */ if (n->left) { n = n->left; while (n->right) n = n->right; return n; } else { while (n->parent && n->parent->left == n) n = n->parent; return n->parent; } } /*! * \brief l_rbtreeGetCount() * * \param[in] t rbtree * \return count the number of nodes in the tree, or 0 on error */ l_int32 l_rbtreeGetCount(L_RBTREE *t) { l_int32 count = 0; node *n; if (!t) return 0; n = t->root; count_helper(n, &count); return count; } /* preorder DFS */ static void count_helper(node *n, l_int32 *pcount) { if (n) (*pcount)++; else return; count_helper(n->left, pcount); count_helper(n->right, pcount); } /*! * \brief l_rbtreePrint() * * \param[in] fp file stream * \param[in] t rbtree * \return void */ void l_rbtreePrint(FILE *fp, L_RBTREE *t) { PROCNAME("l_rbtreePrint"); if (!fp) { L_ERROR("stream not defined\n", procName); return; } if (!t) { L_ERROR("tree not defined\n", procName); return; } print_tree_helper(fp, t->root, t->keytype, 0); fprintf(fp, "\n"); } #define INDENT_STEP 4 static void print_tree_helper(FILE *fp, node *n, l_int32 keytype, l_int32 indent) { l_int32 i; if (n == NULL) { fprintf(fp, "