git.maemo.org Git - blok/blob - Box2D/Source/Common/b2BlockAllocator.cpp

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