LCOV - code coverage report
Current view: top level - src - identity-map.h (source / functions) Hit Total Coverage
Test: app.info Lines: 11 11 100.0 %
Date: 2017-04-26 Functions: 13 24 54.2 %

          Line data    Source code
       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             : 
      17             : // Base class of identity maps contains shared code for all template
      18             : // instantions.
      19             : class IdentityMapBase {
      20             :  public:
      21             :   bool empty() const { return size_ == 0; }
      22             :   int size() const { return size_; }
      23             :   int capacity() const { return capacity_; }
      24             :   bool is_iterable() const { return is_iterable_; }
      25             : 
      26             :  protected:
      27             :   // Allow Tester to access internals, including changing the address of objects
      28             :   // within the {keys_} array in order to simulate a moving GC.
      29             :   friend class IdentityMapTester;
      30             : 
      31             :   typedef void** RawEntry;
      32             : 
      33             :   explicit IdentityMapBase(Heap* heap)
      34             :       : heap_(heap),
      35             :         gc_counter_(-1),
      36             :         size_(0),
      37             :         capacity_(0),
      38             :         mask_(0),
      39             :         keys_(nullptr),
      40             :         values_(nullptr),
      41      546704 :         is_iterable_(false) {}
      42             :   virtual ~IdentityMapBase();
      43             : 
      44             :   RawEntry GetEntry(Object* key);
      45             :   RawEntry FindEntry(Object* key) const;
      46             :   void* DeleteEntry(Object* key);
      47             :   void Clear();
      48             : 
      49             :   V8_EXPORT_PRIVATE RawEntry EntryAtIndex(int index) const;
      50             :   V8_EXPORT_PRIVATE int NextIndex(int index) const;
      51             : 
      52             :   void EnableIteration();
      53             :   void DisableIteration();
      54             : 
      55             :   virtual void** NewPointerArray(size_t length) = 0;
      56             :   virtual void DeleteArray(void* array) = 0;
      57             : 
      58             :  private:
      59             :   // Internal implementation should not be called directly by subclasses.
      60             :   int ScanKeysFor(Object* address) const;
      61             :   int InsertKey(Object* address);
      62             :   int Lookup(Object* key) const;
      63             :   int LookupOrInsert(Object* key);
      64             :   void* DeleteIndex(int index);
      65             :   void Rehash();
      66             :   void Resize(int new_capacity);
      67             :   int Hash(Object* address) const;
      68             : 
      69             :   base::hash<uintptr_t> hasher_;
      70             :   Heap* heap_;
      71             :   int gc_counter_;
      72             :   int size_;
      73             :   int capacity_;
      74             :   int mask_;
      75             :   Object** keys_;
      76             :   void** values_;
      77             :   bool is_iterable_;
      78             : 
      79             :   DISALLOW_COPY_AND_ASSIGN(IdentityMapBase);
      80             : };
      81             : 
      82             : // Implements an identity map from object addresses to a given value type {V}.
      83             : // The map is robust w.r.t. garbage collection by synchronization with the
      84             : // supplied {heap}.
      85             : //  * Keys are treated as strong roots.
      86             : //  * The value type {V} must be reinterpret_cast'able to {void*}
      87             : //  * The value type {V} must not be a heap type.
      88             : template <typename V, class AllocationPolicy>
      89             : class IdentityMap : public IdentityMapBase {
      90             :  public:
      91             :   explicit IdentityMap(Heap* heap,
      92             :                        AllocationPolicy allocator = AllocationPolicy())
      93      546704 :       : IdentityMapBase(heap), allocator_(allocator) {}
      94     1089134 :   ~IdentityMap() override { Clear(); };
      95             : 
      96             :   // Searches this map for the given key using the object's address
      97             :   // as the identity, returning:
      98             :   //    found => a pointer to the storage location for the value
      99             :   //    not found => a pointer to a new storage location for the value
     100             :   V* Get(Handle<Object> key) { return Get(*key); }
     101    25651448 :   V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); }
     102             : 
     103             :   // Searches this map for the given key using the object's address
     104             :   // as the identity, returning:
     105             :   //    found => a pointer to the storage location for the value
     106             :   //    not found => {nullptr}
     107             :   V* Find(Handle<Object> key) const { return Find(*key); }
     108       23951 :   V* Find(Object* key) const { return reinterpret_cast<V*>(FindEntry(key)); }
     109             : 
     110             :   // Set the value for the given key.
     111             :   void Set(Handle<Object> key, V v) { Set(*key, v); }
     112        5978 :   void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; }
     113             : 
     114             :   V Delete(Handle<Object> key) { return Delete(*key); }
     115          28 :   V Delete(Object* key) { return reinterpret_cast<V>(DeleteEntry(key)); }
     116             : 
     117             :   // Removes all elements from the map.
     118      663788 :   void Clear() { IdentityMapBase::Clear(); }
     119             : 
     120             :   // Iterator over IdentityMap. The IteratableScope used to create this Iterator
     121             :   // must be live for the duration of the iteration.
     122             :   class Iterator {
     123             :    public:
     124             :     Iterator& operator++() {
     125             :       index_ = map_->NextIndex(index_);
     126             :       return *this;
     127             :     }
     128             : 
     129             :     V* operator*() { return reinterpret_cast<V*>(map_->EntryAtIndex(index_)); }
     130             :     V* operator->() { return reinterpret_cast<V*>(map_->EntryAtIndex(index_)); }
     131             :     bool operator!=(const Iterator& other) { return index_ != other.index_; }
     132             : 
     133             :    private:
     134             :     Iterator(IdentityMap* map, int index) : map_(map), index_(index) {}
     135             : 
     136             :     IdentityMap* map_;
     137             :     int index_;
     138             : 
     139             :     friend class IdentityMap;
     140             :   };
     141             : 
     142             :   class IteratableScope {
     143             :    public:
     144             :     explicit IteratableScope(IdentityMap* map) : map_(map) {
     145             :       CHECK(!map_->is_iterable());
     146             :       map_->EnableIteration();
     147             :     }
     148             :     ~IteratableScope() {
     149             :       CHECK(map_->is_iterable());
     150             :       map_->DisableIteration();
     151             :     }
     152             : 
     153             :     Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); }
     154             :     Iterator end() { return Iterator(map_, map_->capacity()); }
     155             : 
     156             :    private:
     157             :     IdentityMap* map_;
     158             :     DISALLOW_COPY_AND_ASSIGN(IteratableScope);
     159             :   };
     160             : 
     161             :  protected:
     162     2431930 :   void** NewPointerArray(size_t length) override {
     163     4863860 :     return static_cast<void**>(allocator_.New(sizeof(void*) * length));
     164             :   }
     165     2434439 :   void DeleteArray(void* array) override { allocator_.Delete(array); }
     166             : 
     167             :  private:
     168             :   AllocationPolicy allocator_;
     169             :   DISALLOW_COPY_AND_ASSIGN(IdentityMap);
     170             : };
     171             : 
     172             : }  // namespace internal
     173             : }  // namespace v8
     174             : 
     175             : #endif  // V8_IDENTITY_MAP_H_

Generated by: LCOV version 1.10