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.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_(bit_cast<intptr_t>(handle.address()) | kSingletonTag) {
21 DCHECK(IsAligned(bit_cast<intptr_t>(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 T** const value = bit_cast<T**>(handle.address());
45 DCHECK(IsAligned(bit_cast<intptr_t>(value), kPointerAlignment));
46 if ((data_ & kTagMask) == kEmptyTag) {
47 data_ = bit_cast<intptr_t>(value) | kSingletonTag;
48 } else if ((data_ & kTagMask) == kSingletonTag) {
49 if (singleton() == value) return;
50 List* list = new (zone->New(sizeof(List))) 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(bit_cast<intptr_t>(list), kPointerAlignment));
59 data_ = bit_cast<intptr_t>(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 = new (zone->New(sizeof(List))) 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(bit_cast<intptr_t>(new_list), kPointerAlignment));
80 data_ = bit_cast<intptr_t>(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 if ((data_ & kTagMask) == kSingletonTag) {
109 return singleton() == bit_cast<T**>(other.address());
110 }
111 DCHECK_EQ(kListTag, data_ & kTagMask);
112 return std::find(list()->begin(), list()->end(),
113 bit_cast<T**>(other.address())) != list()->end();
114 }
115
remove(Handle<T> handle,Zone * zone)116 void remove(Handle<T> handle, Zone* zone) {
117 // TODO(bmeurer): Optimize this case.
118 ZoneHandleSet<T> that;
119 for (size_t i = 0; i < size(); ++i) {
120 Handle<T> value = at(i);
121 if (value.address() != handle.address()) {
122 that.insert(value, zone);
123 }
124 }
125 std::swap(*this, that);
126 }
127
128 friend bool operator==(ZoneHandleSet<T> const& lhs,
129 ZoneHandleSet<T> const& rhs) {
130 if (lhs.data_ == rhs.data_) return true;
131 if ((lhs.data_ & kTagMask) == kListTag &&
132 (rhs.data_ & kTagMask) == kListTag) {
133 List const* const lhs_list = lhs.list();
134 List const* const rhs_list = rhs.list();
135 if (lhs_list->size() == rhs_list->size()) {
136 for (size_t i = 0; i < lhs_list->size(); ++i) {
137 if (lhs_list->at(i) != rhs_list->at(i)) return false;
138 }
139 return true;
140 }
141 }
142 return false;
143 }
144
145 friend bool operator!=(ZoneHandleSet<T> const& lhs,
146 ZoneHandleSet<T> const& rhs) {
147 return !(lhs == rhs);
148 }
149
hash_value(ZoneHandleSet<T> const & set)150 friend size_t hash_value(ZoneHandleSet<T> const& set) {
151 return static_cast<size_t>(set.data_);
152 }
153
154 class const_iterator;
155 inline const_iterator begin() const;
156 inline const_iterator end() const;
157
158 private:
159 typedef ZoneVector<T**> List;
160
list()161 List const* list() const {
162 DCHECK_EQ(kListTag, data_ & kTagMask);
163 return bit_cast<List const*>(data_ - kListTag);
164 }
165
singleton()166 T** singleton() const {
167 DCHECK_EQ(kSingletonTag, data_ & kTagMask);
168 return bit_cast<T**>(data_ - kSingletonTag);
169 }
170
171 enum Tag : intptr_t {
172 kSingletonTag = 0,
173 kEmptyTag = 1,
174 kListTag = 2,
175 kTagMask = 3
176 };
177
178 STATIC_ASSERT(kTagMask < kPointerAlignment);
179
180 intptr_t data_;
181 };
182
183 template <typename T>
184 std::ostream& operator<<(std::ostream& os, ZoneHandleSet<T> set) {
185 for (size_t i = 0; i < set.size(); ++i) {
186 if (i > 0) os << ", ";
187 os << set.at(i);
188 }
189 return os;
190 }
191
192 template <typename T>
193 class ZoneHandleSet<T>::const_iterator {
194 public:
195 typedef std::forward_iterator_tag iterator_category;
196 typedef std::ptrdiff_t difference_type;
197 typedef Handle<T> value_type;
198 typedef value_type reference;
199 typedef value_type* pointer;
200
const_iterator(const const_iterator & other)201 const_iterator(const const_iterator& other)
202 : set_(other.set_), current_(other.current_) {}
203
204 reference operator*() const { return (*set_)[current_]; }
205 bool operator==(const const_iterator& other) const {
206 return set_ == other.set_ && current_ == other.current_;
207 }
208 bool operator!=(const const_iterator& other) const {
209 return !(*this == other);
210 }
211 const_iterator& operator++() {
212 DCHECK(current_ < set_->size());
213 current_ += 1;
214 return *this;
215 }
216 const_iterator operator++(int);
217
218 private:
219 friend class ZoneHandleSet<T>;
220
const_iterator(const ZoneHandleSet<T> * set,size_t current)221 explicit const_iterator(const ZoneHandleSet<T>* set, size_t current)
222 : set_(set), current_(current) {}
223
224 const ZoneHandleSet<T>* set_;
225 size_t current_;
226 };
227
228 template <typename T>
begin()229 typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::begin() const {
230 return ZoneHandleSet<T>::const_iterator(this, 0);
231 }
232
233 template <typename T>
end()234 typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::end() const {
235 return ZoneHandleSet<T>::const_iterator(this, size());
236 }
237
238 } // namespace internal
239 } // namespace v8
240
241 #endif // V8_ZONE_ZONE_HANDLE_SET_H_
242