MySQL 8.3.0
Source Code Documentation
my_tree.h
Go to the documentation of this file.
1/* Copyright (c) 2000, 2023, Oracle and/or its affiliates.
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
52typedef int (*tree_walk_action)(void *, element_count, void *);
53
55typedef void (*tree_element_free)(void *, TREE_FREE, const void *);
56
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
67struct TREE {
71 ulong memory_limit{0}, allocated{0};
73 const void *custom_arg{nullptr};
75 bool with_delete{false};
77 uint flag{0};
78};
79
80/* Functions on whole tree */
81void 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);
84void delete_tree(TREE *);
85void reset_tree(TREE *);
86/* similar to delete tree, except we do not my_free() blocks in mem_root
87 */
88inline bool is_tree_inited(TREE *tree) { return tree->root != nullptr; }
89
90/* Functions on leafs */
91TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
92 const void *custom_arg);
93void *tree_search(TREE *tree, void *key, const void *custom_arg);
94int tree_walk(TREE *tree, tree_walk_action action, void *argument,
95 TREE_WALK visit);
96int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg);
97void *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);
100void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
101 TREE_ELEMENT ***last_pos, int child_offs);
102void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
103 int r_offs);
104ha_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
int(* qsort2_cmp)(const void *, const void *, const void *)
Definition: my_sys.h:472
static int flag
Definition: hp_test1.cc:39
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
This file includes constants used by all storage engines.
ha_rkey_function
Definition: my_base.h:77
my_off_t ha_rows
Definition: my_base.h:1140
Some integer typedefs for easier portability.
uint32_t uint32
Definition: my_inttypes.h:66
Common header for many mysys elements.
TREE_WALK
Definition: my_tree.h:50
@ right_root_left
Definition: my_tree.h:50
@ left_root_right
Definition: my_tree.h:50
void * tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, int r_offs)
Definition: tree.cc:420
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_edge(TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
Definition: tree.cc:406
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:332
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
Definition: tree.cc:488
TREE_ELEMENT * tree_insert(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:200
ha_rows tree_record_pos(TREE *tree, const void *key, enum ha_rkey_function search_flag, const void *custom_arg)
Definition: tree.cc:446
bool is_tree_inited(TREE *tree)
Definition: my_tree.h:88
void reset_tree(TREE *)
Definition: tree.cc:173
int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:264
void delete_tree(TREE *)
Definition: tree.cc:169
int(* tree_walk_action)(void *, element_count, void *)
Definition: my_tree.h:52
#define MAX_TREE_HEIGHT
Definition: my_tree.h:39
void * tree_search(TREE *tree, void *key, const void *custom_arg)
Definition: tree.cc:316
uint32 element_count
Definition: my_tree.h:51
void(* tree_element_free)(void *, TREE_FREE, const void *)
Definition: my_tree.h:55
TREE_FREE
Definition: my_tree.h:54
@ free_init
Definition: my_tree.h:54
@ free_free
Definition: my_tree.h:54
@ free_end
Definition: my_tree.h:54
required string key
Definition: replication_asynchronous_connection_failover.proto:59
repeated Action action
Definition: replication_group_member_actions.proto:42
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:106
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Definition: my_tree.h:57
uint32 colour
Definition: my_tree.h:61
TREE_ELEMENT * right
Definition: my_tree.h:60
TREE_ELEMENT()
Definition: my_tree.h:58
uint32 count
Definition: my_tree.h:61
TREE_ELEMENT * left
Definition: my_tree.h:60
Definition: my_tree.h:67
TREE_ELEMENT * root
Definition: my_tree.h:68
TREE_ELEMENT null_element
Definition: my_tree.h:68
TREE_ELEMENT ** parents[MAX_TREE_HEIGHT]
Definition: my_tree.h:69
tree_element_free free
Definition: my_tree.h:76
uint flag
Definition: my_tree.h:77
qsort2_cmp compare
Definition: my_tree.h:72
uint elements_in_tree
Definition: my_tree.h:70
ulong memory_limit
Definition: my_tree.h:71
bool with_delete
Definition: my_tree.h:75
uint offset_to_key
Definition: my_tree.h:70
uint size_of_element
Definition: my_tree.h:70
ulong allocated
Definition: my_tree.h:71
const void * custom_arg
Definition: my_tree.h:73
MEM_ROOT mem_root
Definition: my_tree.h:74