path: root/deps/v8/src/objects/ordered-hash-table.h

// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
#define V8_OBJECTS_ORDERED_HASH_TABLE_H_

#include "src/globals.h"
#include "src/objects/fixed-array.h"

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

// Non-templatized base class for {OrderedHashTable}s.
// TODO(hash): Unify this with the HashTableBase above.
class OrderedHashTableBase : public FixedArray {
 public:
  static const int kNotFound = -1;
  static const int kMinCapacity = 4;

  static const int kNumberOfElementsIndex = 0;
  // The next table is stored at the same index as the nof elements.
  static const int kNextTableIndex = kNumberOfElementsIndex;
  static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
  static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1;
  static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1;
  static const int kRemovedHolesIndex = kHashTableStartIndex;

  static constexpr const int kNumberOfElementsOffset =
      FixedArray::OffsetOfElementAt(kNumberOfElementsIndex);
  static constexpr const int kNextTableOffset =
      FixedArray::OffsetOfElementAt(kNextTableIndex);
  static constexpr const int kNumberOfDeletedElementsOffset =
      FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex);
  static constexpr const int kNumberOfBucketsOffset =
      FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex);
  static constexpr const int kHashTableStartOffset =
      FixedArray::OffsetOfElementAt(kHashTableStartIndex);

  static const int kLoadFactor = 2;

  // NumberOfDeletedElements is set to kClearedTableSentinel when
  // the table is cleared, which allows iterator transitions to
  // optimize that case.
  static const int kClearedTableSentinel = -1;
};

// OrderedHashTable is a HashTable with Object keys that preserves
// insertion order. There are Map and Set interfaces (OrderedHashMap
// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
//
// Only Object* keys are supported, with Object::SameValueZero() used as the
// equality operator and Object::GetHash() for the hash function.
//
// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
// Originally attributed to Tyler Close.
//
// Memory layout:
//   [0]: element count
//   [1]: deleted element count
//   [2]: bucket count
//   [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an
//                            offset into the data table (see below) where the
//                            first item in this bucket is stored.
//   [3 + NumberOfBuckets()..length]: "data table", an array of length
//                            Capacity() * kEntrySize, where the first entrysize
//                            items are handled by the derived class and the
//                            item at kChainOffset is another entry into the
//                            data table indicating the next entry in this hash
//                            bucket.
//
// When we transition the table to a new version we obsolete it and reuse parts
// of the memory to store information how to transition an iterator to the new
// table:
//
// Memory layout for obsolete table:
//   [0]: bucket count
//   [1]: Next newer table
//   [2]: Number of removed holes or -1 when the table was cleared.
//   [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes.
//   [3 + NumberOfRemovedHoles()..length]: Not used
//
template <class Derived, int entrysize>
class OrderedHashTable : public OrderedHashTableBase {
 public:
  // Returns an OrderedHashTable with a capacity of at least |capacity|.
  static Handle<Derived> Allocate(Isolate* isolate, int capacity,
                                  PretenureFlag pretenure = NOT_TENURED);

  // Returns an OrderedHashTable (possibly |table|) with enough space
  // to add at least one new element.
  static Handle<Derived> EnsureGrowable(Handle<Derived> table);

  // Returns an OrderedHashTable (possibly |table|) that's shrunken
  // if possible.
  static Handle<Derived> Shrink(Handle<Derived> table);

  // Returns a new empty OrderedHashTable and records the clearing so that
  // existing iterators can be updated.
  static Handle<Derived> Clear(Handle<Derived> table);

  // Returns true if the OrderedHashTable contains the key
  static bool HasKey(Isolate* isolate, Derived* table, Object* key);

  // Returns a true value if the OrderedHashTable contains the key and
  // the key has been deleted. This does not shrink the table.
  static bool Delete(Isolate* isolate, Derived* table, Object* key);

  int NumberOfElements() const {
    return Smi::ToInt(get(kNumberOfElementsIndex));
  }

  int NumberOfDeletedElements() const {
    return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
  }

  // Returns the number of contiguous entries in the data table, starting at 0,
  // that either are real entries or have been deleted.
  int UsedCapacity() const {
    return NumberOfElements() + NumberOfDeletedElements();
  }

