Home | History | Annotate | Download | only in lib_json 
      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 // included by json_value.cpp
      7 
      8 namespace Json {
      9 
     10 // //////////////////////////////////////////////////////////////////
     11 // //////////////////////////////////////////////////////////////////
     12 // //////////////////////////////////////////////////////////////////
     13 // class ValueInternalArray
     14 // //////////////////////////////////////////////////////////////////
     15 // //////////////////////////////////////////////////////////////////
     16 // //////////////////////////////////////////////////////////////////
     17 
     18 ValueArrayAllocator::~ValueArrayAllocator()
     19 {
     20 }
     21 
     22 // //////////////////////////////////////////////////////////////////
     23 // class DefaultValueArrayAllocator
     24 // //////////////////////////////////////////////////////////////////
     25 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
     26 class DefaultValueArrayAllocator : public ValueArrayAllocator
     27 {
     28 public: // overridden from ValueArrayAllocator
     29    virtual ~DefaultValueArrayAllocator()
     30    {
     31    }
     32 
     33    virtual ValueInternalArray *newArray()
     34    {
     35       return new ValueInternalArray();
     36    }
     37 
     38    virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
     39    {
     40       return new ValueInternalArray( other );
     41    }
     42 
     43    virtual void destructArray( ValueInternalArray *array )
     44    {
     45       delete array;
     46    }
     47 
     48    virtual void reallocateArrayPageIndex( Value **&indexes, 
     49                                           ValueInternalArray::PageIndex &indexCount,
     50                                           ValueInternalArray::PageIndex minNewIndexCount )
     51    {
     52       ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
     53       if ( minNewIndexCount > newIndexCount )
     54          newIndexCount = minNewIndexCount;
     55       void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
     56       JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc.");
     57       indexCount = newIndexCount;
     58       indexes = static_cast<Value **>( newIndexes );
     59    }
     60    virtual void releaseArrayPageIndex( Value **indexes, 
     61                                        ValueInternalArray::PageIndex indexCount )
     62    {
     63       if ( indexes )
     64          free( indexes );
     65    }
     66 
     67    virtual Value *allocateArrayPage()
     68    {
     69       return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
     70    }
     71 
     72    virtual void releaseArrayPage( Value *value )
     73    {
     74       if ( value )
     75          free( value );
     76    }
     77 };
     78 
     79 #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
     80 /// @todo make this thread-safe (lock when accessign batch allocator)
     81 class DefaultValueArrayAllocator : public ValueArrayAllocator
     82 {
     83 public: // overridden from ValueArrayAllocator
     84    virtual ~DefaultValueArrayAllocator()
     85    {
     86    }
     87 
     88    virtual ValueInternalArray *newArray()
     89    {
     90       ValueInternalArray *array = arraysAllocator_.allocate();
     91       new (array) ValueInternalArray(); // placement new
     92       return array;
     93    }
     94 
     95    virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
     96    {
     97       ValueInternalArray *array = arraysAllocator_.allocate();
     98       new (array) ValueInternalArray( other ); // placement new
     99       return array;
    100    }
    101 
    102    virtual void destructArray( ValueInternalArray *array )
    103    {
    104       if ( array )
    105       {
    106          array->~ValueInternalArray();
    107          arraysAllocator_.release( array );
    108       }
    109    }
    110 
    111    virtual void reallocateArrayPageIndex( Value **&indexes, 
    112                                           ValueInternalArray::PageIndex &indexCount,
    113                                           ValueInternalArray::PageIndex minNewIndexCount )
    114    {
    115       ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
    116       if ( minNewIndexCount > newIndexCount )
    117          newIndexCount = minNewIndexCount;
    118       void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
    119       JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc.");
    120       indexCount = newIndexCount;
    121       indexes = static_cast<Value **>( newIndexes );
    122    }
    123    virtual void releaseArrayPageIndex( Value **indexes, 
    124                                        ValueInternalArray::PageIndex indexCount )
    125    {
    126       if ( indexes )
    127          free( indexes );
    128    }
    129 
    130    virtual Value *allocateArrayPage()
    131    {
    132       return static_cast<Value *>( pagesAllocator_.allocate() );
    133    }
    134 
    135    virtual void releaseArrayPage( Value *value )
    136    {
    137       if ( value )
    138          pagesAllocator_.release( value );
    139    }
    140 private:
    141    BatchAllocator<ValueInternalArray,1> arraysAllocator_;
    142    BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
    143 };
    144 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
    145 
    146 static ValueArrayAllocator *&arrayAllocator()
    147 {
    148    static DefaultValueArrayAllocator defaultAllocator;
    149    static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
    150    return arrayAllocator;
    151 }
    152 
    153 static struct DummyArrayAllocatorInitializer {
    154    DummyArrayAllocatorInitializer() 
    155    {
    156       arrayAllocator();      // ensure arrayAllocator() statics are initialized before main().
    157    }
    158 } dummyArrayAllocatorInitializer;
    159 
    160 // //////////////////////////////////////////////////////////////////
    161 // class ValueInternalArray
    162 // //////////////////////////////////////////////////////////////////
    163 bool 
    164 ValueInternalArray::equals( const IteratorState &x, 
    165                             const IteratorState &other )
    166 {
    167    return x.array_ == other.array_  
    168           &&  x.currentItemIndex_ == other.currentItemIndex_  
    169           &&  x.currentPageIndex_ == other.currentPageIndex_;
    170 }
    171 
    172 
    173 void 
    174 ValueInternalArray::increment( IteratorState &it )
    175 {
    176    JSON_ASSERT_MESSAGE( it.array_  &&
    177       (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
    178       != it.array_->size_,
    179       "ValueInternalArray::increment(): moving iterator beyond end" );
    180    ++(it.currentItemIndex_);
    181    if ( it.currentItemIndex_ == itemsPerPage )
    182    {
    183       it.currentItemIndex_ = 0;
    184       ++(it.currentPageIndex_);
    185    }
    186 }
    187 
    188 
    189 void 
    190 ValueInternalArray::decrement( IteratorState &it )
    191 {
    192    JSON_ASSERT_MESSAGE( it.array_  &&  it.currentPageIndex_ == it.array_->pages_ 
    193                         &&  it.currentItemIndex_ == 0,
    194       "ValueInternalArray::decrement(): moving iterator beyond end" );
    195    if ( it.currentItemIndex_ == 0 )
    196    {
    197       it.currentItemIndex_ = itemsPerPage-1;
    198       --(it.currentPageIndex_);
    199    }
    200    else
    201    {
    202       --(it.currentItemIndex_);
    203    }
    204 }
    205 
    206 
    207 Value &
    208 ValueInternalArray::unsafeDereference( const IteratorState &it )
    209 {
    210    return (*(it.currentPageIndex_))[it.currentItemIndex_];
    211 }
    212 
    213 
    214 Value &
    215 ValueInternalArray::dereference( const IteratorState &it )
    216 {
    217    JSON_ASSERT_MESSAGE( it.array_  &&
    218       (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
    219       < it.array_->size_,
    220       "ValueInternalArray::dereference(): dereferencing invalid iterator" );
    221    return unsafeDereference( it );
    222 }
    223 
    224 void 
    225 ValueInternalArray::makeBeginIterator( IteratorState &it ) const
    226 {
    227    it.array_ = const_cast<ValueInternalArray *>( this );
    228    it.currentItemIndex_ = 0;
    229    it.currentPageIndex_ = pages_;
    230 }
    231 
    232 
    233 void 
    234 ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
    235 {
    236    it.array_ = const_cast<ValueInternalArray *>( this );
    237    it.currentItemIndex_ = index % itemsPerPage;
    238    it.currentPageIndex_ = pages_ + index / itemsPerPage;
    239 }
    240 
    241 
    242 void 
    243 ValueInternalArray::makeEndIterator( IteratorState &it ) const
    244 {
    245    makeIterator( it, size_ );
    246 }
    247 
    248 
    249 ValueInternalArray::ValueInternalArray()
    250    : pages_( 0 )
    251    , size_( 0 )
    252    , pageCount_( 0 )
    253 {
    254 }
    255 
    256 
    257 ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
    258    : pages_( 0 )
    259    , size_( other.size_ )
    260    , pageCount_( 0 )
    261 {
    262    PageIndex minNewPages = other.size_ / itemsPerPage;
    263    arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
    264    JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, 
    265                         "ValueInternalArray::reserve(): bad reallocation" );
    266    IteratorState itOther;
    267    other.makeBeginIterator( itOther );
    268    Value *value;
    269    for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
    270    {
    271       if ( index % itemsPerPage == 0 )
    272       {
    273          PageIndex pageIndex = index / itemsPerPage;
    274          value = arrayAllocator()->allocateArrayPage();
    275          pages_[pageIndex] = value;
    276       }
    277       new (value) Value( dereference( itOther ) );
    278    }
    279 }
    280 
    281 
    282 ValueInternalArray &
    283 ValueInternalArray::operator =( const ValueInternalArray &other )
    284 {
    285    ValueInternalArray temp( other );
    286    swap( temp );
    287    return *this;
    288 }
    289 
    290 
    291 ValueInternalArray::~ValueInternalArray()
    292 {
    293    // destroy all constructed items
    294    IteratorState it;
    295    IteratorState itEnd;
    296    makeBeginIterator( it);
    297    makeEndIterator( itEnd );
    298    for ( ; !equals(it,itEnd); increment(it) )
    299    {
    300       Value *value = &dereference(it);
    301       value->~Value();
    302    }
    303    // release all pages
    304    PageIndex lastPageIndex = size_ / itemsPerPage;
    305    for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
    306       arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
    307    // release pages index
    308    arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
    309 }
    310 
    311 
    312 void 
    313 ValueInternalArray::swap( ValueInternalArray &other )
    314 {
    315    Value **tempPages = pages_;
    316    pages_ = other.pages_;
    317    other.pages_ = tempPages;
    318    ArrayIndex tempSize = size_;
    319    size_ = other.size_;
    320    other.size_ = tempSize;
    321    PageIndex tempPageCount = pageCount_;
    322    pageCount_ = other.pageCount_;
    323    other.pageCount_ = tempPageCount;
    324 }
    325 
    326 void 
    327 ValueInternalArray::clear()
    328 {
    329    ValueInternalArray dummy;
    330    swap( dummy );
    331 }
    332 
    333 
    334 void 
    335 ValueInternalArray::resize( ArrayIndex newSize )
    336 {
    337    if ( newSize == 0 )
    338       clear();
    339    else if ( newSize < size_ )
    340    {
    341       IteratorState it;
    342       IteratorState itEnd;
    343       makeIterator( it, newSize );
    344       makeIterator( itEnd, size_ );
    345       for ( ; !equals(it,itEnd); increment(it) )
    346       {
    347          Value *value = &dereference(it);
    348          value->~Value();
    349       }
    350       PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
    351       PageIndex lastPageIndex = size_ / itemsPerPage;
    352       for ( ; pageIndex < lastPageIndex; ++pageIndex )
    353          arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
    354       size_ = newSize;
    355    }
    356    else if ( newSize > size_ )
    357       resolveReference( newSize );
    358 }
    359 
    360 
    361 void 
    362 ValueInternalArray::makeIndexValid( ArrayIndex index )
    363 {
    364    // Need to enlarge page index ?
    365    if ( index >= pageCount_ * itemsPerPage )
    366    {
    367       PageIndex minNewPages = (index + 1) / itemsPerPage;
    368       arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
    369       JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
    370    }
    371 
    372    // Need to allocate new pages ?
    373    ArrayIndex nextPageIndex = 
    374       (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
    375                                   : size_;
    376    if ( nextPageIndex <= index )
    377    {
    378       PageIndex pageIndex = nextPageIndex / itemsPerPage;
    379       PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
    380       for ( ; pageToAllocate-- > 0; ++pageIndex )
    381          pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
    382    }
    383 
    384    // Initialize all new entries
    385    IteratorState it;
    386    IteratorState itEnd;
    387    makeIterator( it, size_ );
    388    size_ = index + 1;
    389    makeIterator( itEnd, size_ );
    390    for ( ; !equals(it,itEnd); increment(it) )
    391    {
    392       Value *value = &dereference(it);
    393       new (value) Value(); // Construct a default value using placement new
    394    }
    395 }
    396 
    397 Value &
    398 ValueInternalArray::resolveReference( ArrayIndex index )
    399 {
    400    if ( index >= size_ )
    401       makeIndexValid( index );
    402    return pages_[index/itemsPerPage][index%itemsPerPage];
    403 }
    404 
    405 Value *
    406 ValueInternalArray::find( ArrayIndex index ) const
    407 {
    408    if ( index >= size_ )
    409       return 0;
    410    return &(pages_[index/itemsPerPage][index%itemsPerPage]);
    411 }
    412 
    413 ValueInternalArray::ArrayIndex 
    414 ValueInternalArray::size() const
    415 {
    416    return size_;
    417 }
    418 
    419 int 
    420 ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
    421 {
    422    return indexOf(y) - indexOf(x);
    423 }
    424 
    425 
    426 ValueInternalArray::ArrayIndex 
    427 ValueInternalArray::indexOf( const IteratorState &iterator )
    428 {
    429    if ( !iterator.array_ )
    430       return ArrayIndex(-1);
    431    return ArrayIndex(
    432       (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage 
    433       + iterator.currentItemIndex_ );
    434 }
    435 
    436 
    437 int 
    438 ValueInternalArray::compare( const ValueInternalArray &other ) const
    439 {
    440    int sizeDiff( size_ - other.size_ );
    441    if ( sizeDiff != 0 )
    442       return sizeDiff;
    443    
    444    for ( ArrayIndex index =0; index < size_; ++index )
    445    {
    446       int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare( 
    447          other.pages_[index/itemsPerPage][index%itemsPerPage] );
    448       if ( diff != 0 )
    449          return diff;
    450    }
    451    return 0;
    452 }
    453 
    454 } // namespace Json
    455