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#include <cstring>
24
25int32 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};
42uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
43bool b2BlockAllocator::s_blockSizeLookupInitialized;
44
45struct b2Chunk
46{
47 int32 blockSize;
48 b2Block* blocks;
49};
50
51struct b2Block
52{
53 b2Block* next;
54};
55
56b2BlockAllocator::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
88b2BlockAllocator::~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
98void* b2BlockAllocator::Allocate(int32 size)
99{
100 if (size == 0)
101 return NULL;
102
103 b2Assert(0 < size);
104
105 if (size > b2_maxBlockSize)
106 {
107 return b2Alloc(size);
108 }
109
110 int32 index = s_blockSizeLookup[size];
111 b2Assert(0 <= index && index < b2_blockSizes);
112
113 if (m_freeLists[index])
114 {
115 b2Block* block = m_freeLists[index];
116 m_freeLists[index] = block->next;
117 return block;
118 }
119 else
120 {
121 if (m_chunkCount == m_chunkSpace)
122 {
123 b2Chunk* oldChunks = m_chunks;
124 m_chunkSpace += b2_chunkArrayIncrement;
125 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
126 memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
127 memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));
128 b2Free(oldChunks);
129 }
130
131 b2Chunk* chunk = m_chunks + m_chunkCount;
132 chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);
133#if defined(_DEBUG)
134 memset(chunk->blocks, 0xcd, b2_chunkSize);
135#endif
136 int32 blockSize = s_blockSizes[index];
137 chunk->blockSize = blockSize;
138 int32 blockCount = b2_chunkSize / blockSize;
139 b2Assert(blockCount * blockSize <= b2_chunkSize);
140 for (int32 i = 0; i < blockCount - 1; ++i)
141 {
142 b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);
143 b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));
144 block->next = next;
145 }
146 b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));
147 last->next = NULL;
148
149 m_freeLists[index] = chunk->blocks->next;
150 ++m_chunkCount;
151
152 return chunk->blocks;
153 }
154}
155
156void b2BlockAllocator::Free(void* p, int32 size)
157{
158 if (size == 0)
159 {
160 return;
161 }
162
163 b2Assert(0 < size);
164
165 if (size > b2_maxBlockSize)
166 {
167 b2Free(p);
168 return;
169 }
170
171 int32 index = s_blockSizeLookup[size];
172 b2Assert(0 <= index && index < b2_blockSizes);
173
174#ifdef _DEBUG
175 // Verify the memory address and size is valid.
176 int32 blockSize = s_blockSizes[index];
177 bool found = false;
178 for (int32 i = 0; i < m_chunkCount; ++i)
179 {
180 b2Chunk* chunk = m_chunks + i;
181 if (chunk->blockSize != blockSize)
182 {
183 b2Assert( (int8*)p + blockSize <= (int8*)chunk->blocks ||
184 (int8*)chunk->blocks + b2_chunkSize <= (int8*)p);
185 }
186 else
187 {
188 if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize)
189 {
190 found = true;
191 }
192 }
193 }
194
195 b2Assert(found);
196
197 memset(p, 0xfd, blockSize);
198#endif
199
200 b2Block* block = (b2Block*)p;
201 block->next = m_freeLists[index];
202 m_freeLists[index] = block;
203}
204
205void b2BlockAllocator::Clear()
206{
207 for (int32 i = 0; i < m_chunkCount; ++i)
208 {
209 b2Free(m_chunks[i].blocks);
210 }
211
212 m_chunkCount = 0;
213 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
214
215 memset(m_freeLists, 0, sizeof(m_freeLists));
216}
217