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