diff options
Diffstat (limited to 'Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl')
| -rw-r--r-- | Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl | 473 |
1 files changed, 473 insertions, 0 deletions
diff --git a/Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl b/Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl new file mode 100644 index 0000000..ef3f330 --- /dev/null +++ b/Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl @@ -0,0 +1,473 @@ +// 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 |