include/lang/PowerOfTwoAllocPool.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20
  21 // Implements a power of two size class allocator.
  22 // There is no consolidation of free space. Once a chunk is allocated it
  23 // remains at that size from then on whether free or allocated.
  24 // It uses AdvancingAllocPool as its parent allocator.
  25 // It is very fast. This is used to allocate Unit output buffers.
  26
  27 #ifndef _PowerOfTwoAllocPool_
  28 #define _PowerOfTwoAllocPool_
  29
  30 #include <stdexcept>
  31 #include <stdlib.h>
  32 #include "clz.h"
  33 #include "AdvancingAllocPool.h"
  34 #include "SC_AllocPool.h"
  35 void post(const char *fmt, ...);
  36 void postbuf(const char *fmt, ...);
  37
  38 template<class Hdr, class Obj, class Elem, int LargeObjSizeClass, int Align>
  39 class PowerOfTwoAllocPool
  40 {
  41 public:
  42         PowerOfTwoAllocPool(::AllocPool *inPool,
  43                 size_t initSize = 64*1024,
  44                 size_t growSize = 64*1024
  45         )
  46                 {
  47                         mLargeObjPool = inPool;
  48                         mNumLargeObjects = 0;
  49                         mNumAlloc = 0;
  50                         mNumFree = 0;
  51                         size_t tooBigSize = (sizeof(Hdr) + (sizeof(Elem) << (LargeObjSizeClass-1))) + 1;
  52                         mSmallObjPool.Init(inPool, initSize, growSize, tooBigSize);
  53                         Init();
  54                         //assert(SanityCheck());
  55                 }
  56         ~PowerOfTwoAllocPool()
  57                 {
  58                         //assert(SanityCheck());
  59                         //assert(mNumLargeObjects == 0); // you have to free the big ones yourself
  60                         mSmallObjPool.FreeAll();
  61                 }
  62
  63         Obj* Alloc(int32 inNumElems)
  64                 {
  65                         //mNumAlloc++;
  66                         //assert(SanityCheck());
  67                         int sizeclass = LOG2CEIL(inNumElems);
  68                         if (sizeclass >= LargeObjSizeClass) {
  69                                 mNumLargeObjects++;
  70                                 size_t size = sizeof(Hdr) + (sizeof(Elem) * inNumElems);
  71                                 return (Obj*)mLargeObjPool->Alloc(size);
  72                         }
  73
  74                         // get from free list
  75                         Obj* obj = mFreeLists[sizeclass];
  76                         if (obj != NULL) {
  77                                 // set free list to next element.
  78                                 mFreeLists[sizeclass] = *(Obj**)obj;
  79                         } else {
  80                                 // have to allocate it
  81                                 size_t size = mSizes[sizeclass];
  82                                 obj = (Obj*)mSmallObjPool.Alloc(size);
  83                                 if (!obj) throw runtime_error("PowerOfTwoAllocPool out of memory");
  84                         }
  85                         //obj->mMagic = 'magk';
  86                         //assert(SanityCheck());
  87                         return obj;
  88                 }
  89         void Free(Obj* inObjPtr)
  90                 {
  91                         //mNumFree++;
  92                         //assert(SanityCheck());
  93                         if (inObjPtr == 0) return;                   /* free(0) has no effect */
  94                         /*if (inObjPtr->mMagic != 'magk') {
  95                                 postbuf("bad object\n");
  96                                 throw runtime_error("bad object");
  97                         }*/
  98                         int sizeclass = inObjPtr->SizeClass();
  99                         if (sizeclass >= LargeObjSizeClass) {
 100                                 mLargeObjPool->Free(inObjPtr);
 101                                 mNumLargeObjects--;
 102                         } else {
 103                                 Obj* nextfree = mFreeLists[sizeclass];
 104                                 mFreeLists[sizeclass] = inObjPtr;
 105                                 *(Obj**)inObjPtr = nextfree;
 106                         }
 107                         //assert(SanityCheck());
 108                 }
 109         void FreeAll()
 110                 {
 111                         //assert(mNumLargeObjects == 0); // you have to free the big ones yourself
 112                         mSmallObjPool.FreeAll();
 113                         Init();
 114                 }
 115
 116         bool SanityCheck()
 117                 {
 118                         //postbuf("PowerOfTwoAllocPool::SanityCheck %d %d\n", mNumAlloc, mNumFree);
 119                         mLargeObjPool->DoCheckPool();
 120                         mSmallObjPool.SanityCheck();
 121                         for (int i=0; i<LargeObjSizeClass; ++i) {
 122                                 Obj* obj = mFreeLists[i];
 123                                 for (int j=0; obj; ++j) {
 124                                         if (j>=1000) {
 125                                                 post("linked loop??\n");
 126                                                 throw runtime_error("linked loop??\n");
 127                                                 return false;
 128                                         }
 129                                         obj = *(Obj**)obj;
 130                                 }
 131                         }
 132                         return true;
 133                 }
 134 private:
 135         void Init()
 136                 {
 137                         for (int i=0; i<LargeObjSizeClass; ++i) {
 138                                 mFreeLists[i] = NULL;
 139                                 size_t size = sizeof(Hdr) + (sizeof(Elem) << i);
 140                                 mSizes[i] = (size + (Align-1)) & ~(Align-1); // alignment
 141                         }
 142                 }
 143
 144         Obj* mFreeLists[LargeObjSizeClass];
 145         size_t mSizes[LargeObjSizeClass];
 146         AllocPool* mLargeObjPool;
 147         AdvancingAllocPool mSmallObjPool;
 148         int mNumLargeObjects;
 149         int mNumAlloc, mNumFree;
 150 };
 151
 152
 153 #endif
 154