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