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: ZoneHandleSet()17 ZoneHandleSet() : data_(kEmptyTag) {} ZoneHandleSet(Handle<T> handle)18 explicit ZoneHandleSet(Handle<T> handle) 19 : data_(bit_cast<intptr_t>(handle.address()) | kSingletonTag) { 20 DCHECK(IsAligned(bit_cast<intptr_t>(handle.address()), kPointerAlignment)); 21 } 22 is_empty()23 bool is_empty() const { return data_ == kEmptyTag; } 24 size()25 size_t size() const { 26 if ((data_ & kTagMask) == kEmptyTag) return 0; 27 if ((data_ & kTagMask) == kSingletonTag) return 1; 28 return list()->length(); 29 } 30 at(size_t i)31 Handle<T> at(size_t i) const { 32 DCHECK_NE(kEmptyTag, data_ & kTagMask); 33 if ((data_ & kTagMask) == kSingletonTag) { 34 DCHECK_EQ(0u, i); 35 return Handle<T>(singleton()); 36 } 37 return Handle<T>(list()->at(static_cast<int>(i))); 38 } 39 40 Handle<T> operator[](size_t i) const { return at(i); } 41 insert(Handle<T> handle,Zone * zone)42 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 if ((data_ & kTagMask) == kEmptyTag) { 46 data_ = bit_cast<intptr_t>(value) | kSingletonTag; 47 } else if ((data_ & kTagMask) == kSingletonTag) { 48 if (singleton() == value) return; 49 List* list = new (zone) List(2, zone); 50 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 data_ = bit_cast<intptr_t>(list) | kListTag; 59 } else { 60 DCHECK_EQ(kListTag, data_ & kTagMask); 61 List const* const old_list = list(); 62 for (int i = 0; i < old_list->length(); ++i) { 63 if (old_list->at(i) == value) return; 64 if (old_list->at(i) > value) break; 65 } 66 List* new_list = new (zone) List(old_list->length() + 1, zone); 67 int i = 0; 68 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 for (; i < old_list->length(); ++i) { 74 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 data_ = bit_cast<intptr_t>(new_list) | kListTag; 79 } 80 } 81 contains(ZoneHandleSet<T> const & other)82 bool contains(ZoneHandleSet<T> const& other) const { 83 if (data_ == other.data_) return true; 84 if (data_ == kEmptyTag) return false; 85 if (other.data_ == kEmptyTag) return true; 86 if ((data_ & kTagMask) == kSingletonTag) return false; 87 DCHECK_EQ(kListTag, data_ & kTagMask); 88 if ((other.data_ & kTagMask) == kSingletonTag) { 89 return list()->Contains(other.singleton()); 90 } 91 DCHECK_EQ(kListTag, other.data_ & kTagMask); 92 // TODO(bmeurer): Optimize this case. 93 for (int i = 0; i < other.list()->length(); ++i) { 94 if (!list()->Contains(other.list()->at(i))) return false; 95 } 96 return true; 97 } 98 remove(Handle<T> handle,Zone * zone)99 void remove(Handle<T> handle, Zone* zone) { 100 // TODO(bmeurer): Optimize this case. 101 ZoneHandleSet<T> that; 102 for (size_t i = 0; i < size(); ++i) { 103 Handle<T> value = at(i); 104 if (value.address() != handle.address()) { 105 that.insert(value, zone); 106 } 107 } 108 std::swap(*this, that); 109 } 110 111 friend bool operator==(ZoneHandleSet<T> const& lhs, 112 ZoneHandleSet<T> const& rhs) { 113 if (lhs.data_ == rhs.data_) return true; 114 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 if (lhs_list->length() == rhs_list->length()) { 119 for (int i = 0; i < lhs_list->length(); ++i) { 120 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 hash_value(ZoneHandleSet<T> const & set)133 friend size_t hash_value(ZoneHandleSet<T> const& set) { 134 return static_cast<size_t>(set.data_); 135 } 136 137 private: 138 typedef ZoneList<T**> List; 139 list()140 List const* list() const { 141 DCHECK_EQ(kListTag, data_ & kTagMask); 142 return bit_cast<List const*>(data_ - kListTag); 143 } 144 singleton()145 T** singleton() const { 146 DCHECK_EQ(kSingletonTag, data_ & kTagMask); 147 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_ 166