Utilities/src/json_internalmap.icc

0001 // included by json_value.cpp
0002 // everything is within Json namespace
0003
0004 // //////////////////////////////////////////////////////////////////
0005 // //////////////////////////////////////////////////////////////////
0006 // //////////////////////////////////////////////////////////////////
0007 // class ValueInternalMap
0008 // //////////////////////////////////////////////////////////////////
0009 // //////////////////////////////////////////////////////////////////
0010 // //////////////////////////////////////////////////////////////////
0011
0012 /** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
0013    * This optimization is used by the fast allocator.
0014    */
0015 ValueInternalLink::ValueInternalLink() : previous_(0), next_(0) {}
0016
0017 ValueInternalLink::~ValueInternalLink() {
0018   for (int index = 0; index < itemPerLink; ++index) {
0019     if (!items_[index].isItemAvailable()) {
0020       if (!items_[index].isMemberNameStatic())
0021         free(keys_[index]);
0022     } else
0023       break;
0024   }
0025 }
0026
0027 ValueMapAllocator::~ValueMapAllocator() {}
0028
0029 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
0030 class DefaultValueMapAllocator : public ValueMapAllocator {
0031 public:  // overridden from ValueMapAllocator
0032   virtual ValueInternalMap *newMap() { return new ValueInternalMap(); }
0033
0034   virtual ValueInternalMap *newMapCopy(const ValueInternalMap &other) { return new ValueInternalMap(other); }
0035
0036   virtual void destructMap(ValueInternalMap *map) { delete map; }
0037
0038   virtual ValueInternalLink *allocateMapBuckets(unsigned int size) { return new ValueInternalLink[size]; }
0039
0040   virtual void releaseMapBuckets(ValueInternalLink *links) { delete[] links; }
0041
0042   virtual ValueInternalLink *allocateMapLink() { return new ValueInternalLink(); }
0043
0044   virtual void releaseMapLink(ValueInternalLink *link) { delete link; }
0045 };
0046 #else
0047 /// @todo make this thread-safe (lock when accessign batch allocator)
0048 class DefaultValueMapAllocator : public ValueMapAllocator {
0049 public:  // overridden from ValueMapAllocator
0050   virtual ValueInternalMap *newMap() {
0051     ValueInternalMap *map = mapsAllocator_.allocate();
0052     new (map) ValueInternalMap();  // placement new
0053     return map;
0054   }
0055
0056   virtual ValueInternalMap *newMapCopy(const ValueInternalMap &other) {
0057     ValueInternalMap *map = mapsAllocator_.allocate();
0058     new (map) ValueInternalMap(other);  // placement new
0059     return map;
0060   }
0061
0062   virtual void destructMap(ValueInternalMap *map) {
0063     if (map) {
0064       map->~ValueInternalMap();
0065       mapsAllocator_.release(map);
0066     }
0067   }
0068
0069   virtual ValueInternalLink *allocateMapBuckets(unsigned int size) { return new ValueInternalLink[size]; }
0070
0071   virtual void releaseMapBuckets(ValueInternalLink *links) { delete[] links; }
0072
0073   virtual ValueInternalLink *allocateMapLink() {
0074     ValueInternalLink *link = linksAllocator_.allocate();
0075     memset(link, 0, sizeof(ValueInternalLink));
0076     return link;
0077   }
0078
0079   virtual void releaseMapLink(ValueInternalLink *link) {
0080     link->~ValueInternalLink();
0081     linksAllocator_.release(link);
0082   }
0083
0084 private:
0085   BatchAllocator<ValueInternalMap, 1> mapsAllocator_;
0086   BatchAllocator<ValueInternalLink, 1> linksAllocator_;
0087 };
0088 #endif
0089
0090 static ValueMapAllocator *&mapAllocator() {
0091   static DefaultValueMapAllocator defaultAllocator;
0092   static ValueMapAllocator *mapAllocator = &defaultAllocator;
0093   return mapAllocator;
0094 }
0095
0096 static struct DummyMapAllocatorInitializer {
0097   DummyMapAllocatorInitializer() {
0098     mapAllocator();  // ensure mapAllocator() statics are initialized before main().
0099   }
0100 } dummyMapAllocatorInitializer;
0101
0102 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
0103
0104 /*
0105 use linked list hash map.
0106 buckets array is a container.
0107 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
0108 value have extra state: valid, available, deleted
0109 */
0110
0111 ValueInternalMap::ValueInternalMap() : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) {}
0112
0113 ValueInternalMap::ValueInternalMap(const ValueInternalMap &other)
0114     : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) {
0115   reserve(other.itemCount_);
0116   IteratorState it;
0117   IteratorState itEnd;
0118   other.makeBeginIterator(it);
0119   other.makeEndIterator(itEnd);
0120   for (; !equals(it, itEnd); increment(it)) {
0121     bool isStatic;
0122     const char *memberName = key(it, isStatic);
0123     const Value &aValue = value(it);
0124     resolveReference(memberName, isStatic) = aValue;
0125   }
0126 }
0127
0128 ValueInternalMap &ValueInternalMap::operator=(const ValueInternalMap &other) {
0129   ValueInternalMap dummy(other);
0130   swap(dummy);
0131   return *this;
0132 }
0133
0134 ValueInternalMap::~ValueInternalMap() {
0135   if (buckets_) {
0136     for (BucketIndex bucketIndex = 0; bucketIndex < bucketsSize_; ++bucketIndex) {
0137       ValueInternalLink *link = buckets_[bucketIndex].next_;
0138       while (link) {
0139         ValueInternalLink *linkToRelease = link;
0140         link = link->next_;
0141         mapAllocator()->releaseMapLink(linkToRelease);
0142       }
0143     }
0144     mapAllocator()->releaseMapBuckets(buckets_);
0145   }
0146 }
0147
0148 void ValueInternalMap::swap(ValueInternalMap &other) {
0149   ValueInternalLink *tempBuckets = buckets_;
0150   buckets_ = other.buckets_;
0151   other.buckets_ = tempBuckets;
0152   ValueInternalLink *tempTailLink = tailLink_;
0153   tailLink_ = other.tailLink_;
0154   other.tailLink_ = tempTailLink;
0155   BucketIndex tempBucketsSize = bucketsSize_;
0156   bucketsSize_ = other.bucketsSize_;
0157   other.bucketsSize_ = tempBucketsSize;
0158   BucketIndex tempItemCount = itemCount_;
0159   itemCount_ = other.itemCount_;
0160   other.itemCount_ = tempItemCount;
0161 }
0162
0163 void ValueInternalMap::clear() {
0164   ValueInternalMap dummy;
0165   swap(dummy);
0166 }
0167
0168 ValueInternalMap::BucketIndex ValueInternalMap::size() const { return itemCount_; }
0169
0170 bool ValueInternalMap::reserveDelta(BucketIndex growth) { return reserve(itemCount_ + growth); }
0171
0172 bool ValueInternalMap::reserve(BucketIndex newItemCount) {
0173   if (!buckets_ && newItemCount > 0) {
0174     buckets_ = mapAllocator()->allocateMapBuckets(1);
0175     bucketsSize_ = 1;
0176     tailLink_ = &buckets_[0];
0177   }
0178   //   BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
0179   return true;
0180 }
0181
0182 const Value *ValueInternalMap::find(const char *key) const {
0183   if (!bucketsSize_)
0184     return 0;
0185   HashKey hashedKey = hash(key);
0186   BucketIndex bucketIndex = hashedKey % bucketsSize_;
0187   for (const ValueInternalLink *current = &buckets_[bucketIndex]; current != 0; current = current->next_) {
0188     for (BucketIndex index = 0; index < ValueInternalLink::itemPerLink; ++index) {
0189       if (current->items_[index].isItemAvailable())
0190         return 0;
0191       if (strcmp(key, current->keys_[index]) == 0)
0192         return &current->items_[index];
0193     }
0194   }
0195   return 0;
0196 }
0197
0198 Value *ValueInternalMap::find(const char *key) {
0199   const ValueInternalMap *constThis = this;
0200   return const_cast<Value *>(constThis->find(key));
0201 }
0202
0203 Value &ValueInternalMap::resolveReference(const char *key, bool isStatic) {
0204   HashKey hashedKey = hash(key);
0205   if (bucketsSize_) {
0206     BucketIndex bucketIndex = hashedKey % bucketsSize_;
0207     ValueInternalLink **previous = 0;
0208     BucketIndex index;
0209     for (ValueInternalLink *current = &buckets_[bucketIndex]; current != 0;
0210          previous = &current->next_, current = current->next_) {
0211       for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
0212         if (current->items_[index].isItemAvailable())
0213           return setNewItem(key, isStatic, current, index);
0214         if (strcmp(key, current->keys_[index]) == 0)
0215           return current->items_[index];
0216       }
0217     }
0218   }
0219
0220   reserveDelta(1);
0221   return unsafeAdd(key, isStatic, hashedKey);
0222 }
0223
0224 void ValueInternalMap::remove(const char *key) {
0225   HashKey hashedKey = hash(key);
0226   if (!bucketsSize_)
0227     return;
0228   BucketIndex bucketIndex = hashedKey % bucketsSize_;
0229   for (ValueInternalLink *link = &buckets_[bucketIndex]; link != 0; link = link->next_) {
0230     BucketIndex index;
0231     for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
0232       if (link->items_[index].isItemAvailable())
0233         return;
0234       if (strcmp(key, link->keys_[index]) == 0) {
0235         doActualRemove(link, index, bucketIndex);
0236         return;
0237       }
0238     }
0239   }
0240 }
0241
0242 void ValueInternalMap::doActualRemove(ValueInternalLink *link, BucketIndex index, BucketIndex bucketIndex) {
0243   // find last item of the bucket and swap it with the 'removed' one.
0244   // set removed items flags to 'available'.
0245   // if last page only contains 'available' items, then desallocate it (it's empty)
0246   ValueInternalLink *&lastLink = getLastLinkInBucket(index);
0247   BucketIndex lastItemIndex = 1;                                           // a link can never be empty, so start at 1
0248   for (; lastItemIndex < ValueInternalLink::itemPerLink; ++lastItemIndex)  // may be optimized with dicotomic search
0249   {
0250     if (lastLink->items_[lastItemIndex].isItemAvailable())
0251       break;
0252   }
0253
0254   BucketIndex lastUsedIndex = lastItemIndex - 1;
0255   Value *valueToDelete = &link->items_[index];
0256   Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
0257   if (valueToDelete != valueToPreserve)
0258     valueToDelete->swap(*valueToPreserve);
0259   if (lastUsedIndex == 0)  // page is now empty
0260   {                        // remove it from bucket linked list and delete it.
0261     ValueInternalLink *linkPreviousToLast = lastLink->previous_;
0262     if (linkPreviousToLast != 0)  // can not deleted bucket link.
0263     {
0264       mapAllocator()->releaseMapLink(lastLink);
0265       linkPreviousToLast->next_ = 0;
0266       lastLink = linkPreviousToLast;
0267     }
0268   } else {
0269     Value dummy;
0270     valueToPreserve->swap(dummy);  // restore deleted to default Value.
0271     valueToPreserve->setItemUsed(false);
0272   }
0273   --itemCount_;
0274 }
0275
0276 ValueInternalLink *&ValueInternalMap::getLastLinkInBucket(BucketIndex bucketIndex) {
0277   if (bucketIndex == bucketsSize_ - 1)
0278     return tailLink_;
0279   ValueInternalLink *&previous = buckets_[bucketIndex + 1].previous_;
0280   if (!previous)
0281     previous = &buckets_[bucketIndex];
0282   return previous;
0283 }
0284
0285 Value &ValueInternalMap::setNewItem(const char *key, bool isStatic, ValueInternalLink *link, BucketIndex index) {
0286   char *duplicatedKey = valueAllocator()->makeMemberName(key);
0287   ++itemCount_;
0288   link->keys_[index] = duplicatedKey;
0289   link->items_[index].setItemUsed();
0290   link->items_[index].setMemberNameIsStatic(isStatic);
0291   return link->items_[index];  // items already default constructed.
0292 }
0293
0294 Value &ValueInternalMap::unsafeAdd(const char *key, bool isStatic, HashKey hashedKey) {
0295   JSON_ASSERT_MESSAGE(bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error.");
0296   BucketIndex bucketIndex = hashedKey % bucketsSize_;
0297   ValueInternalLink *&previousLink = getLastLinkInBucket(bucketIndex);
0298   ValueInternalLink *link = previousLink;
0299   BucketIndex index;
0300   for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
0301     if (link->items_[index].isItemAvailable())
0302       break;
0303   }
0304   if (index == ValueInternalLink::itemPerLink)  // need to add a new page
0305   {
0306     ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
0307     index = 0;
0308     link->next_ = newLink;
0309     previousLink = newLink;
0310     link = newLink;
0311   }
0312   return setNewItem(key, isStatic, link, index);
0313 }
0314
0315 ValueInternalMap::HashKey ValueInternalMap::hash(const char *key) const {
0316   HashKey hash = 0;
0317   while (*key)
0318     hash += *key++ * 37;
0319   return hash;
0320 }
0321
0322 int ValueInternalMap::compare(const ValueInternalMap &other) const {
0323   int sizeDiff(itemCount_ - other.itemCount_);
0324   if (sizeDiff != 0)
0325     return sizeDiff;
0326   // Strict order guaranty is required. Compare all keys FIRST, then compare values.
0327   IteratorState it;
0328   IteratorState itEnd;
0329   makeBeginIterator(it);
0330   makeEndIterator(itEnd);
0331   for (; !equals(it, itEnd); increment(it)) {
0332     if (!other.find(key(it)))
0333       return 1;
0334   }
0335
0336   // All keys are equals, let's compare values
0337   makeBeginIterator(it);
0338   for (; !equals(it, itEnd); increment(it)) {
0339     const Value *otherValue = other.find(key(it));
0340     int valueDiff = value(it).compare(*otherValue);
0341     if (valueDiff != 0)
0342       return valueDiff;
0343   }
0344   return 0;
0345 }
0346
0347 void ValueInternalMap::makeBeginIterator(IteratorState &it) const {
0348   it.map_ = const_cast<ValueInternalMap *>(this);
0349   it.bucketIndex_ = 0;
0350   it.itemIndex_ = 0;
0351   it.link_ = buckets_;
0352 }
0353
0354 void ValueInternalMap::makeEndIterator(IteratorState &it) const {
0355   it.map_ = const_cast<ValueInternalMap *>(this);
0356   it.bucketIndex_ = bucketsSize_;
0357   it.itemIndex_ = 0;
0358   it.link_ = 0;
0359 }
0360
0361 bool ValueInternalMap::equals(const IteratorState &x, const IteratorState &other) {
0362   return x.map_ == other.map_ && x.bucketIndex_ == other.bucketIndex_ && x.link_ == other.link_ &&
0363          x.itemIndex_ == other.itemIndex_;
0364 }
0365
0366 void ValueInternalMap::incrementBucket(IteratorState &iterator) {
0367   ++iterator.bucketIndex_;
0368   JSON_ASSERT_MESSAGE(iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
0369                       "ValueInternalMap::increment(): attempting to iterate beyond end.");
0370   if (iterator.bucketIndex_ == iterator.map_->bucketsSize_)
0371     iterator.link_ = 0;
0372   else
0373     iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
0374   iterator.itemIndex_ = 0;
0375 }
0376
0377 void ValueInternalMap::increment(IteratorState &iterator) {
0378   JSON_ASSERT_MESSAGE(iterator.map_, "Attempting to iterator using invalid iterator.");
0379   ++iterator.itemIndex_;
0380   if (iterator.itemIndex_ == ValueInternalLink::itemPerLink) {
0381     JSON_ASSERT_MESSAGE(iterator.link_ != 0, "ValueInternalMap::increment(): attempting to iterate beyond end.");
0382     iterator.link_ = iterator.link_->next_;
0383     if (iterator.link_ == 0)
0384       incrementBucket(iterator);
0385   } else if (iterator.link_->items_[iterator.itemIndex_].isItemAvailable()) {
0386     incrementBucket(iterator);
0387   }
0388 }
0389
0390 void ValueInternalMap::decrement(IteratorState &iterator) {
0391   if (iterator.itemIndex_ == 0) {
0392     JSON_ASSERT_MESSAGE(iterator.map_, "Attempting to iterate using invalid iterator.");
0393     if (iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_]) {
0394       JSON_ASSERT_MESSAGE(iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning.");
0395       --(iterator.bucketIndex_);
0396     }
0397     iterator.link_ = iterator.link_->previous_;
0398     iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
0399   }
0400 }
0401
0402 const char *ValueInternalMap::key(const IteratorState &iterator) {
0403   JSON_ASSERT_MESSAGE(iterator.link_, "Attempting to iterate using invalid iterator.");
0404   return iterator.link_->keys_[iterator.itemIndex_];
0405 }
0406
0407 const char *ValueInternalMap::key(const IteratorState &iterator, bool &isStatic) {
0408   JSON_ASSERT_MESSAGE(iterator.link_, "Attempting to iterate using invalid iterator.");
0409   isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
0410   return iterator.link_->keys_[iterator.itemIndex_];
0411 }
0412
0413 Value &ValueInternalMap::value(const IteratorState &iterator) {
0414   JSON_ASSERT_MESSAGE(iterator.link_, "Attempting to iterate using invalid iterator.");
0415   return iterator.link_->items_[iterator.itemIndex_];
0416 }
0417
0418 int ValueInternalMap::distance(const IteratorState &x, const IteratorState &y) {
0419   int offset = 0;
0420   IteratorState it = x;
0421   while (!equals(it, y))
0422     increment(it);
0423   return offset;
0424 }