Drizzled Public API Documentation

ut0rbt.h

Go to the documentation of this file.
00001 /***************************************************************************/
00024 /******************************************************************/
00031 #pragma once
00032 #ifndef INNOBASE_UT0RBT_H
00033 #define INNOBASE_UT0RBT_H
00034 
00035 #if !defined(IB_RBT_TESTING)
00036 #include "univ.i"
00037 #include "ut0mem.h"
00038 #else
00039 #include <stdio.h>
00040 #include <stdlib.h>
00041 #include <string.h>
00042 #include <assert.h>
00043 
00044 #define ut_malloc malloc
00045 #define ut_free   free
00046 #define ulint   unsigned long
00047 #define ut_a(c)   assert(c)
00048 #define ut_error  assert(0)
00049 #define ibool   unsigned int
00050 #define TRUE    1
00051 #define FALSE   0
00052 #endif
00053 
00054 /* Red black tree typedefs */
00055 typedef struct ib_rbt_struct ib_rbt_t;
00056 typedef struct ib_rbt_node_struct ib_rbt_node_t;
00057 /* FIXME: Iterator is a better name than _bound_ */
00058 typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
00059 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
00060 typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
00061 
00063 enum ib_rbt_color_enum {
00064   IB_RBT_RED,
00065   IB_RBT_BLACK
00066 };
00067 
00068 typedef enum ib_rbt_color_enum ib_rbt_color_t;
00069 
00071 struct ib_rbt_node_struct {
00072   ib_rbt_color_t  color;      /* color of this node */
00073 
00074   ib_rbt_node_t*  left;     /* points left child */
00075   ib_rbt_node_t*  right;      /* points right child */
00076   ib_rbt_node_t*  parent;     /* points parent node */
00077 
00078   char    value[1];   /* Data value */
00079 };
00080 
00082 struct  ib_rbt_struct {
00083   ib_rbt_node_t*  nil;      /* Black colored node that is
00084             used as a sentinel. This is
00085             pre-allocated too.*/
00086 
00087   ib_rbt_node_t*  root;     /* Root of the tree, this is
00088             pre-allocated and the first
00089             data node is the left child.*/
00090 
00091   ulint   n_nodes;    /* Total number of data nodes */
00092 
00093   ib_rbt_compare  compare;    /* Fn. to use for comparison */
00094   ulint   sizeof_value;   /* Sizeof the item in bytes */
00095 };
00096 
00099 struct ib_rbt_bound_struct {
00100   const ib_rbt_node_t*
00101       last;     /* Last node visited */
00102 
00103   int   result;     /* Result of comparing with
00104             the last non-nil node that
00105             was visited */
00106 };
00107 
00108 /* Size in elements (t is an rb tree instance) */
00109 #define rbt_size(t) (t->n_nodes)
00110 
00111 /* Check whether the rb tree is empty (t is an rb tree instance) */
00112 #define rbt_empty(t)  (rbt_size(t) == 0)
00113 
00114 /* Get data value (t is the data type, n is an rb tree node instance) */
00115 #define rbt_value(t, n) ((t*) &n->value[0])
00116 
00117 /* Compare a key with the node value (t is tree, k is key, n is node)*/
00118 #define rbt_compare(t, k, n) (t->compare(k, n->value))
00119 
00120 /**********************************************************************/
00122 UNIV_INTERN
00123 void
00124 rbt_free(
00125 /*=====*/
00126   ib_rbt_t* tree);      
00127 /**********************************************************************/
00130 UNIV_INTERN
00131 ib_rbt_t*
00132 rbt_create(
00133 /*=======*/
00134   size_t    sizeof_value,   
00135   ib_rbt_compare  compare);   
00136 /**********************************************************************/
00138 UNIV_INTERN
00139 ibool
00140 rbt_delete(
00141 /*=======*/
00142             /* in: TRUE on success */
00143   ib_rbt_t* tree,     /* in: rb tree */
00144   const void* key);     /* in: key to delete */
00145 /**********************************************************************/
00149 UNIV_INTERN
00150 ib_rbt_node_t*
00151 rbt_remove_node(
00152 /*============*/
00153   ib_rbt_t* tree,     
00154   const ib_rbt_node_t*
00155       node);      
00159 /**********************************************************************/
00163 UNIV_INTERN
00164 const ib_rbt_node_t*
00165 rbt_lookup(
00166 /*=======*/
00167   const ib_rbt_t* tree,     
00168   const void* key);     
00169 /**********************************************************************/
00172 UNIV_INTERN
00173 const ib_rbt_node_t*
00174 rbt_insert(
00175 /*=======*/
00176   ib_rbt_t* tree,     
00177   const void* key,      
00178   const void* value);     
00180 /**********************************************************************/
00183 UNIV_INTERN
00184 const ib_rbt_node_t*
00185 rbt_add_node(
00186 /*=========*/
00187   ib_rbt_t* tree,     
00188   ib_rbt_bound_t* parent,     
00189   const void* value);     
00191 /**********************************************************************/
00194 UNIV_INTERN
00195 const ib_rbt_node_t*
00196 rbt_first(
00197 /*======*/
00198   const ib_rbt_t* tree);      
00199 /**********************************************************************/
00202 UNIV_INTERN
00203 const ib_rbt_node_t*
00204 rbt_last(
00205 /*=====*/
00206   const ib_rbt_t* tree);      
00207 /**********************************************************************/
00210 UNIV_INTERN
00211 const ib_rbt_node_t*
00212 rbt_next(
00213 /*=====*/
00214   const ib_rbt_t* tree,     
00215   const ib_rbt_node_t*      /* in: current node */
00216       current);
00217 /**********************************************************************/
00220 UNIV_INTERN
00221 const ib_rbt_node_t*
00222 rbt_prev(
00223 /*=====*/
00224   const ib_rbt_t* tree,     
00225   const ib_rbt_node_t*      /* in: current node */
00226       current);
00227 /**********************************************************************/
00230 UNIV_INTERN
00231 const ib_rbt_node_t*
00232 rbt_lower_bound(
00233 /*============*/
00234   const ib_rbt_t* tree,     
00235   const void* key);     
00236 /**********************************************************************/
00239 UNIV_INTERN
00240 const ib_rbt_node_t*
00241 rbt_upper_bound(
00242 /*============*/
00243   const ib_rbt_t* tree,     
00244   const void* key);     
00245 /**********************************************************************/
00250 UNIV_INTERN
00251 int
00252 rbt_search(
00253 /*=======*/
00254   const ib_rbt_t* tree,     
00255   ib_rbt_bound_t* parent,     
00256   const void* key);     
00257 /**********************************************************************/
00262 UNIV_INTERN
00263 int
00264 rbt_search_cmp(
00265 /*===========*/
00266   const ib_rbt_t* tree,     
00267   ib_rbt_bound_t* parent,     
00268   const void* key,      
00269   ib_rbt_compare  compare);   
00270 /**********************************************************************/
00272 UNIV_INTERN
00273 void
00274 rbt_clear(
00275 /*======*/
00276   ib_rbt_t* tree);      
00277 /**********************************************************************/
00280 UNIV_INTERN
00281 ulint
00282 rbt_merge_uniq(
00283 /*===========*/
00284   ib_rbt_t* dst,      
00285   const ib_rbt_t* src);     
00286 /**********************************************************************/
00293 UNIV_INTERN
00294 ulint
00295 rbt_merge_uniq_destructive(
00296 /*=======================*/
00297   ib_rbt_t* dst,      
00298   ib_rbt_t* src);     
00299 /**********************************************************************/
00303 UNIV_INTERN
00304 ibool
00305 rbt_validate(
00306 /*=========*/
00307   const ib_rbt_t* tree);      
00308 /**********************************************************************/
00310 UNIV_INTERN
00311 void
00312 rbt_print(
00313 /*======*/
00314   const ib_rbt_t*   tree,   
00315   ib_rbt_print_node print);   
00317 #endif /* INNOBASE_UT0RBT_H */