Home | History | Annotate | Download | only in objects 
      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