Made on Kubuntu
00001 // Copyright (C) 2009-2010 Ferdinand Majerech 00002 // This file is part of MiniINI 00003 // For conditions of distribution and use, see copyright notice in LICENSE.txt 00004 00005 #include <cstring> 00006 00007 #include "allocator.h" 00008 #include "time.h" 00009 #include "globals.h" 00010 00011 namespace miniini_private 00012 { 00013 00014 Allocator::Allocator(const ui size, const ui blocks) 00015 :NumBlocks(blocks) 00016 ,CurrentBlock(0) 00017 ,BlockMinSize(size / NumBlocks + 1) 00018 ,Blocks(new Block * [NumBlocks]) 00019 { 00020 #ifdef MINIINI_BENCH_EXTRA 00021 #ifdef linux 00022 ld atimestart = GetTime(); 00023 #endif 00024 #endif 00025 //Allocate enough blocks to have size of space 00026 for(ui block = 0; block < NumBlocks; ++block) 00027 { 00028 Blocks[block] = new Block(BlockMinSize); 00029 } 00030 #ifdef MINIINI_BENCH_EXTRA 00031 #ifdef linux 00032 bench_alloctime += GetTime() - atimestart; 00033 #endif 00034 #endif 00035 } 00036 00037 void Allocator::Trim() 00038 { 00039 //Since current block can only be incremented, 00040 //if the current block is not the last block, there are 00041 //some blocks left over from constructor that we can delete. 00042 while(CurrentBlock < (NumBlocks - 1)) 00043 { 00044 DeleteBlock(CurrentBlock + 1); 00045 } 00046 } 00047 00048 void Allocator::DeleteSpace(c * const ptr) 00049 { 00050 i blockidx = FindBlock(ptr); 00051 //ptr must point to some block. Otherwise we have an error 00052 MINIINI_ASSERT(blockidx >= 0, "Pointer that doesn't point to space " 00053 "allocated by this instance of Allocator " 00054 "was passed as pointer to space to delete " 00055 "to Allocator::DeleteSpace()"); 00056 Block * block = Blocks[blockidx]; 00057 ++block->PtrsDeleted; 00058 //If as many pointers as given out were deleted, this block is no 00059 //longer used and we can delete it 00060 if(block->PtrsDeleted == block->PtrsGiven) 00061 { 00062 //This is the current block: no need to delete it as it's not yet full 00063 if(static_cast<ui>(blockidx) == CurrentBlock) 00064 { 00065 return; 00066 } 00067 DeleteBlock(blockidx); 00068 } 00069 return; 00070 } 00071 00072 c * Allocator::NewSpace(const ui size) 00073 { 00074 Block * block = Blocks[CurrentBlock]; 00075 //Not enough space in this block. Add new block and allocate from there 00076 if((block->Allocated - block->Used) < size) 00077 { 00078 NextBlock(size); 00079 return NewSpace(size); 00080 } 00081 //Pointer to allocated space 00082 c * out = block->Data + block->Used; 00083 //Update block data 00084 block->Used += size; 00085 ++block->PtrsGiven; 00086 return out; 00087 } 00088 00089 Allocator::~Allocator() 00090 { 00091 //Delete all blocks 00092 for(ui block = 0; block < NumBlocks; ++block) 00093 { 00094 delete Blocks[block]; 00095 } 00096 delete [] Blocks; 00097 } 00098 00099 void Allocator::NextBlock(const ui minsize) 00100 { 00101 ++CurrentBlock; 00102 //Size of the new block is max(minsize, BlockMinSize) 00103 if(minsize > BlockMinSize) 00104 { 00105 BlockMinSize = minsize; 00106 } 00107 //Not the last block, we have more allocated blocks so we just need to move 00108 //to the next one 00109 if(CurrentBlock < NumBlocks) 00110 { 00111 //If the block is not large enough, enlarge it 00112 if(Blocks[CurrentBlock]->GetRemainingSpace() < minsize) 00113 { 00114 Blocks[CurrentBlock]->Reallocate(BlockMinSize); 00115 } 00116 } 00117 //We need to allocate a new block (and reallocate the Blocks ptr array) 00118 else 00119 { 00120 NewBlock(); 00121 } 00122 } 00123 00124 void Allocator::NewBlock() 00125 { 00126 #ifdef MINIINI_BENCH_EXTRA 00127 #ifdef linux 00128 ld atimestart = GetTime(); 00129 #endif 00130 #endif 00131 Block * * tempblocks = new Block * [NumBlocks + 1]; 00132 memcpy(tempblocks, Blocks, NumBlocks * sizeof(Block *)); 00133 tempblocks[NumBlocks] = new Block(BlockMinSize); 00134 delete [] Blocks; 00135 Blocks = tempblocks; 00136 ++NumBlocks; 00137 #ifdef MINIINI_BENCH_EXTRA 00138 #ifdef linux 00139 bench_alloctime += GetTime() - atimestart; 00140 #endif 00141 #endif 00142 } 00143 00144 void Allocator::DeleteBlock(ui index) 00145 { 00146 MINIINI_ASSERT(index < NumBlocks, "Block index passed to " 00147 "Allocator::DeleteBlock() out of range"); 00148 Block * const block = Blocks[index]; 00149 NumBlocks -= 1; 00150 delete block; 00151 //This is the only block left, so delete it and replace by an empty block. 00152 if(!NumBlocks) 00153 { 00154 //delete block; 00155 NewBlock(); 00156 return; 00157 } 00158 00159 //Reallocate Blocks to smaller size 00160 Block * * tempblocks = new Block * [NumBlocks]; 00161 memcpy(tempblocks, Blocks, index * sizeof(Block *)); 00162 memcpy(tempblocks + index, Blocks + index + 1, 00163 (NumBlocks - index) * sizeof(Block *)); 00164 delete [] Blocks; 00165 Blocks = tempblocks; 00166 } 00167 00168 i Allocator::FindBlock(c * const ptr) 00169 { 00170 for(ui blockidx = 0; blockidx < NumBlocks; ++blockidx) 00171 { 00172 Block * block = Blocks[blockidx]; 00173 if(ptr >= block->Data && ptr < (block->Data + block->Allocated)) 00174 { 00175 return blockidx; 00176 } 00177 } 00178 return -1; 00179 } 00180 00181 }