1
#ifndef __ALLOCATOR_H__
2
#define __ALLOCATOR_H__
4
// This file (C) 2004-2009 Steven Boswell. All rights reserved.
5
// Released to the public under the GNU General Public License v2.
6
// See the file COPYING for more information.
9
#include "mjpeg_types.h"
13
// An allocator for small classes. It gets large chunks from the
14
// standard memory allocator & divides it up. It's able to handle
15
// several different object sizes at once.
16
template <size_t SIZES>
20
Allocator (size_t a_nChunkSize);
21
// Constructor. Specify the number of bytes to allocate at a
22
// time from the standard memory allocator.
27
void *Allocate (size_t a_nSize, size_t a_nBytes);
28
// Allocate memory for another object.
29
// Use the given size-bucket, which must be for the given number
31
// Returns NULL if memory is exhausted.
33
void Deallocate (size_t a_nSize, size_t a_nBytes, void *a_pMemory);
34
// Deallocate previously-allocated memory.
36
uint32_t GetNumAllocated (void) const { return m_ulAllocated; }
37
// Get the number of allocated blocks.
40
// One chunk of memory.
45
// The next allocated chunk.
47
// The memory to divide up.
51
// The size of allocated chunks. Set by the constructor.
54
// A linked-list of all the allocated chunks.
57
// The next piece of unallocated memory in the
58
// most-recently-allocated chunk.
60
void *m_apFree[SIZES];
61
// Linked lists of freed pieces of memory, for all the sizes we
64
uint32_t m_ulAllocated;
65
// The number of live allocations, i.e. those that haven't been
69
size_t m_aiSizes[SIZES];
71
// The size of the pieces of memory in each bucket.
72
// Used to make sure they always ask for the same memory size
76
// Free up all chunks.
77
// Only safe if there are no live allocations.
82
// Constructor. Specify the number of bytes to allocate at a
83
// time from the standard memory allocator.
84
template <size_t SIZES>
85
Allocator<SIZES>::Allocator (size_t a_nChunkSize)
86
: m_pChunks (NULL), m_pFreeChunk (NULL)
88
// Round our chunk size up to the nearest pointer size.
89
m_nChunkSize = ((a_nChunkSize + sizeof (Chunk *) - 1)
90
/ sizeof (Chunk *)) * sizeof (Chunk *);
92
// All our buckets are empty.
93
for (size_t i = 0; i < SIZES; ++i)
97
// (We don't know the memory-size of each bucket yet.)
99
m_aiSizes[i] = Limits<size_t>::Max;
103
// No allocations yet.
110
template <size_t SIZES>
111
Allocator<SIZES>::~Allocator()
113
// If all allocated objects were deallocated, go ahead and free
114
// up our memory. (If there are any allocated objects left, then
115
// generally, that means this is a global allocator, and since C++
116
// doesn't guarantee order of destruction for global objects, we
117
// have no guarantee our clients have been destroyed, and so it
118
// isn't safe to delete our memory.)
119
if (m_ulAllocated == 0UL)
125
// Allocate memory for another object.
126
// Use the given size-bucket, which must be for the given number
128
// Returns NULL if memory is exhausted.
129
template <size_t SIZES>
131
Allocator<SIZES>::Allocate (size_t a_nSize, size_t a_nBytes)
134
// The memory we allocate.
136
// Make sure they gave us a valid size.
137
assert (a_nSize >= 0 && a_nSize < SIZES);
139
// Make sure they gave us a valid number of bytes.
140
assert (a_nBytes >= 0);
142
// Round the number of bytes up to the nearest pointer size.
143
a_nBytes = ((a_nBytes + sizeof (Chunk *) - 1)
144
/ sizeof (Chunk *)) * sizeof (Chunk *);
146
// Make sure the requested size fits within our chunk size.
147
assert (a_nBytes <= m_nChunkSize - sizeof (Chunk *));
149
// If we don't know the size of this bucket, we do now.
151
if (m_aiSizes[a_nSize] == Limits<size_t>::Max)
152
m_aiSizes[a_nSize] = a_nBytes;
155
// Make sure they ask for the same number of bytes each time.
156
assert (m_aiSizes[a_nSize] == a_nBytes);
158
// If there's a free piece of memory of this size, return it.
159
if (m_apFree[a_nSize] != NULL)
161
// Remember the allocated memory.
162
pAlloc = m_apFree[a_nSize];
164
// Remove it from our list.
165
m_apFree[a_nSize] = *(void **)m_apFree[a_nSize];
167
// That's one more allocation.
170
// Return the allocated memory.
174
// If there's enough unallocated space in the current chunk,
176
if (m_pFreeChunk != NULL
177
&& size_t (m_pFreeChunk - ((char *)m_pChunks))
178
<= m_nChunkSize - a_nBytes)
180
// Remember the allocated memory.
181
pAlloc = (void *) m_pFreeChunk;
183
// Move past this new allocated memory.
184
m_pFreeChunk += a_nBytes;
186
// That's one more allocation.
189
// Return the allocated memory.
193
// We'll have to create a new chunk in order to satisfy this
194
// allocation request.
196
// First, find a place for the rest of this chunk.
198
// (Not currently possible, unless we make m_aiSizes[] a non-debug
201
// Add a new chunk to our list.
203
// Allocate a new chunk.
204
Chunk *pNewChunk = (Chunk *) malloc (m_nChunkSize);
205
if (pNewChunk == NULL)
208
// Hook it into our list.
209
pNewChunk->m_pNext = m_pChunks;
210
m_pChunks = pNewChunk;
213
// The unallocated portion of the new chunk is here.
214
m_pFreeChunk = m_pChunks->m_aSpace + a_nBytes;
216
// That's one more allocation.
219
// Return the allocated memory.
220
return (void *) (&(m_pChunks->m_aSpace));
225
// Deallocate previously-allocated memory.
226
template <size_t SIZES>
228
Allocator<SIZES>::Deallocate (size_t a_nSize, size_t /* a_nBytes */,
231
// Make sure they gave us a valid size.
232
assert (a_nSize >= 0 && a_nSize < SIZES);
234
// Put this memory into the given bucket.
235
*(void **)a_pMemory = m_apFree[a_nSize];
236
m_apFree[a_nSize] = a_pMemory;
238
// That's one less allocation.
241
// If all memory is unallocated, free up our chunks & start over.
242
if (m_ulAllocated == 0UL)
248
// Free up all chunks.
249
template <size_t SIZES>
251
Allocator<SIZES>::Purge (void)
253
// Make sure there are no live allocations
254
assert (m_ulAllocated == 0UL);
256
// Empty the free-space list.
257
for (size_t i = 0; i < SIZES; ++i)
261
// Free all allocated chunks.
262
while (m_pChunks != NULL)
264
// Remember the next chunk.
265
Chunk *pNextChunk = m_pChunks->m_pNext;
270
// Move to the next chunk.
271
m_pChunks = pNextChunk;
277
#endif // __ALLOCATOR_H__