1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_OBJECTS_HASH_TABLE_INL_H_
6 #define V8_OBJECTS_HASH_TABLE_INL_H_
7
8 #include "src/objects/hash-table.h"
9
10 #include "src/heap/heap.h"
11 #include "src/objects-inl.h"
12 #include "src/objects/fixed-array-inl.h"
13 #include "src/roots-inl.h"
14
15 namespace v8 {
16 namespace internal {
17
NumberOfElements()18 int HashTableBase::NumberOfElements() const {
19 return Smi::ToInt(get(kNumberOfElementsIndex));
20 }
21
NumberOfDeletedElements()22 int HashTableBase::NumberOfDeletedElements() const {
23 return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
24 }
25
Capacity()26 int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); }
27
ElementAdded()28 void HashTableBase::ElementAdded() {
29 SetNumberOfElements(NumberOfElements() + 1);
30 }
31
ElementRemoved()32 void HashTableBase::ElementRemoved() {
33 SetNumberOfElements(NumberOfElements() - 1);
34 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
35 }
36
ElementsRemoved(int n)37 void HashTableBase::ElementsRemoved(int n) {
38 SetNumberOfElements(NumberOfElements() - n);
39 SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
40 }
41
42 // static
ComputeCapacity(int at_least_space_for)43 int HashTableBase::ComputeCapacity(int at_least_space_for) {
44 // Add 50% slack to make slot collisions sufficiently unlikely.
45 // See matching computation in HashTable::HasSufficientCapacityToAdd().
46 // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
47 int raw_cap = at_least_space_for + (at_least_space_for >> 1);
48 int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
49 return Max(capacity, kMinCapacity);
50 }
51
SetNumberOfElements(int nof)52 void HashTableBase::SetNumberOfElements(int nof) {
53 set(kNumberOfElementsIndex, Smi::FromInt(nof));
54 }
55
SetNumberOfDeletedElements(int nod)56 void HashTableBase::SetNumberOfDeletedElements(int nod) {
57 set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
58 }
59
60 template <typename Key>
GetMapRootIndex()61 int BaseShape<Key>::GetMapRootIndex() {
62 return Heap::kHashTableMapRootIndex;
63 }
64
GetMapRootIndex()65 int EphemeronHashTableShape::GetMapRootIndex() {
66 return Heap::kEphemeronHashTableMapRootIndex;
67 }
68
69 template <typename Derived, typename Shape>
FindEntry(Isolate * isolate,Key key)70 int HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
71 return FindEntry(ReadOnlyRoots(isolate), key, Shape::Hash(isolate, key));
72 }
73
74 // Find entry for key otherwise return kNotFound.
75 template <typename Derived, typename Shape>
FindEntry(ReadOnlyRoots roots,Key key,int32_t hash)76 int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
77 int32_t hash) {
78 uint32_t capacity = Capacity();
79 uint32_t entry = FirstProbe(hash, capacity);
80 uint32_t count = 1;
81 // EnsureCapacity will guarantee the hash table is never full.
82 Object* undefined = roots.undefined_value();
83 Object* the_hole = roots.the_hole_value();
84 USE(the_hole);
85 while (true) {
86 Object* element = KeyAt(entry);
87 // Empty entry. Uses raw unchecked accessors because it is called by the
88 // string table during bootstrapping.
89 if (element == undefined) break;
90 if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
91 if (Shape::IsMatch(key, element)) return entry;
92 }
93 entry = NextProbe(entry, count++, capacity);
94 }
95 return kNotFound;
96 }
97
98 template <typename Derived, typename Shape>
IsKey(ReadOnlyRoots roots,Object * k)99 bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object* k) {
100 return Shape::IsKey(roots, k);
101 }
102
103 template <typename Derived, typename Shape>
ToKey(ReadOnlyRoots roots,int entry,Object ** out_k)104 bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, int entry,
105 Object** out_k) {
106 Object* k = KeyAt(entry);
107 if (!IsKey(roots, k)) return false;
108 *out_k = Shape::Unwrap(k);
109 return true;
110 }
111
112 template <typename KeyT>
IsKey(ReadOnlyRoots roots,Object * key)113 bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object* key) {
114 return IsLive(roots, key);
115 }
116
117 template <typename KeyT>
IsLive(ReadOnlyRoots roots,Object * k)118 bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object* k) {
119 return k != roots.the_hole_value() && k != roots.undefined_value();
120 }
121
122 template <typename Derived, typename Shape>
cast(Object * obj)123 HashTable<Derived, Shape>* HashTable<Derived, Shape>::cast(Object* obj) {
124 SLOW_DCHECK(obj->IsHashTable());
125 return reinterpret_cast<HashTable*>(obj);
126 }
127
128 template <typename Derived, typename Shape>
cast(const Object * obj)129 const HashTable<Derived, Shape>* HashTable<Derived, Shape>::cast(
130 const Object* obj) {
131 SLOW_DCHECK(obj->IsHashTable());
132 return reinterpret_cast<const HashTable*>(obj);
133 }
134
Has(Isolate * isolate,Handle<Object> key,int32_t hash)135 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
136 return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound;
137 }
138
Has(Isolate * isolate,Handle<Object> key)139 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
140 Object* hash = key->GetHash();
141 if (!hash->IsSmi()) return false;
142 return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)) != kNotFound;
143 }
144
145 } // namespace internal
146 } // namespace v8
147
148 #endif // V8_OBJECTS_HASH_TABLE_INL_H_
149