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/fixed-array-inl.h"
12 : #include "src/roots-inl.h"
13 :
14 : // Has to be the last include (doesn't have include guards):
15 : #include "src/objects/object-macros.h"
16 :
17 : namespace v8 {
18 : namespace internal {
19 :
20 84896199 : int HashTableBase::NumberOfElements() const {
21 84896199 : return Smi::ToInt(get(kNumberOfElementsIndex));
22 : }
23 :
24 34349898 : int HashTableBase::NumberOfDeletedElements() const {
25 34349898 : return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
26 : }
27 :
28 1756070856 : int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); }
29 :
30 34056523 : void HashTableBase::ElementAdded() {
31 34056523 : SetNumberOfElements(NumberOfElements() + 1);
32 34056521 : }
33 :
34 148432 : void HashTableBase::ElementRemoved() {
35 148432 : SetNumberOfElements(NumberOfElements() - 1);
36 148432 : SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
37 148432 : }
38 :
39 83636 : void HashTableBase::ElementsRemoved(int n) {
40 83636 : SetNumberOfElements(NumberOfElements() - n);
41 83636 : SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
42 83636 : }
43 :
44 : // static
45 : int HashTableBase::ComputeCapacity(int at_least_space_for) {
46 : // Add 50% slack to make slot collisions sufficiently unlikely.
47 : // See matching computation in HashTable::HasSufficientCapacityToAdd().
48 : // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
49 1525390 : int raw_cap = at_least_space_for + (at_least_space_for >> 1);
50 1525410 : int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
51 : return Max(capacity, kMinCapacity);
52 : }
53 :
54 : void HashTableBase::SetNumberOfElements(int nof) {
55 : set(kNumberOfElementsIndex, Smi::FromInt(nof));
56 : }
57 :
58 : void HashTableBase::SetNumberOfDeletedElements(int nod) {
59 : set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
60 : }
61 :
62 : template <typename Key>
63 : RootIndex BaseShape<Key>::GetMapRootIndex() {
64 : return RootIndex::kHashTableMap;
65 : }
66 :
67 : RootIndex EphemeronHashTableShape::GetMapRootIndex() {
68 : return RootIndex::kEphemeronHashTableMap;
69 : }
70 :
71 : template <typename Derived, typename Shape>
72 205743442 : int HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
73 411486863 : return FindEntry(ReadOnlyRoots(isolate), key, Shape::Hash(isolate, key));
74 : }
75 :
76 : // Find entry for key otherwise return kNotFound.
77 : template <typename Derived, typename Shape>
78 207915343 : int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
79 : int32_t hash) {
80 207915343 : uint32_t capacity = Capacity();
81 207915384 : uint32_t entry = FirstProbe(hash, capacity);
82 : uint32_t count = 1;
83 : // EnsureCapacity will guarantee the hash table is never full.
84 : Object undefined = roots.undefined_value();
85 : Object the_hole = roots.the_hole_value();
86 : USE(the_hole);
87 : while (true) {
88 366978714 : Object element = KeyAt(entry);
89 : // Empty entry. Uses raw unchecked accessors because it is called by the
90 : // string table during bootstrapping.
91 366978725 : if (element == undefined) break;
92 182882393 : if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
93 218451195 : if (Shape::IsMatch(key, element)) return entry;
94 : }
95 159063332 : entry = NextProbe(entry, count++, capacity);
96 : }
97 159063332 : return kNotFound;
98 : }
99 :
100 : template <typename Derived, typename Shape>
101 107618 : bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object k) {
102 37481601 : return Shape::IsKey(roots, k);
103 : }
104 :
105 : template <typename Derived, typename Shape>
106 50837241 : bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, int entry,
107 : Object* out_k) {
108 50837241 : Object k = KeyAt(entry);
109 50837261 : if (!IsKey(roots, k)) return false;
110 23605205 : *out_k = Shape::Unwrap(k);
111 23605205 : return true;
112 : }
113 :
114 : template <typename KeyT>
115 : bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object key) {
116 14001317 : return IsLive(roots, key);
117 : }
118 :
119 : template <typename KeyT>
120 1390354699 : bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object k) {
121 2762589362 : return k != roots.the_hole_value() && k != roots.undefined_value();
122 : }
123 :
124 106186 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
125 106186 : return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound;
126 : }
127 :
128 11457 : bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
129 11457 : Object hash = key->GetHash();
130 11457 : if (!hash->IsSmi()) return false;
131 21884 : return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)) != kNotFound;
132 : }
133 :
134 156685 : bool ObjectHashTableShape::IsMatch(Handle<Object> key, Object other) {
135 156685 : return key->SameValue(other);
136 : }
137 :
138 1000 : uint32_t ObjectHashTableShape::Hash(Isolate* isolate, Handle<Object> key) {
139 1000 : return Smi::ToInt(key->GetHash());
140 : }
141 :
142 : uint32_t ObjectHashTableShape::HashForObject(Isolate* isolate, Object other) {
143 223322 : return Smi::ToInt(other->GetHash());
144 : }
145 :
146 : } // namespace internal
147 : } // namespace v8
148 :
149 : #include "src/objects/object-macros-undef.h"
150 :
151 : #endif // V8_OBJECTS_HASH_TABLE_INL_H_
|
