src/lib_json/json_internalmap.inl

// Copyright 2007-2010 Baptiste Lepilleur
// Distributed under MIT license, or public domain if desired and
// recognized in your jurisdiction.
// See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE

// included by json_value.cpp

namespace Json {

// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// class ValueInternalMap
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////

/** \internal MUST be safely initialized using memset( this, 0,
 * sizeof(ValueInternalLink) );
   * This optimization is used by the fast allocator.
   */
ValueInternalLink::ValueInternalLink() : previous_(0), next_(0) {}

ValueInternalLink::~ValueInternalLink() {
  for (int index = 0; index < itemPerLink; ++index) {
    if (!items_[index].isItemAvailable()) {
      if (!items_[index].isMemberNameStatic())
        free(keys_[index]);
    } else
      break;
  }
}

ValueMapAllocator::~ValueMapAllocator() {}

#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
class DefaultValueMapAllocator : public ValueMapAllocator {
public: // overridden from ValueMapAllocator
  virtual ValueInternalMap* newMap() { return new ValueInternalMap(); }

  virtual ValueInternalMap* newMapCopy(const ValueInternalMap& other) {
    return new ValueInternalMap(other);
  }

  virtual void destructMap(ValueInternalMap* map) { delete map; }

  virtual ValueInternalLink* allocateMapBuckets(unsigned int size) {
    return new ValueInternalLink[size];
  }

  virtual void releaseMapBuckets(ValueInternalLink* links) { delete[] links; }

  virtual ValueInternalLink* allocateMapLink() {
    return new ValueInternalLink();
  }

  virtual void releaseMapLink(ValueInternalLink* link) { delete link; }
};
#else
/// @todo make this thread-safe (lock when accessign batch allocator)
class DefaultValueMapAllocator : public ValueMapAllocator {
public: // overridden from ValueMapAllocator
  virtual ValueInternalMap* newMap() {
    ValueInternalMap* map = mapsAllocator_.allocate();
    new (map) ValueInternalMap(); // placement new
    return map;
  }

  virtual ValueInternalMap* newMapCopy(const ValueInternalMap& other) {
    ValueInternalMap* map = mapsAllocator_.allocate();
    new (map) ValueInternalMap(other); // placement new
    return map;
  }

  virtual void destructMap(ValueInternalMap* map) {
    if (map) {
      map->~ValueInternalMap();
      mapsAllocator_.release(map);
    }
  }

  virtual ValueInternalLink* allocateMapBuckets(unsigned int size) {
    return new ValueInternalLink[size];
  }

  virtual void releaseMapBuckets(ValueInternalLink* links) { delete[] links; }

  virtual ValueInternalLink* allocateMapLink() {
    ValueInternalLink* link = linksAllocator_.allocate();
    memset(link, 0, sizeof(ValueInternalLink));
    return link;
  }

  virtual void releaseMapLink(ValueInternalLink* link) {
    link->~ValueInternalLink();
    linksAllocator_.release(link);
  }

private:
  BatchAllocator<ValueInternalMap, 1> mapsAllocator_;
  BatchAllocator<ValueInternalLink, 1> linksAllocator_;
};
#endif

static ValueMapAllocator*& mapAllocator() {
  static DefaultValueMapAllocator defaultAllocator;
  static ValueMapAllocator* mapAllocator = &defaultAllocator;
  return mapAllocator;
}

static struct DummyMapAllocatorInitializer {
  DummyMapAllocatorInitializer() {
    mapAllocator(); // ensure mapAllocator() statics are initialized before
                    // main().
  }
} dummyMapAllocatorInitializer;

// h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.

/*
use linked list hash map.
buckets array is a container.
linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
value have extra state: valid, available, deleted
*/

ValueInternalMap::ValueInternalMap()
    : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) {}

ValueInternalMap::ValueInternalMap(const ValueInternalMap& other)
    : buckets_(0), tailLink_(0), bucketsSize_(0), itemCount_(0) {
  reserve(other.itemCount_);
  IteratorState it;
  IteratorState itEnd;
  other.makeBeginIterator(it);
  other.makeEndIterator(itEnd);
  for (; !equals(it, itEnd); increment(it)) {
    bool isStatic;
    const char* memberName = key(it, isStatic);
    const Value& aValue = value(it);
    resolveReference(memberName, isStatic) = aValue;
  }
}

