hash-table-inl.h 8.86 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2017 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_HASH_TABLE_INL_H_
#define V8_OBJECTS_HASH_TABLE_INL_H_

8
#include "src/execution/isolate-utils-inl.h"
9 10
#include "src/heap/heap.h"
#include "src/objects/fixed-array-inl.h"
11
#include "src/objects/hash-table.h"
12
#include "src/objects/heap-object-inl.h"
13
#include "src/objects/objects-inl.h"
14
#include "src/roots/roots-inl.h"
15

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

19 20 21
namespace v8 {
namespace internal {

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
OBJECT_CONSTRUCTORS_IMPL(HashTableBase, FixedArray)

template <typename Derived, typename Shape>
HashTable<Derived, Shape>::HashTable(Address ptr) : HashTableBase(ptr) {
  SLOW_DCHECK(IsHashTable());
}

template <typename Derived, typename Shape>
ObjectHashTableBase<Derived, Shape>::ObjectHashTableBase(Address ptr)
    : HashTable<Derived, Shape>(ptr) {}

ObjectHashTable::ObjectHashTable(Address ptr)
    : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>(ptr) {
  SLOW_DCHECK(IsObjectHashTable());
}

EphemeronHashTable::EphemeronHashTable(Address ptr)
39
    : ObjectHashTableBase<EphemeronHashTable, ObjectHashTableShape>(ptr) {
40 41 42 43 44 45 46 47 48 49 50 51
  SLOW_DCHECK(IsEphemeronHashTable());
}

ObjectHashSet::ObjectHashSet(Address ptr)
    : HashTable<ObjectHashSet, ObjectHashSetShape>(ptr) {
  SLOW_DCHECK(IsObjectHashSet());
}

CAST_ACCESSOR(ObjectHashTable)
CAST_ACCESSOR(EphemeronHashTable)
CAST_ACCESSOR(ObjectHashSet)

52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
void EphemeronHashTable::set_key(int index, Object value) {
  DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
  DCHECK(IsEphemeronHashTable());
  DCHECK_GE(index, 0);
  DCHECK_LT(index, this->length());
  int offset = kHeaderSize + index * kTaggedSize;
  RELAXED_WRITE_FIELD(*this, offset, value);
  EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value);
}

void EphemeronHashTable::set_key(int index, Object value,
                                 WriteBarrierMode mode) {
  DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
  DCHECK(IsEphemeronHashTable());
  DCHECK_GE(index, 0);
  DCHECK_LT(index, this->length());
  int offset = kHeaderSize + index * kTaggedSize;
  RELAXED_WRITE_FIELD(*this, offset, value);
  CONDITIONAL_EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value, mode);
}

73
int HashTableBase::NumberOfElements() const {
74
  return Smi::cast(get(kNumberOfElementsIndex)).value();
75 76 77
}

int HashTableBase::NumberOfDeletedElements() const {
78
  return Smi::cast(get(kNumberOfDeletedElementsIndex)).value();
79 80
}

81
int HashTableBase::Capacity() const {
82
  return Smi::cast(get(kCapacityIndex)).value();
83
}
84

85 86 87 88
InternalIndex::Range HashTableBase::IterateEntries() const {
  return InternalIndex::Range(Capacity());
}

89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
void HashTableBase::ElementAdded() {
  SetNumberOfElements(NumberOfElements() + 1);
}

void HashTableBase::ElementRemoved() {
  SetNumberOfElements(NumberOfElements() - 1);
  SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
}

void HashTableBase::ElementsRemoved(int n) {
  SetNumberOfElements(NumberOfElements() - n);
  SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
}

// static
int HashTableBase::ComputeCapacity(int at_least_space_for) {
  // Add 50% slack to make slot collisions sufficiently unlikely.
  // See matching computation in HashTable::HasSufficientCapacityToAdd().
  // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
  int raw_cap = at_least_space_for + (at_least_space_for >> 1);
  int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
110
  return std::max({capacity, kMinCapacity});
111 112 113 114 115 116 117 118 119 120
}

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

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

121 122 123
// static
template <typename Derived, typename Shape>
Handle<Map> HashTable<Derived, Shape>::GetMap(ReadOnlyRoots roots) {
124
  return roots.hash_table_map_handle();
125 126
}

127 128
// static
Handle<Map> EphemeronHashTable::GetMap(ReadOnlyRoots roots) {
129
  return roots.ephemeron_hash_table_map_handle();
130 131
}

132
template <typename Derived, typename Shape>
133 134
template <typename IsolateT>
InternalIndex HashTable<Derived, Shape>::FindEntry(IsolateT* isolate, Key key) {
135 136
  ReadOnlyRoots roots(isolate);
  return FindEntry(isolate, roots, key, Shape::Hash(roots, key));
137 138 139 140
}

