MySQL 9.0.0
Source Code Documentation
my_tree.h
Go to the documentation of this file.
1/* Copyright (c) 2000, 2024, 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 designed to work 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 either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef _tree_h
25#define _tree_h
26
27/**
28 @file include/my_tree.h
29*/
30
31#include <stddef.h>
32#include <sys/types.h>
33
34#include "my_alloc.h" /* MEM_ROOT */
35#include "my_base.h" /* get 'enum ha_rkey_function' */
36#include "my_inttypes.h"
37#include "my_sys.h" /* qsort2_cmp */
38
39/* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */
40#define MAX_TREE_HEIGHT 64
41
42#define ELEMENT_KEY(tree, element) \
43 (tree->offset_to_key ? (void *)((uchar *)element + tree->offset_to_key) \
44 : *((void **)(element + 1)))
45
46#define tree_set_pointer(element, ptr) \
47 *((uchar **)(element + 1)) = ((uchar *)(ptr))
48
49#define TREE_NO_DUPS 1
50
53typedef int (*tree_walk_action)(void *, element_count, void *);
54
56typedef void (*tree_element_free)(void *, TREE_FREE, const void *);
57
60
61 TREE_ELEMENT *left{nullptr}, *right{nullptr};
62 uint32 count : 31, colour : 1; /* black is marked as 1 */
63};
64
65#define ELEMENT_CHILD(element, offs) \
66 (*(TREE_ELEMENT **)((char *)element + offs))
67
68struct TREE {
72 ulong memory_limit{0}, allocated{0};
74 const void *custom_arg{nullptr};
76 bool with_delete{false};
78 uint flag{0};
79};
80
81/* Functions on whole tree */
82void init_tree(TREE *tree, ulong memory_limit, int element_size,
83 qsort2_cmp compare, bool with_delete,
84 tree_element_free free_element, const void *custom_arg);
85void delete_tree(TREE *);
86void reset_tree(TREE *);
87/* similar to delete tree, except we do not my_free() blocks in mem_root
88 */
89inline bool is_tree_inited(TREE *tree) { return tree->root != nullptr; }
90
91/* Functions on leafs */
92TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
93 const void *custom_arg);
94void *tree_search(TREE *tree, void *key, const void *custom_arg);
95int tree_walk(TREE *tree, tree_walk_action action, void *argument,
96 TREE_WALK visit);
97int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg);
98void *tree_search_key(TREE *tree, const void *key, TREE_ELEMENT **parents,
99 TREE_ELEMENT ***last_pos, enum ha_rkey_function flag,
100 const void *custom_arg);
101void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
102 TREE_ELEMENT ***last_pos, int child_offs);
103void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
104 int r_offs);
105ha_rows tree_record_pos(TREE *tree, const void *key,
106 enum ha_rkey_function search_flag,
107 const void *custom_arg);
108
109#define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void *))
110
111#endif
int(* qsort2_cmp)(const void *, const void *, const void *)
Definition: my_sys.h:473
static int flag
Definition: hp_test1.cc:40
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:78
my_off_t ha_rows
Definition: my_base.h:1141
Some integer typedefs for easier portability.
uint32_t uint32
Definition: my_inttypes.h:67
Common header for many mysys elements.
TREE_WALK
Definition: my_tree.h:51
@ right_root_left
Definition: my_tree.h:51
@ left_root_right
Definition: my_tree.h:51
void * tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, int r_offs)
Definition: tree.cc:421
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:104
void * tree_search_edge(TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
Definition: tree.cc:407
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:333
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
Definition: tree.cc:489
TREE_ELEMENT * tree_insert(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:201
ha_rows tree_record_pos(TREE *tree, const void *key, enum ha_rkey_function search_flag, const void *custom_arg)
Definition: tree.cc:447
bool is_tree_inited(TREE *tree)
Definition: my_tree.h:89
void reset_tree(TREE *)
Definition: tree.cc:174
int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg)
Definition: tree.cc:265
void delete_tree(TREE *)
Definition: tree.cc:170
int(* tree_walk_action)(void *, element_count, void *)
Definition: my_tree.h:53
#define MAX_TREE_HEIGHT
Definition: my_tree.h:40
void * tree_search(TREE *tree, void *key, const void *custom_arg)
Definition: tree.cc:317
uint32 element_count
Definition: my_tree.h:52
void(* tree_element_free)(void *, TREE_FREE, const void *)
Definition: my_tree.h:56
TREE_FREE
Definition: my_tree.h:55
@ free_init
Definition: my_tree.h:55
@ free_free
Definition: my_tree.h:55
@ free_end
Definition: my_tree.h:55
required string key
Definition: replication_asynchronous_connection_failover.proto:60
repeated Action action
Definition: replication_group_member_actions.proto:43
static int compare(size_t a, size_t b)
Function to compare two size_t integers for their relative order.
Definition: rpl_utility.cc:107
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
Definition: my_tree.h:58
uint32 colour
Definition: my_tree.h:62
TREE_ELEMENT * right
Definition: my_tree.h:61
TREE_ELEMENT()
Definition: my_tree.h:59
uint32 count
Definition: my_tree.h:62
TREE_ELEMENT * left
Definition: my_tree.h:61
Definition: my_tree.h:68
TREE_ELEMENT * root
Definition: my_tree.h:69
TREE_ELEMENT null_element
Definition: my_tree.h:69
TREE_ELEMENT ** parents[MAX_TREE_HEIGHT]
Definition: my_tree.h:70
tree_element_free free
Definition: my_tree.h:77
uint flag
Definition: my_tree.h:78
qsort2_cmp compare
Definition: my_tree.h:73
uint elements_in_tree
Definition: my_tree.h:71
ulong memory_limit
Definition: my_tree.h:72
bool with_delete
Definition: my_tree.h:76
uint offset_to_key
Definition: my_tree.h:71
uint size_of_element
Definition: my_tree.h:71
ulong allocated
Definition: my_tree.h:72
const void * custom_arg
Definition: my_tree.h:74
MEM_ROOT mem_root
Definition: my_tree.h:75