MySQL 8.4.3
Source Code Documentation
heap.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2000, 2024, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is designed to work with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have either included with
14 the program or referenced in the documentation.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24*/
25
26/* This file should be included when using heap_database_functions */
27/* Author: Michael Widenius */
28
29/**
30 @file include/heap.h
31*/
32
33#ifndef _heap_h
34#define _heap_h
35
36#ifndef _my_base_h
37#include "my_base.h"
38#endif
39
40#include <sys/types.h>
41#include <time.h>
42
43#include "my_compare.h"
44#include "my_inttypes.h"
45#include "my_list.h"
46#include "my_tree.h"
47#include "thr_lock.h"
48
49/* defines used by heap-funktions */
50
51#define HP_MAX_LEVELS 4 /* 128^5 records is enough */
52#define HP_PTRS_IN_NOD 128
53
54/* struct used with heap_funktions */
55
56struct HEAPINFO /* Struct from heap_info */
57{
58 ulong records; /* Records in database */
59 ulong deleted; /* Deleted records in database */
63 uint reclength; /* Length of one record */
64 int errkey;
67};
68
69/* Structs used by heap-database-handler */
70
71struct HP_PTRS {
72 uchar *blocks[HP_PTRS_IN_NOD]; /* pointers to HP_PTRS or records */
73};
74
76 /* Number of unused slots in *last_blocks HP_PTRS block (0 for 0th level) */
78
79 /*
80 Maximum number of records that can be 'contained' inside of each element
81 of last_blocks array. For level 0 - 1, for level 1 - HP_PTRS_IN_NOD, for
82 level 2 - HP_PTRS_IN_NOD^2 and so forth.
83 */
85
86 /*
87 Ptr to last allocated HP_PTRS (or records buffer for level 0) on this
88 level.
89 */
91};
92
93/*
94 Heap table records and hash index entries are stored in HP_BLOCKs.
95 HP_BLOCK is used as a 'growable array' of fixed-size records. Size of record
96 is recbuffer bytes.
97 The internal representation is as follows:
98 HP_BLOCK is a hierarchical structure of 'blocks'.
99 A block at level 0 is an array records_in_block records.
100 A block at higher level is an HP_PTRS structure with pointers to blocks at
101 lower levels.
102 At the highest level there is one top block. It is stored in HP_BLOCK::root.
103
104 See hp_find_block for a description of how record pointer is obtained from
105 its index.
106 See hp_get_new_block
107*/
108
109struct HP_BLOCK {
110 HP_PTRS *root{nullptr}; /* Top-level block */
112 uint levels{0}; /* number of used levels */
113 uint records_in_block{0}; /* Records in one heap-block */
114 uint recbuffer{0}; /* Length of one saved record */
115 ulong last_allocated{0}; /* number of records there is allocated space for */
116};
117
118struct HP_INFO; /* For reference */
119
120struct HP_KEYDEF /* Key definition with open */
121{
122 uint flag{0}; /* HA_NOSAME | HA_NULL_PART_KEY */
123 uint keysegs{0}; /* Number of key-segment */
124 uint length{0}; /* Length of key (automatic) */
125 uint8 algorithm{0}; /* HASH / BTREE */
126 HA_KEYSEG *seg{nullptr};
127 HP_BLOCK block; /* Where keys are saved */
128 /*
129 Number of buckets used in hash table. Used only to provide
130 #records estimates for heap key scans.
131 */
134 int (*write_key)(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record,
135 uchar *recpos){nullptr};
136 int (*delete_key)(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record,
137 uchar *recpos, int flag){nullptr};
138 uint (*get_key_length)(HP_KEYDEF *keydef, const uchar *key){nullptr};
139};
140
141struct HP_SHARE {
144 ulong min_records, max_records; /* Params to open */
146 uint key_stat_version; /* version to indicate insert/delete */
147 uint records; /* records */
148 uint blength; /* records rounded up to 2^n */
149 uint deleted; /* Deleted records in database */
150 uint reclength; /* Length of one record */
153 uint currently_disabled_keys; /* saved value from "keys" when disabled */
155 uchar *del_link; /* Link to next block with del. rec */
156 char *name; /* Name of "memory-file" */
162 uint auto_key_type; /* real type of the auto key segment */
164};
165
166struct HASH_INFO;
167
168struct HP_INFO {
174 int mode; /* Mode of file (READONLY..) */
176 uchar *lastkey; /* Last used key with rkey */
177 uchar *recbuf; /* Record buffer for rb-tree keys */
185};
186
188
190 HEAP_PTR ptr{nullptr};
191 ulong record_no{0}; /* Number of current record in table scan order (starting
192 at 0) */
193};
194
199 uint auto_key; /* keynr [1 - maxkey] for auto key */
201 uint keys;
208 /*
209 TRUE if heap_create should 'pin' the created share by setting
210 open_count to 1. Is only looked at if not internal_table.
211 */
213};
214
215/* Prototypes for heap-functions */
216
217extern HP_INFO *heap_open(const char *name, int mode);
218extern HP_INFO *heap_open_from_share(HP_SHARE *share, int mode);
220extern void heap_release_share(HP_SHARE *share, bool single_instance);
221extern int heap_close(HP_INFO *info);
222extern int heap_write(HP_INFO *info, const uchar *buff);
223extern int heap_update(HP_INFO *info, const uchar *old, const uchar *newdata);
224extern int heap_rrnd(HP_INFO *info, uchar *buf, HP_HEAP_POSITION *pos);
225extern int heap_scan_init(HP_INFO *info);
226extern int heap_scan(HP_INFO *info, uchar *record);
227extern int heap_delete(HP_INFO *info, const uchar *buff);
228extern int heap_info(HP_INFO *info, HEAPINFO *x, int flag);
229extern int heap_create(const char *name, HP_CREATE_INFO *create_info,
230 HP_SHARE **share, bool *created_new_share);
231extern int heap_delete_table(const char *name);
232extern void heap_drop_table(HP_INFO *info);
233extern int heap_extra(HP_INFO *info, enum ha_extra_function function);
234extern int heap_reset(HP_INFO *info);
235extern int heap_rename(const char *old_name, const char *new_name);
237extern int heap_rsame(HP_INFO *info, uchar *record, int inx);
238extern int heap_rnext(HP_INFO *info, uchar *record);
239extern int heap_rprev(HP_INFO *info, uchar *record);
240extern int heap_rfirst(HP_INFO *info, uchar *record, int inx);
241extern int heap_rlast(HP_INFO *info, uchar *record, int inx);
242extern void heap_clear(HP_INFO *info);
243extern void heap_clear_keys(HP_INFO *info);
244extern int heap_disable_indexes(HP_INFO *info);
245extern int heap_enable_indexes(HP_INFO *info);
246extern int heap_indexes_are_disabled(HP_INFO *info);
247extern void heap_update_auto_increment(HP_INFO *info, const uchar *record);
248ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, key_range *min_key,
249 key_range *max_key);
251int heap_rkey(HP_INFO *info, uchar *record, int inx, const uchar *key,
252 key_part_map keypart_map, enum ha_rkey_function find_flag);
253extern uchar *heap_find(HP_INFO *info, int inx, const uchar *key);
254extern int heap_check_heap(HP_INFO *info, bool print_status);
255extern void heap_position(HP_INFO *info, HP_HEAP_POSITION *pos);
256
257#endif
int heap_scan(HP_INFO *info, uchar *record)
Definition: hp_scan.cc:48
#define HP_PTRS_IN_NOD
Definition: heap.h:52
int heap_panic(enum ha_panic_function flag)
void heap_update_auto_increment(HP_INFO *info, const uchar *record)
Definition: hp_hash.cc:750
HP_INFO * heap_open_from_share_and_register(HP_SHARE *share, int mode)
Definition: hp_open.cc:78
void heap_clear_keys(HP_INFO *info)
Definition: hp_clear.cc:67
int heap_rrnd(HP_INFO *info, uchar *buf, HP_HEAP_POSITION *pos)
Definition: hp_rrnd.cc:37
void heap_drop_table(HP_INFO *info)
Definition: hp_create.cc:305
int heap_rename(const char *old_name, const char *new_name)
Definition: hp_rename.cc:33
int heap_disable_indexes(HP_INFO *info)
Definition: hp_clear.cc:118
int heap_check_heap(HP_INFO *info, bool print_status)
Definition: _check.cc:53
uchar * HEAP_PTR
Definition: heap.h:187
int heap_rnext(HP_INFO *info, uchar *record)
Definition: hp_rnext.cc:30
ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, key_range *min_key, key_range *max_key)
Definition: hp_hash.cc:66
int heap_enable_indexes(HP_INFO *info)
Definition: hp_clear.cc:148
int heap_rprev(HP_INFO *info, uchar *record)
Definition: hp_rprev.cc:30
HP_INFO * heap_open_from_share(HP_SHARE *share, int mode)
Definition: hp_open.cc:42
#define HP_MAX_LEVELS
Definition: heap.h:51
void heap_clear(HP_INFO *info)
Definition: hp_clear.cc:36
HP_INFO * heap_open(const char *name, int mode)
Definition: hp_open.cc:116
int heap_rfirst(HP_INFO *info, uchar *record, int inx)
Definition: hp_rfirst.cc:30
int heap_update(HP_INFO *info, const uchar *old, const uchar *newdata)
Definition: hp_update.cc:32
int heap_reset(HP_INFO *info)
Definition: hp_extra.cc:61
int heap_write(HP_INFO *info, const uchar *buff)
Definition: hp_write.cc:47
int heap_info(HP_INFO *info, HEAPINFO *x, int flag)
Definition: hp_info.cc:39
int heap_indexes_are_disabled(HP_INFO *info)
Definition: hp_clear.cc:177
int heap_rlast(HP_INFO *info, uchar *record, int inx)
Definition: hp_rlast.cc:30
int heap_delete(HP_INFO *info, const uchar *buff)
Definition: hp_delete.cc:33
uchar * heap_find(HP_INFO *info, int inx, const uchar *key)
Definition: hp_rkey.cc:89
int heap_create(const char *name, HP_CREATE_INFO *create_info, HP_SHARE **share, bool *created_new_share)
Definition: hp_create.cc:43
int heap_close(HP_INFO *info)
Definition: hp_close.cc:33
void heap_position(HP_INFO *info, HP_HEAP_POSITION *pos)
Definition: hp_info.cc:30
int heap_rkey(HP_INFO *info, uchar *record, int inx, const uchar *key, key_part_map keypart_map, enum ha_rkey_function find_flag)
Definition: hp_rkey.cc:30
int heap_scan_init(HP_INFO *info)
Definition: hp_scan.cc:39
void heap_release_share(HP_SHARE *share, bool single_instance)
Dereference a HEAP share and free it if it's not referenced.
Definition: hp_open.cc:97
int heap_extra(HP_INFO *info, enum ha_extra_function function)
Definition: hp_extra.cc:38
int heap_rsame(HP_INFO *info, uchar *record, int inx)
Definition: hp_rsame.cc:38
int hp_panic(enum ha_panic_function flag)
Definition: hp_panic.cc:30
int heap_delete_table(const char *name)
Definition: hp_create.cc:288
static int flag
Definition: hp_test1.cc:40
This file includes constants used by all storage engines.
ha_panic_function
Definition: my_base.h:432
ha_rkey_function
Definition: my_base.h:78
ulong key_part_map
Definition: my_base.h:1008
my_off_t ha_rows
Definition: my_base.h:1141
ha_extra_function
Definition: my_base.h:185
Some integer typedefs for easier portability.
unsigned long long int ulonglong
Definition: my_inttypes.h:56
uint8_t uint8
Definition: my_inttypes.h:63
unsigned char uchar
Definition: my_inttypes.h:52
#define MAX_TREE_HEIGHT
Definition: my_tree.h:40
static int record
Definition: mysqltest.cc:195
Definition: buf0block_hint.cc:30
mode
Definition: file_handle.h:61
required string key
Definition: replication_asynchronous_connection_failover.proto:60
case opt name
Definition: sslopt-case.h:29
Definition: heapdef.h:59
Definition: my_compare.h:60
Definition: heap.h:57
ulonglong data_length
Definition: heap.h:61
uint reclength
Definition: heap.h:63
int errkey
Definition: heap.h:64
ulong deleted
Definition: heap.h:59
ulong records
Definition: heap.h:58
time_t create_time
Definition: heap.h:66
ulong max_records
Definition: heap.h:60
ulonglong index_length
Definition: heap.h:62
ulonglong auto_increment
Definition: heap.h:65
Definition: heap.h:109
uint levels
Definition: heap.h:112
uint records_in_block
Definition: heap.h:113
uint recbuffer
Definition: heap.h:114
HP_PTRS * root
Definition: heap.h:110
ulong last_allocated
Definition: heap.h:115
struct st_level_info level_info[HP_MAX_LEVELS+1]
Definition: heap.h:111
Definition: heap.h:195
ulonglong auto_increment
Definition: heap.h:204
ulong max_records
Definition: heap.h:197
uint keys
Definition: heap.h:201
uint auto_key_type
Definition: heap.h:200
bool with_auto_increment
Definition: heap.h:205
ulong min_records
Definition: heap.h:198
HP_KEYDEF * keydef
Definition: heap.h:196
uint reclength
Definition: heap.h:202
uint auto_key
Definition: heap.h:199
bool single_instance
Definition: heap.h:206
bool pin_share
Definition: heap.h:212
bool delete_on_close
Definition: heap.h:207
ulonglong max_table_size
Definition: heap.h:203
Definition: heap.h:189
HEAP_PTR ptr
Definition: heap.h:190
ulong record_no
Definition: heap.h:191
Definition: heap.h:168
bool implicit_emptied
Definition: heap.h:182
HASH_INFO * current_hash_ptr
Definition: heap.h:171
int errkey
Definition: heap.h:173
int lastinx
Definition: heap.h:173
uchar * current_ptr
Definition: heap.h:170
TREE_ELEMENT ** last_pos
Definition: heap.h:180
ulong next_block
Definition: heap.h:172
uchar * lastkey
Definition: heap.h:176
THR_LOCK_DATA lock
Definition: heap.h:183
ulong current_record
Definition: heap.h:172
int mode
Definition: heap.h:174
enum ha_rkey_function last_find_flag
Definition: heap.h:178
HP_SHARE * s
Definition: heap.h:169
uchar * recbuf
Definition: heap.h:177
uint lastkey_len
Definition: heap.h:181
TREE_ELEMENT * parents[MAX_TREE_HEIGHT+1]
Definition: heap.h:179
uint opt_flag
Definition: heap.h:175
uint update
Definition: heap.h:175
LIST open_list
Definition: heap.h:184
Definition: heap.h:121
ha_rows hash_buckets
Definition: heap.h:132
uint keysegs
Definition: heap.h:123
uint8 algorithm
Definition: heap.h:125
uint flag
Definition: heap.h:122
int(* write_key)(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record, uchar *recpos)
Definition: heap.h:134
uint length
Definition: heap.h:124
TREE rb_tree
Definition: heap.h:133
int(* delete_key)(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record, uchar *recpos, int flag)
Definition: heap.h:136
HA_KEYSEG * seg
Definition: heap.h:126
uint(* get_key_length)(HP_KEYDEF *keydef, const uchar *key)
Definition: heap.h:138
HP_BLOCK block
Definition: heap.h:127
Definition: heap.h:71
uchar * blocks[HP_PTRS_IN_NOD]
Definition: heap.h:72
Definition: heap.h:141
uint deleted
Definition: heap.h:149
time_t create_time
Definition: heap.h:157
HP_KEYDEF * keydef
Definition: heap.h:143
ulonglong auto_increment
Definition: heap.h:163
uint currently_disabled_keys
Definition: heap.h:153
uint blength
Definition: heap.h:148
uint max_key_length
Definition: heap.h:152
uint changed
Definition: heap.h:151
uchar * del_link
Definition: heap.h:155
ulong min_records
Definition: heap.h:144
uint keys
Definition: heap.h:152
bool delete_on_close
Definition: heap.h:159
LIST open_list
Definition: heap.h:160
ulonglong index_length
Definition: heap.h:145
ulonglong max_table_size
Definition: heap.h:145
uint auto_key_type
Definition: heap.h:162
uint records
Definition: heap.h:147
ulong max_records
Definition: heap.h:144
uint open_count
Definition: heap.h:154
THR_LOCK lock
Definition: heap.h:158
uint key_stat_version
Definition: heap.h:146
HP_BLOCK block
Definition: heap.h:142
ulonglong data_length
Definition: heap.h:145
char * name
Definition: heap.h:156
uint auto_key
Definition: heap.h:161
uint reclength
Definition: heap.h:150
Definition: my_list.h:36
Definition: thr_lock.h:124
Definition: thr_lock.h:139
Definition: my_tree.h:58
Definition: my_tree.h:68
Definition: my_base.h:1125
Definition: heap.h:75
HP_PTRS * last_blocks
Definition: heap.h:90
ulong records_under_level
Definition: heap.h:84
uint free_ptrs_in_block
Definition: heap.h:77
Include file for Sun RPC to compile out of the box.