Drizzled Public API Documentation

tree.h
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 #pragma once
17 
18 #include <unistd.h>
19 
20 #include <drizzled/base.h> // for 'enum ha_rkey_function'
21 #include <drizzled/memory/root.h>
22 #include <drizzled/qsort_cmp.h>
23 
24 namespace drizzled
25 {
26 
27 // Worst case tree is half full. This gives us 2^(MAX_TREE_HEIGHT/2) leaves
28 static const int MAX_TREE_HEIGHT= 64;
29 
30 static const int TREE_NO_DUPS= 1;
31 
32 typedef enum { left_root_right, right_root_left } TREE_WALK;
33 typedef int (*tree_walk_action)(void *,uint32_t,void *);
34 
35 typedef enum { free_init, free_free, free_end } TREE_FREE;
36 typedef void (*tree_element_free)(void*, TREE_FREE, void *);
37 
38 
40 {
41 public:
42  Tree_Element *left,*right;
43  uint32_t count:31,
44  colour:1; /* black is marked as 1 */
45 };
46 
47 static const int TREE_ELEMENT_EXTRA_SIZE= (sizeof(Tree_Element) + sizeof(void*));
48 
54 class Tree
55 {
56 private:
57  Tree_Element *root, null_element;
58  void *custom_arg;
59  Tree_Element **parents[MAX_TREE_HEIGHT];
60  uint32_t offset_to_key, elements_in_tree, size_of_element;
61  size_t memory_limit;
62  size_t allocated;
63  qsort_cmp2 compare;
64  memory::Root mem_root;
65  bool with_delete;
66  tree_element_free free;
67  uint32_t flag;
68 
69 public:
70  void* getCustomArg() {
71  return custom_arg;
72  }
73  Tree_Element* getRoot() {
74  return root;
75  }
76  void setRoot(Tree_Element* root_arg) {
77  root = root_arg;
78  }
79  uint32_t getElementsInTree() {
80  return elements_in_tree;
81  }
82  // tree methods
83  void init_tree(size_t default_alloc_size, uint32_t memory_limit,
84  uint32_t size, qsort_cmp2 compare, bool with_delete,
85  tree_element_free free_element, void *custom_arg);
86  bool is_inited()
87  {
88  return this->root != 0;
89  }
90  void delete_tree();
91  void reset_tree();
92 
93  // element methods
94  Tree_Element *tree_insert(void *key, uint32_t key_size, void *custom_arg);
95  int tree_walk(tree_walk_action action, void *argument, TREE_WALK visit);
96 
97 private:
98  void free_tree(myf free_flags);
99 
100  void* element_key(Tree_Element* element);
101  void delete_tree_element(Tree_Element* element);
102  int tree_walk_left_root_right(Tree_Element* element, tree_walk_action action, void* argument);
103  int tree_walk_right_root_left(Tree_Element* element, tree_walk_action action, void* argument);
104 
105  void left_rotate(Tree_Element **parent,Tree_Element *element);
106  void right_rotate(Tree_Element **parent, Tree_Element *element);
107  void rb_insert(Tree_Element ***parent, Tree_Element *element);
108 };
109 
110 } /* namespace drizzled */
111 
Memory root declarations.
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