Drizzled Public API Documentation

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 
68 namespace drizzled
69 {
70 
75 void 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 
121 void Tree::delete_tree()
122 {
123  free_tree(MYF(0)); /* free() mem_root if applicable */
124 }
125 
126 void 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 
132 Tree_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 
201 int 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 
217 void 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 
241 void* 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 
247 void 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 
260 int 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 
275 int 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 
292 void 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 
302 void 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 
312 void 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 */
unsigned char * alloc(size_t Size)
Allocate a chunk of memory from the Root structure provided, obtaining more memory from the heap if n...
Definition: root.cc:140
TODO: Rename this file - func.h is stupid.
void free_tree(myf free_flags)
Definition: tree.cc:217
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 init(size_t block_size=ROOT_MIN_BLOCK_SIZE)
Initialize memory root.
Definition: root.cc:57
size_t min_malloc
Definition: root.h:97
void free_root(myf MyFLAGS)
Deallocate everything used by alloc_root or just move used blocks to free list if called with MY_USED...
Definition: root.cc:288