drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
tree.cc
1/* Copyright (C) 2000 MySQL AB
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16/*
17 Code for handling red-black (balanced) binary trees.
18 key in tree is allocated according to following:
19
20 1) If size < 0 then tree will not allocate keys and only a pointer to
21 each key is saved in tree.
22 compare and search functions uses and returns key-pointer
23
24 2) If size == 0 then there are two options:
25 - key_size != 0 to tree_insert: The key will be stored in the tree.
26 - key_size == 0 to tree_insert: A pointer to the key is stored.
27 compare and search functions uses and returns key-pointer.
28
29 3) if key_size is given to init_tree then each node will continue the
30 key and calls to insert_key may increase length of key.
31 if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
32 align) then key will be put on a 8 aligned address. Else
33 the key will be on address (element+1). This is transparent for user
34 compare and search functions uses a pointer to given key-argument.
35
36 - If you use a free function for tree-elements and you are freeing
37 the element itself, you should use key_size = 0 to init_tree and
38 tree_search
39
40 The actual key in TREE_ELEMENT is saved as a pointer or after the
41 TREE_ELEMENT struct.
42 If one uses only pointers in tree one can use tree_set_pointer() to
43 change address of data.
44
45 Implemented by monty.
46*/
47
48/*
49 NOTE:
50 tree->compare function should be ALWAYS called as
51 (*compare)(custom_arg, element_key(element), key)
52 and NOT the other way around, as
53 (*compare)(custom_arg, key, element_key(element))
54*/
55
56#include <config.h>
57
58#include <drizzled/tree.h>
59#include <drizzled/internal/my_sys.h>
60#include <drizzled/internal/m_string.h>
61
62#define BLACK 1
63#define RED 0
64#define DEFAULT_ALLOC_SIZE 8192
65#define DEFAULT_ALIGN_SIZE 8192
66
67
68namespace drizzled
69{
70
74
75void Tree::init_tree(size_t default_alloc_size, uint32_t mem_limit,
76 uint32_t size, qsort_cmp2 compare_callback, bool free_with_tree,
77 tree_element_free free_callback, void *caller_arg)
78{
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;
87 free= free_callback;
88 allocated= 0;
89 elements_in_tree= 0;
90 custom_arg = caller_arg;
91 null_element.colour= BLACK;
92 null_element.left=this->null_element.right= 0;
93 flag= 0;
94 if (!free_callback &&
95 (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
96 {
97 /*
98 We know that the data doesn't have to be aligned (like if the key
99 contains a double), so we can store the data combined with the
100 Tree_Element.
101 */
102 offset_to_key= sizeof(Tree_Element); /* Put key after element */
103 /* Fix allocation size so that we don't lose any memory */
104 default_alloc_size/= (sizeof(Tree_Element)+size);
105 if (!default_alloc_size)
106 default_alloc_size= 1;
107 default_alloc_size*= (sizeof(Tree_Element)+size);
108 }
109 else
110 {
111 offset_to_key= 0; /* use key through pointer */
112 size_of_element+= sizeof(void*);
113 }
114 if (! (with_delete= free_with_tree))
115 {
116 mem_root.init(default_alloc_size);
117 mem_root.min_malloc= (sizeof(Tree_Element)+size_of_element);
118 }
119}
120
121void Tree::delete_tree()
122{
123 free_tree(MYF(0)); /* free() mem_root if applicable */
124}
125
126void Tree::reset_tree()
127{
128 /* do not free mem_root, just mark blocks as free */
129 free_tree(MYF(memory::MARK_BLOCKS_FREE));
130}
131
132Tree_Element* Tree::tree_insert(void* key, uint32_t key_size, void* caller_arg)
133{
134 int cmp;
135 Tree_Element *element,***parent;
136
137 parent= this->parents;
138 *parent = &this->root; element= this->root;
139 for (;;)
140 {
141 if (element == &this->null_element ||
142 (cmp = (*compare)(caller_arg, element_key(element), key)) == 0)
143 break;
144 if (cmp < 0)
145 {
146 *++parent= &element->right; element= element->right;
147 }
148 else
149 {
150 *++parent = &element->left; element= element->left;
151 }
152 }
153 if (element == &this->null_element)
154 {
155 size_t alloc_size= sizeof(Tree_Element)+key_size+this->size_of_element;
156 this->allocated+= alloc_size;
157
158 if (this->memory_limit && this->elements_in_tree
159 && this->allocated > this->memory_limit)
160 {
161 reset_tree();
162 return tree_insert(key, key_size, caller_arg);
163 }
164
165 key_size+= this->size_of_element;
166 if (this->with_delete)
167 element= (Tree_Element *) malloc(alloc_size);
168 else
169 element= (Tree_Element *) this->mem_root.alloc(alloc_size);
170 **parent= element;
171 element->left= element->right= &this->null_element;
172 if (!this->offset_to_key)
173 {
174 if (key_size == sizeof(void*)) /* no length, save pointer */
175 *((void**) (element+1))= key;
176 else
177 {
178 *((void**) (element+1))= (void*) ((void **) (element+1)+1);
179 memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
180 }
181 }
182 else
183 memcpy((unsigned char*) element + this->offset_to_key, key, key_size);
184 element->count= 1; /* May give warning in purify */
185 this->elements_in_tree++;
186 rb_insert(parent,element); /* rebalance tree */
187 }
188 else
189 {
190 if (this->flag & TREE_NO_DUPS)
191 return(NULL);
192 element->count++;
193 /* Avoid a wrap over of the count. */
194 if (! element->count)
195 element->count--;
196 }
197
198 return element;
199}
200
201int Tree::tree_walk(tree_walk_action action, void *argument, TREE_WALK visit)
202{
203 switch (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);
208 }
209
210 return 0; /* Keep gcc happy */
211}
212
216
217void Tree::free_tree(myf free_flags)
218{
219 if (root) /* If initialized */
220 {
221 if (with_delete)
222 delete_tree_element(root);
223 else
224 {
225 if (free)
226 {
227 if (memory_limit)
228 (*free)(NULL, free_init, custom_arg);
229 delete_tree_element(root);
230 if (memory_limit)
231 (*free)(NULL, free_end, custom_arg);
232 }
233 mem_root.free_root(free_flags);
234 }
235 }
236 root= &null_element;
237 elements_in_tree= 0;
238 allocated= 0;
239}
240
241void* Tree::element_key(Tree_Element* element)
242{
243 return offset_to_key ? (void*)((unsigned char*) element + offset_to_key)
244 : *((void**)(element + 1));
245}
246
247void Tree::delete_tree_element(Tree_Element *element)
248{
249 if (element != &null_element)
250 {
251 delete_tree_element(element->left);
252 if (free)
253 (*free)(element_key(element), free_free, custom_arg);
254 delete_tree_element(element->right);
255 if (with_delete)
256 delete element;
257 }
258}
259
260int Tree::tree_walk_left_root_right(Tree_Element *element, tree_walk_action action, void *argument)
261{
262 int error;
263 if (element->left) /* Not null_element */
264 {
265 if ((error=tree_walk_left_root_right(element->left,action,
266 argument)) == 0 &&
267 (error=(*action)(element_key(element), element->count, argument)) == 0)
268 error=tree_walk_left_root_right(element->right,action,argument);
269 return error;
270 }
271
272 return 0;
273}
274
275int Tree::tree_walk_right_root_left(Tree_Element *element, tree_walk_action action, void *argument)
276{
277 int error;
278 if (element->right) /* Not null_element */
279 {
280 if ((error=tree_walk_right_root_left(element->right,action,
281 argument)) == 0 &&
282 (error=(*action)(element_key(element),
283 element->count,
284 argument)) == 0)
285 error=tree_walk_right_root_left(element->left,action,argument);
286 return error;
287 }
288
289 return 0;
290}
291
292void Tree::left_rotate(Tree_Element **parent, Tree_Element *element)
293{
294 Tree_Element *y;
295
296 y= element->right;
297 element->right= y->left;
298 parent[0]= y;
299 y->left= element;
300}
301
302void Tree::right_rotate(Tree_Element **parent, Tree_Element *element)
303{
304 Tree_Element *x;
305
306 x= element->left;
307 element->left= x->right;
308 parent[0]= x;
309 x->right= element;
310}
311
312void Tree::rb_insert(Tree_Element ***parent, Tree_Element *element)
313{
314 Tree_Element *y,*par,*par2;
315
316 element->colour=RED;
317 while (element != root && (par=parent[-1][0])->colour == RED)
318 {
319 if (par == (par2=parent[-2][0])->left)
320 {
321 y= par2->right;
322 if (y->colour == RED)
323 {
324 par->colour= BLACK;
325 y->colour= BLACK;
326 element= par2;
327 parent-= 2;
328 element->colour= RED; /* And the loop continues */
329 }
330 else
331 {
332 if (element == par->right)
333 {
334 left_rotate(parent[-1],par);
335 par= element; /* element is now parent to old element */
336 }
337 par->colour= BLACK;
338 par2->colour= RED;
339 right_rotate(parent[-2],par2);
340 break;
341 }
342 }
343 else
344 {
345 y= par2->left;
346 if (y->colour == RED)
347 {
348 par->colour= BLACK;
349 y->colour= BLACK;
350 element= par2;
351 parent-= 2;
352 element->colour= RED; /* And the loop continues */
353 }
354 else
355 {
356 if (element == par->left)
357 {
358 right_rotate(parent[-1],par);
359 par= element;
360 }
361 par->colour= BLACK;
362 par2->colour= RED;
363 left_rotate(parent[-2],par2);
364 break;
365 }
366 }
367 }
368 root->colour=BLACK;
369}
370
371} /* namespace drizzled */
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)
Definition tree.cc:75
void free_tree(myf free_flags)
Definition tree.cc:217
TODO: Rename this file - func.h is stupid.