aGrUM  0.13.2
fixedAllocator_inl.h
Go to the documentation of this file.
1 
2 /***************************************************************************
3  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
4  * {prenom.nom}_at_lip6.fr *
5  * *
6  * This program is free software; you can redistribute it and/or modify *
7  * it under the terms of the GNU General Public License as published by *
8  * the Free Software Foundation; either version 2 of the License, or *
9  * (at your option) any later version. *
10  * *
11  * This program is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14  * GNU General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU General Public License *
17  * along with this program; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
20  ***************************************************************************/
28 // ============================================================================
30 // ============================================================================
31 
32 namespace gum {
33 
34  // ============================================================================
35  // Initializes a Chunk object
36  // ============================================================================
37  INLINE void FixedAllocator::__Chunk::__init(const std::size_t& blockSize,
38  const unsigned char& numBlocks) {
39  // Chunk memory space allocation. A chunk allocates a memory of blockSize *
40  // numBlocks size.
41  // The chunk will then give us numBlocks distinct blocks of blockSize from
42  // that space.
43  __pData = new unsigned char[blockSize * numBlocks];
44 
45  // The first available block of memory is logically at the beginning.
47 
48  // The number of block still available is all the blocks at the beginning.
49  __blocksAvailable = numBlocks;
50 
51  // For each unallocated block, the first byte contains a number.
52  // That number is the index of the next available block
53  // Since we're at the beginning, next free block is the next one simply.
54  // Following code initiate those number for each block
55  unsigned char* p = __pData;
56  for (unsigned char indexBlock = 0; indexBlock != numBlocks; p += blockSize)
57  *p = ++indexBlock;
58  }
59 
60  // ============================================================================
61  // Allocates a block of memory
62  // ============================================================================
63  INLINE void* FixedAllocator::__Chunk::__allocate(const std::size_t& blockSize) {
64  if (!__blocksAvailable)
65  // If no block is available return nullptr
66  return NULL;
67 
68  // __pData points to the beginning of allocated space.
69  // __firstAvailableBlock gives us how many block to pass before getting
70  // the good one. We have to multiply by blockSize to get the good memory
71  // emplacement
72  unsigned char* pResult = __pData + (__firstAvailableBlock * blockSize);
73 
74  // Remember that the first byte of each block gives us the index of next
75  // available slot.
76  // The new first availble block will be at the index indicating in this
77  // block.
78  __firstAvailableBlock = *pResult;
79 
80  // We lose one block
82 
83  return pResult;
84  }
85 
86  // ============================================================================
87  // Deallocates a block of memory
88  // ============================================================================
89  INLINE void FixedAllocator::__Chunk::__deallocat(void* pDeallocatedBlock,
90  const std::size_t& blockSize) {
91  // first, ensure that deallocated is in this chunk
92  assert(pDeallocatedBlock >= __pData);
93 
94  // Conversion pf pointer for handling
95  unsigned char* toRelease = static_cast< unsigned char* >(pDeallocatedBlock);
96 
97  // Alignement check
98  assert((toRelease - __pData) % blockSize == 0);
99 
100  // First byte of toRelease has now to give the index of current first
101  // available block
102  *toRelease = __firstAvailableBlock;
103 
104  // So that first available block points to it
106  static_cast< unsigned char >((toRelease - __pData) / blockSize);
107 
108  // Truncation check
109  assert(__firstAvailableBlock == (toRelease - __pData) / blockSize);
110 
111  // We gain one block, yeah
113  }
114 
115  // ============================================================================
116  // Releases the allocated memory
117  // ============================================================================
118  INLINE void FixedAllocator::__Chunk::__release() { delete[] __pData; }
119 
120 
121  // ############################################################################
122  // @name Constructors / Destructors
123  // ############################################################################
124 
125  // ============================================================================
126  // Constructor.
127  // ============================================================================
128  INLINE FixedAllocator::FixedAllocator(const std::size_t& blockSize,
129  const unsigned char& numBlocks) {
130  // GUM_CONSTRUCTOR(FixedAllocator)
131  __blockSize = blockSize;
132  __numBlocks = numBlocks;
133  __allocChunk = __chunks.begin();
134  __deallocChunk = __chunks.begin();
135  }
136 
137  // ============================================================================
138  // Destructor.
139  // ============================================================================
141  for (__Chunks::iterator chunkIter = __chunks.begin();
142  chunkIter != __chunks.end();
143  ++chunkIter)
144  chunkIter->__release();
145  // GUM_DESTRUCTOR(FixedAllocator)
146  }
147 
148  // ############################################################################
149  // @name Allocator / Deallocator
150  // ############################################################################
151 
152  // ============================================================================
153  // Allocates a block
154  // ============================================================================
155  INLINE void* FixedAllocator::allocate() {
156  if (__chunks.empty() || __allocChunk->__blocksAvailable == 0) {
157  // no available memory in this chunk
158  // Try to find one with memory available
159  for (__Chunks::iterator chunksIter = __chunks.begin();; ++chunksIter) {
160  if (chunksIter == __chunks.end()) {
161  // All chunks are filled up. Adding a new one
162  __chunks.reserve(__chunks.size() + 1);
163  __Chunk newChunk;
164  newChunk.__init(__blockSize, __numBlocks);
165  __chunks.push_back(newChunk);
166  __allocChunk = __chunks.end();
167  --__allocChunk;
169  break;
170  }
171  if (chunksIter->__blocksAvailable > 0) {
172  // Found a chunk
173  __allocChunk = chunksIter;
174  break;
175  }
176  }
177  }
178  return __allocChunk->__allocate(__blockSize);
179  }
180 
181  // ============================================================================
182  // Deallocates a block
183  // ============================================================================
184  INLINE void FixedAllocator::deallocate(void* pDeallocatedBlock) {
185  if (__deallocChunk->__pData > pDeallocatedBlock
186  || pDeallocatedBlock
187  > (__deallocChunk->__pData + (__numBlocks * __blockSize))) {
188  // If not things get ugly
189  // We have to find where the Chunk containing this pointer is
190  std::ptrdiff_t offset = 0;
191 
192  // We perform a bidirectionnal search from __deallocChunk
193  while (true) {
194  ++offset;
195  // First we look for the one going to the end of the vector
196  if ((__deallocChunk + offset) < __chunks.end()) {
197  if ((__deallocChunk + offset)->__pData <= pDeallocatedBlock
198  && pDeallocatedBlock < ((__deallocChunk + offset)->__pData
199  + (__numBlocks * __blockSize))) {
200  // If pointed chunk contains this pointer, deallocation find the
201  // place
202  __deallocChunk = (__deallocChunk + offset);
203  break;
204  }
205  }
206 
207  // Then we look for the one going to the beginning of the vector
208  if ((__deallocChunk - offset) >= __chunks.begin()) {
209  if ((__deallocChunk - offset)->__pData <= pDeallocatedBlock
210  && pDeallocatedBlock < ((__deallocChunk - offset)->__pData
211  + (__numBlocks * __blockSize))) {
212  // If pointed chunk contains this pointer, deallocation find the
213  // place
214  __deallocChunk = (__deallocChunk - offset);
215  break;
216  }
217  }
218  }
219  }
220  __deallocChunk->__deallocat(pDeallocatedBlock, __blockSize);
221  }
222 
223 } // namespace gum
void * allocate()
Allocates a block.
void deallocate(void *pDeallocatedBlock)
Deallocates a block.
unsigned char __blocksAvailable
Number of blocks available in this chunck.
FixedAllocator(const std::size_t &blockSize, const unsigned char &numBlocks=UCHAR_MAX)
Constructor.
__Chunks::iterator __allocChunk
Last Chunk used for an allocation.
Allocates objects of one given size.
void __deallocat(void *p, const std::size_t &blockSize)
Deallocates a block of memory.
std::size_t __blockSize
Size of a memory block allocated.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
unsigned char __numBlocks
The maximum number of blocks a chunk can allocate.
void * __allocate(const std::size_t &blockSize)
Allocates a block of memory.
unsigned char * __pData
Pointer to the managed memory itself.
__Chunks::iterator __deallocChunk
Last Chunk used for a deallocation.
unsigned char __firstAvailableBlock
Holds the index of the first block available in this chunck.
~FixedAllocator()
Destructor.
void __init(const std::size_t &blockSize, const unsigned char &numBlocks)
Initializes a Chunk object.
Headers of gum::FixedAllocator.
void __release()
Releases the allocated memory.