Drizzled Public API Documentation

tree.cc
00001 /* Copyright (C) 2000 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /*
00017   Code for handling red-black (balanced) binary trees.
00018   key in tree is allocated accrding to following:
00019 
00020   1) If size < 0 then tree will not allocate keys and only a pointer to
00021      each key is saved in tree.
00022      compare and search functions uses and returns key-pointer
00023 
00024   2) If size == 0 then there are two options:
00025        - key_size != 0 to tree_insert: The key will be stored in the tree.
00026        - key_size == 0 to tree_insert:  A pointer to the key is stored.
00027      compare and search functions uses and returns key-pointer.
00028 
00029   3) if key_size is given to init_tree then each node will continue the
00030      key and calls to insert_key may increase length of key.
00031      if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
00032      allign) then key will be put on a 8 alligned adress. Else
00033      the key will be on adress (element+1). This is transparent for user
00034      compare and search functions uses a pointer to given key-argument.
00035 
00036   - If you use a free function for tree-elements and you are freeing
00037     the element itself, you should use key_size = 0 to init_tree and
00038     tree_search
00039 
00040   The actual key in TREE_ELEMENT is saved as a pointer or after the
00041   TREE_ELEMENT struct.
00042   If one uses only pointers in tree one can use tree_set_pointer() to
00043   change address of data.
00044 
00045   Implemented by monty.
00046 */
00047 
00048 /*
00049   NOTE:
00050   tree->compare function should be ALWAYS called as
00051     (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
00052   and not other way around, as
00053     (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
00054 */
00055 
00056 #include <config.h>
00057 
00058 #include <drizzled/tree.h>
00059 #include <drizzled/internal/my_sys.h>
00060 #include <drizzled/internal/m_string.h>
00061 #include <drizzled/memory/root.h>
00062 
00063 #define BLACK   1
00064 #define RED   0
00065 #define DEFAULT_ALLOC_SIZE 8192
00066 #define DEFAULT_ALIGN_SIZE 8192
00067 
00068 #define ELEMENT_KEY(tree,element)\
00069 (tree->offset_to_key ? (void*)((unsigned char*) element+tree->offset_to_key) :\
00070       *((void**) (element+1)))
00071 #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
00072 
00073 namespace drizzled
00074 {
00075 
00076 
00077 static void delete_tree_element(TREE *,TREE_ELEMENT *);
00078 static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
00079              tree_walk_action,void *);
00080 static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
00081              tree_walk_action,void *);
00082 static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
00083 static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
00084 static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
00085           TREE_ELEMENT *leaf);
00086 static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
00087 
00088 
00089 void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
00090                uint32_t size, qsort_cmp2 compare, bool with_delete,
00091          tree_element_free free_element, void *custom_arg)
00092 {
00093   if (default_alloc_size < DEFAULT_ALLOC_SIZE)
00094     default_alloc_size= DEFAULT_ALLOC_SIZE;
00095   default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
00096   memset(&tree->null_element, 0, sizeof(tree->null_element));
00097   tree->root= &tree->null_element;
00098   tree->compare= compare;
00099   tree->size_of_element= size > 0 ? (uint32_t) size : 0;
00100   tree->memory_limit= memory_limit;
00101   tree->free= free_element;
00102   tree->allocated= 0;
00103   tree->elements_in_tree= 0;
00104   tree->custom_arg = custom_arg;
00105   tree->null_element.colour= BLACK;
00106   tree->null_element.left=tree->null_element.right= 0;
00107   tree->flag= 0;
00108   if (!free_element &&
00109       (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
00110   {
00111     /*
00112       We know that the data doesn't have to be aligned (like if the key
00113       contains a double), so we can store the data combined with the
00114       TREE_ELEMENT.
00115     */
00116     tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
00117     /* Fix allocation size so that we don't lose any memory */
00118     default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
00119     if (!default_alloc_size)
00120       default_alloc_size= 1;
00121     default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
00122   }
00123   else
00124   {
00125     tree->offset_to_key= 0;   /* use key through pointer */
00126     tree->size_of_element+= sizeof(void*);
00127   }
00128   if (! (tree->with_delete= with_delete))
00129   {
00130     tree->mem_root.init_alloc_root(default_alloc_size);
00131     tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
00132   }
00133 }
00134 
00135 static void free_tree(TREE *tree, myf free_flags)
00136 {
00137   if (tree->root)       /* If initialized */
00138   {
00139     if (tree->with_delete)
00140       delete_tree_element(tree,tree->root);
00141     else
00142     {
00143       if (tree->free)
00144       {
00145         if (tree->memory_limit)
00146           (*tree->free)(NULL, free_init, tree->custom_arg);
00147   delete_tree_element(tree,tree->root);
00148         if (tree->memory_limit)
00149           (*tree->free)(NULL, free_end, tree->custom_arg);
00150       }
00151       tree->mem_root.free_root(free_flags);
00152     }
00153   }
00154   tree->root= &tree->null_element;
00155   tree->elements_in_tree= 0;
00156   tree->allocated= 0;
00157 }
00158 
00159 void delete_tree(TREE* tree)
00160 {
00161   free_tree(tree, MYF(0)); /* free() mem_root if applicable */
00162 }
00163 
00164 void reset_tree(TREE* tree)
00165 {
00166   /* do not free mem_root, just mark blocks as free */
00167   free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
00168 }
00169 
00170 
00171 static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
00172 {
00173   if (element != &tree->null_element)
00174   {
00175     delete_tree_element(tree,element->left);
00176     if (tree->free)
00177       (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00178     delete_tree_element(tree,element->right);
00179     if (tree->with_delete)
00180       free((char*) element);
00181   }
00182 }
00183 
00184 
00185 /*
00186   insert, search and delete of elements
00187 
00188   The following should be true:
00189     parent[0] = & parent[-1][0]->left ||
00190     parent[0] = & parent[-1][0]->right
00191 */
00192 
00193 TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
00194                           void* custom_arg)
00195 {
00196   int cmp;
00197   TREE_ELEMENT *element,***parent;
00198 
00199   parent= tree->parents;
00200   *parent = &tree->root; element= tree->root;
00201   for (;;)
00202   {
00203     if (element == &tree->null_element ||
00204   (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00205                                 key)) == 0)
00206       break;
00207     if (cmp < 0)
00208     {
00209       *++parent= &element->right; element= element->right;
00210     }
00211     else
00212     {
00213       *++parent = &element->left; element= element->left;
00214     }
00215   }
00216   if (element == &tree->null_element)
00217   {
00218     size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
00219     tree->allocated+= alloc_size;
00220 
00221     if (tree->memory_limit && tree->elements_in_tree
00222                            && tree->allocated > tree->memory_limit)
00223     {
00224       reset_tree(tree);
00225       return tree_insert(tree, key, key_size, custom_arg);
00226     }
00227 
00228     key_size+= tree->size_of_element;
00229     if (tree->with_delete)
00230       element= (TREE_ELEMENT *) malloc(alloc_size);
00231     else
00232       element= (TREE_ELEMENT *) tree->mem_root.alloc_root(alloc_size);
00233     if (!element)
00234       return(NULL);
00235     **parent= element;
00236     element->left= element->right= &tree->null_element;
00237     if (!tree->offset_to_key)
00238     {
00239       if (key_size == sizeof(void*))     /* no length, save pointer */
00240   *((void**) (element+1))= key;
00241       else
00242       {
00243   *((void**) (element+1))= (void*) ((void **) (element+1)+1);
00244   memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
00245       }
00246     }
00247     else
00248       memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
00249     element->count= 1;      /* May give warning in purify */
00250     tree->elements_in_tree++;
00251     rb_insert(tree,parent,element); /* rebalance tree */
00252   }
00253   else
00254   {
00255     if (tree->flag & TREE_NO_DUPS)
00256       return(NULL);
00257     element->count++;
00258     /* Avoid a wrap over of the count. */
00259     if (! element->count)
00260       element->count--;
00261   }
00262 
00263   return element;
00264 }
00265 
00266 int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
00267 {
00268   int remove_colour;
00269   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
00270   if (!tree->with_delete)
00271     return 1;         /* not allowed */
00272 
00273   parent= tree->parents;
00274   *parent= &tree->root; element= tree->root;
00275   for (;;)
00276   {
00277     int cmp;
00278 
00279     if (element == &tree->null_element)
00280       return 1;       /* Was not in tree */
00281     if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00282                                 key)) == 0)
00283       break;
00284     if (cmp < 0)
00285     {
00286       *++parent= &element->right; element= element->right;
00287     }
00288     else
00289     {
00290       *++parent = &element->left; element= element->left;
00291     }
00292   }
00293   if (element->left == &tree->null_element)
00294   {
00295     (**parent)= element->right;
00296     remove_colour= element->colour;
00297   }
00298   else if (element->right == &tree->null_element)
00299   {
00300     (**parent)= element->left;
00301     remove_colour= element->colour;
00302   }
00303   else
00304   {
00305     org_parent= parent;
00306     *++parent= &element->right; nod= element->right;
00307     while (nod->left != &tree->null_element)
00308     {
00309       *++parent= &nod->left; nod= nod->left;
00310     }
00311     (**parent)= nod->right;   /* unlink nod from tree */
00312     remove_colour= nod->colour;
00313     org_parent[0][0]= nod;    /* put y in place of element */
00314     org_parent[1]= &nod->right;
00315     nod->left= element->left;
00316     nod->right= element->right;
00317     nod->colour= element->colour;
00318   }
00319   if (remove_colour == BLACK)
00320     rb_delete_fixup(tree,parent);
00321   if (tree->free)
00322     (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00323   tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
00324   free((unsigned char*) element);
00325   tree->elements_in_tree--;
00326 
00327   return 0;
00328 }
00329 
00330 void *tree_search_key(TREE *tree, const void *key,
00331                       TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
00332                       enum ha_rkey_function flag, void *custom_arg)
00333 {
00334   TREE_ELEMENT *element= tree->root;
00335   TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
00336   TREE_ELEMENT **last_equal_element= NULL;
00337 
00338 /*
00339   TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
00340 */
00341 
00342   *parents = &tree->null_element;
00343   while (element != &tree->null_element)
00344   {
00345     int cmp;
00346 
00347     *++parents= element;
00348 
00349     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
00350              key)) == 0)
00351     {
00352       switch (flag) {
00353       case HA_READ_KEY_EXACT:
00354       case HA_READ_KEY_OR_NEXT:
00355       case HA_READ_BEFORE_KEY:
00356   last_equal_element= parents;
00357   cmp= 1;
00358   break;
00359       case HA_READ_AFTER_KEY:
00360   cmp= -1;
00361   break;
00362       case HA_READ_PREFIX_LAST:
00363       case HA_READ_PREFIX_LAST_OR_PREV:
00364   last_equal_element= parents;
00365   cmp= -1;
00366   break;
00367       default:
00368   return NULL;
00369       }
00370     }
00371     if (cmp < 0) /* element < key */
00372     {
00373       last_right_step_parent= parents;
00374       element= element->right;
00375     }
00376     else
00377     {
00378       last_left_step_parent= parents;
00379       element= element->left;
00380     }
00381   }
00382   switch (flag) {
00383   case HA_READ_KEY_EXACT:
00384   case HA_READ_PREFIX_LAST:
00385     *last_pos= last_equal_element;
00386     break;
00387   case HA_READ_KEY_OR_NEXT:
00388     *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
00389     break;
00390   case HA_READ_AFTER_KEY:
00391     *last_pos= last_left_step_parent;
00392     break;
00393   case HA_READ_PREFIX_LAST_OR_PREV:
00394     *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
00395     break;
00396   case HA_READ_BEFORE_KEY:
00397     *last_pos= last_right_step_parent;
00398     break;
00399   default:
00400     return NULL;
00401   }
00402 
00403   return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
00404 }
00405 
00406 /*
00407   Search first (the most left) or last (the most right) tree element
00408 */
00409 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
00410            TREE_ELEMENT ***last_pos, int child_offs)
00411 {
00412   TREE_ELEMENT *element= tree->root;
00413 
00414   *parents= &tree->null_element;
00415   while (element != &tree->null_element)
00416   {
00417     *++parents= element;
00418     element= ELEMENT_CHILD(element, child_offs);
00419   }
00420   *last_pos= parents;
00421   return **last_pos != &tree->null_element ?
00422     ELEMENT_KEY(tree, **last_pos) : NULL;
00423 }
00424 
00425 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
00426                        int r_offs)
00427 {
00428   TREE_ELEMENT *x= **last_pos;
00429 
00430   if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
00431   {
00432     x= ELEMENT_CHILD(x, r_offs);
00433     *++*last_pos= x;
00434     while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
00435     {
00436       x= ELEMENT_CHILD(x, l_offs);
00437       *++*last_pos= x;
00438     }
00439     return ELEMENT_KEY(tree, x);
00440   }
00441   else
00442   {
00443     TREE_ELEMENT *y= *--*last_pos;
00444     while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
00445     {
00446       x= y;
00447       y= *--*last_pos;
00448     }
00449     return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
00450   }
00451 }
00452 
00453 /*
00454   Expected that tree is fully balanced
00455   (each path from root to leaf has the same length)
00456 */
00457 ha_rows tree_record_pos(TREE *tree, const void *key,
00458       enum ha_rkey_function flag, void *custom_arg)
00459 {
00460   TREE_ELEMENT *element= tree->root;
00461   double left= 1;
00462   double right= tree->elements_in_tree;
00463 
00464   while (element != &tree->null_element)
00465   {
00466     int cmp;
00467 
00468     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
00469              key)) == 0)
00470     {
00471       switch (flag) {
00472       case HA_READ_KEY_EXACT:
00473       case HA_READ_BEFORE_KEY:
00474         cmp= 1;
00475         break;
00476       case HA_READ_AFTER_KEY:
00477         cmp= -1;
00478         break;
00479       default:
00480         return HA_POS_ERROR;
00481       }
00482     }
00483     if (cmp < 0) /* element < key */
00484     {
00485       element= element->right;
00486       left= (left + right) / 2;
00487     }
00488     else
00489     {
00490       element= element->left;
00491       right= (left + right) / 2;
00492     }
00493   }
00494 
00495   switch (flag) {
00496   case HA_READ_KEY_EXACT:
00497   case HA_READ_BEFORE_KEY:
00498     return (ha_rows) right;
00499   case HA_READ_AFTER_KEY:
00500     return (ha_rows) left;
00501   default:
00502     return HA_POS_ERROR;
00503   }
00504 }
00505 
00506 int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
00507 {
00508   switch (visit) {
00509   case left_root_right:
00510     return tree_walk_left_root_right(tree,tree->root,action,argument);
00511   case right_root_left:
00512     return tree_walk_right_root_left(tree,tree->root,action,argument);
00513   }
00514 
00515   return 0;     /* Keep gcc happy */
00516 }
00517 
00518 static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
00519 {
00520   int error;
00521   if (element->left)        /* Not null_element */
00522   {
00523     if ((error=tree_walk_left_root_right(tree,element->left,action,
00524             argument)) == 0 &&
00525   (error=(*action)(ELEMENT_KEY(tree,element),
00526         element->count,
00527         argument)) == 0)
00528       error=tree_walk_left_root_right(tree,element->right,action,argument);
00529     return error;
00530   }
00531 
00532   return 0;
00533 }
00534 
00535 static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
00536 {
00537   int error;
00538   if (element->right)       /* Not null_element */
00539   {
00540     if ((error=tree_walk_right_root_left(tree,element->right,action,
00541             argument)) == 0 &&
00542   (error=(*action)(ELEMENT_KEY(tree,element),
00543         element->count,
00544         argument)) == 0)
00545      error=tree_walk_right_root_left(tree,element->left,action,argument);
00546     return error;
00547   }
00548 
00549   return 0;
00550 }
00551 
00552 
00553 /* Functions to fix up the tree after insert and delete */
00554 
00555 static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
00556 {
00557   TREE_ELEMENT *y;
00558 
00559   y= leaf->right;
00560   leaf->right= y->left;
00561   parent[0]= y;
00562   y->left= leaf;
00563 }
00564 
00565 static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
00566 {
00567   TREE_ELEMENT *x;
00568 
00569   x= leaf->left;
00570   leaf->left= x->right;
00571   parent[0]= x;
00572   x->right= leaf;
00573 }
00574 
00575 static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
00576 {
00577   TREE_ELEMENT *y,*par,*par2;
00578 
00579   leaf->colour=RED;
00580   while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
00581   {
00582     if (par == (par2=parent[-2][0])->left)
00583     {
00584       y= par2->right;
00585       if (y->colour == RED)
00586       {
00587   par->colour= BLACK;
00588   y->colour= BLACK;
00589   leaf= par2;
00590   parent-= 2;
00591   leaf->colour= RED;    /* And the loop continues */
00592       }
00593       else
00594       {
00595   if (leaf == par->right)
00596   {
00597     left_rotate(parent[-1],par);
00598     par= leaf;      /* leaf is now parent to old leaf */
00599   }
00600   par->colour= BLACK;
00601   par2->colour= RED;
00602   right_rotate(parent[-2],par2);
00603   break;
00604       }
00605     }
00606     else
00607     {
00608       y= par2->left;
00609       if (y->colour == RED)
00610       {
00611   par->colour= BLACK;
00612   y->colour= BLACK;
00613   leaf= par2;
00614   parent-= 2;
00615   leaf->colour= RED;    /* And the loop continues */
00616       }
00617       else
00618       {
00619   if (leaf == par->left)
00620   {
00621     right_rotate(parent[-1],par);
00622     par= leaf;
00623   }
00624   par->colour= BLACK;
00625   par2->colour= RED;
00626   left_rotate(parent[-2],par2);
00627   break;
00628       }
00629     }
00630   }
00631   tree->root->colour=BLACK;
00632 }
00633 
00634 static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
00635 {
00636   TREE_ELEMENT *x,*w,*par;
00637 
00638   x= **parent;
00639   while (x != tree->root && x->colour == BLACK)
00640   {
00641     if (x == (par=parent[-1][0])->left)
00642     {
00643       w= par->right;
00644       if (w->colour == RED)
00645       {
00646   w->colour= BLACK;
00647   par->colour= RED;
00648   left_rotate(parent[-1],par);
00649   parent[0]= &w->left;
00650   *++parent= &par->left;
00651   w= par->right;
00652       }
00653       if (w->left->colour == BLACK && w->right->colour == BLACK)
00654       {
00655   w->colour= RED;
00656   x= par;
00657   parent--;
00658       }
00659       else
00660       {
00661   if (w->right->colour == BLACK)
00662   {
00663     w->left->colour= BLACK;
00664     w->colour= RED;
00665     right_rotate(&par->right,w);
00666     w= par->right;
00667   }
00668   w->colour= par->colour;
00669   par->colour= BLACK;
00670   w->right->colour= BLACK;
00671   left_rotate(parent[-1],par);
00672   x= tree->root;
00673   break;
00674       }
00675     }
00676     else
00677     {
00678       w=par->left;
00679       if (w->colour == RED)
00680       {
00681   w->colour= BLACK;
00682   par->colour= RED;
00683   right_rotate(parent[-1],par);
00684   parent[0]= &w->right;
00685   *++parent= &par->right;
00686   w= par->left;
00687       }
00688       if (w->right->colour == BLACK && w->left->colour == BLACK)
00689       {
00690   w->colour= RED;
00691   x= par;
00692   parent--;
00693       }
00694       else
00695       {
00696   if (w->left->colour == BLACK)
00697   {
00698     w->right->colour= BLACK;
00699     w->colour= RED;
00700     left_rotate(&par->left,w);
00701     w= par->left;
00702   }
00703   w->colour= par->colour;
00704   par->colour= BLACK;
00705   w->left->colour= BLACK;
00706   right_rotate(parent[-1],par);
00707   x= tree->root;
00708   break;
00709       }
00710     }
00711   }
00712   x->colour= BLACK;
00713 }
00714 
00715 } /* namespace drizzled */