58 #include <drizzled/tree.h>
59 #include <drizzled/internal/my_sys.h>
60 #include <drizzled/internal/m_string.h>
64 #define DEFAULT_ALLOC_SIZE 8192
65 #define DEFAULT_ALIGN_SIZE 8192
76 uint32_t size, qsort_cmp2 compare_callback,
bool free_with_tree,
77 tree_element_free free_callback,
void *caller_arg)
79 if (default_alloc_size < DEFAULT_ALLOC_SIZE)
80 default_alloc_size= DEFAULT_ALLOC_SIZE;
81 default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
82 memset(&this->null_element, 0,
sizeof(this->null_element));
83 root= &this->null_element;
84 compare= compare_callback;
85 size_of_element= size > 0 ? (uint32_t) size : 0;
86 memory_limit= mem_limit;
90 custom_arg = caller_arg;
91 null_element.colour= BLACK;
92 null_element.left=this->null_element.right= 0;
95 (size <=
sizeof(
void*) || ((uint32_t) size & (
sizeof(
void*)-1))))
105 if (!default_alloc_size)
106 default_alloc_size= 1;
112 size_of_element+=
sizeof(
void*);
114 if (! (with_delete= free_with_tree))
116 mem_root.
init(default_alloc_size);
121 void Tree::delete_tree()
126 void Tree::reset_tree()
129 free_tree(MYF(memory::MARK_BLOCKS_FREE));
132 Tree_Element* Tree::tree_insert(
void* key, uint32_t key_size,
void* caller_arg)
135 Tree_Element *element,***parent;
137 parent= this->parents;
138 *parent = &this->root; element= this->root;
141 if (element == &this->null_element ||
142 (cmp = (*compare)(caller_arg, element_key(element), key)) == 0)
146 *++parent= &element->right; element= element->right;
150 *++parent = &element->left; element= element->left;
153 if (element == &this->null_element)
155 size_t alloc_size=
sizeof(Tree_Element)+key_size+this->size_of_element;
156 this->allocated+= alloc_size;
158 if (this->memory_limit && this->elements_in_tree
159 && this->allocated > this->memory_limit)
162 return tree_insert(key, key_size, caller_arg);
165 key_size+= this->size_of_element;
166 if (this->with_delete)
167 element= (Tree_Element *) malloc(alloc_size);
169 element= (Tree_Element *) this->mem_root.
alloc(alloc_size);
171 element->left= element->right= &this->null_element;
172 if (!this->offset_to_key)
174 if (key_size ==
sizeof(
void*))
175 *((
void**) (element+1))= key;
178 *((
void**) (element+1))= (
void*) ((
void **) (element+1)+1);
179 memcpy(*((
void **) (element+1)),key, key_size -
sizeof(
void*));
183 memcpy((
unsigned char*) element + this->offset_to_key, key, key_size);
185 this->elements_in_tree++;
186 rb_insert(parent,element);
190 if (this->flag & TREE_NO_DUPS)
194 if (! element->count)
201 int Tree::tree_walk(tree_walk_action action,
void *argument, TREE_WALK visit)
204 case left_root_right:
205 return tree_walk_left_root_right(root,action,argument);
206 case right_root_left:
207 return tree_walk_right_root_left(root,action,argument);
222 delete_tree_element(root);
228 (*free)(NULL, free_init, custom_arg);
229 delete_tree_element(root);
231 (*free)(NULL, free_end, custom_arg);
243 return offset_to_key ? (
void*)((
unsigned char*) element + offset_to_key)
244 : *((
void**)(element + 1));
249 if (element != &null_element)
251 delete_tree_element(element->left);
253 (*free)(element_key(element), free_free, custom_arg);
254 delete_tree_element(element->right);
260 int Tree::tree_walk_left_root_right(Tree_Element *element, tree_walk_action action,
void *argument)
265 if ((error=tree_walk_left_root_right(element->left,action,
267 (error=(*action)(element_key(element), element->count, argument)) == 0)
268 error=tree_walk_left_root_right(element->right,action,argument);
275 int Tree::tree_walk_right_root_left(Tree_Element *element, tree_walk_action action,
void *argument)
280 if ((error=tree_walk_right_root_left(element->right,action,
282 (error=(*action)(element_key(element),
285 error=tree_walk_right_root_left(element->left,action,argument);
292 void Tree::left_rotate(Tree_Element **parent, Tree_Element *element)
297 element->right= y->left;
302 void Tree::right_rotate(Tree_Element **parent, Tree_Element *element)
307 element->left= x->right;
312 void Tree::rb_insert(Tree_Element ***parent, Tree_Element *element)
314 Tree_Element *y,*par,*par2;
317 while (element != root && (par=parent[-1][0])->colour == RED)
319 if (par == (par2=parent[-2][0])->left)
322 if (y->colour == RED)
328 element->colour= RED;
332 if (element == par->right)
334 left_rotate(parent[-1],par);
339 right_rotate(parent[-2],par2);
346 if (y->colour == RED)
352 element->colour= RED;
356 if (element == par->left)
358 right_rotate(parent[-1],par);
363 left_rotate(parent[-2],par2);
unsigned char * alloc(size_t Size)
Allocate a chunk of memory from the Root structure provided, obtaining more memory from the heap if n...
void free_tree(myf free_flags)
void init_tree(size_t default_alloc_size, uint32_t memory_limit, uint32_t size, qsort_cmp2 compare, bool with_delete, tree_element_free free_element, void *custom_arg)
void init(size_t block_size=ROOT_MIN_BLOCK_SIZE)
Initialize memory root.
void free_root(myf MyFLAGS)
Deallocate everything used by alloc_root or just move used blocks to free list if called with MY_USED...