Utilities/cmjsoncpp/src/lib_json/json_internalmap.inl - third_party/cmake - Git at Google

 // 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 &current->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 = &current->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
	// 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 &current->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 = &current->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