1 /*
2 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
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 <Box2D/Common/b2BlockAllocator.h>
20 #include <cstdlib>
21 #include <climits>
22 #include <cstring>
23 #include <memory>
24 using namespace std;
25
26 int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] =
27 {
28 16, // 0
29 32, // 1
30 64, // 2
31 96, // 3
32 128, // 4
33 160, // 5
34 192, // 6
35 224, // 7
36 256, // 8
37 320, // 9
38 384, // 10
39 448, // 11
40 512, // 12
41 640, // 13
42 };
43 uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
44 bool b2BlockAllocator::s_blockSizeLookupInitialized;
45
46 struct b2Chunk
47 {
48 int32 blockSize;
49 b2Block* blocks;
50 };
51
52 struct b2Block
53 {
54 b2Block* next;
55 };
56
b2BlockAllocator()57 b2BlockAllocator::b2BlockAllocator()
58 {
59 b2Assert(b2_blockSizes < UCHAR_MAX);
60
61 m_chunkSpace = b2_chunkArrayIncrement;
62 m_chunkCount = 0;
63 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
64
65 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
66 memset(m_freeLists, 0, sizeof(m_freeLists));
67
68 if (s_blockSizeLookupInitialized == false)
69 {
70 int32 j = 0;
71 for (int32 i = 1; i <= b2_maxBlockSize; ++i)
72 {
73 b2Assert(j < b2_blockSizes);
74 if (i <= s_blockSizes[j])
75 {
76 s_blockSizeLookup[i] = (uint8)j;
77 }
78 else
79 {
80 ++j;
81 s_blockSizeLookup[i] = (uint8)j;
82 }
83 }
84
85 s_blockSizeLookupInitialized = true;
86 }
87 }
88
~b2BlockAllocator()89 b2BlockAllocator::~b2BlockAllocator()
90 {
91 for (int32 i = 0; i < m_chunkCount; ++i)
92 {
93 b2Free(m_chunks[i].blocks);
94 }
95
96 b2Free(m_chunks);
97 }
98
Allocate(int32 size)99 void* b2BlockAllocator::Allocate(int32 size)
100 {
101 if (size == 0)
102 return NULL;
103
104 b2Assert(0 < size);
105
106 if (size > b2_maxBlockSize)
107 {
108 return b2Alloc(size);
109 }
110
111 int32 index = s_blockSizeLookup[size];
112 b2Assert(0 <= index && index < b2_blockSizes);
113
114 if (m_freeLists[index])
115 {
116 b2Block* block = m_freeLists[index];
117 m_freeLists[index] = block->next;
118 return block;
119 }
120 else
121 {
122 if (m_chunkCount == m_chunkSpace)
123 {
124 b2Chunk* oldChunks = m_chunks;
125 m_chunkSpace += b2_chunkArrayIncrement;
126 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
127 memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
128 memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));
129 b2Free(oldChunks);
130 }
131
132 b2Chunk* chunk = m_chunks + m_chunkCount;
133 chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);
134 #if defined(_DEBUG)
135 memset(chunk->blocks, 0xcd, b2_chunkSize);
136 #endif
137 int32 blockSize = s_blockSizes[index];
138 chunk->blockSize = blockSize;
139 int32 blockCount = b2_chunkSize / blockSize;
140 b2Assert(blockCount * blockSize <= b2_chunkSize);
141 for (int32 i = 0; i < blockCount - 1; ++i)
142 {
143 b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);
144 b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));
145 block->next = next;
146 }
147 b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));
148 last->next = NULL;
149
150 m_freeLists[index] = chunk->blocks->next;
151 ++m_chunkCount;
152
153 return chunk->blocks;
154 }
155 }
156
Free(void * p,int32 size)157 void b2BlockAllocator::Free(void* p, int32 size)
158 {
159 if (size == 0)
160 {
161 return;
162 }
163
164 b2Assert(0 < size);
165
166 if (size > b2_maxBlockSize)
167 {
168 b2Free(p);
169 return;
170 }
171
172 int32 index = s_blockSizeLookup[size];
173 b2Assert(0 <= index && index < b2_blockSizes);
174
175 #ifdef _DEBUG
176 // Verify the memory address and size is valid.
177 int32 blockSize = s_blockSizes[index];
178 bool found = false;
179 for (int32 i = 0; i < m_chunkCount; ++i)
180 {
181 b2Chunk* chunk = m_chunks + i;
182 if (chunk->blockSize != blockSize)
183 {
184 b2Assert( (int8*)p + blockSize <= (int8*)chunk->blocks ||
185 (int8*)chunk->blocks + b2_chunkSize <= (int8*)p);
186 }
187 else
188 {
189 if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize)
190 {
191 found = true;
192 }
193 }
194 }
195
196 b2Assert(found);
197
198 memset(p, 0xfd, blockSize);
199 #endif
200
201 b2Block* block = (b2Block*)p;
202 block->next = m_freeLists[index];
203 m_freeLists[index] = block;
204 }
205
Clear()206 void b2BlockAllocator::Clear()
207 {
208 for (int32 i = 0; i < m_chunkCount; ++i)
209 {
210 b2Free(m_chunks[i].blocks);
211 }
212
213 m_chunkCount = 0;
214 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
215
216 memset(m_freeLists, 0, sizeof(m_freeLists));
217 }
218