ValueInternalMap& ValueInternalMap::operator=(ValueInternalMap other) {
  swap(other);
  return *this;
}

ValueInternalMap::~ValueInternalMap() {
  if (buckets_) {
    for (BucketIndex bucketIndex = 0; bucketIndex < bucketsSize_;
         ++bucketIndex) {
      ValueInternalLink* link = buckets_[bucketIndex].next_;
      while (link) {
        ValueInternalLink* linkToRelease = link;
        link = link->next_;
        mapAllocator()->releaseMapLink(linkToRelease);
      }
    }
    mapAllocator()->releaseMapBuckets(buckets_);
  }
}

void ValueInternalMap::swap(ValueInternalMap& other) {
  ValueInternalLink* tempBuckets = buckets_;
  buckets_ = other.buckets_;
  other.buckets_ = tempBuckets;
  ValueInternalLink* tempTailLink = tailLink_;
  tailLink_ = other.tailLink_;
  other.tailLink_ = tempTailLink;
  BucketIndex tempBucketsSize = bucketsSize_;
  bucketsSize_ = other.bucketsSize_;
  other.bucketsSize_ = tempBucketsSize;
  BucketIndex tempItemCount = itemCount_;
  itemCount_ = other.itemCount_;
  other.itemCount_ = tempItemCount;
}

void ValueInternalMap::clear() {
  ValueInternalMap dummy;
  swap(dummy);
}

ValueInternalMap::BucketIndex ValueInternalMap::size() const {
  return itemCount_;
}

bool ValueInternalMap::reserveDelta(BucketIndex growth) {
  return reserve(itemCount_ + growth);
}

bool ValueInternalMap::reserve(BucketIndex newItemCount) {
  if (!buckets_ && newItemCount > 0) {
    buckets_ = mapAllocator()->allocateMapBuckets(1);
    bucketsSize_ = 1;
    tailLink_ = &buckets_[0];
  }
  //   BucketIndex idealBucketCount = (newItemCount +
  // ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
  return true;
}

const Value* ValueInternalMap::find(const char* key) const {
  if (!bucketsSize_)
    return 0;
  HashKey hashedKey = hash(key);
  BucketIndex bucketIndex = hashedKey % bucketsSize_;
  for (const ValueInternalLink* current = &buckets_[bucketIndex]; current != 0;
       current = current->next_) {
    for (BucketIndex index = 0; index < ValueInternalLink::itemPerLink;
         ++index) {
      if (current->items_[index].isItemAvailable())
        return 0;
      if (strcmp(key, current->keys_[index]) == 0)
        return &current->items_[index];
    }
  }
  return 0;
}

Value* ValueInternalMap::find(const char* key) {
  const ValueInternalMap* constThis = this;
  return const_cast<Value*>(constThis->find(key));
}

Value& ValueInternalMap::resolveReference(const char* key, bool isStatic) {
  HashKey hashedKey = hash(key);
  if (bucketsSize_) {
    BucketIndex bucketIndex = hashedKey % bucketsSize_;
    ValueInternalLink** previous = 0;
    BucketIndex index;
    for (ValueInternalLink* current = &buckets_[bucketIndex]; current != 0;
         previous = &current->next_, current = current->next_) {
      for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
        if (current->items_[index].isItemAvailable())
          return setNewItem(key, isStatic, current, index);
        if (strcmp(key, current->keys_[index]) == 0)
          return current->items_[index];
      }
    }
  }

  reserveDelta(1);
  return unsafeAdd(key, isStatic, hashedKey);
}