  int NumberOfBuckets() const { return Smi::ToInt(get(kNumberOfBucketsIndex)); }

  // Returns an index into |this| for the given entry.
  int EntryToIndex(int entry) {
    return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
  }

  int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }

  int HashToEntry(int hash) {
    int bucket = HashToBucket(hash);
    Object* entry = this->get(kHashTableStartIndex + bucket);
    return Smi::ToInt(entry);
  }

  int KeyToFirstEntry(Isolate* isolate, Object* key) {
    // This special cases for Smi, so that we avoid the HandleScope
    // creation below.
    if (key->IsSmi()) {
      uint32_t hash = ComputeIntegerHash(Smi::ToInt(key));
      return HashToEntry(hash & Smi::kMaxValue);
    }
    HandleScope scope(isolate);
    Object* hash = key->GetHash();
    // If the object does not have an identity hash, it was never used as a key
    if (hash->IsUndefined(isolate)) return kNotFound;
    return HashToEntry(Smi::ToInt(hash));
  }

  int FindEntry(Isolate* isolate, Object* key) {
    int entry = KeyToFirstEntry(isolate, key);
    // Walk the chain in the bucket to find the key.
    while (entry != kNotFound) {
      Object* candidate_key = KeyAt(entry);
      if (candidate_key->SameValueZero(key)) break;
      entry = NextChainEntry(entry);
    }

    return entry;
  }

  int NextChainEntry(int entry) {
    Object* next_entry = get(EntryToIndex(entry) + kChainOffset);
    return Smi::ToInt(next_entry);
  }

  // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
  Object* KeyAt(int entry) {
    DCHECK_LT(entry, this->UsedCapacity());
    return get(EntryToIndex(entry));
  }

  bool IsObsolete() { return !get(kNextTableIndex)->IsSmi(); }

  // The next newer table. This is only valid if the table is obsolete.
  Derived* NextTable() { return Derived::cast(get(kNextTableIndex)); }

  // When the table is obsolete we store the indexes of the removed holes.
  int RemovedIndexAt(int index) {
    return Smi::ToInt(get(kRemovedHolesIndex + index));
  }

  static const int kEntrySize = entrysize + 1;
  static const int kChainOffset = entrysize;

  static const int kMaxCapacity =
      (FixedArray::kMaxLength - kHashTableStartIndex) /
      (1 + (kEntrySize * kLoadFactor));

 protected:
  static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);

  void SetNumberOfBuckets(int num) {
    set(kNumberOfBucketsIndex, Smi::FromInt(num));
  }

  void SetNumberOfElements(int num) {
    set(kNumberOfElementsIndex, Smi::FromInt(num));
  }

  void SetNumberOfDeletedElements(int num) {
    set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
  }

  // Returns the number elements that can fit into the allocated buffer.
  int Capacity() { return NumberOfBuckets() * kLoadFactor; }

  void SetNextTable(Derived* next_table) { set(kNextTableIndex, next_table); }

  void SetRemovedIndexAt(int index, int removed_index) {
    return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
  }
};

class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
 public:
  DECL_CAST(OrderedHashSet)

  static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table,
                                    Handle<Object> value);
  static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table,
                                               GetKeysConversion convert);
  static HeapObject* GetEmpty(Isolate* isolate);
  static inline int GetMapRootIndex();
};

class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
 public:
  DECL_CAST(OrderedHashMap)

  // Returns a value if the OrderedHashMap contains the key, otherwise
  // returns undefined.
  static Handle<OrderedHashMap> Add(Handle<OrderedHashMap> table,
                                    Handle<Object> key, Handle<Object> value);
  Object* ValueAt(int entry);

  static Object* GetHash(Isolate* isolate, Object* key);

  static HeapObject* GetEmpty(Isolate* isolate);
  static inline int GetMapRootIndex();

  static const int kValueOffset = 1;
};

