1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_HEAP_WEAK_TABLE_H_
6#define RUNTIME_VM_HEAP_WEAK_TABLE_H_
7
8#include "vm/globals.h"
9
10#include "platform/assert.h"
11#include "vm/lockers.h"
12#include "vm/raw_object.h"
13
14namespace dart {
15
16class WeakTable {
17 public:
18 static constexpr intptr_t kNoValue = 0;
19
20 WeakTable() : size_(kMinSize), used_(0), count_(0) {
21 ASSERT(Utils::IsPowerOfTwo(size_));
22 data_ = reinterpret_cast<intptr_t*>(calloc(size_, kEntrySize * kWordSize));
23 }
24 explicit WeakTable(intptr_t size) : used_(0), count_(0) {
25 ASSERT(size >= 0);
26 ASSERT(Utils::IsPowerOfTwo(kMinSize));
27 if (size < kMinSize) {
28 size = kMinSize;
29 }
30 // Get a max size that avoids overflows.
31 const intptr_t kMaxSize =
32 (kIntptrOne << (kBitsPerWord - 2)) / (kEntrySize * kWordSize);
33 ASSERT(Utils::IsPowerOfTwo(kMaxSize));
34 if (size > kMaxSize) {
35 size = kMaxSize;
36 }
37 size_ = size;
38 ASSERT(Utils::IsPowerOfTwo(size_));
39 data_ = reinterpret_cast<intptr_t*>(calloc(size_, kEntrySize * kWordSize));
40 }
41
42 ~WeakTable() { free(data_); }
43
44 static WeakTable* NewFrom(WeakTable* original) {
45 return new WeakTable(SizeFor(original->count(), original->size()));
46 }
47
48 intptr_t size() const { return size_; }
49 intptr_t used() const { return used_; }
50 intptr_t count() const { return count_; }
51
52 // The following methods can be called concurrently and are guarded by a lock.
53
54 intptr_t GetValue(ObjectPtr key) {
55 MutexLocker ml(&mutex_);
56 return GetValueExclusive(key);
57 }
58
59 void SetValue(ObjectPtr key, intptr_t val) {
60 MutexLocker ml(&mutex_);
61 return SetValueExclusive(key, val);
62 }
63
64 // The following "exclusive" methods must only be called from call sites
65 // which are known to have exclusive access to the weak table.
66 //
67 // This is mostly limited to GC related code (e.g. scavenger, marker, ...)
68
69 bool IsValidEntryAtExclusive(intptr_t i) const {
70 ASSERT((ValueAtExclusive(i) == 0 &&
71 (ObjectAtExclusive(i) == nullptr ||
72 data_[ObjectIndex(i)] == kDeletedEntry)) ||
73 (ValueAtExclusive(i) != 0 && ObjectAtExclusive(i) != nullptr &&
74 data_[ObjectIndex(i)] != kDeletedEntry));
75 return (data_[ValueIndex(i)] != 0);
76 }
77
78 void InvalidateAtExclusive(intptr_t i) {
79 ASSERT(IsValidEntryAtExclusive(i));
80 SetValueAt(i, 0);
81 }
82
83 ObjectPtr ObjectAtExclusive(intptr_t i) const {
84 ASSERT(i >= 0);
85 ASSERT(i < size());
86 return static_cast<ObjectPtr>(data_[ObjectIndex(i)]);
87 }
88
89 intptr_t ValueAtExclusive(intptr_t i) const {
90 ASSERT(i >= 0);
91 ASSERT(i < size());
92 return data_[ValueIndex(i)];
93 }
94
95 void SetValueExclusive(ObjectPtr key, intptr_t val);
96
97 intptr_t GetValueExclusive(ObjectPtr key) const {
98 intptr_t mask = size() - 1;
99 intptr_t idx = Hash(key) & mask;
100 ObjectPtr obj = ObjectAtExclusive(idx);
101 while (obj != nullptr) {
102 if (obj == key) {
103 return ValueAtExclusive(idx);
104 }
105 idx = (idx + 1) & mask;
106 obj = ObjectAtExclusive(idx);
107 }
108 ASSERT(ValueAtExclusive(idx) == 0);
109 return kNoValue;
110 }
111
112 // Removes and returns the value associated with |key|. Returns 0 if there is
113 // no value associated with |key|.
114 intptr_t RemoveValueExclusive(ObjectPtr key) {
115 intptr_t mask = size() - 1;
116 intptr_t idx = Hash(key) & mask;
117 ObjectPtr obj = ObjectAtExclusive(idx);
118 while (obj != nullptr) {
119 if (obj == key) {
120 intptr_t result = ValueAtExclusive(idx);
121 InvalidateAtExclusive(idx);
122 return result;
123 }
124 idx = (idx + 1) & mask;
125 obj = ObjectAtExclusive(idx);
126 }
127 ASSERT(ValueAtExclusive(idx) == 0);
128 return kNoValue;
129 }
130
131 void Forward(ObjectPointerVisitor* visitor);
132
133 void Reset();
134
135 void MergeFrom(WeakTable* donor);
136
137 private:
138 enum {
139 kObjectOffset = 0,
140 kValueOffset,
141 kEntrySize,
142 };
143
144 static const intptr_t kDeletedEntry = 1; // Equivalent to a tagged NULL.
145 static const intptr_t kMinSize = 8;
146
147 static intptr_t SizeFor(intptr_t count, intptr_t size);
148 static intptr_t LimitFor(intptr_t size) {
149 // Maintain a maximum of 75% fill rate.
150 return 3 * (size / 4);
151 }
152 intptr_t limit() const { return LimitFor(size()); }
153
154 intptr_t index(intptr_t i) const { return i * kEntrySize; }
155
156 void set_used(intptr_t val) {
157 ASSERT(val <= limit());
158 used_ = val;
159 }
160
161 void set_count(intptr_t val) {
162 ASSERT(val <= limit());
163 ASSERT(val <= used());
164 count_ = val;
165 }
166
167 intptr_t ObjectIndex(intptr_t i) const { return index(i) + kObjectOffset; }
168
169 intptr_t ValueIndex(intptr_t i) const { return index(i) + kValueOffset; }
170
171 ObjectPtr* ObjectPointerAt(intptr_t i) const {
172 ASSERT(i >= 0);
173 ASSERT(i < size());
174 return reinterpret_cast<ObjectPtr*>(&data_[ObjectIndex(i)]);
175 }
176
177 void SetObjectAt(intptr_t i, ObjectPtr key) {
178 ASSERT(i >= 0);
179 ASSERT(i < size());
180 data_[ObjectIndex(i)] = static_cast<intptr_t>(key);
181 }
182
183 void SetValueAt(intptr_t i, intptr_t val) {
184 ASSERT(i >= 0);
185 ASSERT(i < size());
186 // Setting a value of 0 is equivalent to invalidating the entry.
187 if (val == 0) {
188 data_[ObjectIndex(i)] = kDeletedEntry;
189 set_count(count() - 1);
190 }
191 data_[ValueIndex(i)] = val;
192 }
193
194 void Rehash();
195
196 static intptr_t Hash(ObjectPtr key) {
197 return static_cast<uintptr_t>(key) * 92821;
198 }
199
200 Mutex mutex_;
201
202 // data_ contains size_ tuples of key/value.
203 intptr_t* data_;
204 // size_ keeps the number of entries in data_. used_ maintains the number of
205 // non-NULL entries and will trigger rehashing if needed. count_ stores the
206 // number valid entries, and will determine the size_ after rehashing.
207 intptr_t size_;
208 intptr_t used_;
209 intptr_t count_;
210
211 DISALLOW_COPY_AND_ASSIGN(WeakTable);
212};
213
214} // namespace dart
215
216#endif // RUNTIME_VM_HEAP_WEAK_TABLE_H_
217