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