Home | History | Annotate | Download | only in lib_json 
      1 // Copyright 2007-2010 Baptiste Lepilleur
      2 // Distributed under MIT license, or public domain if desired and
      3 // recognized in your jurisdiction.
      4 // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE
      5 
      6 #ifndef JSONCPP_BATCHALLOCATOR_H_INCLUDED
      7 # define JSONCPP_BATCHALLOCATOR_H_INCLUDED
      8 
      9 # include <stdlib.h>
     10 # include <assert.h>
     11 
     12 # ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
     13 
     14 namespace Json {
     15 
     16 /* Fast memory allocator.
     17  *
     18  * This memory allocator allocates memory for a batch of object (specified by
     19  * the page size, the number of object in each page).
     20  *
     21  * It does not allow the destruction of a single object. All the allocated objects
     22  * can be destroyed at once. The memory can be either released or reused for future
     23  * allocation.
     24  *
     25  * The in-place new operator must be used to construct the object using the pointer
     26  * returned by allocate.
     27  */
     28 template<typename AllocatedType
     29         ,const unsigned int objectPerAllocation>
     30 class BatchAllocator
     31 {
     32 public:
     33    BatchAllocator( unsigned int objectsPerPage = 255 )
     34       : freeHead_( 0 )
     35       , objectsPerPage_( objectsPerPage )
     36    {
     37 //      printf( "Size: %d => %s\n", sizeof(AllocatedType), typeid(AllocatedType).name() );
     38       assert( sizeof(AllocatedType) * objectPerAllocation >= sizeof(AllocatedType *) ); // We must be able to store a slist in the object free space.
     39       assert( objectsPerPage >= 16 );
     40       batches_ = allocateBatch( 0 );   // allocated a dummy page
     41       currentBatch_ = batches_;
     42    }
     43 
     44    ~BatchAllocator()
     45    {
     46       for ( BatchInfo *batch = batches_; batch;  )
     47       {
     48          BatchInfo *nextBatch = batch->next_;
     49          free( batch );
     50          batch = nextBatch;
     51       }
     52    }
     53 
     54    /// allocate space for an array of objectPerAllocation object.
     55    /// @warning it is the responsability of the caller to call objects constructors.
     56    AllocatedType *allocate()
     57    {
     58       if ( freeHead_ ) // returns node from free list.
     59       {
     60          AllocatedType *object = freeHead_;
     61          freeHead_ = *(AllocatedType **)object;
     62          return object;
     63       }
     64       if ( currentBatch_->used_ == currentBatch_->end_ )
     65       {
     66          currentBatch_ = currentBatch_->next_;
     67          while ( currentBatch_  &&  currentBatch_->used_ == currentBatch_->end_ )
     68             currentBatch_ = currentBatch_->next_;
     69 
     70          if ( !currentBatch_  ) // no free batch found, allocate a new one
     71          {
     72             currentBatch_ = allocateBatch( objectsPerPage_ );
     73             currentBatch_->next_ = batches_; // insert at the head of the list
     74             batches_ = currentBatch_;
     75          }
     76       }
     77       AllocatedType *allocated = currentBatch_->used_;
     78       currentBatch_->used_ += objectPerAllocation;
     79       return allocated;
     80    }
     81 
     82    /// Release the object.
     83    /// @warning it is the responsability of the caller to actually destruct the object.
     84    void release( AllocatedType *object )
     85    {
     86       assert( object != 0 );
     87       *(AllocatedType **)object = freeHead_;
     88       freeHead_ = object;
     89    }
     90 
     91 private:
     92    struct BatchInfo
     93    {
     94       BatchInfo *next_;
     95       AllocatedType *used_;
     96       AllocatedType *end_;
     97       AllocatedType buffer_[objectPerAllocation];
     98    };
     99 
    100    // disabled copy constructor and assignement operator.
    101    BatchAllocator( const BatchAllocator & );
    102    void operator =( const BatchAllocator &);
    103 
    104    static BatchInfo *allocateBatch( unsigned int objectsPerPage )
    105    {
    106       const unsigned int mallocSize = sizeof(BatchInfo) - sizeof(AllocatedType)* objectPerAllocation
    107                                 + sizeof(AllocatedType) * objectPerAllocation * objectsPerPage;
    108       BatchInfo *batch = static_cast<BatchInfo*>( malloc( mallocSize ) );
    109       batch->next_ = 0;
    110       batch->used_ = batch->buffer_;
    111       batch->end_ = batch->buffer_ + objectsPerPage;
    112       return batch;
    113    }
    114 
    115    BatchInfo *batches_;
    116    BatchInfo *currentBatch_;
    117    /// Head of a single linked list within the allocated space of freeed object
    118    AllocatedType *freeHead_;
    119    unsigned int objectsPerPage_;
    120 };
    121 
    122 
    123 } // namespace Json
    124 
    125 # endif // ifndef JSONCPP_DOC_INCLUDE_IMPLEMENTATION
    126 
    127 #endif // JSONCPP_BATCHALLOCATOR_H_INCLUDED
    128