V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
hash-table-inl.h
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 int HashTableBase::NumberOfElements() const {
21  return Smi::ToInt(get(kNumberOfElementsIndex));
22 }
23 
24 int HashTableBase::NumberOfDeletedElements() const {
25  return Smi::ToInt(get(kNumberOfDeletedElementsIndex));
26 }
27 
28 int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); }
29 
30 void HashTableBase::ElementAdded() {
31  SetNumberOfElements(NumberOfElements() + 1);
32 }
33 
34 void HashTableBase::ElementRemoved() {
35  SetNumberOfElements(NumberOfElements() - 1);
36  SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
37 }
38 
39 void HashTableBase::ElementsRemoved(int n) {
40  SetNumberOfElements(NumberOfElements() - n);
41  SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
42 }
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  int raw_cap = at_least_space_for + (at_least_space_for >> 1);
50  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 int HashTable<Derived, Shape>::FindEntry(Isolate* isolate, Key key) {
73  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 int HashTable<Derived, Shape>::FindEntry(ReadOnlyRoots roots, Key key,
79  int32_t hash) {
80  uint32_t capacity = Capacity();
81  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  Object* element = KeyAt(entry);
89  // Empty entry. Uses raw unchecked accessors because it is called by the
90  // string table during bootstrapping.
91  if (element == undefined) break;
92  if (!(Shape::kNeedsHoleCheck && the_hole == element)) {
93  if (Shape::IsMatch(key, element)) return entry;
94  }
95  entry = NextProbe(entry, count++, capacity);
96  }
97  return kNotFound;
98 }
99 
100 template <typename Derived, typename Shape>
101 bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object* k) {
102  return Shape::IsKey(roots, k);
103 }
104 
105 template <typename Derived, typename Shape>
106 bool HashTable<Derived, Shape>::ToKey(ReadOnlyRoots roots, int entry,
107  Object** out_k) {
108  Object* k = KeyAt(entry);
109  if (!IsKey(roots, k)) return false;
110  *out_k = Shape::Unwrap(k);
111  return true;
112 }
113 
114 template <typename KeyT>
115 bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object* key) {
116  return IsLive(roots, key);
117 }
118 
119 template <typename KeyT>
120 bool BaseShape<KeyT>::IsLive(ReadOnlyRoots roots, Object* k) {
121  return k != roots.the_hole_value() && k != roots.undefined_value();
122 }
123 
124 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) {
125  return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound;
126 }
127 
128 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key) {
129  Object* hash = key->GetHash();
130  if (!hash->IsSmi()) return false;
131  return FindEntry(ReadOnlyRoots(isolate), key, Smi::ToInt(hash)) != kNotFound;
132 }
133 
134 } // namespace internal
135 } // namespace v8
136 
137 #include "src/objects/object-macros-undef.h"
138 
139 #endif // V8_OBJECTS_HASH_TABLE_INL_H_
Definition: libplatform.h:13