CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

blockallocator.h

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 
00022 #include "csutil/array.h"
00023 
00024 // hack: work around problems caused by #defining 'new'
00025 #ifdef CS_EXTENSIVE_MEMDEBUG
00026 # undef new
00027 #endif
00028 #include <new>
00029 
00041 template <class T>
00042 class csBlockAllocator
00043 {
00044 private:
00045   // A dummy structure for a linked list of free items.
00046   struct csFreeList
00047   {
00048     csFreeList* next;
00049     uint32 numfree;     // Free elements in this block.
00050   };
00051 
00052   // A memory block (a series of 'size' objects).
00053   struct csBlock
00054   {
00055     void* memory;
00056     csFreeList* firstfree;      // Linked list of free items in this block.
00057     csBlock () : memory (NULL) { }
00058     ~csBlock () { if (memory) free (memory); }
00059   };
00060 
00061   csArray<csBlock> blocks;
00062   unsigned int size;            // Number of elements per block.
00063   unsigned int elsize;          // Element size (bigger than 8).
00064   unsigned int blocksize;       // Size in bytes per block.
00065 
00066   // First block that contains a free element.
00067   int firstfreeblock;
00068 
00072   int FindBlock (void* m)
00073   {
00074     int i;
00075     for (i = 0 ; i < blocks.Length () ; i++)
00076     {
00077       csBlock* b = &blocks[i];
00078       if (b->memory <= m)
00079       {
00080         char* eb = ((char*)b->memory) + blocksize;
00081         if (((char*)m) < eb)
00082           return i;
00083       }
00084     }
00085     return -1;
00086   }
00087 
00092   void FindAndUpdateFreeBlock ()
00093   {
00094     ++firstfreeblock;
00095     while (firstfreeblock < blocks.Length ()
00096                 && blocks[firstfreeblock].firstfree == NULL)
00097       ++firstfreeblock;
00098 
00099     if (firstfreeblock == blocks.Length ())
00100     {
00101       firstfreeblock = blocks.Push (csBlock ());
00102       csBlock& bl = blocks[firstfreeblock];
00103       bl.memory = (void*)malloc (blocksize);
00104       bl.firstfree = (csFreeList*)bl.memory;
00105       bl.firstfree->next = NULL;
00106       bl.firstfree->numfree = size;
00107     }
00108   }
00109 
00110 public:
00116   csBlockAllocator (int s)
00117   {
00118     size = s;
00119     elsize = sizeof (T);
00120     if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList);
00121     blocksize = elsize * size;
00122 
00123     int idx = blocks.Push (csBlock ());
00124     csBlock& bl = blocks[idx];
00125     bl.memory = (void*)malloc (blocksize);
00126     bl.firstfree = (csFreeList*)bl.memory;
00127     bl.firstfree->next = NULL;
00128     bl.firstfree->numfree = size;
00129 
00130     firstfreeblock = 0;
00131   }
00132 
00139   ~csBlockAllocator ()
00140   {
00141 #ifdef CS_DEBUG
00142     CS_ASSERT (firstfreeblock == 0);
00143     int i;
00144     for (i = 0 ; i < blocks.Length () ; i++)
00145     {
00146       CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory);
00147       CS_ASSERT (blocks[i].firstfree->next == NULL);
00148       CS_ASSERT (blocks[i].firstfree->numfree == size);
00149     }
00150 #endif
00151   }
00152 
00156   T* Alloc ()
00157   {
00158     // This routine makes sure there is ALWAYS free space available.
00159     csBlock& freebl = blocks[firstfreeblock];
00160     void* ptr = (void*)(freebl.firstfree);
00161 
00162     if (freebl.firstfree->numfree >= 2)
00163     {
00164       // Still room in this block after allocation.
00165       csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize);
00166       nf->next = freebl.firstfree->next;
00167       nf->numfree = freebl.firstfree->numfree-1;
00168       freebl.firstfree = nf;
00169     }
00170     else
00171     {
00172       // We need a new block later.
00173       freebl.firstfree = freebl.firstfree->next;
00174       if (!freebl.firstfree)
00175       {
00176         // This block has no more free space. We need a new one.
00177         FindAndUpdateFreeBlock ();
00178       }
00179     }
00180 
00181     return new (ptr) T ();
00182   }
00183 
00187   void Free (T* el)
00188   {
00189     if (!el) return;
00190 
00191     int idx = FindBlock ((void*)el);
00192     CS_ASSERT (idx != -1);
00193 
00194     el->T::~T();
00195 
00196     // If the index is lower than the index of the first free block
00197     // then we update the firstfreeblock index.
00198     if (idx < firstfreeblock)
00199       firstfreeblock = idx;
00200 
00201     csBlock& bl = blocks[idx];
00202     if (bl.firstfree == NULL)
00203     {
00204       // Block has no free items so we create the first free item
00205       // here.
00206       bl.firstfree = (csFreeList*)el;
00207       bl.firstfree->next = NULL;
00208       bl.firstfree->numfree = 1;
00209     }
00210     else
00211     {
00212       csFreeList* p_el = (csFreeList*)el;
00213 
00214       if (p_el < bl.firstfree)
00215       {
00216         // New free element is before the current free element.
00217         if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize)
00218         {
00219           // New free element is directly before the current free
00220           // element.
00221           p_el->next = bl.firstfree->next;
00222           p_el->numfree = bl.firstfree->numfree+1;
00223         }
00224         else
00225         {
00226           // There is a gap.
00227           p_el->next = bl.firstfree;
00228           p_el->numfree = 1;
00229         }
00230 
00231         bl.firstfree = p_el;
00232       }
00233       else
00234       {
00235         // New free element is after the current free element.
00236         // First we find the two free blocks that enclose the new
00237         // free element.
00238         csFreeList* fl_before = bl.firstfree;
00239         csFreeList* fl_after = bl.firstfree->next;
00240         while (fl_after != NULL && fl_after < p_el)
00241         {
00242           fl_before = fl_after;
00243           fl_after = fl_after->next;
00244         }
00245 
00246         // 'fl_before_end' points to the memory right after the free block
00247         // that is directly before the new free element. We use
00248         // 'fl_before_end' later.
00249         char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize;
00250 
00251         if (!fl_after)
00252         {
00253           // The new free element is after the last free block. First check
00254           // if the new free element directly follows that free block.
00255           // If so we can extend that.
00256           if (fl_before_end == (char*)p_el)
00257           {
00258             // Yes, extend.
00259             ++(fl_before->numfree);
00260           }
00261           else
00262           {
00263             // No, we have to create a new free block.
00264             p_el->next = NULL;
00265             p_el->numfree = 1;
00266             fl_before->next = p_el;
00267           }
00268         }
00269         else
00270         {
00271           // We have a block before and after the new free block.
00272           // First we check if the new free item exactly between
00273           // fl_before and fl_after.
00274           if (fl_before_end == (char*)p_el
00275                 && ((char*)p_el) + elsize == (char*)fl_after)
00276           {
00277             // Perfect fit, merge fl_before and fl_after.
00278             fl_before->next = fl_after->next;
00279             fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree;
00280           }
00281           else if (fl_before_end == (char*)p_el)
00282           {
00283             // New free item fits directly after fl_before.
00284             ++(fl_before->numfree);
00285           }
00286           else if (((char*)p_el) + elsize == (char*)fl_after)
00287           {
00288             // New free item fits directly before fl_after.
00289             fl_before->next = p_el;
00290             p_el->next = fl_after->next;
00291             p_el->numfree = fl_after->numfree+1;
00292           }
00293           else
00294           {
00295             // We need a new free block.
00296             fl_before->next = p_el;
00297             p_el->next = fl_after;
00298             p_el->numfree = 1;
00299           }
00300         }
00301       }
00302     }
00303   }
00304 
00308   void Dump ()
00309   {
00310     int i;
00311     printf ("=============================\nelsize = %d\n", elsize);
00312     for (i = 0 ; i < blocks.Length () ; i++)
00313     {
00314       printf ("Block %d\n", i);
00315       csFreeList* fl = blocks[i].firstfree;
00316       char* m = (char*)blocks[i].memory;
00317       while (fl)
00318       {
00319         printf ("  free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree);
00320         fl = fl->next;
00321       }
00322     }
00323     printf ("=============================\n");
00324     fflush (stdout);
00325   }
00326 };
00327 
00328 #ifdef CS_EXTENSIVE_MEMDEBUG
00329 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00330 #endif
00331 
00332 #endif
00333 

Generated for Crystal Space by doxygen 1.2.14