MySQL  8.0.19
Source Code Documentation
my_tree.h
Go to the documentation of this file.
1 /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
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, version 2.0,
5  as published by the Free Software Foundation.
6 
7  This program is also distributed with certain software (including
8  but not limited to OpenSSL) that is licensed under separate terms,
9  as designated in a particular file or component or in included license
10  documentation. The authors of MySQL hereby grant you an additional
11  permission to link the program and your derivative works with the
12  separately licensed software that they have included with MySQL.
13 
14  This program is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU General Public License, version 2.0, for more details.
18 
19  You should have received a copy of the GNU General Public License
20  along with this program; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22 
23 #ifndef _tree_h
24 #define _tree_h
25 
26 /**
27  @file include/my_tree.h
28 */
29 
30 #include <stddef.h>
31 #include <sys/types.h>
32 
33 #include "my_alloc.h" /* MEM_ROOT */
34 #include "my_base.h" /* get 'enum ha_rkey_function' */
35 #include "my_inttypes.h"
36 #include "my_sys.h" /* qsort2_cmp */
37 
38 /* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */
39 #define MAX_TREE_HEIGHT 64
40 
41 #define ELEMENT_KEY(tree, element) \
42  (tree->offset_to_key ? (void *)((uchar *)element + tree->offset_to_key) \
43  : *((void **)(element + 1)))
44 
45 #define tree_set_pointer(element, ptr) \
46  *((uchar **)(element + 1)) = ((uchar *)(ptr))
47 
48 #define TREE_NO_DUPS 1
49 
52 typedef int (*tree_walk_action)(void *, element_count, void *);
53 
55 typedef void (*tree_element_free)(void *, TREE_FREE, const void *);
56 
57 struct TREE_ELEMENT {
58  TREE_ELEMENT() : count(0), colour(0) {}
59 
60  TREE_ELEMENT *left{nullptr}, *right{nullptr};
61  uint32 count : 31, colour : 1; /* black is marked as 1 */
62 };
63 
64 #define ELEMENT_CHILD(element, offs) \
65  (*(TREE_ELEMENT **)((char *)element + offs))
66 
67 struct TREE {
72  qsort2_cmp compare{nullptr};
73  const void *custom_arg{nullptr};
75  bool with_delete{false};
77  uint flag{0};
78 };
79 
80 /* Functions on whole tree */
81 void init_tree(TREE *tree, ulong memory_limit, int element_size,
82  qsort2_cmp compare, bool with_delete,
83  tree_element_free free_element, const void *custom_arg);
84 void delete_tree(TREE *);
85 void reset_tree(TREE *);
86 /* similar to delete tree, except we do not my_free() blocks in mem_root
87  */
88 #define is_tree_inited(tree) ((tree)->root != 0)
89 
90 /* Functions on leafs */
91 TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
92  const void *custom_arg);
93 void *tree_search(TREE *tree, void *key, const void *custom_arg);
94 int tree_walk(TREE *tree, tree_walk_action action, void *argument,
95  TREE_WALK visit);
96 int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg);
97 void *tree_search_key(TREE *tree, const void *key, TREE_ELEMENT **parents,
98  TREE_ELEMENT ***last_pos, enum ha_rkey_function flag,
99  const void *custom_arg);
100 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
101  TREE_ELEMENT ***last_pos, int child_offs);
102 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
103  int r_offs);
104 ha_rows tree_record_pos(TREE *tree, const void *key,
105  enum ha_rkey_function search_flag,
106  const void *custom_arg);
107 
108 #define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void *))
109 
110 #endif
right_root_left
@ right_root_left
Definition: my_tree.h:50
TREE::memory_limit
ulong memory_limit
Definition: my_tree.h:71
tree_insert
TREE_ELEMENT * tree_insert(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:194
tree_search_next
void * tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, int r_offs)
Definition: tree.cc:412
my_base.h
TREE::compare
qsort2_cmp compare
Definition: my_tree.h:72
tree_delete
int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:257
TREE::elements_in_tree
uint elements_in_tree
Definition: my_tree.h:70
tree_walk_action
int(* tree_walk_action)(void *, element_count, void *)
Definition: my_tree.h:52
qsort2_cmp
int(* qsort2_cmp)(const void *, const void *, const void *)
Definition: my_sys.h:460
element_count
uint32 element_count
Definition: my_tree.h:51
TREE::offset_to_key
uint offset_to_key
Definition: my_tree.h:70
free_end
@ free_end
Definition: my_tree.h:54
init_tree
void init_tree(TREE *tree, ulong memory_limit, int element_size, qsort2_cmp compare, bool with_delete, tree_element_free free_element, const void *custom_arg)
Definition: tree.cc:103
TREE_ELEMENT::colour
uint32 colour
Definition: my_tree.h:61
TREE_ELEMENT::left
TREE_ELEMENT * left
Definition: my_tree.h:60
tree_search
void * tree_search(TREE *tree, void *key, const void *custom_arg)
Definition: tree.cc:309
MAX_TREE_HEIGHT
#define MAX_TREE_HEIGHT
Definition: my_tree.h:39
key
static const char * key
Definition: suite_stubs.c:14
TREE::allocated
ulong allocated
Definition: my_tree.h:71
TREE::mem_root
MEM_ROOT mem_root
Definition: my_tree.h:74
my_alloc.h
TREE::parents
TREE_ELEMENT ** parents[MAX_TREE_HEIGHT]
Definition: my_tree.h:69
TREE_ELEMENT::count
uint32 count
Definition: my_tree.h:61
TREE::size_of_element
uint size_of_element
Definition: my_tree.h:70
TREE::flag
uint flag
Definition: my_tree.h:77
my_inttypes.h
MEM_ROOT
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:77
tree_search_key
void * tree_search_key(TREE *tree, const void *key, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, enum ha_rkey_function flag, const void *custom_arg)
Definition: tree.cc:325
free_init
@ free_init
Definition: my_tree.h:54
TREE_WALK
TREE_WALK
Definition: my_tree.h:50
TREE_ELEMENT::TREE_ELEMENT
TREE_ELEMENT()
Definition: my_tree.h:58
uint
unsigned int uint
Definition: uca-dump.cc:29
TREE
Definition: my_tree.h:67
free_free
@ free_free
Definition: my_tree.h:54
TREE::custom_arg
const void * custom_arg
Definition: my_tree.h:73
reset_tree
void reset_tree(TREE *)
Definition: tree.cc:167
TREE_ELEMENT
Definition: my_tree.h:57
uint32
uint32_t uint32
Definition: my_inttypes.h:66
TREE::root
TREE_ELEMENT * root
Definition: my_tree.h:68
tree_walk
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
Definition: tree.cc:480
tree_record_pos
ha_rows tree_record_pos(TREE *tree, const void *key, enum ha_rkey_function search_flag, const void *custom_arg)
Definition: tree.cc:438
tree_search_edge
void * tree_search_edge(TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
Definition: tree.cc:398
TREE::free
tree_element_free free
Definition: my_tree.h:76
TREE::null_element
TREE_ELEMENT null_element
Definition: my_tree.h:68
ha_rkey_function
ha_rkey_function
Definition: my_base.h:77
TREE::with_delete
bool with_delete
Definition: my_tree.h:75
TREE_FREE
TREE_FREE
Definition: my_tree.h:54
compare
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:103
ulong
unsigned long ulong
Definition: my_inttypes.h:48
ha_rows
my_off_t ha_rows
Definition: my_base.h:1132
left_root_right
@ left_root_right
Definition: my_tree.h:50
TREE_ELEMENT::right
TREE_ELEMENT * right
Definition: my_tree.h:60
my_sys.h
delete_tree
void delete_tree(TREE *)
Definition: tree.cc:163
flag
static int flag
Definition: hp_test1.cc:39
tree_element_free
void(* tree_element_free)(void *, TREE_FREE, const void *)
Definition: my_tree.h:55