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