src/blackberry10/native/public/json_internalmap.inl - cordova-plugin-globalization - 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

 /*
 Permission is hereby granted, free of charge, to any person obtaining
 a copy of this software and associated documentation files (the
 "Software"), to deal in the Software without restriction, including
 without limitation the rights to use, copy, modify, merge, publish,
 distribute, sublicense, and/or sell copies of the Software, and to
 permit persons to whom the Software is furnished to do so, subject to
 the following conditions:

 The above copyright notice and this permission notice shall be
 included in all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */


 // included by json_value.cpp
 // everything is within Json namespace

 // //////////////////////////////////////////////////////////////////
 // //////////////////////////////////////////////////////////////////
 // //////////////////////////////////////////////////////////////////
 // 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 =( 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 &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 = valueAllocator()->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;
 }
	// 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

	/*
	Permission is hereby granted, free of charge, to any person obtaining
	a copy of this software and associated documentation files (the
	"Software"), to deal in the Software without restriction, including
	without limitation the rights to use, copy, modify, merge, publish,
	distribute, sublicense, and/or sell copies of the Software, and to
	permit persons to whom the Software is furnished to do so, subject to
	the following conditions:

	The above copyright notice and this permission notice shall be
	included in all copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
	EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
	MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
	NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
	LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
	OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
	WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	*/


	// included by json_value.cpp
	// everything is within Json namespace

	// //////////////////////////////////////////////////////////////////
	// //////////////////////////////////////////////////////////////////
	// //////////////////////////////////////////////////////////////////
	// 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 =( 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 &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 = valueAllocator()->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;
	}