The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/mysys/tree.c File Reference

mysql/src/5.1-dbg/mysys/tree.c File Reference

#include "mysys_priv.h"
#include <m_string.h>
#include <my_tree.h>
#include "my_base.h"

Include dependency graph for tree.c:


Defines
#define	BLACK 1
#define	RED 0
#define	DEFAULT_ALLOC_SIZE 8192
#define	DEFAULT_ALIGN_SIZE 8192
Functions
static void	delete_tree_element (TREE , TREE_ELEMENT )
static int	tree_walk_left_root_right (TREE , TREE_ELEMENT , tree_walk_action, void *)
static int	tree_walk_right_root_left (TREE , TREE_ELEMENT , tree_walk_action, void *)
static void	left_rotate (TREE_ELEMENT *parent, TREE_ELEMENT leaf)
static void	right_rotate (TREE_ELEMENT *parent, TREE_ELEMENT leaf)
static void	rb_insert (TREE tree, TREE_ELEMENT *parent, TREE_ELEMENT leaf)
static void	rb_delete_fixup (TREE tree, TREE_ELEMENT **parent)
static int	test_rb_tree (TREE_ELEMENT *element)
void	init_tree (TREE tree, uint default_alloc_size, uint memory_limit, int size, qsort_cmp2 compare, my_bool with_delete, tree_element_free free_element, void custom_arg)
static void	free_tree (TREE *tree, myf free_flags)
void	delete_tree (TREE *tree)
void	reset_tree (TREE *tree)
TREE_ELEMENT *	tree_insert (TREE tree, void key, uint key_size, void *custom_arg)
int	tree_delete (TREE tree, void key, uint key_size, void *custom_arg)
void *	tree_search (TREE tree, void key, void *custom_arg)
void *	tree_search_key (TREE tree, const void key, TREE_ELEMENT parents, TREE_ELEMENT last_pos, enum ha_rkey_function flag, void custom_arg)
void *	tree_search_edge (TREE tree, TREE_ELEMENT parents, TREE_ELEMENT **last_pos, int child_offs)
void *	tree_search_next (TREE tree, TREE_ELEMENT **last_pos, int l_offs, int r_offs)
ha_rows	tree_record_pos (TREE tree, const void key, enum ha_rkey_function flag, void *custom_arg)
int	tree_walk (TREE tree, tree_walk_action action, void argument, TREE_WALK visit)

Define Documentation

#define BLACK 1

Definition at line 64 of file tree.c.

Referenced by init_tree(), rb_delete_fixup(), rb_insert(), and test_rb_tree().

#define DEFAULT_ALIGN_SIZE 8192

Definition at line 67 of file tree.c.

Referenced by init_tree().

#define DEFAULT_ALLOC_SIZE 8192

Definition at line 66 of file tree.c.

Referenced by init_tree().

#define RED 0

Definition at line 65 of file tree.c.

Referenced by rb_delete_fixup(), rb_insert(), and test_rb_tree().

Function Documentation

void delete_tree ( TREE * tree )

Definition at line 166 of file tree.c.

References free_tree(), and MYF.

Referenced by field_str::add(), field_real::add(), field_decimal::add(), field_longlong::add(), field_ulonglong::add(), Item_func_group_concat::cleanup(), fakebigcodes(), free_counts_and_tree_and_queue(), ft_add_word(), ft_boolean_close_search(), ft_free_stopwords(), ft_init_nlq_search(), ft_linearize(), hp_clear_keys(), mi_end_bulk_insert(), and field_info::~field_info().

