Warning, file /education/gcompris/external/qml-box2d/Box2D/Common/b2BlockAllocator.cpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* 0002 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org 0003 * 0004 * This software is provided 'as-is', without any express or implied 0005 * warranty. In no event will the authors be held liable for any damages 0006 * arising from the use of this software. 0007 * Permission is granted to anyone to use this software for any purpose, 0008 * including commercial applications, and to alter it and redistribute it 0009 * freely, subject to the following restrictions: 0010 * 1. The origin of this software must not be misrepresented; you must not 0011 * claim that you wrote the original software. If you use this software 0012 * in a product, an acknowledgment in the product documentation would be 0013 * appreciated but is not required. 0014 * 2. Altered source versions must be plainly marked as such, and must not be 0015 * misrepresented as being the original software. 0016 * 3. This notice may not be removed or altered from any source distribution. 0017 */ 0018 0019 #include <Box2D/Common/b2BlockAllocator.h> 0020 #include <limits.h> 0021 #include <string.h> 0022 #include <stddef.h> 0023 0024 int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] = 0025 { 0026 16, // 0 0027 32, // 1 0028 64, // 2 0029 96, // 3 0030 128, // 4 0031 160, // 5 0032 192, // 6 0033 224, // 7 0034 256, // 8 0035 320, // 9 0036 384, // 10 0037 448, // 11 0038 512, // 12 0039 640, // 13 0040 }; 0041 uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1]; 0042 bool b2BlockAllocator::s_blockSizeLookupInitialized; 0043 0044 struct b2Chunk 0045 { 0046 int32 blockSize; 0047 b2Block* blocks; 0048 }; 0049 0050 struct b2Block 0051 { 0052 b2Block* next; 0053 }; 0054 0055 b2BlockAllocator::b2BlockAllocator() 0056 { 0057 b2Assert(b2_blockSizes < UCHAR_MAX); 0058 0059 m_chunkSpace = b2_chunkArrayIncrement; 0060 m_chunkCount = 0; 0061 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk)); 0062 0063 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk)); 0064 memset(m_freeLists, 0, sizeof(m_freeLists)); 0065 0066 if (s_blockSizeLookupInitialized == false) 0067 { 0068 int32 j = 0; 0069 for (int32 i = 1; i <= b2_maxBlockSize; ++i) 0070 { 0071 b2Assert(j < b2_blockSizes); 0072 if (i <= s_blockSizes[j]) 0073 { 0074 s_blockSizeLookup[i] = (uint8)j; 0075 } 0076 else 0077 { 0078 ++j; 0079 s_blockSizeLookup[i] = (uint8)j; 0080 } 0081 } 0082 0083 s_blockSizeLookupInitialized = true; 0084 } 0085 } 0086 0087 b2BlockAllocator::~b2BlockAllocator() 0088 { 0089 for (int32 i = 0; i < m_chunkCount; ++i) 0090 { 0091 b2Free(m_chunks[i].blocks); 0092 } 0093 0094 b2Free(m_chunks); 0095 } 0096 0097 void* b2BlockAllocator::Allocate(int32 size) 0098 { 0099 if (size == 0) 0100 return NULL; 0101 0102 b2Assert(0 < size); 0103 0104 if (size > b2_maxBlockSize) 0105 { 0106 return b2Alloc(size); 0107 } 0108 0109 int32 index = s_blockSizeLookup[size]; 0110 b2Assert(0 <= index && index < b2_blockSizes); 0111 0112 if (m_freeLists[index]) 0113 { 0114 b2Block* block = m_freeLists[index]; 0115 m_freeLists[index] = block->next; 0116 return block; 0117 } 0118 else 0119 { 0120 if (m_chunkCount == m_chunkSpace) 0121 { 0122 b2Chunk* oldChunks = m_chunks; 0123 m_chunkSpace += b2_chunkArrayIncrement; 0124 m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk)); 0125 memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk)); 0126 memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk)); 0127 b2Free(oldChunks); 0128 } 0129 0130 b2Chunk* chunk = m_chunks + m_chunkCount; 0131 chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize); 0132 #if defined(_DEBUG) 0133 memset(chunk->blocks, 0xcd, b2_chunkSize); 0134 #endif 0135 int32 blockSize = s_blockSizes[index]; 0136 chunk->blockSize = blockSize; 0137 int32 blockCount = b2_chunkSize / blockSize; 0138 b2Assert(blockCount * blockSize <= b2_chunkSize); 0139 for (int32 i = 0; i < blockCount - 1; ++i) 0140 { 0141 b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i); 0142 b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1)); 0143 block->next = next; 0144 } 0145 b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1)); 0146 last->next = NULL; 0147 0148 m_freeLists[index] = chunk->blocks->next; 0149 ++m_chunkCount; 0150 0151 return chunk->blocks; 0152 } 0153 } 0154 0155 void b2BlockAllocator::Free(void* p, int32 size) 0156 { 0157 if (size == 0) 0158 { 0159 return; 0160 } 0161 0162 b2Assert(0 < size); 0163 0164 if (size > b2_maxBlockSize) 0165 { 0166 b2Free(p); 0167 return; 0168 } 0169 0170 int32 index = s_blockSizeLookup[size]; 0171 b2Assert(0 <= index && index < b2_blockSizes); 0172 0173 #ifdef _DEBUG 0174 // Verify the memory address and size is valid. 0175 int32 blockSize = s_blockSizes[index]; 0176 bool found = false; 0177 for (int32 i = 0; i < m_chunkCount; ++i) 0178 { 0179 b2Chunk* chunk = m_chunks + i; 0180 if (chunk->blockSize != blockSize) 0181 { 0182 b2Assert( (int8*)p + blockSize <= (int8*)chunk->blocks || 0183 (int8*)chunk->blocks + b2_chunkSize <= (int8*)p); 0184 } 0185 else 0186 { 0187 if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize) 0188 { 0189 found = true; 0190 } 0191 } 0192 } 0193 0194 b2Assert(found); 0195 0196 memset(p, 0xfd, blockSize); 0197 #endif 0198 0199 b2Block* block = (b2Block*)p; 0200 block->next = m_freeLists[index]; 0201 m_freeLists[index] = block; 0202 } 0203 0204 void b2BlockAllocator::Clear() 0205 { 0206 for (int32 i = 0; i < m_chunkCount; ++i) 0207 { 0208 b2Free(m_chunks[i].blocks); 0209 } 0210 0211 m_chunkCount = 0; 0212 memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk)); 0213 0214 memset(m_freeLists, 0, sizeof(m_freeLists)); 0215 }