JsonCpp project page JsonCpp home page

json_internalarray.inl
Go to the documentation of this file.
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 
8 namespace Json {
9 
10 // //////////////////////////////////////////////////////////////////
11 // //////////////////////////////////////////////////////////////////
12 // //////////////////////////////////////////////////////////////////
13 // class ValueInternalArray
14 // //////////////////////////////////////////////////////////////////
15 // //////////////////////////////////////////////////////////////////
16 // //////////////////////////////////////////////////////////////////
17 
19 {
20 }
21 
22 // //////////////////////////////////////////////////////////////////
23 // class DefaultValueArrayAllocator
24 // //////////////////////////////////////////////////////////////////
25 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
26 class DefaultValueArrayAllocator : public ValueArrayAllocator
27 {
28 public: // 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,
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  if ( !newIndexes )
57  throw std::bad_alloc();
58  indexCount = newIndexCount;
59  indexes = static_cast<Value **>( newIndexes );
60  }
61  virtual void releaseArrayPageIndex( Value **indexes,
63  {
64  if ( indexes )
65  free( indexes );
66  }
67 
68  virtual Value *allocateArrayPage()
69  {
70  return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
71  }
72 
73  virtual void releaseArrayPage( Value *value )
74  {
75  if ( value )
76  free( value );
77  }
78 };
79 
80 #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
81 class DefaultValueArrayAllocator : public ValueArrayAllocator
83 {
84 public: // overridden from ValueArrayAllocator
85  virtual ~DefaultValueArrayAllocator()
86  {
87  }
88 
89  virtual ValueInternalArray *newArray()
90  {
91  ValueInternalArray *array = arraysAllocator_.allocate();
92  new (array) ValueInternalArray(); // placement new
93  return array;
94  }
95 
96  virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
97  {
98  ValueInternalArray *array = arraysAllocator_.allocate();
99  new (array) ValueInternalArray( other ); // placement new
100  return array;
101  }
102 
103  virtual void destructArray( ValueInternalArray *array )
104  {
105  if ( array )
106  {
107  array->~ValueInternalArray();
108  arraysAllocator_.release( array );
109  }
110  }
111 
112  virtual void reallocateArrayPageIndex( Value **&indexes,
113  ValueInternalArray::PageIndex &indexCount,
114  ValueInternalArray::PageIndex minNewIndexCount )
115  {
116  ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
117  if ( minNewIndexCount > newIndexCount )
118  newIndexCount = minNewIndexCount;
119  void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
120  if ( !newIndexes )
121  throw std::bad_alloc();
122  indexCount = newIndexCount;
123  indexes = static_cast<Value **>( newIndexes );
124  }
125  virtual void releaseArrayPageIndex( Value **indexes,
126  ValueInternalArray::PageIndex indexCount )
127  {
128  if ( indexes )
129  free( indexes );
130  }
131 
132  virtual Value *allocateArrayPage()
133  {
134  return static_cast<Value *>( pagesAllocator_.allocate() );
135  }
136 
137  virtual void releaseArrayPage( Value *value )
138  {
139  if ( value )
140  pagesAllocator_.release( value );
141  }
142 private:
143  BatchAllocator<ValueInternalArray,1> arraysAllocator_;
144  BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
145 };
146 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
147 
149 {
150  static DefaultValueArrayAllocator defaultAllocator;
151  static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
152  return arrayAllocator;
153 }
154 
155 static struct DummyArrayAllocatorInitializer {
156  DummyArrayAllocatorInitializer()
157  {
158  arrayAllocator(); // ensure arrayAllocator() statics are initialized before main().
159  }
161 
162 // //////////////////////////////////////////////////////////////////
163 // class ValueInternalArray
164 // //////////////////////////////////////////////////////////////////
165 bool
166 ValueInternalArray::equals( const IteratorState &x,
167  const IteratorState &other )
168 {
169  return x.array_ == other.array_
170  && x.currentItemIndex_ == other.currentItemIndex_
171  && x.currentPageIndex_ == other.currentPageIndex_;
172 }
173 
174 
175 void
176 ValueInternalArray::increment( IteratorState &it )
177 {
178  JSON_ASSERT_MESSAGE( it.array_ &&
179  (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
180  != it.array_->size_,
181  "ValueInternalArray::increment(): moving iterator beyond end" );
182  ++(it.currentItemIndex_);
183  if ( it.currentItemIndex_ == itemsPerPage )
184  {
185  it.currentItemIndex_ = 0;
186  ++(it.currentPageIndex_);
187  }
188 }
189 
190 
191 void
192 ValueInternalArray::decrement( IteratorState &it )
193 {
194  JSON_ASSERT_MESSAGE( it.array_ && it.currentPageIndex_ == it.array_->pages_
195  && it.currentItemIndex_ == 0,
196  "ValueInternalArray::decrement(): moving iterator beyond end" );
197  if ( it.currentItemIndex_ == 0 )
198  {
199  it.currentItemIndex_ = itemsPerPage-1;
200  --(it.currentPageIndex_);
201  }
202  else
203  {
204  --(it.currentItemIndex_);
205  }
206 }
207 
208 
209 Value &
210 ValueInternalArray::unsafeDereference( const IteratorState &it )
211 {
212  return (*(it.currentPageIndex_))[it.currentItemIndex_];
213 }
214 
215 
216 Value &
217 ValueInternalArray::dereference( const IteratorState &it )
218 {
219  JSON_ASSERT_MESSAGE( it.array_ &&
220  (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
221  < it.array_->size_,
222  "ValueInternalArray::dereference(): dereferencing invalid iterator" );
223  return unsafeDereference( it );
224 }
225 
226 void
227 ValueInternalArray::makeBeginIterator( IteratorState &it ) const
228 {
229  it.array_ = const_cast<ValueInternalArray *>( this );
230  it.currentItemIndex_ = 0;
231  it.currentPageIndex_ = pages_;
232 }
233 
234 
235 void
236 ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
237 {
238  it.array_ = const_cast<ValueInternalArray *>( this );
239  it.currentItemIndex_ = index % itemsPerPage;
240  it.currentPageIndex_ = pages_ + index / itemsPerPage;
241 }
242 
243 
244 void
245 ValueInternalArray::makeEndIterator( IteratorState &it ) const
246 {
247  makeIterator( it, size_ );
248 }
249 
250 
252  : pages_( 0 )
253  , size_( 0 )
254  , pageCount_( 0 )
255 {
256 }
257 
258 
260  : pages_( 0 )
261  , pageCount_( 0 )
262  , size_( other.size_ )
263 {
264  PageIndex minNewPages = other.size_ / itemsPerPage;
265  arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
266  JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages,
267  "ValueInternalArray::reserve(): bad reallocation" );
268  IteratorState itOther;
269  other.makeBeginIterator( itOther );
270  Value *value;
271  for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
272  {
273  if ( index % itemsPerPage == 0 )
274  {
275  PageIndex pageIndex = index / itemsPerPage;
276  value = arrayAllocator()->allocateArrayPage();
277  pages_[pageIndex] = value;
278  }
279  new (value) Value( dereference( itOther ) );
280  }
281 }
282 
283 
286 {
287  ValueInternalArray temp( other );
288  swap( temp );
289  return *this;
290 }
291 
292 
294 {
295  // destroy all constructed items
296  IteratorState it;
297  IteratorState itEnd;
298  makeBeginIterator( it);
299  makeEndIterator( itEnd );
300  for ( ; !equals(it,itEnd); increment(it) )
301  {
302  Value *value = &dereference(it);
303  value->~Value();
304  }
305  // release all pages
306  PageIndex lastPageIndex = size_ / itemsPerPage;
307  for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
308  arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
309  // release pages index
310  arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
311 }
312 
313 
314 void
316 {
317  Value **tempPages = pages_;
318  pages_ = other.pages_;
319  other.pages_ = tempPages;
320  ArrayIndex tempSize = size_;
321  size_ = other.size_;
322  other.size_ = tempSize;
323  PageIndex tempPageCount = pageCount_;
324  pageCount_ = other.pageCount_;
325  other.pageCount_ = tempPageCount;
326 }
327 
328 void
330 {
331  ValueInternalArray dummy;
332  swap( dummy );
333 }
334 
335 
336 void
338 {
339  if ( newSize == 0 )
340  clear();
341  else if ( newSize < size_ )
342  {
343  IteratorState it;
344  IteratorState itEnd;
345  makeIterator( it, newSize );
346  makeIterator( itEnd, size_ );
347  for ( ; !equals(it,itEnd); increment(it) )
348  {
349  Value *value = &dereference(it);
350  value->~Value();
351  }
352  PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
353  PageIndex lastPageIndex = size_ / itemsPerPage;
354  for ( ; pageIndex < lastPageIndex; ++pageIndex )
355  arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
356  size_ = newSize;
357  }
358  else if ( newSize > size_ )
359  resolveReference( newSize );
360 }
361 
362 
363 void
364 ValueInternalArray::makeIndexValid( ArrayIndex index )
365 {
366  // Need to enlarge page index ?
367  if ( index >= pageCount_ * itemsPerPage )
368  {
369  PageIndex minNewPages = (index + 1) / itemsPerPage;
370  arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
371  JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
372  }
373 
374  // Need to allocate new pages ?
375  ArrayIndex nextPageIndex =
376  (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
377  : size_;
378  if ( nextPageIndex <= index )
379  {
380  PageIndex pageIndex = nextPageIndex / itemsPerPage;
381  PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
382  for ( ; pageToAllocate-- > 0; ++pageIndex )
383  pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
384  }
385 
386  // Initialize all new entries
387  IteratorState it;
388  IteratorState itEnd;
389  makeIterator( it, size_ );
390  size_ = index + 1;
391  makeIterator( itEnd, size_ );
392  for ( ; !equals(it,itEnd); increment(it) )
393  {
394  Value *value = &dereference(it);
395  new (value) Value(); // Construct a default value using placement new
396  }
397 }
398 
399 Value &
401 {
402  if ( index >= size_ )
403  makeIndexValid( index );
404  return pages_[index/itemsPerPage][index%itemsPerPage];
405 }
406 
407 Value *
409 {
410  if ( index >= size_ )
411  return 0;
412  return &(pages_[index/itemsPerPage][index%itemsPerPage]);
413 }
414 
417 {
418  return size_;
419 }
420 
421 int
422 ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
423 {
424  return indexOf(y) - indexOf(x);
425 }
426 
427 
429 ValueInternalArray::indexOf( const IteratorState &iterator )
430 {
431  if ( !iterator.array_ )
432  return ArrayIndex(-1);
433  return ArrayIndex(
434  (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage
435  + iterator.currentItemIndex_ );
436 }
437 
438 
439 int
441 {
442  int sizeDiff( size_ - other.size_ );
443  if ( sizeDiff != 0 )
444  return sizeDiff;
445 
446  for ( ArrayIndex index =0; index < size_; ++index )
447  {
448  int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare(
449  other.pages_[index/itemsPerPage][index%itemsPerPage] );
450  if ( diff != 0 )
451  return diff;
452  }
453  return 0;
454 }
455 
456 } // namespace Json
Experimental: do not use.
Definition: value.h:881
int compare(const ValueInternalArray &other) const
unsigned int ArrayIndex
Definition: forwards.h:23
Value & resolveReference(ArrayIndex index)
unsigned int PageIndex
Definition: value.h:769
virtual void reallocateArrayPageIndex(Value **&indexes, ValueInternalArray::PageIndex &indexCount, ValueInternalArray::PageIndex minNewIndexCount)=0
Reallocate array page index.
int compare(const Value &other) const
Definition: json_value.cpp:527
static struct Json::DummyArrayAllocatorInitializer dummyArrayAllocatorInitializer
Value::ArrayIndex ArrayIndex
Definition: value.h:768
static ValueArrayAllocator *& arrayAllocator()
void swap(ValueInternalArray &other)
ValueInternalArray & operator=(const ValueInternalArray &other)
#define JSON_ASSERT_MESSAGE(condition, message)
Definition: json_value.cpp:26
void resize(ArrayIndex newSize)
JSON (JavaScript Object Notation).
Definition: config.h:73
friend class Value
Definition: value.h:764
Value * find(ArrayIndex index) const
A simplified deque implementation used internally by Value.
Definition: value.h:762
Represents a JSON value.
Definition: value.h:118
virtual Value * allocateArrayPage()=0
virtual void releaseArrayPage(Value *value)=0
virtual void releaseArrayPageIndex(Value **indexes, ValueInternalArray::PageIndex indexCount)=0

SourceForge Logo hosts this site. Send comments to:
Json-cpp Developers