Line data Source code
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/objects/heap-object-inl.h"
14 : #include "src/roots-inl.h"
15 :
16 : // Has to be the last include (doesn't have include guards):
17 : #include "src/objects/object-macros.h"
18 :
19 : namespace v8 {
20 : namespace internal {
21 :
22 : OBJECT_CONSTRUCTORS_IMPL(HashTableBase, FixedArray)
23 :
24 : template <typename Derived, typename Shape>
25 0 : HashTable<Derived, Shape>::HashTable(Address ptr) : HashTableBase(ptr) {
26 : SLOW_DCHECK(IsHashTable());
27 0 : }
28 :
29 : template <typename Derived, typename Shape>
30 0 : ObjectHashTableBase<Derived, Shape>::ObjectHashTableBase(Address ptr)
31 0 : : HashTable<Derived, Shape>(ptr) {}
32 :
33 : ObjectHashTable::ObjectHashTable(Address ptr)
34 : : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>(ptr) {
35 : SLOW_DCHECK(IsObjectHashTable());
36 : }
37 :
38 : EphemeronHashTable::EphemeronHashTable(Address ptr)
39 : : ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>(ptr) {
40 : SLOW_DCHECK(IsEphemeronHashTable());
41 : }
42 :
43 : ObjectHashSet::ObjectHashSet(Address ptr)
44 : : HashTable<ObjectHashSet, ObjectHashSetShape>(ptr) {
45 : SLOW_DCHECK(IsObjectHashSet());
46 : }
47 :
48 : CAST_ACCESSOR(ObjectHashTable)
49 : CAST_ACCESSOR(EphemeronHashTable)
50 : CAST_ACCESSOR(ObjectHashSet)
51 :
52 1303 : void EphemeronHashTable::set_key(int index, Object value) {
53 : DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
54 : DCHECK(IsEphemeronHashTable());
55 : DCHECK_GE(index, 0);
56 : DCHECK_LT(index, this->length());
57 1303 : int offset = kHeaderSize + index * kTaggedSize;
58 1303 : RELAXED_WRITE_FIELD(*this, offset, value);
59 1303 : EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value);
60 1303 : }
61 :
62 16972 : void EphemeronHashTable::set_key(int index, Object value,
63 : WriteBarrierMode mode) {
64 : DCHECK_NE(GetReadOnlyRoots().fixed_cow_array_map(), map());
65 : DCHECK(IsEphemeronHashTable());
66 : DCHECK_GE(index, 0);
67 : DCHECK_LT(index, this->length());
68 16972 : int offset = kHeaderSize + index * kTaggedSize;
69 16972 : RELAXED_WRITE_FIELD(*this, offset, value);
70 19059 : CONDITIONAL_EPHEMERON_KEY_WRITE_BARRIER(*this, offset, value, mode);
71 16972 : }
72 :
73 0 : int HashTableBase::NumberOfElements() const {
74 0 : return Smi::ToInt(get(kNumberOfElementsIndex));
75 : }
76 :
77 : int HashTableBase::NumberOfDeletedElements() const {
78 : return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
79 : }
80 :
81 : int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); }
82 :
83 33522920 : void HashTableBase::ElementAdded() {
84 33522920 : SetNumberOfElements(NumberOfElements() + 1);
85 33522920 : }
86 :
87 207683 : void HashTableBase::ElementRemoved() {
88 207683 : SetNumberOfElements(NumberOfElements() - 1);
89 207683 : SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
90 207683 : }
91 :
92 69009 : void HashTableBase::ElementsRemoved(int n) {
93 69009 : SetNumberOfElements(NumberOfElements() - n);
94 69009 : SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
95 69009 : }
96 :
97 : // static
98 : int HashTableBase::ComputeCapacity(int at_least_space_for) {
99 : // Add 50% slack to make slot collisions sufficiently unlikely.
100 : // See matching computation in HashTable::HasSufficientCapacityToAdd().
101 : // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
102 1572231 : int raw_cap = at_least_space_for + (at_least_space_for >> 1);
103 1572252 : int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
104 : return Max(capacity, kMinCapacity);
105 : }
106 :
107 : void HashTableBase::SetNumberOfElements(int nof) {
108 : set(kNumberOfElementsIndex, Smi::FromInt(nof));
109 : }
110 :
111 : void HashTableBase::SetNumberOfDeletedElements(int nod) {
112 : set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
113 : }
114 :
115 : template <typename Key>
116 : RootIndex BaseShape<Key>::GetMapRootIndex() {
117 : return RootIndex::kHashTableMap;
118 : }
119 :
120 : RootIndex EphemeronHashTableShape::GetMapRootIndex() {
121 : return RootIndex::kEphemeronHashTableMap;
122 : }
123 :
124 : template <typename Derived, typename Shape>
125 201375688 : int HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
126 402751380 : return FindEntry(ReadOnlyRoots(isolate), key, Shape::Hash(isolate, key));
127 : }
128 :
129 : // Find entry for key otherwise return kNotFound.
130 : template <typename Derived, typename Shape>
131 213837578 : int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
132 : int32_t hash) {
133 213837578 : uint32_t capacity = Capacity();
134 213837578 : uint32_t entry = FirstProbe(hash, capacity);
135 : uint32_t count = 1;
136 : // EnsureCapacity will guarantee the hash table is never full.
137 : Object undefined = roots.undefined_value();
138 : Object the_hole = roots.the_hole_value();
139 : USE(the_hole);
140 167585423 : while (true) {
141 381423001 : Object element = KeyAt(entry);
142 : // Empty entry. Uses raw unchecked accessors because it is called by the
143 : // string table during bootstrapping.
144 381423001 : if (element == undefined) break;
145 197762969 : if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
146 234507727 : if (Shape::IsMatch(key, element)) return entry;
147 : }
148 167585423 : entry = NextProbe(entry, count++, capacity);
149 : }
150 : return kNotFound;
151 : }
152 :
153 : template <typename Derived, typename Shape>
154 15816506 : bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object k) {
155 15816506 : return Shape::IsKey(roots, k);
156 : }
157 :
158 : template <typename Derived, typename Shape>
159 58370004 : bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, int entry,
160 : Object* out_k) {
161 : Object k = KeyAt(entry);
162 58370004 : if (!IsKey(roots, k)) return false;
163 27421012 : *out_k = Shape::Unwrap(k);
164 27421012 : return true;
165 : }
166 :
167 : template <typename Derived, typename Shape>
168 0 : void HashTable<Derived, Shape>::set_key(int index, Object value) {
169 : DCHECK(!IsEphemeronHashTable());
170 69804 : FixedArray::set(index, value);
171 0 : }
172 :
173 : template <typename Derived, typename Shape>
174 0 : void HashTable<Derived, Shape>::set_key(int index, Object value,
175 : WriteBarrierMode mode) {
176 : DCHECK(!IsEphemeronHashTable());
177 86887529 : FixedArray::set(index, value, mode);
178 0 : }
179 :
180 : template <typename KeyT>
181 : bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object key) {
182 : return IsLive(roots, key);
183 : }
184 :
185 : template <typename KeyT>
186 : bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object k) {
187 2539481225 : return k != roots.the_hole_value() && k != roots.undefined_value();
188 : }
189 :
190 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
191 107938 : return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound;
192 : }
193 :
194 11457 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
195 11457 : Object hash = key->GetHash();
196 11457 : if (!hash->IsSmi()) return false;
197 10942 : return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)) != kNotFound;
198 : }
199 :
200 : bool ObjectHashTableShape::IsMatch(Handle<Object> key, Object other) {
201 190450 : return key->SameValue(other);
202 : }
203 :
204 : uint32_t ObjectHashTableShape::Hash(Isolate* isolate, Handle<Object> key) {
205 2000 : return Smi::ToInt(key->GetHash());
206 : }
207 :
208 : uint32_t ObjectHashTableShape::HashForObject(ReadOnlyRoots roots,
209 : Object other) {
210 452622 : return Smi::ToInt(other->GetHash());
211 : }
212 :
213 : } // namespace internal
214 : } // namespace v8
215 :
216 : #include "src/objects/object-macros-undef.h"
217 :
218 : #endif // V8_OBJECTS_HASH_TABLE_INL_H_
|
