text: /*
   * Copyright (c) Facebook, Inc. and its affiliates.
   *
   * This source code is licensed under the MIT license found in the
   * LICENSE file in the root directory of this source tree.
   */
  
  #include "hermes/VM/OrderedHashMap.h"
  
  #include "hermes/Support/ErrorHandling.h"
  #include "hermes/VM/BuildMetadata.h"
  #include "hermes/VM/GCPointer-inline.h"
  #include "hermes/VM/Operations.h"
  
  #include "llvm/Support/Debug.h"
  #define DEBUG_TYPE "serialize"
  
  namespace hermes {
  namespace vm {
  //===----------------------------------------------------------------------===//
  // class HashMapEntry
  
  VTable HashMapEntry::vt{CellKind::HashMapEntryKind, sizeof(HashMapEntry)};
  
  void HashMapEntryBuildMeta(const GCCell *cell, Metadata::Builder &mb) {
    const auto *self = static_cast<const HashMapEntry *>(cell);
    mb.addField("key", &self->key);
    mb.addField("value", &self->value);
    mb.addField("prevIterationEntry", &self->prevIterationEntry);
    mb.addField("nextIterationEntry", &self->nextIterationEntry);
    mb.addField("nextEntryInBucket", &self->nextEntryInBucket);
  }
  
  #ifdef HERMESVM_SERIALIZE
  HashMapEntry::HashMapEntry(Deserializer &d)
      : GCCell(&d.getRuntime()->getHeap(), &vt) {
    d.readHermesValue(&key);
    d.readHermesValue(&value);
    d.readRelocation(&prevIterationEntry, RelocationKind::GCPointer);
    d.readRelocation(&nextIterationEntry, RelocationKind::GCPointer);
    d.readRelocation(&nextEntryInBucket, RelocationKind::GCPointer);
  }
  
  void HashMapEntrySerialize(Serializer &s, const GCCell *cell) {
    auto *self = vmcast<const HashMapEntry>(cell);
    s.writeHermesValue(self->key);
    s.writeHermesValue(self->value);
    s.writeRelocation(self->prevIterationEntry.get(s.getRuntime()));
    s.writeRelocation(self->nextIterationEntry.get(s.getRuntime()));
    s.writeRelocation(self->nextEntryInBucket.get(s.getRuntime()));
    s.endObject(cell);
  }
  
  void HashMapEntryDeserialize(Deserializer &d, CellKind kind) {
    assert(kind == CellKind::HashMapEntryKind && "Expected HashMapEntry");
    void *mem = d.getRuntime()->alloc(sizeof(HashMapEntry));
    auto *cell = new (mem) HashMapEntry(d);
    d.endObject(cell);
  }
  #endif
  
  CallResult<HermesValue> HashMapEntry::create(Runtime *runtime) {
    void *mem = runtime->alloc(sizeof(HashMapEntry));
    return HermesValue::encodeObjectValue(new (mem) HashMapEntry(runtime));
  }
  
  //===----------------------------------------------------------------------===//
  // class OrderedHashMap
  
  VTable OrderedHashMap::vt{CellKind::OrderedHashMapKind, sizeof(OrderedHashMap)};
  
  void OrderedHashMapBuildMeta(const GCCell *cell, Metadata::Builder &mb) {
    const auto *self = static_cast<const OrderedHashMap *>(cell);
    mb.addField("hashTable", &self->hashTable_);
    mb.addField("firstIterationEntry", &self->firstIterationEntry_);
    mb.addField("lastIterationEntry", &self->lastIterationEntry_);
  }
  
  #ifdef HERMESVM_SERIALIZE
  OrderedHashMap::OrderedHashMap(Deserializer &d)
      : GCCell(&d.getRuntime()->getHeap(), &vt) {
    if (d.readInt<uint8_t>()) {
      hashTable_.set(
          d.getRuntime(),
          ArrayStorage::deserializeArrayStorage(d),
          &d.getRuntime()->getHeap());
    }
  
    d.readRelocation(&firstIterationEntry_, RelocationKind::GCPointer);
    d.readRelocation(&lastIterationEntry_, RelocationKind::GCPointer);
    capacity_ = d.readInt<uint32_t>();
    size_ = d.readInt<uint32_t>();
  }
  
  void OrderedHashMapSerialize(Serializer &s, const GCCell *cell) {
    auto *self = vmcast<const OrderedHashMap>(cell);
    // If we have an ArrayStorage, it doesn't store any native pointers. Serialize
    // it here.
    bool hasArray = (bool)self->hashTable_;
    s.writeInt<uint8_t>(hasArray);
    if (hasArray) {
      ArrayStorage::serializeArrayStorage(
          s, self->hashTable_.get(s.getRuntime()));
    }
  
    s.writeRelocation(self->firstIterationEntry_.get(s.getRuntime()));
    s.writeRelocation(self->lastIterationEntry_.get(s.getRuntime()));
    s.writeInt<uint32_t>(self->capacity_);
    s.writeInt<uint32_t>(self->size_);
  
    s.endObject(cell);
  }
  
  void OrderedHashMapDeserialize(Deserializer &d, CellKind kind) {
    assert(kind == CellKind::OrderedHashMapKind && "ExpectedOrderedHashMap");
    void *mem = d.getRuntime()->alloc(sizeof(OrderedHashMap));
    auto *cell = new (mem) OrderedHashMap(d);
  
    d.endObject(cell);
  }
  #endif
  
  OrderedHashMap::OrderedHashMap(
      Runtime *runtime,
      Handle<ArrayStorage> hashTableStorage)
      : GCCell(&runtime->getHeap(), &vt),
        hashTable_(runtime, hashTableStorage.get(), &runtime->getHeap()) {}
  
  CallResult<HermesValue> OrderedHashMap::create(Runtime *runtime) {
    auto arrRes =
        ArrayStorage::create(runtime, INITIAL_CAPACITY, INITIAL_CAPACITY);
    if (LLVM_UNLIKELY(arrRes == ExecutionStatus::EXCEPTION)) {
      return ExecutionStatus::EXCEPTION;
    }
    auto hashTableStorage = runtime->makeHandle<ArrayStorage>(*arrRes);
  
    void *mem = runtime->alloc(sizeof(OrderedHashMap));
    return HermesValue::encodeObjectValue(
        new (mem) OrderedHashMap(runtime, hashTableStorage));
  }
  
  void OrderedHashMap::removeLinkedListNode(
      Runtime *runtime,
      HashMapEntry *entry,
      GC *gc) {
    assert(
        entry != lastIterationEntry_.get(runtime) &&
        "Cannot remove the last entry");
    if (entry->prevIterationEntry) {
      entry->prevIterationEntry.get(runtime)->nextIterationEntry.set(
          runtime, entry->nextIterationEntry, gc);
    }
    if (entry->nextIterationEntry) {
      entry->nextIterationEntry.get(runtime)->prevIterationEntry.set(
          runtime, entry->prevIterationEntry, gc);
    }
    if (entry == firstIterationEntry_.get(runtime)) {
      firstIterationEntry_.set(runtime, entry->nextIterationEntry, gc);
    }
    entry->prevIterationEntry = nullptr;
  }
  
  HashMapEntry *OrderedHashMap::lookupInBucket(
      Runtime *runtime,
      uint32_t bucket,
      HermesValue key) {
    assert(
        hashTable_.get(runtime)->size() == capacity_ && "Inconsistent capacity");
    auto *entry = dyn_vmcast<HashMapEntry>(hashTable_.get(runtime)->at(bucket));
    while (entry && !isSameValueZero(entry->key, key)) {
      entry = entry->nextEntryInBucket.get(runtime);
    }
    return entry;
  }
  
  ExecutionStatus OrderedHashMap::rehashIfNecessary(
      Handle<OrderedHashMap> self,
      Runtime *runtime) {
    uint32_t newCapacity = self->capacity_;
    // NOTE: we have ensured that self->capacity_ * 4 never overflows uint32_t by
    // setting MAX_CAPACITY to the apropriate value. self->size_ is always <=
    // self->capacity_, so this applies to self->size_ as well.
    static_assert(
        MAX_CAPACITY < UINT32_MAX / 4,
        "Avoid overflow checks on multiplying capacity by 4");
    if (self->size_ * 4 > self->capacity_ * 3) {
      // Load factor is more than 0.75, need to increase the capacity.
      newCapacity = self->capacity_ * 2;
      if (LLVM_UNLIKELY(newCapacity > MAX_CAPACITY)) {
        // We maintain the invariant that the capacity_ is a power of two.
        // Therefore, if doubling would exceed the max, we revert to the
        // previous value.  (Assert the invariant to make it clear.)
        assert(
            (self->capacity_ & (self->capacity_ - 1)) == 0 &&
            "capacity_ must be power of 2");
        newCapacity = self->capacity_;
      }
    } else if (
        self->size_ * 4 < self->capacity_ && self->capacity_ > INITIAL_CAPACITY) {
      // Load factor is less than 0.25, and we are not at initial cap.
      newCapacity = self->capacity_ / 2;
    }
    if (newCapacity == self->capacity_) {
      // No need to rehash.
      return ExecutionStatus::RETURNED;
    }
    assert(
        self->size_ && self->firstIterationEntry_ && self->lastIterationEntry_ &&
        "We should never be rehashing when there are no elements");
  
    // Set new capacity first to update the hash function.
    self->capacity_ = newCapacity;
  
    // Create a new hash table.
    auto arrRes = ArrayStorage::create(runtime, newCapacity, newCapacity);
    if (LLVM_UNLIKELY(arrRes == ExecutionStatus::EXCEPTION)) {
      return ExecutionStatus::EXCEPTION;
    }
    auto newHashTable = runtime->makeHandle<ArrayStorage>(*arrRes);
  
    // Now re-add all entries to the hash table.
    MutableHandle<HashMapEntry> entry{runtime};
    MutableHandle<HashMapEntry> oldNextInBucket{runtime};
    MutableHandle<> keyHandle{runtime};
    GCScopeMarkerRAII marker{runtime};
    for (unsigned i = 0, len = self->hashTable_.get(runtime)->size(); i < len;
         ++i) {
      entry = dyn_vmcast<HashMapEntry>(self->hashTable_.get(runtime)->at(i));
      while (entry) {
        marker.flush();
        keyHandle = entry->key;
        uint32_t bucket = hashToBucket(self, runtime, keyHandle);
        oldNextInBucket = entry->nextEntryInBucket.get(runtime);
        if (newHashTable->at(bucket).isEmpty()) {
          // Empty bucket.
          entry->nextEntryInBucket = nullptr;
        } else {
          // There are already a bucket head.
          entry->nextEntryInBucket.set(
              runtime,
              vmcast<HashMapEntry>(newHashTable->at(bucket)),
              &runtime->getHeap());
        }
        // Update bucket head to the new entry.
        newHashTable->at(bucket).set(entry.getHermesValue(), &runtime->getHeap());
  
        entry = *oldNextInBucket;
      }
    }
  
    self->hashTable_.set(runtime, newHashTable.get(), &runtime->getHeap());
    assert(
        self->hashTable_.get(runtime)->size() == self->capacity_ &&
        "Inconsistent capacity");
    return ExecutionStatus::RETURNED;
  }
  
  bool OrderedHashMap::has(
      Handle<OrderedHashMap> self,
      Runtime *runtime,
      Handle<> key) {
    auto bucket = hashToBucket(self, runtime, key);
    return self->lookupInBucket(runtime, bucket, key.getHermesValue());
  }
  
  HashMapEntry *OrderedHashMap::find(
      Handle<OrderedHashMap> self,
      Runtime *runtime,
      Handle<> key) {
    auto bucket = hashToBucket(self, runtime, key);
    return self->lookupInBucket(runtime, bucket, key.getHermesValue());
  }
  
  HermesValue OrderedHashMap::get(
      Handle<OrderedHashMap> self,
      Runtime *runtime,
      Handle<> key) {
    auto *entry = find(self, runtime, key);
    if (!entry) {
      return HermesValue::encodeUndefinedValue();
    }
    return entry->value;
  }
  
  ExecutionStatus OrderedHashMap::insert(
      Handle<OrderedHashMap> self,
      Runtime *runtime,
      Handle<> key,
      Handle<> value) {
    uint32_t bucket = hashToBucket(self, runtime, key);
    if (auto *entry =
            self->lookupInBucket(runtime, bucket, key.getHermesValue())) {
      // Element already exists, update value and return.
      entry->value.set(value.get(), &runtime->getHeap());
      return ExecutionStatus::RETURNED;
    }
    // Create a new entry, set the key and value.
    auto crtRes = HashMapEntry::create(runtime);
    if (LLVM_UNLIKELY(crtRes == ExecutionStatus::EXCEPTION)) {
      return ExecutionStatus::EXCEPTION;
    }
    auto newMapEntry = runtime->makeHandle<HashMapEntry>(*crtRes);
    newMapEntry->key.set(key.get(), &runtime->getHeap());
    newMapEntry->value.set(value.get(), &runtime->getHeap());
    auto *curBucketFront =
        dyn_vmcast<HashMapEntry>(self->hashTable_.get(runtime)->at(bucket));
    if (curBucketFront) {
      // If the bucket we are inserting to is not empty, we maintain the
      // linked list properly.
      newMapEntry->nextEntryInBucket.set(
          runtime, curBucketFront, &runtime->getHeap());
    }
    // Set the newly inserted entry as the front of this bucket chain.
    self->hashTable_.get(runtime)->at(bucket).set(
        newMapEntry.getHermesValue(), &runtime->getHeap());
  
    if (!self->firstIterationEntry_) {
      // If we are inserting the first ever element, update
      // first iteration entry pointer.
      self->firstIterationEntry_.set(
          runtime, newMapEntry.get(), &runtime->getHeap());
      self->lastIterationEntry_.set(
          runtime, newMapEntry.get(), &runtime->getHeap());
    } else {
      // Connect the new entry with the last entry.
      self->lastIterationEntry_.get(runtime)->nextIterationEntry.set(
          runtime, newMapEntry.get(), &runtime->getHeap());
      newMapEntry->prevIterationEntry.set(
          runtime, self->lastIterationEntry_, &runtime->getHeap());
  
      HashMapEntry *previousLastEntry = self->lastIterationEntry_.get(runtime);
      self->lastIterationEntry_.set(
          runtime, newMapEntry.get(), &runtime->getHeap());
  
      if (previousLastEntry && previousLastEntry->isDeleted()) {
        // If the last entry was a deleted entry, we no longer need to keep it.
        self->removeLinkedListNode(
            runtime, previousLastEntry, &runtime->getHeap());
      }
    }
  
    self->size_++;
    return self->rehashIfNecessary(self, runtime);
  }
  
  bool OrderedHashMap::erase(
      Handle<OrderedHashMap> self,
      Runtime *runtime,
      Handle<> key) {
    uint32_t bucket = hashToBucket(self, runtime, key);
    HashMapEntry *prevEntry = nullptr;
    auto *entry =
        dyn_vmcast<HashMapEntry>(self->hashTable_.get(runtime)->at(bucket));
    while (entry && !isSameValueZero(entry->key, key.getHermesValue())) {
      prevEntry = entry;
      entry = entry->nextEntryInBucket.get(runtime);
    }
    if (!entry) {
      // Element does not exist.
      return false;
    }
  
    if (prevEntry) {
      // The entry we are deleting has a previous entry, update the link.
      prevEntry->nextEntryInBucket.set(
          runtime, entry->nextEntryInBucket, &runtime->getHeap());
    } else {
      // The entry we are erasing is the front entry in the bucket, we need
      // to update the bucket head to the next entry in the bucket, if not
      // any, set to empty value.
      self->hashTable_.get(runtime)->at(bucket).set(
          entry->nextEntryInBucket ? HermesValue::encodeObjectValue(
                                         entry->nextEntryInBucket.get(runtime))
                                   : HermesValue::encodeEmptyValue(),
          &runtime->getHeap());
    }
  
    entry->markDeleted();
    self->size_--;
  
    // Now delete the entry from the iteration linked list.
    // If we are deleting the last entry, don't remove it from the list yet.
    // This will ensure that if any iterator out there is currently pointing to
    // this entry, it will be able to follow on if we add new entries in the
    // future.
    if (entry != self->lastIterationEntry_.get(runtime)) {
      self->removeLinkedListNode(runtime, entry, &runtime->getHeap());
    }
  
    self->rehashIfNecessary(self, runtime);
  
    return true;
  }
  
  HashMapEntry *OrderedHashMap::iteratorNext(
      Runtime *runtime,
      HashMapEntry *entry) const {
    if (entry == nullptr) {
      // Starting a new iteration from the first entry.
      entry = firstIterationEntry_.get(runtime);
    } else {
      // Advance to the next entry.
      entry = entry->nextIterationEntry.get(runtime);
    }
  
    // Make sure the entry we returned (if not nullptr) must not be deleted.
    while (entry && entry->isDeleted()) {
      entry = entry->nextIterationEntry.get(runtime);
    }
    return entry;
  }
  
  void OrderedHashMap::clear(Runtime *runtime) {
    if (!firstIterationEntry_) {
      // Empty set.
      return;
    }
  
    // Clear the hash table.
    for (unsigned i = 0; i < capacity_; ++i) {
      auto entry = dyn_vmcast<HashMapEntry>(hashTable_.get(runtime)->at(i));
      // Delete every element reachable from the hash table.
      while (entry) {
        entry->markDeleted();
        entry = entry->nextEntryInBucket.get(runtime);
      }
      // Clear every element in the hash table.
      hashTable_.get(runtime)->at(i).setNonPtr(HermesValue::encodeEmptyValue());
    }
    // Resize the hash table to the initial size.
    ArrayStorage::resizeWithinCapacity(
        createPseudoHandle(hashTable_.get(runtime)), runtime, INITIAL_CAPACITY);
    capacity_ = INITIAL_CAPACITY;
  
    // After clearing, we will still keep the last deleted entry
    // in case there is an iterator out there
    // pointing to the middle of the iteration chain. We need it to be
    // able to merge back eventually.
    firstIterationEntry_.set(runtime, lastIterationEntry_, &runtime->getHeap());
    firstIterationEntry_.get(runtime)->prevIterationEntry = nullptr;
    size_ = 0;
  }
  
  } // namespace vm
  } // namespace hermes
  