00001
00002
00003
00004
00005
00006
00007
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:
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:
00085 virtual ValueInternalMap *newMap()
00086 {
00087 ValueInternalMap *map = mapsAllocator_.allocate();
00088 new (map) ValueInternalMap();
00089 return map;
00090 }
00091
00092 virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
00093 {
00094 ValueInternalMap *map = mapsAllocator_.allocate();
00095 new (map) ValueInternalMap( other );
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();
00147 }
00148 } dummyMapAllocatorInitializer;
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
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
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 ¤t->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 = ¤t->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
00363
00364
00365 ValueInternalLink *&lastLink = getLastLinkInBucket( index );
00366 BucketIndex lastItemIndex = 1;
00367 for ( ;
00368 lastItemIndex < ValueInternalLink::itemPerLink;
00369 ++lastItemIndex )
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 )
00381 {
00382 ValueInternalLink *linkPreviousToLast = lastLink->previous_;
00383 if ( linkPreviousToLast != 0 )
00384 {
00385 mapAllocator()->releaseMapLink( lastLink );
00386 linkPreviousToLast->next_ = 0;
00387 lastLink = linkPreviousToLast;
00388 }
00389 }
00390 else
00391 {
00392 Value dummy;
00393 valueToPreserve->swap( dummy );
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];
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 )
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
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
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 }