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 18 int HashTableBase::NumberOfElements() const { 19 return Smi::ToInt(get(kNumberOfElementsIndex)); 20 } 21 22 int HashTableBase::NumberOfDeletedElements() const { 23 return Smi::ToInt(get(kNumberOfDeletedElementsIndex)); 24 } 25 26 int HashTableBase::Capacity() const { return Smi::ToInt(get(kCapacityIndex)); } 27 28 void HashTableBase::ElementAdded() { 29 SetNumberOfElements(NumberOfElements() + 1); 30 } 31 32 void HashTableBase::ElementRemoved() { 33 SetNumberOfElements(NumberOfElements() - 1); 34 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); 35 } 36 37 void HashTableBase::ElementsRemoved(int n) { 38 SetNumberOfElements(NumberOfElements() - n); 39 SetNumberOfDeletedElements(NumberOfDeletedElements() + n); 40 } 41 42 // static 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 52 void HashTableBase::SetNumberOfElements(int nof) { 53 set(kNumberOfElementsIndex, Smi::FromInt(nof)); 54 } 55 56 void HashTableBase::SetNumberOfDeletedElements(int nod) { 57 set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod)); 58 } 59 60 template <typename Key> 61 int BaseShape<Key>::GetMapRootIndex() { 62 return Heap::kHashTableMapRootIndex; 63 } 64 65 int EphemeronHashTableShape::GetMapRootIndex() { 66 return Heap::kEphemeronHashTableMapRootIndex; 67 } 68 69 template <typename Derived, typename Shape> 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> 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> 99 bool HashTable<Derived, Shape>::IsKey(ReadOnlyRoots roots, Object* k) { 100 return Shape::IsKey(roots, k); 101 } 102 103 template <typename Derived, typename Shape> 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> 113 bool BaseShape<KeyT>::IsKey(ReadOnlyRoots roots, Object* key) { 114 return IsLive(roots, key); 115 } 116 117 template <typename KeyT> 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> 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> 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 135 bool ObjectHashSet::Has(Isolate* isolate, Handle<Object> key, int32_t hash) { 136 return FindEntry(ReadOnlyRoots(isolate), key, hash) != kNotFound; 137 } 138 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