dataChunker.h

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _DATACHUNKER_H_
 25#define _DATACHUNKER_H_
 26
 27#ifndef _PLATFORM_H_
 28#  include "platform/platform.h"
 29#endif
 30
 31//----------------------------------------------------------------------------
 32/// Implements a chunked data allocator.
 33///
 34/// Calling new/malloc all the time is a time consuming operation. Therefore,
 35/// we provide the DataChunker, which allocates memory in blocks of
 36/// chunkSize (by default 16k, see ChunkSize, though it can be set in
 37/// the constructor), then doles it out as requested, in chunks of up to
 38/// chunkSize in size.
 39///
 40/// It will assert if you try to get more than ChunkSize bytes at a time,
 41/// and it deals with the logic of allocating new blocks and giving out
 42/// word-aligned chunks.
 43///
 44/// Note that new/free/realloc WILL NOT WORK on memory gotten from the
 45/// DataChunker. This also only grows (you can call freeBlocks to deallocate
 46/// and reset things).
 47class DataChunker
 48{
 49public:
 50   /// Block of allocated memory.
 51   ///
 52   /// <b>This has nothing to do with datablocks as used in the rest of Torque.</b>
 53   struct DataBlock
 54   {
 55      DataBlock* next;        ///< linked list pointer to the next DataBlock for this chunker
 56      S32 curIndex;           ///< current allocation point within this DataBlock
 57      DataBlock();
 58      ~DataBlock();
 59      inline U8 *getData();
 60   };
 61
 62   enum {
 63      PaddDBSize = (sizeof(DataBlock) + 3) & ~3, ///< Padded size of DataBlock
 64      ChunkSize = 16384 - PaddDBSize ///< Default size of each DataBlock page in the DataChunker
 65   };
 66
 67   /// Return a pointer to a chunk of memory from a pre-allocated block.
 68   ///
 69   /// This memory goes away when you call freeBlocks.
 70   ///
 71   /// This memory is word-aligned.
 72   /// @param   size    Size of chunk to return. This must be less than chunkSize or else
 73   ///                  an assertion will occur.
 74   void *alloc(S32 size);
 75
 76   /// Free all allocated memory blocks.
 77   ///
 78   /// This invalidates all pointers returned from alloc().
 79   void freeBlocks(bool keepOne = false);
 80
 81   /// Initialize using blocks of a given size.
 82   ///
 83   /// One new block is allocated at constructor-time.
 84   ///
 85   /// @param   size    Size in bytes of the space to allocate for each block.
 86   DataChunker(S32 size=<a href="/coding/class/classdatachunker/#classdatachunker_1ade8fb4b614fa1fef8c4fa6e353972896a536630bb06ed00f89cfb97eadca9c7c4">ChunkSize</a>);
 87   ~DataChunker();
 88
 89   /// Swaps the memory allocated in one data chunker for another.  This can be used to implement
 90   /// packing of memory stored in a DataChunker.
 91   void swap(DataChunker &d)
 92   {
 93      DataBlock *temp = d.mCurBlock;
 94      d.mCurBlock = mCurBlock;
 95      mCurBlock = temp;
 96   }
 97   
 98public:
 99   U32 countUsedBlocks()
100   {
101      U32 count = 0;
102      if (!mCurBlock)
103         return 0;
104      for (DataBlock *ptr = mCurBlock; ptr != NULL; ptr = ptr->next)
105      {
106         count++;
107      }
108      return count;
109   }
110   
111   void setChunkSize(U32 size)
112   {
113      AssertFatal(mCurBlock == NULL, "Cant resize now");
114      mChunkSize = size;
115   }
116
117   
118public:
119
120   DataBlock*  mCurBlock;    ///< current page we're allocating data from.  If the
121                              ///< data size request is greater than the memory space currently
122                              ///< available in the current page, a new page will be allocated.
123   S32         mChunkSize;    ///< The size allocated for each page in the DataChunker
124};
125
126
127inline U8 *DataChunker::DataBlock::getData()
128{
129   return (U8*)this + DataChunker::PaddDBSize;
130}
131
132//----------------------------------------------------------------------------
133
134template<class T>
135class Chunker: private DataChunker
136{
137public:
138   Chunker(S32 size = DataChunker::ChunkSize) : DataChunker(size) {};
139   T* alloc()  { return reinterpret_cast<T*>(DataChunker::alloc(S32(sizeof(T)))); }
140   void clear()  { freeBlocks(); }
141};
142
143//----------------------------------------------------------------------------
144/// This class is similar to the Chunker<> class above.  But it allows for multiple
145/// types of structs to be stored.  
146/// CodeReview:  This could potentially go into DataChunker directly, but I wasn't sure if 
147/// CodeReview:  That would be polluting it.  BTR
148class MultiTypedChunker : private DataChunker
149{
150public:
151   MultiTypedChunker(S32 size = DataChunker::ChunkSize) : DataChunker(size) {};
152
153   /// Use like so:  MyType* t = chunker.alloc<MyType>();
154   template<typename T>
155   T* alloc()  { return reinterpret_cast<T*>(DataChunker::alloc(S32(sizeof(T)))); }
156   void clear()  { freeBlocks(true); }
157};
158
159//----------------------------------------------------------------------------
160
161/// Templatized data chunker class with proper construction and destruction of its elements.
162///
163/// DataChunker just allocates space. This subclass actually constructs/destructs the
164/// elements. This class is appropriate for more complex classes.
165template<class T>
166class ClassChunker: private DataChunker
167{
168public:
169   ClassChunker(S32 size = DataChunker::ChunkSize) : DataChunker(size)
170   {
171      mElementSize = getMax(U32(sizeof(T)), U32(sizeof(T *)));
172      mFreeListHead = NULL;
173   }
174
175   /// Allocates and properly constructs in place a new element.
176   T *alloc()
177   {
178      if(mFreeListHead == NULL)
179         return constructInPlace(reinterpret_cast<T*>(DataChunker::alloc(mElementSize)));
180      T* ret = mFreeListHead;
181      mFreeListHead = *(reinterpret_cast<T**>(mFreeListHead));
182      return constructInPlace(ret);
183   }
184
185   /// Properly destructs and frees an element allocated with the alloc method.
186   void free(T* elem)
187   {
188      destructInPlace(elem);
189      *(reinterpret_cast<T**>(elem)) = mFreeListHead;
190      mFreeListHead = elem;
191   }
192
193   void freeBlocks( bool keepOne = false ) 
194   { 
195      DataChunker::freeBlocks( keepOne ); 
196      mFreeListHead = NULL;
197   }
198
199private:
200   S32   mElementSize;     ///< the size of each element, or the size of a pointer, whichever is greater
201   T     *mFreeListHead;   ///< a pointer to a linked list of freed elements for reuse
202};
203
204//----------------------------------------------------------------------------
205
206template<class T>
207class FreeListChunker
208{
209public:
210   FreeListChunker(DataChunker *inChunker)
211      :  mChunker( inChunker ),
212         mOwnChunker( false ),
213         mFreeListHead( NULL )
214   {
215      mElementSize = getMax(U32(sizeof(T)), U32(sizeof(T *)));
216   }
217
218   FreeListChunker(S32 size = DataChunker::ChunkSize)
219      :  mFreeListHead( NULL )
220   {
221      mChunker = new DataChunker( size );
222      mOwnChunker = true;
223
224      mElementSize = getMax(U32(sizeof(T)), U32(sizeof(T *)));
225   }
226
227   ~FreeListChunker()
228   {
229      if ( mOwnChunker )
230         delete mChunker;
231   }
232
233   T *alloc()
234   {
235      if(mFreeListHead == NULL)
236         return reinterpret_cast<T*>(mChunker->alloc(mElementSize));
237      T* ret = mFreeListHead;
238      mFreeListHead = *(reinterpret_cast<T**>(mFreeListHead));
239      return ret;
240   }
241
242   void free(T* elem)
243   {
244      *(reinterpret_cast<T**>(elem)) = mFreeListHead;
245      mFreeListHead = elem;
246   }
247
248   /// Allow people to free all their memory if they want.
249   void freeBlocks( bool keepOne = false )
250   {
251      mChunker->freeBlocks( keepOne );
252      mFreeListHead = NULL;
253   }
254   
255private:
256   DataChunker *mChunker;
257   bool        mOwnChunker;
258
259   S32   mElementSize;
260   T     *mFreeListHead;
261};
262
263
264class FreeListChunkerUntyped
265{
266public:
267   FreeListChunkerUntyped(U32 inElementSize, DataChunker *inChunker)
268      :  mChunker( inChunker ),
269         mOwnChunker( false ),
270         mElementSize( inElementSize ),
271         mFreeListHead( NULL )
272   {
273   }
274
275   FreeListChunkerUntyped(U32 inElementSize, S32 size = DataChunker::ChunkSize)
276      :  mElementSize( inElementSize ),
277         mFreeListHead( NULL )
278   {
279      mChunker = new DataChunker( size );
280      mOwnChunker = true;
281   }
282
283   ~FreeListChunkerUntyped()
284   {
285      if ( mOwnChunker )
286         delete mChunker; 
287   }
288
289   void *alloc()
290   {
291      if(mFreeListHead == NULL)
292         return mChunker->alloc(mElementSize);
293
294      void  *ret = mFreeListHead;
295      mFreeListHead = *(reinterpret_cast<void**>(mFreeListHead));
296      return ret;
297   }
298
299   void free(void* elem)
300   {
301      *(reinterpret_cast<void**>(elem)) = mFreeListHead;
302      mFreeListHead = elem;
303   }
304
305   // Allow people to free all their memory if they want.
306   void freeBlocks()
307   {
308      mChunker->freeBlocks();
309
310      // We have to terminate the freelist as well or else we'll run
311      // into crazy unused memory.
312      mFreeListHead = NULL;
313   }
314
315   U32   getElementSize() const { return mElementSize; }
316
317private:
318   DataChunker *mChunker;
319   bool        mOwnChunker;
320
321   const U32   mElementSize;
322   void        *mFreeListHead;
323};
324#endif
325