identity-map.h 6.99 KB
Newer Older
1 2 3 4
// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#ifndef V8_UTILS_IDENTITY_MAP_H_
#define V8_UTILS_IDENTITY_MAP_H_
7

8 9
#include <type_traits>

10
#include "src/base/functional.h"
11
#include "src/handles/handles.h"
12
#include "src/objects/heap-object.h"
13 14 15 16

namespace v8 {
namespace internal {

17
// Forward declarations.
18
class Heap;
19
class StrongRootsEntry;
20

21 22 23 24 25 26
template <typename T>
struct IdentityMapFindResult {
  T* entry;
  bool already_exists;
};

27 28
// Base class of identity maps contains shared code for all template
// instantions.
29
class V8_EXPORT_PRIVATE IdentityMapBase {
30
 public:
31 32
  IdentityMapBase(const IdentityMapBase&) = delete;
  IdentityMapBase& operator=(const IdentityMapBase&) = delete;
33 34 35 36 37
  bool empty() const { return size_ == 0; }
  int size() const { return size_; }
  int capacity() const { return capacity_; }
  bool is_iterable() const { return is_iterable_; }

38 39 40 41 42
 protected:
  // Allow Tester to access internals, including changing the address of objects
  // within the {keys_} array in order to simulate a moving GC.
  friend class IdentityMapTester;

43
  using RawEntry = uintptr_t*;
44

45
  explicit IdentityMapBase(Heap* heap)
46 47 48
      : heap_(heap),
        gc_counter_(-1),
        size_(0),
49
        capacity_(0),
50 51
        mask_(0),
        keys_(nullptr),
52
        strong_roots_entry_(nullptr),
53 54 55
        values_(nullptr),
        is_iterable_(false) {}
  virtual ~IdentityMapBase();
56

57
  IdentityMapFindResult<uintptr_t> FindOrInsertEntry(Address key);
58
  RawEntry FindEntry(Address key) const;
59 60
  RawEntry InsertEntry(Address key);
  bool DeleteEntry(Address key, uintptr_t* deleted_value);
61
  void Clear();
62

63
  Address KeyAtIndex(int index) const;
64

65 66
  RawEntry EntryAtIndex(int index) const;
  int NextIndex(int index) const;
67 68 69 70

  void EnableIteration();
  void DisableIteration();

71 72
  virtual uintptr_t* NewPointerArray(size_t length) = 0;
  virtual void DeletePointerArray(uintptr_t* array, size_t length) = 0;
73

74 75
 private:
  // Internal implementation should not be called directly by subclasses.
76 77
  int ScanKeysFor(Address address, uint32_t hash) const;
  std::pair<int, bool> InsertKey(Address address, uint32_t hash);
78
  int Lookup(Address key) const;
79 80
  std::pair<int, bool> LookupOrInsert(Address key);
  bool DeleteIndex(int index, uintptr_t* deleted_value);
81
  void Rehash();
82
  void Resize(int new_capacity);
83
  uint32_t Hash(Address address) const;
84

85
  base::hash<uintptr_t> hasher_;
86 87 88
  Heap* heap_;
  int gc_counter_;
  int size_;
89
  int capacity_;
90
  int mask_;
91
  Address* keys_;
92
  StrongRootsEntry* strong_roots_entry_;
93
  uintptr_t* values_;
94
  bool is_iterable_;
95 96 97 98 99 100
};

// Implements an identity map from object addresses to a given value type {V}.
// The map is robust w.r.t. garbage collection by synchronization with the
// supplied {heap}.
//  * Keys are treated as strong roots.
101
//  * The value type {V} must be reinterpret_cast'able to {uintptr_t}
102
//  * The value type {V} must not be a heap type.
103
template <typename V, class AllocationPolicy>
104 105
class IdentityMap : public IdentityMapBase {
 public:
106 107 108 109
  STATIC_ASSERT(sizeof(V) <= sizeof(uintptr_t));
  STATIC_ASSERT(std::is_trivially_copyable<V>::value);
  STATIC_ASSERT(std::is_trivially_destructible<V>::value);

110 111 112
  explicit IdentityMap(Heap* heap,
                       AllocationPolicy allocator = AllocationPolicy())
      : IdentityMapBase(heap), allocator_(allocator) {}
113 114
  IdentityMap(const IdentityMap&) = delete;
  IdentityMap& operator=(const IdentityMap&) = delete;
115
  ~IdentityMap() override { Clear(); }
116 117 118