// This is similar to the OrderedHashTable, except for the memory
// layout where we use byte instead of Smi. The max capacity of this
// is only 254, we transition to an OrderedHashTable beyond that
// limit.
//
// Each bucket and chain value is a byte long. The padding exists so
// that the DataTable entries start aligned. A bucket or chain value
// of 255 is used to denote an unknown entry.
//
// Memory layout: [ Header ]  [ Padding ] [ DataTable ] [ HashTable ] [ Chains ]
//
// The index are represented as bytes, on a 64 bit machine with
// kEntrySize = 1, capacity = 4 and entries = 2:
//
// [ Header ]  :
//    [0] : Number of elements
//    [1] : Number of deleted elements
//    [2] : Number of buckets
//
// [ Padding ] :
//    [3 .. 7] : Padding
//
// [ DataTable ] :
//    [8  .. 15] : Entry 1
//    [16 .. 23] : Entry 2
//    [24 .. 31] : empty
//    [32 .. 39] : empty
//
// [ HashTable ] :
//    [40] : First chain-link for bucket 1
//    [41] : empty
//
// [ Chains ] :
//    [42] : Next chain link for bucket 1
//    [43] : empty
//    [44] : empty
//    [45] : empty
//
template <class Derived>
class SmallOrderedHashTable : public HeapObject {
 public:
  // Offset points to a relative location in the table
  typedef int Offset;

  // ByteIndex points to a index in the table that needs to be
  // converted to an Offset.
  typedef int ByteIndex;

  void Initialize(Isolate* isolate, int capacity);

  static Handle<Derived> Allocate(Isolate* isolate, int capacity,
                                  PretenureFlag pretenure = NOT_TENURED);

  // Returns a true if the OrderedHashTable contains the key
  bool HasKey(Isolate* isolate, Handle<Object> key);

  // Returns a true value if the table contains the key and
  // the key has been deleted. This does not shrink the table.
  static bool Delete(Isolate* isolate, Derived* table, Object* key);

  // Returns an SmallOrderedHashTable (possibly |table|) with enough
  // space to add at least one new element.
  static Handle<Derived> Grow(Handle<Derived> table);

