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 
~BatchAllocator()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.
allocate()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.
release(AllocatedType * 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 
allocateBatch(unsigned int objectsPerPage)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