00167 {
00168   free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */
00169 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void delete_tree_element	(	TREE *	,
		TREE_ELEMENT *
	)			`[static]`

Definition at line 178 of file tree.c.

References st_tree::custom_arg, ELEMENT_KEY, st_tree::free, free_free, st_tree_element::left, my_free, MYF, st_tree::null_element, st_tree_element::right, and st_tree::with_delete.

Referenced by free_tree().

00179 {
00180   if (element != &tree->null_element)
00181   {
00182     delete_tree_element(tree,element->left);
00183     if (tree->free)
00184       (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00185     delete_tree_element(tree,element->right);
00186     if (tree->with_delete)
00187       my_free((char*) element,MYF(0));
00188   }
00189 }

Here is the caller graph for this function:

static void free_tree	(	TREE *	tree,
		myf	free_flags
	)			`[static]`

Definition at line 137 of file tree.c.

References st_tree::allocated, st_tree::custom_arg, DBUG_ENTER, DBUG_PRINT, DBUG_VOID_RETURN, delete_tree_element(), st_tree::elements_in_tree, st_tree::free, free_end, free_init, free_root(), st_tree::mem_root, st_tree::memory_limit, NULL, st_tree::null_element, st_tree::root, and st_tree::with_delete.

Referenced by delete_tree(), and reset_tree().

00138 {
00139   DBUG_ENTER("free_tree");
00140   DBUG_PRINT("enter",("tree: 0x%lx",tree));
00141 
00142   if (tree->root)                               /* If initialized */
00143   {
00144     if (tree->with_delete)
00145       delete_tree_element(tree,tree->root);
00146     else
00147     {
00148       if (tree->free)
00149       {
00150         if (tree->memory_limit)
00151           (*tree->free)(NULL, free_init, tree->custom_arg);
00152         delete_tree_element(tree,tree->root);
00153         if (tree->memory_limit)
00154           (*tree->free)(NULL, free_end, tree->custom_arg);
00155       }
00156       free_root(&tree->mem_root, free_flags);
00157     }
00158   }
00159   tree->root= &tree->null_element;
00160   tree->elements_in_tree=0;
00161   tree->allocated=0;
00162 
00163   DBUG_VOID_RETURN;
00164 }

Here is the call graph for this function:

Here is the caller graph for this function:

void init_tree	(	TREE *	tree,
		uint	default_alloc_size,
		uint	memory_limit,
		int	size,
		qsort_cmp2	compare,
		my_bool	with_delete,
		tree_element_free	free_element,
		void *	custom_arg
	)

Definition at line 87 of file tree.c.

References st_tree::allocated, BLACK, bzero, st_tree_element::colour, st_tree::compare, st_tree::custom_arg, DBUG_ENTER, DBUG_PRINT, DBUG_VOID_RETURN, DEFAULT_ALIGN_SIZE, DEFAULT_ALLOC_SIZE, st_tree::elements_in_tree, st_tree::flag, st_tree::free, init_alloc_root(), st_tree_element::left, st_tree::mem_root, st_tree::memory_limit, st_mem_root::min_malloc, MY_ALIGN, st_tree::null_element, st_tree::offset_to_key, st_tree_element::right, st_tree::root, st_tree::size_of_element, and st_tree::with_delete.

Referenced by _ftb_init_index_search(), examine_log(), field_decimal::field_decimal(), field_longlong::field_longlong(), field_real::field_real(), field_str::field_str(), field_ulonglong::field_ulonglong(), ft_init_nlq_search(), ft_init_stopwords(), ft_parse_init(), init_huff_count(), and Item_func_group_concat::setup().

00090 {
00091   DBUG_ENTER("init_tree");
00092   DBUG_PRINT("enter",("tree: 0x%lx  size: %d",tree,size));
00093 
00094   if (default_alloc_size < DEFAULT_ALLOC_SIZE)
00095     default_alloc_size= DEFAULT_ALLOC_SIZE;
00096   default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
00097   bzero((gptr) &tree->null_element,sizeof(tree->null_element));
00098   tree->root= &tree->null_element;
00099   tree->compare=compare;
00100   tree->size_of_element=size > 0 ? (uint) size : 0;
00101   tree->memory_limit=memory_limit;
00102   tree->free=free_element;
00103   tree->allocated=0;
00104   tree->elements_in_tree=0;
00105   tree->custom_arg = custom_arg;
00106   tree->null_element.colour=BLACK;
00107   tree->null_element.left=tree->null_element.right=0;
00108   tree->flag= 0;
00109   if (!free_element && size >= 0 &&
00110       ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
00111   {
00112     /*
00113       We know that the data doesn't have to be aligned (like if the key
00114       contains a double), so we can store the data combined with the
00115       TREE_ELEMENT.
00116     */
00117     tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
00118     /* Fix allocation size so that we don't lose any memory */
00119     default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
00120     if (!default_alloc_size)
00121       default_alloc_size=1;
00122     default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
00123   }
00124   else
00125   {
00126     tree->offset_to_key=0;              /* use key through pointer */
00127     tree->size_of_element+=sizeof(void*);
00128   }
00129   if (!(tree->with_delete=with_delete))
00130   {
00131     init_alloc_root(&tree->mem_root, default_alloc_size,0);
00132     tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
00133   }
00134   DBUG_VOID_RETURN;
00135 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void left_rotate	(	TREE_ELEMENT **	parent,
		TREE_ELEMENT *	leaf
	)			`[static]`

Definition at line 572 of file tree.c.

References st_tree_element::left, and st_tree_element::right.

Referenced by rb_delete_fixup(), SEL_ARG::rb_insert(), and rb_insert().

00573 {
00574   TREE_ELEMENT *y;
00575 
00576   y=leaf->right;
00577   leaf->right=y->left;
00578   parent[0]=y;
00579   y->left=leaf;
00580 }

Here is the caller graph for this function:

static void rb_delete_fixup	(	TREE *	tree,
		TREE_ELEMENT ***	parent
	)			`[static]`

Definition at line 651 of file tree.c.

References BLACK, st_tree_element::colour, st_tree_element::left, left_rotate(), RED, st_tree_element::right, right_rotate(), st_tree::root, and x.

00652 {
00653   TREE_ELEMENT *x,*w,*par;
00654 
00655   x= **parent;
00656   while (x != tree->root && x->colour == BLACK)
00657   {
00658     if (x == (par=parent[-1][0])->left)
00659     {
00660       w=par->right;
00661       if (w->colour == RED)
00662       {
00663         w->colour=BLACK;
00664         par->colour=RED;
00665         left_rotate(parent[-1],par);
00666         parent[0]= &w->left;
00667         *++parent= &par->left;
00668         w=par->right;
00669       }
00670       if (w->left->colour == BLACK && w->right->colour == BLACK)
00671       {
00672         w->colour=RED;
00673         x=par;
00674         parent--;
00675       }
00676       else
00677       {
00678         if (w->right->colour == BLACK)
00679         {
00680           w->left->colour=BLACK;
00681           w->colour=RED;
00682           right_rotate(&par->right,w);
00683           w=par->right;
00684         }
00685         w->colour=par->colour;
00686         par->colour=BLACK;
00687         w->right->colour=BLACK;
00688         left_rotate(parent[-1],par);
00689         x=tree->root;
00690         break;
00691       }
00692     }
00693     else
00694     {
00695       w=par->left;
00696       if (w->colour == RED)
00697       {
00698         w->colour=BLACK;
00699         par->colour=RED;
00700         right_rotate(parent[-1],par);
00701         parent[0]= &w->right;
00702         *++parent= &par->right;
00703         w=par->left;
00704       }
00705       if (w->right->colour == BLACK && w->left->colour == BLACK)
00706       {
00707         w->colour=RED;
00708         x=par;
00709         parent--;
00710       }
00711       else
00712       {
00713         if (w->left->colour == BLACK)
00714         {
00715           w->right->colour=BLACK;
00716           w->colour=RED;
00717           left_rotate(&par->left,w);
00718           w=par->left;
00719         }
00720         w->colour=par->colour;
00721         par->colour=BLACK;
00722         w->left->colour=BLACK;
00723         right_rotate(parent[-1],par);
00724         x=tree->root;
00725         break;
00726       }
00727     }
00728   }
00729   x->colour=BLACK;
00730 }

Here is the call graph for this function:

static void rb_insert	(	TREE *	tree,
		TREE_ELEMENT ***	parent,
		TREE_ELEMENT *	leaf
	)			`[static]`

Definition at line 592 of file tree.c.

References BLACK, st_tree_element::colour, st_tree_element::left, left_rotate(), RED, st_tree_element::right, right_rotate(), and st_tree::root.

00593 {
00594   TREE_ELEMENT *y,*par,*par2;
00595 
00596   leaf->colour=RED;
00597   while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
00598   {
00599     if (par == (par2=parent[-2][0])->left)
00600     {
00601       y= par2->right;
00602       if (y->colour == RED)
00603       {
00604         par->colour=BLACK;
00605         y->colour=BLACK;
00606         leaf=par2;
00607         parent-=2;
00608         leaf->colour=RED;               /* And the loop continues */
00609       }
00610       else
00611       {
00612         if (leaf == par->right)
00613         {
00614           left_rotate(parent[-1],par);
00615           par=leaf;                     /* leaf is now parent to old leaf */
00616         }
00617         par->colour=BLACK;
00618         par2->colour=RED;
00619         right_rotate(parent[-2],par2);
00620         break;
00621       }
00622     }
00623     else
00624     {
00625       y= par2->left;
00626       if (y->colour == RED)
00627       {
00628         par->colour=BLACK;
00629         y->colour=BLACK;
00630         leaf=par2;
00631         parent-=2;
00632         leaf->colour=RED;               /* And the loop continues */
00633       }
00634       else
00635       {
00636         if (leaf == par->left)
00637         {
00638           right_rotate(parent[-1],par);
00639           par=leaf;
00640         }
00641         par->colour=BLACK;
00642         par2->colour=RED;
00643         left_rotate(parent[-2],par2);
00644         break;
00645       }
00646     }
00647   }
00648   tree->root->colour=BLACK;
00649 }

Here is the call graph for this function:

void reset_tree ( TREE * tree )

Definition at line 171 of file tree.c.

References free_tree(), MY_MARK_BLOCKS_FREE, and MYF.

Referenced by _ftb_init_index_search(), Item_func_group_concat::clear(), ft_init_nlq_search(), mi_flush_bulk_insert(), and tree_insert().

00172 {
00173   /* do not free mem_root, just mark blocks as free */
00174   free_tree(tree, MYF(MY_MARK_BLOCKS_FREE));
00175 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void right_rotate	(	TREE_ELEMENT **	parent,
		TREE_ELEMENT *	leaf
	)			`[static]`

Definition at line 582 of file tree.c.

References st_tree_element::left, and x.

Referenced by rb_delete_fixup(), SEL_ARG::rb_insert(), and rb_insert().

00583 {
00584   TREE_ELEMENT *x;
00585 
00586   x=leaf->left;
00587   leaf->left=x->right;
00588   parent[0]=x;
00589   x->right=leaf;
00590 }

Here is the caller graph for this function:

static int test_rb_tree ( TREE_ELEMENT * element ) [static]

Definition at line 736 of file tree.c.

References BLACK, st_tree_element::colour, st_tree_element::left, RED, st_tree_element::right, and test_rb_tree.

00737 {
00738   int count_l,count_r;
00739 
00740   if (!element->left)
00741     return 0;                           /* Found end of tree */
00742   if (element->colour == RED &&
00743       (element->left->colour == RED || element->right->colour == RED))
00744   {
00745     printf("Wrong tree: Found two red in a row\n");
00746     return -1;
00747   }
00748   count_l=test_rb_tree(element->left);
00749   count_r=test_rb_tree(element->right);
00750   if (count_l >= 0 && count_r >= 0)
00751   {
00752     if (count_l == count_r)
00753       return count_l+(element->colour == BLACK);
00754     printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
00755   }
00756   return -1;
00757 }

int tree_delete	(	TREE *	tree,
		void *	key,
		uint	key_size,
		void *	custom_arg
	)

Definition at line 274 of file tree.c.

References cmp, st_tree_element::colour, st_tree::compare, ELEMENT_KEY, st_tree_element::left, st_tree::null_element, st_tree::parents, st_tree_element::right, st_tree::root, and st_tree::with_delete.

Referenced by examine_log(), and hp_rb_delete_key().

00275 {
00276   int cmp,remove_colour;
00277   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
00278   if (!tree->with_delete)
00279     return 1;                                   /* not allowed */
00280 
00281   parent= tree->parents;
00282   *parent= &tree->root; element= tree->root;
00283   for (;;)
00284   {
00285     if (element == &tree->null_element)
00286       return 1;                         /* Was not in tree */
00287     if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00288                                 key)) == 0)
00289       break;
00290     if (cmp < 0)
00291     {
00292       *++parent= &element->right; element= element->right;
00293     }
00294     else
00295     {
00296       *++parent = &element->left; element= element->left;
00297     }
00298   }
00299   if (element->left == &tree->null_element)
00300   {
00301     (**parent)=element->right;
00302     remove_colour= element->colour;
00303   }
00304   else if (element->right == &tree->null_element)
00305   {
00306     (**parent)=element->left;
00307     remove_colour= element->colour;
00308   }
00309   else
00310   {
00311     org_parent= parent;
00312     *++parent= &element->right; nod= element->right;
00313     while (nod->left != &tree->null_element)
00314     {
00315       *++parent= &nod->left; nod= nod->left;
00316     }
00317     (**parent)=nod->right;              /* unlink nod from tree */
00318     remove_colour= nod->colour;
00319     org_parent[0][0]=nod;               /* put y in place of element */
00320     org_parent[1]= &nod->right;
00321     nod->left=element->left;
00322     nod->right=element->right;
00323     nod->colour=element->colour;
00324   }
00325   if (remove_colour == BLACK)
00326     rb_delete_fixup(tree,parent);
00327   if (tree->free)
00328     (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00329   tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
00330   my_free((gptr) element,MYF(0));
00331   tree->elements_in_tree--;
00332   return 0;
00333 }

Here is the caller graph for this function:

TREE_ELEMENT* tree_insert	(	TREE *	tree,
		void *	key,
		uint	key_size,
		void *	custom_arg
	)

Definition at line 200 of file tree.c.

References st_tree::allocated, cmp, st_tree::compare, ELEMENT_KEY, st_tree::elements_in_tree, st_tree_element::left, st_tree::memory_limit, st_tree::null_element, st_tree::parents, reset_tree(), st_tree_element::right, st_tree::root, st_tree::size_of_element, and tree_insert().

Referenced by _mi_ck_write_tree(), Item_func_group_concat::add(), field_str::add(), field_real::add(), field_decimal::add(), field_longlong::add(), field_ulonglong::add(), examine_log(), ft_add_stopword(), ft_add_word(), ft_boolean_read_next(), hp_rb_write_key(), tree_insert(), and walk_and_match().

00202 {
00203   int cmp;
00204   TREE_ELEMENT *element,***parent;
00205 
00206   parent= tree->parents;
00207   *parent = &tree->root; element= tree->root;
00208   for (;;)
00209   {
00210     if (element == &tree->null_element ||
00211         (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00212                                 key)) == 0)
00213       break;
00214     if (cmp < 0)
00215     {
00216       *++parent= &element->right; element= element->right;
00217     }
00218     else
00219     {
00220       *++parent = &element->left; element= element->left;
00221     }
00222   }
00223   if (element == &tree->null_element)
00224   {
00225     uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
00226     tree->allocated+=alloc_size;
00227 
00228     if (tree->memory_limit && tree->elements_in_tree
00229                            && tree->allocated > tree->memory_limit)
00230     {
00231       reset_tree(tree);
00232       return tree_insert(tree, key, key_size, custom_arg);
00233     }
00234 
00235     key_size+=tree->size_of_element;
00236     if (tree->with_delete)
00237       element=(TREE_ELEMENT *) my_malloc(alloc_size, MYF(MY_WME));
00238     else
00239       element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
00240     if (!element)
00241       return(NULL);
00242     **parent=element;
00243     element->left=element->right= &tree->null_element;
00244     if (!tree->offset_to_key)
00245     {
00246       if (key_size == sizeof(void*))             /* no length, save pointer */
00247         *((void**) (element+1))=key;
00248       else
00249       {
00250         *((void**) (element+1))= (void*) ((void **) (element+1)+1);
00251         memcpy((byte*) *((void **) (element+1)),key,
00252                (size_t) (key_size-sizeof(void*)));
00253       }
00254     }
00255     else
00256       memcpy((byte*) element+tree->offset_to_key,key,(size_t) key_size);
00257     element->count=1;                   /* May give warning in purify */
00258     tree->elements_in_tree++;
00259     rb_insert(tree,parent,element);     /* rebalance tree */
00260   }
00261   else
00262   {
00263     if (tree->flag & TREE_NO_DUPS)
00264       return(NULL);
00265     element->count++;
00266     /* Avoid a wrap over of the count. */
00267     if (! element->count)
00268       element->count--;
00269   }
00270   DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
00271   return element;
00272 }

Here is the call graph for this function:

Here is the caller graph for this function:

ha_rows tree_record_pos	(	TREE *	tree,
		const void *	key,
		enum ha_rkey_function	flag,
		void *	custom_arg
	)

Definition at line 479 of file tree.c.

References cmp, st_tree::compare, ELEMENT_KEY, st_tree::elements_in_tree, HA_POS_ERROR, HA_READ_AFTER_KEY, HA_READ_BEFORE_KEY, HA_READ_KEY_EXACT, st_tree_element::left, st_tree::null_element, st_tree_element::right, and st_tree::root.

Referenced by hp_rb_records_in_range().

00481 {
00482   int cmp;
00483   TREE_ELEMENT *element= tree->root;
00484   double left= 1;
00485   double right= tree->elements_in_tree;
00486 
00487   while (element != &tree->null_element)
00488   {
00489     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
00490                                key)) == 0)
00491     {
00492       switch (flag) {
00493       case HA_READ_KEY_EXACT:
00494       case HA_READ_BEFORE_KEY:
00495         cmp= 1;
00496         break;
00497       case HA_READ_AFTER_KEY:
00498         cmp= -1;
00499         break;
00500       default:
00501         return HA_POS_ERROR;
00502       }
00503     }
00504     if (cmp < 0) /* element < key */
00505     {
00506       element= element->right;
00507       left= (left + right) / 2;
00508     }
00509     else
00510     {
00511       element= element->left;
00512       right= (left + right) / 2;
00513     }
00514   }
00515   switch (flag) {
00516   case HA_READ_KEY_EXACT:
00517   case HA_READ_BEFORE_KEY:
00518     return (ha_rows) right;
00519   case HA_READ_AFTER_KEY:
00520     return (ha_rows) left;
00521   default:
00522     return HA_POS_ERROR;
00523   }
00524 }

