OpenHarmony-v5.0-Beta1/s

// Copyright 2021 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.

// Only including the -inl.h file directly makes the linter complain.
#include "src/objects/swiss-name-dictionary.h"

#include "src/heap/heap-inl.h"
#include "src/objects/swiss-name-dictionary-inl.h"

namespace v8 {
namespace internal {

// static
Handle<SwissNameDictionary> SwissNameDictionary::DeleteEntry(
    Isolate* isolate, Handle<SwissNameDictionary> table, InternalIndex entry) {
  // GetCtrl() does the bounds check.
  DCHECK(IsFull(table->GetCtrl(entry.as_int())));

  int i = entry.as_int();

  table->SetCtrl(i, Ctrl::kDeleted);
  table->ClearDataTableEntry(isolate, i);
  // We leave the PropertyDetails unchanged because they are not relevant for
  // GC.

  int nof = table->NumberOfElements();
  table->SetNumberOfElements(nof - 1);
  int nod = table->NumberOfDeletedElements();
  table->SetNumberOfDeletedElements(nod + 1);

  // TODO(v8:11388) Abseil's flat_hash_map doesn't shrink on deletion, but may
  // decide on addition to do an in-place rehash to remove deleted elements. We
  // shrink on deletion here to follow what NameDictionary and
  // OrderedNameDictionary do. We should investigate which approach works
  // better.
  return Shrink(isolate, table);
}

// static
template <typename IsolateT>
Handle<SwissNameDictionary> SwissNameDictionary::Rehash(
    IsolateT* isolate, Handle<SwissNameDictionary> table, int new_capacity) {
  DCHECK(IsValidCapacity(new_capacity));
  DCHECK_LE(table->NumberOfElements(), MaxUsableCapacity(new_capacity));
  ReadOnlyRoots roots(isolate);

  Handle<SwissNameDictionary> new_table =
      isolate->factory()->NewSwissNameDictionaryWithCapacity(
          new_capacity, Heap::InYoungGeneration(*table) ? AllocationType::kYoung
                                                        : AllocationType::kOld);

  DisallowHeapAllocation no_gc;

  int new_enum_index = 0;
  new_table->SetNumberOfElements(table->NumberOfElements());
  for (int enum_index = 0; enum_index < table->UsedCapacity(); ++enum_index) {
    int entry = table->EntryForEnumerationIndex(enum_index);

    Object key;

    if (table->ToKey(roots, entry, &key)) {
      Object value = table->ValueAtRaw(entry);
      PropertyDetails details = table->DetailsAt(entry);

      int new_entry = new_table->AddInternal(Name::cast(key), value, details);

      // TODO(v8::11388) Investigate ways of hoisting the branching needed to
      // select the correct meta table entry size (based on the capacity of the
      // table) out of the loop.
      new_table->SetEntryForEnumerationIndex(new_enum_index, new_entry);
      ++new_enum_index;
    }
  }

  new_table->SetHash(table->Hash());
  return new_table;
}

bool SwissNameDictionary::EqualsForTesting(SwissNameDictionary other) {
  if (Capacity() != other.Capacity() ||
      NumberOfElements() != other.NumberOfElements() ||
      NumberOfDeletedElements() != other.NumberOfDeletedElements() ||
      Hash() != other.Hash()) {
    return false;
  }

  for (int i = 0; i < Capacity() + kGroupWidth; i++) {
    if (CtrlTable()[i] != other.CtrlTable()[i]) {
      return false;
    }
  }
  for (int i = 0; i < Capacity(); i++) {
    if (KeyAt(i) != other.KeyAt(i) || ValueAtRaw(i) != other.ValueAtRaw(i)) {
      return false;
    }
    if (IsFull(GetCtrl(i))) {
      if (DetailsAt(i) != other.DetailsAt(i)) return false;
    }
  }
  for (int i = 0; i < UsedCapacity(); i++) {
    if (EntryForEnumerationIndex(i) != other.EntryForEnumerationIndex(i)) {
      return false;
    }
  }
  return true;
}

// static
Handle<SwissNameDictionary> SwissNameDictionary::ShallowCopy(
    Isolate* isolate, Handle<SwissNameDictionary> table) {
  // TODO(v8:11388) Consider doing some cleanup during copying: For example, we
  // could turn kDeleted into kEmpty in certain situations. But this would
  // require tidying up the enumeration table in a similar fashion as would be
  // required when trying to re-use deleted entries.

  if (table->Capacity() == 0) {
    return table;
  }

  int capacity = table->Capacity();
  int used_capacity = table->UsedCapacity();

  Handle<SwissNameDictionary> new_table =
      isolate->factory()->NewSwissNameDictionaryWithCapacity(
          capacity, Heap::InYoungGeneration(*table) ? AllocationType::kYoung
                                                    : AllocationType::kOld);

  new_table->SetHash(table->Hash());

  DisallowGarbageCollection no_gc;
  WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc);

