MySQL  8.0.22
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 {
68  TREE_ELEMENT *root{nullptr}, null_element;
69  TREE_ELEMENT **parents[MAX_TREE_HEIGHT]{nullptr};
70  uint offset_to_key{0}, elements_in_tree{0}, size_of_element{0};
71  ulong memory_limit{0}, allocated{0};
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
TREE_ELEMENT()
Definition: my_tree.h:58
#define free(A)
Definition: fts0ast.h:42
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:466
void * tree_search_edge(TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
Definition: tree.cc:400
TREE_ELEMENT * tree_insert(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:195
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:482
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
Definition: my_tree.h:67
TREE_WALK
Definition: my_tree.h:50
unsigned int uint
Definition: uca-dump.cc:29
void delete_tree(TREE *)
Definition: tree.cc:164
uint32_t uint32
Definition: my_inttypes.h:66
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:326
Definition: my_tree.h:54
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
void * tree_search(TREE *tree, void *key, const void *custom_arg)
Definition: tree.cc:310
int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:258
static int flag
Definition: hp_test1.cc:39
Definition: my_tree.h:57
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:414
ha_rows tree_record_pos(TREE *tree, const void *key, enum ha_rkey_function search_flag, const void *custom_arg)
Definition: tree.cc:440
TREE_ELEMENT * right
Definition: my_tree.h:60
#define MAX_TREE_HEIGHT
Definition: my_tree.h:39
void reset_tree(TREE *)
Definition: tree.cc:168
static SEL_ARG * null_element
Shared sentinel node for all trees.
Definition: opt_range.cc:1495
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
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:104
my_off_t ha_rows
Definition: my_base.h:1136
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...