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