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 357595 : ZoneHandleSet() : data_(kEmptyTag) {}
18 : explicit ZoneHandleSet(Handle<T> handle)
19 152452 : : 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 388264 : if ((data_ & kTagMask) == kEmptyTag) return 0;
27 388142 : if ((data_ & kTagMask) == kSingletonTag) return 1;
28 6083 : return list()->length();
29 : }
30 :
31 : Handle<T> at(size_t i) const {
32 : DCHECK_NE(kEmptyTag, data_ & kTagMask);
33 245357 : if ((data_ & kTagMask) == kSingletonTag) {
34 : DCHECK_EQ(0u, i);
35 : return Handle<T>(singleton());
36 : }
37 14464 : return Handle<T>(list()->at(static_cast<int>(i)));
38 : }
39 :
40 : Handle<T> operator[](size_t i) const { return at(i); }
41 :
42 63189 : void insert(Handle<T> handle, Zone* zone) {
43 : T** const value = bit_cast<T**>(handle.address());
44 : DCHECK(IsAligned(bit_cast<intptr_t>(value), kPointerAlignment));
45 63189 : if ((data_ & kTagMask) == kEmptyTag) {
46 59937 : data_ = bit_cast<intptr_t>(value) | kSingletonTag;
47 3252 : } else if ((data_ & kTagMask) == kSingletonTag) {
48 2771 : if (singleton() == value) return;
49 2283 : List* list = new (zone) List(2, zone);
50 2283 : if (singleton() < value) {
51 : list->Add(singleton(), zone);
52 : list->Add(value, zone);
53 : } else {
54 : list->Add(value, zone);
55 : list->Add(singleton(), zone);
56 : }
57 : DCHECK(IsAligned(bit_cast<intptr_t>(list), kPointerAlignment));
58 2283 : data_ = bit_cast<intptr_t>(list) | kListTag;
59 : } else {
60 : DCHECK_EQ(kListTag, data_ & kTagMask);
61 : List const* const old_list = list();
62 2646 : for (int i = 0; i < old_list->length(); ++i) {
63 4054 : if (old_list->at(i) == value) return;
64 907 : if (old_list->at(i) > value) break;
65 : }
66 862 : List* new_list = new (zone) List(old_list->length() + 1, zone);
67 : int i = 0;
68 2440 : for (; i < old_list->length(); ++i) {
69 : if (old_list->at(i) > value) break;
70 : new_list->Add(old_list->at(i), zone);
71 : }
72 : new_list->Add(value, zone);
73 677 : for (; i < old_list->length(); ++i) {
74 123 : 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 431 : data_ = bit_cast<intptr_t>(new_list) | kListTag;
79 : }
80 : }
81 :
82 37078 : bool contains(ZoneHandleSet<T> const& other) const {
83 37078 : if (data_ == other.data_) return true;
84 1419 : if (data_ == kEmptyTag) return false;
85 1419 : if (other.data_ == kEmptyTag) return true;
86 1419 : if ((data_ & kTagMask) == kSingletonTag) return false;
87 : DCHECK_EQ(kListTag, data_ & kTagMask);
88 678 : if ((other.data_ & kTagMask) == kSingletonTag) {
89 79 : return list()->Contains(other.singleton());
90 : }
91 : DCHECK_EQ(kListTag, other.data_ & kTagMask);
92 : // TODO(bmeurer): Optimize this case.
93 3205 : for (int i = 0; i < other.list()->length(); ++i) {
94 2606 : if (!list()->Contains(other.list()->at(i))) return false;
95 : }
96 : return true;
97 : }
98 :
99 62 : void remove(Handle<T> handle, Zone* zone) {
100 : // TODO(bmeurer): Optimize this case.
101 : ZoneHandleSet<T> that;
102 336 : for (size_t i = 0; i < size(); ++i) {
103 : Handle<T> value = at(i);
104 106 : if (value.address() != handle.address()) {
105 44 : that.insert(value, zone);
106 : }
107 : }
108 : std::swap(*this, that);
109 62 : }
110 :
111 33237 : friend bool operator==(ZoneHandleSet<T> const& lhs,
112 : ZoneHandleSet<T> const& rhs) {
113 33237 : if (lhs.data_ == rhs.data_) return true;
114 1342 : if ((lhs.data_ & kTagMask) == kListTag &&
115 : (rhs.data_ & kTagMask) == kListTag) {
116 : List const* const lhs_list = lhs.list();
117 : List const* const rhs_list = rhs.list();
118 98 : if (lhs_list->length() == rhs_list->length()) {
119 279 : for (int i = 0; i < lhs_list->length(); ++i) {
120 558 : if (lhs_list->at(i) != rhs_list->at(i)) return false;
121 : }
122 : return true;
123 : }
124 : }
125 : return false;
126 : }
127 :
128 : friend bool operator!=(ZoneHandleSet<T> const& lhs,
129 : ZoneHandleSet<T> const& rhs) {
130 : return !(lhs == rhs);
131 : }
132 :
133 0 : friend size_t hash_value(ZoneHandleSet<T> const& set) {
134 0 : return static_cast<size_t>(set.data_);
135 : }
136 :
137 : private:
138 : typedef ZoneList<T**> List;
139 :
140 : List const* list() const {
141 : DCHECK_EQ(kListTag, data_ & kTagMask);
142 17276 : return bit_cast<List const*>(data_ - kListTag);
143 : }
144 :
145 : T** singleton() const {
146 : DCHECK_EQ(kSingletonTag, data_ & kTagMask);
147 2421 : return bit_cast<T**>(data_ - kSingletonTag);
148 : }
149 :
150 : enum Tag : intptr_t {
151 : kSingletonTag = 0,
152 : kEmptyTag = 1,
153 : kListTag = 2,
154 : kTagMask = 3
155 : };
156 :
157 : STATIC_ASSERT(kTagMask < kPointerAlignment);
158 :
159 : intptr_t data_;
160 : };
161 :
162 : } // namespace internal
163 : } // namespace v8
164 :
165 : #endif // V8_ZONE_ZONE_HANDLE_SET_H_
|