Here is the caller graph for this function:

void* tree_search	(	TREE *	tree,
		void *	key,
		void *	custom_arg
	)

Definition at line 336 of file tree.c.

References cmp, st_tree::compare, ELEMENT_KEY, st_tree_element::left, st_tree::null_element, st_tree_element::right, and st_tree::root.

Referenced by field_str::add(), examine_log(), and is_stopword().

00337 {
00338   int cmp;
00339   TREE_ELEMENT *element=tree->root;
00340 
00341   for (;;)
00342   {
00343     if (element == &tree->null_element)
00344       return (void*) 0;
00345     if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00346                                 key)) == 0)
00347       return ELEMENT_KEY(tree,element);
00348     if (cmp < 0)
00349       element=element->right;
00350     else
00351       element=element->left;
00352   }
00353 }

Here is the caller graph for this function:

void* tree_search_edge	(	TREE *	tree,
		TREE_ELEMENT **	parents,
		TREE_ELEMENT ***	last_pos,
		int	child_offs
	)

Definition at line 431 of file tree.c.

References ELEMENT_CHILD, ELEMENT_KEY, st_tree::null_element, and st_tree::root.

Referenced by check_one_rb_key(), heap_rfirst(), and heap_rlast().

00433 {
00434   TREE_ELEMENT *element= tree->root;
00435   
00436   *parents= &tree->null_element;
00437   while (element != &tree->null_element)
00438   {
00439     *++parents= element;
00440     element= ELEMENT_CHILD(element, child_offs);
00441   }
00442   *last_pos= parents;
00443   return **last_pos != &tree->null_element ? 
00444     ELEMENT_KEY(tree, **last_pos) : NULL;
00445 }

