b2BlockAllocator.cpp
Go to the documentation of this file.
00001 /*
00002 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
00003 *
00004 * This software is provided 'as-is', without any express or implied
00005 * warranty.  In no event will the authors be held liable for any damages
00006 * arising from the use of this software.
00007 * Permission is granted to anyone to use this software for any purpose,
00008 * including commercial applications, and to alter it and redistribute it
00009 * freely, subject to the following restrictions:
00010 * 1. The origin of this software must not be misrepresented; you must not
00011 * claim that you wrote the original software. If you use this software
00012 * in a product, an acknowledgment in the product documentation would be
00013 * appreciated but is not required.
00014 * 2. Altered source versions must be plainly marked as such, and must not be
00015 * misrepresented as being the original software.
00016 * 3. This notice may not be removed or altered from any source distribution.
00017 */
00018 
00019 #include <Box2D/Common/b2BlockAllocator.h>
00020 #include <limits.h>
00021 #include <string.h>
00022 #include <stddef.h>
00023 
00024 int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] = 
00025 {
00026         16,             // 0
00027         32,             // 1
00028         64,             // 2
00029         96,             // 3
00030         128,    // 4
00031         160,    // 5
00032         192,    // 6
00033         224,    // 7
00034         256,    // 8
00035         320,    // 9
00036         384,    // 10
00037         448,    // 11
00038         512,    // 12
00039         640,    // 13
00040 };
00041 uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
00042 bool b2BlockAllocator::s_blockSizeLookupInitialized;
00043 
00044 struct b2Chunk
00045 {
00046         int32 blockSize;
00047         b2Block* blocks;
00048 };
00049 
00050 struct b2Block
00051 {
00052         b2Block* next;
00053 };
00054 
00055 b2BlockAllocator::b2BlockAllocator()
00056 {
00057         b2Assert(b2_blockSizes < UCHAR_MAX);
00058 
00059         m_chunkSpace = b2_chunkArrayIncrement;
00060         m_chunkCount = 0;
00061         m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
00062         
00063         memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
00064         memset(m_freeLists, 0, sizeof(m_freeLists));
00065 
00066         if (s_blockSizeLookupInitialized == false)
00067         {
00068                 int32 j = 0;
00069                 for (int32 i = 1; i <= b2_maxBlockSize; ++i)
00070                 {
00071                         b2Assert(j < b2_blockSizes);
00072                         if (i <= s_blockSizes[j])
00073                         {
00074                                 s_blockSizeLookup[i] = (uint8)j;
00075                         }
00076                         else
00077                         {
00078                                 ++j;
00079                                 s_blockSizeLookup[i] = (uint8)j;
00080                         }
00081                 }
00082 
00083                 s_blockSizeLookupInitialized = true;
00084         }
00085 }
00086 
00087 b2BlockAllocator::~b2BlockAllocator()
00088 {
00089         for (int32 i = 0; i < m_chunkCount; ++i)
00090         {
00091                 b2Free(m_chunks[i].blocks);
00092         }
00093 
00094         b2Free(m_chunks);
00095 }
00096 
00097 void* b2BlockAllocator::Allocate(int32 size)
00098 {
00099         if (size == 0)
00100                 return NULL;
00101 
00102         b2Assert(0 < size);
00103 
00104         if (size > b2_maxBlockSize)
00105         {
00106                 return b2Alloc(size);
00107         }
00108 
00109         int32 index = s_blockSizeLookup[size];
00110         b2Assert(0 <= index && index < b2_blockSizes);
00111 
00112         if (m_freeLists[index])
00113         {
00114                 b2Block* block = m_freeLists[index];
00115                 m_freeLists[index] = block->next;
00116                 return block;
00117         }
00118         else
00119         {
00120                 if (m_chunkCount == m_chunkSpace)
00121                 {
00122                         b2Chunk* oldChunks = m_chunks;
00123                         m_chunkSpace += b2_chunkArrayIncrement;
00124                         m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
00125                         memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
00126                         memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));
00127                         b2Free(oldChunks);
00128                 }
00129 
00130                 b2Chunk* chunk = m_chunks + m_chunkCount;
00131                 chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);
00132 #if defined(_DEBUG)
00133                 memset(chunk->blocks, 0xcd, b2_chunkSize);
00134 #endif
00135                 int32 blockSize = s_blockSizes[index];
00136                 chunk->blockSize = blockSize;
00137                 int32 blockCount = b2_chunkSize / blockSize;
00138                 b2Assert(blockCount * blockSize <= b2_chunkSize);
00139                 for (int32 i = 0; i < blockCount - 1; ++i)
00140                 {
00141                         b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);
00142                         b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));
00143                         block->next = next;
00144                 }
00145                 b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));
00146                 last->next = NULL;
00147 
00148                 m_freeLists[index] = chunk->blocks->next;
00149                 ++m_chunkCount;
00150 
00151                 return chunk->blocks;
00152         }
00153 }
00154 
00155 void b2BlockAllocator::Free(void* p, int32 size)
00156 {
00157         if (size == 0)
00158         {
00159                 return;
00160         }
00161 
00162         b2Assert(0 < size);
00163 
00164         if (size > b2_maxBlockSize)
00165         {
00166                 b2Free(p);
00167                 return;
00168         }
00169 
00170         int32 index = s_blockSizeLookup[size];
00171         b2Assert(0 <= index && index < b2_blockSizes);
00172 
00173 #ifdef _DEBUG
00174         // Verify the memory address and size is valid.
00175         int32 blockSize = s_blockSizes[index];
00176         bool found = false;
00177         for (int32 i = 0; i < m_chunkCount; ++i)
00178         {
00179                 b2Chunk* chunk = m_chunks + i;
00180                 if (chunk->blockSize != blockSize)
00181                 {
00182                         b2Assert(       (int8*)p + blockSize <= (int8*)chunk->blocks ||
00183                                                 (int8*)chunk->blocks + b2_chunkSize <= (int8*)p);
00184                 }
00185                 else
00186                 {
00187                         if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize)
00188                         {
00189                                 found = true;
00190                         }
00191                 }
00192         }
00193 
00194         b2Assert(found);
00195 
00196         memset(p, 0xfd, blockSize);
00197 #endif
00198 
00199         b2Block* block = (b2Block*)p;
00200         block->next = m_freeLists[index];
00201         m_freeLists[index] = block;
00202 }
00203 
00204 void b2BlockAllocator::Clear()
00205 {
00206         for (int32 i = 0; i < m_chunkCount; ++i)
00207         {
00208                 b2Free(m_chunks[i].blocks);
00209         }
00210 
00211         m_chunkCount = 0;
00212         memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
00213 
00214         memset(m_freeLists, 0, sizeof(m_freeLists));
00215 }


mvsim
Author(s):
autogenerated on Thu Sep 7 2017 09:27:47