1 // Copyright 2007-2010 Baptiste Lepilleur
2 // Distributed under MIT license, or public domain if desired and
3 // recognized in your jurisdiction.
4 // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE
6 // included by json_value.cpp
7 // everything is within Json namespace
9 // //////////////////////////////////////////////////////////////////
10 // //////////////////////////////////////////////////////////////////
11 // //////////////////////////////////////////////////////////////////
12 // class ValueInternalMap
13 // //////////////////////////////////////////////////////////////////
14 // //////////////////////////////////////////////////////////////////
15 // //////////////////////////////////////////////////////////////////
17 /** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
18 * This optimization is used by the fast allocator.
20 ValueInternalLink::ValueInternalLink()
26 ValueInternalLink::~ValueInternalLink()
28 for ( int index =0; index < itemPerLink; ++index )
30 if ( !items_[index].isItemAvailable() )
32 if ( !items_[index].isMemberNameStatic() )
42 ValueMapAllocator::~ValueMapAllocator()
46 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
47 class DefaultValueMapAllocator : public ValueMapAllocator
49 public: // overridden from ValueMapAllocator
50 virtual ValueInternalMap *newMap()
52 return new ValueInternalMap();
55 virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
57 return new ValueInternalMap( other );
60 virtual void destructMap( ValueInternalMap *map )
65 virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
67 return new ValueInternalLink[size];
70 virtual void releaseMapBuckets( ValueInternalLink *links )
75 virtual ValueInternalLink *allocateMapLink()
77 return new ValueInternalLink();
80 virtual void releaseMapLink( ValueInternalLink *link )
86 /// @todo make this thread-safe (lock when accessign batch allocator)
87 class DefaultValueMapAllocator : public ValueMapAllocator
89 public: // overridden from ValueMapAllocator
90 virtual ValueInternalMap *newMap()
92 ValueInternalMap *map = mapsAllocator_.allocate();
93 new (map) ValueInternalMap(); // placement new
97 virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
99 ValueInternalMap *map = mapsAllocator_.allocate();
100 new (map) ValueInternalMap( other ); // placement new
104 virtual void destructMap( ValueInternalMap *map )
108 map->~ValueInternalMap();
109 mapsAllocator_.release( map );
113 virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
115 return new ValueInternalLink[size];
118 virtual void releaseMapBuckets( ValueInternalLink *links )
123 virtual ValueInternalLink *allocateMapLink()
125 ValueInternalLink *link = linksAllocator_.allocate();
126 memset( link, 0, sizeof(ValueInternalLink) );
130 virtual void releaseMapLink( ValueInternalLink *link )
132 link->~ValueInternalLink();
133 linksAllocator_.release( link );
136 BatchAllocator<ValueInternalMap,1> mapsAllocator_;
137 BatchAllocator<ValueInternalLink,1> linksAllocator_;
141 static ValueMapAllocator *&mapAllocator()
143 static DefaultValueMapAllocator defaultAllocator;
144 static ValueMapAllocator *mapAllocator = &defaultAllocator;
148 static struct DummyMapAllocatorInitializer {
149 DummyMapAllocatorInitializer()
151 mapAllocator(); // ensure mapAllocator() statics are initialized before main().
153 } dummyMapAllocatorInitializer;
157 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
160 use linked list hash map.
161 buckets array is a container.
162 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
163 value have extra state: valid, available, deleted
167 ValueInternalMap::ValueInternalMap()
176 ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
182 reserve( other.itemCount_ );
185 other.makeBeginIterator( it );
186 other.makeEndIterator( itEnd );
187 for ( ; !equals(it,itEnd); increment(it) )
190 const char *memberName = key( it, isStatic );
191 const Value &aValue = value( it );
192 resolveReference(memberName, isStatic) = aValue;
198 ValueInternalMap::operator =( const ValueInternalMap &other )
200 ValueInternalMap dummy( other );
206 ValueInternalMap::~ValueInternalMap()
210 for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
212 ValueInternalLink *link = buckets_[bucketIndex].next_;
215 ValueInternalLink *linkToRelease = link;
217 mapAllocator()->releaseMapLink( linkToRelease );
220 mapAllocator()->releaseMapBuckets( buckets_ );
226 ValueInternalMap::swap( ValueInternalMap &other )
228 ValueInternalLink *tempBuckets = buckets_;
229 buckets_ = other.buckets_;
230 other.buckets_ = tempBuckets;
231 ValueInternalLink *tempTailLink = tailLink_;
232 tailLink_ = other.tailLink_;
233 other.tailLink_ = tempTailLink;
234 BucketIndex tempBucketsSize = bucketsSize_;
235 bucketsSize_ = other.bucketsSize_;
236 other.bucketsSize_ = tempBucketsSize;
237 BucketIndex tempItemCount = itemCount_;
238 itemCount_ = other.itemCount_;
239 other.itemCount_ = tempItemCount;
244 ValueInternalMap::clear()
246 ValueInternalMap dummy;
251 ValueInternalMap::BucketIndex
252 ValueInternalMap::size() const
258 ValueInternalMap::reserveDelta( BucketIndex growth )
260 return reserve( itemCount_ + growth );
264 ValueInternalMap::reserve( BucketIndex newItemCount )
266 if ( !buckets_ && newItemCount > 0 )
268 buckets_ = mapAllocator()->allocateMapBuckets( 1 );
270 tailLink_ = &buckets_[0];
272 // BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
278 ValueInternalMap::find( const char *key ) const
282 HashKey hashedKey = hash( key );
283 BucketIndex bucketIndex = hashedKey % bucketsSize_;
284 for ( const ValueInternalLink *current = &buckets_[bucketIndex];
286 current = current->next_ )
288 for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
290 if ( current->items_[index].isItemAvailable() )
292 if ( strcmp( key, current->keys_[index] ) == 0 )
293 return ¤t->items_[index];
301 ValueInternalMap::find( const char *key )
303 const ValueInternalMap *constThis = this;
304 return const_cast<Value *>( constThis->find( key ) );
309 ValueInternalMap::resolveReference( const char *key,
312 HashKey hashedKey = hash( key );
315 BucketIndex bucketIndex = hashedKey % bucketsSize_;
316 ValueInternalLink **previous = 0;
318 for ( ValueInternalLink *current = &buckets_[bucketIndex];
320 previous = ¤t->next_, current = current->next_ )
322 for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
324 if ( current->items_[index].isItemAvailable() )
325 return setNewItem( key, isStatic, current, index );
326 if ( strcmp( key, current->keys_[index] ) == 0 )
327 return current->items_[index];
333 return unsafeAdd( key, isStatic, hashedKey );
338 ValueInternalMap::remove( const char *key )
340 HashKey hashedKey = hash( key );
343 BucketIndex bucketIndex = hashedKey % bucketsSize_;
344 for ( ValueInternalLink *link = &buckets_[bucketIndex];
349 for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
351 if ( link->items_[index].isItemAvailable() )
353 if ( strcmp( key, link->keys_[index] ) == 0 )
355 doActualRemove( link, index, bucketIndex );
363 ValueInternalMap::doActualRemove( ValueInternalLink *link,
365 BucketIndex bucketIndex )
367 // find last item of the bucket and swap it with the 'removed' one.
368 // set removed items flags to 'available'.
369 // if last page only contains 'available' items, then desallocate it (it's empty)
370 ValueInternalLink *&lastLink = getLastLinkInBucket( index );
371 BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
373 lastItemIndex < ValueInternalLink::itemPerLink;
374 ++lastItemIndex ) // may be optimized with dicotomic search
376 if ( lastLink->items_[lastItemIndex].isItemAvailable() )
380 BucketIndex lastUsedIndex = lastItemIndex - 1;
381 Value *valueToDelete = &link->items_[index];
382 Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
383 if ( valueToDelete != valueToPreserve )
384 valueToDelete->swap( *valueToPreserve );
385 if ( lastUsedIndex == 0 ) // page is now empty
386 { // remove it from bucket linked list and delete it.
387 ValueInternalLink *linkPreviousToLast = lastLink->previous_;
388 if ( linkPreviousToLast != 0 ) // can not deleted bucket link.
390 mapAllocator()->releaseMapLink( lastLink );
391 linkPreviousToLast->next_ = 0;
392 lastLink = linkPreviousToLast;
398 valueToPreserve->swap( dummy ); // restore deleted to default Value.
399 valueToPreserve->setItemUsed( false );
406 ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
408 if ( bucketIndex == bucketsSize_ - 1 )
410 ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
412 previous = &buckets_[bucketIndex];
418 ValueInternalMap::setNewItem( const char *key,
420 ValueInternalLink *link,
423 char *duplicatedKey = makeMemberName( key );
425 link->keys_[index] = duplicatedKey;
426 link->items_[index].setItemUsed();
427 link->items_[index].setMemberNameIsStatic( isStatic );
428 return link->items_[index]; // items already default constructed.
433 ValueInternalMap::unsafeAdd( const char *key,
437 JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
438 BucketIndex bucketIndex = hashedKey % bucketsSize_;
439 ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
440 ValueInternalLink *link = previousLink;
442 for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
444 if ( link->items_[index].isItemAvailable() )
447 if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
449 ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
451 link->next_ = newLink;
452 previousLink = newLink;
455 return setNewItem( key, isStatic, link, index );
459 ValueInternalMap::HashKey
460 ValueInternalMap::hash( const char *key ) const
470 ValueInternalMap::compare( const ValueInternalMap &other ) const
472 int sizeDiff( itemCount_ - other.itemCount_ );
475 // Strict order guaranty is required. Compare all keys FIRST, then compare values.
478 makeBeginIterator( it );
479 makeEndIterator( itEnd );
480 for ( ; !equals(it,itEnd); increment(it) )
482 if ( !other.find( key( it ) ) )
486 // All keys are equals, let's compare values
487 makeBeginIterator( it );
488 for ( ; !equals(it,itEnd); increment(it) )
490 const Value *otherValue = other.find( key( it ) );
491 int valueDiff = value(it).compare( *otherValue );
492 if ( valueDiff != 0 )
500 ValueInternalMap::makeBeginIterator( IteratorState &it ) const
502 it.map_ = const_cast<ValueInternalMap *>( this );
510 ValueInternalMap::makeEndIterator( IteratorState &it ) const
512 it.map_ = const_cast<ValueInternalMap *>( this );
513 it.bucketIndex_ = bucketsSize_;
520 ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
522 return x.map_ == other.map_
523 && x.bucketIndex_ == other.bucketIndex_
524 && x.link_ == other.link_
525 && x.itemIndex_ == other.itemIndex_;
530 ValueInternalMap::incrementBucket( IteratorState &iterator )
532 ++iterator.bucketIndex_;
533 JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
534 "ValueInternalMap::increment(): attempting to iterate beyond end." );
535 if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
538 iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
539 iterator.itemIndex_ = 0;
544 ValueInternalMap::increment( IteratorState &iterator )
546 JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
547 ++iterator.itemIndex_;
548 if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
550 JSON_ASSERT_MESSAGE( iterator.link_ != 0,
551 "ValueInternalMap::increment(): attempting to iterate beyond end." );
552 iterator.link_ = iterator.link_->next_;
553 if ( iterator.link_ == 0 )
554 incrementBucket( iterator );
556 else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
558 incrementBucket( iterator );
564 ValueInternalMap::decrement( IteratorState &iterator )
566 if ( iterator.itemIndex_ == 0 )
568 JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
569 if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
571 JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
572 --(iterator.bucketIndex_);
574 iterator.link_ = iterator.link_->previous_;
575 iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
581 ValueInternalMap::key( const IteratorState &iterator )
583 JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
584 return iterator.link_->keys_[iterator.itemIndex_];
588 ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
590 JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
591 isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
592 return iterator.link_->keys_[iterator.itemIndex_];
597 ValueInternalMap::value( const IteratorState &iterator )
599 JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
600 return iterator.link_->items_[iterator.itemIndex_];
605 ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
608 IteratorState it = x;
609 while ( !equals( it, y ) )