~drizzle-trunk/drizzle/development : contents of plugin/json_server/json/json

~drizzle-trunk/drizzle/development : (revision 2310)

/*  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 * 
 *  JSON Library, originally from http://jsoncpp.sourceforge.net/
 *
 *  Copyright (C) 2011 Stewart Smith
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are
 *  met:
 *
 *      * Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 *
 *      * Redistributions in binary form must reproduce the above
 *  copyright notice, this list of conditions and the following disclaimer
 *  in the documentation and/or other materials provided with the
 *  distribution.
 *
 *      * The names of its contributors may not be used to endorse or
 *  promote products derived from this software without specific prior
 *  written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#pragma once
// included by json_value.cpp
// everything is within Json namespace

// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// class ValueInternalArray
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////

ValueArrayAllocator::~ValueArrayAllocator()
{
}

// //////////////////////////////////////////////////////////////////
// class DefaultValueArrayAllocator
// //////////////////////////////////////////////////////////////////
#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
class DefaultValueArrayAllocator : public ValueArrayAllocator
{
public: // overridden from ValueArrayAllocator
   virtual ~DefaultValueArrayAllocator()
   {
   }

   virtual ValueInternalArray *newArray()
   {
      return new ValueInternalArray();
   }

   virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
   {
      return new ValueInternalArray( other );
   }

   virtual void destructArray( ValueInternalArray *array )
   {
      delete array;
   }

   virtual void reallocateArrayPageIndex( Value **&indexes, 
                                          ValueInternalArray::PageIndex &indexCount,
                                          ValueInternalArray::PageIndex minNewIndexCount )
   {
      ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
      if ( minNewIndexCount > newIndexCount )
         newIndexCount = minNewIndexCount;
      void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
      if ( !newIndexes )
         throw std::bad_alloc();
      indexCount = newIndexCount;
      indexes = static_cast<Value **>( newIndexes );
   }
   virtual void releaseArrayPageIndex( Value **indexes, 
                                       ValueInternalArray::PageIndex indexCount )
   {
      if ( indexes )
         free( indexes );
   }

   virtual Value *allocateArrayPage()
   {
      return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
   }

   virtual void releaseArrayPage( Value *value )
   {
      if ( value )
         free( value );
   }
};

#else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
/// @todo make this thread-safe (lock when accessign batch allocator)
class DefaultValueArrayAllocator : public ValueArrayAllocator
{
public: // overridden from ValueArrayAllocator
   virtual ~DefaultValueArrayAllocator()
   {
   }

   virtual ValueInternalArray *newArray()
   {
      ValueInternalArray *array = arraysAllocator_.allocate();
      new (array) ValueInternalArray(); // placement new
      return array;
   }

   virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
   {
      ValueInternalArray *array = arraysAllocator_.allocate();
      new (array) ValueInternalArray( other ); // placement new
      return array;
   }

   virtual void destructArray( ValueInternalArray *array )
   {
      if ( array )
      {
         array->~ValueInternalArray();
         arraysAllocator_.release( array );
      }
   }

   virtual void reallocateArrayPageIndex( Value **&indexes, 
                                          ValueInternalArray::PageIndex &indexCount,
                                          ValueInternalArray::PageIndex minNewIndexCount )
   {
      ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
      if ( minNewIndexCount > newIndexCount )
         newIndexCount = minNewIndexCount;
      void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
      if ( !newIndexes )
         throw std::bad_alloc();
      indexCount = newIndexCount;
      indexes = static_cast<Value **>( newIndexes );
   }
   virtual void releaseArrayPageIndex( Value **indexes, 
                                       ValueInternalArray::PageIndex indexCount )
   {
      if ( indexes )
         free( indexes );
   }

   virtual Value *allocateArrayPage()
   {
      return static_cast<Value *>( pagesAllocator_.allocate() );
   }

   virtual void releaseArrayPage( Value *value )
   {
      if ( value )
         pagesAllocator_.release( value );
   }
private:
   BatchAllocator<ValueInternalArray,1> arraysAllocator_;
   BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
};
#endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR

static ValueArrayAllocator *&arrayAllocator()
{
   static DefaultValueArrayAllocator defaultAllocator;
   static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
   return arrayAllocator;
}

static struct DummyArrayAllocatorInitializer {
   DummyArrayAllocatorInitializer() 
   {
      arrayAllocator();      // ensure arrayAllocator() statics are initialized before main().
   }
} dummyArrayAllocatorInitializer;

// //////////////////////////////////////////////////////////////////
// class ValueInternalArray
// //////////////////////////////////////////////////////////////////
bool 
ValueInternalArray::equals( const IteratorState &x, 
                            const IteratorState &other )
{
   return x.array_ == other.array_  
          &&  x.currentItemIndex_ == other.currentItemIndex_  
          &&  x.currentPageIndex_ == other.currentPageIndex_;
}


void 
ValueInternalArray::increment( IteratorState &it )
{
   JSON_ASSERT_MESSAGE( it.array_  &&
      (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
      != it.array_->size_,
      "ValueInternalArray::increment(): moving iterator beyond end" );
   ++(it.currentItemIndex_);
   if ( it.currentItemIndex_ == itemsPerPage )
   {
      it.currentItemIndex_ = 0;
      ++(it.currentPageIndex_);
   }
}


void 
ValueInternalArray::decrement( IteratorState &it )
{
   JSON_ASSERT_MESSAGE( it.array_  &&  it.currentPageIndex_ == it.array_->pages_ 
                        &&  it.currentItemIndex_ == 0,
      "ValueInternalArray::decrement(): moving iterator beyond end" );
   if ( it.currentItemIndex_ == 0 )
   {
      it.currentItemIndex_ = itemsPerPage-1;
      --(it.currentPageIndex_);
   }
   else
   {
      --(it.currentItemIndex_);
   }
}


Value &
ValueInternalArray::unsafeDereference( const IteratorState &it )
{
   return (*(it.currentPageIndex_))[it.currentItemIndex_];
}


Value &
ValueInternalArray::dereference( const IteratorState &it )
{
   JSON_ASSERT_MESSAGE( it.array_  &&
      (it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
      < it.array_->size_,
      "ValueInternalArray::dereference(): dereferencing invalid iterator" );
   return unsafeDereference( it );
}

void 
ValueInternalArray::makeBeginIterator( IteratorState &it ) const
{
   it.array_ = const_cast<ValueInternalArray *>( this );
   it.currentItemIndex_ = 0;
   it.currentPageIndex_ = pages_;
}


void 
ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
{
   it.array_ = const_cast<ValueInternalArray *>( this );
   it.currentItemIndex_ = index % itemsPerPage;
   it.currentPageIndex_ = pages_ + index / itemsPerPage;
}


void 
ValueInternalArray::makeEndIterator( IteratorState &it ) const
{
   makeIterator( it, size_ );
}


ValueInternalArray::ValueInternalArray()
   : pages_( 0 )
   , size_( 0 )
   , pageCount_( 0 )
{
}


ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
   : pages_( 0 )
   , pageCount_( 0 )
   , size_( other.size_ )
{
   PageIndex minNewPages = other.size_ / itemsPerPage;
   arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
   JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, 
                        "ValueInternalArray::reserve(): bad reallocation" );
   IteratorState itOther;
   other.makeBeginIterator( itOther );
   Value *value;
   for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
   {
      if ( index % itemsPerPage == 0 )
      {
         PageIndex pageIndex = index / itemsPerPage;
         value = arrayAllocator()->allocateArrayPage();
         pages_[pageIndex] = value;
      }
      new (value) Value( dereference( itOther ) );
   }
}


ValueInternalArray &
ValueInternalArray::operator =( const ValueInternalArray &other )
{
   ValueInternalArray temp( other );
   swap( temp );
   return *this;
}


ValueInternalArray::~ValueInternalArray()
{
   // destroy all constructed items
   IteratorState it;
   IteratorState itEnd;
   makeBeginIterator( it);
   makeEndIterator( itEnd );
   for ( ; !equals(it,itEnd); increment(it) )
   {
      Value *value = &dereference(it);
      value->~Value();
   }
   // release all pages
   PageIndex lastPageIndex = size_ / itemsPerPage;
   for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
      arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
   // release pages index
   arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
}


void 
ValueInternalArray::swap( ValueInternalArray &other )
{
   Value **tempPages = pages_;
   pages_ = other.pages_;
   other.pages_ = tempPages;
   ArrayIndex tempSize = size_;
   size_ = other.size_;
   other.size_ = tempSize;
   PageIndex tempPageCount = pageCount_;
   pageCount_ = other.pageCount_;
   other.pageCount_ = tempPageCount;
}

void 
ValueInternalArray::clear()
{
   ValueInternalArray dummy;
   swap( dummy );
}


void 
ValueInternalArray::resize( ArrayIndex newSize )
{
   if ( newSize == 0 )
      clear();
   else if ( newSize < size_ )
   {
      IteratorState it;
      IteratorState itEnd;
      makeIterator( it, newSize );
      makeIterator( itEnd, size_ );
      for ( ; !equals(it,itEnd); increment(it) )
      {
         Value *value = &dereference(it);
         value->~Value();
      }
      PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
      PageIndex lastPageIndex = size_ / itemsPerPage;
      for ( ; pageIndex < lastPageIndex; ++pageIndex )
         arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
      size_ = newSize;
   }
   else if ( newSize > size_ )
      resolveReference( newSize );
}


void 
ValueInternalArray::makeIndexValid( ArrayIndex index )
{
   // Need to enlarge page index ?
   if ( index >= pageCount_ * itemsPerPage )
   {
      PageIndex minNewPages = (index + 1) / itemsPerPage;
      arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
      JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
   }

   // Need to allocate new pages ?
   ArrayIndex nextPageIndex = 
      (size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
                                  : size_;
   if ( nextPageIndex <= index )
   {
      PageIndex pageIndex = nextPageIndex / itemsPerPage;
      PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
      for ( ; pageToAllocate-- > 0; ++pageIndex )
         pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
   }

   // Initialize all new entries
   IteratorState it;
   IteratorState itEnd;
   makeIterator( it, size_ );
   size_ = index + 1;
   makeIterator( itEnd, size_ );
   for ( ; !equals(it,itEnd); increment(it) )
   {
      Value *value = &dereference(it);
      new (value) Value(); // Construct a default value using placement new
   }
}

Value &
ValueInternalArray::resolveReference( ArrayIndex index )
{
   if ( index >= size_ )
      makeIndexValid( index );
   return pages_[index/itemsPerPage][index%itemsPerPage];
}

Value *
ValueInternalArray::find( ArrayIndex index ) const
{
   if ( index >= size_ )
      return 0;
   return &(pages_[index/itemsPerPage][index%itemsPerPage]);
}

ValueInternalArray::ArrayIndex 
ValueInternalArray::size() const
{
   return size_;
}

int 
ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
{
   return indexOf(y) - indexOf(x);
}


ValueInternalArray::ArrayIndex 
ValueInternalArray::indexOf( const IteratorState &iterator )
{
   if ( !iterator.array_ )
      return ArrayIndex(-1);
   return ArrayIndex(
      (iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage 
      + iterator.currentItemIndex_ );
}


int 
ValueInternalArray::compare( const ValueInternalArray &other ) const
{
   int sizeDiff( size_ - other.size_ );
   if ( sizeDiff != 0 )
      return sizeDiff;
   
   for ( ArrayIndex index =0; index < size_; ++index )
   {
      int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare( 
         other.pages_[index/itemsPerPage][index%itemsPerPage] );
      if ( diff != 0 )
         return diff;
   }
   return 0;
}

2295.1.1 by Brian Aker Fix up stewart JSON patch.	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
2283.4.3 by Stewart Smith add JSON library to json_server, fix up for building in our tree, and add simple /0.1/version JSON response as well as latest_api_version snippet to /	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
	61	virtual ~DefaultValueArrayAllocator()
	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	if ( indexes )
	97	free( indexes );
	98	}
	99
	100	virtual Value *allocateArrayPage()
	101	{
	102	return static_cast<Value >( malloc( sizeof(Value) ValueInternalArray::itemsPerPage ) );
103	}
104
105	virtual void releaseArrayPage( Value *value )
106	{
107	if ( value )
108	free( value );
109	}
110	};
111
112	#else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
113	/// @todo make this thread-safe (lock when accessign batch allocator)
114	class DefaultValueArrayAllocator : public ValueArrayAllocator
115	{
116	public: // overridden from ValueArrayAllocator
117	virtual ~DefaultValueArrayAllocator()
118	{
119	}
120
121	virtual ValueInternalArray *newArray()
122	{
123	ValueInternalArray *array = arraysAllocator_.allocate();
124	new (array) ValueInternalArray(); // placement new
125	return array;
126	}
127
128	virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
129	{
130	ValueInternalArray *array = arraysAllocator_.allocate();
131	new (array) ValueInternalArray( other ); // placement new
132	return array;
133	}
134
135	virtual void destructArray( ValueInternalArray *array )
136	{
137	if ( array )
138	{
139	array->~ValueInternalArray();
140	arraysAllocator_.release( array );
141	}
142	}
143
144	virtual void reallocateArrayPageIndex( Value **&indexes,
145	ValueInternalArray::PageIndex &indexCount,
146	ValueInternalArray::PageIndex minNewIndexCount )
147	{
148	ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
149	if ( minNewIndexCount > newIndexCount )
150	newIndexCount = minNewIndexCount;
151	void newIndexes = realloc( indexes, sizeof(Value) * newIndexCount );
152	if ( !newIndexes )
153	throw std::bad_alloc();
154	indexCount = newIndexCount;
155	indexes = static_cast<Value **>( newIndexes );
156	}
157	virtual void releaseArrayPageIndex( Value **indexes,
158	ValueInternalArray::PageIndex indexCount )
159	{
160	if ( indexes )
161	free( indexes );
162	}
163
164	virtual Value *allocateArrayPage()
165	{
166	return static_cast<Value *>( pagesAllocator_.allocate() );
167	}
168
169	virtual void releaseArrayPage( Value *value )
170	{
171	if ( value )
172	pagesAllocator_.release( value );
173	}
174	private:
175	BatchAllocator<ValueInternalArray,1> arraysAllocator_;
176	BatchAllocator<Value,ValueInternalArray::itemsPerPage> pagesAllocator_;
177	};
178	#endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
179
180	static ValueArrayAllocator *&arrayAllocator()
181	{
182	static DefaultValueArrayAllocator defaultAllocator;
183	static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
184	return arrayAllocator;
185	}
186
187	static struct DummyArrayAllocatorInitializer {
188	DummyArrayAllocatorInitializer()
189	{
190	arrayAllocator(); // ensure arrayAllocator() statics are initialized before main().
191	}
192	} dummyArrayAllocatorInitializer;
193
194	// //////////////////////////////////////////////////////////////////
195	// class ValueInternalArray
196	// //////////////////////////////////////////////////////////////////
197	bool
198	ValueInternalArray::equals( const IteratorState &x,
199	const IteratorState &other )
200	{
201	return x.array_ == other.array_
202	&& x.currentItemIndex_ == other.currentItemIndex_
203	&& x.currentPageIndex_ == other.currentPageIndex_;
204	}
205
206
207	void
208	ValueInternalArray::increment( IteratorState &it )
209	{
210	JSON_ASSERT_MESSAGE( it.array_ &&
211	(it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
212	!= it.array_->size_,
213	"ValueInternalArray::increment(): moving iterator beyond end" );
214	++(it.currentItemIndex_);
215	if ( it.currentItemIndex_ == itemsPerPage )
216	{
217	it.currentItemIndex_ = 0;
218	++(it.currentPageIndex_);
219	}
220	}
221
222
223	void
224	ValueInternalArray::decrement( IteratorState &it )
225	{
226	JSON_ASSERT_MESSAGE( it.array_ && it.currentPageIndex_ == it.array_->pages_
227	&& it.currentItemIndex_ == 0,
228	"ValueInternalArray::decrement(): moving iterator beyond end" );
229	if ( it.currentItemIndex_ == 0 )
230	{
231	it.currentItemIndex_ = itemsPerPage-1;
232	--(it.currentPageIndex_);
233	}
234	else
235	{
236	--(it.currentItemIndex_);
237	}
238	}
239
240
241	Value &
242	ValueInternalArray::unsafeDereference( const IteratorState &it )
243	{
244	return (*(it.currentPageIndex_))[it.currentItemIndex_];
245	}
246
247
248	Value &
249	ValueInternalArray::dereference( const IteratorState &it )
250	{
251	JSON_ASSERT_MESSAGE( it.array_ &&
252	(it.currentPageIndex_ - it.array_->pages_)*itemsPerPage + it.currentItemIndex_
253	< it.array_->size_,
254	"ValueInternalArray::dereference(): dereferencing invalid iterator" );
255	return unsafeDereference( it );
256	}
257
258	void
259	ValueInternalArray::makeBeginIterator( IteratorState &it ) const
260	{
261	it.array_ = const_cast<ValueInternalArray *>( this );
262	it.currentItemIndex_ = 0;
263	it.currentPageIndex_ = pages_;
264	}
265
266
267	void
268	ValueInternalArray::makeIterator( IteratorState &it, ArrayIndex index ) const
269	{
270	it.array_ = const_cast<ValueInternalArray *>( this );
271	it.currentItemIndex_ = index % itemsPerPage;
272	it.currentPageIndex_ = pages_ + index / itemsPerPage;
273	}
274
275
276	void
277	ValueInternalArray::makeEndIterator( IteratorState &it ) const
278	{
279	makeIterator( it, size_ );
280	}
281
282
283	ValueInternalArray::ValueInternalArray()
284	: pages_( 0 )
285	, size_( 0 )
286	, pageCount_( 0 )
287	{
288	}
289
290
291	ValueInternalArray::ValueInternalArray( const ValueInternalArray &other )
292	: pages_( 0 )
293	, pageCount_( 0 )
294	, size_( other.size_ )
295	{
296	PageIndex minNewPages = other.size_ / itemsPerPage;
297	arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
298	JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages,
299	"ValueInternalArray::reserve(): bad reallocation" );
300	IteratorState itOther;
301	other.makeBeginIterator( itOther );
302	Value *value;
303	for ( ArrayIndex index = 0; index < size_; ++index, increment(itOther) )
304	{
305	if ( index % itemsPerPage == 0 )
306	{
307	PageIndex pageIndex = index / itemsPerPage;
308	value = arrayAllocator()->allocateArrayPage();
309	pages_[pageIndex] = value;
310	}
311	new (value) Value( dereference( itOther ) );
312	}
313	}
314
315
316	ValueInternalArray &
317	ValueInternalArray::operator =( const ValueInternalArray &other )
318	{
319	ValueInternalArray temp( other );
320	swap( temp );
321	return *this;
322	}
323
324
325	ValueInternalArray::~ValueInternalArray()
326	{
327	// destroy all constructed items
328	IteratorState it;
329	IteratorState itEnd;
330	makeBeginIterator( it);
331	makeEndIterator( itEnd );
332	for ( ; !equals(it,itEnd); increment(it) )
333	{
334	Value *value = &dereference(it);
335	value->~Value();
336	}
337	// release all pages
338	PageIndex lastPageIndex = size_ / itemsPerPage;
339	for ( PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex )
340	arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
341	// release pages index
342	arrayAllocator()->releaseArrayPageIndex( pages_, pageCount_ );
343	}
344
345
346	void
347	ValueInternalArray::swap( ValueInternalArray &other )
348	{
349	Value **tempPages = pages_;
350	pages_ = other.pages_;
351	other.pages_ = tempPages;
352	ArrayIndex tempSize = size_;
353	size_ = other.size_;
354	other.size_ = tempSize;
355	PageIndex tempPageCount = pageCount_;
356	pageCount_ = other.pageCount_;
357	other.pageCount_ = tempPageCount;
358	}
359
360	void
361	ValueInternalArray::clear()
362	{
363	ValueInternalArray dummy;
364	swap( dummy );
365	}
366
367
368	void
369	ValueInternalArray::resize( ArrayIndex newSize )
370	{
371	if ( newSize == 0 )
372	clear();
373	else if ( newSize < size_ )
374	{
375	IteratorState it;
376	IteratorState itEnd;
377	makeIterator( it, newSize );
378	makeIterator( itEnd, size_ );
379	for ( ; !equals(it,itEnd); increment(it) )
380	{
381	Value *value = &dereference(it);
382	value->~Value();
383	}
384	PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
385	PageIndex lastPageIndex = size_ / itemsPerPage;
386	for ( ; pageIndex < lastPageIndex; ++pageIndex )
387	arrayAllocator()->releaseArrayPage( pages_[pageIndex] );
388	size_ = newSize;
389	}
390	else if ( newSize > size_ )
391	resolveReference( newSize );
392	}
393
394
395	void
396	ValueInternalArray::makeIndexValid( ArrayIndex index )
397	{
398	// Need to enlarge page index ?
399	if ( index >= pageCount_ * itemsPerPage )
400	{
401	PageIndex minNewPages = (index + 1) / itemsPerPage;
402	arrayAllocator()->reallocateArrayPageIndex( pages_, pageCount_, minNewPages );
403	JSON_ASSERT_MESSAGE( pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation" );
404	}
405
406	// Need to allocate new pages ?
407	ArrayIndex nextPageIndex =
408	(size_ % itemsPerPage) != 0 ? size_ - (size_%itemsPerPage) + itemsPerPage
409	: size_;
410	if ( nextPageIndex <= index )
411	{
412	PageIndex pageIndex = nextPageIndex / itemsPerPage;
413	PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
414	for ( ; pageToAllocate-- > 0; ++pageIndex )
415	pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
416	}
417
418	// Initialize all new entries
419	IteratorState it;
420	IteratorState itEnd;
421	makeIterator( it, size_ );
422	size_ = index + 1;
423	makeIterator( itEnd, size_ );
424	for ( ; !equals(it,itEnd); increment(it) )
425	{
426	Value *value = &dereference(it);
427	new (value) Value(); // Construct a default value using placement new
428	}
429	}
430
431	Value &
432	ValueInternalArray::resolveReference( ArrayIndex index )
433	{
434	if ( index >= size_ )
435	makeIndexValid( index );
436	return pages_[index/itemsPerPage][index%itemsPerPage];
437	}
438
439	Value *
440	ValueInternalArray::find( ArrayIndex index ) const
441	{
442	if ( index >= size_ )
443	return 0;
444	return &(pages_[index/itemsPerPage][index%itemsPerPage]);
445	}
446
447	ValueInternalArray::ArrayIndex
448	ValueInternalArray::size() const
449	{
450	return size_;
451	}
452
453	int
454	ValueInternalArray::distance( const IteratorState &x, const IteratorState &y )
455	{
456	return indexOf(y) - indexOf(x);
457	}
458
459
460	ValueInternalArray::ArrayIndex
461	ValueInternalArray::indexOf( const IteratorState &iterator )
462	{
463	if ( !iterator.array_ )
464	return ArrayIndex(-1);
465	return ArrayIndex(
466	(iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage
467	+ iterator.currentItemIndex_ );
468	}
469
470
471	int
472	ValueInternalArray::compare( const ValueInternalArray &other ) const
473	{
474	int sizeDiff( size_ - other.size_ );
475	if ( sizeDiff != 0 )
476	return sizeDiff;
477
478	for ( ArrayIndex index =0; index < size_; ++index )
479	{
480	int diff = pages_[index/itemsPerPage][index%itemsPerPage].compare(
481	other.pages_[index/itemsPerPage][index%itemsPerPage] );
482	if ( diff != 0 )
483	return diff;
484	}
485	return 0;
486	}