1/* Copyright (c) 2000, 2014, 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 as published by
5 the Free Software Foundation; version 2 of the License.
6
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.
11
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 */
15
16/* functions on blocks; Keys and records are saved in blocks */
17
18#include "heapdef.h"
19
20/*
21 Find record according to record-position.
22
23 The record is located by factoring position number pos into (p_0, p_1, ...)
24 such that
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.
27*/
28
29uchar *hp_find_block(HP_BLOCK *block, ulong pos)
30{
31 reg1 int i;
32 reg3 HP_PTRS *ptr; /* block base ptr */
33
34 for (i=block->levels-1, ptr=block->root ; i > 0 ; i--)
35 {
36 ptr=(HP_PTRS*)ptr->blocks[pos/block->level_info[i].records_under_level];
37 pos%=block->level_info[i].records_under_level;
38 }
39 return (uchar*) ptr+ pos*block->recbuffer;
40}
41
42
43/*
44 Get one new block-of-records. Alloc ptr to block if needed
45
46 SYNOPSIS
47 hp_get_new_block()
48 info heap handle
49 block HP_BLOCK tree-like block
50 alloc_length OUT Amount of memory allocated from the heap
51
52 Interrupts are stopped to allow ha_panic in interrupts
53 RETURN
54 0 OK
55 1 Out of memory
56*/
57
58int hp_get_new_block(HP_SHARE *info, HP_BLOCK *block, size_t *alloc_length)
59{
60 reg1 uint i,j;
61 HP_PTRS *root;
62
63 for (i=0 ; i < block->levels ; i++)
64 if (block->level_info[i].free_ptrs_in_block)
65 break;
66
67 /*
68 Allocate space for leaf block (data) plus space for upper level blocks
69 up to first level that has a free slot to put the pointer.
70 If this is a new level, we have to allocate pointers to all future
71 lower levels.
72
73 For example, for level 0, we allocate data for X rows.
74 When level 0 is full, we allocate data for HP_PTRS_IN_NOD + X rows.
75 Next time we allocate data for X rows.
76 When level 1 is full, we allocate data for HP_PTRS_IN_NOD at level 2 and 1
77 + X rows at level 0.
78 */
79 *alloc_length= (sizeof(HP_PTRS) * ((i == block->levels) ? i : i - 1) +
80 (ulonglong)block->records_in_block * block->recbuffer);
81 if (!(root=(HP_PTRS*) my_malloc(*alloc_length,
82 MYF(MY_WME |
83 (info->internal ?
84 MY_THREAD_SPECIFIC : 0)))))
85 return 1;
86
87 if (i == 0)
88 {
89 block->levels=1;
90 block->root=block->level_info[0].last_blocks=root;
91 }
92 else
93 {
94 if ((uint) i == block->levels)
95 {
96 /* Adding a new level on top of the existing ones. */
97 block->levels=i+1;
98 /*
99 Use first allocated HP_PTRS as a top-level block. Put the current
100 block tree into the first slot of a new top-level block.
101 */
102 block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
103 ((HP_PTRS**) root)[0]= block->root;
104 block->root=block->level_info[i].last_blocks= root++;
105 }
106 /* Occupy the free slot we've found at level i */
107 block->level_info[i].last_blocks->
108 blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
109 (uchar*) root;
110
111 /* Add a block subtree with each node having one left-most child */
112 for (j=i-1 ; j >0 ; j--)
113 {
114 block->level_info[j].last_blocks= root++;
115 block->level_info[j].last_blocks->blocks[0]=(uchar*) root;
116 block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
117 }
118
119 /*
120 root now points to last (block->records_in_block* block->recbuffer)
121 allocated bytes. Use it as a leaf block.
122 */
123 block->level_info[0].last_blocks= root;
124 }
125 return 0;
126}
127
128
129 /* free all blocks under level */
130
131uchar *hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, uchar *last_pos)
132{
133 int i,max_pos;
134 uchar *next_ptr;
135
136 if (level == 1)
137 next_ptr=(uchar*) pos+block->recbuffer;
138 else
139 {
140 max_pos= (block->level_info[level-1].last_blocks == pos) ?
141 HP_PTRS_IN_NOD - block->level_info[level-1].free_ptrs_in_block :
142 HP_PTRS_IN_NOD;
143
144 next_ptr=(uchar*) (pos+1);
145 for (i=0 ; i < max_pos ; i++)
146 next_ptr=hp_free_level(block,level-1,
147 (HP_PTRS*) pos->blocks[i],next_ptr);
148 }
149 if ((uchar*) pos != last_pos)
150 {
151 my_free(pos);
152 return last_pos;
153 }
154 return next_ptr; /* next memory position */
155}
156