Drizzled Public API Documentation

hp_block.cc
00001 /* Copyright (C) 2000-2002, 2004 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /* functions on blocks; Keys and records are saved in blocks */
00017 
00018 #include "heap_priv.h"
00019 
00020 #include <cstdlib>
00021 
00022 /*
00023   Find record according to record-position.
00024 
00025   The record is located by factoring position number pos into (p_0, p_1, ...)
00026   such that
00027      pos = SUM_i(block->level_info[i].records_under_level * p_i)
00028   {p_0, p_1, ...} serve as indexes to descend the blocks tree.
00029 */
00030 
00031 unsigned char *hp_find_block(HP_BLOCK *block, uint32_t pos)
00032 {
00033   int i;
00034   HP_PTRS *ptr; /* block base ptr */
00035 
00036   for (i= block->levels-1, ptr=block->root ; i > 0 ; i--)
00037   {
00038     ptr=(HP_PTRS*)ptr->blocks[pos/block->level_info[i].records_under_level];
00039     pos%=block->level_info[i].records_under_level;
00040   }
00041   return (unsigned char*) ptr+ pos*block->recbuffer;
00042 }
00043 
00044 
00045 /*
00046   Get one new block-of-records. Alloc ptr to block if needed
00047 
00048   SYNOPSIS
00049     hp_get_new_block()
00050       block             HP_BLOCK tree-like block
00051       alloc_length OUT  Amount of memory allocated from the heap
00052 
00053   Interrupts are stopped to allow ha_panic in interrupts
00054   RETURN
00055     0  OK
00056     1  Out of memory
00057 */
00058 
00059 int hp_get_new_block(HP_BLOCK *block, size_t *alloc_length)
00060 {
00061   uint32_t i;
00062   HP_PTRS *root;
00063 
00064   for (i=0 ; i < block->levels ; i++)
00065     if (block->level_info[i].free_ptrs_in_block)
00066       break;
00067 
00068   /*
00069     Allocate space for leaf block plus space for upper level blocks up to
00070     first level that has a free slot to put the pointer.
00071     In some cases we actually allocate more then we need:
00072     Consider e.g. a situation where we have one level 1 block and one level 0
00073     block, the level 0 block is full and this function is called. We only
00074     need a leaf block in this case. Nevertheless, we will get here with i=1
00075     and will also allocate sizeof(HP_PTRS) for non-leaf block and will never
00076     use this space.
00077     This doesn't add much overhead - with current values of sizeof(HP_PTRS)
00078     and my_default_record_cache_size we get about 1/128 unused memory.
00079    */
00080   *alloc_length=sizeof(HP_PTRS)*i+block->records_in_block* block->recbuffer;
00081   if (!(root=(HP_PTRS*) malloc(*alloc_length)))
00082     return 1;
00083 
00084   if (i == 0)
00085   {
00086     block->levels=1;
00087     block->root=block->level_info[0].last_blocks=root;
00088   }
00089   else
00090   {
00091     if ((uint) i == block->levels)
00092     {
00093       /* Adding a new level on top of the existing ones. */
00094       block->levels=i+1;
00095       /*
00096         Use first allocated HP_PTRS as a top-level block. Put the current
00097         block tree into the first slot of a new top-level block.
00098       */
00099       block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
00100       ((HP_PTRS**) root)[0]= block->root;
00101       block->root=block->level_info[i].last_blocks= root++;
00102     }
00103     /* Occupy the free slot we've found at level i */
00104     block->level_info[i].last_blocks->
00105       blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
00106   (unsigned char*) root;
00107 
00108     /* Add a block subtree with each node having one left-most child */
00109     for (uint32_t j= i-1 ; j >0 ; j--)
00110     {
00111       block->level_info[j].last_blocks= root++;
00112       block->level_info[j].last_blocks->blocks[0]=(unsigned char*) root;
00113       block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
00114     }
00115 
00116     /*
00117       root now points to last (block->records_in_block* block->recbuffer)
00118       allocated bytes. Use it as a leaf block.
00119     */
00120     block->level_info[0].last_blocks= root;
00121   }
00122   return 0;
00123 }
00124 
00125 
00126   /* free all blocks under level */
00127 
00128 unsigned char *hp_free_level(HP_BLOCK *block, uint32_t level, HP_PTRS *pos, unsigned char *last_pos)
00129 {
00130   int max_pos;
00131   unsigned char *next_ptr;
00132 
00133   if (level == 1)
00134   {
00135     next_ptr=(unsigned char*) pos+block->recbuffer;
00136   }
00137   else
00138   {
00139     max_pos= (block->level_info[level-1].last_blocks == pos) ?
00140       HP_PTRS_IN_NOD - block->level_info[level-1].free_ptrs_in_block :
00141     HP_PTRS_IN_NOD;
00142 
00143     next_ptr=(unsigned char*) (pos+1);
00144     for (int i= 0; i < max_pos ; i++)
00145       next_ptr=hp_free_level(block,level-1,
00146             (HP_PTRS*) pos->blocks[i],next_ptr);
00147   }
00148 
00149   if ((unsigned char*) pos != last_pos)
00150   {
00151     free((unsigned char*) pos);
00152     return last_pos;
00153   }
00154   return next_ptr;      /* next memory position */
00155 }