  static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);

  // Iterates only fields in the DataTable.
  class BodyDescriptor;

  // No weak fields.
  typedef BodyDescriptor BodyDescriptorWeak;

  // Returns total size in bytes required for a table of given
  // capacity.
  static int SizeFor(int capacity) {
    DCHECK_GE(capacity, kMinCapacity);
    DCHECK_LE(capacity, kMaxCapacity);

    int data_table_size = DataTableSizeFor(capacity);
    int hash_table_size = capacity / kLoadFactor;
    int chain_table_size = capacity;
    int total_size = kHeaderSize + kDataTableStartOffset + data_table_size +
                     hash_table_size + chain_table_size;

    return ((total_size + kPointerSize - 1) / kPointerSize) * kPointerSize;
  }

  // Returns the number elements that can fit into the allocated table.
  int Capacity() const {
    int capacity = NumberOfBuckets() * kLoadFactor;
    DCHECK_GE(capacity, kMinCapacity);
    DCHECK_LE(capacity, kMaxCapacity);

    return capacity;
  }

  // Returns the number elements that are present in the table.
  int NumberOfElements() const {
    int nof_elements = getByte(0, kNumberOfElementsByteIndex);
    DCHECK_LE(nof_elements, Capacity());

    return nof_elements;
  }

  int NumberOfDeletedElements() const {
    int nof_deleted_elements = getByte(0, kNumberOfDeletedElementsByteIndex);
    DCHECK_LE(nof_deleted_elements, Capacity());

    return nof_deleted_elements;
  }

  int NumberOfBuckets() const { return getByte(0, kNumberOfBucketsByteIndex); }

  DECL_VERIFIER(SmallOrderedHashTable)

  static const int kMinCapacity = 4;
  static const byte kNotFound = 0xFF;

  // We use the value 255 to indicate kNotFound for chain and bucket
  // values, which means that this value can't be used a valid
  // index.
  static const int kMaxCapacity = 254;
  STATIC_ASSERT(kMaxCapacity < kNotFound);

  // The load factor is used to derive the number of buckets from
  // capacity during Allocation. We also depend on this to calaculate
  // the capacity from number of buckets after allocation. If we
  // decide to change kLoadFactor to something other than 2, capacity
  // should be stored as another field of this object.
  static const int kLoadFactor = 2;

 protected:
  void SetDataEntry(int entry, int relative_index, Object* value);

  // TODO(gsathya): Calculate all the various possible values for this
  // at compile time since capacity can only be 4 different values.
  Offset GetBucketsStartOffset() const {
    int capacity = Capacity();
    int data_table_size = DataTableSizeFor(capacity);
    return kDataTableStartOffset + data_table_size;
  }

  Address GetHashTableStartAddress(int capacity) const {
    return FIELD_ADDR(
        this, kHeaderSize + kDataTableStartOffset + DataTableSizeFor(capacity));
  }

  void SetFirstEntry(int bucket, byte value) {
    DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
    setByte(GetBucketsStartOffset(), bucket, value);
  }

  int GetFirstEntry(int bucket) const {
    DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
    return getByte(GetBucketsStartOffset(), bucket);
  }

  // TODO(gsathya): Calculate all the various possible values for this
  // at compile time since capacity can only be 4 different values.
  Offset GetChainTableOffset() const {
    int nof_buckets = NumberOfBuckets();
    int capacity = nof_buckets * kLoadFactor;
    DCHECK_EQ(Capacity(), capacity);

    int data_table_size = DataTableSizeFor(capacity);
    int hash_table_size = nof_buckets;
    return kDataTableStartOffset + data_table_size + hash_table_size;
  }

  void SetNextEntry(int entry, int next_entry) {
    DCHECK_LT(static_cast<unsigned>(entry), Capacity());
    DCHECK_GE(static_cast<unsigned>(next_entry), 0);
    DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
    setByte(GetChainTableOffset(), entry, next_entry);
  }

  int GetNextEntry(int entry) const {
    DCHECK_LT(entry, Capacity());
    return getByte(GetChainTableOffset(), entry);
  }

  Object* GetDataEntry(int entry, int relative_index) {
    DCHECK_LT(entry, Capacity());
    DCHECK_LE(static_cast<unsigned>(relative_index), Derived::kEntrySize);
    Offset entry_offset = GetDataEntryOffset(entry, relative_index);
    return READ_FIELD(this, kHeaderSize + entry_offset);
  }

  Object* KeyAt(int entry) const {
    DCHECK_LT(entry, Capacity());
    Offset entry_offset = GetDataEntryOffset(entry, Derived::kKeyIndex);
    return READ_FIELD(this, kHeaderSize + entry_offset);
  }

  int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }

  int HashToFirstEntry(int hash) const {
    int bucket = HashToBucket(hash);
    int entry = GetFirstEntry(bucket);
    DCHECK(entry < Capacity() || entry == kNotFound);
    return entry;
  }

  void SetNumberOfBuckets(int num) {
    setByte(0, kNumberOfBucketsByteIndex, num);
  }

  void SetNumberOfElements(int num) {
    DCHECK_LE(static_cast<unsigned>(num), Capacity());
    setByte(0, kNumberOfElementsByteIndex, num);
  }

  void SetNumberOfDeletedElements(int num) {
    DCHECK_LE(static_cast<unsigned>(num), Capacity());
    setByte(0, kNumberOfDeletedElementsByteIndex, num);
  }

  int FindEntry(Isolate* isolate, Object* key) {
    DisallowHeapAllocation no_gc;
    Object* hash = key->GetHash();

    if (hash->IsUndefined(isolate)) return kNotFound;
    int entry = HashToFirstEntry(Smi::ToInt(hash));

    // Walk the chain in the bucket to find the key.
    while (entry != kNotFound) {
      Object* candidate_key = KeyAt(entry);
      if (candidate_key->SameValueZero(key)) return entry;
      entry = GetNextEntry(entry);
    }
    return kNotFound;
  }

  static const int kNumberOfElementsByteIndex = 0;
  static const int kNumberOfDeletedElementsByteIndex = 1;
  static const int kNumberOfBucketsByteIndex = 2;

  static const Offset kDataTableStartOffset = kPointerSize;
  static constexpr int DataTableSizeFor(int capacity) {
    return capacity * Derived::kEntrySize * kPointerSize;
  }

  // Our growth strategy involves doubling the capacity until we reach
  // kMaxCapacity, but since the kMaxCapacity is always less than 256,
  // we will never fully utilize this table. We special case for 256,
  // by changing the new capacity to be kMaxCapacity in
  // SmallOrderedHashTable::Grow.
  static const int kGrowthHack = 256;

  // This is used for accessing the non |DataTable| part of the
  // structure.
  byte getByte(Offset offset, ByteIndex index) const {
    DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset());
    return READ_BYTE_FIELD(this, kHeaderSize + offset + (index * kOneByteSize));
  }

  void setByte(Offset offset, ByteIndex index, byte value) {
    DCHECK(offset < kDataTableStartOffset || offset >= GetBucketsStartOffset());
    WRITE_BYTE_FIELD(this, kHeaderSize + offset + (index * kOneByteSize),
                     value);
  }

  Offset GetDataEntryOffset(int entry, int relative_index) const {
    DCHECK_LT(entry, Capacity());
    int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize;
    int offset_in_entry = relative_index * kPointerSize;
    return kDataTableStartOffset + offset_in_datatable + offset_in_entry;
  }

  int UsedCapacity() const {
    int used = NumberOfElements() + NumberOfDeletedElements();
    DCHECK_LE(used, Capacity());

    return used;
  }
};

