1 /*
2 * Copyright (c) 2006-2009 Erin Catto http://www.gphysics.com
3 *
4 * This software is provided 'as-is', without any express or implied
5 * warranty. In no event will the authors be held liable for any damages
6 * arising from the use of this software.
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 * 1. The origin of this software must not be misrepresented; you must not
11 * claim that you wrote the original software. If you use this software
12 * in a product, an acknowledgment in the product documentation would be
13 * appreciated but is not required.
14 * 2. Altered source versions must be plainly marked as such, and must not be
15 * misrepresented as being the original software.
16 * 3. This notice may not be removed or altered from any source distribution.
17 */
18
19 #include "b2BlockAllocator.h"
20 #include <cstdlib>
21 #include <climits>
22 #include <cstring>
23 #include <memory>
24
25 int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] =
26 {
27 16, // 0
28 32, // 1
29 64, // 2
30 96, // 3
31 128, // 4
32 160, // 5
33 192, // 6
34 224, // 7
35 256, // 8
36 320, // 9
37 384, // 10
38 448, // 11
39 512, // 12
40 640, // 13
41 };
42 uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
43 bool b2BlockAllocator::s_blockSizeLookupInitialized;
44
45 struct b2Chunk
46 {
47 int32 blockSize;
48 b2Block* blocks;
49 };
50
51 struct b2Block
52 {
53 b2Block* next;
54 };
55
b2BlockAllocator()56 b2BlockAllocator::b2BlockAllocator()
57 {
58 b2Assert(b2_blockSizes < UCHAR_MAX);
59
60 m_chunkSpace = b2_chunkArrayIncrement;
61 m_chunkCount = 0;
62 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
63
64 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
65 memset(m_freeLists, 0, sizeof(m_freeLists));
66
67 if (s_blockSizeLookupInitialized == false)
68 {
69 int32 j = 0;
70 for (int32 i = 1; i <= b2_maxBlockSize; ++i)
71 {
72 b2Assert(j < b2_blockSizes);
73 if (i <= s_blockSizes[j])
74 {
75 s_blockSizeLookup[i] = (uint8)j;
76 }
77 else
78 {
79 ++j;
80 s_blockSizeLookup[i] = (uint8)j;
81 }
82 }
83
84 s_blockSizeLookupInitialized = true;
85 }
86 }
87
~b2BlockAllocator()88 b2BlockAllocator::~b2BlockAllocator()
89 {
90 for (int32 i = 0; i < m_chunkCount; ++i)
91 {
92 b2Free(m_chunks[i].blocks);
93 }
94
95 b2Free(m_chunks);
96 }
97
Allocate(int32 size)98 void* b2BlockAllocator::Allocate(int32 size)
99 {
100 if (size == 0)
101 return NULL;
102
103 b2Assert(0 < size && size <= b2_maxBlockSize);
104
105 int32 index = s_blockSizeLookup[size];
106 b2Assert(0 <= index && index < b2_blockSizes);
107
108 if (m_freeLists[index])
109 {
110 b2Block* block = m_freeLists[index];
111 m_freeLists[index] = block->next;
112 return block;
113 }
114 else
115 {
116 if (m_chunkCount == m_chunkSpace)
117 {
118 b2Chunk* oldChunks = m_chunks;
119 m_chunkSpace += b2_chunkArrayIncrement;
120 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
121 memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
122 memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));
123 b2Free(oldChunks);
124 }
125
126 b2Chunk* chunk = m_chunks + m_chunkCount;
127 chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);
128 #if defined(_DEBUG)
129 memset(chunk->blocks, 0xcd, b2_chunkSize);
130 #endif
131 int32 blockSize = s_blockSizes[index];
132 chunk->blockSize = blockSize;
133 int32 blockCount = b2_chunkSize / blockSize;
134 b2Assert(blockCount * blockSize <= b2_chunkSize);
135 for (int32 i = 0; i < blockCount - 1; ++i)
136 {
137 b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);
138 b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));
139 block->next = next;
140 }
141 b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));
142 last->next = NULL;
143
144 m_freeLists[index] = chunk->blocks->next;
145 ++m_chunkCount;
146
147 return chunk->blocks;
148 }
149 }
150
Free(void * p,int32 size)151 void b2BlockAllocator::Free(void* p, int32 size)
152 {
153 if (size == 0)
154 {
155 return;
156 }
157
158 b2Assert(0 < size && size <= b2_maxBlockSize);
159
160 int32 index = s_blockSizeLookup[size];
161 b2Assert(0 <= index && index < b2_blockSizes);
162
163 #ifdef _DEBUG
164 // Verify the memory address and size is valid.
165 int32 blockSize = s_blockSizes[index];
166 bool found = false;
167 for (int32 i = 0; i < m_chunkCount; ++i)
168 {
169 b2Chunk* chunk = m_chunks + i;
170 if (chunk->blockSize != blockSize)
171 {
172 b2Assert( (int8*)p + blockSize <= (int8*)chunk->blocks ||
173 (int8*)chunk->blocks + b2_chunkSize <= (int8*)p);
174 }
175 else
176 {
177 if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize)
178 {
179 found = true;
180 }
181 }
182 }
183
184 b2Assert(found);
185
186 memset(p, 0xfd, blockSize);
187 #endif
188
189 b2Block* block = (b2Block*)p;
190 block->next = m_freeLists[index];
191 m_freeLists[index] = block;
192 }
193
Clear()194 void b2BlockAllocator::Clear()
195 {
196 for (int32 i = 0; i < m_chunkCount; ++i)
197 {
198 b2Free(m_chunks[i].blocks);
199 }
200
201 m_chunkCount = 0;
202 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
203
204 memset(m_freeLists, 0, sizeof(m_freeLists));
205 }
206