C++ Loki The Fixed Size Allocator














































C++ Loki The Fixed Size Allocator



The Fixed Size Allocator

In the Small Object Allocator hierarchy structure, the fixed size allocator lies in the second position just after chunk. Chunk could allocate only fixed size of memory based on the  size of unsigned character that is 255 bytes of memory. On the other hand, FixedAllocator doesn't limit allocation based on size of chunk. It conglomerates a vector of Chunk objects. The request received is passed on to chunk to allocate memory, if all chunk are filled, it appends a new chunk to the existing vector. The definition of FixedAllocator is given below:

class FixedAllocator
{
...
private:
std::size_t blockSize_;
unsigned char numBlocks_;
typedef std::vector<Chunk> Chunks;
Chunks chunks_;
Chunk* allocChunk_;
Chunk* deallocChunk_;
};

ALLOCATION

The allocChunk_ is a pointer which holds the position of the last chunk which was allocated. The request checks allocChunk_ for available space. If space is available the request is satisfied or else the chunk vector is updated by appending a new chunk to the vector. The time complexity of FixedAllocator is constant. The allocator function implements this logic which is defined below:

void* FixedAllocator::Allocate()
{
if (allocChunk_ == 0 ||
allocChunk_->blocksAvailable_ == 0)
{
// Memory unavailable in this chunk
// Try to find one
Chunks::iterator i = chunks_.begin();
for (;; ++i)
{
if (i == chunks_.end())
{
// Last chunk is too filled
// appending a new chunk to the vector
chunks_.reserve(chunks _.size()+1);
Chunk newChunk;
newChunk.Init(blockSize_, numBlocks_);
chunks_.push_back(newChunk);
allocChunk_ = &chunks_.back();
deallocChunk_ = &chunks_.back();
break;
}
if (i->blocksAvailable_ > 0)
{
// Found a chunk
allocChunk_ = &*i;
break;
}
}
}
assert(allocChunk_ != 0);
assert(allocChunk_->blocksAvailable_ > 0);
return allocChunk_->Allocate(blockSize_);
}

DEALLOCATION


One way of deallocation would be to check the pointer which is to be deallocated in the whole chunks_ vector i.e. from pData_ to pData_ + blockSize_ * numBlocks_. The time complexity would be linear in this case.
Another method would be to use the concept of memoization. A temporary memory which is also called cache memory is used to store the pointer. Let's say when FixedAllocator::Deallocate(p) is passed, p is stored in cache memory. When an allocation is to done, FixedAllocator::Allocate() checks for this memory and if it is non-empty, it returns p to allocate. If it is empty, allocate member function allocates generally by passing the request to chunk.

More Articles of Abhinav Verma:

Name Views Likes
C++ Loki Abstract Factory Implementation 255 1
C++ Loki SmallObject Compiler Working 152 1
C++ Loki SmallObject 180 1
C++ Loki Abstract Factory Interface 249 1
C++ Loki Double Dispatching 167 2
C++ Loki SmallObjAllocator 138 2
C++ Loki Abstract Factory 132 2
C++ Loki Small Objects Allocation Methods 144 1
C++ Loki The Fixed Size Allocator 203 1
C++ Loki Necessity of Multi-Methods 125 1
C++ Loki Chunks 132 1
C++ Loki Packing Order of Small Object Allocator 125 2
C++ Loki Multimethods Polymorphism 148 2
C++ Loki How does memory allocator works? 131 1
C++ Loki Default Storage Allocator 120 1
C++ Loki Multimethods 127 1
C++ Loki Small Object Allocator 118 1
C++ Loki Techniques Compile Time Affirmations 120 1
C++ Loki Typelist Linear Hierarchy 130 1
C++ Loki Techniques type_info 114 1
C++ Loki Traits Generating Tuples 121 1
C++ Loki Techniques Partial Template Specialization 127 1
C++ Loki Typelist Generating Scattered Hierarchy 123 1
C++ Loki Techniques Select 119 1
C++ Loki Clubbing TypeList 114 1
C++ Loki Techniques Traits 113 1
C++ Loki TypeList Substituting Elements 117 1
C++ Loki Techniques Local Classes 115 1
C++ Loki TypeList Deleting Duplicated 116 1
C++ Loki Techniques Introduction 119 1
C++ Loki Effacing type from typelist 118 1
C++ Loki Append TypeList 113 1
C++ Loki Mouldering Classes 117 1
C++ Loki Searching TypeList 121 1
C++ Loki Smart Pointer Compatibility of Policies 128 1
C++ Loki TypeList Indexed Access 121 1
C++ Loki Smart Pointer Structure Customization 118 1
C++ Loki Length of TypeList 123 1
C++ Loki Smart Pointer Threading Model and Checking Policy 118 1
C++ Loki Voluntary Functionality through Incomplete Initialization 113 1
C++ Loki Policy Class Destructor 128 1
C++ Loki Enriched Policies 115 1
C++ Loki Policy Classes with Template Template Parameter and Member functions 115 1
C++ Loki Kernel of Policy Classes 116 1
C++ Loki Templates in design 125 1
C++ Loki Do-it-All Interface & Multiple Inheritance 125 1
C++ Loki Policy Based Design 153 2
C++ Loki Introduction 144 2
C++ iomanip ends 124 1
C++ iomanip flush 130 2
C++ iomanip ws 162 2

Comments