class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
 public:
  DECL_CAST(SmallOrderedHashSet)

  DECL_PRINTER(SmallOrderedHashSet)

  static const int kKeyIndex = 0;
  static const int kEntrySize = 1;

  // Adds |value| to |table|, if the capacity isn't enough, a new
  // table is created. The original |table| is returned if there is
  // capacity to store |value| otherwise the new table is returned.
  static Handle<SmallOrderedHashSet> Add(Handle<SmallOrderedHashSet> table,
                                         Handle<Object> key);
};

class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
 public:
  DECL_CAST(SmallOrderedHashMap)

  DECL_PRINTER(SmallOrderedHashMap)

  static const int kKeyIndex = 0;
  static const int kValueIndex = 1;
  static const int kEntrySize = 2;

  // Adds |value| to |table|, if the capacity isn't enough, a new
  // table is created. The original |table| is returned if there is
  // capacity to store |value| otherwise the new table is returned.
  static Handle<SmallOrderedHashMap> Add(Handle<SmallOrderedHashMap> table,
                                         Handle<Object> key,
                                         Handle<Object> value);
};

class JSCollectionIterator : public JSObject {
 public:
  // [table]: the backing hash table mapping keys to values.
  DECL_ACCESSORS(table, Object)

  // [index]: The index into the data table.
  DECL_ACCESSORS(index, Object)

  // Dispatched behavior.
  DECL_PRINTER(JSCollectionIterator)

  static const int kTableOffset = JSObject::kHeaderSize;
  static const int kIndexOffset = kTableOffset + kPointerSize;
  static const int kSize = kIndexOffset + kPointerSize;

 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(JSCollectionIterator);
};

// OrderedHashTableIterator is an iterator that iterates over the keys and
// values of an OrderedHashTable.
//
// The iterator has a reference to the underlying OrderedHashTable data,
// [table], as well as the current [index] the iterator is at.
//
// When the OrderedHashTable is rehashed it adds a reference from the old table
// to the new table as well as storing enough data about the changes so that the
// iterator [index] can be adjusted accordingly.
//
// When the [Next] result from the iterator is requested, the iterator checks if
// there is a newer table that it needs to transition to.
template <class Derived, class TableType>
class OrderedHashTableIterator : public JSCollectionIterator {
 public:
  // Whether the iterator has more elements. This needs to be called before
  // calling |CurrentKey| and/or |CurrentValue|.
  bool HasMore();

  // Move the index forward one.
  void MoveNext() { set_index(Smi::FromInt(Smi::ToInt(index()) + 1)); }

  // Returns the current key of the iterator. This should only be called when
  // |HasMore| returns true.
  inline Object* CurrentKey();

 private:
  // Transitions the iterator to the non obsolete backing store. This is a NOP
  // if the [table] is not obsolete.
  void Transition();

  DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
};

}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_ORDERED_HASH_TABLE_H_