comparison third_party/json/json_internalmap.inl @ 0:add35537fdbb tip

Initial import

+// 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 =( 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 = 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