MySQL  8.0.27
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 
55 struct HEAPINFO /* Struct from heap_info */
56 {
57  ulong records; /* Records in database */
58  ulong deleted; /* Deleted records in database */
59  ulong max_records;
62  uint reclength; /* Length of one record */
63  int errkey;
65  time_t create_time;
66 };
67 
68 /* Structs used by heap-database-handler */
69 
70 struct HP_PTRS {
71  uchar *blocks[HP_PTRS_IN_NOD]; /* pointers to HP_PTRS or records */
72 };
73 
74 struct st_level_info {
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  */
89  HP_PTRS *last_blocks{nullptr};
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 
108 struct 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 
117 struct HP_INFO; /* For referense */
118 
119 struct 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 
140 struct 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" */
156  time_t create_time;
161  uint auto_key_type; /* real type of the auto key segment */
163 };
164 
165 struct HASH_INFO;
166 
167 struct 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 
186 typedef uchar *HEAP_PTR;
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 
196  ulong max_records;
197  ulong min_records;
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  */
211  bool pin_share;
212 };
213 
214 /* Prototypes for heap-functions */
215 
216 extern HP_INFO *heap_open(const char *name, int mode);
217 extern HP_INFO *heap_open_from_share(HP_SHARE *share, int mode);
219 extern void heap_release_share(HP_SHARE *share, bool single_instance);
220 extern int heap_close(HP_INFO *info);
221 extern int heap_write(HP_INFO *info, const uchar *buff);
222 extern int heap_update(HP_INFO *info, const uchar *old, const uchar *newdata);
224 extern int heap_scan_init(HP_INFO *info);
225 extern int heap_scan(HP_INFO *info, uchar *record);
226 extern int heap_delete(HP_INFO *info, const uchar *buff);
227 extern int heap_info(HP_INFO *info, HEAPINFO *x, int flag);
228 extern int heap_create(const char *name, HP_CREATE_INFO *create_info,
229  HP_SHARE **share, bool *created_new_share);
230 extern int heap_delete_table(const char *name);
231 extern void heap_drop_table(HP_INFO *info);
232 extern int heap_extra(HP_INFO *info, enum ha_extra_function function);
233 extern int heap_reset(HP_INFO *info);
234 extern int heap_rename(const char *old_name, const char *new_name);
236 extern int heap_rsame(HP_INFO *info, uchar *record, int inx);
237 extern int heap_rnext(HP_INFO *info, uchar *record);
238 extern int heap_rprev(HP_INFO *info, uchar *record);
239 extern int heap_rfirst(HP_INFO *info, uchar *record, int inx);
240 extern int heap_rlast(HP_INFO *info, uchar *record, int inx);
241 extern void heap_clear(HP_INFO *info);
242 extern void heap_clear_keys(HP_INFO *info);
243 extern int heap_disable_indexes(HP_INFO *info);
244 extern int heap_enable_indexes(HP_INFO *info);
246 extern void heap_update_auto_increment(HP_INFO *info, const uchar *record);
248  key_range *max_key);
250 int heap_rkey(HP_INFO *info, uchar *record, int inx, const uchar *key,
251  key_part_map keypart_map, enum ha_rkey_function find_flag);
252 extern uchar *heap_find(HP_INFO *info, int inx, const uchar *key);
253 extern 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
HP_INFO * heap_open_from_share(HP_SHARE *share, int mode)
Definition: hp_open.cc:41
#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:748
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
HP_INFO * heap_open(const char *name, int mode)
Definition: hp_open.cc:115
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
#define HP_MAX_LEVELS
Definition: heap.h:50
void heap_clear(HP_INFO *info)
Definition: hp_clear.cc:35
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
int heap_create(const char *name, HP_CREATE_INFO *create_info, HP_SHARE **share, bool *created_new_share)
Definition: hp_create.cc:42
HP_INFO * heap_open_from_share_and_register(HP_SHARE *share, int mode)
Definition: hp_open.cc:77
int heap_close(HP_INFO *info)
Definition: hp_close.cc:32
uchar * heap_find(HP_INFO *info, int inx, const uchar *key)
Definition: hp_rkey.cc:88
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:1138
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:1122
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