| // Copyright 2007-2010 Baptiste Lepilleur |
| // Distributed under MIT license, or public domain if desired and |
| // recognized in your jurisdiction. |
| // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE |
| |
| // included by json_value.cpp |
| |
| namespace Json { |
| |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // class ValueInternalArray |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| |
| ValueArrayAllocator::~ValueArrayAllocator() |
| { |
| } |
| |
| // ////////////////////////////////////////////////////////////////// |
| // class DefaultValueArrayAllocator |
| // ////////////////////////////////////////////////////////////////// |
| #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| class DefaultValueArrayAllocator : public ValueArrayAllocator |
| { |
| public: // overridden from ValueArrayAllocator |
| virtual ~DefaultValueArrayAllocator() |
| { |
| } |
| |
| virtual ValueInternalArray *newArray() |
| { |
| return new ValueInternalArray(); |
| } |
| |
| virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other ) |
| { |
| return new ValueInternalArray( other ); |
| } |
| |
| virtual void destructArray( ValueInternalArray *array ) |
| { |
| delete array; |
| } |
| |
| virtual void reallocateArrayPageIndex( Value **&indexes, |
| ValueInternalArray::PageIndex &indexCount, |
| ValueInternalArray::PageIndex minNewIndexCount ) |
| { |
| ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1; |
| if ( minNewIndexCount > newIndexCount ) |
| newIndexCount = minNewIndexCount; |
| void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount ); |
| JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc."); |
| indexCount = newIndexCount; |
| indexes = static_cast<Value **>( newIndexes ); |
| } |
| virtual void releaseArrayPageIndex( Value **indexes, |
| ValueInternalArray::PageIndex indexCount ) |
| { |
| if ( indexes ) |
| free( indexes ); |
| } |
| |
| virtual Value *allocateArrayPage() |
| { |
| return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) ); |
| } |
| |
| virtual void releaseArrayPage( Value *value ) |
| { |
| if ( value ) |
| free( value ); |
| } |
| }; |
| |
| #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| /// @todo make this thread-safe (lock when accessign batch allocator) |
| class DefaultValueArrayAllocator : public ValueArrayAllocator |
| { |
| public: // overridden from ValueArrayAllocator |
| virtual ~DefaultValueArrayAllocator() |
| { |
| } |
| |
| virtual ValueInternalArray *newArray() |
| { |
| ValueInternalArray *array = arraysAllocator_.allocate(); |
| new (array) ValueInternalArray(); // placement new |
| return array; |
| } |
| |
| virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other ) |
| { |
| ValueInternalArray *array = arraysAllocator_.allocate(); |
| new (array) ValueInternalArray( other ); // placement new |
| return array; |
| } |
| |
| virtual void destructArray( ValueInternalArray *array ) |
| { |
| if ( array ) |
| { |
| array->~ValueInternalArray(); |
| arraysAllocator_.release( array ); |
| } |
| } |
| |
| virtual void reallocateArrayPageIndex( Value **&indexes, |
| ValueInternalArray::PageIndex &indexCount, |
| ValueInternalArray::PageIndex minNewIndexCount ) |
| { |
| ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1; |
| if ( minNewIndexCount > newIndexCount ) |
| newIndexCount = minNewIndexCount; |
| void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount ); |
| JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc."); |
| indexCount = newIndexCount; |
| indexes = static_cast<Value **>( newIndexes ); |
| } |
| virtual void releaseArrayPageIndex( Value **indexes, |
| ValueInternalArray::PageIndex indexCount ) |
| { |
| if ( indexes ) |
| free( indexes ); |
| } |
| |
| virtual Value *allocateArrayPage() |
| { |
| return static_cast<Value *>( pagesAllocator_.allocate() ); |
| } |
| |
| virtual void releaseArrayPage( Value *value ) |
| { |
| if ( value ) |
| pagesAllocator_.release( value ); |
| } |
| private: |
| BatchAllocator<ValueInternalArray,1> arraysAllocator_; |
| BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_; |
| }; |
| #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| |
| static ValueArrayAllocator *&arrayAllocator() |
| { |
| static DefaultValueArrayAllocator defaultAllocator; |
| static ValueArrayAllocator *arrayAllocator = &defaultAllocator; |
| return arrayAllocator; |
| } |
| |
| static struct DummyArrayAllocatorInitializer { |
| DummyArrayAllocatorInitializer() |
| { |
| arrayAllocator(); // ensure arrayAllocator() statics are initialized before main(). |
| } |
| } dummyArrayAllocatorInitializer; |
| |
| // ////////////////////////////////////////////////////////////////// |
| // class ValueInternalArray |
| // ////////////////////////////////////////////////////////////////// |
| bool |
| ValueInternalArray::equals( const IteratorState &x, |
| const IteratorState &other ) |
| { |
| return x.array_ == other.array_ |
| && x.currentItemIndex_ == other.currentItemIndex_ |
| && x.currentPageIndex_ == other.currentPageIndex_; |
| } |
| |
| |
| void |
| ValueInternalArray::increment( IteratorState &it ) |
| { |
| JSON_ASSERT_MESSAGE( it.array_ && |
| (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_ |
| != it.array_->size_, |
| "ValueInternalArray::increment(): moving iterator beyond end" ); |
| ++(it.currentItemIndex_); |
| if ( it.currentItemIndex_ == itemsPerPage ) |
| { |
| it.currentItemIndex_ = 0; |
| ++(it.currentPageIndex_); |
| } |
| } |
| |
| |
| void |
| ValueInternalArray::decrement( IteratorState &it ) |
| { |
| JSON_ASSERT_MESSAGE( it.array_ && it.currentPageIndex_ == it.array_->pages_ |
| && it.currentItemIndex_ == 0, |
| "ValueInternalArray::decrement(): moving iterator beyond end" ); |
| if ( it.currentItemIndex_ == 0 ) |
| { |
| it.currentItemIndex_ = itemsPerPage-1; |
| --(it.currentPageIndex_); |
| } |
| else |
| { |
| --(it.currentItemIndex_); |
| } |
| } |
| |
| |
| Value & |
| ValueInternalArray::unsafeDereference( const IteratorState &it ) |
| { |
| return (*(it.currentPageIndex_))[it.currentItemIndex_]; |
| } |
| |
| |
| Value & |
| ValueInternalArray::dereference( const IteratorState &it ) |
| { |
| JSON_ASSERT_MESSAGE( it.array_ && |
| (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_ |
| < it.array_->size_, |
| "ValueInternalArray::dereference(): dereferencing invalid iterator" ); |
| return unsafeDereference( it ); |
| } |
| |
| void |
| ValueInternalArray::makeBeginIterator( IteratorState &it ) const |
| { |
| it.array_ = const_cast<ValueInternalArray *>( this ); |
| it.currentItemIndex_ = 0; |
| it.currentPageIndex_ = pages_; |
| } |
| |
| |
| void |
| ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const |
| { |
| it.array_ = const_cast<ValueInternalArray *>( this ); |
| it.currentItemIndex_ = index % itemsPerPage; |
| it.currentPageIndex_ = pages_ + index / itemsPerPage; |
| } |
| |
| |
| void |
| ValueInternalArray::makeEndIterator( IteratorState &it ) const |
| { |
| makeIterator( it, size_ ); |
| } |
| |
| |
| ValueInternalArray::ValueInternalArray() |
| : pages_( 0 ) |
| , size_( 0 ) |
| , pageCount_( 0 ) |
| { |
| } |
| |
| |
| ValueInternalArray::ValueInternalArray( const ValueInternalArray &other ) |
| : pages_( 0 ) |
| , size_( other.size_ ) |
| , pageCount_( 0 ) |
| { |
| PageIndex minNewPages = other.size_ / itemsPerPage; |
| arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages ); |
| JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, |
| "ValueInternalArray::reserve(): bad reallocation" ); |
| IteratorState itOther; |
| other.makeBeginIterator( itOther ); |
| Value *value; |
| for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) ) |
| { |
| if ( index % itemsPerPage == 0 ) |
| { |
| PageIndex pageIndex = index / itemsPerPage; |
| value = arrayAllocator()->allocateArrayPage(); |
| pages_[pageIndex] = value; |
| } |
| new (value) Value( dereference( itOther ) ); |
| } |
| } |
| |
| |
| ValueInternalArray & |
| ValueInternalArray::operator =( const ValueInternalArray &other ) |
| { |
| ValueInternalArray temp( other ); |
| swap( temp ); |
| return *this; |
| } |
| |
| |
| ValueInternalArray::~ValueInternalArray() |
| { |
| // destroy all constructed items |
| IteratorState it; |
| IteratorState itEnd; |
| makeBeginIterator( it); |
| makeEndIterator( itEnd ); |
| for ( ; !equals(it,itEnd); increment(it) ) |
| { |
| Value *value = &dereference(it); |
| value->~Value(); |
| } |
| // release all pages |
| PageIndex lastPageIndex = size_ / itemsPerPage; |
| for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex ) |
| arrayAllocator()->releaseArrayPage( pages_[pageIndex] ); |
| // release pages index |
| arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ ); |
| } |
| |
| |
| void |
| ValueInternalArray::swap( ValueInternalArray &other ) |
| { |
| Value **tempPages = pages_; |
| pages_ = other.pages_; |
| other.pages_ = tempPages; |
| ArrayIndex tempSize = size_; |
| size_ = other.size_; |
| other.size_ = tempSize; |
| PageIndex tempPageCount = pageCount_; |
| pageCount_ = other.pageCount_; |
| other.pageCount_ = tempPageCount; |
| } |
| |
| void |
| ValueInternalArray::clear() |
| { |
| ValueInternalArray dummy; |
| swap( dummy ); |
| } |
| |
| |
| void |
| ValueInternalArray::resize( ArrayIndex newSize ) |
| { |
| if ( newSize == 0 ) |
| clear(); |
| else if ( newSize < size_ ) |
| { |
| IteratorState it; |
| IteratorState itEnd; |
| makeIterator( it, newSize ); |
| makeIterator( itEnd, size_ ); |
| for ( ; !equals(it,itEnd); increment(it) ) |
| { |
| Value *value = &dereference(it); |
| value->~Value(); |
| } |
| PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage; |
| PageIndex lastPageIndex = size_ / itemsPerPage; |
| for ( ; pageIndex < lastPageIndex; ++pageIndex ) |
| arrayAllocator()->releaseArrayPage( pages_[pageIndex] ); |
| size_ = newSize; |
| } |
| else if ( newSize > size_ ) |
| resolveReference( newSize ); |
| } |
| |
| |
| void |
| ValueInternalArray::makeIndexValid( ArrayIndex index ) |
| { |
| // Need to enlarge page index ? |
| if ( index >= pageCount_ * itemsPerPage ) |
| { |
| PageIndex minNewPages = (index + 1) / itemsPerPage; |
| arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages ); |
| JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" ); |
| } |
| |
| // Need to allocate new pages ? |
| ArrayIndex nextPageIndex = |
| (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage |
| : size_; |
| if ( nextPageIndex <= index ) |
| { |
| PageIndex pageIndex = nextPageIndex / itemsPerPage; |
| PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1; |
| for ( ; pageToAllocate-- > 0; ++pageIndex ) |
| pages_[pageIndex] = arrayAllocator()->allocateArrayPage(); |
| } |
| |
| // Initialize all new entries |
| IteratorState it; |
| IteratorState itEnd; |
| makeIterator( it, size_ ); |
| size_ = index + 1; |
| makeIterator( itEnd, size_ ); |
| for ( ; !equals(it,itEnd); increment(it) ) |
| { |
| Value *value = &dereference(it); |
| new (value) Value(); // Construct a default value using placement new |
| } |
| } |
| |
| Value & |
| ValueInternalArray::resolveReference( ArrayIndex index ) |
| { |
| if ( index >= size_ ) |
| makeIndexValid( index ); |
| return pages_[index/itemsPerPage][index%itemsPerPage]; |
| } |
| |
| Value * |
| ValueInternalArray::find( ArrayIndex index ) const |
| { |
| if ( index >= size_ ) |
| return 0; |
| return &(pages_[index/itemsPerPage][index%itemsPerPage]); |
| } |
| |
| ValueInternalArray::ArrayIndex |
| ValueInternalArray::size() const |
| { |
| return size_; |
| } |
| |
| int |
| ValueInternalArray::distance( const IteratorState &x, const IteratorState &y ) |
| { |
| return indexOf(y) - indexOf(x); |
| } |
| |
| |
| ValueInternalArray::ArrayIndex |
| ValueInternalArray::indexOf( const IteratorState &iterator ) |
| { |
| if ( !iterator.array_ ) |
| return ArrayIndex(-1); |
| return ArrayIndex( |
| (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage |
| + iterator.currentItemIndex_ ); |
| } |
| |
| |
| int |
| ValueInternalArray::compare( const ValueInternalArray &other ) const |
| { |
| int sizeDiff( size_ - other.size_ ); |
| if ( sizeDiff != 0 ) |
| return sizeDiff; |
| |
| for ( ArrayIndex index =0; index < size_; ++index ) |
| { |
| int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare( |
| other.pages_[index/itemsPerPage][index%itemsPerPage] ); |
| if ( diff != 0 ) |
| return diff; |
| } |
| return 0; |
| } |
| |
| } // namespace Json |