CrystalSpace

Public API Reference

Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

blockallocator.h

Go to the documentation of this file.
00001 /*
00002   Crystal Space Generic Memory Block Allocator
00003   Copyright (C) 2003 by Jorrit Tyberghein
00004 
00005   This library is free software; you can redistribute it and/or
00006   modify it under the terms of the GNU Library General Public
00007   License as published by the Free Software Foundation; either
00008   version 2 of the License, or (at your option) any later version.
00009 
00010   This library is distributed in the hope that it will be useful,
00011   but WITHOUT ANY WARRANTY; without even the implied warranty of
00012   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013   Library General Public License for more details.
00014 
00015   You should have received a copy of the GNU Library General Public
00016   License along with this library; if not, write to the Free
00017   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 #ifndef __CSUTIL_BLKALLOC_H__
00020 #define __CSUTIL_BLKALLOC_H__
00021 
00026 #include "csextern.h"
00027 #include "array.h"
00028 
00029 // hack: work around problems caused by #defining 'new'
00030 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00031 # undef new
00032 #endif
00033 #include <new>
00034 
00035 #ifdef CS_MEMORY_TRACKER
00036 #include "csutil/memdebug.h"
00037 #include <typeinfo>
00038 #endif
00039 
00056 template <class T>
00057 class csBlockAllocator
00058 {
00059 private:
00060   // A dummy structure for a linked list of free items.
00061   struct csFreeList
00062   {
00063     csFreeList* next;
00064     size_t numfree;             // Free elements in this block.
00065   };
00066 
00067   // A memory block (a series of 'size' objects).
00068   struct csBlock
00069   {
00070     void* memory;
00071     csFreeList* firstfree;      // Linked list of free items in this block.
00072     csBlock () : memory (0), firstfree (0) {}
00073     ~csBlock ()
00074     {
00075       if (memory)
00076       {
00077 #       ifdef CS_MEMORY_TRACKER
00078         int32* ptr = ((int32*)memory)-2;
00079         mtiRegisterFree ((MemTrackerInfo*)*ptr, (size_t)ptr[1]);
00080         free (ptr);
00081 #       else
00082         free (memory);
00083 #       endif
00084       }
00085     }
00086   };
00087 
00088   csArray<csBlock> blocks;
00089   size_t size;                  // Number of elements per block.
00090   size_t elsize;                // Element size (bigger than 8).
00091   size_t blocksize;             // Size in bytes per block.
00092 
00093   // First block that contains a free element.
00094   size_t firstfreeblock;
00095 
00099   size_t FindBlock (void* m)
00100   {
00101     size_t i;
00102     for (i = 0 ; i < blocks.Length () ; i++)
00103     {
00104       csBlock* b = &blocks[i];
00105       if (b->memory <= m)
00106       {
00107         char* eb = ((char*)b->memory) + blocksize;
00108         if (((char*)m) < eb)
00109           return i;
00110       }
00111     }
00112     return (size_t)-1;
00113   }
00114 
00119   void FindAndUpdateFreeBlock ()
00120   {
00121     CS_ASSERT (blocks.Length() != 0);
00122     ++firstfreeblock;
00123     while (firstfreeblock < blocks.Length ()
00124                 && blocks[firstfreeblock].firstfree == 0)
00125       ++firstfreeblock;
00126 
00127     if (firstfreeblock == blocks.Length ())
00128     {
00129       firstfreeblock = blocks.Push (csBlock ());
00130       csBlock& bl = blocks[firstfreeblock];
00131 #     ifdef CS_MEMORY_TRACKER
00132       char buf[255];
00133       sprintf (buf, "csBlockAllocator<%s>", typeid (T).name());
00134       int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2);
00135       *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf);
00136       *ptr++ = blocksize;
00137       bl.memory = (void*)ptr;
00138 #     else
00139       bl.memory = (void*)malloc (blocksize);
00140 #     endif
00141       bl.firstfree = (csFreeList*)bl.memory;
00142       bl.firstfree->next = 0;
00143       bl.firstfree->numfree = size;
00144     }
00145   }
00146 
00147 public:
00153   csBlockAllocator (size_t s)
00154   {
00155     size = s;
00156     elsize = sizeof (T);
00157     if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList);
00158     blocksize = elsize * size;
00159 
00160     size_t idx = blocks.Push (csBlock ());
00161     csBlock& bl = blocks[idx];
00162 #   ifdef CS_MEMORY_TRACKER
00163     char buf[255];
00164     sprintf (buf, "csBlockAllocator<%s>", typeid (T).name());
00165     int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2);
00166     *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf);
00167     *ptr++ = blocksize;
00168     bl.memory = (void*)ptr;
00169 #   else
00170     bl.memory = (void*)malloc (blocksize);
00171 #endif
00172     bl.firstfree = (csFreeList*)bl.memory;
00173     bl.firstfree->next = 0;
00174     bl.firstfree->numfree = size;
00175 
00176     firstfreeblock = 0;
00177   }
00178 
00185   ~csBlockAllocator ()
00186   {
00187 #ifdef CS_DEBUG
00188     CS_ASSERT (firstfreeblock == 0);
00189     size_t i;
00190     for (i = 0 ; i < blocks.Length () ; i++)
00191     {
00192       CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory);
00193       CS_ASSERT (blocks[i].firstfree->next == 0);
00194       CS_ASSERT (blocks[i].firstfree->numfree == size);
00195     }
00196 #endif
00197   }
00198 
00203   void Compact ()
00204   {
00205     CS_ASSERT (blocks.Length() != 0);
00206     size_t i = blocks.Length () - 1;
00207     while (i > firstfreeblock)
00208     {
00209       if (blocks[i].firstfree == (csFreeList*)blocks[i].memory 
00210         && blocks[i].firstfree->numfree == size)
00211       {
00212         CS_ASSERT (blocks[i].firstfree->next == 0);
00213         blocks.DeleteIndex (i);
00214       }
00215       i--;
00216     }
00217   }
00218 
00222   T* Alloc ()
00223   {
00224     CS_ASSERT (blocks.Length() != 0);
00225 
00226     // This routine makes sure there is ALWAYS free space available.
00227     csBlock& freebl = blocks[firstfreeblock];
00228     void* ptr = (void*)(freebl.firstfree);
00229 
00230     if (freebl.firstfree->numfree >= 2)
00231     {
00232       // Still room in this block after allocation.
00233       csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize);
00234       nf->next = freebl.firstfree->next;
00235       nf->numfree = freebl.firstfree->numfree-1;
00236       freebl.firstfree = nf;
00237     }
00238     else
00239     {
00240       // We need a new block later.
00241       freebl.firstfree = freebl.firstfree->next;
00242       if (!freebl.firstfree)
00243       {
00244         // This block has no more free space. We need a new one.
00245         FindAndUpdateFreeBlock ();
00246       }
00247     }
00248 
00249     return new (ptr) T;
00250   }
00251 
00255   void Free (T* el)
00256   {
00257     if (!el) return;
00258 
00259     size_t idx = FindBlock ((void*)el);
00260     CS_ASSERT_MSG (
00261       "csBlockAllocator<>::Free() called with invalid element address",
00262       idx != (size_t)-1);
00263 
00264     el->~T();
00265 
00266 #ifdef CS_BLOCKALLOC_DEBUG
00267     memset (el, 0xfb, elsize);
00268 #endif
00269 
00270     // If the index is lower than the index of the first free block
00271     // then we update the firstfreeblock index.
00272     if (idx < firstfreeblock)
00273       firstfreeblock = idx;
00274 
00275     csBlock& bl = blocks[idx];
00276     if (bl.firstfree == 0)
00277     {
00278       // Block has no free items so we create the first free item
00279       // here.
00280       bl.firstfree = (csFreeList*)el;
00281       bl.firstfree->next = 0;
00282       bl.firstfree->numfree = 1;
00283     }
00284     else
00285     {
00286       csFreeList* p_el = (csFreeList*)el;
00287 
00288       if (p_el < bl.firstfree)
00289       {
00290         // New free element is before the current free element.
00291         if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize)
00292         {
00293           // New free element is directly before the current free
00294           // element.
00295           p_el->next = bl.firstfree->next;
00296           p_el->numfree = bl.firstfree->numfree+1;
00297         }
00298         else
00299         {
00300           // There is a gap.
00301           p_el->next = bl.firstfree;
00302           p_el->numfree = 1;
00303         }
00304 
00305         bl.firstfree = p_el;
00306       }
00307       else
00308       {
00309         // New free element is after the current free element.
00310         // First we find the two free blocks that enclose the new
00311         // free element.
00312         csFreeList* fl_before = bl.firstfree;
00313         csFreeList* fl_after = bl.firstfree->next;
00314         while (fl_after != 0 && fl_after < p_el)
00315         {
00316           fl_before = fl_after;
00317           fl_after = fl_after->next;
00318         }
00319 
00320         // 'fl_before_end' points to the memory right after the free block
00321         // that is directly before the new free element. We use
00322         // 'fl_before_end' later.
00323         char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize;
00324 
00325         if (!fl_after)
00326         {
00327           // The new free element is after the last free block. First check
00328           // if the new free element directly follows that free block.
00329           // If so we can extend that.
00330           if (fl_before_end == (char*)p_el)
00331           {
00332             // Yes, extend.
00333             ++(fl_before->numfree);
00334           }
00335           else
00336           {
00337             // No, we have to create a new free block.
00338             p_el->next = 0;
00339             p_el->numfree = 1;
00340             fl_before->next = p_el;
00341           }
00342         }
00343         else
00344         {
00345           // We have a block before and after the new free block.
00346           // First we check if the new free item exactly between
00347           // fl_before and fl_after.
00348           if (fl_before_end == (char*)p_el
00349                 && ((char*)p_el) + elsize == (char*)fl_after)
00350           {
00351             // Perfect fit, merge fl_before and fl_after.
00352             fl_before->next = fl_after->next;
00353             fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree;
00354           }
00355           else if (fl_before_end == (char*)p_el)
00356           {
00357             // New free item fits directly after fl_before.
00358             ++(fl_before->numfree);
00359           }
00360           else if (((char*)p_el) + elsize == (char*)fl_after)
00361           {
00362             // New free item fits directly before fl_after.
00363             fl_before->next = p_el;
00364             p_el->next = fl_after->next;
00365             p_el->numfree = fl_after->numfree+1;
00366           }
00367           else
00368           {
00369             // We need a new free block.
00370             fl_before->next = p_el;
00371             p_el->next = fl_after;
00372             p_el->numfree = 1;
00373           }
00374         }
00375       }
00376     }
00377   }
00378 
00382   void Dump ()
00383   {
00384     int i;
00385     printf ("=============================\nelsize = %d\n", elsize);
00386     for (i = 0 ; i < blocks.Length () ; i++)
00387     {
00388       printf ("Block %d\n", i);
00389       csFreeList* fl = blocks[i].firstfree;
00390       char* m = (char*)blocks[i].memory;
00391       while (fl)
00392       {
00393         printf ("  free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree);
00394         fl = fl->next;
00395       }
00396     }
00397     printf ("=============================\n");
00398     fflush (stdout);
00399   }
00400 };
00401 
00402 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00403 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00404 #endif
00405 
00406 #endif

Generated for Crystal Space by doxygen 1.3.9.1