src/third_party/jsoncpp/json_internalarray.inl

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