Here is the caller graph for this function:

void* tree_search_key	(	TREE *	tree,
		const void *	key,
		TREE_ELEMENT **	parents,
		TREE_ELEMENT ***	last_pos,
		enum ha_rkey_function	flag,
		void *	custom_arg
	)

Definition at line 355 of file tree.c.

References cmp, st_tree::compare, ELEMENT_KEY, HA_READ_AFTER_KEY, HA_READ_BEFORE_KEY, HA_READ_KEY_EXACT, HA_READ_KEY_OR_NEXT, HA_READ_PREFIX_LAST, HA_READ_PREFIX_LAST_OR_PREV, st_tree_element::left, st_tree::null_element, st_tree_element::right, and st_tree::root.

Referenced by heap_rkey(), heap_rnext(), and heap_rprev().

00358 {
00359   int cmp;
00360   TREE_ELEMENT *element= tree->root;
00361   TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
00362   TREE_ELEMENT **last_equal_element= NULL;
00363 
00364 /* 
00365   TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
00366 */
00367 
00368   *parents = &tree->null_element;
00369   while (element != &tree->null_element)
00370   {
00371     *++parents= element;
00372     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
00373                                key)) == 0)
00374     {
00375       switch (flag) {
00376       case HA_READ_KEY_EXACT:
00377       case HA_READ_KEY_OR_NEXT:
00378       case HA_READ_BEFORE_KEY:
00379         last_equal_element= parents;
00380         cmp= 1;
00381         break;
00382       case HA_READ_AFTER_KEY:
00383         cmp= -1;
00384         break;
00385       case HA_READ_PREFIX_LAST:
00386       case HA_READ_PREFIX_LAST_OR_PREV:
00387         last_equal_element= parents;
00388         cmp= -1;
00389         break;
00390       default:
00391         return NULL;
00392       }
00393     }
00394     if (cmp < 0) /* element < key */
00395     {
00396       last_right_step_parent= parents;
00397       element= element->right;
00398     }
00399     else
00400     {
00401       last_left_step_parent= parents;
00402       element= element->left;
00403     }
00404   }
00405   switch (flag) {
00406   case HA_READ_KEY_EXACT:
00407   case HA_READ_PREFIX_LAST:
00408     *last_pos= last_equal_element;
00409     break;
00410   case HA_READ_KEY_OR_NEXT:
00411     *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
00412     break;
00413   case HA_READ_AFTER_KEY:
00414     *last_pos= last_left_step_parent;
00415     break;
00416   case HA_READ_PREFIX_LAST_OR_PREV:
00417     *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
00418     break;
00419   case HA_READ_BEFORE_KEY:
00420     *last_pos= last_right_step_parent;
00421     break;
00422   default:
00423     return NULL;
00424   }
00425   return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
00426 }

