b2BlockAllocator.cpp
Go to the documentation of this file.
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 
20 #include <limits.h>
21 #include <string.h>
22 #include <stddef.h>
23 
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 };
43 
44 struct b2Chunk
45 {
48 };
49 
50 struct b2Block
51 {
53 };
54 
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  {
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 
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 
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 
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 
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 }
void BASE_IMPEXP memcpy(void *dest, size_t destSize, const void *src, size_t copyCount) MRPT_NO_THROWS
const int32 b2_maxBlockSize
void Free(void *p, int32 size)
Free memory. This will use b2Free if the size is larger than b2_maxBlockSize.
static int32 s_blockSizes[b2_blockSizes]
signed int int32
Definition: b2Settings.h:31
static uint8 s_blockSizeLookup[b2_maxBlockSize+1]
void * Allocate(int32 size)
Allocate memory. This will use b2Alloc if the size is larger than b2_maxBlockSize.
static bool s_blockSizeLookupInitialized
b2Block * next
GLfloat GLfloat p
GLsizeiptr size
signed char int8
Definition: b2Settings.h:29
unsigned char uint8
Definition: b2Settings.h:32
const int32 b2_chunkArrayIncrement
GLuint index
#define b2Assert(A)
Definition: b2Settings.h:27
const int32 b2_blockSizes
b2Block * blocks
void * b2Alloc(int32 size)
Implement this function to use your own memory allocator.
Definition: b2Settings.cpp:27
void b2Free(void *mem)
If you implement b2Alloc, you should also implement this function.
Definition: b2Settings.cpp:32
const int32 b2_chunkSize


mvsim
Author(s):
autogenerated on Fri May 7 2021 03:05:51