← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/json_server/json/json_internalarray.inl

  • Committer: Mark Atwood
  • Date: 2011-05-12 22:20:08 UTC
  • mfrom: (2283.4.17 json-interface)
  • Revision ID: me@mark.atwood.name-20110512222008-7facdn0qu7lsbm0g
merge lp:~stewart/drizzle/json-interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/json_server/json/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
 
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
}