Home | History | Annotate | Download | only in src 
      1 // Copyright 2015 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_IDENTITY_MAP_H_
      6 #define V8_IDENTITY_MAP_H_
      7 
      8 #include "src/base/functional.h"
      9 #include "src/handles.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 
     14 // Forward declarations.
     15 class Heap;
     16 class Zone;
     17 
     18 // Base class of identity maps contains shared code for all template
     19 // instantions.
     20 class IdentityMapBase {
     21  protected:
     22   // Allow Tester to access internals, including changing the address of objects
     23   // within the {keys_} array in order to simulate a moving GC.
     24   friend class IdentityMapTester;
     25 
     26   typedef void** RawEntry;
     27 
     28   IdentityMapBase(Heap* heap, Zone* zone)
     29       : heap_(heap),
     30         zone_(zone),
     31         gc_counter_(-1),
     32         size_(0),
     33         mask_(0),
     34         keys_(nullptr),
     35         values_(nullptr) {}
     36   ~IdentityMapBase();
     37 
     38   RawEntry GetEntry(Object* key);
     39   RawEntry FindEntry(Object* key);
     40   void Clear();
     41 
     42  private:
     43   // Internal implementation should not be called directly by subclasses.
     44   int LookupIndex(Object* address);
     45   int InsertIndex(Object* address);
     46   void Rehash();
     47   void Resize();
     48   RawEntry Lookup(Object* key);
     49   RawEntry Insert(Object* key);
     50   int Hash(Object* address);
     51 
     52   base::hash<uintptr_t> hasher_;
     53   Heap* heap_;
     54   Zone* zone_;
     55   int gc_counter_;
     56   int size_;
     57   int mask_;
     58   Object** keys_;
     59   void** values_;
     60 };
     61 
     62 // Implements an identity map from object addresses to a given value type {V}.
     63 // The map is robust w.r.t. garbage collection by synchronization with the
     64 // supplied {heap}.
     65 //  * Keys are treated as strong roots.
     66 //  * SMIs are valid keys, except SMI #0.
     67 //  * The value type {V} must be reinterpret_cast'able to {void*}
     68 //  * The value type {V} must not be a heap type.
     69 template <typename V>
     70 class IdentityMap : public IdentityMapBase {
     71  public:
     72   IdentityMap(Heap* heap, Zone* zone) : IdentityMapBase(heap, zone) {}
     73 
     74   // Searches this map for the given key using the object's address
     75   // as the identity, returning:
     76   //    found => a pointer to the storage location for the value
     77   //    not found => a pointer to a new storage location for the value
     78   V* Get(Handle<Object> key) { return Get(*key); }
     79   V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); }
     80 
     81   // Searches this map for the given key using the object's address
     82   // as the identity, returning:
     83   //    found => a pointer to the storage location for the value
     84   //    not found => {nullptr}
     85   V* Find(Handle<Object> key) { return Find(*key); }
     86   V* Find(Object* key) { return reinterpret_cast<V*>(FindEntry(key)); }
     87 
     88   // Set the value for the given key.
     89   void Set(Handle<Object> key, V v) { Set(*key, v); }
     90   void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; }
     91 
     92   // Removes all elements from the map.
     93   void Clear() { IdentityMapBase::Clear(); }
     94 };
     95 }  // namespace internal
     96 }  // namespace v8
     97 
     98 #endif  // V8_IDENTITY_MAP_H_
     99