  if (mode == WriteBarrierMode::SKIP_WRITE_BARRIER) {
    // Copy data table and ctrl table, which are stored next to each other.
    void* original_start =
        reinterpret_cast<void*>(table->field_address(DataTableStartOffset()));
    void* new_table_start = reinterpret_cast<void*>(
        new_table->field_address(DataTableStartOffset()));
    size_t bytes_to_copy = DataTableSize(capacity) + CtrlTableSize(capacity);
    DCHECK(DataTableEndOffset(capacity) == CtrlTableStartOffset(capacity));
    MemCopy(new_table_start, original_start, bytes_to_copy);
  } else {
    DCHECK_EQ(UPDATE_WRITE_BARRIER, mode);

    // We may have to trigger write barriers when copying the data table.
    for (int i = 0; i < capacity; ++i) {
      Object key = table->KeyAt(i);
      Object value = table->ValueAtRaw(i);

      // Cannot use SetKey/ValueAtPut because they don't accept the hole as data
      // to store.
      new_table->StoreToDataTable(i, kDataTableKeyEntryIndex, key);
      new_table->StoreToDataTable(i, kDataTableValueEntryIndex, value);
    }

    void* original_ctrl_table = table->CtrlTable();
    void* new_ctrl_table = new_table->CtrlTable();
    MemCopy(new_ctrl_table, original_ctrl_table, CtrlTableSize(capacity));
  }

  // PropertyDetails table may contain uninitialized data for unused slots.
  for (int i = 0; i < capacity; ++i) {
    if (IsFull(table->GetCtrl(i))) {
      new_table->DetailsAtPut(i, table->DetailsAt(i));
    }
  }

  // Meta table is only initialized for the first 2 + UsedCapacity() entries,
  // where size of each entry depends on table capacity.
  int size_per_meta_table_entry = MetaTableSizePerEntryFor(capacity);
  int meta_table_used_bytes = (2 + used_capacity) * size_per_meta_table_entry;
  new_table->meta_table().copy_in(0, table->meta_table().GetDataStartAddress(),
                                  meta_table_used_bytes);

