00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #include "heap_priv.h"
00019
00020 #include <cstdlib>
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 unsigned char *hp_find_block(HP_BLOCK *block, uint32_t pos)
00032 {
00033 int i;
00034 HP_PTRS *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
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
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
00070
00071
00072
00073
00074
00075
00076
00077
00078
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
00094 block->levels=i+1;
00095
00096
00097
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
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
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
00118
00119
00120 block->level_info[0].last_blocks= root;
00121 }
00122 return 0;
00123 }
00124
00125
00126
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;
00155 }