// Find entry for key otherwise return kNotFound.
template <typename Derived, typename Shape>
141
InternalIndex HashTable<Derived, Shape>::FindEntry(PtrComprCageBase cage_base,
142
                                                   ReadOnlyRoots roots, Key key,
143
                                                   int32_t hash) {
144
  DisallowGarbageCollection no_gc;
145 146
  uint32_t capacity = Capacity();
  uint32_t count = 1;
147 148
  Object undefined = roots.undefined_value();
  Object the_hole = roots.the_hole_value();
149 150 151
  // EnsureCapacity will guarantee the hash table is never full.
  for (InternalIndex entry = FirstProbe(hash, capacity);;
       entry = NextProbe(entry, count++, capacity)) {
152
    Object element = KeyAt(cage_base, entry);
153 154
    // Empty entry. Uses raw unchecked accessors because it is called by the
    // string table during bootstrapping.
155
    if (element == undefined) return InternalIndex::NotFound();
156 157
    if (Shape::kMatchNeedsHoleCheck && element == the_hole) continue;
    if (Shape::IsMatch(key, element)) return entry;
158 159 160
  }
}

161 162 163 164 165 166 167
// static
template <typename Derived, typename Shape>
bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object k) {
  // TODO(leszeks): Dictionaries that don't delete could skip the hole check.
  return k != roots.undefined_value() && k != roots.the_hole_value();
}

168
template <typename Derived, typename Shape>
169
bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, InternalIndex entry,
170 171
                                      Object* out_k) {
  Object k = KeyAt(entry);
172
  if (!IsKey(roots, k)) return false;
173 174 175 176
  *out_k = Shape::Unwrap(k);
  return true;
}

177
template <typename Derived, typename Shape>
178 179 180 181
bool HashTable<Derived, Shape>::ToKey(PtrComprCageBase cage_base,
                                      InternalIndex entry, Object* out_k) {
  Object k = KeyAt(cage_base, entry);
  if (!IsKey(GetReadOnlyRoots(cage_base), k)) return false;
182 183 184 185
  *out_k = Shape::Unwrap(k);
  return true;
}

186 187
template <typename Derived, typename Shape>
Object HashTable<Derived, Shape>::KeyAt(InternalIndex entry) {
188 189
  PtrComprCageBase cage_base = GetPtrComprCageBase(*this);
  return KeyAt(cage_base, entry);
190 191 192
}

template <typename Derived, typename Shape>
193
Object HashTable<Derived, Shape>::KeyAt(PtrComprCageBase cage_base,
194
                                        InternalIndex entry) {
195
  return get(cage_base, EntryToIndex(entry) + kEntryKeyIndex);
196 197
}

198 199 200 201 202 203 204 205 206 207 208 209 210 211
template <typename Derived, typename Shape>
Object HashTable<Derived, Shape>::KeyAt(InternalIndex entry,
                                        RelaxedLoadTag tag) {
  PtrComprCageBase cage_base = GetPtrComprCageBase(*this);
  return KeyAt(cage_base, entry, tag);
}

template <typename Derived, typename Shape>
Object HashTable<Derived, Shape>::KeyAt(PtrComprCageBase cage_base,
                                        InternalIndex entry,
                                        RelaxedLoadTag tag) {
  return get(cage_base, EntryToIndex(entry) + kEntryKeyIndex, tag);
}

212 213 214 215 216 217 218 219 220 221 222 223 224
template <typename Derived, typename Shape>
void HashTable<Derived, Shape>::set_key(int index, Object value) {
  DCHECK(!IsEphemeronHashTable());
  FixedArray::set(index, value);
}

template <typename Derived, typename Shape>
void HashTable<Derived, Shape>::set_key(int index, Object value,
                                        WriteBarrierMode mode) {
  DCHECK(!IsEphemeronHashTable());
  FixedArray::set(index, value, mode);
}

225 226 227 228 229 230 231 232 233 234
template <typename Derived, typename Shape>
void HashTable<Derived, Shape>::SetCapacity(int capacity) {
  // To scale a computed hash code to fit within the hash table, we
  // use bit-wise AND with a mask, so the capacity must be positive
  // and non-zero.
  DCHECK_GT(capacity, 0);
  DCHECK_LE(capacity, kMaxCapacity);
  set(kCapacityIndex, Smi::FromInt(capacity));
}

235
bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
236
  return FindEntry(isolate, ReadOnlyRoots(isolate), key, hash).is_found();
237 238 239
}

bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
240
  Object hash = key->GetHash();
241
  if (!hash.IsSmi()) return false;
242 243
  return FindEntry(isolate, ReadOnlyRoots(isolate), key, Smi::ToInt(hash))
      .is_found();
244 245
}

246
bool ObjectHashTableShape::IsMatch(Handle<Object> key, Object other) {
247 248 249
  return key->SameValue(other);
}

250
uint32_t ObjectHashTableShape::Hash(ReadOnlyRoots roots, Handle<Object> key) {
251 252 253
  return Smi::ToInt(key->GetHash());
}

254 255
uint32_t ObjectHashTableShape::HashForObject(ReadOnlyRoots roots,
                                             Object other) {
256
  return Smi::ToInt(other.GetHash());
257 258
}

259 260 261
}  // namespace internal
}  // namespace v8

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

264
#endif  // V8_OBJECTS_HASH_TABLE_INL_H_