  return new_table;
}

// static
Handle<SwissNameDictionary> SwissNameDictionary::Shrink(
    Isolate* isolate, Handle<SwissNameDictionary> table) {
  // TODO(v8:11388) We're using the same logic to decide whether or not to
  // shrink as OrderedNameDictionary and NameDictionary here. We should compare
  // this with the logic used by Abseil's flat_hash_map, which has a heuristic
  // for triggering an (in-place) rehash on addition, but never shrinks the
  // table. Abseil's heuristic doesn't take the numbere of deleted elements into
  // account, because it doesn't track that.

  int nof = table->NumberOfElements();
  int capacity = table->Capacity();
  if (nof >= (capacity >> 2)) return table;
  int new_capacity = std::max(capacity / 2, kInitialCapacity);
  return Rehash(isolate, table, new_capacity);
}

// TODO(v8::11388) Copying all data into a std::vector and then re-adding into
// the table doesn't seem like a good algorithm. Abseil's Swiss Tables come with
// a clever algorithm for re-hashing in place: It first changes the control
// table, effectively changing the roles of full, empty and deleted buckets. It
// then moves each entry to its new bucket by swapping entries (see
// drop_deletes_without_resize in Abseil's raw_hash_set.h). This algorithm could
// generally adapted to work on our insertion order preserving implementation,
// too. However, it would require a mapping from hash table buckets back to
// enumeration indices. This could either be be created in this function
// (requiring a vector with Capacity() entries and a separate pass over the
// enumeration table) or by creating this backwards mapping ahead of time and
// storing it somewhere in the main table or the meta table, for those
// SwissNameDictionaries that we know will be in-place rehashed, most notably
// those stored in the snapshot.
template <typename IsolateT>
void SwissNameDictionary::Rehash(IsolateT* isolate) {
  DisallowHeapAllocation no_gc;

  struct Entry {
    Name key;
    Object value;
    PropertyDetails details;
  };

  if (Capacity() == 0) return;

  Entry dummy{Name(), Object(), PropertyDetails::Empty()};
  std::vector<Entry> data(NumberOfElements(), dummy);

  ReadOnlyRoots roots(isolate);
  int data_index = 0;
  for (int enum_index = 0; enum_index < UsedCapacity(); ++enum_index) {
    int entry = EntryForEnumerationIndex(enum_index);
    Object key;
    if (!ToKey(roots, entry, &key)) continue;

    data[data_index++] =
        Entry{Name::cast(key), ValueAtRaw(entry), DetailsAt(entry)};
  }

  Initialize(isolate, meta_table(), Capacity());

  int new_enum_index = 0;
  SetNumberOfElements(static_cast<int>(data.size()));
  for (Entry& e : data) {
    int new_entry = AddInternal(e.key, e.value, e.details);

    // TODO(v8::11388) Investigate ways of hoisting the branching needed to
    // select the correct meta table entry size (based on the capacity of the
    // table) out of the loop.
    SetEntryForEnumerationIndex(new_enum_index, new_entry);
    ++new_enum_index;
  }
}

// TODO(emrich,v8:11388): This is almost an identical copy of
// HashTable<..>::NumberOfEnumerableProperties. Consolidate both versions
// elsewhere (e.g., hash-table-utils)?
int SwissNameDictionary::NumberOfEnumerableProperties() {
  ReadOnlyRoots roots = this->GetReadOnlyRoots();
  int result = 0;
  for (InternalIndex i : this->IterateEntries()) {
    Object k;
    if (!this->ToKey(roots, i, &k)) continue;
    if (k.FilterKey(ENUMERABLE_STRINGS)) continue;
    PropertyDetails details = this->DetailsAt(i);
    PropertyAttributes attr = details.attributes();
    if ((attr & ONLY_ENUMERABLE) == 0) result++;
  }
  return result;
}

// TODO(emrich, v8:11388): This is almost an identical copy of
// Dictionary<..>::SlowReverseLookup. Consolidate both versions elsewhere (e.g.,
// hash-table-utils)?
Object SwissNameDictionary::SlowReverseLookup(Isolate* isolate, Object value) {
  ReadOnlyRoots roots(isolate);
  for (InternalIndex i : IterateEntries()) {
    Object k;
    if (!ToKey(roots, i, &k)) continue;
    Object e = this->ValueAt(i);
    if (e == value) return k;
  }
  return roots.undefined_value();
}

// The largest value we ever have to store in the enumeration table is
// Capacity() - 1. The largest value we ever have to store for the present or
// deleted element count is MaxUsableCapacity(Capacity()). All data in the
// meta table is unsigned. Using this, we verify the values of the constants
// |kMax1ByteMetaTableCapacity| and |kMax2ByteMetaTableCapacity|.
STATIC_ASSERT(SwissNameDictionary::kMax1ByteMetaTableCapacity - 1 <=
              std::numeric_limits<uint8_t>::max());
STATIC_ASSERT(SwissNameDictionary::MaxUsableCapacity(
                  SwissNameDictionary::kMax1ByteMetaTableCapacity) <=
              std::numeric_limits<uint8_t>::max());
STATIC_ASSERT(SwissNameDictionary::kMax2ByteMetaTableCapacity - 1 <=
              std::numeric_limits<uint16_t>::max());
STATIC_ASSERT(SwissNameDictionary::MaxUsableCapacity(
                  SwissNameDictionary::kMax2ByteMetaTableCapacity) <=
              std::numeric_limits<uint16_t>::max());

template V8_EXPORT_PRIVATE void SwissNameDictionary::Initialize(
    Isolate* isolate, ByteArray meta_table, int capacity);
template V8_EXPORT_PRIVATE void SwissNameDictionary::Initialize(
    LocalIsolate* isolate, ByteArray meta_table, int capacity);

template V8_EXPORT_PRIVATE Handle<SwissNameDictionary>
SwissNameDictionary::Rehash(LocalIsolate* isolate,
                            Handle<SwissNameDictionary> table,
                            int new_capacity);
template V8_EXPORT_PRIVATE Handle<SwissNameDictionary>
SwissNameDictionary::Rehash(Isolate* isolate, Handle<SwissNameDictionary> table,
                            int new_capacity);

template V8_EXPORT_PRIVATE void SwissNameDictionary::Rehash(
    LocalIsolate* isolate);
template V8_EXPORT_PRIVATE void SwissNameDictionary::Rehash(Isolate* isolate);

constexpr int SwissNameDictionary::kInitialCapacity;
constexpr int SwissNameDictionary::kGroupWidth;

}  // namespace internal
}  // namespace v8