heap.h

/*
 Copyright (c) 2000, 2025, Oracle and/or its affiliates.

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License, version 2.0,
 as published by the Free Software Foundation.

 This program is designed to work with certain software (including
 but not limited to OpenSSL) that is licensed under separate terms,
 as designated in a particular file or component or in included license
 documentation. The authors of MySQL hereby grant you an additional
 permission to link the program and your derivative works with the
 separately licensed software that they have either included with
 the program or referenced in the documentation.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 GNU General Public License, version 2.0, for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/

/* This file should be included when using heap_database_functions */
/* Author: Michael Widenius */

/**
 @file include/heap.h
*/

#ifndef_heap_h
#define_heap_h

#ifndef_my_base_h
#include"my_base.h"
#endif

#include<sys/types.h>
#include<time.h>

#include"my_compare.h"
#include"my_inttypes.h"
#include"my_list.h"
#include"my_tree.h"
#include"thr_lock.h"

/* defines used by heap-funktions */

#defineHP_MAX_LEVELS 4 /* 128^5 records is enough */
#defineHP_PTRS_IN_NOD 128

/* struct used with heap_funktions */

structHEAPINFO/* Struct from heap_info */
{
ulongrecords; /* Records in database */
ulongdeleted; /* Deleted records in database */
ulongmax_records;
ulonglongdata_length;
ulonglongindex_length;
uintreclength; /* Length of one record */
interrkey;
ulonglongauto_increment;
time_tcreate_time;
};

/* Structs used by heap-database-handler */

structHP_PTRS {
uchar*blocks[HP_PTRS_IN_NOD]; /* pointers to HP_PTRS or records */
};

structst_level_info {
/* Number of unused slots in *last_blocks HP_PTRS block (0 for 0th level) */
uintfree_ptrs_in_block{0};

/*
 Maximum number of records that can be 'contained' inside of each element
 of last_blocks array. For level 0 - 1, for level 1 - HP_PTRS_IN_NOD, for
 level 2 - HP_PTRS_IN_NOD^2 and so forth.
 */
ulongrecords_under_level{0};

/*
 Ptr to last allocated HP_PTRS (or records buffer for level 0) on this
 level.
 */
HP_PTRS*last_blocks{nullptr};
};

/*
 Heap table records and hash index entries are stored in HP_BLOCKs.
 HP_BLOCK is used as a 'growable array' of fixed-size records. Size of record
 is recbuffer bytes.
 The internal representation is as follows:
 HP_BLOCK is a hierarchical structure of 'blocks'.
 A block at level 0 is an array records_in_block records.
 A block at higher level is an HP_PTRS structure with pointers to blocks at
 lower levels.
 At the highest level there is one top block. It is stored in HP_BLOCK::root.

 See hp_find_block for a description of how record pointer is obtained from
 its index.
 See hp_get_new_block
*/

structHP_BLOCK {
HP_PTRS*root{nullptr}; /* Top-level block */
structst_level_infolevel_info[HP_MAX_LEVELS+1];
uintlevels{0}; /* number of used levels */
uintrecords_in_block{0}; /* Records in one heap-block */
uintrecbuffer{0}; /* Length of one saved record */
ulonglast_allocated{0}; /* number of records there is allocated space for */
};

structHP_INFO; /* For reference */

structHP_KEYDEF/* Key definition with open */
{
uintflag{0}; /* HA_NOSAME | HA_NULL_PART_KEY */
uintkeysegs{0}; /* Number of key-segment */
uintlength{0}; /* Length of key (automatic) */
uint8algorithm{0}; /* HASH / BTREE */
HA_KEYSEG*seg{nullptr};
HP_BLOCKblock; /* Where keys are saved */
/*
 Number of buckets used in hash table. Used only to provide
 #records estimates for heap key scans.
 */
ha_rowshash_buckets{0};
TREErb_tree;
int (*write_key)(HP_INFO*info, HP_KEYDEF*keyinfo, constuchar*record,
uchar*recpos){nullptr};
int (*delete_key)(HP_INFO*info, HP_KEYDEF*keyinfo, constuchar*record,
uchar*recpos, intflag){nullptr};
uint (*get_key_length)(HP_KEYDEF*keydef, constuchar*key){nullptr};
};

