JsonCpp project page JsonCpp home page

json_internalarray.inl

Go to the documentation of this file.
00001 // included by json_value.cpp
00002 // everything is within Json namespace
00003 
00004 // //////////////////////////////////////////////////////////////////
00005 // //////////////////////////////////////////////////////////////////
00006 // //////////////////////////////////////////////////////////////////
00007 // class ValueInternalArray
00008 // //////////////////////////////////////////////////////////////////
00009 // //////////////////////////////////////////////////////////////////
00010 // //////////////////////////////////////////////////////////////////
00011 
00012 ValueArrayAllocator::~ValueArrayAllocator()
00013 {
00014 }
00015 
00016 // //////////////////////////////////////////////////////////////////
00017 // class DefaultValueArrayAllocator
00018 // //////////////////////////////////////////////////////////////////
00019 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
00020 class DefaultValueArrayAllocator : public ValueArrayAllocator
00021 {
00022 public: // overridden from ValueArrayAllocator
00023    virtual ~DefaultValueArrayAllocator()
00024    {
00025    }
00026 
00027    virtual ValueInternalArray *newArray()
00028    {
00029       return new ValueInternalArray();
00030    }
00031 
00032    virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
00033    {
00034       return new ValueInternalArray( other );
00035    }
00036 
00037    virtual void destructArray( ValueInternalArray *array )
00038    {
00039       delete array;
00040    }
00041 
00042    virtual void reallocateArrayPageIndex( Value **&indexes, 
00043                                           ValueInternalArray::PageIndex &indexCount,
00044                                           ValueInternalArray::PageIndex minNewIndexCount )
00045    {
00046       ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
00047       if ( minNewIndexCount > newIndexCount )
00048          newIndexCount = minNewIndexCount;
00049       void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
00050       if ( !newIndexes )
00051          throw std::bad_alloc();
00052       indexCount = newIndexCount;
00053       indexes = static_cast<Value **>( newIndexes );
00054    }
00055    virtual void releaseArrayPageIndex( Value **indexes, 
00056                                        ValueInternalArray::PageIndex indexCount )
00057    {
00058       if ( indexes )
00059          free( indexes );
00060    }
00061 
00062    virtual Value *allocateArrayPage()
00063    {
00064       return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
00065    }
00066 
00067    virtual void releaseArrayPage( Value *value )
00068    {
00069       if ( value )
00070          free( value );
00071    }
00072 };
00073 
00074 #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
00075 
00076 class DefaultValueArrayAllocator : public ValueArrayAllocator
00077 {
00078 public: // overridden from ValueArrayAllocator
00079    virtual ~DefaultValueArrayAllocator()
00080    {
00081    }
00082 
00083    virtual ValueInternalArray *newArray()
00084    {
00085       ValueInternalArray *array = arraysAllocator_.allocate();
00086       new (array) ValueInternalArray(); // placement new
00087       return array;
00088    }
00089 
00090    virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
00091    {
00092       ValueInternalArray *array = arraysAllocator_.allocate();
00093       new (array) ValueInternalArray( other ); // placement new
00094       return array;
00095    }
00096 
00097    virtual void destructArray( ValueInternalArray *array )
00098    {
00099       if ( array )
00100       {
00101          array->~ValueInternalArray();
00102          arraysAllocator_.release( array );
00103       }
00104    }
00105 
00106    virtual void reallocateArrayPageIndex( Value **&indexes, 
00107                                           ValueInternalArray::PageIndex &indexCount,
00108                                           ValueInternalArray::PageIndex minNewIndexCount )
00109    {
00110       ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
00111       if ( minNewIndexCount > newIndexCount )
00112          newIndexCount = minNewIndexCount;
00113       void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
00114       if ( !newIndexes )
00115          throw std::bad_alloc();
00116       indexCount = newIndexCount;
00117       indexes = static_cast<Value **>( newIndexes );
00118    }
00119    virtual void releaseArrayPageIndex( Value **indexes, 
00120                                        ValueInternalArray::PageIndex indexCount )
00121    {
00122       if ( indexes )
00123          free( indexes );
00124    }
00125 
00126    virtual Value *allocateArrayPage()
00127    {
00128       return static_cast<Value *>( pagesAllocator_.allocate() );
00129    }
00130 
00131    virtual void releaseArrayPage( Value *value )
00132    {
00133       if ( value )
00134          pagesAllocator_.release( value );
00135    }
00136 private:
00137    BatchAllocator<ValueInternalArray,1> arraysAllocator_;
00138    BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
00139 };
00140 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
00141 
00142 static ValueArrayAllocator *&arrayAllocator()
00143 {
00144    static DefaultValueArrayAllocator defaultAllocator;
00145    static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
00146    return arrayAllocator;
00147 }
00148 
00149 static struct DummyArrayAllocatorInitializer {
00150    DummyArrayAllocatorInitializer() 
00151    {
00152       arrayAllocator();      // ensure arrayAllocator() statics are initialized before main().
00153    }
00154 } dummyArrayAllocatorInitializer;
00155 
00156 // //////////////////////////////////////////////////////////////////
00157 // class ValueInternalArray
00158 // //////////////////////////////////////////////////////////////////
00159 bool 
00160 ValueInternalArray::equals( const IteratorState &x, 
00161                             const IteratorState &other )
00162 {
00163    return x.array_ == other.array_  
00164           &&  x.currentItemIndex_ == other.currentItemIndex_  
00165           &&  x.currentPageIndex_ == other.currentPageIndex_;
00166 }
00167 
00168 
00169 void 
00170 ValueInternalArray::increment( IteratorState &it )
00171 {
00172    JSON_ASSERT_MESSAGE( it.array_  &&
00173       (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
00174       != it.array_->size_,
00175       "ValueInternalArray::increment(): moving iterator beyond end" );
00176    ++(it.currentItemIndex_);
00177    if ( it.currentItemIndex_ == itemsPerPage )
00178    {
00179       it.currentItemIndex_ = 0;
00180       ++(it.currentPageIndex_);
00181    }
00182 }
00183 
00184 
00185 void 
00186 ValueInternalArray::decrement( IteratorState &it )
00187 {
00188    JSON_ASSERT_MESSAGE( it.array_  &&  it.currentPageIndex_ == it.array_->pages_ 
00189                         &&  it.currentItemIndex_ == 0,
00190       "ValueInternalArray::decrement(): moving iterator beyond end" );
00191    if ( it.currentItemIndex_ == 0 )
00192    {
00193       it.currentItemIndex_ = itemsPerPage-1;
00194       --(it.currentPageIndex_);
00195    }
00196    else
00197    {
00198       --(it.currentItemIndex_);
00199    }
00200 }
00201 
00202 
00203 Value &
00204 ValueInternalArray::unsafeDereference( const IteratorState &it )
00205 {
00206    return (*(it.currentPageIndex_))[it.currentItemIndex_];
00207 }
00208 
00209 
00210 Value &
00211 ValueInternalArray::dereference( const IteratorState &it )
00212 {
00213    JSON_ASSERT_MESSAGE( it.array_  &&
00214       (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
00215       < it.array_->size_,
00216       "ValueInternalArray::dereference(): dereferencing invalid iterator" );
00217    return unsafeDereference( it );
00218 }
00219 
00220 void 
00221 ValueInternalArray::makeBeginIterator( IteratorState &it ) const
00222 {
00223    it.array_ = const_cast<ValueInternalArray *>( this );
00224    it.currentItemIndex_ = 0;
00225    it.currentPageIndex_ = pages_;
00226 }
00227 
00228 
00229 void 
00230 ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
00231 {
00232    it.array_ = const_cast<ValueInternalArray *>( this );
00233    it.currentItemIndex_ = index % itemsPerPage;
00234    it.currentPageIndex_ = pages_ + index / itemsPerPage;
00235 }
00236 
00237 
00238 void 
00239 ValueInternalArray::makeEndIterator( IteratorState &it ) const
00240 {
00241    makeIterator( it, size_ );
00242 }
00243 
00244 
00245 ValueInternalArray::ValueInternalArray()
00246    : pages_( 0 )
00247    , size_( 0 )
00248    , pageCount_( 0 )
00249 {
00250 }
00251 
00252 
00253 ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
00254    : pages_( 0 )
00255    , pageCount_( 0 )
00256    , size_( other.size_ )
00257 {
00258    PageIndex minNewPages = other.size_ / itemsPerPage;
00259    arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
00260    JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, 
00261                         "ValueInternalArray::reserve(): bad reallocation" );
00262    IteratorState itOther;
00263    other.makeBeginIterator( itOther );
00264    Value *value;
00265    for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
00266    {
00267       if ( index % itemsPerPage == 0 )
00268       {
00269          PageIndex pageIndex = index / itemsPerPage;
00270          value = arrayAllocator()->allocateArrayPage();
00271          pages_[pageIndex] = value;
00272       }
00273       new (value) Value( dereference( itOther ) );
00274    }
00275 }
00276 
00277 
00278 ValueInternalArray &
00279 ValueInternalArray::operator =( const ValueInternalArray &other )
00280 {
00281    ValueInternalArray temp( other );
00282    swap( temp );
00283    return *this;
00284 }
00285 
00286 
00287 ValueInternalArray::~ValueInternalArray()
00288 {
00289    // destroy all constructed items
00290    IteratorState it;
00291    IteratorState itEnd;
00292    makeBeginIterator( it);
00293    makeEndIterator( itEnd );
00294    for ( ; !equals(it,itEnd); increment(it) )
00295    {
00296       Value *value = &dereference(it);
00297       value->~Value();
00298    }
00299    // release all pages
00300    PageIndex lastPageIndex = size_ / itemsPerPage;
00301    for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
00302       arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
00303    // release pages index
00304    arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
00305 }
00306 
00307 
00308 void 
00309 ValueInternalArray::swap( ValueInternalArray &other )
00310 {
00311    Value **tempPages = pages_;
00312    pages_ = other.pages_;
00313    other.pages_ = tempPages;
00314    ArrayIndex tempSize = size_;
00315    size_ = other.size_;
00316    other.size_ = tempSize;
00317    PageIndex tempPageCount = pageCount_;
00318    pageCount_ = other.pageCount_;
00319    other.pageCount_ = tempPageCount;
00320 }
00321 
00322 void 
00323 ValueInternalArray::clear()
00324 {
00325    ValueInternalArray dummy;
00326    swap( dummy );
00327 }
00328 
00329 
00330 void 
00331 ValueInternalArray::resize( ArrayIndex newSize )
00332 {
00333    if ( newSize == 0 )
00334       clear();
00335    else if ( newSize < size_ )
00336    {
00337       IteratorState it;
00338       IteratorState itEnd;
00339       makeIterator( it, newSize );
00340       makeIterator( itEnd, size_ );
00341       for ( ; !equals(it,itEnd); increment(it) )
00342       {
00343          Value *value = &dereference(it);
00344          value->~Value();
00345       }
00346       PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
00347       PageIndex lastPageIndex = size_ / itemsPerPage;
00348       for ( ; pageIndex < lastPageIndex; ++pageIndex )
00349          arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
00350       size_ = newSize;
00351    }
00352    else if ( newSize > size_ )
00353       resolveReference( newSize );
00354 }
00355 
00356 
00357 void 
00358 ValueInternalArray::makeIndexValid( ArrayIndex index )
00359 {
00360    // Need to enlarge page index ?
00361    if ( index >= pageCount_ * itemsPerPage )
00362    {
00363       PageIndex minNewPages = (index + 1) / itemsPerPage;
00364       arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
00365       JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
00366    }
00367 
00368    // Need to allocate new pages ?
00369    ArrayIndex nextPageIndex = 
00370       (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
00371                                   : size_;
00372    if ( nextPageIndex <= index )
00373    {
00374       PageIndex pageIndex = nextPageIndex / itemsPerPage;
00375       PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
00376       for ( ; pageToAllocate-- > 0; ++pageIndex )
00377          pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
00378    }
00379 
00380    // Initialize all new entries
00381    IteratorState it;
00382    IteratorState itEnd;
00383    makeIterator( it, size_ );
00384    size_ = index + 1;
00385    makeIterator( itEnd, size_ );
00386    for ( ; !equals(it,itEnd); increment(it) )
00387    {
00388       Value *value = &dereference(it);
00389       new (value) Value(); // Construct a default value using placement new
00390    }
00391 }
00392 
00393 Value &
00394 ValueInternalArray::resolveReference( ArrayIndex index )
00395 {
00396    if ( index >= size_ )
00397       makeIndexValid( index );
00398    return pages_[index/itemsPerPage][index%itemsPerPage];
00399 }
00400 
00401 Value *
00402 ValueInternalArray::find( ArrayIndex index ) const
00403 {
00404    if ( index >= size_ )
00405       return 0;
00406    return &(pages_[index/itemsPerPage][index%itemsPerPage]);
00407 }
00408 
00409 ValueInternalArray::ArrayIndex 
00410 ValueInternalArray::size() const
00411 {
00412    return size_;
00413 }
00414 
00415 int 
00416 ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
00417 {
00418    return indexOf(y) - indexOf(x);
00419 }
00420 
00421 
00422 ValueInternalArray::ArrayIndex 
00423 ValueInternalArray::indexOf( const IteratorState &iterator )
00424 {
00425    if ( !iterator.array_ )
00426       return ArrayIndex(-1);
00427    return ArrayIndex(
00428       (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage 
00429       + iterator.currentItemIndex_ );
00430 }
00431 
00432 
00433 int 
00434 ValueInternalArray::compare( const ValueInternalArray &other ) const
00435 {
00436    int sizeDiff( size_ - other.size_ );
00437    if ( sizeDiff != 0 )
00438       return sizeDiff;
00439    
00440    for ( ArrayIndex index =0; index < size_; ++index )
00441    {
00442       int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare( 
00443          other.pages_[index/itemsPerPage][index%itemsPerPage] );
00444       if ( diff != 0 )
00445          return diff;
00446    }
00447    return 0;
00448 }

SourceForge Logo hosts this site. Send comments to:
Json-cpp Developers