Drizzled Public API Documentation

json_internalarray.inl
1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
2  *
3  * JSON Library, originally from http://jsoncpp.sourceforge.net/
4  *
5  * Copyright (C) 2011 Stewart Smith
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions are
10  * met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following disclaimer
17  * in the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * * The names of its contributors may not be used to endorse or
21  * promote products derived from this software without specific prior
22  * written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  *
36  */
37 
38 #pragma once
39 // included by json_value.cpp
40 // everything is within Json namespace
41 
42 // //////////////////////////////////////////////////////////////////
43 // //////////////////////////////////////////////////////////////////
44 // //////////////////////////////////////////////////////////////////
45 // class ValueInternalArray
46 // //////////////////////////////////////////////////////////////////
47 // //////////////////////////////////////////////////////////////////
48 // //////////////////////////////////////////////////////////////////
49 
50 ValueArrayAllocator::~ValueArrayAllocator()
51 {
52 }
53 
54 // //////////////////////////////////////////////////////////////////
55 // class DefaultValueArrayAllocator
56 // //////////////////////////////////////////////////////////////////
57 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
58 class DefaultValueArrayAllocator : public ValueArrayAllocator
59 {
60 public: // overridden from ValueArrayAllocator
62  {
63  }
64 
65  virtual ValueInternalArray *newArray()
66  {
67  return new ValueInternalArray();
68  }
69 
70  virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
71  {
72  return new ValueInternalArray( other );
73  }
74 
75  virtual void destructArray( ValueInternalArray *array )
76  {
77  delete array;
78  }
79 
80  virtual void reallocateArrayPageIndex( Value **&indexes,
81  ValueInternalArray::PageIndex &indexCount,
82  ValueInternalArray::PageIndex minNewIndexCount )
83  {
84  ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
85  if ( minNewIndexCount > newIndexCount )
86  newIndexCount = minNewIndexCount;
87  void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
88  if ( !newIndexes )
89  throw std::bad_alloc();
90  indexCount = newIndexCount;
91  indexes = static_cast<Value **>( newIndexes );
92  }
93  virtual void releaseArrayPageIndex( Value **indexes,
94  ValueInternalArray::PageIndex indexCount )
95  {
96  free( indexes );
97  }
98 
99  virtual Value *allocateArrayPage()
100  {
101  return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
102  }
103 
104  virtual void releaseArrayPage( Value *value )
105  {
106  free( value );
107  }
108 };
109 
110 #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
111 
112 class DefaultValueArrayAllocator : public ValueArrayAllocator
113 {
114 public: // overridden from ValueArrayAllocator
115  virtual ~DefaultValueArrayAllocator()
116  {
117  }
118 
119  virtual ValueInternalArray *newArray()
120  {
121  ValueInternalArray *array = arraysAllocator_.allocate();
122  new (array) ValueInternalArray(); // placement new
123  return array;
124  }
125 
126  virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
127  {
128  ValueInternalArray *array = arraysAllocator_.allocate();
129  new (array) ValueInternalArray( other ); // placement new
130  return array;
131  }
132 
133  virtual void destructArray( ValueInternalArray *array )
134  {
135  if ( array )
136  {
137  array->~ValueInternalArray();
138  arraysAllocator_.release( array );
139  }
140  }
141 
142  virtual void reallocateArrayPageIndex( Value **&indexes,
143  ValueInternalArray::PageIndex &indexCount,
144  ValueInternalArray::PageIndex minNewIndexCount )
145  {
146  ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
147  if ( minNewIndexCount > newIndexCount )
148  newIndexCount = minNewIndexCount;
149  void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
150  if ( !newIndexes )
151  throw std::bad_alloc();
152  indexCount = newIndexCount;
153  indexes = static_cast<Value **>( newIndexes );
154  }
155  virtual void releaseArrayPageIndex( Value **indexes,
156  ValueInternalArray::PageIndex indexCount )
157  {
158  free( indexes );
159  }
160 
161  virtual Value *allocateArrayPage()
162  {
163  return static_cast<Value *>( pagesAllocator_.allocate() );
164  }
165 
166  virtual void releaseArrayPage( Value *value )
167  {
168  if ( value )
169  pagesAllocator_.release( value );
170  }
171 private:
172  BatchAllocator<ValueInternalArray,1> arraysAllocator_;
173  BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
174 };
175 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
176 
177 static ValueArrayAllocator *&arrayAllocator()
178 {
179  static DefaultValueArrayAllocator defaultAllocator;
180  static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
181  return arrayAllocator;
182 }
183 
186  {
187  arrayAllocator(); // ensure arrayAllocator() statics are initialized before main().
188  }
189 } dummyArrayAllocatorInitializer;
190 
191 // //////////////////////////////////////////////////////////////////
192 // class ValueInternalArray
193 // //////////////////////////////////////////////////////////////////
194 bool
195 ValueInternalArray::equals( const IteratorState &x,
196  const IteratorState &other )
197 {
198  return x.array_ == other.array_
199  && x.currentItemIndex_ == other.currentItemIndex_
200  && x.currentPageIndex_ == other.currentPageIndex_;
201 }
202 
203 
204 void
205 ValueInternalArray::increment( IteratorState &it )
206 {
207  JSON_ASSERT_MESSAGE( it.array_ &&
208  (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
209  != it.array_->size_,
210  "ValueInternalArray::increment(): moving iterator beyond end" );
211  ++(it.currentItemIndex_);
212  if ( it.currentItemIndex_ == itemsPerPage )
213  {
214  it.currentItemIndex_ = 0;
215  ++(it.currentPageIndex_);
216  }
217 }
218 
219 
220 void
221 ValueInternalArray::decrement( IteratorState &it )
222 {
223  JSON_ASSERT_MESSAGE( it.array_ && it.currentPageIndex_ == it.array_->pages_
224  && it.currentItemIndex_ == 0,
225  "ValueInternalArray::decrement(): moving iterator beyond end" );
226  if ( it.currentItemIndex_ == 0 )
227  {
228  it.currentItemIndex_ = itemsPerPage-1;
229  --(it.currentPageIndex_);
230  }
231  else
232  {
233  --(it.currentItemIndex_);
234  }
235 }
236 
237 
238 Value &
239 ValueInternalArray::unsafeDereference( const IteratorState &it )
240 {
241  return (*(it.currentPageIndex_))[it.currentItemIndex_];
242 }
243 
244 
245 Value &
246 ValueInternalArray::dereference( const IteratorState &it )
247 {
248  JSON_ASSERT_MESSAGE( it.array_ &&
249  (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
250  < it.array_->size_,
251  "ValueInternalArray::dereference(): dereferencing invalid iterator" );
252  return unsafeDereference( it );
253 }
254 
255 void
256 ValueInternalArray::makeBeginIterator( IteratorState &it ) const
257 {
258  it.array_ = const_cast<ValueInternalArray *>( this );
259  it.currentItemIndex_ = 0;
260  it.currentPageIndex_ = pages_;
261 }
262 
263 
264 void
265 ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
266 {
267  it.array_ = const_cast<ValueInternalArray *>( this );
268  it.currentItemIndex_ = index % itemsPerPage;
269  it.currentPageIndex_ = pages_ + index / itemsPerPage;
270 }
271 
272 
273 void
274 ValueInternalArray::makeEndIterator( IteratorState &it ) const
275 {
276  makeIterator( it, size_ );
277 }
278 
279 
280 ValueInternalArray::ValueInternalArray()
281  : pages_( 0 )
282  , size_( 0 )
283  , pageCount_( 0 )
284 {
285 }
286 
287 
288 ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
289  : pages_( 0 )
290  , pageCount_( 0 )
291  , size_( other.size_ )
292 {
293  PageIndex minNewPages = other.size_ / itemsPerPage;
294  arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
295  JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages,
296  "ValueInternalArray::reserve(): bad reallocation" );
297  IteratorState itOther;
298  other.makeBeginIterator( itOther );
299  Value *value;
300  for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
301  {
302  if ( index % itemsPerPage == 0 )
303  {
304  PageIndex pageIndex = index / itemsPerPage;
305  value = arrayAllocator()->allocateArrayPage();
306  pages_[pageIndex] = value;
307  }
308  new (value) Value( dereference( itOther ) );
309  }
310 }
311 
312 
313 ValueInternalArray &
314 ValueInternalArray::operator =( const ValueInternalArray &other )
315 {
316  ValueInternalArray temp( other );
317  swap( temp );
318  return *this;
319 }
320 
321 
322 ValueInternalArray::~ValueInternalArray()
323 {
324  // destroy all constructed items
325  IteratorState it;
326  IteratorState itEnd;
327  makeBeginIterator( it);
328  makeEndIterator( itEnd );
329  for ( ; !equals(it,itEnd); increment(it) )
330  {
331  Value *value = &dereference(it);
332  value->~Value();
333  }
334  // release all pages
335  PageIndex lastPageIndex = size_ / itemsPerPage;
336  for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
337  arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
338  // release pages index
339  arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
340 }
341 
342 
343 void
344 ValueInternalArray::swap( ValueInternalArray &other )
345 {
346  Value **tempPages = pages_;
347  pages_ = other.pages_;
348  other.pages_ = tempPages;
349  ArrayIndex tempSize = size_;
350  size_ = other.size_;
351  other.size_ = tempSize;
352  PageIndex tempPageCount = pageCount_;
353  pageCount_ = other.pageCount_;
354  other.pageCount_ = tempPageCount;
355 }
356 
357 void
358 ValueInternalArray::clear()
359 {
360  ValueInternalArray dummy;
361  swap( dummy );
362 }
363 
364 
365 void
366 ValueInternalArray::resize( ArrayIndex newSize )
367 {
368  if ( newSize == 0 )
369  clear();
370  else if ( newSize < size_ )
371  {
372  IteratorState it;
373  IteratorState itEnd;
374  makeIterator( it, newSize );
375  makeIterator( itEnd, size_ );
376  for ( ; !equals(it,itEnd); increment(it) )
377  {
378  Value *value = &dereference(it);
379  value->~Value();
380  }
381  PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
382  PageIndex lastPageIndex = size_ / itemsPerPage;
383  for ( ; pageIndex < lastPageIndex; ++pageIndex )
384  arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
385  size_ = newSize;
386  }
387  else if ( newSize > size_ )
388  resolveReference( newSize );
389 }
390 
391 
392 void
393 ValueInternalArray::makeIndexValid( ArrayIndex index )
394 {
395  // Need to enlarge page index ?
396  if ( index >= pageCount_ * itemsPerPage )
397  {
398  PageIndex minNewPages = (index + 1) / itemsPerPage;
399  arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
400  JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
401  }
402 
403  // Need to allocate new pages ?
404  ArrayIndex nextPageIndex =
405  (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
406  : size_;
407  if ( nextPageIndex <= index )
408  {
409  PageIndex pageIndex = nextPageIndex / itemsPerPage;
410  PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
411  for ( ; pageToAllocate-- > 0; ++pageIndex )
412  pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
413  }
414 
415  // Initialize all new entries
416  IteratorState it;
417  IteratorState itEnd;
418  makeIterator( it, size_ );
419  size_ = index + 1;
420  makeIterator( itEnd, size_ );
421  for ( ; !equals(it,itEnd); increment(it) )
422  {
423  Value *value = &dereference(it);
424  new (value) Value(); // Construct a default value using placement new
425  }
426 }
427 
428 Value &
429 ValueInternalArray::resolveReference( ArrayIndex index )
430 {
431  if ( index >= size_ )
432  makeIndexValid( index );
433  return pages_[index/itemsPerPage][index%itemsPerPage];
434 }
435 
436 Value *
437 ValueInternalArray::find( ArrayIndex index ) const
438 {
439  if ( index >= size_ )
440  return 0;
441  return &(pages_[index/itemsPerPage][index%itemsPerPage]);
442 }
443 
444 ValueInternalArray::ArrayIndex
445 ValueInternalArray::size() const
446 {
447  return size_;
448 }
449 
450 int
451 ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
452 {
453  return indexOf(y) - indexOf(x);
454 }
455 
456 
457 ValueInternalArray::ArrayIndex
458 ValueInternalArray::indexOf( const IteratorState &iterator )
459 {
460  if ( !iterator.array_ )
461  return ArrayIndex(-1);
462  return ArrayIndex(
463  (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage
464  + iterator.currentItemIndex_ );
465 }
466 
467 
468 int
469 ValueInternalArray::compare( const ValueInternalArray &other ) const
470 {
471  int sizeDiff( size_ - other.size_ );
472  if ( sizeDiff != 0 )
473  return sizeDiff;
474 
475  for ( ArrayIndex index =0; index < size_; ++index )
476  {
477  int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare(
478  other.pages_[index/itemsPerPage][index%itemsPerPage] );
479  if ( diff != 0 )
480  return diff;
481  }
482  return 0;
483 }