diff options
Diffstat (limited to 'src/lib_json/json_internalmap.inl')
| -rw-r--r-- | src/lib_json/json_internalmap.inl | 982 |
1 files changed, 420 insertions, 562 deletions
diff --git a/src/lib_json/json_internalmap.inl b/src/lib_json/json_internalmap.inl index f2fa160..ef3f330 100644 --- a/src/lib_json/json_internalmap.inl +++ b/src/lib_json/json_internalmap.inl @@ -15,601 +15,459 @@ namespace Json { // ////////////////////////////////////////////////////////////////// // ////////////////////////////////////////////////////////////////// -/** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) ); +/** \internal MUST be safely initialized using memset( this, 0, + * sizeof(ValueInternalLink) ); * This optimization is used by the fast allocator. */ -ValueInternalLink::ValueInternalLink() - : previous_( 0 ) - , next_( 0 ) -{ -} +ValueInternalLink::ValueInternalLink() : previous_(0), next_(0) {} -ValueInternalLink::~ValueInternalLink() -{ - for ( int index =0; index < itemPerLink; ++index ) - { - if ( !items_[index].isItemAvailable() ) - { - if ( !items_[index].isMemberNameStatic() ) - free( keys_[index] ); - } - else - break; - } +ValueInternalLink::~ValueInternalLink() { + for (int index = 0; index < itemPerLink; ++index) { + if (!items_[index].isItemAvailable()) { + if (!items_[index].isMemberNameStatic()) + free(keys_[index]); + } else + break; + } } - - -ValueMapAllocator::~ValueMapAllocator() -{ -} +ValueMapAllocator::~ValueMapAllocator() {} #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR -class DefaultValueMapAllocator : public ValueMapAllocator -{ +class DefaultValueMapAllocator : public ValueMapAllocator { public: // overridden from ValueMapAllocator - virtual ValueInternalMap *newMap() - { - return new ValueInternalMap(); - } - - virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other ) - { - return new ValueInternalMap( other ); - } - - virtual void destructMap( ValueInternalMap *map ) - { - delete map; - } - - virtual ValueInternalLink *allocateMapBuckets( unsigned int size ) - { - return new ValueInternalLink[size]; - } - - virtual void releaseMapBuckets( ValueInternalLink *links ) - { - delete [] links; - } - - virtual ValueInternalLink *allocateMapLink() - { - return new ValueInternalLink(); - } - - virtual void releaseMapLink( ValueInternalLink *link ) - { - delete link; - } + virtual ValueInternalMap* newMap() { return new ValueInternalMap(); } + + virtual ValueInternalMap* newMapCopy(const ValueInternalMap& other) { + return new ValueInternalMap(other); + } + + virtual void destructMap(ValueInternalMap* map) { delete map; } + + virtual ValueInternalLink* allocateMapBuckets(unsigned int size) { + return new ValueInternalLink[size]; + } + + virtual void releaseMapBuckets(ValueInternalLink* links) { delete[] links; } + + virtual ValueInternalLink* allocateMapLink() { + return new ValueInternalLink(); + } + + virtual void releaseMapLink(ValueInternalLink* link) { delete link; } }; #else /// @todo make this thread-safe (lock when accessign batch allocator) -class DefaultValueMapAllocator : public ValueMapAllocator -{ +class DefaultValueMapAllocator : public ValueMapAllocator { public: // overridden from ValueMapAllocator - virtual ValueInternalMap *newMap() - { - ValueInternalMap *map = mapsAllocator_.allocate(); - new (map) ValueInternalMap(); // placement new - return map; - } - - virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other ) - { - ValueInternalMap *map = mapsAllocator_.allocate(); - new (map) ValueInternalMap( other ); // placement new - return map; - } - - virtual void destructMap( ValueInternalMap *map ) - { - if ( map ) - { - map->~ValueInternalMap(); - mapsAllocator_.release( map ); - } - } - - virtual ValueInternalLink *allocateMapBuckets( unsigned int size ) - { - return new ValueInternalLink[size]; - } - - virtual void releaseMapBuckets( ValueInternalLink *links ) - { - delete [] links; - } - - virtual ValueInternalLink *allocateMapLink() - { - ValueInternalLink *link = linksAllocator_.allocate(); - memset( link, 0, sizeof(ValueInternalLink) ); - return link; - } - - virtual void releaseMapLink( ValueInternalLink *link ) - { - link->~ValueInternalLink(); - linksAllocator_.release( link ); - } + virtual ValueInternalMap* newMap() { + ValueInternalMap* map = mapsAllocator_.allocate(); + new (map) ValueInternalMap(); // placement new + return map; + } + + virtual ValueInternalMap* newMapCopy(const ValueInternalMap& other) { + ValueInternalMap* map = mapsAllocator_.allocate(); + new (map) ValueInternalMap(other); // placement new + return map; + } + + virtual void destructMap(ValueInternalMap* map) { + if (map) { + map->~ValueInternalMap(); + mapsAllocator_.release(map); + } + } + + virtual ValueInternalLink* allocateMapBuckets(unsigned int size) { + return new ValueInternalLink[size]; + } + + virtual void releaseMapBuckets(ValueInternalLink* links) { delete[] links; } + + virtual ValueInternalLink* allocateMapLink() { + ValueInternalLink* link = linksAllocator_.allocate(); + memset(link, 0, sizeof(ValueInternalLink)); + return link; + } + + virtual void releaseMapLink(ValueInternalLink* link) { + link->~ValueInternalLink(); + linksAllocator_.release(link); + } + private: - BatchAllocator<ValueInternalMap,1> mapsAllocator_; - BatchAllocator<ValueInternalLink,1> linksAllocator_; + BatchAllocator<ValueInternalMap, 1> mapsAllocator_; + BatchAllocator<ValueInternalLink, 1> linksAllocator_; }; #endif -static ValueMapAllocator *&mapAllocator() -{ - static DefaultValueMapAllocator defaultAllocator; - static ValueMapAllocator *mapAllocator = &defaultAllocator; - return mapAllocator; +static ValueMapAllocator*& mapAllocator() { + static DefaultValueMapAllocator defaultAllocator; + static ValueMapAllocator* mapAllocator = &defaultAllocator; + return mapAllocator; } static struct DummyMapAllocatorInitializer { - DummyMapAllocatorInitializer() - { - mapAllocator(); // ensure mapAllocator() statics are initialized before main(). - } + DummyMapAllocatorInitializer() { + mapAllocator(); // ensure mapAllocator() statics are initialized before + // main(). + } } dummyMapAllocatorInitializer; - - // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32. /* -use linked list hash map. +use linked list hash map. buckets array is a container. linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124) value have extra state: valid, available, deleted */ - ValueInternalMap::ValueInternalMap() - : buckets_( 0 ) - , tailLink_( 0 ) - , bucketsSize_( 0 ) - , itemCount_( 0 ) -{ -} - - -ValueInternalMap::ValueInternalMap( const ValueInternalMap &other ) - : buckets_( 0 ) - , tailLink_( 0 ) - , bucketsSize_( 0 ) - , itemCount_( 0 ) -{ - reserve( other.itemCount_ ); - IteratorState it; - IteratorState itEnd; - other.makeBeginIterator( it ); - other.makeEndIterator( itEnd ); - for ( ; !equals(it,itEnd); increment(it) ) - { - bool isStatic; - const char *memberName = key( it, isStatic ); - const Value &aValue = value( it ); - resolveReference(memberName, isStatic) = aValue; - } -} - - -ValueInternalMap & -ValueInternalMap::operator =( const ValueInternalMap &other ) -{ - ValueInternalMap dummy( other ); - swap( dummy ); - return *this; -} - - -ValueInternalMap::~ValueInternalMap() -{ - if ( buckets_ ) - { - for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex ) - { - ValueInternalLink *link = buckets_[bucketIndex].next_; - while ( link ) - { - ValueInternalLink *linkToRelease = link; - link = link->next_; - mapAllocator()->releaseMapLink( linkToRelease ); - } - } - mapAllocator()->releaseMapBuckets( buckets_ ); - } -} - - -void -ValueInternalMap::swap( ValueInternalMap &other ) -{ - ValueInternalLink *tempBuckets = buckets_; - buckets_ = other.buckets_; - other.buckets_ = tempBuckets; - ValueInternalLink *tempTailLink = tailLink_; - tailLink_ = other.tailLink_; - other.tailLink_ = tempTailLink; - BucketIndex tempBucketsSize = bucketsSize_; - bucketsSize_ = other.bucketsSize_; - other.bucketsSize_ = tempBucketsSize; - BucketIndex tempItemCount = itemCount_; - itemCount_ = other.itemCount_; - other.itemCount_ = tempItemCount; -} - - -void -ValueInternalMap::clear() -{ - ValueInternalMap dummy; - swap( dummy ); -} - - -ValueInternalMap::BucketIndex -ValueInternalMap::size() const -{ - return itemCount_; -} - -bool -ValueInternalMap::reserveDelta( BucketIndex growth ) -{ - return reserve( itemCount_ + growth ); -} - -bool -ValueInternalMap::reserve( BucketIndex newItemCount ) -{ - if ( !buckets_ && newItemCount > 0 ) - { - buckets_ = mapAllocator()->allocateMapBuckets( 1 ); - bucketsSize_ = 1; - tailLink_ = &buckets_[0]; - } -// BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink; - return true; -} - - -const Value * -ValueInternalMap::find( const char *key ) const -{ - if ( !bucketsSize_ ) - return 0; - HashKey hashedKey = hash( key ); - BucketIndex bucketIndex = hashedKey % bucketsSize_; - for ( const ValueInternalLink *current = &buckets_[bucketIndex]; - current != 0; - current = current->next_ ) - { - for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index ) - { - if ( current->items_[index].isItemAvailable() ) - return 0; - if ( strcmp( key, current->keys_[index] ) == 0 ) - return ¤t->items_[index]; - } - } - return 0; -} - - -Value * -ValueInternalMap::find( const char *key ) -{ - const ValueInternalMap *constThis = this; - return const_cast<Value *>( constThis->find( key ) ); -} - - -Value & -ValueInternalMap::resolveReference( const char *key, - bool isStatic ) -{ - HashKey hashedKey = hash( key ); - if ( bucketsSize_ ) - { - BucketIndex bucketIndex = hashedKey % bucketsSize_; - ValueInternalLink **previous = 0; - BucketIndex index; - for ( ValueInternalLink *current = &buckets_[bucketIndex]; - current != 0; - previous = ¤t->next_, current = current->next_ ) - { - for ( index=0; index < ValueInternalLink::itemPerLink; ++index ) - { - if ( current->items_[index].isItemAvailable() ) - return setNewItem( key, isStatic, current, index ); - if ( strcmp( key, current->keys_[index] ) == 0 ) - return current->items_[index]; - } - } - } - - reserveDelta( 1 ); - return unsafeAdd( key, isStatic, hashedKey ); -} - - -void -ValueInternalMap::remove( const char *key ) -{ - HashKey hashedKey = hash( key ); - if ( !bucketsSize_ ) - return; - BucketIndex bucketIndex = hashedKey % bucketsSize_; - for ( ValueInternalLink *link = &buckets_[bucketIndex]; - link != 0; - link = link->next_ ) - { - BucketIndex index; - for ( index =0; index < ValueInternalLink::itemPerLink; ++index ) - { - if ( link->items_[index].isItemAvailable() ) - return; - if ( strcmp( key, link->keys_[index] ) == 0 ) - { - doActualRemove( link, index, bucketIndex ); - return; - } + : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) {} + +ValueInternalMap::ValueInternalMap(const ValueInternalMap& other) + : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) { + reserve(other.itemCount_); + IteratorState it; + IteratorState itEnd; + other.makeBeginIterator(it); + other.makeEndIterator(itEnd); + for (; !equals(it, itEnd); increment(it)) { + bool isStatic; + const char* memberName = key(it, isStatic); + const Value& aValue = value(it); + resolveReference(memberName, isStatic) = aValue; + } +} + +ValueInternalMap& ValueInternalMap::operator=(ValueInternalMap other) { + swap(other); + return *this; +} + +ValueInternalMap::~ValueInternalMap() { + if (buckets_) { + for (BucketIndex bucketIndex = 0; bucketIndex < bucketsSize_; + ++bucketIndex) { + ValueInternalLink* link = buckets_[bucketIndex].next_; + while (link) { + ValueInternalLink* linkToRelease = link; + link = link->next_; + mapAllocator()->releaseMapLink(linkToRelease); } - } -} - -void -ValueInternalMap::doActualRemove( ValueInternalLink *link, - BucketIndex index, - BucketIndex bucketIndex ) -{ - // find last item of the bucket and swap it with the 'removed' one. - // set removed items flags to 'available'. - // if last page only contains 'available' items, then desallocate it (it's empty) - ValueInternalLink *&lastLink = getLastLinkInBucket( index ); - BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1 - for ( ; - lastItemIndex < ValueInternalLink::itemPerLink; - ++lastItemIndex ) // may be optimized with dicotomic search - { - if ( lastLink->items_[lastItemIndex].isItemAvailable() ) - break; - } - - BucketIndex lastUsedIndex = lastItemIndex - 1; - Value *valueToDelete = &link->items_[index]; - Value *valueToPreserve = &lastLink->items_[lastUsedIndex]; - if ( valueToDelete != valueToPreserve ) - valueToDelete->swap( *valueToPreserve ); - if ( lastUsedIndex == 0 ) // page is now empty - { // remove it from bucket linked list and delete it. - ValueInternalLink *linkPreviousToLast = lastLink->previous_; - if ( linkPreviousToLast != 0 ) // can not deleted bucket link. - { - mapAllocator()->releaseMapLink( lastLink ); - linkPreviousToLast->next_ = 0; - lastLink = linkPreviousToLast; + } + mapAllocator()->releaseMapBuckets(buckets_); + } +} + +void ValueInternalMap::swap(ValueInternalMap& other) { + ValueInternalLink* tempBuckets = buckets_; + buckets_ = other.buckets_; + other.buckets_ = tempBuckets; + ValueInternalLink* tempTailLink = tailLink_; + tailLink_ = other.tailLink_; + other.tailLink_ = tempTailLink; + BucketIndex tempBucketsSize = bucketsSize_; + bucketsSize_ = other.bucketsSize_; + other.bucketsSize_ = tempBucketsSize; + BucketIndex tempItemCount = itemCount_; + itemCount_ = other.itemCount_; + other.itemCount_ = tempItemCount; +} + +void ValueInternalMap::clear() { + ValueInternalMap dummy; + swap(dummy); +} + +ValueInternalMap::BucketIndex ValueInternalMap::size() const { + return itemCount_; +} + +bool ValueInternalMap::reserveDelta(BucketIndex growth) { + return reserve(itemCount_ + growth); +} + +bool ValueInternalMap::reserve(BucketIndex newItemCount) { + if (!buckets_ && newItemCount > 0) { + buckets_ = mapAllocator()->allocateMapBuckets(1); + bucketsSize_ = 1; + tailLink_ = &buckets_[0]; + } + // BucketIndex idealBucketCount = (newItemCount + + // ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink; + return true; +} + +const Value* ValueInternalMap::find(const char* key) const { + if (!bucketsSize_) + return 0; + HashKey hashedKey = hash(key); + BucketIndex bucketIndex = hashedKey % bucketsSize_; + for (const ValueInternalLink* current = &buckets_[bucketIndex]; current != 0; + current = current->next_) { + for (BucketIndex index = 0; index < ValueInternalLink::itemPerLink; + ++index) { + if (current->items_[index].isItemAvailable()) + return 0; + if (strcmp(key, current->keys_[index]) == 0) + return ¤t->items_[index]; + } + } + return 0; +} + +Value* ValueInternalMap::find(const char* key) { + const ValueInternalMap* constThis = this; + return const_cast<Value*>(constThis->find(key)); +} + +Value& ValueInternalMap::resolveReference(const char* key, bool isStatic) { + HashKey hashedKey = hash(key); + if (bucketsSize_) { + BucketIndex bucketIndex = hashedKey % bucketsSize_; + ValueInternalLink** previous = 0; + BucketIndex index; + for (ValueInternalLink* current = &buckets_[bucketIndex]; current != 0; + previous = ¤t->next_, current = current->next_) { + for (index = 0; index < ValueInternalLink::itemPerLink; ++index) { + if (current->items_[index].isItemAvailable()) + return setNewItem(key, isStatic, current, index); + if (strcmp(key, current->keys_[index]) == 0) + return current->items_[index]; } - } - else - { - Value dummy; - valueToPreserve->swap( dummy ); // restore deleted to default Value. - valueToPreserve->setItemUsed( false ); - } - --itemCount_; -} - - -ValueInternalLink *& -ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex ) -{ - if ( bucketIndex == bucketsSize_ - 1 ) - return tailLink_; - ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_; - if ( !previous ) - previous = &buckets_[bucketIndex]; - return previous; -} - - -Value & -ValueInternalMap::setNewItem( const char *key, - bool isStatic, - ValueInternalLink *link, - BucketIndex index ) -{ - char *duplicatedKey = makeMemberName( key ); - ++itemCount_; - link->keys_[index] = duplicatedKey; - link->items_[index].setItemUsed(); - link->items_[index].setMemberNameIsStatic( isStatic ); - return link->items_[index]; // items already default constructed. -} - - -Value & -ValueInternalMap::unsafeAdd( const char *key, - bool isStatic, - HashKey hashedKey ) -{ - JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." ); - BucketIndex bucketIndex = hashedKey % bucketsSize_; - ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex ); - ValueInternalLink *link = previousLink; - BucketIndex index; - for ( index =0; index < ValueInternalLink::itemPerLink; ++index ) - { - if ( link->items_[index].isItemAvailable() ) - break; - } - if ( index == ValueInternalLink::itemPerLink ) // need to add a new page - { - ValueInternalLink *newLink = mapAllocator()->allocateMapLink(); - index = 0; - link->next_ = newLink; - previousLink = newLink; - link = newLink; - } - return setNewItem( key, isStatic, link, index ); -} - - -ValueInternalMap::HashKey -ValueInternalMap::hash( const char *key ) const -{ - HashKey hash = 0; - while ( *key ) - hash += *key++ * 37; - return hash; -} - - -int -ValueInternalMap::compare( const ValueInternalMap &other ) const -{ - int sizeDiff( itemCount_ - other.itemCount_ ); - if ( sizeDiff != 0 ) - return sizeDiff; - // Strict order guaranty is required. Compare all keys FIRST, then compare values. - IteratorState it; - IteratorState itEnd; - makeBeginIterator( it ); - makeEndIterator( itEnd ); - for ( ; !equals(it,itEnd); increment(it) ) - { - if ( !other.find( key( it ) ) ) - return 1; - } - - // All keys are equals, let's compare values - makeBeginIterator( it ); - for ( ; !equals(it,itEnd); increment(it) ) - { - const Value *otherValue = other.find( key( it ) ); - int valueDiff = value(it).compare( *otherValue ); - if ( valueDiff != 0 ) - return valueDiff; - } - return 0; -} - - -void -ValueInternalMap::makeBeginIterator( IteratorState &it ) const -{ - it.map_ = const_cast<ValueInternalMap *>( this ); - it.bucketIndex_ = 0; - it.itemIndex_ = 0; - it.link_ = buckets_; -} - - -void -ValueInternalMap::makeEndIterator( IteratorState &it ) const -{ - it.map_ = const_cast<ValueInternalMap *>( this ); - it.bucketIndex_ = bucketsSize_; - it.itemIndex_ = 0; - it.link_ = 0; -} - - -bool -ValueInternalMap::equals( const IteratorState &x, const IteratorState &other ) -{ - return x.map_ == other.map_ - && x.bucketIndex_ == other.bucketIndex_ - && x.link_ == other.link_ - && x.itemIndex_ == other.itemIndex_; -} - - -void -ValueInternalMap::incrementBucket( IteratorState &iterator ) -{ - ++iterator.bucketIndex_; - JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_, - "ValueInternalMap::increment(): attempting to iterate beyond end." ); - if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ ) - iterator.link_ = 0; - else - iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]); - iterator.itemIndex_ = 0; -} - - -void -ValueInternalMap::increment( IteratorState &iterator ) -{ - JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." ); - ++iterator.itemIndex_; - if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink ) - { - JSON_ASSERT_MESSAGE( iterator.link_ != 0, - "ValueInternalMap::increment(): attempting to iterate beyond end." ); - iterator.link_ = iterator.link_->next_; - if ( iterator.link_ == 0 ) - incrementBucket( iterator ); - } - else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() ) - { - incrementBucket( iterator ); - } -} - - -void -ValueInternalMap::decrement( IteratorState &iterator ) -{ - if ( iterator.itemIndex_ == 0 ) - { - JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." ); - if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] ) - { - JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." ); - --(iterator.bucketIndex_); + } + } + + reserveDelta(1); + return unsafeAdd(key, isStatic, hashedKey); +} + +void ValueInternalMap::remove(const char* key) { + HashKey hashedKey = hash(key); + if (!bucketsSize_) + return; + BucketIndex bucketIndex = hashedKey % bucketsSize_; + for (ValueInternalLink* link = &buckets_[bucketIndex]; link != 0; + link = link->next_) { + BucketIndex index; + for (index = 0; index < ValueInternalLink::itemPerLink; ++index) { + if (link->items_[index].isItemAvailable()) + return; + if (strcmp(key, link->keys_[index]) == 0) { + doActualRemove(link, index, bucketIndex); + return; } - iterator.link_ = iterator.link_->previous_; - iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1; - } -} - - -const char * -ValueInternalMap::key( const IteratorState &iterator ) -{ - JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." ); - return iterator.link_->keys_[iterator.itemIndex_]; -} - -const char * -ValueInternalMap::key( const IteratorState &iterator, bool &isStatic ) -{ - JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." ); - isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic(); - return iterator.link_->keys_[iterator.itemIndex_]; -} - - -Value & -ValueInternalMap::value( const IteratorState &iterator ) -{ - JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." ); - return iterator.link_->items_[iterator.itemIndex_]; -} - - -int -ValueInternalMap::distance( const IteratorState &x, const IteratorState &y ) -{ - int offset = 0; - IteratorState it = x; - while ( !equals( it, y ) ) - increment( it ); - return offset; + } + } +} + +void ValueInternalMap::doActualRemove(ValueInternalLink* link, + BucketIndex index, + BucketIndex bucketIndex) { + // find last item of the bucket and swap it with the 'removed' one. + // set removed items flags to 'available'. + // if last page only contains 'available' items, then desallocate it (it's + // empty) + ValueInternalLink*& lastLink = getLastLinkInBucket(index); + BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1 + for (; lastItemIndex < ValueInternalLink::itemPerLink; + ++lastItemIndex) // may be optimized with dicotomic search + { + if (lastLink->items_[lastItemIndex].isItemAvailable()) + break; + } + + BucketIndex lastUsedIndex = lastItemIndex - 1; + Value* valueToDelete = &link->items_[index]; + Value* valueToPreserve = &lastLink->items_[lastUsedIndex]; + if (valueToDelete != valueToPreserve) + valueToDelete->swap(*valueToPreserve); + if (lastUsedIndex == 0) // page is now empty + { // remove it from bucket linked list and delete it. + ValueInternalLink* linkPreviousToLast = lastLink->previous_; + if (linkPreviousToLast != 0) // can not deleted bucket link. + { + mapAllocator()->releaseMapLink(lastLink); + linkPreviousToLast->next_ = 0; + lastLink = linkPreviousToLast; + } + } else { + Value dummy; + valueToPreserve->swap(dummy); // restore deleted to default Value. + valueToPreserve->setItemUsed(false); + } + --itemCount_; +} + +ValueInternalLink*& +ValueInternalMap::getLastLinkInBucket(BucketIndex bucketIndex) { + if (bucketIndex == bucketsSize_ - 1) + return tailLink_; + ValueInternalLink*& previous = buckets_[bucketIndex + 1].previous_; + if (!previous) + previous = &buckets_[bucketIndex]; + return previous; +} + +Value& ValueInternalMap::setNewItem(const char* key, + bool isStatic, + ValueInternalLink* link, + BucketIndex index) { + char* duplicatedKey = makeMemberName(key); + ++itemCount_; + link->keys_[index] = duplicatedKey; + link->items_[index].setItemUsed(); + link->items_[index].setMemberNameIsStatic(isStatic); + return link->items_[index]; // items already default constructed. +} + +Value& +ValueInternalMap::unsafeAdd(const char* key, bool isStatic, HashKey hashedKey) { + JSON_ASSERT_MESSAGE(bucketsSize_ > 0, + "ValueInternalMap::unsafeAdd(): internal logic error."); + BucketIndex bucketIndex = hashedKey % bucketsSize_; + ValueInternalLink*& previousLink = getLastLinkInBucket(bucketIndex); + ValueInternalLink* link = previousLink; + BucketIndex index; + for (index = 0; index < ValueInternalLink::itemPerLink; ++index) { + if (link->items_[index].isItemAvailable()) + break; + } + if (index == ValueInternalLink::itemPerLink) // need to add a new page + { + ValueInternalLink* newLink = mapAllocator()->allocateMapLink(); + index = 0; + link->next_ = newLink; + previousLink = newLink; + link = newLink; + } + return setNewItem(key, isStatic, link, index); +} + +ValueInternalMap::HashKey ValueInternalMap::hash(const char* key) const { + HashKey hash = 0; + while (*key) + hash += *key++ * 37; + return hash; +} + +int ValueInternalMap::compare(const ValueInternalMap& other) const { + int sizeDiff(itemCount_ - other.itemCount_); + if (sizeDiff != 0) + return sizeDiff; + // Strict order guaranty is required. Compare all keys FIRST, then compare + // values. + IteratorState it; + IteratorState itEnd; + makeBeginIterator(it); + makeEndIterator(itEnd); + for (; !equals(it, itEnd); increment(it)) { + if (!other.find(key(it))) + return 1; + } + + // All keys are equals, let's compare values + makeBeginIterator(it); + for (; !equals(it, itEnd); increment(it)) { + const Value* otherValue = other.find(key(it)); + int valueDiff = value(it).compare(*otherValue); + if (valueDiff != 0) + return valueDiff; + } + return 0; +} + +void ValueInternalMap::makeBeginIterator(IteratorState& it) const { + it.map_ = const_cast<ValueInternalMap*>(this); + it.bucketIndex_ = 0; + it.itemIndex_ = 0; + it.link_ = buckets_; +} + +void ValueInternalMap::makeEndIterator(IteratorState& it) const { + it.map_ = const_cast<ValueInternalMap*>(this); + it.bucketIndex_ = bucketsSize_; + it.itemIndex_ = 0; + it.link_ = 0; +} + +bool ValueInternalMap::equals(const IteratorState& x, + const IteratorState& other) { + return x.map_ == other.map_ && x.bucketIndex_ == other.bucketIndex_ && + x.link_ == other.link_ && x.itemIndex_ == other.itemIndex_; +} + +void ValueInternalMap::incrementBucket(IteratorState& iterator) { + ++iterator.bucketIndex_; + JSON_ASSERT_MESSAGE( + iterator.bucketIndex_ <= iterator.map_->bucketsSize_, + "ValueInternalMap::increment(): attempting to iterate beyond end."); + if (iterator.bucketIndex_ == iterator.map_->bucketsSize_) + iterator.link_ = 0; + else + iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]); + iterator.itemIndex_ = 0; +} + +void ValueInternalMap::increment(IteratorState& iterator) { + JSON_ASSERT_MESSAGE(iterator.map_, + "Attempting to iterator using invalid iterator."); + ++iterator.itemIndex_; + if (iterator.itemIndex_ == ValueInternalLink::itemPerLink) { + JSON_ASSERT_MESSAGE( + iterator.link_ != 0, + "ValueInternalMap::increment(): attempting to iterate beyond end."); + iterator.link_ = iterator.link_->next_; + if (iterator.link_ == 0) + incrementBucket(iterator); + } else if (iterator.link_->items_[iterator.itemIndex_].isItemAvailable()) { + incrementBucket(iterator); + } +} + +void ValueInternalMap::decrement(IteratorState& iterator) { + if (iterator.itemIndex_ == 0) { + JSON_ASSERT_MESSAGE(iterator.map_, + "Attempting to iterate using invalid iterator."); + if (iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_]) { + JSON_ASSERT_MESSAGE(iterator.bucketIndex_ > 0, + "Attempting to iterate beyond beginning."); + --(iterator.bucketIndex_); + } + iterator.link_ = iterator.link_->previous_; + iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1; + } +} + +const char* ValueInternalMap::key(const IteratorState& iterator) { + JSON_ASSERT_MESSAGE(iterator.link_, + "Attempting to iterate using invalid iterator."); + return iterator.link_->keys_[iterator.itemIndex_]; +} + +const char* ValueInternalMap::key(const IteratorState& iterator, + bool& isStatic) { + JSON_ASSERT_MESSAGE(iterator.link_, + "Attempting to iterate using invalid iterator."); + isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic(); + return iterator.link_->keys_[iterator.itemIndex_]; +} + +Value& ValueInternalMap::value(const IteratorState& iterator) { + JSON_ASSERT_MESSAGE(iterator.link_, + "Attempting to iterate using invalid iterator."); + return iterator.link_->items_[iterator.itemIndex_]; +} + +int ValueInternalMap::distance(const IteratorState& x, const IteratorState& y) { + int offset = 0; + IteratorState it = x; + while (!equals(it, y)) + increment(it); + return offset; } } // namespace Json |