CrystalSpace

Public API Reference

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

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

Generated for Crystal Space by doxygen 1.2.18