Here is the caller graph for this function:

void* tree_search_next	(	TREE *	tree,
		TREE_ELEMENT ***	last_pos,
		int	l_offs,
		int	r_offs
	)

Definition at line 447 of file tree.c.

References ELEMENT_CHILD, ELEMENT_KEY, st_tree::null_element, and x.

Referenced by check_one_rb_key(), heap_rnext(), and heap_rprev().

00449 {
00450   TREE_ELEMENT *x= **last_pos;
00451   
00452   if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
00453   {
00454     x= ELEMENT_CHILD(x, r_offs);
00455     *++*last_pos= x;
00456     while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
00457     {
00458       x= ELEMENT_CHILD(x, l_offs);
00459       *++*last_pos= x;
00460     }
00461     return ELEMENT_KEY(tree, x);
00462   }
00463   else
00464   {
00465     TREE_ELEMENT *y= *--*last_pos;
00466     while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
00467     {
00468       x= y;
00469       y= *--*last_pos;
00470     }
00471     return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
00472   }
00473 }

Here is the caller graph for this function:

int tree_walk	(	TREE *	tree,
		tree_walk_action	action,
		void *	argument,
		TREE_WALK	visit
	)

Definition at line 526 of file tree.c.

References left_root_right, right_root_left, st_tree::root, tree_walk_left_root_right(), and tree_walk_right_root_left().

