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