1 // Copyright 2016 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_ZONE_ZONE_HANDLE_SET_H_
6 #define V8_ZONE_ZONE_HANDLE_SET_H_
7
8 #include "src/handles/handles.h"
9 #include "src/zone/zone-containers.h"
10 #include "src/zone/zone.h"
11
12 namespace v8 {
13 namespace internal {
14
15 template <typename T>
16 class ZoneHandleSet final {
17 public:
ZoneHandleSet()18 ZoneHandleSet() : data_(kEmptyTag) {}
ZoneHandleSet(Handle<T> handle)19 explicit ZoneHandleSet(Handle<T> handle)
20 : data_(handle.address() | kSingletonTag) {
21 DCHECK(IsAligned(handle.address(), kPointerAlignment));
22 }
23
is_empty()24 bool is_empty() const { return data_ == kEmptyTag; }
25
size()26 size_t size() const {
27 if ((data_ & kTagMask) == kEmptyTag) return 0;
28 if ((data_ & kTagMask) == kSingletonTag) return 1;
29 return list()->size();
30 }
31
at(size_t i)32 Handle<T> at(size_t i) const {
33 DCHECK_NE(kEmptyTag, data_ & kTagMask);
34 if ((data_ & kTagMask) == kSingletonTag) {
35 DCHECK_EQ(0u, i);
36 return Handle<T>(singleton());
37 }
38 return Handle<T>(list()->at(static_cast<int>(i)));
39 }
40
41 Handle<T> operator[](size_t i) const { return at(i); }
42
insert(Handle<T> handle,Zone * zone)43 void insert(Handle<T> handle, Zone* zone) {
44 Address* const value = reinterpret_cast<Address*>(handle.address());
45 DCHECK(IsAligned(reinterpret_cast<Address>(value), kPointerAlignment));
46 if ((data_ & kTagMask) == kEmptyTag) {
47 data_ = reinterpret_cast<Address>(value) | kSingletonTag;
48 } else if ((data_ & kTagMask) == kSingletonTag) {
49 if (singleton() == value) return;
50 List* list = zone->New<List>(zone);
51 if (singleton() < value) {
52 list->push_back(singleton());
53 list->push_back(value);
54 } else {
55 list->push_back(value);
56 list->push_back(singleton());
57 }
58 DCHECK(IsAligned(reinterpret_cast<Address>(list), kPointerAlignment));
59 data_ = reinterpret_cast<Address>(list) | kListTag;
60 } else {
61 DCHECK_EQ(kListTag, data_ & kTagMask);
62 List const* const old_list = list();
63 for (size_t i = 0; i < old_list->size(); ++i) {
64 if (old_list->at(i) == value) return;
65 if (old_list->at(i) > value) break;
66 }
67 List* new_list = zone->New<List>(zone);
68 new_list->reserve(old_list->size() + 1);
69 size_t i = 0;
70 for (; i < old_list->size(); ++i) {
71 if (old_list->at(i) > value) break;
72 new_list->push_back(old_list->at(i));
73 }
74 new_list->push_back(value);
75 for (; i < old_list->size(); ++i) {
76 new_list->push_back(old_list->at(i));
77 }
78 DCHECK_EQ(old_list->size() + 1, new_list->size());
79 DCHECK(IsAligned(reinterpret_cast<Address>(new_list), kPointerAlignment));
80 data_ = reinterpret_cast<Address>(new_list) | kListTag;
81 }
82 }
83
contains(ZoneHandleSet<T> const & other)84 bool contains(ZoneHandleSet<T> const& other) const {
85 if (data_ == other.data_) return true;
86 if (data_ == kEmptyTag) return false;
87 if (other.data_ == kEmptyTag) return true;
88 if ((data_ & kTagMask) == kSingletonTag) return false;
89 DCHECK_EQ(kListTag, data_ & kTagMask);
90 List const* cached_list = list();
91 if ((other.data_ & kTagMask) == kSingletonTag) {
92 return std::find(cached_list->begin(), cached_list->end(),
93 other.singleton()) != cached_list->end();
94 }
95 DCHECK_EQ(kListTag, other.data_ & kTagMask);
96 // TODO(bmeurer): Optimize this case.
97 for (size_t i = 0; i < other.list()->size(); ++i) {
98 if (std::find(cached_list->begin(), cached_list->end(),
99 other.list()->at(i)) == cached_list->end()) {
100 return false;
101 }
102 }
103 return true;
104 }
105
contains(Handle<T> other)106 bool contains(Handle<T> other) const {
107 if (data_ == kEmptyTag) return false;
108 Address* other_address = reinterpret_cast<Address*>(other.address());
109 if ((data_ & kTagMask) == kSingletonTag) {
110 return singleton() == other_address;
111 }
112 DCHECK_EQ(kListTag, data_ & kTagMask);
113 return std::find(list()->begin(), list()->end(), other_address) !=
114 list()->end();
115 }
116
remove(Handle<T> handle,Zone * zone)117 void remove(Handle<T> handle, Zone* zone) {
118 // TODO(bmeurer): Optimize this case.
119 ZoneHandleSet<T> that;
120 for (size_t i = 0; i < size(); ++i) {
121 Handle<T> value = at(i);
122 if (value.address() != handle.address()) {
123 that.insert(value, zone);
124 }
125 }
126 std::swap(*this, that);
127 }
128
129 friend bool operator==(ZoneHandleSet<T> const& lhs,
130 ZoneHandleSet<T> const& rhs) {
131 if (lhs.data_ == rhs.data_) return true;
132 if ((lhs.data_ & kTagMask) == kListTag &&
133 (rhs.data_ & kTagMask) == kListTag) {
134 List const* const lhs_list = lhs.list();
135 List const* const rhs_list = rhs.list();
136 if (lhs_list->size() == rhs_list->size()) {
137 for (size_t i = 0; i < lhs_list->size(); ++i) {
138 if (lhs_list->at(i) != rhs_list->at(i)) return false;
139 }
140 return true;
141 }
142 }
143 return false;
144 }
145
146 friend bool operator!=(ZoneHandleSet<T> const& lhs,
147 ZoneHandleSet<T> const& rhs) {
148 return !(lhs == rhs);
149 }
150
hash_value(ZoneHandleSet<T> const & set)151 friend size_t hash_value(ZoneHandleSet<T> const& set) {
152 return static_cast<size_t>(set.data_);
153 }
154
155 class const_iterator;
156 inline const_iterator begin() const;
157 inline const_iterator end() const;
158
159 private:
160 using List = ZoneVector<Address*>;
161
list()162 List const* list() const {
163 DCHECK_EQ(kListTag, data_ & kTagMask);
164 return reinterpret_cast<List const*>(data_ - kListTag);
165 }
166
singleton()167 Address* singleton() const {
168 DCHECK_EQ(kSingletonTag, data_ & kTagMask);
169 return reinterpret_cast<Address*>(data_ - kSingletonTag);
170 }
171
172 enum Tag : Address {
173 kSingletonTag = 0,
174 kEmptyTag = 1,
175 kListTag = 2,
176 kTagMask = 3
177 };
178
179 STATIC_ASSERT(kTagMask < kPointerAlignment);
180
181 Address data_;
182 };
183
184 template <typename T>
185 std::ostream& operator<<(std::ostream& os, ZoneHandleSet<T> set) {
186 for (size_t i = 0; i < set.size(); ++i) {
187 if (i > 0) os << ", ";
188 os << set.at(i);
189 }
190 return os;
191 }
192
193 template <typename T>
194 class ZoneHandleSet<T>::const_iterator {
195 public:
196 using iterator_category = std::forward_iterator_tag;
197 using difference_type = std::ptrdiff_t;
198 using value_type = Handle<T>;
199 using reference = value_type;
200 using pointer = value_type*;
201
202 const_iterator(const const_iterator& other) = default;
203 const_iterator& operator=(const const_iterator& other) = default;
204
205 reference operator*() const { return (*set_)[current_]; }
206 bool operator==(const const_iterator& other) const {
207 return set_ == other.set_ && current_ == other.current_;
208 }
209 bool operator!=(const const_iterator& other) const {
210 return !(*this == other);
211 }
212 const_iterator& operator++() {
213 DCHECK(current_ < set_->size());
214 current_ += 1;
215 return *this;
216 }
217 const_iterator operator++(int);
218
219 private:
220 friend class ZoneHandleSet<T>;
221
const_iterator(const ZoneHandleSet<T> * set,size_t current)222 explicit const_iterator(const ZoneHandleSet<T>* set, size_t current)
223 : set_(set), current_(current) {}
224
225 const ZoneHandleSet<T>* set_;
226 size_t current_;
227 };
228
229 template <typename T>
begin()230 typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::begin() const {
231 return ZoneHandleSet<T>::const_iterator(this, 0);
232 }
233
234 template <typename T>
end()235 typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::end() const {
236 return ZoneHandleSet<T>::const_iterator(this, size());
237 }
238
239 } // namespace internal
240 } // namespace v8
241
242 #endif // V8_ZONE_ZONE_HANDLE_SET_H_
243