Referenced by close_some_file(), analyse::end_of_records(), examine_log(), ft_init_nlq_search(), ft_linearize(), and Item_func_group_concat::val_str().

00527 {
00528   switch (visit) {
00529   case left_root_right:
00530     return tree_walk_left_root_right(tree,tree->root,action,argument);
00531   case right_root_left:
00532     return tree_walk_right_root_left(tree,tree->root,action,argument);
00533   }
00534   return 0;                     /* Keep gcc happy */
00535 }

Here is the call graph for this function:

Here is the caller graph for this function:

static int tree_walk_left_root_right	(	TREE *	,
		TREE_ELEMENT *	,
		tree_walk_action	,
		void *
	)			`[static]`

Definition at line 537 of file tree.c.

References st_tree_element::count, ELEMENT_KEY, error, st_tree_element::left, and st_tree_element::right.

Referenced by tree_walk().

00538 {
00539   int error;
00540   if (element->left)                            /* Not null_element */
00541   {
00542     if ((error=tree_walk_left_root_right(tree,element->left,action,
00543                                           argument)) == 0 &&
00544         (error=(*action)(ELEMENT_KEY(tree,element),
00545                           (element_count) element->count,
00546                           argument)) == 0)
00547       error=tree_walk_left_root_right(tree,element->right,action,argument);
00548     return error;
00549   }
00550   return 0;
00551 }

Here is the caller graph for this function:

static int tree_walk_right_root_left	(	TREE *	,
		TREE_ELEMENT *	,
		tree_walk_action	,
		void *
	)			`[static]`

Definition at line 553 of file tree.c.

References st_tree_element::count, ELEMENT_KEY, error, st_tree_element::left, and st_tree_element::right.

Referenced by tree_walk().

00554 {
00555   int error;
00556   if (element->right)                           /* Not null_element */
00557   {
00558     if ((error=tree_walk_right_root_left(tree,element->right,action,
00559                                           argument)) == 0 &&
00560         (error=(*action)(ELEMENT_KEY(tree,element),
00561                           (element_count) element->count,
00562                           argument)) == 0)
00563      error=tree_walk_right_root_left(tree,element->left,action,argument);
00564     return error;
00565   }
00566   return 0;
00567 }

Here is the caller graph for this function:

Generated on Sat Sep 9 02:12:00 2006 for MySQL 5.1 by

1.4.7

The world's most popular open source database

mysql/src/5.1-dbg/mysys/tree.c File Reference

Defines

Functions

Define Documentation

Function Documentation