The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/include/my_tree.h File Reference

mysql/src/5.1-dbg/include/my_tree.h File Reference

#include "my_base.h"

Include dependency graph for my_tree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


Classes
struct	st_tree_element
struct	st_tree
Defines
#define	MAX_TREE_HEIGHT 64
#define	ELEMENT_KEY(tree, element)
#define	tree_set_pointer(element, ptr) ((byte ) (element+1))=((byte) (ptr))
#define	TREE_NO_DUPS 1
#define	ELEMENT_CHILD(element, offs) ((TREE_ELEMENT)((char)element + offs))
#define	is_tree_inited(tree) ((tree)->root != 0)
#define	TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void*))
Typedefs
typedef uint32	element_count
typedef int(*)	tree_walk_action (void , element_count, void )
typedef void(*)	tree_element_free (void , TREE_FREE, void )
typedef st_tree_element	TREE_ELEMENT
typedef st_tree	TREE
Enumerations
enum	TREE_WALK { left_root_right, right_root_left }
enum	TREE_FREE { free_init, free_free, free_end }
Functions
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)
void	delete_tree (TREE *)
void	reset_tree (TREE *)
TREE_ELEMENT *	tree_insert (TREE tree, void key, uint key_size, void *custom_arg)
void *	tree_search (TREE tree, void key, void *custom_arg)
int	tree_walk (TREE tree, tree_walk_action action, void argument, TREE_WALK visit)
int	tree_delete (TREE tree, void key, uint key_size, 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 search_flag, void *custom_arg)

Define Documentation

#define ELEMENT_CHILD	(	element,
		offs		)	((TREE_ELEMENT)((char)element + offs))

Definition at line 49 of file my_tree.h.

Referenced by tree_search_edge(), and tree_search_next().

#define ELEMENT_KEY	(	tree,
		element		)

Value:

(tree->offset_to_key ? (void*)((byte*) element+tree->offset_to_key) :\
                        *((void**) (element+1)))

Definition at line 28 of file my_tree.h.

Referenced by delete_tree_element(), tree_delete(), tree_insert(), tree_record_pos(), tree_search(), tree_search_edge(), tree_search_key(), tree_search_next(), tree_walk_left_root_right(), tree_walk_right_root_left(), and walk_and_match().

#define is_tree_inited ( tree ) ((tree)->root != 0)

Definition at line 71 of file my_tree.h.

Referenced by _ftb_init_index_search(), _mi_ck_write(), ft_boolean_close_search(), ft_boolean_read_next(), ft_parse_init(), mi_end_bulk_insert(), and mi_flush_bulk_insert().

#define MAX_TREE_HEIGHT 64

Definition at line 26 of file my_tree.h.

#define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void*))

Definition at line 90 of file my_tree.h.

Referenced by mi_init_bulk_insert().

#define TREE_NO_DUPS 1

Definition at line 34 of file my_tree.h.

Referenced by hp_rb_write_key().

#define tree_set_pointer	(	element,
		ptr		)	((byte ) (element+1))=((byte) (ptr))

Definition at line 32 of file my_tree.h.

Typedef Documentation

typedef uint32 element_count

Definition at line 37 of file my_tree.h.

typedef struct st_tree TREE

typedef struct st_tree_element TREE_ELEMENT

typedef void(*) tree_element_free(void *, TREE_FREE, void *)

Definition at line 41 of file my_tree.h.

typedef int(*) tree_walk_action(void *, element_count, void *)

Definition at line 38 of file my_tree.h.

Enumeration Type Documentation

enum TREE_FREE

Enumerator:

free_init
free_free
free_end

Definition at line 40 of file my_tree.h.

00040 { free_init, free_free, free_end } TREE_FREE;

enum TREE_WALK

Enumerator:

left_root_right
right_root_left

Definition at line 36 of file my_tree.h.

00036 { left_root_right, right_root_left } TREE_WALK;

Function Documentation

void delete_tree ( TREE * )

Definition at line 166 of file tree.c.

References free_tree(), and MYF.

Referenced by field_ulonglong::add(), field_longlong::add(), field_decimal::add(), field_real::add(), field_str::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:

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:

void reset_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:

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(), field_ulonglong::add(), field_longlong::add(), field_decimal::add(), field_real::add(), field_str::add(), Item_func_group_concat::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	search_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:

Generated on Sat Sep 9 01:43:05 2006 for MySQL 5.1 by

1.4.7

The world's most popular open source database

mysql/src/5.1-dbg/include/my_tree.h File Reference

Classes

Defines

Typedefs

Enumerations

Functions

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation