--- /dev/null
+// 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
+// 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 ¤t->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 = ¤t->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;
+}
projects / bamtools.git / blobdiff