1
/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
3
This program is free software; you can redistribute it and/or modify
4
it under the terms of the GNU General Public License as published by
5
the Free Software Foundation; version 2 of the License.
7
This program is distributed in the hope that it will be useful,
8
but WITHOUT ANY WARRANTY; without even the implied warranty of
9
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10
GNU General Public License for more details.
12
You should have received a copy of the GNU General Public License
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
/* functions on blocks; Keys and records are saved in blocks */
21
Find record according to record-position.
23
The record is located by factoring position number pos into (p_0, p_1, ...)
25
pos = SUM_i(block->level_info[i].records_under_level * p_i)
26
{p_0, p_1, ...} serve as indexes to descend the blocks tree.
29
uchar *hp_find_block(HP_BLOCK *block, ulong pos)
32
reg3 HP_PTRS *ptr; /* block base ptr */
34
for (i=block->levels-1, ptr=block->root ; i > 0 ; i--)
36
ptr=(HP_PTRS*)ptr->blocks[pos/block->level_info[i].records_under_level];
37
pos%=block->level_info[i].records_under_level;
39
return (uchar*) ptr+ pos*block->recbuffer;
44
Get one new block-of-records. Alloc ptr to block if needed
48
block HP_BLOCK tree-like block
49
alloc_length OUT Amount of memory allocated from the heap
51
Interrupts are stopped to allow ha_panic in interrupts
57
int hp_get_new_block(HP_BLOCK *block, size_t *alloc_length)
62
for (i=0 ; i < block->levels ; i++)
63
if (block->level_info[i].free_ptrs_in_block)
67
Allocate space for leaf block plus space for upper level blocks up to
68
first level that has a free slot to put the pointer.
69
In some cases we actually allocate more then we need:
70
Consider e.g. a situation where we have one level 1 block and one level 0
71
block, the level 0 block is full and this function is called. We only
72
need a leaf block in this case. Nevertheless, we will get here with i=1
73
and will also allocate sizeof(HP_PTRS) for non-leaf block and will never
75
This doesn't add much overhead - with current values of sizeof(HP_PTRS)
76
and my_default_record_cache_size we get about 1/128 unused memory.
78
*alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer;
79
if (!(root=(HP_PTRS*) my_malloc(*alloc_length,MYF(MY_WME))))
85
block->root=block->level_info[0].last_blocks=root;
89
if ((uint) i == block->levels)
91
/* Adding a new level on top of the existing ones. */
94
Use first allocated HP_PTRS as a top-level block. Put the current
95
block tree into the first slot of a new top-level block.
97
block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
98
((HP_PTRS**) root)[0]= block->root;
99
block->root=block->level_info[i].last_blocks= root++;
101
/* Occupy the free slot we've found at level i */
102
block->level_info[i].last_blocks->
103
blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
106
/* Add a block subtree with each node having one left-most child */
107
for (j=i-1 ; j >0 ; j--)
109
block->level_info[j].last_blocks= root++;
110
block->level_info[j].last_blocks->blocks[0]=(uchar*) root;
111
block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
115
root now points to last (block->records_in_block* block->recbuffer)
116
allocated bytes. Use it as a leaf block.
118
block->level_info[0].last_blocks= root;
124
/* free all blocks under level */
126
uchar *hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, uchar *last_pos)
132
next_ptr=(uchar*) pos+block->recbuffer;
135
max_pos= (block->level_info[level-1].last_blocks == pos) ?
136
HP_PTRS_IN_NOD - block->level_info[level-1].free_ptrs_in_block :
139
next_ptr=(uchar*) (pos+1);
140
for (i=0 ; i < max_pos ; i++)
141
next_ptr=hp_free_level(block,level-1,
142
(HP_PTRS*) pos->blocks[i],next_ptr);
144
if ((uchar*) pos != last_pos)
149
return next_ptr; /* next memory position */