Line data Source code
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:
18 771724 : ZoneHandleSet() : data_(kEmptyTag) {}
19 : explicit ZoneHandleSet(Handle<T> handle)
20 174323 : : data_(handle.address() | kSingletonTag) {
21 : DCHECK(IsAligned(handle.address(), kPointerAlignment));
22 : }
23 :
24 : bool is_empty() const { return data_ == kEmptyTag; }
25 :
26 : size_t size() const {
27 613506 : if ((data_ & kTagMask) == kEmptyTag) return 0;
28 613505 : if ((data_ & kTagMask) == kSingletonTag) return 1;
29 36275 : return list()->size();
30 : }
31 :
32 499731 : Handle<T> at(size_t i) const {
33 : DCHECK_NE(kEmptyTag, data_ & kTagMask);
34 499731 : if ((data_ & kTagMask) == kSingletonTag) {
35 : DCHECK_EQ(0u, i);
36 450139 : return Handle<T>(singleton());
37 : }
38 99184 : return Handle<T>(list()->at(static_cast<int>(i)));
39 : }
40 :
41 386710 : Handle<T> operator[](size_t i) const { return at(i); }
42 :
43 107655 : void insert(Handle<T> handle, Zone* zone) {
44 107655 : Address* const value = reinterpret_cast<Address*>(handle.address());
45 : DCHECK(IsAligned(reinterpret_cast<Address>(value), kPointerAlignment));
46 107655 : if ((data_ & kTagMask) == kEmptyTag) {
47 96305 : data_ = reinterpret_cast<Address>(value) | kSingletonTag;
48 11350 : } else if ((data_ & kTagMask) == kSingletonTag) {
49 10682 : if (singleton() == value) return;
50 9867 : List* list = new (zone->New(sizeof(List))) List(zone);
51 9867 : if (singleton() < value) {
52 19124 : list->push_back(singleton());
53 9562 : list->push_back(value);
54 : } else {
55 305 : list->push_back(value);
56 610 : list->push_back(singleton());
57 : }
58 : DCHECK(IsAligned(reinterpret_cast<Address>(list), kPointerAlignment));
59 9867 : data_ = reinterpret_cast<Address>(list) | kListTag;
60 : } else {
61 : DCHECK_EQ(kListTag, data_ & kTagMask);
62 : List const* const old_list = list();
63 6632 : for (size_t i = 0; i < old_list->size(); ++i) {
64 11064 : if (old_list->at(i) == value) return;
65 2274 : if (old_list->at(i) > value) break;
66 : }
67 1049 : List* new_list = new (zone->New(sizeof(List))) List(zone);
68 1049 : new_list->reserve(old_list->size() + 1);
69 : size_t i = 0;
70 6420 : for (; i < old_list->size(); ++i) {
71 2221 : if (old_list->at(i) > value) break;
72 2161 : new_list->push_back(old_list->at(i));
73 : }
74 1049 : new_list->push_back(value);
75 2324 : for (; i < old_list->size(); ++i) {
76 113 : 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 1049 : data_ = reinterpret_cast<Address>(new_list) | kListTag;
81 : }
82 : }
83 :
84 47709 : bool contains(ZoneHandleSet<T> const& other) const {
85 47709 : if (data_ == other.data_) return true;
86 3926 : if (data_ == kEmptyTag) return false;
87 3926 : if (other.data_ == kEmptyTag) return true;
88 3926 : if ((data_ & kTagMask) == kSingletonTag) return false;
89 : DCHECK_EQ(kListTag, data_ & kTagMask);
90 : List const* cached_list = list();
91 2105 : if ((other.data_ & kTagMask) == kSingletonTag) {
92 : return std::find(cached_list->begin(), cached_list->end(),
93 4496 : other.singleton()) != cached_list->end();
94 : }
95 : DCHECK_EQ(kListTag, other.data_ & kTagMask);
96 : // TODO(bmeurer): Optimize this case.
97 16114 : for (size_t i = 0; i < other.list()->size(); ++i) {
98 4064 : 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 :
106 4401 : bool contains(Handle<T> other) const {
107 4401 : if (data_ == kEmptyTag) return false;
108 4401 : Address* other_address = reinterpret_cast<Address*>(other.address());
109 4401 : if ((data_ & kTagMask) == kSingletonTag) {
110 4401 : return singleton() == other_address;
111 : }
112 : DCHECK_EQ(kListTag, data_ & kTagMask);
113 0 : return std::find(list()->begin(), list()->end(), other_address) !=
114 : list()->end();
115 : }
116 :
117 95 : void remove(Handle<T> handle, Zone* zone) {
118 : // TODO(bmeurer): Optimize this case.
119 : ZoneHandleSet<T> that;
120 388 : for (size_t i = 0; i < size(); ++i) {
121 99 : Handle<T> value = at(i);
122 99 : if (value.address() != handle.address()) {
123 4 : that.insert(value, zone);
124 : }
125 : }
126 : std::swap(*this, that);
127 95 : }
128 :
129 18314 : friend bool operator==(ZoneHandleSet<T> const& lhs,
130 : ZoneHandleSet<T> const& rhs) {
131 18314 : if (lhs.data_ == rhs.data_) return true;
132 8517 : 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 1359 : if (lhs_list->size() == rhs_list->size()) {
137 2509 : for (size_t i = 0; i < lhs_list->size(); ++i) {
138 2056 : 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 38 : return !(lhs == rhs);
149 : }
150 :
151 0 : friend size_t hash_value(ZoneHandleSet<T> const& set) {
152 0 : 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 : typedef ZoneVector<Address*> List;
161 :
162 : List const* list() const {
163 : DCHECK_EQ(kListTag, data_ & kTagMask);
164 95552 : return reinterpret_cast<List const*>(data_ - kListTag);
165 : }
166 :
167 : Address* singleton() const {
168 : DCHECK_EQ(kSingletonTag, data_ & kTagMask);
169 475104 : 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 : typedef std::forward_iterator_tag iterator_category;
197 : typedef std::ptrdiff_t difference_type;
198 : typedef Handle<T> value_type;
199 : typedef value_type reference;
200 : typedef value_type* pointer;
201 :
202 : const_iterator(const const_iterator& other)
203 7146 : : set_(other.set_), current_(other.current_) {}
204 :
205 1191 : reference operator*() const { return (*set_)[current_]; }
206 : bool operator==(const const_iterator& other) const {
207 281045 : 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 141745 : current_ += 1;
215 : return *this;
216 : }
217 : const_iterator operator++(int);
218 :
219 : private:
220 : friend class ZoneHandleSet<T>;
221 :
222 : explicit const_iterator(const ZoneHandleSet<T>* set, size_t current)
223 1191 : : set_(set), current_(current) {}
224 :
225 : const ZoneHandleSet<T>* set_;
226 : size_t current_;
227 : };
228 :
229 : template <typename T>
230 : typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::begin() const {
231 : return ZoneHandleSet<T>::const_iterator(this, 0);
232 : }
233 :
234 : template <typename T>
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_
|
