1
/* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
* JSON Library, originally from http://jsoncpp.sourceforge.net/
5
* Copyright (C) 2011 Stewart Smith
8
* Redistribution and use in source and binary forms, with or without
9
* modification, are permitted provided that the following conditions are
12
* * Redistributions of source code must retain the above copyright
13
* notice, this list of conditions and the following disclaimer.
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
20
* * The names of its contributors may not be used to endorse or
21
* promote products derived from this software without specific prior
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.
39
// included by json_value.cpp
40
// everything is within Json namespace
42
// //////////////////////////////////////////////////////////////////
43
// //////////////////////////////////////////////////////////////////
44
// //////////////////////////////////////////////////////////////////
45
// class ValueInternalMap
46
// //////////////////////////////////////////////////////////////////
47
// //////////////////////////////////////////////////////////////////
48
// //////////////////////////////////////////////////////////////////
50
/** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
51
* This optimization is used by the fast allocator.
53
ValueInternalLink::ValueInternalLink()
59
ValueInternalLink::~ValueInternalLink()
61
for ( int index =0; index < itemPerLink; ++index )
63
if ( !items_[index].isItemAvailable() )
65
if ( !items_[index].isMemberNameStatic() )
75
ValueMapAllocator::~ValueMapAllocator()
79
#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
80
class DefaultValueMapAllocator : public ValueMapAllocator
82
public: // overridden from ValueMapAllocator
83
virtual ValueInternalMap *newMap()
85
return new ValueInternalMap();
88
virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
90
return new ValueInternalMap( other );
93
virtual void destructMap( ValueInternalMap *map )
98
virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
100
return new ValueInternalLink[size];
103
virtual void releaseMapBuckets( ValueInternalLink *links )
108
virtual ValueInternalLink *allocateMapLink()
110
return new ValueInternalLink();
113
virtual void releaseMapLink( ValueInternalLink *link )
119
/// @todo make this thread-safe (lock when accessign batch allocator)
120
class DefaultValueMapAllocator : public ValueMapAllocator
122
public: // overridden from ValueMapAllocator
123
virtual ValueInternalMap *newMap()
125
ValueInternalMap *map = mapsAllocator_.allocate();
126
new (map) ValueInternalMap(); // placement new
130
virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
132
ValueInternalMap *map = mapsAllocator_.allocate();
133
new (map) ValueInternalMap( other ); // placement new
137
virtual void destructMap( ValueInternalMap *map )
141
map->~ValueInternalMap();
142
mapsAllocator_.release( map );
146
virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
148
return new ValueInternalLink[size];
151
virtual void releaseMapBuckets( ValueInternalLink *links )
156
virtual ValueInternalLink *allocateMapLink()
158
ValueInternalLink *link = linksAllocator_.allocate();
159
memset( link, 0, sizeof(ValueInternalLink) );
163
virtual void releaseMapLink( ValueInternalLink *link )
165
link->~ValueInternalLink();
166
linksAllocator_.release( link );
169
BatchAllocator<ValueInternalMap,1> mapsAllocator_;
170
BatchAllocator<ValueInternalLink,1> linksAllocator_;
174
static ValueMapAllocator *&mapAllocator()
176
static DefaultValueMapAllocator defaultAllocator;
177
static ValueMapAllocator *mapAllocator = &defaultAllocator;
181
static struct DummyMapAllocatorInitializer {
182
DummyMapAllocatorInitializer()
184
mapAllocator(); // ensure mapAllocator() statics are initialized before main().
186
} dummyMapAllocatorInitializer;
190
// h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
193
use linked list hash map.
194
buckets array is a container.
195
linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
196
value have extra state: valid, available, deleted
200
ValueInternalMap::ValueInternalMap()
209
ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
215
reserve( other.itemCount_ );
218
other.makeBeginIterator( it );
219
other.makeEndIterator( itEnd );
220
for ( ; !equals(it,itEnd); increment(it) )
223
const char *memberName = key( it, isStatic );
224
const Value &aValue = value( it );
225
resolveReference(memberName, isStatic) = aValue;
231
ValueInternalMap::operator =( const ValueInternalMap &other )
233
ValueInternalMap dummy( other );
239
ValueInternalMap::~ValueInternalMap()
243
for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
245
ValueInternalLink *link = buckets_[bucketIndex].next_;
248
ValueInternalLink *linkToRelease = link;
250
mapAllocator()->releaseMapLink( linkToRelease );
253
mapAllocator()->releaseMapBuckets( buckets_ );
259
ValueInternalMap::swap( ValueInternalMap &other )
261
ValueInternalLink *tempBuckets = buckets_;
262
buckets_ = other.buckets_;
263
other.buckets_ = tempBuckets;
264
ValueInternalLink *tempTailLink = tailLink_;
265
tailLink_ = other.tailLink_;
266
other.tailLink_ = tempTailLink;
267
BucketIndex tempBucketsSize = bucketsSize_;
268
bucketsSize_ = other.bucketsSize_;
269
other.bucketsSize_ = tempBucketsSize;
270
BucketIndex tempItemCount = itemCount_;
271
itemCount_ = other.itemCount_;
272
other.itemCount_ = tempItemCount;
277
ValueInternalMap::clear()
279
ValueInternalMap dummy;
284
ValueInternalMap::BucketIndex
285
ValueInternalMap::size() const
291
ValueInternalMap::reserveDelta( BucketIndex growth )
293
return reserve( itemCount_ + growth );
297
ValueInternalMap::reserve( BucketIndex newItemCount )
299
if ( !buckets_ && newItemCount > 0 )
301
buckets_ = mapAllocator()->allocateMapBuckets( 1 );
303
tailLink_ = &buckets_[0];
305
// BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
311
ValueInternalMap::find( const char *key ) const
315
HashKey hashedKey = hash( key );
316
BucketIndex bucketIndex = hashedKey % bucketsSize_;
317
for ( const ValueInternalLink *current = &buckets_[bucketIndex];
319
current = current->next_ )
321
for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
323
if ( current->items_[index].isItemAvailable() )
325
if ( strcmp( key, current->keys_[index] ) == 0 )
326
return ¤t->items_[index];
334
ValueInternalMap::find( const char *key )
336
const ValueInternalMap *constThis = this;
337
return const_cast<Value *>( constThis->find( key ) );
342
ValueInternalMap::resolveReference( const char *key,
345
HashKey hashedKey = hash( key );
348
BucketIndex bucketIndex = hashedKey % bucketsSize_;
349
ValueInternalLink **previous = 0;
351
for ( ValueInternalLink *current = &buckets_[bucketIndex];
353
previous = ¤t->next_, current = current->next_ )
355
for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
357
if ( current->items_[index].isItemAvailable() )
358
return setNewItem( key, isStatic, current, index );
359
if ( strcmp( key, current->keys_[index] ) == 0 )
360
return current->items_[index];
366
return unsafeAdd( key, isStatic, hashedKey );
371
ValueInternalMap::remove( const char *key )
373
HashKey hashedKey = hash( key );
376
BucketIndex bucketIndex = hashedKey % bucketsSize_;
377
for ( ValueInternalLink *link = &buckets_[bucketIndex];
382
for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
384
if ( link->items_[index].isItemAvailable() )
386
if ( strcmp( key, link->keys_[index] ) == 0 )
388
doActualRemove( link, index, bucketIndex );
396
ValueInternalMap::doActualRemove( ValueInternalLink *link,
398
BucketIndex bucketIndex )
400
// find last item of the bucket and swap it with the 'removed' one.
401
// set removed items flags to 'available'.
402
// if last page only contains 'available' items, then desallocate it (it's empty)
403
ValueInternalLink *&lastLink = getLastLinkInBucket( index );
404
BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
406
lastItemIndex < ValueInternalLink::itemPerLink;
407
++lastItemIndex ) // may be optimized with dicotomic search
409
if ( lastLink->items_[lastItemIndex].isItemAvailable() )
413
BucketIndex lastUsedIndex = lastItemIndex - 1;
414
Value *valueToDelete = &link->items_[index];
415
Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
416
if ( valueToDelete != valueToPreserve )
417
valueToDelete->swap( *valueToPreserve );
418
if ( lastUsedIndex == 0 ) // page is now empty
419
{ // remove it from bucket linked list and delete it.
420
ValueInternalLink *linkPreviousToLast = lastLink->previous_;
421
if ( linkPreviousToLast != 0 ) // can not deleted bucket link.
423
mapAllocator()->releaseMapLink( lastLink );
424
linkPreviousToLast->next_ = 0;
425
lastLink = linkPreviousToLast;
431
valueToPreserve->swap( dummy ); // restore deleted to default Value.
432
valueToPreserve->setItemUsed( false );
439
ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
441
if ( bucketIndex == bucketsSize_ - 1 )
443
ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
445
previous = &buckets_[bucketIndex];
451
ValueInternalMap::setNewItem( const char *key,
453
ValueInternalLink *link,
456
char *duplicatedKey = valueAllocator()->makeMemberName( key );
458
link->keys_[index] = duplicatedKey;
459
link->items_[index].setItemUsed();
460
link->items_[index].setMemberNameIsStatic( isStatic );
461
return link->items_[index]; // items already default constructed.
466
ValueInternalMap::unsafeAdd( const char *key,
470
JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
471
BucketIndex bucketIndex = hashedKey % bucketsSize_;
472
ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
473
ValueInternalLink *link = previousLink;
475
for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
477
if ( link->items_[index].isItemAvailable() )
480
if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
482
ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
484
link->next_ = newLink;
485
previousLink = newLink;
488
return setNewItem( key, isStatic, link, index );
492
ValueInternalMap::HashKey
493
ValueInternalMap::hash( const char *key ) const
503
ValueInternalMap::compare( const ValueInternalMap &other ) const
505
int sizeDiff( itemCount_ - other.itemCount_ );
508
// Strict order guaranty is required. Compare all keys FIRST, then compare values.
511
makeBeginIterator( it );
512
makeEndIterator( itEnd );
513
for ( ; !equals(it,itEnd); increment(it) )
515
if ( !other.find( key( it ) ) )
519
// All keys are equals, let's compare values
520
makeBeginIterator( it );
521
for ( ; !equals(it,itEnd); increment(it) )
523
const Value *otherValue = other.find( key( it ) );
524
int valueDiff = value(it).compare( *otherValue );
525
if ( valueDiff != 0 )
533
ValueInternalMap::makeBeginIterator( IteratorState &it ) const
535
it.map_ = const_cast<ValueInternalMap *>( this );
543
ValueInternalMap::makeEndIterator( IteratorState &it ) const
545
it.map_ = const_cast<ValueInternalMap *>( this );
546
it.bucketIndex_ = bucketsSize_;
553
ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
555
return x.map_ == other.map_
556
&& x.bucketIndex_ == other.bucketIndex_
557
&& x.link_ == other.link_
558
&& x.itemIndex_ == other.itemIndex_;
563
ValueInternalMap::incrementBucket( IteratorState &iterator )
565
++iterator.bucketIndex_;
566
JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
567
"ValueInternalMap::increment(): attempting to iterate beyond end." );
568
if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
571
iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
572
iterator.itemIndex_ = 0;
577
ValueInternalMap::increment( IteratorState &iterator )
579
JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
580
++iterator.itemIndex_;
581
if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
583
JSON_ASSERT_MESSAGE( iterator.link_ != 0,
584
"ValueInternalMap::increment(): attempting to iterate beyond end." );
585
iterator.link_ = iterator.link_->next_;
586
if ( iterator.link_ == 0 )
587
incrementBucket( iterator );
589
else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
591
incrementBucket( iterator );
597
ValueInternalMap::decrement( IteratorState &iterator )
599
if ( iterator.itemIndex_ == 0 )
601
JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
602
if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
604
JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
605
--(iterator.bucketIndex_);
607
iterator.link_ = iterator.link_->previous_;
608
iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
614
ValueInternalMap::key( const IteratorState &iterator )
616
JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
617
return iterator.link_->keys_[iterator.itemIndex_];
621
ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
623
JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
624
isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
625
return iterator.link_->keys_[iterator.itemIndex_];
630
ValueInternalMap::value( const IteratorState &iterator )
632
JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
633
return iterator.link_->items_[iterator.itemIndex_];
638
ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
641
IteratorState it = x;
642
while ( !equals( it, y ) )