LCOV - code coverage report
Current view: top level - src/objects - hash-table.h (source / functions) Hit Total Coverage
Test: app.info Lines: 27 36 75.0 %
Date: 2017-04-26 Functions: 9 35 25.7 %

          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_H_
       6             : #define V8_OBJECTS_HASH_TABLE_H_
       7             : 
       8             : #include "src/objects.h"
       9             : 
      10             : // Has to be the last include (doesn't have include guards):
      11             : #include "src/objects/object-macros.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : 
      16             : // HashTable is a subclass of FixedArray that implements a hash table
      17             : // that uses open addressing and quadratic probing.
      18             : //
      19             : // In order for the quadratic probing to work, elements that have not
      20             : // yet been used and elements that have been deleted are
      21             : // distinguished.  Probing continues when deleted elements are
      22             : // encountered and stops when unused elements are encountered.
      23             : //
      24             : // - Elements with key == undefined have not been used yet.
      25             : // - Elements with key == the_hole have been deleted.
      26             : //
      27             : // The hash table class is parameterized with a Shape and a Key.
      28             : // Shape must be a class with the following interface:
      29             : //   class ExampleShape {
      30             : //    public:
      31             : //      // Tells whether key matches other.
      32             : //     static bool IsMatch(Key key, Object* other);
      33             : //     // Returns the hash value for key.
      34             : //     static uint32_t Hash(Key key);
      35             : //     // Returns the hash value for object.
      36             : //     static uint32_t HashForObject(Key key, Object* object);
      37             : //     // Convert key to an object.
      38             : //     static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
      39             : //     // The prefix size indicates number of elements in the beginning
      40             : //     // of the backing storage.
      41             : //     static const int kPrefixSize = ..;
      42             : //     // The Element size indicates number of elements per entry.
      43             : //     static const int kEntrySize = ..;
      44             : //   };
      45             : // The prefix size indicates an amount of memory in the
      46             : // beginning of the backing storage that can be used for non-element
      47             : // information by subclasses.
      48             : 
      49             : template <typename Key>
      50             : class BaseShape {
      51             :  public:
      52             :   static const bool UsesSeed = false;
      53             :   static uint32_t Hash(Key key) { return 0; }
      54             :   static uint32_t SeededHash(Key key, uint32_t seed) {
      55             :     DCHECK(UsesSeed);
      56             :     return Hash(key);
      57             :   }
      58             :   static uint32_t HashForObject(Key key, Object* object) { return 0; }
      59             :   static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) {
      60             :     DCHECK(UsesSeed);
      61             :     return HashForObject(key, object);
      62             :   }
      63             :   static inline Map* GetMap(Isolate* isolate);
      64             : };
      65             : 
      66             : class HashTableBase : public FixedArray {
      67             :  public:
      68             :   // Returns the number of elements in the hash table.
      69             :   inline int NumberOfElements();
      70             : 
      71             :   // Returns the number of deleted elements in the hash table.
      72             :   inline int NumberOfDeletedElements();
      73             : 
      74             :   // Returns the capacity of the hash table.
      75             :   inline int Capacity();
      76             : 
      77             :   // ElementAdded should be called whenever an element is added to a
      78             :   // hash table.
      79             :   inline void ElementAdded();
      80             : 
      81             :   // ElementRemoved should be called whenever an element is removed from
      82             :   // a hash table.
      83             :   inline void ElementRemoved();
      84             :   inline void ElementsRemoved(int n);
      85             : 
      86             :   // Computes the required capacity for a table holding the given
      87             :   // number of elements. May be more than HashTable::kMaxCapacity.
      88             :   static inline int ComputeCapacity(int at_least_space_for);
      89             : 
      90             :   // Tells whether k is a real key.  The hole and undefined are not allowed
      91             :   // as keys and can be used to indicate missing or deleted elements.
      92             :   inline bool IsKey(Isolate* isolate, Object* k);
      93             : 
      94             :   // Compute the probe offset (quadratic probing).
      95             :   INLINE(static uint32_t GetProbeOffset(uint32_t n)) {
      96        5644 :     return (n + n * n) >> 1;
      97             :   }
      98             : 
      99             :   static const int kNumberOfElementsIndex = 0;
     100             :   static const int kNumberOfDeletedElementsIndex = 1;
     101             :   static const int kCapacityIndex = 2;
     102             :   static const int kPrefixStartIndex = 3;
     103             : 
     104             :   // Constant used for denoting a absent entry.
     105             :   static const int kNotFound = -1;
     106             : 
     107             :   // Minimum capacity for newly created hash tables.
     108             :   static const int kMinCapacity = 4;
     109             : 
     110             :  protected:
     111             :   // Update the number of elements in the hash table.
     112             :   inline void SetNumberOfElements(int nof);
     113             : 
     114             :   // Update the number of deleted elements in the hash table.
     115             :   inline void SetNumberOfDeletedElements(int nod);
     116             : 
     117             :   // Returns probe entry.
     118             :   static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) {
     119             :     DCHECK(base::bits::IsPowerOfTwo32(size));
     120             :     return (hash + GetProbeOffset(number)) & (size - 1);
     121             :   }
     122             : 
     123             :   inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
     124   497720433 :     return hash & (size - 1);
     125             :   }
     126             : 
     127             :   inline static uint32_t NextProbe(uint32_t last, uint32_t number,
     128             :                                    uint32_t size) {
     129   339430613 :     return (last + number) & (size - 1);
     130             :   }
     131             : };
     132             : 
     133             : template <typename Derived, typename Shape, typename Key>
     134             : class HashTable : public HashTableBase {
     135             :  public:
     136             :   typedef Shape ShapeT;
     137             : 
     138             :   // Wrapper methods
     139   145221511 :   inline uint32_t Hash(Key key) {
     140             :     if (Shape::UsesSeed) {
     141             :       return Shape::SeededHash(key, GetHeap()->HashSeed());
     142             :     } else {
     143    33151133 :       return Shape::Hash(key);
     144             :     }
     145             :   }
     146             : 
     147           0 :   inline uint32_t HashForObject(Key key, Object* object) {
     148             :     if (Shape::UsesSeed) {
     149     3607223 :       return Shape::SeededHashForObject(key, GetHeap()->HashSeed(), object);
     150             :     } else {
     151     1481288 :       return Shape::HashForObject(key, object);
     152             :     }
     153             :   }
     154             : 
     155             :   // Returns a new HashTable object.
     156             :   MUST_USE_RESULT static Handle<Derived> New(
     157             :       Isolate* isolate, int at_least_space_for,
     158             :       MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY,
     159             :       PretenureFlag pretenure = NOT_TENURED);
     160             : 
     161             :   DECLARE_CAST(HashTable)
     162             : 
     163             :   // Garbage collection support.
     164             :   void IteratePrefix(ObjectVisitor* visitor);
     165             :   void IterateElements(ObjectVisitor* visitor);
     166             : 
     167             :   // Find entry for key otherwise return kNotFound.
     168             :   inline int FindEntry(Key key);
     169             :   inline int FindEntry(Isolate* isolate, Key key, int32_t hash);
     170             :   int FindEntry(Isolate* isolate, Key key);
     171             :   inline bool Has(Isolate* isolate, Key key);
     172             :   inline bool Has(Key key);
     173             : 
     174             :   // Rehashes the table in-place.
     175             :   void Rehash(Key key);
     176             : 
     177             :   // Returns the key at entry.
     178           0 :   Object* KeyAt(int entry) { return get(EntryToIndex(entry) + kEntryKeyIndex); }
     179             : 
     180             :   static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
     181             :   static const int kEntrySize = Shape::kEntrySize;
     182             :   STATIC_ASSERT(kEntrySize > 0);
     183             :   static const int kEntryKeyIndex = 0;
     184             :   static const int kElementsStartOffset =
     185             :       kHeaderSize + kElementsStartIndex * kPointerSize;
     186             :   // Maximal capacity of HashTable. Based on maximal length of underlying
     187             :   // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
     188             :   // cannot overflow.
     189             :   static const int kMaxCapacity =
     190             :       (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
     191             : 
     192             :   // Returns the index for an entry (of the key)
     193           0 :   static inline int EntryToIndex(int entry) {
     194  1650315022 :     return (entry * kEntrySize) + kElementsStartIndex;
     195             :   }
     196             : 
     197             :  protected:
     198             :   friend class ObjectHashTable;
     199             : 
     200             :   MUST_USE_RESULT static Handle<Derived> New(Isolate* isolate, int capacity,
     201             :                                              PretenureFlag pretenure);
     202             : 
     203             :   // Find the entry at which to insert element with the given key that
     204             :   // has the given hash value.
     205             :   uint32_t FindInsertionEntry(uint32_t hash);
     206             : 
     207             :   // Attempt to shrink hash table after removal of key.
     208             :   MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table, Key key);
     209             : 
     210             :   // Ensure enough space for n additional elements.
     211             :   MUST_USE_RESULT static Handle<Derived> EnsureCapacity(
     212             :       Handle<Derived> table, int n, Key key,
     213             :       PretenureFlag pretenure = NOT_TENURED);
     214             : 
     215             :   // Returns true if this table has sufficient capacity for adding n elements.
     216             :   bool HasSufficientCapacityToAdd(int number_of_additional_elements);
     217             : 
     218             :   // Sets the capacity of the hash table.
     219           0 :   void SetCapacity(int capacity) {
     220             :     // To scale a computed hash code to fit within the hash table, we
     221             :     // use bit-wise AND with a mask, so the capacity must be positive
     222             :     // and non-zero.
     223             :     DCHECK(capacity > 0);
     224             :     DCHECK(capacity <= kMaxCapacity);
     225             :     set(kCapacityIndex, Smi::FromInt(capacity));
     226           0 :   }
     227             : 
     228             :  private:
     229             :   // Returns _expected_ if one of entries given by the first _probe_ probes is
     230             :   // equal to  _expected_. Otherwise, returns the entry given by the probe
     231             :   // number _probe_.
     232             :   uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected);
     233             : 
     234             :   void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
     235             : 
     236             :   // Rehashes this hash-table into the new table.
     237             :   void Rehash(Handle<Derived> new_table, Key key);
     238             : };
     239             : 
     240             : // HashTableKey is an abstract superclass for virtual key behavior.
     241   105686262 : class HashTableKey {
     242             :  public:
     243             :   // Returns whether the other object matches this key.
     244             :   virtual bool IsMatch(Object* other) = 0;
     245             :   // Returns the hash value for this key.
     246             :   virtual uint32_t Hash() = 0;
     247             :   // Returns the hash value for object.
     248             :   virtual uint32_t HashForObject(Object* key) = 0;
     249             :   // Returns the key object for storing into the hash table.
     250             :   MUST_USE_RESULT virtual Handle<Object> AsHandle(Isolate* isolate) = 0;
     251             :   // Required.
     252       30357 :   virtual ~HashTableKey() {}
     253             : };
     254             : 
     255             : class ObjectHashTableShape : public BaseShape<Handle<Object>> {
     256             :  public:
     257             :   static inline bool IsMatch(Handle<Object> key, Object* other);
     258             :   static inline uint32_t Hash(Handle<Object> key);
     259             :   static inline uint32_t HashForObject(Handle<Object> key, Object* object);
     260             :   static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
     261             :   static const int kPrefixSize = 0;
     262             :   static const int kEntrySize = 2;
     263             : };
     264             : 
     265             : // ObjectHashTable maps keys that are arbitrary objects to object values by
     266             : // using the identity hash of the key for hashing purposes.
     267             : class ObjectHashTable
     268             :     : public HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>> {
     269             :   typedef HashTable<ObjectHashTable, ObjectHashTableShape, Handle<Object>>
     270             :       DerivedHashTable;
     271             : 
     272             :  public:
     273             :   DECLARE_CAST(ObjectHashTable)
     274             : 
     275             :   // Attempt to shrink hash table after removal of key.
     276             :   MUST_USE_RESULT static inline Handle<ObjectHashTable> Shrink(
     277             :       Handle<ObjectHashTable> table, Handle<Object> key);
     278             : 
     279             :   // Looks up the value associated with the given key. The hole value is
     280             :   // returned in case the key is not present.
     281             :   Object* Lookup(Handle<Object> key);
     282             :   Object* Lookup(Handle<Object> key, int32_t hash);
     283             :   Object* Lookup(Isolate* isolate, Handle<Object> key, int32_t hash);
     284             : 
     285             :   // Returns the value at entry.
     286             :   Object* ValueAt(int entry);
     287             : 
     288             :   // Adds (or overwrites) the value associated with the given key.
     289             :   static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
     290             :                                      Handle<Object> key, Handle<Object> value);
     291             :   static Handle<ObjectHashTable> Put(Handle<ObjectHashTable> table,
     292             :                                      Handle<Object> key, Handle<Object> value,
     293             :                                      int32_t hash);
     294             : 
     295             :   // Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
     296             :   static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
     297             :                                         Handle<Object> key, bool* was_present);
     298             :   static Handle<ObjectHashTable> Remove(Handle<ObjectHashTable> table,
     299             :                                         Handle<Object> key, bool* was_present,
     300             :                                         int32_t hash);
     301             : 
     302             :  protected:
     303             :   friend class MarkCompactCollector;
     304             : 
     305             :   void AddEntry(int entry, Object* key, Object* value);
     306             :   void RemoveEntry(int entry);
     307             : 
     308             :   // Returns the index to the value of an entry.
     309             :   static inline int EntryToValueIndex(int entry) {
     310       27543 :     return EntryToIndex(entry) + 1;
     311             :   }
     312             : };
     313             : 
     314             : class ObjectHashSetShape : public ObjectHashTableShape {
     315             :  public:
     316             :   static const int kPrefixSize = 0;
     317             :   static const int kEntrySize = 1;
     318             : };
     319             : 
     320             : class ObjectHashSet
     321             :     : public HashTable<ObjectHashSet, ObjectHashSetShape, Handle<Object>> {
     322             :  public:
     323             :   static Handle<ObjectHashSet> Add(Handle<ObjectHashSet> set,
     324             :                                    Handle<Object> key);
     325             : 
     326             :   inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
     327             :   inline bool Has(Isolate* isolate, Handle<Object> key);
     328             : 
     329             :   DECLARE_CAST(ObjectHashSet)
     330             : };
     331             : 
     332             : // OrderedHashTable is a HashTable with Object keys that preserves
     333             : // insertion order. There are Map and Set interfaces (OrderedHashMap
     334             : // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
     335             : //
     336             : // Only Object* keys are supported, with Object::SameValueZero() used as the
     337             : // equality operator and Object::GetHash() for the hash function.
     338             : //
     339             : // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
     340             : // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
     341             : // Originally attributed to Tyler Close.
     342             : //
     343             : // Memory layout:
     344             : //   [0]: element count
     345             : //   [1]: deleted element count
     346             : //   [2]: bucket count
     347             : //   [3..(3 + NumberOfBuckets() - 1)]: "hash table", where each item is an
     348             : //                            offset into the data table (see below) where the
     349             : //                            first item in this bucket is stored.
     350             : //   [3 + NumberOfBuckets()..length]: "data table", an array of length
     351             : //                            Capacity() * kEntrySize, where the first entrysize
     352             : //                            items are handled by the derived class and the
     353             : //                            item at kChainOffset is another entry into the
     354             : //                            data table indicating the next entry in this hash
     355             : //                            bucket.
     356             : //
     357             : // When we transition the table to a new version we obsolete it and reuse parts
     358             : // of the memory to store information how to transition an iterator to the new
     359             : // table:
     360             : //
     361             : // Memory layout for obsolete table:
     362             : //   [0]: bucket count
     363             : //   [1]: Next newer table
     364             : //   [2]: Number of removed holes or -1 when the table was cleared.
     365             : //   [3..(3 + NumberOfRemovedHoles() - 1)]: The indexes of the removed holes.
     366             : //   [3 + NumberOfRemovedHoles()..length]: Not used
     367             : //
     368             : template <class Derived, int entrysize>
     369             : class OrderedHashTable : public FixedArray {
     370             :  public:
     371             :   // Returns an OrderedHashTable with a capacity of at least |capacity|.
     372             :   static Handle<Derived> Allocate(Isolate* isolate, int capacity,
     373             :                                   PretenureFlag pretenure = NOT_TENURED);
     374             : 
     375             :   // Returns an OrderedHashTable (possibly |table|) with enough space
     376             :   // to add at least one new element.
     377             :   static Handle<Derived> EnsureGrowable(Handle<Derived> table);
     378             : 
     379             :   // Returns an OrderedHashTable (possibly |table|) that's shrunken
     380             :   // if possible.
     381             :   static Handle<Derived> Shrink(Handle<Derived> table);
     382             : 
     383             :   // Returns a new empty OrderedHashTable and records the clearing so that
     384             :   // existing iterators can be updated.
     385             :   static Handle<Derived> Clear(Handle<Derived> table);
     386             : 
     387             :   // Returns a true if the OrderedHashTable contains the key
     388             :   static bool HasKey(Handle<Derived> table, Handle<Object> key);
     389             : 
     390             :   int NumberOfElements() {
     391             :     return Smi::cast(get(kNumberOfElementsIndex))->value();
     392             :   }
     393             : 
     394             :   int NumberOfDeletedElements() {
     395             :     return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
     396             :   }
     397             : 
     398             :   // Returns the number of contiguous entries in the data table, starting at 0,
     399             :   // that either are real entries or have been deleted.
     400       25642 :   int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
     401             : 
     402             :   int NumberOfBuckets() {
     403             :     return Smi::cast(get(kNumberOfBucketsIndex))->value();
     404             :   }
     405             : 
     406             :   // Returns an index into |this| for the given entry.
     407             :   int EntryToIndex(int entry) {
     408   217722968 :     return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize);
     409             :   }
     410             : 
     411   235381850 :   int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
     412             : 
     413   156921509 :   int HashToEntry(int hash) {
     414             :     int bucket = HashToBucket(hash);
     415   156921509 :     Object* entry = this->get(kHashTableStartIndex + bucket);
     416   156921509 :     return Smi::cast(entry)->value();
     417             :   }
     418             : 
     419           0 :   int KeyToFirstEntry(Isolate* isolate, Object* key) {
     420           0 :     Object* hash = key->GetHash();
     421             :     // If the object does not have an identity hash, it was never used as a key
     422           0 :     if (hash->IsUndefined(isolate)) return kNotFound;
     423           0 :     return HashToEntry(Smi::cast(hash)->value());
     424             :   }
     425             : 
     426    50517032 :   int NextChainEntry(int entry) {
     427    50517032 :     Object* next_entry = get(EntryToIndex(entry) + kChainOffset);
     428    50517032 :     return Smi::cast(next_entry)->value();
     429             :   }
     430             : 
     431             :   // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
     432    63426114 :   Object* KeyAt(int entry) {
     433             :     DCHECK_LT(entry, this->UsedCapacity());
     434    63426114 :     return get(EntryToIndex(entry));
     435             :   }
     436             : 
     437             :   bool IsObsolete() { return !get(kNextTableIndex)->IsSmi(); }
     438             : 
     439             :   // The next newer table. This is only valid if the table is obsolete.
     440             :   Derived* NextTable() { return Derived::cast(get(kNextTableIndex)); }
     441             : 
     442             :   // When the table is obsolete we store the indexes of the removed holes.
     443             :   int RemovedIndexAt(int index) {
     444         224 :     return Smi::cast(get(kRemovedHolesIndex + index))->value();
     445             :   }
     446             : 
     447             :   static const int kNotFound = -1;
     448             :   static const int kMinCapacity = 4;
     449             : 
     450             :   static const int kNumberOfElementsIndex = 0;
     451             :   // The next table is stored at the same index as the nof elements.
     452             :   static const int kNextTableIndex = kNumberOfElementsIndex;
     453             :   static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1;
     454             :   static const int kNumberOfBucketsIndex = kNumberOfDeletedElementsIndex + 1;
     455             :   static const int kHashTableStartIndex = kNumberOfBucketsIndex + 1;
     456             : 
     457             :   static constexpr const int kNumberOfElementsOffset =
     458             :       FixedArray::OffsetOfElementAt(kNumberOfElementsIndex);
     459             :   static constexpr const int kNextTableOffset =
     460             :       FixedArray::OffsetOfElementAt(kNextTableIndex);
     461             :   static constexpr const int kNumberOfDeletedElementsOffset =
     462             :       FixedArray::OffsetOfElementAt(kNumberOfDeletedElementsIndex);
     463             :   static constexpr const int kNumberOfBucketsOffset =
     464             :       FixedArray::OffsetOfElementAt(kNumberOfBucketsIndex);
     465             :   static constexpr const int kHashTableStartOffset =
     466             :       FixedArray::OffsetOfElementAt(kHashTableStartIndex);
     467             : 
     468             :   static const int kEntrySize = entrysize + 1;
     469             :   static const int kChainOffset = entrysize;
     470             : 
     471             :   static const int kLoadFactor = 2;
     472             : 
     473             :   // NumberOfDeletedElements is set to kClearedTableSentinel when
     474             :   // the table is cleared, which allows iterator transitions to
     475             :   // optimize that case.
     476             :   static const int kClearedTableSentinel = -1;
     477             : 
     478             :  protected:
     479             :   static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
     480             : 
     481             :   void SetNumberOfBuckets(int num) {
     482             :     set(kNumberOfBucketsIndex, Smi::FromInt(num));
     483             :   }
     484             : 
     485             :   void SetNumberOfElements(int num) {
     486             :     set(kNumberOfElementsIndex, Smi::FromInt(num));
     487             :   }
     488             : 
     489             :   void SetNumberOfDeletedElements(int num) {
     490             :     set(kNumberOfDeletedElementsIndex, Smi::FromInt(num));
     491             :   }
     492             : 
     493             :   // Returns the number elements that can fit into the allocated buffer.
     494    78680772 :   int Capacity() { return NumberOfBuckets() * kLoadFactor; }
     495             : 
     496      481614 :   void SetNextTable(Derived* next_table) { set(kNextTableIndex, next_table); }
     497             : 
     498             :   void SetRemovedIndexAt(int index, int removed_index) {
     499             :     return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index));
     500             :   }
     501             : 
     502             :   static const int kRemovedHolesIndex = kHashTableStartIndex;
     503             : 
     504             :   static const int kMaxCapacity =
     505             :       (FixedArray::kMaxLength - kHashTableStartIndex) /
     506             :       (1 + (kEntrySize * kLoadFactor));
     507             : };
     508             : 
     509             : class OrderedHashSet : public OrderedHashTable<OrderedHashSet, 1> {
     510             :  public:
     511             :   DECLARE_CAST(OrderedHashSet)
     512             : 
     513             :   static Handle<OrderedHashSet> Add(Handle<OrderedHashSet> table,
     514             :                                     Handle<Object> value);
     515             :   static Handle<FixedArray> ConvertToKeysArray(Handle<OrderedHashSet> table,
     516             :                                                GetKeysConversion convert);
     517             : };
     518             : 
     519             : class OrderedHashMap : public OrderedHashTable<OrderedHashMap, 2> {
     520             :  public:
     521             :   DECLARE_CAST(OrderedHashMap)
     522             : 
     523             :   inline Object* ValueAt(int entry);
     524             : 
     525             :   static const int kValueOffset = 1;
     526             : };
     527             : 
     528             : template <int entrysize>
     529             : class WeakHashTableShape : public BaseShape<Handle<Object>> {
     530             :  public:
     531             :   static inline bool IsMatch(Handle<Object> key, Object* other);
     532             :   static inline uint32_t Hash(Handle<Object> key);
     533             :   static inline uint32_t HashForObject(Handle<Object> key, Object* object);
     534             :   static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Object> key);
     535             :   static const int kPrefixSize = 0;
     536             :   static const int kEntrySize = entrysize;
     537             : };
     538             : 
     539             : // WeakHashTable maps keys that are arbitrary heap objects to heap object
     540             : // values. The table wraps the keys in weak cells and store values directly.
     541             : // Thus it references keys weakly and values strongly.
     542             : class WeakHashTable
     543             :     : public HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>> {
     544             :   typedef HashTable<WeakHashTable, WeakHashTableShape<2>, Handle<Object>>
     545             :       DerivedHashTable;
     546             : 
     547             :  public:
     548             :   DECLARE_CAST(WeakHashTable)
     549             : 
     550             :   // Looks up the value associated with the given key. The hole value is
     551             :   // returned in case the key is not present.
     552             :   Object* Lookup(Handle<HeapObject> key);
     553             : 
     554             :   // Adds (or overwrites) the value associated with the given key. Mapping a
     555             :   // key to the hole value causes removal of the whole entry.
     556             :   MUST_USE_RESULT static Handle<WeakHashTable> Put(Handle<WeakHashTable> table,
     557             :                                                    Handle<HeapObject> key,
     558             :                                                    Handle<HeapObject> value);
     559             : 
     560             :   static Handle<FixedArray> GetValues(Handle<WeakHashTable> table);
     561             : 
     562             :  private:
     563             :   friend class MarkCompactCollector;
     564             : 
     565             :   void AddEntry(int entry, Handle<WeakCell> key, Handle<HeapObject> value);
     566             : 
     567             :   // Returns the index to the value of an entry.
     568             :   static inline int EntryToValueIndex(int entry) {
     569     2130517 :     return EntryToIndex(entry) + 1;
     570             :   }
     571             : };
     572             : 
     573             : // OrderedHashTableIterator is an iterator that iterates over the keys and
     574             : // values of an OrderedHashTable.
     575             : //
     576             : // The iterator has a reference to the underlying OrderedHashTable data,
     577             : // [table], as well as the current [index] the iterator is at.
     578             : //
     579             : // When the OrderedHashTable is rehashed it adds a reference from the old table
     580             : // to the new table as well as storing enough data about the changes so that the
     581             : // iterator [index] can be adjusted accordingly.
     582             : //
     583             : // When the [Next] result from the iterator is requested, the iterator checks if
     584             : // there is a newer table that it needs to transition to.
     585             : template <class Derived, class TableType>
     586             : class OrderedHashTableIterator : public JSObject {
     587             :  public:
     588             :   // [table]: the backing hash table mapping keys to values.
     589             :   DECL_ACCESSORS(table, Object)
     590             : 
     591             :   // [index]: The index into the data table.
     592             :   DECL_ACCESSORS(index, Object)
     593             : 
     594             :   // [kind]: The kind of iteration this is. One of the [Kind] enum values.
     595             :   DECL_ACCESSORS(kind, Object)
     596             : 
     597             : #ifdef OBJECT_PRINT
     598             :   void OrderedHashTableIteratorPrint(std::ostream& os);  // NOLINT
     599             : #endif
     600             : 
     601             :   static const int kTableOffset = JSObject::kHeaderSize;
     602             :   static const int kIndexOffset = kTableOffset + kPointerSize;
     603             :   static const int kKindOffset = kIndexOffset + kPointerSize;
     604             :   static const int kSize = kKindOffset + kPointerSize;
     605             : 
     606             :   enum Kind { kKindKeys = 1, kKindValues = 2, kKindEntries = 3 };
     607             : 
     608             :   // Whether the iterator has more elements. This needs to be called before
     609             :   // calling |CurrentKey| and/or |CurrentValue|.
     610             :   bool HasMore();
     611             : 
     612             :   // Move the index forward one.
     613       30579 :   void MoveNext() { set_index(Smi::FromInt(Smi::cast(index())->value() + 1)); }
     614             : 
     615             :   // Populates the array with the next key and value and then moves the iterator
     616             :   // forward.
     617             :   // This returns the |kind| or 0 if the iterator is already at the end.
     618             :   Smi* Next(JSArray* value_array);
     619             : 
     620             :   // Returns the current key of the iterator. This should only be called when
     621             :   // |HasMore| returns true.
     622             :   inline Object* CurrentKey();
     623             : 
     624             :  private:
     625             :   // Transitions the iterator to the non obsolete backing store. This is a NOP
     626             :   // if the [table] is not obsolete.
     627             :   void Transition();
     628             : 
     629             :   DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator);
     630             : };
     631             : 
     632             : class JSSetIterator
     633             :     : public OrderedHashTableIterator<JSSetIterator, OrderedHashSet> {
     634             :  public:
     635             :   // Dispatched behavior.
     636             :   DECLARE_PRINTER(JSSetIterator)
     637             :   DECLARE_VERIFIER(JSSetIterator)
     638             : 
     639             :   DECLARE_CAST(JSSetIterator)
     640             : 
     641             :   // Called by |Next| to populate the array. This allows the subclasses to
     642             :   // populate the array differently.
     643             :   inline void PopulateValueArray(FixedArray* array);
     644             : 
     645             :  private:
     646             :   DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator);
     647             : };
     648             : 
     649             : class JSMapIterator
     650             :     : public OrderedHashTableIterator<JSMapIterator, OrderedHashMap> {
     651             :  public:
     652             :   // Dispatched behavior.
     653             :   DECLARE_PRINTER(JSMapIterator)
     654             :   DECLARE_VERIFIER(JSMapIterator)
     655             : 
     656             :   DECLARE_CAST(JSMapIterator)
     657             : 
     658             :   // Called by |Next| to populate the array. This allows the subclasses to
     659             :   // populate the array differently.
     660             :   inline void PopulateValueArray(FixedArray* array);
     661             : 
     662             :  private:
     663             :   // Returns the current value of the iterator. This should only be called when
     664             :   // |HasMore| returns true.
     665             :   inline Object* CurrentValue();
     666             : 
     667             :   DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator);
     668             : };
     669             : 
     670             : }  // namespace internal
     671             : }  // namespace v8
     672             : 
     673             : #include "src/objects/object-macros-undef.h"
     674             : 
     675             : #endif  // V8_OBJECTS_HASH_TABLE_H_

Generated by: LCOV version 1.10