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