// Copyright 2016 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_ZONE_ZONE_HANDLE_SET_H_ #define V8_ZONE_ZONE_HANDLE_SET_H_ #include "src/handles/handles.h" #include "src/zone/zone-containers.h" #include "src/zone/zone.h" namespace v8 { namespace internal { template <typename T> class ZoneHandleSet final { public: ZoneHandleSet() : data_(kEmptyTag) {} explicit ZoneHandleSet(Handle<T> handle) : data_(handle.address() | kSingletonTag) { DCHECK(IsAligned(handle.address(), kPointerAlignment)); } bool is_empty() const { return data_ == kEmptyTag; } size_t size() const { if ((data_ & kTagMask) == kEmptyTag) return 0; if ((data_ & kTagMask) == kSingletonTag) return 1; return list()->size(); } Handle<T> at(size_t i) const { DCHECK_NE(kEmptyTag, data_ & kTagMask); if ((data_ & kTagMask) == kSingletonTag) { DCHECK_EQ(0u, i); return Handle<T>(singleton()); } return Handle<T>(list()->at(static_cast<int>(i))); } Handle<T> operator[](size_t i) const { return at(i); } void insert(Handle<T> handle, Zone* zone) { Address* const value = reinterpret_cast<Address*>(handle.address()); DCHECK(IsAligned(reinterpret_cast<Address>(value), kPointerAlignment)); if ((data_ & kTagMask) == kEmptyTag) { data_ = reinterpret_cast<Address>(value) | kSingletonTag; } else if ((data_ & kTagMask) == kSingletonTag) { if (singleton() == value) return; List* list = zone->New<List>(zone); if (singleton() < value) { list->push_back(singleton()); list->push_back(value); } else { list->push_back(value); list->push_back(singleton()); } DCHECK(IsAligned(reinterpret_cast<Address>(list), kPointerAlignment)); data_ = reinterpret_cast<Address>(list) | kListTag; } else { DCHECK_EQ(kListTag, data_ & kTagMask); List const* const old_list = list(); for (size_t i = 0; i < old_list->size(); ++i) { if (old_list->at(i) == value) return; if (old_list->at(i) > value) break; } List* new_list = zone->New<List>(zone); new_list->reserve(old_list->size() + 1); size_t i = 0; for (; i < old_list->size(); ++i) { if (old_list->at(i) > value) break; new_list->push_back(old_list->at(i)); } new_list->push_back(value); for (; i < old_list->size(); ++i) { new_list->push_back(old_list->at(i)); } DCHECK_EQ(old_list->size() + 1, new_list->size()); DCHECK(IsAligned(reinterpret_cast<Address>(new_list), kPointerAlignment)); data_ = reinterpret_cast<Address>(new_list) | kListTag; } } bool contains(ZoneHandleSet<T> const& other) const { if (data_ == other.data_) return true; if (data_ == kEmptyTag) return false; if (other.data_ == kEmptyTag) return true; if ((data_ & kTagMask) == kSingletonTag) return false; DCHECK_EQ(kListTag, data_ & kTagMask); List const* cached_list = list(); if ((other.data_ & kTagMask) == kSingletonTag) { return std::find(cached_list->begin(), cached_list->end(), other.singleton()) != cached_list->end(); } DCHECK_EQ(kListTag, other.data_ & kTagMask); // TODO(bmeurer): Optimize this case. for (size_t i = 0; i < other.list()->size(); ++i) { if (std::find(cached_list->begin(), cached_list->end(), other.list()->at(i)) == cached_list->end()) { return false; } } return true; } bool contains(Handle<T> other) const { if (data_ == kEmptyTag) return false; Address* other_address = reinterpret_cast<Address*>(other.address()); if ((data_ & kTagMask) == kSingletonTag) { return singleton() == other_address; } DCHECK_EQ(kListTag, data_ & kTagMask); return std::find(list()->begin(), list()->end(), other_address) != list()->end(); } void remove(Handle<T> handle, Zone* zone) { // TODO(bmeurer): Optimize this case. ZoneHandleSet<T> that; for (size_t i = 0; i < size(); ++i) { Handle<T> value = at(i); if (value.address() != handle.address()) { that.insert(value, zone); } } std::swap(*this, that); } friend bool operator==(ZoneHandleSet<T> const& lhs, ZoneHandleSet<T> const& rhs) { if (lhs.data_ == rhs.data_) return true; if ((lhs.data_ & kTagMask) == kListTag && (rhs.data_ & kTagMask) == kListTag) { List const* const lhs_list = lhs.list(); List const* const rhs_list = rhs.list(); if (lhs_list->size() == rhs_list->size()) { for (size_t i = 0; i < lhs_list->size(); ++i) { if (lhs_list->at(i) != rhs_list->at(i)) return false; } return true; } } return false; } friend bool operator!=(ZoneHandleSet<T> const& lhs, ZoneHandleSet<T> const& rhs) { return !(lhs == rhs); } friend size_t hash_value(ZoneHandleSet<T> const& set) { return static_cast<size_t>(set.data_); } class const_iterator; inline const_iterator begin() const; inline const_iterator end() const; private: using List = ZoneVector<Address*>; List const* list() const { DCHECK_EQ(kListTag, data_ & kTagMask); return reinterpret_cast<List const*>(data_ - kListTag); } Address* singleton() const { DCHECK_EQ(kSingletonTag, data_ & kTagMask); return reinterpret_cast<Address*>(data_ - kSingletonTag); } enum Tag : Address { kSingletonTag = 0, kEmptyTag = 1, kListTag = 2, kTagMask = 3 }; STATIC_ASSERT(kTagMask < kPointerAlignment); Address data_; }; template <typename T> std::ostream& operator<<(std::ostream& os, ZoneHandleSet<T> set) { for (size_t i = 0; i < set.size(); ++i) { if (i > 0) os << ", "; os << set.at(i); } return os; } template <typename T> class ZoneHandleSet<T>::const_iterator { public: using iterator_category = std::forward_iterator_tag; using difference_type = std::ptrdiff_t; using value_type = Handle<T>; using reference = value_type; using pointer = value_type*; const_iterator(const const_iterator& other) = default; const_iterator& operator=(const const_iterator& other) = default; reference operator*() const { return (*set_)[current_]; } bool operator==(const const_iterator& other) const { return set_ == other.set_ && current_ == other.current_; } bool operator!=(const const_iterator& other) const { return !(*this == other); } const_iterator& operator++() { DCHECK(current_ < set_->size()); current_ += 1; return *this; } const_iterator operator++(int); private: friend class ZoneHandleSet<T>; explicit const_iterator(const ZoneHandleSet<T>* set, size_t current) : set_(set), current_(current) {} const ZoneHandleSet<T>* set_; size_t current_; }; template <typename T> typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::begin() const { return ZoneHandleSet<T>::const_iterator(this, 0); } template <typename T> typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::end() const { return ZoneHandleSet<T>::const_iterator(this, size()); } } // namespace internal } // namespace v8 #endif // V8_ZONE_ZONE_HANDLE_SET_H_