src/identity-map.h

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