JsonCpp project page JsonCpp home page

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

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