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