← Back to branch summary

~c-e-pidcott/maus/devel

« back to all changes in this revision

Viewing changes to third_party/JsonCpp_0.5.0/src/lib_json/json_internalmap.inl

  • Committer: Christopher Tunnell
  • Date: 2010-10-22 23:28:44 UTC
  • Revision ID: c.tunnell1@physics.ox.ac.uk-20101022232844-o8bl6n26kk03deuw
remove jsoncpp (so it's now downloaded instead)

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/JsonCpp_0.5.0/src/lib_json/json_internalmap.inl
1
 
// included by json_value.cpp
2
 
// everything is within Json namespace
3
 
 
4
 
// //////////////////////////////////////////////////////////////////
5
 
// //////////////////////////////////////////////////////////////////
6
 
// //////////////////////////////////////////////////////////////////
7
 
// class ValueInternalMap
8
 
// //////////////////////////////////////////////////////////////////
9
 
// //////////////////////////////////////////////////////////////////
10
 
// //////////////////////////////////////////////////////////////////
11
 
 
12
 
/** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
13
 
   * This optimization is used by the fast allocator.
14
 
   */
15
 
ValueInternalLink::ValueInternalLink()
16
 
   : previous_( 0 )
17
 
   , next_( 0 )
18
 
{
19
 
}
20
 
 
21
 
ValueInternalLink::~ValueInternalLink()
22
 
{ 
23
 
   for ( int index =0; index < itemPerLink; ++index )
24
 
   {
25
 
      if ( !items_[index].isItemAvailable() )
26
 
      {
27
 
         if ( !items_[index].isMemberNameStatic() )
28
 
            free( keys_[index] );
29
 
      }
30
 
      else
31
 
         break;
32
 
   }
33
 
}
34
 
 
35
 
 
36
 
 
37
 
ValueMapAllocator::~ValueMapAllocator()
38
 
{
39
 
}
40
 
 
41
 
#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
42
 
class DefaultValueMapAllocator : public ValueMapAllocator
43
 
{
44
 
public: // overridden from ValueMapAllocator
45
 
   virtual ValueInternalMap *newMap()
46
 
   {
47
 
      return new ValueInternalMap();
48
 
   }
49
 
 
50
 
   virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
51
 
   {
52
 
      return new ValueInternalMap( other );
53
 
   }
54
 
 
55
 
   virtual void destructMap( ValueInternalMap *map )
56
 
   {
57
 
      delete map;
58
 
   }
59
 
 
60
 
   virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
61
 
   {
62
 
      return new ValueInternalLink[size];
63
 
   }
64
 
 
65
 
   virtual void releaseMapBuckets( ValueInternalLink *links )
66
 
   {
67
 
      delete [] links;
68
 
   }
69
 
 
70
 
   virtual ValueInternalLink *allocateMapLink()
71
 
   {
72
 
      return new ValueInternalLink();
73
 
   }
74
 
 
75
 
   virtual void releaseMapLink( ValueInternalLink *link )
76
 
   {
77
 
      delete link;
78
 
   }
79
 
};
80
 
#else
81
 
/// @todo make this thread-safe (lock when accessign batch allocator)
82
 
class DefaultValueMapAllocator : public ValueMapAllocator
83
 
{
84
 
public: // overridden from ValueMapAllocator
85
 
   virtual ValueInternalMap *newMap()
86
 
   {
87
 
      ValueInternalMap *map = mapsAllocator_.allocate();
88
 
      new (map) ValueInternalMap(); // placement new
89
 
      return map;
90
 
   }
91
 
 
92
 
   virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
93
 
   {
94
 
      ValueInternalMap *map = mapsAllocator_.allocate();
95
 
      new (map) ValueInternalMap( other ); // placement new
96
 
      return map;
97
 
   }
98
 
 
99
 
   virtual void destructMap( ValueInternalMap *map )
100
 
   {
101
 
      if ( map )
102
 
      {
103
 
         map->~ValueInternalMap();
104
 
         mapsAllocator_.release( map );
105
 
      }
106
 
   }
107
 
 
108
 
   virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
109
 
   {
110
 
      return new ValueInternalLink[size];
111
 
   }
112
 
 
113
 
   virtual void releaseMapBuckets( ValueInternalLink *links )
114
 
   {
115
 
      delete [] links;
116
 
   }
117
 
 
118
 
   virtual ValueInternalLink *allocateMapLink()
119
 
   {
120
 
      ValueInternalLink *link = linksAllocator_.allocate();
121
 
      memset( link, 0, sizeof(ValueInternalLink) );
122
 
      return link;
123
 
   }
124
 
 
125
 
   virtual void releaseMapLink( ValueInternalLink *link )
126
 
   {
127
 
      link->~ValueInternalLink();
128
 
      linksAllocator_.release( link );
129
 
   }
130
 
private:
131
 
   BatchAllocator<ValueInternalMap,1> mapsAllocator_;
132
 
   BatchAllocator<ValueInternalLink,1> linksAllocator_;
133
 
};
134
 
#endif
135
 
 
136
 
static ValueMapAllocator *&mapAllocator()
137
 
{
138
 
   static DefaultValueMapAllocator defaultAllocator;
139
 
   static ValueMapAllocator *mapAllocator = &defaultAllocator;
140
 
   return mapAllocator;
141
 
}
142
 
 
143
 
static struct DummyMapAllocatorInitializer {
144
 
   DummyMapAllocatorInitializer() 
145
 
   {
146
 
      mapAllocator();      // ensure mapAllocator() statics are initialized before main().
147
 
   }
148
 
} dummyMapAllocatorInitializer;
149
 
 
150
 
 
151
 
 
152
 
// h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
153
 
 
154
 
/*
155
 
use linked list hash map. 
156
 
buckets array is a container.
157
 
linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
158
 
value have extra state: valid, available, deleted
159
 
*/
160
 
 
161
 
 
162
 
ValueInternalMap::ValueInternalMap()
163
 
   : buckets_( 0 )
164
 
   , tailLink_( 0 )
165
 
   , bucketsSize_( 0 )
166
 
   , itemCount_( 0 )
167
 
{
168
 
}
169
 
 
170
 
 
171
 
ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
172
 
   : buckets_( 0 )
173
 
   , tailLink_( 0 )
174
 
   , bucketsSize_( 0 )
175
 
   , itemCount_( 0 )
176
 
{
177
 
   reserve( other.itemCount_ );
178
 
   IteratorState it;
179
 
   IteratorState itEnd;
180
 
   other.makeBeginIterator( it );
181
 
   other.makeEndIterator( itEnd );
182
 
   for ( ; !equals(it,itEnd); increment(it) )
183
 
   {
184
 
      bool isStatic;
185
 
      const char *memberName = key( it, isStatic );
186
 
      const Value &aValue = value( it );
187
 
      resolveReference(memberName, isStatic) = aValue;
188
 
   }
189
 
}
190
 
 
191
 
 
192
 
ValueInternalMap &
193
 
ValueInternalMap::operator =( const ValueInternalMap &other )
194
 
{
195
 
   ValueInternalMap dummy( other );
196
 
   swap( dummy );
197
 
   return *this;
198
 
}
199
 
 
200
 
 
201
 
ValueInternalMap::~ValueInternalMap()
202
 
{
203
 
   if ( buckets_ )
204
 
   {
205
 
      for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
206
 
      {
207
 
         ValueInternalLink *link = buckets_[bucketIndex].next_;
208
 
         while ( link )
209
 
         {
210
 
            ValueInternalLink *linkToRelease = link;
211
 
            link = link->next_;
212
 
            mapAllocator()->releaseMapLink( linkToRelease );
213
 
         }
214
 
      }
215
 
      mapAllocator()->releaseMapBuckets( buckets_ );
216
 
   }
217
 
}
218
 
 
219
 
 
220
 
void 
221
 
ValueInternalMap::swap( ValueInternalMap &other )
222
 
{
223
 
   ValueInternalLink *tempBuckets = buckets_;
224
 
   buckets_ = other.buckets_;
225
 
   other.buckets_ = tempBuckets;
226
 
   ValueInternalLink *tempTailLink = tailLink_;
227
 
   tailLink_ = other.tailLink_;
228
 
   other.tailLink_ = tempTailLink;
229
 
   BucketIndex tempBucketsSize = bucketsSize_;
230
 
   bucketsSize_ = other.bucketsSize_;
231
 
   other.bucketsSize_ = tempBucketsSize;
232
 
   BucketIndex tempItemCount = itemCount_;
233
 
   itemCount_ = other.itemCount_;
234
 
   other.itemCount_ = tempItemCount;
235
 
}
236
 
 
237
 
 
238
 
void 
239
 
ValueInternalMap::clear()
240
 
{
241
 
   ValueInternalMap dummy;
242
 
   swap( dummy );
243
 
}
244
 
 
245
 
 
246
 
ValueInternalMap::BucketIndex 
247
 
ValueInternalMap::size() const
248
 
{
249
 
   return itemCount_;
250
 
}
251
 
 
252
 
bool 
253
 
ValueInternalMap::reserveDelta( BucketIndex growth )
254
 
{
255
 
   return reserve( itemCount_ + growth );
256
 
}
257
 
 
258
 
bool 
259
 
ValueInternalMap::reserve( BucketIndex newItemCount )
260
 
{
261
 
   if ( !buckets_  &&  newItemCount > 0 )
262
 
   {
263
 
      buckets_ = mapAllocator()->allocateMapBuckets( 1 );
264
 
      bucketsSize_ = 1;
265
 
      tailLink_ = &buckets_[0];
266
 
   }
267
 
//   BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
268
 
   return true;
269
 
}
270
 
 
271
 
 
272
 
const Value *
273
 
ValueInternalMap::find( const char *key ) const
274
 
{
275
 
   if ( !bucketsSize_ )
276
 
      return 0;
277
 
   HashKey hashedKey = hash( key );
278
 
   BucketIndex bucketIndex = hashedKey % bucketsSize_;
279
 
   for ( const ValueInternalLink *current = &buckets_[bucketIndex]; 
280
 
         current != 0; 
281
 
         current = current->next_ )
282
 
   {
283
 
      for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
284
 
      {
285
 
         if ( current->items_[index].isItemAvailable() )
286
 
            return 0;
287
 
         if ( strcmp( key, current->keys_[index] ) == 0 )
288
 
            return &current->items_[index];
289
 
      }
290
 
   }
291
 
   return 0;
292
 
}
293
 
 
294
 
 
295
 
Value *
296
 
ValueInternalMap::find( const char *key )
297
 
{
298
 
   const ValueInternalMap *constThis = this;
299
 
   return const_cast<Value *>( constThis->find( key ) );
300
 
}
301
 
 
302
 
 
303
 
Value &
304
 
ValueInternalMap::resolveReference( const char *key,
305
 
                                    bool isStatic )
306
 
{
307
 
   HashKey hashedKey = hash( key );
308
 
   if ( bucketsSize_ )
309
 
   {
310
 
      BucketIndex bucketIndex = hashedKey % bucketsSize_;
311
 
      ValueInternalLink **previous = 0;
312
 
      BucketIndex index;
313
 
      for ( ValueInternalLink *current = &buckets_[bucketIndex]; 
314
 
            current != 0; 
315
 
            previous = &current->next_, current = current->next_ )
316
 
      {
317
 
         for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
318
 
         {
319
 
            if ( current->items_[index].isItemAvailable() )
320
 
               return setNewItem( key, isStatic, current, index );
321
 
            if ( strcmp( key, current->keys_[index] ) == 0 )
322
 
               return current->items_[index];
323
 
         }
324
 
      }
325
 
   }
326
 
 
327
 
   reserveDelta( 1 );
328
 
   return unsafeAdd( key, isStatic, hashedKey );
329
 
}
330
 
 
331
 
 
332
 
void 
333
 
ValueInternalMap::remove( const char *key )
334
 
{
335
 
   HashKey hashedKey = hash( key );
336
 
   if ( !bucketsSize_ )
337
 
      return;
338
 
   BucketIndex bucketIndex = hashedKey % bucketsSize_;
339
 
   for ( ValueInternalLink *link = &buckets_[bucketIndex]; 
340
 
         link != 0; 
341
 
         link = link->next_ )
342
 
   {
343
 
      BucketIndex index;
344
 
      for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
345
 
      {
346
 
         if ( link->items_[index].isItemAvailable() )
347
 
            return;
348
 
         if ( strcmp( key, link->keys_[index] ) == 0 )
349
 
         {
350
 
            doActualRemove( link, index, bucketIndex );
351
 
            return;
352
 
         }
353
 
      }
354
 
   }
355
 
}
356
 
 
357
 
void 
358
 
ValueInternalMap::doActualRemove( ValueInternalLink *link, 
359
 
                                  BucketIndex index,
360
 
                                  BucketIndex bucketIndex )
361
 
{
362
 
   // find last item of the bucket and swap it with the 'removed' one.
363
 
   // set removed items flags to 'available'.
364
 
   // if last page only contains 'available' items, then desallocate it (it's empty)
365
 
   ValueInternalLink *&lastLink = getLastLinkInBucket( index );
366
 
   BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
367
 
   for ( ;   
368
 
         lastItemIndex < ValueInternalLink::itemPerLink; 
369
 
         ++lastItemIndex ) // may be optimized with dicotomic search
370
 
   {
371
 
      if ( lastLink->items_[lastItemIndex].isItemAvailable() )
372
 
         break;
373
 
   }
374
 
   
375
 
   BucketIndex lastUsedIndex = lastItemIndex - 1;
376
 
   Value *valueToDelete = &link->items_[index];
377
 
   Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
378
 
   if ( valueToDelete != valueToPreserve )
379
 
      valueToDelete->swap( *valueToPreserve );
380
 
   if ( lastUsedIndex == 0 )  // page is now empty
381
 
   {  // remove it from bucket linked list and delete it.
382
 
      ValueInternalLink *linkPreviousToLast = lastLink->previous_;
383
 
      if ( linkPreviousToLast != 0 )   // can not deleted bucket link.
384
 
      {
385
 
         mapAllocator()->releaseMapLink( lastLink );
386
 
         linkPreviousToLast->next_ = 0;
387
 
         lastLink = linkPreviousToLast;
388
 
      }
389
 
   }
390
 
   else
391
 
   {
392
 
      Value dummy;
393
 
      valueToPreserve->swap( dummy ); // restore deleted to default Value.
394
 
      valueToPreserve->setItemUsed( false );
395
 
   }
396
 
   --itemCount_;
397
 
}
398
 
 
399
 
 
400
 
ValueInternalLink *&
401
 
ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
402
 
{
403
 
   if ( bucketIndex == bucketsSize_ - 1 )
404
 
      return tailLink_;
405
 
   ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
406
 
   if ( !previous )
407
 
      previous = &buckets_[bucketIndex];
408
 
   return previous;
409
 
}
410
 
 
411
 
 
412
 
Value &
413
 
ValueInternalMap::setNewItem( const char *key, 
414
 
                              bool isStatic,
415
 
                              ValueInternalLink *link, 
416
 
                              BucketIndex index )
417
 
{
418
 
   char *duplicatedKey = valueAllocator()->makeMemberName( key );
419
 
   ++itemCount_;
420
 
   link->keys_[index] = duplicatedKey;
421
 
   link->items_[index].setItemUsed();
422
 
   link->items_[index].setMemberNameIsStatic( isStatic );
423
 
   return link->items_[index]; // items already default constructed.
424
 
}
425
 
 
426
 
 
427
 
Value &
428
 
ValueInternalMap::unsafeAdd( const char *key, 
429
 
                             bool isStatic, 
430
 
                             HashKey hashedKey )
431
 
{
432
 
   JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
433
 
   BucketIndex bucketIndex = hashedKey % bucketsSize_;
434
 
   ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
435
 
   ValueInternalLink *link = previousLink;
436
 
   BucketIndex index;
437
 
   for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
438
 
   {
439
 
      if ( link->items_[index].isItemAvailable() )
440
 
         break;
441
 
   }
442
 
   if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
443
 
   {
444
 
      ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
445
 
      index = 0;
446
 
      link->next_ = newLink;
447
 
      previousLink = newLink;
448
 
      link = newLink;
449
 
   }
450
 
   return setNewItem( key, isStatic, link, index );
451
 
}
452
 
 
453
 
 
454
 
ValueInternalMap::HashKey 
455
 
ValueInternalMap::hash( const char *key ) const
456
 
{
457
 
   HashKey hash = 0;
458
 
   while ( *key )
459
 
      hash += *key++ * 37;
460
 
   return hash;
461
 
}
462
 
 
463
 
 
464
 
int 
465
 
ValueInternalMap::compare( const ValueInternalMap &other ) const
466
 
{
467
 
   int sizeDiff( itemCount_ - other.itemCount_ );
468
 
   if ( sizeDiff != 0 )
469
 
      return sizeDiff;
470
 
   // Strict order guaranty is required. Compare all keys FIRST, then compare values.
471
 
   IteratorState it;
472
 
   IteratorState itEnd;
473
 
   makeBeginIterator( it );
474
 
   makeEndIterator( itEnd );
475
 
   for ( ; !equals(it,itEnd); increment(it) )
476
 
   {
477
 
      if ( !other.find( key( it ) ) )
478
 
         return 1;
479
 
   }
480
 
 
481
 
   // All keys are equals, let's compare values
482
 
   makeBeginIterator( it );
483
 
   for ( ; !equals(it,itEnd); increment(it) )
484
 
   {
485
 
      const Value *otherValue = other.find( key( it ) );
486
 
      int valueDiff = value(it).compare( *otherValue );
487
 
      if ( valueDiff != 0 )
488
 
         return valueDiff;
489
 
   }
490
 
   return 0;
491
 
}
492
 
 
493
 
 
494
 
void 
495
 
ValueInternalMap::makeBeginIterator( IteratorState &it ) const
496
 
{
497
 
   it.map_ = const_cast<ValueInternalMap *>( this );
498
 
   it.bucketIndex_ = 0;
499
 
   it.itemIndex_ = 0;
500
 
   it.link_ = buckets_;
501
 
}
502
 
 
503
 
 
504
 
void 
505
 
ValueInternalMap::makeEndIterator( IteratorState &it ) const
506
 
{
507
 
   it.map_ = const_cast<ValueInternalMap *>( this );
508
 
   it.bucketIndex_ = bucketsSize_;
509
 
   it.itemIndex_ = 0;
510
 
   it.link_ = 0;
511
 
}
512
 
 
513
 
 
514
 
bool 
515
 
ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
516
 
{
517
 
   return x.map_ == other.map_  
518
 
          &&  x.bucketIndex_ == other.bucketIndex_  
519
 
          &&  x.link_ == other.link_
520
 
          &&  x.itemIndex_ == other.itemIndex_;
521
 
}
522
 
 
523
 
 
524
 
void 
525
 
ValueInternalMap::incrementBucket( IteratorState &iterator )
526
 
{
527
 
   ++iterator.bucketIndex_;
528
 
   JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
529
 
      "ValueInternalMap::increment(): attempting to iterate beyond end." );
530
 
   if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
531
 
      iterator.link_ = 0;
532
 
   else
533
 
      iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
534
 
   iterator.itemIndex_ = 0;
535
 
}
536
 
 
537
 
 
538
 
