Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 ValueArrayAllocator::~ValueArrayAllocator()
00013 {
00014 }
00015
00016
00017
00018
00019 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
00020 class DefaultValueArrayAllocator : public ValueArrayAllocator
00021 {
00022 public:
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:
00079 virtual ~DefaultValueArrayAllocator()
00080 {
00081 }
00082
00083 virtual ValueInternalArray *newArray()
00084 {
00085 ValueInternalArray *array = arraysAllocator_.allocate();
00086 new (array) ValueInternalArray();
00087 return array;
00088 }
00089
00090 virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
00091 {
00092 ValueInternalArray *array = arraysAllocator_.allocate();
00093 new (array) ValueInternalArray( other );
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();
00153 }
00154 } dummyArrayAllocatorInitializer;
00155
00156
00157
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
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
00300 PageIndex lastPageIndex = size_ / itemsPerPage;
00301 for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
00302 arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
00303
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
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
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
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();
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 }