JsonCpp project page JsonCpp home page

json_internalmap.inl

Go to the documentation of this file.
00001 // included by json_value.cpp
00002 // everything is within Json namespace
00003 
00004 // //////////////////////////////////////////////////////////////////
00005 // //////////////////////////////////////////////////////////////////
00006 // //////////////////////////////////////////////////////////////////
00007 // class ValueInternalMap
00008 // //////////////////////////////////////////////////////////////////
00009 // //////////////////////////////////////////////////////////////////
00010 // //////////////////////////////////////////////////////////////////
00011 
00015 ValueInternalLink::ValueInternalLink()
00016    : previous_( 0 )
00017    , next_( 0 )
00018 {
00019 }
00020 
00021 ValueInternalLink::~ValueInternalLink()
00022 { 
00023    for ( int index =0; index < itemPerLink; ++index )
00024    {
00025       if ( !items_[index].isItemAvailable() )
00026       {
00027          if ( !items_[index].isMemberNameStatic() )
00028             free( keys_[index] );
00029       }
00030       else
00031          break;
00032    }
00033 }
00034 
00035 
00036 
00037 ValueMapAllocator::~ValueMapAllocator()
00038 {
00039 }
00040 
00041 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
00042 class DefaultValueMapAllocator : public ValueMapAllocator
00043 {
00044 public: // overridden from ValueMapAllocator
00045    virtual ValueInternalMap *newMap()
00046    {
00047       return new ValueInternalMap();
00048    }
00049 
00050    virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
00051    {
00052       return new ValueInternalMap( other );
00053    }
00054 
00055    virtual void destructMap( ValueInternalMap *map )
00056    {
00057       delete map;
00058    }
00059 
00060    virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
00061    {
00062       return new ValueInternalLink[size];
00063    }
00064 
00065    virtual void releaseMapBuckets( ValueInternalLink *links )
00066    {
00067       delete [] links;
00068    }
00069 
00070    virtual ValueInternalLink *allocateMapLink()
00071    {
00072       return new ValueInternalLink();
00073    }
00074 
00075    virtual void releaseMapLink( ValueInternalLink *link )
00076    {
00077       delete link;
00078    }
00079 };
00080 #else
00081 
00082 class DefaultValueMapAllocator : public ValueMapAllocator
00083 {
00084 public: // overridden from ValueMapAllocator
00085    virtual ValueInternalMap *newMap()
00086    {
00087       ValueInternalMap *map = mapsAllocator_.allocate();
00088       new (map) ValueInternalMap(); // placement new
00089       return map;
00090    }
00091 
00092    virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
00093    {
00094       ValueInternalMap *map = mapsAllocator_.allocate();
00095       new (map) ValueInternalMap( other ); // placement new
00096       return map;
00097    }
00098 
00099    virtual void destructMap( ValueInternalMap *map )
00100    {
00101       if ( map )
00102       {
00103          map->~ValueInternalMap();
00104          mapsAllocator_.release( map );
00105       }
00106    }
00107 
00108    virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
00109    {
00110       return new ValueInternalLink[size];
00111    }
00112 
00113    virtual void releaseMapBuckets( ValueInternalLink *links )
00114    {
00115       delete [] links;
00116    }
00117 
00118    virtual ValueInternalLink *allocateMapLink()
00119    {
00120       ValueInternalLink *link = linksAllocator_.allocate();
00121       memset( link, 0, sizeof(ValueInternalLink) );
00122       return link;
00123    }
00124 
00125    virtual void releaseMapLink( ValueInternalLink *link )
00126    {
00127       link->~ValueInternalLink();
00128       linksAllocator_.release( link );
00129    }
00130 private:
00131    BatchAllocator<ValueInternalMap,1> mapsAllocator_;
00132    BatchAllocator<ValueInternalLink,1> linksAllocator_;
00133 };
00134 #endif
00135 
00136 static ValueMapAllocator *&mapAllocator()
00137 {
00138    static DefaultValueMapAllocator defaultAllocator;
00139    static ValueMapAllocator *mapAllocator = &defaultAllocator;
00140    return mapAllocator;
00141 }
00142 
00143 static struct DummyMapAllocatorInitializer {
00144    DummyMapAllocatorInitializer() 
00145    {
00146       mapAllocator();      // ensure mapAllocator() statics are initialized before main().
00147    }
00148 } dummyMapAllocatorInitializer;
00149 
00150 
00151 
00152 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
00153 
00154 /*
00155 use linked list hash map. 
00156 buckets array is a container.
00157 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
00158 value have extra state: valid, available, deleted
00159 */
00160 
00161 
00162 ValueInternalMap::ValueInternalMap()
00163    : buckets_( 0 )
00164    , tailLink_( 0 )
00165    , bucketsSize_( 0 )
00166    , itemCount_( 0 )
00167 {
00168 }
00169 
00170 
00171 ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
00172    : buckets_( 0 )
00173    , tailLink_( 0 )
00174    , bucketsSize_( 0 )
00175    , itemCount_( 0 )
00176 {
00177    reserve( other.itemCount_ );
00178    IteratorState it;
00179    IteratorState itEnd;
00180    other.makeBeginIterator( it );
00181    other.makeEndIterator( itEnd );
00182    for ( ; !equals(it,itEnd); increment(it) )
00183    {
00184       bool isStatic;
00185       const char *memberName = key( it, isStatic );
00186       const Value &aValue = value( it );
00187       resolveReference(memberName, isStatic) = aValue;
00188    }
00189 }
00190 
00191 
00192 ValueInternalMap &
00193 ValueInternalMap::operator =( const ValueInternalMap &other )
00194 {
00195    ValueInternalMap dummy( other );
00196    swap( dummy );
00197    return *this;
00198 }
00199 
00200 
00201 ValueInternalMap::~ValueInternalMap()
00202 {
00203    if ( buckets_ )
00204    {
00205       for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
00206       {
00207          ValueInternalLink *link = buckets_[bucketIndex].next_;
00208          while ( link )
00209          {
00210             ValueInternalLink *linkToRelease = link;
00211             link = link->next_;
00212             mapAllocator()->releaseMapLink( linkToRelease );
00213          }
00214       }
00215       mapAllocator()->releaseMapBuckets( buckets_ );
00216    }
00217 }
00218 
00219 
00220 void 
00221 ValueInternalMap::swap( ValueInternalMap &other )
00222 {
00223    ValueInternalLink *tempBuckets = buckets_;
00224    buckets_ = other.buckets_;
00225    other.buckets_ = tempBuckets;
00226    ValueInternalLink *tempTailLink = tailLink_;
00227    tailLink_ = other.tailLink_;
00228    other.tailLink_ = tempTailLink;
00229    BucketIndex tempBucketsSize = bucketsSize_;
00230    bucketsSize_ = other.bucketsSize_;
00231    other.bucketsSize_ = tempBucketsSize;
00232    BucketIndex tempItemCount = itemCount_;
00233    itemCount_ = other.itemCount_;
00234    other.itemCount_ = tempItemCount;
00235 }
00236 
00237 
00238 void 
00239 ValueInternalMap::clear()
00240 {
00241    ValueInternalMap dummy;
00242    swap( dummy );
00243 }
00244 
00245 
00246 ValueInternalMap::BucketIndex 
00247 ValueInternalMap::size() const
00248 {
00249    return itemCount_;
00250 }
00251 
00252 bool 
00253 ValueInternalMap::reserveDelta( BucketIndex growth )
00254 {
00255    return reserve( itemCount_ + growth );
00256 }
00257 
00258 bool 
00259 ValueInternalMap::reserve( BucketIndex newItemCount )
00260 {
00261    if ( !buckets_  &&  newItemCount > 0 )
00262    {
00263       buckets_ = mapAllocator()->allocateMapBuckets( 1 );
00264       bucketsSize_ = 1;
00265       tailLink_ = &buckets_[0];
00266    }
00267 //   BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
00268    return true;
00269 }
00270 
00271 
00272 const Value *
00273 ValueInternalMap::find( const char *key ) const
00274 {
00275    if ( !bucketsSize_ )
00276       return 0;
00277    HashKey hashedKey = hash( key );
00278    BucketIndex bucketIndex = hashedKey % bucketsSize_;
00279    for ( const ValueInternalLink *current = &buckets_[bucketIndex]; 
00280          current != 0; 
00281          current = current->next_ )
00282    {
00283       for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
00284       {
00285          if ( current->items_[index].isItemAvailable() )
00286             return 0;
00287          if ( strcmp( key, current->keys_[index] ) == 0 )
00288             return &current->items_[index];
00289       }
00290    }
00291    return 0;
00292 }
00293 
00294 
00295 Value *
00296 ValueInternalMap::find( const char *key )
00297 {
00298    const ValueInternalMap *constThis = this;
00299    return const_cast<Value *>( constThis->find( key ) );
00300 }
00301 
00302 
00303 Value &
00304 ValueInternalMap::resolveReference( const char *key,
00305                                     bool isStatic )
00306 {
00307    HashKey hashedKey = hash( key );
00308    if ( bucketsSize_ )
00309    {
00310       BucketIndex bucketIndex = hashedKey % bucketsSize_;
00311       ValueInternalLink **previous = 0;
00312       BucketIndex index;
00313       for ( ValueInternalLink *current = &buckets_[bucketIndex]; 
00314             current != 0; 
00315             previous = &current->next_, current = current->next_ )
00316       {
00317          for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
00318          {
00319             if ( current->items_[index].isItemAvailable() )
00320                return setNewItem( key, isStatic, current, index );
00321             if ( strcmp( key, current->keys_[index] ) == 0 )
00322                return current->items_[index];
00323          }
00324       }
00325    }
00326 
00327    reserveDelta( 1 );
00328    return unsafeAdd( key, isStatic, hashedKey );
00329 }
00330 
00331 
00332 void 
00333 ValueInternalMap::remove( const char *key )
00334 {
00335    HashKey hashedKey = hash( key );
00336    if ( !bucketsSize_ )
00337       return;
00338    BucketIndex bucketIndex = hashedKey % bucketsSize_;
00339    for ( ValueInternalLink *link = &buckets_[bucketIndex]; 
00340          link != 0; 
00341          link = link->next_ )
00342    {
00343       BucketIndex index;
00344       for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
00345       {
00346          if ( link->items_[index].isItemAvailable() )
00347             return;
00348          if ( strcmp( key, link->keys_[index] ) == 0 )
00349          {
00350             doActualRemove( link, index, bucketIndex );
00351             return;
00352          }
00353       }
00354    }
00355 }
00356 
00357 void 
00358 ValueInternalMap::doActualRemove( ValueInternalLink *link, 
00359                                   BucketIndex index,
00360                                   BucketIndex bucketIndex )
00361 {
00362    // find last item of the bucket and swap it with the 'removed' one.
00363    // set removed items flags to 'available'.
00364    // if last page only contains 'available' items, then desallocate it (it's empty)
00365    ValueInternalLink *&lastLink = getLastLinkInBucket( index );
00366    BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
00367    for ( ;   
00368          lastItemIndex < ValueInternalLink::itemPerLink; 
00369          ++lastItemIndex ) // may be optimized with dicotomic search
00370    {
00371       if ( lastLink->items_[lastItemIndex].isItemAvailable() )
00372          break;
00373    }
00374    
00375    BucketIndex lastUsedIndex = lastItemIndex - 1;
00376    Value *valueToDelete = &link->items_[index];
00377    Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
00378    if ( valueToDelete != valueToPreserve )
00379       valueToDelete->swap( *valueToPreserve );
00380    if ( lastUsedIndex == 0 )  // page is now empty
00381    {  // remove it from bucket linked list and delete it.
00382       ValueInternalLink *linkPreviousToLast = lastLink->previous_;
00383       if ( linkPreviousToLast != 0 )   // can not deleted bucket link.
00384       {
00385          mapAllocator()->releaseMapLink( lastLink );
00386          linkPreviousToLast->next_ = 0;
00387          lastLink = linkPreviousToLast;
00388       }
00389    }
00390    else
00391    {
00392       Value dummy;
00393       valueToPreserve->swap( dummy ); // restore deleted to default Value.
00394       valueToPreserve->setItemUsed( false );
00395    }
00396    --itemCount_;
00397 }
00398 
00399 
00400 ValueInternalLink *&
00401 ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
00402 {
00403    if ( bucketIndex == bucketsSize_ - 1 )
00404       return tailLink_;
00405    ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
00406    if ( !previous )
00407       previous = &buckets_[bucketIndex];
00408    return previous;
00409 }
00410 
00411 
00412 Value &
00413 ValueInternalMap::setNewItem( const char *key, 
00414                               bool isStatic,
00415                               ValueInternalLink *link, 
00416                               BucketIndex index )
00417 {
00418    char *duplicatedKey = valueAllocator()->makeMemberName( key );
00419    ++itemCount_;
00420    link->keys_[index] = duplicatedKey;
00421    link->items_[index].setItemUsed();
00422    link->items_[index].setMemberNameIsStatic( isStatic );
00423    return link->items_[index]; // items already default constructed.
00424 }
00425 
00426 
00427 Value &
00428 ValueInternalMap::unsafeAdd( const char *key, 
00429                              bool isStatic, 
00430                              HashKey hashedKey )
00431 {
00432    JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
00433    BucketIndex bucketIndex = hashedKey % bucketsSize_;
00434    ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
00435    ValueInternalLink *link = previousLink;
00436    BucketIndex index;
00437    for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
00438    {
00439       if ( link->items_[index].isItemAvailable() )
00440          break;
00441    }
00442    if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
00443    {
00444       ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
00445       index = 0;
00446       link->next_ = newLink;
00447       previousLink = newLink;
00448       link = newLink;
00449    }
00450    return setNewItem( key, isStatic, link, index );
00451 }
00452 
00453 
00454 ValueInternalMap::HashKey 
00455 ValueInternalMap::hash( const char *key ) const
00456 {
00457    HashKey hash = 0;
00458    while ( *key )
00459       hash += *key++ * 37;
00460    return hash;
00461 }
00462 
00463 
00464 int 
00465 ValueInternalMap::compare( const ValueInternalMap &other ) const
00466 {
00467    int sizeDiff( itemCount_ - other.itemCount_ );
00468    if ( sizeDiff != 0 )
00469       return sizeDiff;
00470    // Strict order guaranty is required. Compare all keys FIRST, then compare values.
00471    IteratorState it;
00472    IteratorState itEnd;
00473    makeBeginIterator( it );
00474    makeEndIterator( itEnd );
00475    for ( ; !equals(it,itEnd); increment(it) )
00476    {
00477       if ( !other.find( key( it ) ) )
00478          return 1;
00479    }
00480 
00481    // All keys are equals, let's compare values
00482    makeBeginIterator( it );
00483    for ( ; !equals(it,itEnd); increment(it) )
00484    {
00485       const Value *otherValue = other.find( key( it ) );
00486       int valueDiff = value(it).compare( *otherValue );
00487       if ( valueDiff != 0 )
00488          return valueDiff;
00489    }
00490    return 0;
00491 }
00492 
00493 
00494 void 
00495 ValueInternalMap::makeBeginIterator( IteratorState &it ) const
00496 {
00497    it.map_ = const_cast<ValueInternalMap *>( this );
00498    it.bucketIndex_ = 0;
00499    it.itemIndex_ = 0;
00500    it.link_ = buckets_;
00501 }
00502 
00503 
00504 void 
00505 ValueInternalMap::makeEndIterator( IteratorState &it ) const
00506 {
00507    it.map_ = const_cast<ValueInternalMap *>( this );
00508    it.bucketIndex_ = bucketsSize_;
00509    it.itemIndex_ = 0;
00510    it.link_ = 0;
00511 }
00512 
00513 
00514 bool 
00515 ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
00516 {
00517    return x.map_ == other.map_  
00518           &&  x.bucketIndex_ == other.bucketIndex_  
00519           &&  x.link_ == other.link_
00520           &&  x.itemIndex_ == other.itemIndex_;
00521 }
00522 
00523 
00524 void 
00525 ValueInternalMap::incrementBucket( IteratorState &iterator )
00526 {
00527    ++iterator.bucketIndex_;
00528    JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
00529       "ValueInternalMap::increment(): attempting to iterate beyond end." );
00530    if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
00531       iterator.link_ = 0;
00532    else
00533       iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
00534    iterator.itemIndex_ = 0;
00535 }
00536 
00537 
00538 void 
00539 ValueInternalMap::increment( IteratorState &iterator )
00540 {
00541    JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
00542    ++iterator.itemIndex_;
00543    if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
00544    {
00545       JSON_ASSERT_MESSAGE( iterator.link_ != 0,
00546          "ValueInternalMap::increment(): attempting to iterate beyond end." );
00547       iterator.link_ = iterator.link_->next_;
00548       if ( iterator.link_ == 0 )
00549          incrementBucket( iterator );
00550    }
00551    else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
00552    {
00553       incrementBucket( iterator );
00554    }
00555 }
00556 
00557 
00558 void 
00559 ValueInternalMap::decrement( IteratorState &iterator )
00560 {
00561    if ( iterator.itemIndex_ == 0 )
00562    {
00563       JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
00564       if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
00565       {
00566          JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
00567          --(iterator.bucketIndex_);
00568       }
00569       iterator.link_ = iterator.link_->previous_;
00570       iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
00571    }
00572 }
00573 
00574 
00575 const char *
00576 ValueInternalMap::key( const IteratorState &iterator )
00577 {
00578    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
00579    return iterator.link_->keys_[iterator.itemIndex_];
00580 }
00581 
00582 const char *
00583 ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
00584 {
00585    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
00586    isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
00587    return iterator.link_->keys_[iterator.itemIndex_];
00588 }
00589 
00590 
00591 Value &
00592 ValueInternalMap::value( const IteratorState &iterator )
00593 {
00594    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
00595    return iterator.link_->items_[iterator.itemIndex_];
00596 }
00597 
00598 
00599 int 
00600 ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
00601 {
00602    int offset = 0;
00603    IteratorState it = x;
00604    while ( !equals( it, y ) )
00605       increment( it );
00606    return offset;
00607 }

SourceForge Logo hosts this site. Send comments to:
Json-cpp Developers