MySQL  8.0.16
Source Code Documentation
my_tree.h
Go to the documentation of this file.
1 /* Copyright (c) 2000, 2017, 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 
51 typedef uint32 element_count;
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, size_t default_alloc_size, ulong memory_limit,
82  int size, 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
qsort2_cmp compare
Definition: my_tree.h:72
TREE_ELEMENT()
Definition: my_tree.h:58
uint offset_to_key
Definition: my_tree.h:70
uint32 colour
Definition: my_tree.h:61
Some integer typedefs for easier portability.
int(* qsort2_cmp)(const void *, const void *, const void *)
Definition: my_sys.h:473
ulong memory_limit
Definition: my_tree.h:71
TREE_ELEMENT ** parents[MAX_TREE_HEIGHT]
Definition: my_tree.h:69
void * tree_search_edge(TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
Definition: tree.cc:403
uint size_of_element
Definition: my_tree.h:70
TREE_ELEMENT * tree_insert(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:199
TREE_FREE
Definition: my_tree.h:54
MEM_ROOT mem_root
Definition: my_tree.h:74
ha_rkey_function
Definition: my_base.h:77
Definition: my_tree.h:54
Definition: my_tree.h:54
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
Definition: tree.cc:485
Definition: my_tree.h:50
This file includes constants used by all storage engines.
uint32 element_count
Definition: my_tree.h:51
void(* tree_element_free)(void *, TREE_FREE, const void *)
Definition: my_tree.h:55
ulong allocated
Definition: my_tree.h:71
TREE_ELEMENT * root
Definition: my_tree.h:68
Definition: my_tree.h:67
TREE_WALK
Definition: my_tree.h:50
uint flag
Definition: my_tree.h:77
unsigned int uint
Definition: uca-dump.cc:29
void delete_tree(TREE *)
Definition: tree.cc:172
Common header for many mysys elements.
static const char * key
Definition: suite_stubs.c:14
Definition: my_tree.h:50
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:330
Definition: my_tree.h:54
void * tree_search(TREE *tree, void *key, const void *custom_arg)
Definition: tree.cc:314
int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:262
bool with_delete
Definition: my_tree.h:75
static int flag
Definition: hp_test1.cc:39
TREE_ELEMENT null_element
Definition: my_tree.h:68
Definition: my_tree.h:57
const void * custom_arg
Definition: my_tree.h:73
uint32 count
Definition: my_tree.h:61
int(* tree_walk_action)(void *, element_count, void *)
Definition: my_tree.h:52
void * tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, int r_offs)
Definition: tree.cc:417
ha_rows tree_record_pos(TREE *tree, const void *key, enum ha_rkey_function search_flag, const void *custom_arg)
Definition: tree.cc:443
TREE_ELEMENT * right
Definition: my_tree.h:60
#define MAX_TREE_HEIGHT
Definition: my_tree.h:39
void reset_tree(TREE *)
Definition: tree.cc:176
TREE_ELEMENT * left
Definition: my_tree.h:60
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:77
tree_element_free free
Definition: my_tree.h:76
uint elements_in_tree
Definition: my_tree.h:70
void init_tree(TREE *tree, size_t default_alloc_size, ulong memory_limit, int size, qsort2_cmp compare, bool with_delete, tree_element_free free_element, const void *custom_arg)
Definition: tree.cc:104
unsigned long ulong
Definition: my_inttypes.h:46
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:102
my_off_t ha_rows
Definition: my_base.h:1066
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...