swiss-name-dictionary.h | Explore in Territory

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

#ifndef V8_OBJECTS_SWISS_NAME_DICTIONARY_H_
#define V8_OBJECTS_SWISS_NAME_DICTIONARY_H_

#include <cstdint>
#include <optional>

#include "src/base/export-template.h"
#include "src/common/globals.h"
#include "src/objects/fixed-array.h"
#include "src/objects/internal-index.h"
#include "src/objects/js-objects.h"
#include "src/objects/swiss-hash-table-helpers.h"
#include "src/roots/roots.h"

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

namespace v8::internal {

// A property backing store based on Swiss Tables/Abseil's flat_hash_map. The
// implementation is heavily based on Abseil's raw_hash_set.h.
//
// Memory layout (see below for detailed description of parts):
//   Prefix:                      [table type dependent part, can have 0 size]
//   Capacity:                    4 bytes, raw int32_t
//   Meta table pointer:          kTaggedSize bytes
//   Data table:                  2 * |capacity| * |kTaggedSize| bytes
//   Ctrl table:                  |capacity| + |kGroupWidth| uint8_t entries
//   PropertyDetails table:       |capacity| uint_8 entries
//
// Note that because of |kInitialCapacity| == 4 there is no need for padding.
//
// Description of parts directly contained in SwissNameDictionary allocation:
//   Prefix:
//     In case of SwissNameDictionary:
//       identity hash: 4 bytes, raw int32_t
//   Meta table pointer: kTaggedSize bytes.
//     See below for explanation of the meta table.
//   Data table:
//     For each logical bucket of the hash table, contains the corresponding key
//     and value.
//   Ctrl table:
//     The control table is used to implement a Swiss Table: Each byte is either
//     Ctrl::kEmpty, Ctrl::kDeleted, or in case of a bucket denoting a present
//     entry in the hash table, the 7 lowest bits of the key's hash. The first
//     |capacity| entries are the actual control table. The additional
//     |kGroupWidth| bytes contain a copy of the first min(capacity,
//     kGroupWidth) bytes of the table.
//   PropertyDetails table:
//     Each byte contains the PropertyDetails for the corresponding bucket of
//     the ctrl table. Entries may contain unitialized data if the corresponding
//     bucket hasn't been used before.
//
// Meta table:
//   The meta table (not to be confused with the control table used in any
//   Swiss Table design!) is a separate ByteArray. Here, the "X" in "uintX_t"
//   depends on the capacity of the swiss table. For capacities <= 256 we have X
//   = 8, for 256 < |capacity| <= 2^16 we have X = 16, and otherwise X = 32 (see
//   MetaTableSizePerEntryFor). It contais the following data:
//     Number of Entries: uintX_t.
//     Number of Deleted Entries: uintX_t.
//     Enumeration table: max_load_factor * Capacity() entries of type uintX_t:
//       The i-th entry in the enumeration table
//       contains the number of the bucket representing the i-th entry of the
//       table in enumeration order. Entries may contain unitialized data if the
//       corresponding bucket  hasn't been used before.
class V8_EXPORT_PRIVATE SwissNameDictionary : public HeapObject { … };

}  // namespace v8::internal

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

#endif  // V8_OBJECTS_SWISS_NAME_DICTIONARY_H_
chromium/v8/src/objects/swiss-name-dictionary.h