structHP_SHARE {
HP_BLOCKblock;
HP_KEYDEF*keydef;
ulongmin_records, max_records; /* Params to open */
ulonglongdata_length, index_length, max_table_size;
uintkey_stat_version; /* version to indicate insert/delete */
uintrecords; /* records */
uintblength; /* records rounded up to 2^n */
uintdeleted; /* Deleted records in database */
uintreclength; /* Length of one record */
uintchanged;
uintkeys, max_key_length;
uintcurrently_disabled_keys; /* saved value from "keys" when disabled */
uintopen_count;
uchar*del_link; /* Link to next block with del. rec */
char*name; /* Name of "memory-file" */
time_tcreate_time;
THR_LOCKlock;
booldelete_on_close;
LISTopen_list;
uintauto_key;
uintauto_key_type; /* real type of the auto key segment */
ulonglongauto_increment;
};

structHASH_INFO;

structHP_INFO {
HP_SHARE*s;
uchar*current_ptr;
HASH_INFO*current_hash_ptr;
ulongcurrent_record, next_block;
intlastinx, errkey;
intmode; /* Mode of file (READONLY..) */
uintopt_flag, update;
uchar*lastkey; /* Last used key with rkey */
uchar*recbuf; /* Record buffer for rb-tree keys */
enumha_rkey_functionlast_find_flag;
TREE_ELEMENT*parents[MAX_TREE_HEIGHT+1];
TREE_ELEMENT**last_pos;
uintlastkey_len;
boolimplicit_emptied;
THR_LOCK_DATAlock;
LISTopen_list;
};

typedefuchar*HEAP_PTR;

structHP_HEAP_POSITION {
HEAP_PTRptr{nullptr};
ulongrecord_no{0}; /* Number of current record in table scan order (starting
 at 0) */
};

structHP_CREATE_INFO {
HP_KEYDEF*keydef;
ulongmax_records;
ulongmin_records;
uintauto_key; /* keynr [1 - maxkey] for auto key */
uintauto_key_type;
uintkeys;
uintreclength;
ulonglongmax_table_size;
ulonglongauto_increment;
boolwith_auto_increment;
boolsingle_instance;
booldelete_on_close;
/*
 TRUE if heap_create should 'pin' the created share by setting
 open_count to 1. Is only looked at if not internal_table.
 */
boolpin_share;
};

/* Prototypes for heap-functions */

externHP_INFO*heap_open(constchar*name, intmode);
externHP_INFO*heap_open_from_share(HP_SHARE*share, intmode);
externHP_INFO*heap_open_from_share_and_register(HP_SHARE*share, intmode);
externvoidheap_release_share(HP_SHARE*share, boolsingle_instance);
externintheap_close(HP_INFO*info);
externintheap_write(HP_INFO*info, constuchar*buff);
externintheap_update(HP_INFO*info, constuchar*old, constuchar*newdata);
externintheap_rrnd(HP_INFO*info, uchar*buf, HP_HEAP_POSITION*pos);
externintheap_scan_init(HP_INFO*info);
externintheap_scan(HP_INFO*info, uchar*record);
externintheap_delete(HP_INFO*info, constuchar*buff);
externintheap_info(HP_INFO*info, HEAPINFO*x, intflag);
externintheap_create(constchar*name, HP_CREATE_INFO*create_info,
HP_SHARE**share, bool*created_new_share);
externintheap_delete_table(constchar*name);
externvoidheap_drop_table(HP_INFO*info);
externintheap_extra(HP_INFO*info, enumha_extra_functionfunction);
externintheap_reset(HP_INFO*info);
externintheap_rename(constchar*old_name, constchar*new_name);
externintheap_panic(enumha_panic_functionflag);
externintheap_rsame(HP_INFO*info, uchar*record, intinx);
externintheap_rnext(HP_INFO*info, uchar*record);
externintheap_rprev(HP_INFO*info, uchar*record);
externintheap_rfirst(HP_INFO*info, uchar*record, intinx);
externintheap_rlast(HP_INFO*info, uchar*record, intinx);
externvoidheap_clear(HP_INFO*info);
externvoidheap_clear_keys(HP_INFO*info);
externintheap_disable_indexes(HP_INFO*info);
externintheap_enable_indexes(HP_INFO*info);
externintheap_indexes_are_disabled(HP_INFO*info);
externvoidheap_update_auto_increment(HP_INFO*info, constuchar*record);
ha_rowshp_rb_records_in_range(HP_INFO*info, intinx, key_range*min_key,
key_range*max_key);
inthp_panic(enumha_panic_functionflag);
intheap_rkey(HP_INFO*info, uchar*record, intinx, constuchar*key,
key_part_mapkeypart_map, enumha_rkey_functionfind_flag);
externuchar*heap_find(HP_INFO*info, intinx, constuchar*key);
externintheap_check_heap(HP_INFO*info, boolprint_status);
externvoidheap_position(HP_INFO*info, HP_HEAP_POSITION*pos);

#endif