void 
539
 
ValueInternalMap::increment( IteratorState &iterator )
540
 
{
541
 
   JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
542
 
   ++iterator.itemIndex_;
543
 
   if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
544
 
   {
545
 
      JSON_ASSERT_MESSAGE( iterator.link_ != 0,
546
 
         "ValueInternalMap::increment(): attempting to iterate beyond end." );
547
 
      iterator.link_ = iterator.link_->next_;
548
 
      if ( iterator.link_ == 0 )
549
 
         incrementBucket( iterator );
550
 
   }
551
 
   else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
552
 
   {
553
 
      incrementBucket( iterator );
554
 
   }
555
 
}
556
 
 
557
 
 
558
 
void 
559
 
ValueInternalMap::decrement( IteratorState &iterator )
560
 
{
561
 
   if ( iterator.itemIndex_ == 0 )
562
 
   {
563
 
      JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
564
 
      if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
565
 
      {
566
 
         JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
567
 
         --(iterator.bucketIndex_);
568
 
      }
569
 
      iterator.link_ = iterator.link_->previous_;
570
 
      iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
571
 
   }
572
 
}
573
 
 
574
 
 
575
 
const char *
576
 
ValueInternalMap::key( const IteratorState &iterator )
577
 
{
578
 
   JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
579
 
   return iterator.link_->keys_[iterator.itemIndex_];
580
 
}
581
 
 
582
 
const char *
583
 
ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
584
 
{
585
 
   JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
586
 
   isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
587
 
   return iterator.link_->keys_[iterator.itemIndex_];
588
 
}
589
 
 
590
 
 
591
 
Value &
592
 
ValueInternalMap::value( const IteratorState &iterator )
593
 
{
594
 
   JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
595
 
   return iterator.link_->items_[iterator.itemIndex_];
596
 
}
597
 
 
598
 
 
599
 
int 
600
 
ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
601
 
{
602
 
   int offset = 0;
603
 
   IteratorState it = x;
604
 
   while ( !equals( it, y ) )
605
 
      increment( it );
606
 
   return offset;
607
 
}