text: // 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;
  }
  