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
6 // included by json_value.cpp
7 // everything is within Json namespace
9 // //////////////////////////////////////////////////////////////////
10 // //////////////////////////////////////////////////////////////////
11 // //////////////////////////////////////////////////////////////////
12 // class ValueInternalArray
13 // //////////////////////////////////////////////////////////////////
14 // //////////////////////////////////////////////////////////////////
15 // //////////////////////////////////////////////////////////////////
17 ValueArrayAllocator::~ValueArrayAllocator()
21 // //////////////////////////////////////////////////////////////////
22 // class DefaultValueArrayAllocator
23 // //////////////////////////////////////////////////////////////////
24 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
25 class DefaultValueArrayAllocator : public ValueArrayAllocator
27 public: // overridden from ValueArrayAllocator
28 virtual ~DefaultValueArrayAllocator()
32 virtual ValueInternalArray *newArray()
34 return new ValueInternalArray();
37 virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
39 return new ValueInternalArray( other );
42 virtual void destructArray( ValueInternalArray *array )
47 virtual void reallocateArrayPageIndex( Value **&indexes,
48 ValueInternalArray::PageIndex &indexCount,
49 ValueInternalArray::PageIndex minNewIndexCount )
51 ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
52 if ( minNewIndexCount > newIndexCount )
53 newIndexCount = minNewIndexCount;
54 void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
56 throw std::bad_alloc();
57 indexCount = newIndexCount;
58 indexes = static_cast<Value **>( newIndexes );
60 virtual void releaseArrayPageIndex( Value **indexes,
61 ValueInternalArray::PageIndex indexCount )
67 virtual Value *allocateArrayPage()
69 return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
72 virtual void releaseArrayPage( Value *value )
79 #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
80 /// @todo make this thread-safe (lock when accessign batch allocator)
81 class DefaultValueArrayAllocator : public ValueArrayAllocator
83 public: // overridden from ValueArrayAllocator
84 virtual ~DefaultValueArrayAllocator()
88 virtual ValueInternalArray *newArray()
90 ValueInternalArray *array = arraysAllocator_.allocate();
91 new (array) ValueInternalArray(); // placement new
95 virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
97 ValueInternalArray *array = arraysAllocator_.allocate();
98 new (array) ValueInternalArray( other ); // placement new
102 virtual void destructArray( ValueInternalArray *array )
106 array->~ValueInternalArray();
107 arraysAllocator_.release( array );
111 virtual void reallocateArrayPageIndex( Value **&indexes,
112 ValueInternalArray::PageIndex &indexCount,
113 ValueInternalArray::PageIndex minNewIndexCount )
115 ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
116 if ( minNewIndexCount > newIndexCount )
117 newIndexCount = minNewIndexCount;
118 void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
120 throw std::bad_alloc();
121 indexCount = newIndexCount;
122 indexes = static_cast<Value **>( newIndexes );
124 virtual void releaseArrayPageIndex( Value **indexes,
125 ValueInternalArray::PageIndex indexCount )
131 virtual Value *allocateArrayPage()
133 return static_cast<Value *>( pagesAllocator_.allocate() );
136 virtual void releaseArrayPage( Value *value )
139 pagesAllocator_.release( value );
142 BatchAllocator<ValueInternalArray,1> arraysAllocator_;
143 BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
145 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
147 static ValueArrayAllocator *&arrayAllocator()
149 static DefaultValueArrayAllocator defaultAllocator;
150 static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
151 return arrayAllocator;
154 static struct DummyArrayAllocatorInitializer {
155 DummyArrayAllocatorInitializer()
157 arrayAllocator(); // ensure arrayAllocator() statics are initialized before main().
159 } dummyArrayAllocatorInitializer;
161 // //////////////////////////////////////////////////////////////////
162 // class ValueInternalArray
163 // //////////////////////////////////////////////////////////////////
165 ValueInternalArray::equals( const IteratorState &x,
166 const IteratorState &other )
168 return x.array_ == other.array_
169 && x.currentItemIndex_ == other.currentItemIndex_
170 && x.currentPageIndex_ == other.currentPageIndex_;
175 ValueInternalArray::increment( IteratorState &it )
177 JSON_ASSERT_MESSAGE( it.array_ &&
178 (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
180 "ValueInternalArray::increment(): moving iterator beyond end" );
181 ++(it.currentItemIndex_);
182 if ( it.currentItemIndex_ == itemsPerPage )
184 it.currentItemIndex_ = 0;
185 ++(it.currentPageIndex_);
191 ValueInternalArray::decrement( IteratorState &it )
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 )
198 it.currentItemIndex_ = itemsPerPage-1;
199 --(it.currentPageIndex_);
203 --(it.currentItemIndex_);
209 ValueInternalArray::unsafeDereference( const IteratorState &it )
211 return (*(it.currentPageIndex_))[it.currentItemIndex_];
216 ValueInternalArray::dereference( const IteratorState &it )
218 JSON_ASSERT_MESSAGE( it.array_ &&
219 (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
221 "ValueInternalArray::dereference(): dereferencing invalid iterator" );
222 return unsafeDereference( it );
226 ValueInternalArray::makeBeginIterator( IteratorState &it ) const
228 it.array_ = const_cast<ValueInternalArray *>( this );
229 it.currentItemIndex_ = 0;
230 it.currentPageIndex_ = pages_;
235 ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
237 it.array_ = const_cast<ValueInternalArray *>( this );
238 it.currentItemIndex_ = index % itemsPerPage;
239 it.currentPageIndex_ = pages_ + index / itemsPerPage;
244 ValueInternalArray::makeEndIterator( IteratorState &it ) const
246 makeIterator( it, size_ );
250 ValueInternalArray::ValueInternalArray()
258 ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
261 , size_( other.size_ )
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 );
270 for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
272 if ( index % itemsPerPage == 0 )
274 PageIndex pageIndex = index / itemsPerPage;
275 value = arrayAllocator()->allocateArrayPage();
276 pages_[pageIndex] = value;
278 new (value) Value( dereference( itOther ) );
284 ValueInternalArray::operator =( const ValueInternalArray &other )
286 ValueInternalArray temp( other );
292 ValueInternalArray::~ValueInternalArray()
294 // destroy all constructed items
297 makeBeginIterator( it);
298 makeEndIterator( itEnd );
299 for ( ; !equals(it,itEnd); increment(it) )
301 Value *value = &dereference(it);
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_ );
314 ValueInternalArray::swap( ValueInternalArray &other )
316 Value **tempPages = pages_;
317 pages_ = other.pages_;
318 other.pages_ = tempPages;
319 ArrayIndex tempSize = size_;
321 other.size_ = tempSize;
322 PageIndex tempPageCount = pageCount_;
323 pageCount_ = other.pageCount_;
324 other.pageCount_ = tempPageCount;
328 ValueInternalArray::clear()
330 ValueInternalArray dummy;
336 ValueInternalArray::resize( ArrayIndex newSize )
340 else if ( newSize < size_ )
344 makeIterator( it, newSize );
345 makeIterator( itEnd, size_ );
346 for ( ; !equals(it,itEnd); increment(it) )
348 Value *value = &dereference(it);
351 PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
352 PageIndex lastPageIndex = size_ / itemsPerPage;
353 for ( ; pageIndex < lastPageIndex; ++pageIndex )
354 arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
357 else if ( newSize > size_ )
358 resolveReference( newSize );
363 ValueInternalArray::makeIndexValid( ArrayIndex index )
365 // Need to enlarge page index ?
366 if ( index >= pageCount_ * itemsPerPage )
368 PageIndex minNewPages = (index + 1) / itemsPerPage;
369 arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
370 JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
373 // Need to allocate new pages ?
374 ArrayIndex nextPageIndex =
375 (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
377 if ( nextPageIndex <= index )
379 PageIndex pageIndex = nextPageIndex / itemsPerPage;
380 PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
381 for ( ; pageToAllocate-- > 0; ++pageIndex )
382 pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
385 // Initialize all new entries
388 makeIterator( it, size_ );
390 makeIterator( itEnd, size_ );
391 for ( ; !equals(it,itEnd); increment(it) )
393 Value *value = &dereference(it);
394 new (value) Value(); // Construct a default value using placement new
399 ValueInternalArray::resolveReference( ArrayIndex index )
401 if ( index >= size_ )
402 makeIndexValid( index );
403 return pages_[index/itemsPerPage][index%itemsPerPage];
407 ValueInternalArray::find( ArrayIndex index ) const
409 if ( index >= size_ )
411 return &(pages_[index/itemsPerPage][index%itemsPerPage]);
414 ValueInternalArray::ArrayIndex
415 ValueInternalArray::size() const
421 ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
423 return indexOf(y) - indexOf(x);
427 ValueInternalArray::ArrayIndex
428 ValueInternalArray::indexOf( const IteratorState &iterator )
430 if ( !iterator.array_ )
431 return ArrayIndex(-1);
433 (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage
434 + iterator.currentItemIndex_ );
439 ValueInternalArray::compare( const ValueInternalArray &other ) const
441 int sizeDiff( size_ - other.size_ );
445 for ( ArrayIndex index =0; index < size_; ++index )
447 int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare(
448 other.pages_[index/itemsPerPage][index%itemsPerPage] );