diff options
Diffstat (limited to 'heap/hp_block.c')
| -rw-r--r-- | heap/hp_block.c | 51 |
1 files changed, 46 insertions, 5 deletions
diff --git a/heap/hp_block.c b/heap/hp_block.c index 6a022fb3084..f26b208b521 100644 --- a/heap/hp_block.c +++ b/heap/hp_block.c @@ -18,12 +18,19 @@ #include "heapdef.h" - /* Find record according to record-position */ +/* + Find record according to record-position. + + The record is located by factoring position number pos into (p_0, p_1, ...) + such that + pos = SUM_i(block->level_info[i].records_under_level * p_i) + {p_0, p_1, ...} serve as indexes to descend the blocks tree. +*/ byte *hp_find_block(HP_BLOCK *block, ulong pos) { reg1 int i; - reg3 HP_PTRS *ptr; + reg3 HP_PTRS *ptr; /* block base ptr */ for (i=block->levels-1, ptr=block->root ; i > 0 ; i--) { @@ -34,8 +41,18 @@ byte *hp_find_block(HP_BLOCK *block, ulong pos) } - /* get one new block-of-records. Alloc ptr to block if neaded */ - /* Interrupts are stopped to allow ha_panic in interrupts */ +/* + Get one new block-of-records. Alloc ptr to block if needed + SYNOPSIS + hp_get_new_block() + block HP_BLOCK tree-like block + alloc_length OUT Amount of memory allocated from the heap + + Interrupts are stopped to allow ha_panic in interrupts + RETURN + 0 OK + 1 Out of memory +*/ int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length) { @@ -46,6 +63,18 @@ int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length) if (block->level_info[i].free_ptrs_in_block) break; + /* + Allocate space for leaf block plus space for upper level blocks up to + first level that has a free slot to put the pointer. + In some cases we actually allocate more then we need: + Consider e.g. a situation where we have one level 1 block and one level 0 + block, the level 0 block is full and this function is called. We only + need a leaf block in this case. Nevertheless, we will get here with i=1 + and will also allocate sizeof(HP_PTRS) for non-leaf block and will never + use this space. + This doesn't add much overhead - with current values of sizeof(HP_PTRS) + and my_default_record_cache_size we get about 1/128 unused memory. + */ *alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer; if (!(root=(HP_PTRS*) my_malloc(*alloc_length,MYF(0)))) return 1; @@ -60,21 +89,33 @@ int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length) dont_break(); /* Dont allow SIGHUP or SIGINT */ if ((uint) i == block->levels) { + /* Adding a new level on top of the existing ones. */ block->levels=i+1; + /* + Use first allocated HP_PTRS as a top-level block. Put the current + block tree into the first slot of a new top-level block. + */ block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1; ((HP_PTRS**) root)[0]= block->root; block->root=block->level_info[i].last_blocks= root++; } + /* Occupy the free slot we've found at level i */ block->level_info[i].last_blocks-> blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]= (byte*) root; - + + /* Add a block subtree with each node having one left-most child */ for (j=i-1 ; j >0 ; j--) { block->level_info[j].last_blocks= root++; block->level_info[j].last_blocks->blocks[0]=(byte*) root; block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1; } + + /* + root now points to last (block->records_in_block* block->recbuffer) + allocated bytes. Use it as a leaf block. + */ block->level_info[0].last_blocks= root; allow_break(); /* Allow SIGHUP & SIGINT */ } |