diff options
Diffstat (limited to 'src/lib_json/json_internalmap.inl')
| -rw-r--r-- | src/lib_json/json_internalmap.inl | 473 |
1 files changed, 0 insertions, 473 deletions
diff --git a/src/lib_json/json_internalmap.inl b/src/lib_json/json_internalmap.inl deleted file mode 100644 index ef3f330..0000000 --- a/src/lib_json/json_internalmap.inl +++ /dev/null @@ -1,473 +0,0 @@ -// Copyright 2007-2010 Baptiste Lepilleur -// Distributed under MIT license, or public domain if desired and -// recognized in your jurisdiction. -// See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE - -// included by json_value.cpp - -namespace Json { - -// ////////////////////////////////////////////////////////////////// -// ////////////////////////////////////////////////////////////////// -// ////////////////////////////////////////////////////////////////// -// class ValueInternalMap -// ////////////////////////////////////////////////////////////////// -// ////////////////////////////////////////////////////////////////// -// ////////////////////////////////////////////////////////////////// - -/** \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() { - for (int index = 0; index < itemPerLink; ++index) { - if (!items_[index].isItemAvailable()) { - if (!items_[index].isMemberNameStatic()) - free(keys_[index]); - } else - break; - } -} - -ValueMapAllocator::~ValueMapAllocator() {} - -#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR -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; } -}; -#else -/// @todo make this thread-safe (lock when accessign batch allocator) -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); - } - -private: - BatchAllocator<ValueInternalMap, 1> mapsAllocator_; - BatchAllocator<ValueInternalLink, 1> linksAllocator_; -}; -#endif - -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; - -// h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32. - -/* -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=(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); - } - } - 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; - } - } - } -} - -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 |