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