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