1 /***************************************************************************** 2 3 Copyright (c) 2007, 2015, Oracle and/or its affiliates. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify it under 6 the terms of the GNU General Public License as published by the Free Software 7 Foundation; version 2 of the License. 8 9 This program is distributed in the hope that it will be useful, but WITHOUT 10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 11 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License along with 14 this program; if not, write to the Free Software Foundation, Inc., 15 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA 16 17 *****************************************************************************/ 18 /******************************************************************//** 19 @file include/ut0rbt.h 20 Various utilities 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 "ut0mem.h" 30 #else 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include <string.h> 34 #include <assert.h> 35 36 #define ut_malloc malloc 37 #define ut_free free 38 #define ulint unsigned long 39 #define ut_a(c) assert(c) 40 #define ut_error assert(0) 41 #define ibool unsigned int 42 #define TRUE 1 43 #define FALSE 0 44 #endif 45 46 struct ib_rbt_node_t; 47 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node); 48 typedef int (*ib_rbt_compare)(const void* p1, const void* p2); 49 typedef int (*ib_rbt_arg_compare)(const void*, const void* p1, const void* p2); 50 51 /** Red black tree color types */ 52 enum ib_rbt_color_t { 53 IB_RBT_RED, 54 IB_RBT_BLACK 55 }; 56 57 /** Red black tree node */ 58 struct ib_rbt_node_t { 59 ib_rbt_color_t color; /* color of this node */ 60 61 ib_rbt_node_t* left; /* points left child */ 62 ib_rbt_node_t* right; /* points right child */ 63 ib_rbt_node_t* parent; /* points parent node */ 64 65 char value[1]; /* Data value */ 66 }; 67 68 /** Red black tree instance.*/ 69 struct ib_rbt_t { 70 ib_rbt_node_t* nil; /* Black colored node that is 71 used as a sentinel. This is 72 pre-allocated too.*/ 73 74 ib_rbt_node_t* root; /* Root of the tree, this is 75 pre-allocated and the first 76 data node is the left child.*/ 77 78 ulint n_nodes; /* Total number of data nodes */ 79 80 ib_rbt_compare compare; /* Fn. to use for comparison */ 81 ib_rbt_arg_compare 82 compare_with_arg; /* Fn. to use for comparison 83 with argument */ 84 ulint sizeof_value; /* Sizeof the item in bytes */ 85 void* cmp_arg; /* Compare func argument */ 86 }; 87 88 /** The result of searching for a key in the tree, this is useful for 89 a speedy lookup and insert if key doesn't exist.*/ 90 struct ib_rbt_bound_t { 91 const ib_rbt_node_t* 92 last; /* Last node visited */ 93 94 int result; /* Result of comparing with 95 the last non-nil node that 96 was visited */ 97 }; 98 99 /* Size in elements (t is an rb tree instance) */ 100 #define rbt_size(t) (t->n_nodes) 101 102 /* Check whether the rb tree is empty (t is an rb tree instance) */ 103 #define rbt_empty(t) (rbt_size(t) == 0) 104 105 /* Get data value (t is the data type, n is an rb tree node instance) */ 106 #define rbt_value(t, n) ((t*) &n->value[0]) 107 108 /* Compare a key with the node value (t is tree, k is key, n is node)*/ 109 #define rbt_compare(t, k, n) (t->compare(k, n->value)) 110 111 /**********************************************************************//** 112 Free an instance of a red black tree */ 113 void 114 rbt_free( 115 /*=====*/ 116 ib_rbt_t* tree); /*!< in: rb tree to free */ 117 /**********************************************************************//** 118 Create an instance of a red black tree 119 @return rb tree instance */ 120 ib_rbt_t* 121 rbt_create( 122 /*=======*/ 123 size_t sizeof_value, /*!< in: size in bytes */ 124 ib_rbt_compare compare); /*!< in: comparator */ 125 /**********************************************************************//** 126 Create an instance of a red black tree, whose comparison function takes 127 an argument 128 @return rb tree instance */ 129 ib_rbt_t* 130 rbt_create_arg_cmp( 131 /*===============*/ 132 size_t sizeof_value, /*!< in: size in bytes */ 133 ib_rbt_arg_compare 134 compare, /*!< in: comparator */ 135 void* cmp_arg); /*!< in: compare fn arg */ 136 /**********************************************************************//** 137 Delete a node from the red black tree, identified by key */ 138 ibool 139 rbt_delete( 140 /*=======*/ 141 /* in: TRUE on success */ 142 ib_rbt_t* tree, /* in: rb tree */ 143 const void* key); /* in: key to delete */ 144 /**********************************************************************//** 145 Remove a node from the red black tree, NOTE: This function will not delete 146 the node instance, THAT IS THE CALLERS RESPONSIBILITY. 147 @return the deleted node with the const. */ 148 ib_rbt_node_t* 149 rbt_remove_node( 150 /*============*/ 151 ib_rbt_t* tree, /*!< in: rb tree */ 152 const ib_rbt_node_t* 153 node); /*!< in: node to delete, this 154 is a fudge and declared const 155 because the caller has access 156 only to const nodes.*/ 157 /**********************************************************************//** 158 Add data to the red black tree, identified by key (no dups yet!) 159 @return inserted node */ 160 const ib_rbt_node_t* 161 rbt_insert( 162 /*=======*/ 163 ib_rbt_t* tree, /*!< in: rb tree */ 164 const void* key, /*!< in: key for ordering */ 165 const void* value); /*!< in: data that will be 166 copied to the node.*/ 167 /**********************************************************************//** 168 Add a new node to the tree, useful for data that is pre-sorted. 169 @return appended node */ 170 const ib_rbt_node_t* 171 rbt_add_node( 172 /*=========*/ 173 ib_rbt_t* tree, /*!< in: rb tree */ 174 ib_rbt_bound_t* parent, /*!< in: parent */ 175 const void* value); /*!< in: this value is copied 176 to the node */ 177 /**********************************************************************//** 178 Return the left most data node in the tree 179 @return left most node */ 180 const ib_rbt_node_t* 181 rbt_first( 182 /*======*/ 183 const ib_rbt_t* tree); /*!< in: rb tree */ 184 /**********************************************************************//** 185 Return the right most data node in the tree 186 @return right most node */ 187 const ib_rbt_node_t* 188 rbt_last( 189 /*=====*/ 190 const ib_rbt_t* tree); /*!< in: rb tree */ 191 /**********************************************************************//** 192 Return the next node from current. 193 @return successor node to current that is passed in. */ 194 const ib_rbt_node_t* 195 rbt_next( 196 /*=====*/ 197 const ib_rbt_t* tree, /*!< in: rb tree */ 198 const ib_rbt_node_t* /* in: current node */ 199 current); 200 /**********************************************************************//** 201 Return the prev node from current. 202 @return precedessor node to current that is passed in */ 203 const ib_rbt_node_t* 204 rbt_prev( 205 /*=====*/ 206 const ib_rbt_t* tree, /*!< in: rb tree */ 207 const ib_rbt_node_t* /* in: current node */ 208 current); 209 /**********************************************************************//** 210 Search for the key, a node will be retuned in parent.last, whether it 211 was found or not. If not found then parent.last will contain the 212 parent node for the possibly new key otherwise the matching node. 213 @return result of last comparison */ 214 int 215 rbt_search( 216 /*=======*/ 217 const ib_rbt_t* tree, /*!< in: rb tree */ 218 ib_rbt_bound_t* parent, /*!< in: search bounds */ 219 const void* key); /*!< in: key to search */ 220 /**********************************************************************//** 221 Search for the key, a node will be retuned in parent.last, whether it 222 was found or not. If not found then parent.last will contain the 223 parent node for the possibly new key otherwise the matching node. 224 @return result of last comparison */ 225 int 226 rbt_search_cmp( 227 /*===========*/ 228 const ib_rbt_t* tree, /*!< in: rb tree */ 229 ib_rbt_bound_t* parent, /*!< in: search bounds */ 230 const void* key, /*!< in: key to search */ 231 ib_rbt_compare compare, /*!< in: comparator */ 232 ib_rbt_arg_compare 233 arg_compare); /*!< in: fn to compare items 234 with argument */ 235 /**********************************************************************//** 236 Merge the node from dst into src. Return the number of nodes merged. 237 @return no. of recs merged */ 238 ulint 239 rbt_merge_uniq( 240 /*===========*/ 241 ib_rbt_t* dst, /*!< in: dst rb tree */ 242 const ib_rbt_t* src); /*!< in: src rb tree */ 243 #if defined UNIV_DEBUG || defined IB_RBT_TESTING 244 /**********************************************************************//** 245 Verify the integrity of the RB tree. For debugging. 0 failure else height 246 of tree (in count of black nodes). 247 @return TRUE if OK FALSE if tree invalid. */ 248 ibool 249 rbt_validate( 250 /*=========*/ 251 const ib_rbt_t* tree); /*!< in: tree to validate */ 252 #endif /* UNIV_DEBUG || IB_RBT_TESTING */ 253 254 #endif /* INNOBASE_UT0RBT_H */ 255