1// Copyright (c) 2020, 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_PORT_SET_H_
6#define RUNTIME_VM_PORT_SET_H_
7
8#include "include/dart_api.h"
9
10#include "platform/globals.h"
11#include "platform/utils.h"
12
13namespace dart {
14
15template <typename T /* :public PortSet<T>::Entry */>
16class PortSet {
17 public:
18 static constexpr Dart_Port kFreePort = static_cast<Dart_Port>(0);
19 static constexpr Dart_Port kDeletedPort = static_cast<Dart_Port>(3);
20
21 struct Entry {
22 Entry() : port(kFreePort) {}
23
24 // Free entries have set this to 0.
25 Dart_Port port;
26 };
27
28 class Iterator {
29 public:
30 Iterator(PortSet<T>* ports, intptr_t index) : ports_(ports), index_(index) {
31#if defined(DEBUG)
32 dirty_counter_ = ports_->dirty_counter_;
33#endif
34 }
35
36 DART_FORCE_INLINE T& operator->() const {
37 ASSERT(index_ >= 0 && index_ < ports_->capacity_);
38 DEBUG_ASSERT(!WasModified());
39 return ports_->map_[index_];
40 }
41 DART_FORCE_INLINE T& operator*() const {
42 ASSERT(index_ >= 0 && index_ < ports_->capacity_);
43 DEBUG_ASSERT(!WasModified());
44 return ports_->map_[index_];
45 }
46
47 DART_FORCE_INLINE bool operator==(const Iterator& other) const {
48 DEBUG_ASSERT(!WasModified());
49 return ports_ == other.ports_ && index_ == other.index_;
50 }
51
52 DART_FORCE_INLINE bool operator!=(const Iterator& other) const {
53 DEBUG_ASSERT(!WasModified());
54 return !(*this == other);
55 }
56
57 DART_FORCE_INLINE Iterator& operator++() {
58 DEBUG_ASSERT(!WasModified());
59 index_++;
60 while (index_ < ports_->capacity_) {
61 const Dart_Port port = ports_->map_[index_].port;
62 if (port == kFreePort || port == kDeletedPort) {
63 index_++;
64 continue;
65 } else {
66 break;
67 }
68 }
69 return *this;
70 }
71
72 // The caller must ensure to call [PortSet::Rebalance] once the iterator is
73 // not used anymore.
74 DART_FORCE_INLINE void Delete() {
75 DEBUG_ASSERT(!WasModified());
76 ports_->map_[index_] = T();
77 ports_->map_[index_].port = kDeletedPort;
78 ports_->used_--;
79 ports_->deleted_++;
80 }
81
82 private:
83 friend class PortSet;
84
85#if defined(DEBUG)
86 // Whether the underlying [PortSet] was modified in a way that would render
87 // the iterator unusable.
88 bool WasModified() const {
89 return dirty_counter_ != ports_->dirty_counter_;
90 }
91#endif
92
93 PortSet<T>* ports_;
94 intptr_t index_ = 0;
95#if defined(DEBUG)
96 intptr_t dirty_counter_ = 0;
97#endif
98 };
99
100 PortSet() {
101 static const intptr_t kInitialCapacity = 8;
102 ASSERT(Utils::IsPowerOfTwo(kInitialCapacity));
103 map_ = new T[kInitialCapacity];
104 capacity_ = kInitialCapacity;
105 }
106 ~PortSet() {
107 delete[] map_;
108 map_ = nullptr;
109 }
110
111 bool IsEmpty() const { return used_ == 0; }
112
113 DART_FORCE_INLINE Iterator begin() {
114 for (intptr_t i = 0; i < capacity_; ++i) {
115 auto& entry = map_[i];
116 if (entry.port != kFreePort && entry.port != kDeletedPort) {
117 return Iterator(this, i);
118 }
119 }
120 return end();
121 }
122
123 DART_FORCE_INLINE Iterator end() { return Iterator(this, capacity_); }
124
125 void Insert(const T& entry) {
126 // Search for the first unused slot. Make use of the knowledge that here is
127 // currently no port with this id in the port map.
128 ASSERT(FindIndexOfPort(entry.port) < 0);
129 intptr_t index = entry.port % capacity_;
130 T cur = map_[index];
131
132 // Stop the search at the first found unused (free or deleted) slot.
133 while (cur.port != kFreePort && cur.port != kDeletedPort) {
134 index = (index + 1) % capacity_;
135 cur = map_[index];
136 }
137
138 // Insert the newly created port at the index.
139 ASSERT(map_[index].port == kFreePort || map_[index].port == kDeletedPort);
140 if (map_[index].port == kDeletedPort) {
141 deleted_--;
142 }
143 map_[index] = entry;
144 ASSERT(FindIndexOfPort(entry.port) >= 0);
145
146 // Increment number of used slots and grow if necessary.
147 used_++;
148 MaintainInvariants();
149
150#if defined(DEBUG)
151 dirty_counter_++;
152#endif
153 }
154
155 Iterator TryLookup(Dart_Port port) {
156 const intptr_t index = FindIndexOfPort(port);
157 if (index >= 0) return Iterator(this, index);
158 return Iterator(this, capacity_);
159 }
160
161 bool Contains(Dart_Port port) { return FindIndexOfPort(port) >= 0; }
162
163 // To be called if an iterator was used to delete an entry.
164 void Rebalance() { MaintainInvariants(); }
165
166 private:
167 intptr_t FindIndexOfPort(Dart_Port port) {
168 // ILLEGAL_PORT (0) is used as a sentinel value in Entry.port. The loop
169 // below could return the index to a deleted port when we are searching for
170 // port id ILLEGAL_PORT. Return -1 immediately to indicate the port
171 // does not exist.
172 if (port == ILLEGAL_PORT) {
173 return -1;
174 }
175 ASSERT(port != ILLEGAL_PORT);
176 intptr_t index = port % capacity_;
177 intptr_t start_index = index;
178 T entry = map_[index];
179 while (entry.port != kFreePort) {
180 if (entry.port == port) {
181 return index;
182 }
183 index = (index + 1) % capacity_;
184 // Prevent endless loops.
185 ASSERT(index != start_index);
186 entry = map_[index];
187 }
188 return -1;
189 }
190
191 void MaintainInvariants() {
192 const intptr_t empty = capacity_ - used_ - deleted_;
193 if (used_ > ((capacity_ / 4) * 3)) {
194 // Grow the port map.
195 Rehash(capacity_ * 2);
196 } else if (empty < deleted_) {
197 // Rehash without growing the table to flush the deleted slots out of the
198 // map.
199 Rehash(capacity_);
200 }
201 }
202
203 void Rehash(intptr_t new_capacity) {
204 T* new_ports = new T[new_capacity];
205
206 for (auto entry : *this) {
207 intptr_t new_index = entry.port % new_capacity;
208 while (new_ports[new_index].port != 0) {
209 new_index = (new_index + 1) % new_capacity;
210 }
211 new_ports[new_index] = entry;
212 }
213 delete[] map_;
214 map_ = new_ports;
215 capacity_ = new_capacity;
216 deleted_ = 0;
217
218#if defined(DEBUG)
219 dirty_counter_++;
220#endif
221 }
222
223 T* map_ = nullptr;
224 intptr_t capacity_ = 0;
225 intptr_t used_ = 0;
226 intptr_t deleted_ = 0;
227
228#if defined(DEBUG)
229 intptr_t dirty_counter_ = 0;
230#endif
231};
232
233} // namespace dart
234
235#endif // RUNTIME_VM_PORT_SET_H_
236