drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
hp_block.cc
1/* Copyright (C) 2000-2002, 2004 MySQL AB
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 "heap_priv.h"
19
20#include <cstdlib>
21
22/*
23 Find record according to record-position.
24
25 The record is located by factoring position number pos into (p_0, p_1, ...)
26 such that
27 pos = SUM_i(block->level_info[i].records_under_level * p_i)
28 {p_0, p_1, ...} serve as indexes to descend the blocks tree.
29*/
30
31unsigned char *hp_find_block(HP_BLOCK *block, uint32_t pos)
32{
33 int i;
34 HP_PTRS *ptr; /* block base ptr */
35
36 for (i= block->levels-1, ptr=block->root ; i > 0 ; i--)
37 {
38 ptr=(HP_PTRS*)ptr->blocks[pos/block->level_info[i].records_under_level];
39 pos%=block->level_info[i].records_under_level;
40 }
41 return (unsigned char*) ptr+ pos*block->recbuffer;
42}
43
44
45/*
46 Get one new block-of-records. Alloc ptr to block if needed
47
48 SYNOPSIS
49 hp_get_new_block()
50 block HP_BLOCK tree-like block
51 alloc_length OUT Amount of memory allocated from the heap
52
53 Interrupts are stopped to allow ha_panic in interrupts
54 RETURN
55 0 OK
56 1 Out of memory
57*/
58
59int hp_get_new_block(HP_BLOCK *block, size_t *alloc_length)
60{
61 uint32_t i;
62 HP_PTRS *root;
63
64 for (i=0 ; i < block->levels ; i++)
65 if (block->level_info[i].free_ptrs_in_block)
66 break;
67
68 /*
69 Allocate space for leaf block plus space for upper level blocks up to
70 first level that has a free slot to put the pointer.
71 In some cases we actually allocate more then we need:
72 Consider e.g. a situation where we have one level 1 block and one level 0
73 block, the level 0 block is full and this function is called. We only
74 need a leaf block in this case. Nevertheless, we will get here with i=1
75 and will also allocate sizeof(HP_PTRS) for non-leaf block and will never
76 use this space.
77 This doesn't add much overhead - with current values of sizeof(HP_PTRS)
78 and my_default_record_cache_size we get about 1/128 unused memory.
79 */
80 *alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer;
81 root=(HP_PTRS*) malloc(*alloc_length);
82
83 if (i == 0)
84 {
85 block->levels=1;
86 block->root=block->level_info[0].last_blocks=root;
87 }
88 else
89 {
90 if ((uint) i == block->levels)
91 {
92 /* Adding a new level on top of the existing ones. */
93 block->levels=i+1;
94 /*
95 Use first allocated HP_PTRS as a top-level block. Put the current
96 block tree into the first slot of a new top-level block.
97 */
98 block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
99 ((HP_PTRS**) root)[0]= block->root;
100 block->root=block->level_info[i].last_blocks= root++;
101 }
102 /* Occupy the free slot we've found at level i */
103 block->level_info[i].last_blocks->
104 blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
105 (unsigned char*) root;
106
107 /* Add a block subtree with each node having one left-most child */
108 for (uint32_t j= i-1 ; j >0 ; j--)
109 {
110 block->level_info[j].last_blocks= root++;
111 block->level_info[j].last_blocks->blocks[0]=(unsigned char*) root;
112 block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
113 }
114
115 /*
116 root now points to last (block->records_in_block* block->recbuffer)
117 allocated bytes. Use it as a leaf block.
118 */
119 block->level_info[0].last_blocks= root;
120 }
121 return 0;
122}
123
124
125 /* free all blocks under level */
126
127unsigned char *hp_free_level(HP_BLOCK *block, uint32_t level, HP_PTRS *pos, unsigned char *last_pos)
128{
129 unsigned char *next_ptr;
130
131 if (level == 1)
132 {
133 next_ptr=(unsigned char*) pos+block->recbuffer;
134 }
135 else
136 {
137 int max_pos= (block->level_info[level-1].last_blocks == pos) ? HP_PTRS_IN_NOD - block->level_info[level-1].free_ptrs_in_block : HP_PTRS_IN_NOD;
138
139 next_ptr=(unsigned char*) (pos+1);
140 for (int i= 0; i < max_pos ; i++)
141 next_ptr=hp_free_level(block,level-1,
142 (HP_PTRS*) pos->blocks[i],next_ptr);
143 }
144
145 if ((unsigned char*) pos != last_pos)
146 {
147 free(pos);
148 return last_pos;
149 }
150 return next_ptr; /* next memory position */
151}