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
14namespace 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 */
28template<typename AllocatedType
29        ,const unsigned int objectPerAllocation>
30class BatchAllocator
31{
32public:
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
91private:
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