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 88497 : ObjectHashTable::ObjectHashTable(Address ptr)
34 : : ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>(ptr) {
35 : SLOW_DCHECK(IsObjectHashTable());
36 88497 : }
37 :
38 152186 : EphemeronHashTable::EphemeronHashTable(Address ptr)
39 : : ObjectHashTableBase<EphemeronHashTable, EphemeronHashTableShape>(ptr) {
40 : SLOW_DCHECK(IsEphemeronHashTable());
41 152186 : }
42 :
43 7730 : ObjectHashSet::ObjectHashSet(Address ptr)
44 : : HashTable<ObjectHashSet, ObjectHashSetShape>(ptr) {
45 : SLOW_DCHECK(IsObjectHashSet());
46 7730 : }
47 :
48 88497 : CAST_ACCESSOR(ObjectHashTable)
49 152198 : CAST_ACCESSOR(EphemeronHashTable)
50 7730 : CAST_ACCESSOR(ObjectHashSet)
51 :
52 80710857 : int HashTableBase::NumberOfElements() const {
53 80710857 : return Smi::ToInt(get(kNumberOfElementsIndex));
54 : }
55 :
56 32397808 : int HashTableBase::NumberOfDeletedElements() const {
57 32397808 : return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
58 : }
59 :
60 2043695552 : int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); }
61 :
62 32117580 : void HashTableBase::ElementAdded() {
63 32117580 : SetNumberOfElements(NumberOfElements() + 1);
64 32117580 : }
65 :
66 143580 : void HashTableBase::ElementRemoved() {
67 143580 : SetNumberOfElements(NumberOfElements() - 1);
68 143580 : SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
69 143580 : }
70 :
71 74646 : void HashTableBase::ElementsRemoved(int n) {
72 74646 : SetNumberOfElements(NumberOfElements() - n);
73 74646 : SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
74 74646 : }
75 :
76 : // static
77 : int HashTableBase::ComputeCapacity(int at_least_space_for) {
78 : // Add 50% slack to make slot collisions sufficiently unlikely.
79 : // See matching computation in HashTable::HasSufficientCapacityToAdd().
80 : // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
81 1514000 : int raw_cap = at_least_space_for + (at_least_space_for >> 1);
82 1514020 : int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
83 : return Max(capacity, kMinCapacity);
84 : }
85 :
86 : void HashTableBase::SetNumberOfElements(int nof) {
87 : set(kNumberOfElementsIndex, Smi::FromInt(nof));
88 : }
89 :
90 : void HashTableBase::SetNumberOfDeletedElements(int nod) {
91 : set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
92 : }
93 :
94 : template <typename Key>
95 : RootIndex BaseShape<Key>::GetMapRootIndex() {
96 : return RootIndex::kHashTableMap;
97 : }
98 :
99 112 : RootIndex EphemeronHashTableShape::GetMapRootIndex() {
100 112 : return RootIndex::kEphemeronHashTableMap;
101 : }
102 :
103 : template <typename Derived, typename Shape>
104 200997541 : int HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
105 401995091 : return FindEntry(ReadOnlyRoots(isolate), key, Shape::Hash(isolate, key));
106 : }
107 :
108 : // Find entry for key otherwise return kNotFound.
109 : template <typename Derived, typename Shape>
110 203175015 : int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
111 : int32_t hash) {
112 203175015 : uint32_t capacity = Capacity();
113 203175015 : uint32_t entry = FirstProbe(hash, capacity);
114 : uint32_t count = 1;
115 : // EnsureCapacity will guarantee the hash table is never full.
116 : Object undefined = roots.undefined_value();
117 : Object the_hole = roots.the_hole_value();
118 : USE(the_hole);
119 : while (true) {
120 370585944 : Object element = KeyAt(entry);
121 : // Empty entry. Uses raw unchecked accessors because it is called by the
122 : // string table during bootstrapping.
123 370585953 : if (element == undefined) break;
124 183242724 : if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
125 225486484 : if (Shape::IsMatch(key, element)) return entry;
126 : }
127 167410932 : entry = NextProbe(entry, count++, capacity);
128 : }
129 167410932 : return kNotFound;
130 : }
131 :
132 : template <typename Derived, typename Shape>
133 117574 : bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object k) {
134 37677263 : return Shape::IsKey(roots, k);
135 : }
136 :
137 : template <typename Derived, typename Shape>
138 50941154 : bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, int entry,
139 : Object* out_k) {
140 50941154 : Object k = KeyAt(entry);
141 50941158 : if (!IsKey(roots, k)) return false;
142 23603872 : *out_k = Shape::Unwrap(k);
143 23603872 : return true;
144 : }
145 :
146 : template <typename KeyT>
147 : bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object key) {
148 13964195 : return IsLive(roots, key);
149 : }
150 :
151 : template <typename KeyT>
152 1724666557 : bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object k) {
153 3427766152 : return k != roots.the_hole_value() && k != roots.undefined_value();
154 : }
155 :
156 107853 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
157 107853 : return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound;
158 : }
159 :
160 11457 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
161 11457 : Object hash = key->GetHash();
162 11457 : if (!hash->IsSmi()) return false;
163 21884 : return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)) != kNotFound;
164 : }
165 :
166 155184 : bool ObjectHashTableShape::IsMatch(Handle<Object> key, Object other) {
167 155184 : return key->SameValue(other);
168 : }
169 :
170 1000 : uint32_t ObjectHashTableShape::Hash(Isolate* isolate, Handle<Object> key) {
171 1000 : return Smi::ToInt(key->GetHash());
172 : }
173 :
174 : uint32_t ObjectHashTableShape::HashForObject(Isolate* isolate, Object other) {
175 225626 : return Smi::ToInt(other->GetHash());
176 : }
177 :
178 : } // namespace internal
179 : } // namespace v8
180 :
181 : #include "src/objects/object-macros-undef.h"
182 :
183 : #endif // V8_OBJECTS_HASH_TABLE_INL_H_
|
