release/src/router/mysql/storage/innodb_plugin/include/ut0rbt.h

   1 /*****************************************************************************
   2 Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
   3
   4 This program is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free Software
   6 Foundation; version 2 of the License.
   7
   8 This program is distributed in the hope that it will be useful, but WITHOUT
   9 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  10 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  11
  12 You should have received a copy of the GNU General Public License along with
  13 this program; if not, write to the Free Software Foundation, Inc.,
  14 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  15
  16 *****************************************************************************/
  17
  18 /*******************************************************************//**
  19 @file include/ut0rbt.h
  20 Red-Black tree implementation.
  21
  22 Created 2007-03-20 Sunny Bains
  23 ************************************************************************/
  24
  25 #ifndef INNOBASE_UT0RBT_H
  26 #define INNOBASE_UT0RBT_H
  27
  28 #if !defined(IB_RBT_TESTING)
  29 #include "univ.i"
  30 #include "ut0mem.h"
  31 #else
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <assert.h>
  36
  37 #define ut_malloc       malloc
  38 #define ut_free         free
  39 #define ulint           unsigned long
  40 #define ut_a(c)         assert(c)
  41 #define ut_error        assert(0)
  42 #define ibool           unsigned int
  43 #define TRUE            1
  44 #define FALSE           0
  45 #endif
  46
  47 /* Red black tree typedefs */
  48 typedef struct ib_rbt_struct ib_rbt_t;
  49 typedef struct ib_rbt_node_struct ib_rbt_node_t;
  50 /* FIXME: Iterator is a better name than _bound_ */
  51 typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
  52 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
  53 typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
  54
  55 /* Red black tree color types */
  56 enum ib_rbt_color_enum {
  57         IB_RBT_RED,
  58         IB_RBT_BLACK
  59 };
  60
  61 typedef enum ib_rbt_color_enum ib_rbt_color_t;
  62
  63 /* Red black tree node */
  64 struct ib_rbt_node_struct {
  65         ib_rbt_color_t  color;                  /* color of this node */
  66
  67         ib_rbt_node_t*  left;                   /* points left child */
  68         ib_rbt_node_t*  right;                  /* points right child */
  69         ib_rbt_node_t*  parent;                 /* points parent node */
  70
  71         char            value[1];               /* Data value */
  72 };
  73
  74 /* Red black tree instance.*/
  75 struct  ib_rbt_struct {
  76         ib_rbt_node_t*  nil;                    /* Black colored node that is
  77                                                 used as a sentinel. This is
  78                                                 pre-allocated too.*/
  79
  80         ib_rbt_node_t*  root;                   /* Root of the tree, this is
  81                                                 pre-allocated and the first
  82                                                 data node is the left child.*/
  83
  84         ulint           n_nodes;                /* Total number of data nodes */
  85
  86         ib_rbt_compare  compare;                /* Fn. to use for comparison */
  87         ulint           sizeof_value;           /* Sizeof the item in bytes */
  88 };
  89
  90 /* The result of searching for a key in the tree, this is useful for
  91 a speedy lookup and insert if key doesn't exist.*/
  92 struct ib_rbt_bound_struct {
  93         const ib_rbt_node_t*
  94                         last;                   /* Last node visited */
  95
  96         int             result;                 /* Result of comparing with
  97                                                 the last non-nil node that
  98                                                 was visited */
  99 };
 100
 101 /* Size in elements (t is an rb tree instance) */
 102 #define rbt_size(t)     (t->n_nodes)
 103
 104 /* Check whether the rb tree is empty (t is an rb tree instance) */
 105 #define rbt_empty(t)    (rbt_size(t) == 0)
 106
 107 /* Get data value (t is the data type, n is an rb tree node instance) */
 108 #define rbt_value(t, n) ((t*) &n->value[0])
 109
 110 /* Compare a key with the node value (t is tree, k is key, n is node)*/
 111 #define rbt_compare(t, k, n) (t->compare(k, n->value))
 112
 113 /****************************************************************//**
 114 Free an instance of  a red black tree */
 115 UNIV_INTERN
 116 void
 117 rbt_free(
 118 /*=====*/
 119         ib_rbt_t*       tree);          /*!< in: rb tree to free */
 120 /****************************************************************//**
 121 Create an instance of a red black tree
 122 @return rb tree instance */
 123 UNIV_INTERN
 124 ib_rbt_t*
 125 rbt_create(
 126 /*=======*/
 127         size_t          sizeof_value,   /*!< in: size in bytes */
 128         ib_rbt_compare  compare);       /*!< in: comparator */
 129 /****************************************************************//**
 130 Delete a node from the red black tree, identified by key.
 131 @return TRUE if success FALSE if not found */
 132 UNIV_INTERN
 133 ibool
 134 rbt_delete(
 135 /*=======*/
 136         ib_rbt_t*       tree,           /*!< in: rb tree */
 137         const void*     key);           /*!< in: key to delete */
 138 /****************************************************************//**
 139 Remove a node from the rb tree, the node is not free'd, that is the
 140 callers responsibility.
 141 @return the deleted node with the const. */
 142 UNIV_INTERN
 143 ib_rbt_node_t*
 144 rbt_remove_node(
 145 /*============*/
 146         ib_rbt_t*       tree,           /*!< in: rb tree */
 147         const ib_rbt_node_t*
 148                         node);          /*!< in: node to delete, this
 149                                         is a fudge and declared const
 150                                         because the caller has access
 151                                         only to const nodes.*/
 152 /****************************************************************//**
 153 Find a matching node in the rb tree.
 154 @return node if found else return NULL */
 155 UNIV_INTERN
 156 const ib_rbt_node_t*
 157 rbt_lookup(
 158 /*=======*/
 159         const ib_rbt_t* tree,           /*!< in: rb tree to search */
 160         const void*     key);           /*!< in: key to lookup */
 161 /****************************************************************//**
 162 Generic insert of a value in the rb tree.
 163 @return inserted node */
 164 UNIV_INTERN
 165 const ib_rbt_node_t*
 166 rbt_insert(
 167 /*=======*/
 168         ib_rbt_t*       tree,           /*!< in: rb tree */
 169         const void*     key,            /*!< in: key for ordering */
 170         const void*     value);         /*!< in: data that will be
 171                                         copied to the node.*/
 172 /****************************************************************//**
 173 Add a new node to the tree, useful for data that is pre-sorted.
 174 @return appended node */
 175 UNIV_INTERN
 176 const ib_rbt_node_t*
 177 rbt_add_node(
 178 /*=========*/
 179         ib_rbt_t*       tree,           /*!< in: rb tree */
 180         ib_rbt_bound_t* parent,         /*!< in: parent */
 181         const void*     value);         /*!< in: this value is copied
 182                                         to the node */
 183 /****************************************************************//**
 184 Return the left most data node in the tree
 185 @return left most node */
 186 UNIV_INTERN
 187 const ib_rbt_node_t*
 188 rbt_first(
 189 /*======*/
 190         const ib_rbt_t* tree);          /*!< in: rb tree */
 191 /****************************************************************//**
 192 Return the right most data node in the tree
 193 @return right most node */
 194 UNIV_INTERN
 195 const ib_rbt_node_t*
 196 rbt_last(
 197 /*=====*/
 198         const ib_rbt_t* tree);          /*!< in: rb tree */
 199 /****************************************************************//**
 200 Return the next node from current.
 201 @return successor node to current that is passed in. */
 202 UNIV_INTERN
 203 const ib_rbt_node_t*
 204 rbt_next(
 205 /*=====*/
 206         const ib_rbt_t* tree,           /*!< in: rb tree */
 207         const ib_rbt_node_t*            /*!< in: current node */
 208                         current);
 209 /****************************************************************//**
 210 Return the prev node from current.
 211 @return precedessor node to current that is passed in */
 212 UNIV_INTERN
 213 const ib_rbt_node_t*
 214 rbt_prev(
 215 /*=====*/
 216         const ib_rbt_t* tree,           /*!< in: rb tree */
 217         const ib_rbt_node_t*            /*!< in: current node */
 218                         current);
 219 /****************************************************************//**
 220 Find the node that has the lowest key that is >= key.
 221 @return node that satisfies the lower bound constraint or NULL */
 222 UNIV_INTERN
 223 const ib_rbt_node_t*
 224 rbt_lower_bound(
 225 /*============*/
 226         const ib_rbt_t* tree,           /*!< in: rb tree */
 227         const void*     key);           /*!< in: key to search */
 228 /****************************************************************//**
 229 Find the node that has the greatest key that is <= key.
 230 @return node that satisifies the upper bound constraint or NULL */
 231 UNIV_INTERN
 232 const ib_rbt_node_t*
 233 rbt_upper_bound(
 234 /*============*/
 235         const ib_rbt_t* tree,           /*!< in: rb tree */
 236         const void*     key);           /*!< in: key to search */
 237 /****************************************************************//**
 238 Search for the key, a node will be retuned in parent.last, whether it
 239 was found or not. If not found then parent.last will contain the
 240 parent node for the possibly new key otherwise the matching node.
 241 @return result of last comparison */
 242 UNIV_INTERN
 243 int
 244 rbt_search(
 245 /*=======*/
 246         const ib_rbt_t* tree,           /*!< in: rb tree */
 247         ib_rbt_bound_t* parent,         /*!< in: search bounds */
 248         const void*     key);           /*!< in: key to search */
 249 /****************************************************************//**
 250 Search for the key, a node will be retuned in parent.last, whether it
 251 was found or not. If not found then parent.last will contain the
 252 parent node for the possibly new key otherwise the matching node.
 253 @return result of last comparison */
 254 UNIV_INTERN
 255 int
 256 rbt_search_cmp(
 257 /*===========*/
 258         const ib_rbt_t* tree,           /*!< in: rb tree */
 259         ib_rbt_bound_t* parent,         /*!< in: search bounds */
 260         const void*     key,            /*!< in: key to search */
 261         ib_rbt_compare  compare);       /*!< in: comparator */
 262 /****************************************************************//**
 263 Clear the tree, deletes (and free's) all the nodes. */
 264 UNIV_INTERN
 265 void
 266 rbt_clear(
 267 /*======*/
 268         ib_rbt_t*       tree);          /*!< in: rb tree */
 269 /****************************************************************//**
 270 Merge the node from dst into src. Return the number of nodes merged.
 271 @return no. of recs merged */
 272 UNIV_INTERN
 273 ulint
 274 rbt_merge_uniq(
 275 /*===========*/
 276         ib_rbt_t*       dst,            /*!< in: dst rb tree */
 277         const ib_rbt_t* src);           /*!< in: src rb tree */
 278 /****************************************************************//**
 279 Merge the node from dst into src. Return the number of nodes merged.
 280 Delete the nodes from src after copying node to dst. As a side effect
 281 the duplicates will be left untouched in the src, since we don't support
 282 duplicates (yet). NOTE: src and dst must be similar, the function doesn't
 283 check for this condition (yet).
 284 @return no. of recs merged */
 285 UNIV_INTERN
 286 ulint
 287 rbt_merge_uniq_destructive(
 288 /*=======================*/
 289         ib_rbt_t*       dst,            /*!< in: dst rb tree */
 290         ib_rbt_t*       src);           /*!< in: src rb tree */
 291 /****************************************************************//**
 292 Verify the integrity of the RB tree. For debugging. 0 failure else height
 293 of tree (in count of black nodes).
 294 @return TRUE if OK FALSE if tree invalid. */
 295 UNIV_INTERN
 296 ibool
 297 rbt_validate(
 298 /*=========*/
 299         const ib_rbt_t* tree);          /*!< in: tree to validate */
 300 /****************************************************************//**
 301 Iterate over the tree in depth first order. */
 302 UNIV_INTERN
 303 void
 304 rbt_print(
 305 /*======*/
 306         const ib_rbt_t*         tree,   /*!< in: tree to traverse */
 307         ib_rbt_print_node       print); /*!< in: print function */
 308
 309 #endif /* INNOBASE_UT0RBT_H */