void ValueInternalMap::remove(const char* key) {
  HashKey hashedKey = hash(key);
  if (!bucketsSize_)
    return;
  BucketIndex bucketIndex = hashedKey % bucketsSize_;
  for (ValueInternalLink* link = &buckets_[bucketIndex]; link != 0;
       link = link->next_) {
    BucketIndex index;
    for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
      if (link->items_[index].isItemAvailable())
        return;
      if (strcmp(key, link->keys_[index]) == 0) {
        doActualRemove(link, index, bucketIndex);
        return;
      }
    }
  }
}

void ValueInternalMap::doActualRemove(ValueInternalLink* link,
                                      BucketIndex index,
                                      BucketIndex bucketIndex) {
  // find last item of the bucket and swap it with the 'removed' one.
  // set removed items flags to 'available'.
  // if last page only contains 'available' items, then desallocate it (it's
  // empty)
  ValueInternalLink*& lastLink = getLastLinkInBucket(index);
  BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
  for (; lastItemIndex < ValueInternalLink::itemPerLink;
       ++lastItemIndex) // may be optimized with dicotomic search
  {
    if (lastLink->items_[lastItemIndex].isItemAvailable())
      break;
  }

  BucketIndex lastUsedIndex = lastItemIndex - 1;
  Value* valueToDelete = &link->items_[index];
  Value* valueToPreserve = &lastLink->items_[lastUsedIndex];
  if (valueToDelete != valueToPreserve)
    valueToDelete->swap(*valueToPreserve);
  if (lastUsedIndex == 0) // page is now empty
  {                       // remove it from bucket linked list and delete it.
    ValueInternalLink* linkPreviousToLast = lastLink->previous_;
    if (linkPreviousToLast != 0) // can not deleted bucket link.
    {
      mapAllocator()->releaseMapLink(lastLink);
      linkPreviousToLast->next_ = 0;
      lastLink = linkPreviousToLast;
    }
  } else {
    Value dummy;
    valueToPreserve->swap(dummy); // restore deleted to default Value.
    valueToPreserve->setItemUsed(false);
  }
  --itemCount_;
}

ValueInternalLink*&
ValueInternalMap::getLastLinkInBucket(BucketIndex bucketIndex) {
  if (bucketIndex == bucketsSize_ - 1)
    return tailLink_;
  ValueInternalLink*& previous = buckets_[bucketIndex + 1].previous_;
  if (!previous)
    previous = &buckets_[bucketIndex];
  return previous;
}

Value& ValueInternalMap::setNewItem(const char* key,
                                    bool isStatic,
                                    ValueInternalLink* link,
                                    BucketIndex index) {
  char* duplicatedKey = makeMemberName(key);
  ++itemCount_;
  link->keys_[index] = duplicatedKey;
  link->items_[index].setItemUsed();
  link->items_[index].setMemberNameIsStatic(isStatic);
  return link->items_[index]; // items already default constructed.
}

Value&
ValueInternalMap::unsafeAdd(const char* key, bool isStatic, HashKey hashedKey) {
  JSON_ASSERT_MESSAGE(bucketsSize_ > 0,
                      "ValueInternalMap::unsafeAdd(): internal logic error.");
  BucketIndex bucketIndex = hashedKey % bucketsSize_;
  ValueInternalLink*& previousLink = getLastLinkInBucket(bucketIndex);
  ValueInternalLink* link = previousLink;
  BucketIndex index;
  for (index = 0; index < ValueInternalLink::itemPerLink; ++index) {
    if (link->items_[index].isItemAvailable())
      break;
  }
  if (index == ValueInternalLink::itemPerLink) // need to add a new page
  {
    ValueInternalLink* newLink = mapAllocator()->allocateMapLink();
    index = 0;
    link->next_ = newLink;
    previousLink = newLink;
    link = newLink;
  }
  return setNewItem(key, isStatic, link, index);
}

ValueInternalMap::HashKey ValueInternalMap::hash(const char* key) const {
  HashKey hash = 0;
  while (*key)
    hash += *key++ * 37;
  return hash;
}

