off-heap-hash-table.h | Explore in Territory

// Copyright 2023 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_OFF_HEAP_HASH_TABLE_H_
#define V8_OBJECTS_OFF_HEAP_HASH_TABLE_H_

#include "src/common/globals.h"
#include "src/execution/isolate-utils.h"
#include "src/objects/compressed-slots.h"
#include "src/objects/slots.h"
#include "src/objects/smi.h"
#include "src/objects/visitors.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 {
namespace internal {

// A base class for building off-heap hash tables (e.g. the string table) that
// stores tagged values.
//
// It is a variable sized structure, with a "header" followed directly in memory
// by the elements themselves. These are accessed as offsets from the elements_
// field, which itself provides storage for the first element.
//
// The elements themselves are stored as an open-addressed hash table, with
// quadratic probing and Smi 0 and Smi 1 as the empty and deleted sentinels,
// respectively.
//
// It is a CRTP class whose derived class must provide the following
// definitions:
//
//  // The number of elements per table entry.
//  static constexpr int kEntrySize;
//
//  // The factor by which to decide if the table ought to shrink.
//  static constexpr int kMaxEmptyFactor;
//
//  // The minimum number of elements for new tables.
//  static constexpr int kMinCapacity;
//
//  // Computes the hash of a key {obj}.
//  static uint32_t Hash(Tagged<Object> obj);
//
//  // Returns whether the lookup key {key} matches the key element {obj}.
//  template <typename IsolateT, typename Key>
//  static bool KeyIsMatch(IsolateT* isolate, Key key, Tagged<Object> obj);
//
//  // Load the key object at entry {index}, decompressing it if needed.
//  Tagged<Object> GetKey(PtrComprCageBase, InternalIndex index);
//
//  // Store the key object at the entry {index}.
//  void SetKey(InternalIndex index, Tagged<Object> key);
//
//  // Store an entire entry at {index}. The arity of this function must be
//  // kEntrySize + 1.
//  void Set(InternalIndex index, Tagged<Object>...);
//
//  // Copy an entry in this table at {from_index} into the entry in {to} at
//  // {to_index}, exclusive of the key.
//  void CopyEntryExcludingKeyInto(PtrComprCageBase, InternalIndex from_index,
//                                 Derived* to, InternalIndex to_index);
//
template <typename Derived>
class OffHeapHashTableBase { … };

}  // namespace internal
}  // namespace v8

#endif  // V8_OBJECTS_OFF_HEAP_HASH_TABLE_H_
chromium/v8/src/objects/off-heap-hash-table.h
