drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
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'
22#include <drizzled/qsort_cmp.h>
23
24namespace drizzled
25{
26
27// Worst case tree is half full. This gives us 2^(MAX_TREE_HEIGHT/2) leaves
28static const int MAX_TREE_HEIGHT= 64;
29
30static const int TREE_NO_DUPS= 1;
31
32typedef enum { left_root_right, right_root_left } TREE_WALK;
33typedef int (*tree_walk_action)(void *,uint32_t,void *);
34
35typedef enum { free_init, free_free, free_end } TREE_FREE;
36typedef void (*tree_element_free)(void*, TREE_FREE, void *);
37
38
40{
41public:
42 Tree_Element *left,*right;
43 uint32_t count:31,
44 colour:1; /* black is marked as 1 */
45};
46
47static const int TREE_ELEMENT_EXTRA_SIZE= (sizeof(Tree_Element) + sizeof(void*));
48
54class Tree
55{
56private:
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
69public:
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
97private:
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
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.
Memory root declarations.