src/third_party/jsoncpp/json_internalmap.inl

   1 // Copyright 2007-2010 Baptiste Lepilleur
   2 // Distributed under MIT license, or public domain if desired and
   3 // recognized in your jurisdiction.
   4 // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE
   5
   6 // included by json_value.cpp
   7 // everything is within Json namespace
   8
   9 // //////////////////////////////////////////////////////////////////
  10 // //////////////////////////////////////////////////////////////////
  11 // //////////////////////////////////////////////////////////////////
  12 // class ValueInternalMap
  13 // //////////////////////////////////////////////////////////////////
  14 // //////////////////////////////////////////////////////////////////
  15 // //////////////////////////////////////////////////////////////////
  16
  17 /** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
  18    * This optimization is used by the fast allocator.
  19    */
  20 ValueInternalLink::ValueInternalLink()
  21    : previous_( 0 )
  22    , next_( 0 )
  23 {
  24 }
  25
  26 ValueInternalLink::~ValueInternalLink()
  27 {
  28    for ( int index =0; index < itemPerLink; ++index )
  29    {
  30       if ( !items_[index].isItemAvailable() )
  31       {
  32          if ( !items_[index].isMemberNameStatic() )
  33             free( keys_[index] );
  34       }
  35       else
  36          break;
  37    }
  38 }
  39
  40
  41
  42 ValueMapAllocator::~ValueMapAllocator()
  43 {
  44 }
  45
  46 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
  47 class DefaultValueMapAllocator : public ValueMapAllocator
  48 {
  49 public: // overridden from ValueMapAllocator
  50    virtual ValueInternalMap *newMap()
  51    {
  52       return new ValueInternalMap();
  53    }
  54
  55    virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
  56    {
  57       return new ValueInternalMap( other );
  58    }
  59
  60    virtual void destructMap( ValueInternalMap *map )
  61    {
  62       delete map;
  63    }
  64
  65    virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
  66    {
  67       return new ValueInternalLink[size];
  68    }
  69
  70    virtual void releaseMapBuckets( ValueInternalLink *links )
  71    {
  72       delete [] links;
  73    }
  74
  75    virtual ValueInternalLink *allocateMapLink()
  76    {
  77       return new ValueInternalLink();
  78    }
  79
  80    virtual void releaseMapLink( ValueInternalLink *link )
  81    {
  82       delete link;
  83    }
  84 };
  85 #else
  86 /// @todo make this thread-safe (lock when accessign batch allocator)
  87 class DefaultValueMapAllocator : public ValueMapAllocator
  88 {
  89 public: // overridden from ValueMapAllocator
  90    virtual ValueInternalMap *newMap()
  91    {
  92       ValueInternalMap *map = mapsAllocator_.allocate();
  93       new (map) ValueInternalMap(); // placement new
  94       return map;
  95    }
  96
  97    virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
  98    {
  99       ValueInternalMap *map = mapsAllocator_.allocate();
 100       new (map) ValueInternalMap( other ); // placement new
 101       return map;
 102    }
 103
 104    virtual void destructMap( ValueInternalMap *map )
 105    {
 106       if ( map )
 107       {
 108          map->~ValueInternalMap();
 109          mapsAllocator_.release( map );
 110       }
 111    }
 112
 113    virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
 114    {
 115       return new ValueInternalLink[size];
 116    }
 117
 118    virtual void releaseMapBuckets( ValueInternalLink *links )
 119    {
 120       delete [] links;
 121    }
 122
 123    virtual ValueInternalLink *allocateMapLink()
 124    {
 125       ValueInternalLink *link = linksAllocator_.allocate();
 126       memset( link, 0, sizeof(ValueInternalLink) );
 127       return link;
 128    }
 129
 130    virtual void releaseMapLink( ValueInternalLink *link )
 131    {
 132       link->~ValueInternalLink();
 133       linksAllocator_.release( link );
 134    }
 135 private:
 136    BatchAllocator<ValueInternalMap,1> mapsAllocator_;
 137    BatchAllocator<ValueInternalLink,1> linksAllocator_;
 138 };
 139 #endif
 140
 141 static ValueMapAllocator *&mapAllocator()
 142 {
 143    static DefaultValueMapAllocator defaultAllocator;
 144    static ValueMapAllocator *mapAllocator = &defaultAllocator;
 145    return mapAllocator;
 146 }
 147
 148 static struct DummyMapAllocatorInitializer {
 149    DummyMapAllocatorInitializer()
 150    {
 151       mapAllocator();      // ensure mapAllocator() statics are initialized before main().
 152    }
 153 } dummyMapAllocatorInitializer;
 154
 155
 156
 157 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
 158
 159 /*
 160 use linked list hash map.
 161 buckets array is a container.
 162 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
 163 value have extra state: valid, available, deleted
 164 */
 165
 166
 167 ValueInternalMap::ValueInternalMap()
 168    : buckets_( 0 )
 169    , tailLink_( 0 )
 170    , bucketsSize_( 0 )
 171    , itemCount_( 0 )
 172 {
 173 }
 174
 175
 176 ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
 177    : buckets_( 0 )
 178    , tailLink_( 0 )
 179    , bucketsSize_( 0 )
 180    , itemCount_( 0 )
 181 {
 182    reserve( other.itemCount_ );
 183    IteratorState it;
 184    IteratorState itEnd;
 185    other.makeBeginIterator( it );
 186    other.makeEndIterator( itEnd );
 187    for ( ; !equals(it,itEnd); increment(it) )
 188    {
 189       bool isStatic;
 190       const char *memberName = key( it, isStatic );
 191       const Value &aValue = value( it );
 192       resolveReference(memberName, isStatic) = aValue;
 193    }
 194 }
 195
 196
 197 ValueInternalMap &
 198 ValueInternalMap::operator =( const ValueInternalMap &other )
 199 {
 200    ValueInternalMap dummy( other );
 201    swap( dummy );
 202    return *this;
 203 }
 204
 205
 206 ValueInternalMap::~ValueInternalMap()
 207 {
 208    if ( buckets_ )
 209    {
 210       for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
 211       {
 212          ValueInternalLink *link = buckets_[bucketIndex].next_;
 213          while ( link )
 214          {
 215             ValueInternalLink *linkToRelease = link;
 216             link = link->next_;
 217             mapAllocator()->releaseMapLink( linkToRelease );
 218          }
 219       }
 220       mapAllocator()->releaseMapBuckets( buckets_ );
 221    }
 222 }
 223
 224
 225 void
 226 ValueInternalMap::swap( ValueInternalMap &other )
 227 {
 228    ValueInternalLink *tempBuckets = buckets_;
 229    buckets_ = other.buckets_;
 230    other.buckets_ = tempBuckets;
 231    ValueInternalLink *tempTailLink = tailLink_;
 232    tailLink_ = other.tailLink_;
 233    other.tailLink_ = tempTailLink;
 234    BucketIndex tempBucketsSize = bucketsSize_;
 235    bucketsSize_ = other.bucketsSize_;
 236    other.bucketsSize_ = tempBucketsSize;
 237    BucketIndex tempItemCount = itemCount_;
 238    itemCount_ = other.itemCount_;
 239    other.itemCount_ = tempItemCount;
 240 }
 241
 242
 243 void
 244 ValueInternalMap::clear()
 245 {
 246    ValueInternalMap dummy;
 247    swap( dummy );
 248 }
 249
 250
 251 ValueInternalMap::BucketIndex
 252 ValueInternalMap::size() const
 253 {
 254    return itemCount_;
 255 }
 256
 257 bool
 258 ValueInternalMap::reserveDelta( BucketIndex growth )
 259 {
 260    return reserve( itemCount_ + growth );
 261 }
 262
 263 bool
 264 ValueInternalMap::reserve( BucketIndex newItemCount )
 265 {
 266    if ( !buckets_  &&  newItemCount > 0 )
 267    {
 268       buckets_ = mapAllocator()->allocateMapBuckets( 1 );
 269       bucketsSize_ = 1;
 270       tailLink_ = &buckets_[0];
 271    }
 272 //   BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
 273    return true;
 274 }
 275
 276
 277 const Value *
 278 ValueInternalMap::find( const char *key ) const
 279 {
 280    if ( !bucketsSize_ )
 281       return 0;
 282    HashKey hashedKey = hash( key );
 283    BucketIndex bucketIndex = hashedKey % bucketsSize_;
 284    for ( const ValueInternalLink *current = &buckets_[bucketIndex];
 285          current != 0;
 286          current = current->next_ )
 287    {
 288       for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
 289       {
 290          if ( current->items_[index].isItemAvailable() )
 291             return 0;
 292          if ( strcmp( key, current->keys_[index] ) == 0 )
 293             return &current->items_[index];
 294       }
 295    }
 296    return 0;
 297 }
 298
 299
 300 Value *
 301 ValueInternalMap::find( const char *key )
 302 {
 303    const ValueInternalMap *constThis = this;
 304    return const_cast<Value *>( constThis->find( key ) );
 305 }
 306
 307
 308 Value &
 309 ValueInternalMap::resolveReference( const char *key,
 310                                     bool isStatic )
 311 {
 312    HashKey hashedKey = hash( key );
 313    if ( bucketsSize_ )
 314    {
 315       BucketIndex bucketIndex = hashedKey % bucketsSize_;
 316       ValueInternalLink **previous = 0;
 317       BucketIndex index;
 318       for ( ValueInternalLink *current = &buckets_[bucketIndex];
 319             current != 0;
 320             previous = &current->next_, current = current->next_ )
 321       {
 322          for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
 323          {
 324             if ( current->items_[index].isItemAvailable() )
 325                return setNewItem( key, isStatic, current, index );
 326             if ( strcmp( key, current->keys_[index] ) == 0 )
 327                return current->items_[index];
 328          }
 329       }
 330    }
 331
 332    reserveDelta( 1 );
 333    return unsafeAdd( key, isStatic, hashedKey );
 334 }
 335
 336
 337 void
 338 ValueInternalMap::remove( const char *key )
 339 {
 340    HashKey hashedKey = hash( key );
 341    if ( !bucketsSize_ )
 342       return;
 343    BucketIndex bucketIndex = hashedKey % bucketsSize_;
 344    for ( ValueInternalLink *link = &buckets_[bucketIndex];
 345          link != 0;
 346          link = link->next_ )
 347    {
 348       BucketIndex index;
 349       for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
 350       {
 351          if ( link->items_[index].isItemAvailable() )
 352             return;
 353          if ( strcmp( key, link->keys_[index] ) == 0 )
 354          {
 355             doActualRemove( link, index, bucketIndex );
 356             return;
 357          }
 358       }
 359    }
 360 }
 361
 362 void
 363 ValueInternalMap::doActualRemove( ValueInternalLink *link,
 364                                   BucketIndex index,
 365                                   BucketIndex bucketIndex )
 366 {
 367    // find last item of the bucket and swap it with the 'removed' one.
 368    // set removed items flags to 'available'.
 369    // if last page only contains 'available' items, then desallocate it (it's empty)
 370    ValueInternalLink *&lastLink = getLastLinkInBucket( index );
 371    BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
 372    for ( ;
 373          lastItemIndex < ValueInternalLink::itemPerLink;
 374          ++lastItemIndex ) // may be optimized with dicotomic search
 375    {
 376       if ( lastLink->items_[lastItemIndex].isItemAvailable() )
 377          break;
 378    }
 379
 380    BucketIndex lastUsedIndex = lastItemIndex - 1;
 381    Value *valueToDelete = &link->items_[index];
 382    Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
 383    if ( valueToDelete != valueToPreserve )
 384       valueToDelete->swap( *valueToPreserve );
 385    if ( lastUsedIndex == 0 )  // page is now empty
 386    {  // remove it from bucket linked list and delete it.
 387       ValueInternalLink *linkPreviousToLast = lastLink->previous_;
 388       if ( linkPreviousToLast != 0 )   // can not deleted bucket link.
 389       {
 390          mapAllocator()->releaseMapLink( lastLink );
 391          linkPreviousToLast->next_ = 0;
 392          lastLink = linkPreviousToLast;
 393       }
 394    }
 395    else
 396    {
 397       Value dummy;
 398       valueToPreserve->swap( dummy ); // restore deleted to default Value.
 399       valueToPreserve->setItemUsed( false );
 400    }
 401    --itemCount_;
 402 }
 403
 404
 405 ValueInternalLink *&
 406 ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
 407 {
 408    if ( bucketIndex == bucketsSize_ - 1 )
 409       return tailLink_;
 410    ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
 411    if ( !previous )
 412       previous = &buckets_[bucketIndex];
 413    return previous;
 414 }
 415
 416
 417 Value &
 418 ValueInternalMap::setNewItem( const char *key,
 419                               bool isStatic,
 420                               ValueInternalLink *link,
 421                               BucketIndex index )
 422 {
 423    char *duplicatedKey = makeMemberName( key );
 424    ++itemCount_;
 425    link->keys_[index] = duplicatedKey;
 426    link->items_[index].setItemUsed();
 427    link->items_[index].setMemberNameIsStatic( isStatic );
 428    return link->items_[index]; // items already default constructed.
 429 }
 430
 431
 432 Value &
 433 ValueInternalMap::unsafeAdd( const char *key,
 434                              bool isStatic,
 435                              HashKey hashedKey )
 436 {
 437    JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
 438    BucketIndex bucketIndex = hashedKey % bucketsSize_;
 439    ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
 440    ValueInternalLink *link = previousLink;
 441    BucketIndex index;
 442    for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
 443    {
 444       if ( link->items_[index].isItemAvailable() )
 445          break;
 446    }
 447    if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
 448    {
 449       ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
 450       index = 0;
 451       link->next_ = newLink;
 452       previousLink = newLink;
 453       link = newLink;
 454    }
 455    return setNewItem( key, isStatic, link, index );
 456 }
 457
 458
 459 ValueInternalMap::HashKey
 460 ValueInternalMap::hash( const char *key ) const
 461 {
 462    HashKey hash = 0;
 463    while ( *key )
 464       hash += *key++ * 37;
 465    return hash;
 466 }
 467
 468
 469 int
 470 ValueInternalMap::compare( const ValueInternalMap &other ) const
 471 {
 472    int sizeDiff( itemCount_ - other.itemCount_ );
 473    if ( sizeDiff != 0 )
 474       return sizeDiff;
 475    // Strict order guaranty is required. Compare all keys FIRST, then compare values.
 476    IteratorState it;
 477    IteratorState itEnd;
 478    makeBeginIterator( it );
 479    makeEndIterator( itEnd );
 480    for ( ; !equals(it,itEnd); increment(it) )
 481    {
 482       if ( !other.find( key( it ) ) )
 483          return 1;
 484    }
 485
 486    // All keys are equals, let's compare values
 487    makeBeginIterator( it );
 488    for ( ; !equals(it,itEnd); increment(it) )
 489    {
 490       const Value *otherValue = other.find( key( it ) );
 491       int valueDiff = value(it).compare( *otherValue );
 492       if ( valueDiff != 0 )
 493          return valueDiff;
 494    }
 495    return 0;
 496 }
 497
 498
 499 void
 500 ValueInternalMap::makeBeginIterator( IteratorState &it ) const
 501 {
 502    it.map_ = const_cast<ValueInternalMap *>( this );
 503    it.bucketIndex_ = 0;
 504    it.itemIndex_ = 0;
 505    it.link_ = buckets_;
 506 }
 507
 508
 509 void
 510 ValueInternalMap::makeEndIterator( IteratorState &it ) const
 511 {
 512    it.map_ = const_cast<ValueInternalMap *>( this );
 513    it.bucketIndex_ = bucketsSize_;
 514    it.itemIndex_ = 0;
 515    it.link_ = 0;
 516 }
 517
 518
 519 bool
 520 ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
 521 {
 522    return x.map_ == other.map_
 523           &&  x.bucketIndex_ == other.bucketIndex_
 524           &&  x.link_ == other.link_
 525           &&  x.itemIndex_ == other.itemIndex_;
 526 }
 527
 528
 529 void
 530 ValueInternalMap::incrementBucket( IteratorState &iterator )
 531 {
 532    ++iterator.bucketIndex_;
 533    JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
 534       "ValueInternalMap::increment(): attempting to iterate beyond end." );
 535    if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
 536       iterator.link_ = 0;
 537    else
 538       iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
 539    iterator.itemIndex_ = 0;
 540 }
 541
 542
 543 void
 544 ValueInternalMap::increment( IteratorState &iterator )
 545 {
 546    JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
 547    ++iterator.itemIndex_;
 548    if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
 549    {
 550       JSON_ASSERT_MESSAGE( iterator.link_ != 0,
 551          "ValueInternalMap::increment(): attempting to iterate beyond end." );
 552       iterator.link_ = iterator.link_->next_;
 553       if ( iterator.link_ == 0 )
 554          incrementBucket( iterator );
 555    }
 556    else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
 557    {
 558       incrementBucket( iterator );
 559    }
 560 }
 561
 562
 563 void
 564 ValueInternalMap::decrement( IteratorState &iterator )
 565 {
 566    if ( iterator.itemIndex_ == 0 )
 567    {
 568       JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
 569       if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
 570       {
 571          JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
 572          --(iterator.bucketIndex_);
 573       }
 574       iterator.link_ = iterator.link_->previous_;
 575       iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
 576    }
 577 }
 578
 579
 580 const char *
 581 ValueInternalMap::key( const IteratorState &iterator )
 582 {
 583    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
 584    return iterator.link_->keys_[iterator.itemIndex_];
 585 }
 586
 587 const char *
 588 ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
 589 {
 590    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
 591    isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
 592    return iterator.link_->keys_[iterator.itemIndex_];
 593 }
 594
 595
 596 Value &
 597 ValueInternalMap::value( const IteratorState &iterator )
 598 {
 599    JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
 600    return iterator.link_->items_[iterator.itemIndex_];
 601 }
 602
 603
 604 int
 605 ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
 606 {
 607    int offset = 0;
 608    IteratorState it = x;
 609    while ( !equals( it, y ) )
 610       increment( it );
 611    return offset;
 612 }