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