53 ValueInternalLink::ValueInternalLink()
59 ValueInternalLink::~ValueInternalLink()
61 for (
int index =0; index < itemPerLink; ++index )
63 if ( !items_[index].isItemAvailable() )
65 if ( !items_[index].isMemberNameStatic() )
75 ValueMapAllocator::~ValueMapAllocator()
79 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
83 virtual ValueInternalMap *newMap()
85 return new ValueInternalMap();
88 virtual ValueInternalMap *newMapCopy(
const ValueInternalMap &other )
90 return new ValueInternalMap( other );
93 virtual void destructMap( ValueInternalMap *map )
98 virtual ValueInternalLink *allocateMapBuckets(
unsigned int size )
100 return new ValueInternalLink[size];
103 virtual void releaseMapBuckets( ValueInternalLink *links )
108 virtual ValueInternalLink *allocateMapLink()
110 return new ValueInternalLink();
113 virtual void releaseMapLink( ValueInternalLink *link )
123 virtual ValueInternalMap *newMap()
125 ValueInternalMap *map = mapsAllocator_.allocate();
126 new (map) ValueInternalMap();
130 virtual ValueInternalMap *newMapCopy(
const ValueInternalMap &other )
132 ValueInternalMap *map = mapsAllocator_.allocate();
133 new (map) ValueInternalMap( other );
137 virtual void destructMap( ValueInternalMap *map )
141 map->~ValueInternalMap();
142 mapsAllocator_.release( map );
146 virtual ValueInternalLink *allocateMapBuckets(
unsigned int size )
148 return new ValueInternalLink[size];
151 virtual void releaseMapBuckets( ValueInternalLink *links )
156 virtual ValueInternalLink *allocateMapLink()
158 ValueInternalLink *link = linksAllocator_.allocate();
159 memset( link, 0,
sizeof(ValueInternalLink) );
163 virtual void releaseMapLink( ValueInternalLink *link )
165 link->~ValueInternalLink();
166 linksAllocator_.release( link );
169 BatchAllocator<ValueInternalMap,1> mapsAllocator_;
170 BatchAllocator<ValueInternalLink,1> linksAllocator_;
174 static ValueMapAllocator *&mapAllocator()
177 static ValueMapAllocator *mapAllocator = &defaultAllocator;
186 } dummyMapAllocatorInitializer;
200 ValueInternalMap::ValueInternalMap()
209 ValueInternalMap::ValueInternalMap(
const ValueInternalMap &other )
215 reserve( other.itemCount_ );
218 other.makeBeginIterator( it );
219 other.makeEndIterator( itEnd );
220 for ( ; !equals(it,itEnd); increment(it) )
223 const char *memberName = key( it, isStatic );
224 const Value &aValue = value( it );
225 resolveReference(memberName, isStatic) = aValue;
231 ValueInternalMap::operator =(
const ValueInternalMap &other )
233 ValueInternalMap dummy( other );
239 ValueInternalMap::~ValueInternalMap()
243 for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
245 ValueInternalLink *link = buckets_[bucketIndex].next_;
248 ValueInternalLink *linkToRelease = link;
250 mapAllocator()->releaseMapLink( linkToRelease );
253 mapAllocator()->releaseMapBuckets( buckets_ );
259 ValueInternalMap::swap( ValueInternalMap &other )
261 ValueInternalLink *tempBuckets = buckets_;
262 buckets_ = other.buckets_;
263 other.buckets_ = tempBuckets;
264 ValueInternalLink *tempTailLink = tailLink_;
265 tailLink_ = other.tailLink_;
266 other.tailLink_ = tempTailLink;
267 BucketIndex tempBucketsSize = bucketsSize_;
268 bucketsSize_ = other.bucketsSize_;
269 other.bucketsSize_ = tempBucketsSize;
270 BucketIndex tempItemCount = itemCount_;
271 itemCount_ = other.itemCount_;
272 other.itemCount_ = tempItemCount;
277 ValueInternalMap::clear()
279 ValueInternalMap dummy;
284 ValueInternalMap::BucketIndex
285 ValueInternalMap::size()
const
291 ValueInternalMap::reserveDelta( BucketIndex growth )
293 return reserve( itemCount_ + growth );
297 ValueInternalMap::reserve( BucketIndex newItemCount )
299 if ( !buckets_ && newItemCount > 0 )
301 buckets_ = mapAllocator()->allocateMapBuckets( 1 );
303 tailLink_ = &buckets_[0];
311 ValueInternalMap::find(
const char *key )
const
315 HashKey hashedKey = hash( key );
316 BucketIndex bucketIndex = hashedKey % bucketsSize_;
317 for (
const ValueInternalLink *current = &buckets_[bucketIndex];
319 current = current->next_ )
321 for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
323 if ( current->items_[index].isItemAvailable() )
325 if ( strcmp( key, current->keys_[index] ) == 0 )
326 return ¤t->items_[index];
334 ValueInternalMap::find(
const char *key )
336 const ValueInternalMap *constThis =
this;
337 return const_cast<Value *
>( constThis->find( key ) );
342 ValueInternalMap::resolveReference(
const char *key,
345 HashKey hashedKey = hash( key );
348 BucketIndex bucketIndex = hashedKey % bucketsSize_;
349 ValueInternalLink **previous = 0;
351 for ( ValueInternalLink *current = &buckets_[bucketIndex];
353 previous = ¤t->next_, current = current->next_ )
355 for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
357 if ( current->items_[index].isItemAvailable() )
358 return setNewItem( key, isStatic, current, index );
359 if ( strcmp( key, current->keys_[index] ) == 0 )
360 return current->items_[index];
366 return unsafeAdd( key, isStatic, hashedKey );
371 ValueInternalMap::remove(
const char *key )
373 HashKey hashedKey = hash( key );
376 BucketIndex bucketIndex = hashedKey % bucketsSize_;
377 for ( ValueInternalLink *link = &buckets_[bucketIndex];
382 for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
384 if ( link->items_[index].isItemAvailable() )
386 if ( strcmp( key, link->keys_[index] ) == 0 )
388 doActualRemove( link, index, bucketIndex );
396 ValueInternalMap::doActualRemove( ValueInternalLink *link,
398 BucketIndex bucketIndex )
403 ValueInternalLink *&lastLink = getLastLinkInBucket( index );
404 BucketIndex lastItemIndex = 1;
406 lastItemIndex < ValueInternalLink::itemPerLink;
409 if ( lastLink->items_[lastItemIndex].isItemAvailable() )
413 BucketIndex lastUsedIndex = lastItemIndex - 1;
414 Value *valueToDelete = &link->items_[index];
415 Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
416 if ( valueToDelete != valueToPreserve )
417 valueToDelete->swap( *valueToPreserve );
418 if ( lastUsedIndex == 0 )
420 ValueInternalLink *linkPreviousToLast = lastLink->previous_;
421 if ( linkPreviousToLast != 0 )
423 mapAllocator()->releaseMapLink( lastLink );
424 linkPreviousToLast->next_ = 0;
425 lastLink = linkPreviousToLast;
431 valueToPreserve->swap( dummy );
432 valueToPreserve->setItemUsed(
false );
439 ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
441 if ( bucketIndex == bucketsSize_ - 1 )
443 ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
445 previous = &buckets_[bucketIndex];
451 ValueInternalMap::setNewItem(
const char *key,
453 ValueInternalLink *link,
456 char *duplicatedKey = valueAllocator()->makeMemberName( key );
458 link->keys_[index] = duplicatedKey;
459 link->items_[index].setItemUsed();
460 link->items_[index].setMemberNameIsStatic( isStatic );
461 return link->items_[index];
466 ValueInternalMap::unsafeAdd(
const char *key,
470 JSON_ASSERT_MESSAGE( bucketsSize_ > 0,
"ValueInternalMap::unsafeAdd(): internal logic error." );
471 BucketIndex bucketIndex = hashedKey % bucketsSize_;
472 ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
473 ValueInternalLink *link = previousLink;
475 for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
477 if ( link->items_[index].isItemAvailable() )
480 if ( index == ValueInternalLink::itemPerLink )
482 ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
484 link->next_ = newLink;
485 previousLink = newLink;
488 return setNewItem( key, isStatic, link, index );
492 ValueInternalMap::HashKey
493 ValueInternalMap::hash(
const char *key )
const
503 ValueInternalMap::compare(
const ValueInternalMap &other )
const
505 int sizeDiff( itemCount_ - other.itemCount_ );
511 makeBeginIterator( it );
512 makeEndIterator( itEnd );
513 for ( ; !equals(it,itEnd); increment(it) )
515 if ( !other.find( key( it ) ) )
520 makeBeginIterator( it );
521 for ( ; !equals(it,itEnd); increment(it) )
523 const Value *otherValue = other.find( key( it ) );
524 int valueDiff = value(it).compare( *otherValue );
525 if ( valueDiff != 0 )
533 ValueInternalMap::makeBeginIterator( IteratorState &it )
const
535 it.map_ =
const_cast<ValueInternalMap *
>( this );
543 ValueInternalMap::makeEndIterator( IteratorState &it )
const
545 it.map_ =
const_cast<ValueInternalMap *
>( this );
546 it.bucketIndex_ = bucketsSize_;
553 ValueInternalMap::equals(
const IteratorState &x,
const IteratorState &other )
555 return x.map_ == other.map_
556 && x.bucketIndex_ == other.bucketIndex_
557 && x.link_ == other.link_
558 && x.itemIndex_ == other.itemIndex_;
563 ValueInternalMap::incrementBucket( IteratorState &iterator )
565 ++iterator.bucketIndex_;
566 JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
567 "ValueInternalMap::increment(): attempting to iterate beyond end." );
568 if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
571 iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
572 iterator.itemIndex_ = 0;
577 ValueInternalMap::increment( IteratorState &iterator )
579 JSON_ASSERT_MESSAGE( iterator.map_,
"Attempting to iterator using invalid iterator." );
580 ++iterator.itemIndex_;
581 if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
583 JSON_ASSERT_MESSAGE( iterator.link_ != 0,
584 "ValueInternalMap::increment(): attempting to iterate beyond end." );
585 iterator.link_ = iterator.link_->next_;
586 if ( iterator.link_ == 0 )
587 incrementBucket( iterator );
589 else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
591 incrementBucket( iterator );
597 ValueInternalMap::decrement( IteratorState &iterator )
599 if ( iterator.itemIndex_ == 0 )
601 JSON_ASSERT_MESSAGE( iterator.map_,
"Attempting to iterate using invalid iterator." );
602 if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
604 JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0,
"Attempting to iterate beyond beginning." );
605 --(iterator.bucketIndex_);
607 iterator.link_ = iterator.link_->previous_;
608 iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
614 ValueInternalMap::key(
const IteratorState &iterator )
616 JSON_ASSERT_MESSAGE( iterator.link_,
"Attempting to iterate using invalid iterator." );
617 return iterator.link_->keys_[iterator.itemIndex_];
621 ValueInternalMap::key(
const IteratorState &iterator,
bool &isStatic )
623 JSON_ASSERT_MESSAGE( iterator.link_,
"Attempting to iterate using invalid iterator." );
624 isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
625 return iterator.link_->keys_[iterator.itemIndex_];
630 ValueInternalMap::value(
const IteratorState &iterator )
632 JSON_ASSERT_MESSAGE( iterator.link_,
"Attempting to iterate using invalid iterator." );
633 return iterator.link_->items_[iterator.itemIndex_];
638 ValueInternalMap::distance(
const IteratorState &x,
const IteratorState &y )
641 IteratorState it = x;
642 while ( !equals( it, y ) )