int ValueInternalMap::compare(const ValueInternalMap& other) const {
  int sizeDiff(itemCount_ - other.itemCount_);
  if (sizeDiff != 0)
    return sizeDiff;
  // Strict order guaranty is required. Compare all keys FIRST, then compare
  // values.
  IteratorState it;
  IteratorState itEnd;
  makeBeginIterator(it);
  makeEndIterator(itEnd);
  for (; !equals(it, itEnd); increment(it)) {
    if (!other.find(key(it)))
      return 1;
  }

  // All keys are equals, let's compare values
  makeBeginIterator(it);
  for (; !equals(it, itEnd); increment(it)) {
    const Value* otherValue = other.find(key(it));
    int valueDiff = value(it).compare(*otherValue);
    if (valueDiff != 0)
      return valueDiff;
  }
  return 0;
}

void ValueInternalMap::makeBeginIterator(IteratorState& it) const {
  it.map_ = const_cast<ValueInternalMap*>(this);
  it.bucketIndex_ = 0;
  it.itemIndex_ = 0;
  it.link_ = buckets_;
}

void ValueInternalMap::makeEndIterator(IteratorState& it) const {
  it.map_ = const_cast<ValueInternalMap*>(this);
  it.bucketIndex_ = bucketsSize_;
  it.itemIndex_ = 0;
  it.link_ = 0;
}

bool ValueInternalMap::equals(const IteratorState& x,
                              const IteratorState& other) {
  return x.map_ == other.map_ && x.bucketIndex_ == other.bucketIndex_ &&
         x.link_ == other.link_ && x.itemIndex_ == other.itemIndex_;
}

void ValueInternalMap::incrementBucket(IteratorState& iterator) {
  ++iterator.bucketIndex_;
  JSON_ASSERT_MESSAGE(
      iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
      "ValueInternalMap::increment(): attempting to iterate beyond end.");
  if (iterator.bucketIndex_ == iterator.map_->bucketsSize_)
    iterator.link_ = 0;
  else
    iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
  iterator.itemIndex_ = 0;
}

void ValueInternalMap::increment(IteratorState& iterator) {
  JSON_ASSERT_MESSAGE(iterator.map_,
                      "Attempting to iterator using invalid iterator.");
  ++iterator.itemIndex_;
  if (iterator.itemIndex_ == ValueInternalLink::itemPerLink) {
    JSON_ASSERT_MESSAGE(
        iterator.link_ != 0,
        "ValueInternalMap::increment(): attempting to iterate beyond end.");
    iterator.link_ = iterator.link_->next_;
    if (iterator.link_ == 0)
      incrementBucket(iterator);
  } else if (iterator.link_->items_[iterator.itemIndex_].isItemAvailable()) {
    incrementBucket(iterator);
  }
}

void ValueInternalMap::decrement(IteratorState& iterator) {
  if (iterator.itemIndex_ == 0) {
    JSON_ASSERT_MESSAGE(iterator.map_,
                        "Attempting to iterate using invalid iterator.");
    if (iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_]) {
      JSON_ASSERT_MESSAGE(iterator.bucketIndex_ > 0,
                          "Attempting to iterate beyond beginning.");
      --(iterator.bucketIndex_);
    }
    iterator.link_ = iterator.link_->previous_;
    iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
  }
}

const char* ValueInternalMap::key(const IteratorState& iterator) {
  JSON_ASSERT_MESSAGE(iterator.link_,
                      "Attempting to iterate using invalid iterator.");
  return iterator.link_->keys_[iterator.itemIndex_];
}

const char* ValueInternalMap::key(const IteratorState& iterator,
                                  bool& isStatic) {
  JSON_ASSERT_MESSAGE(iterator.link_,
                      "Attempting to iterate using invalid iterator.");
  isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
  return iterator.link_->keys_[iterator.itemIndex_];
}

Value& ValueInternalMap::value(const IteratorState& iterator) {
  JSON_ASSERT_MESSAGE(iterator.link_,
                      "Attempting to iterate using invalid iterator.");
  return iterator.link_->items_[iterator.itemIndex_];
}

int ValueInternalMap::distance(const IteratorState& x, const IteratorState& y) {
  int offset = 0;
  IteratorState it = x;
  while (!equals(it, y))
    increment(it);
  return offset;
}

} // namespace Json