  // Searches this map for the given key using the object's address
  // as the identity, returning:
119 120 121 122 123 124 125 126 127
  //    found => a pointer to the storage location for the value, true
  //    not found => a pointer to a new storage location for the value, false
  IdentityMapFindResult<V> FindOrInsert(Handle<Object> key) {
    return FindOrInsert(*key);
  }
  IdentityMapFindResult<V> FindOrInsert(Object key) {
    auto raw = FindOrInsertEntry(key.ptr());
    return {reinterpret_cast<V*>(raw.entry), raw.already_exists};
  }
128 129 130 131 132

  // Searches this map for the given key using the object's address
  // as the identity, returning:
  //    found => a pointer to the storage location for the value
  //    not found => {nullptr}
133
  V* Find(Handle<Object> key) const { return Find(*key); }
134
  V* Find(Object key) const {
135 136
    return reinterpret_cast<V*>(FindEntry(key.ptr()));
  }
137

138 139 140 141 142
  // Insert the value for the given key. The key must not have previously
  // existed.
  void Insert(Handle<Object> key, V v) { Insert(*key, v); }
  void Insert(Object key, V v) {
    *reinterpret_cast<V*>(InsertEntry(key.ptr())) = v;
143
  }
144

145 146 147
  bool Delete(Handle<Object> key, V* deleted_value) {
    return Delete(*key, deleted_value);
  }
148
  bool Delete(Object key, V* deleted_value) {
149
    uintptr_t v;
150 151 152 153 154 155
    bool deleted_something = DeleteEntry(key.ptr(), &v);
    if (deleted_value != nullptr && deleted_something) {
      *deleted_value = *reinterpret_cast<V*>(&v);
    }
    return deleted_something;
  }
156

157 158
  // Removes all elements from the map.
  void Clear() { IdentityMapBase::Clear(); }
159 160 161 162 163 164 165 166 167 168

  // Iterator over IdentityMap. The IteratableScope used to create this Iterator
  // must be live for the duration of the iteration.
  class Iterator {
   public:
    Iterator& operator++() {
      index_ = map_->NextIndex(index_);
      return *this;
    }

169
    Object key() const { return Object(map_->KeyAtIndex(index_)); }
170 171 172 173 174 175
    V* entry() const {
      return reinterpret_cast<V*>(map_->EntryAtIndex(index_));
    }

    V* operator*() { return entry(); }
    V* operator->() { return entry(); }
176 177 178 179 180 181 182 183 184 185 186
    bool operator!=(const Iterator& other) { return index_ != other.index_; }

   private:
    Iterator(IdentityMap* map, int index) : map_(map), index_(index) {}

    IdentityMap* map_;
    int index_;

    friend class IdentityMap;
  };

187
  class V8_NODISCARD IteratableScope {
188 189 190 191 192
   public:
    explicit IteratableScope(IdentityMap* map) : map_(map) {
      CHECK(!map_->is_iterable());
      map_->EnableIteration();
    }
193 194
    IteratableScope(const IteratableScope&) = delete;
    IteratableScope& operator=(const IteratableScope&) = delete;
195 196 197 198 199 200 201 202 203 204 205 206 207
    ~IteratableScope() {
      CHECK(map_->is_iterable());
      map_->DisableIteration();
    }

    Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); }
    Iterator end() { return Iterator(map_, map_->capacity()); }

   private:
    IdentityMap* map_;
  };

 protected:
208 209 210 211 212
  // This struct is just a type tag for Zone::NewArray<T>(size_t) call.
  struct Buffer {};

  // TODO(ishell): consider removing virtual methods in favor of combining
  // IdentityMapBase and IdentityMap into one class. This would also save
213 214 215
  // space when sizeof(V) is less than sizeof(uintptr_t).
  uintptr_t* NewPointerArray(size_t length) override {
    return allocator_.template NewArray<uintptr_t, Buffer>(length);
216
  }
217 218
  void DeletePointerArray(uintptr_t* array, size_t length) override {
    allocator_.template DeleteArray<uintptr_t, Buffer>(array, length);
219 220 221 222
  }

 private:
  AllocationPolicy allocator_;
223
};
224

225 226
}  // namespace internal
}  // namespace v8
227

228
#endif  // V8_UTILS_IDENTITY_MAP_H_