//===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines the DenseSet and SmallDenseSet classes. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_DENSESET_H #define LLVM_ADT_DENSESET_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMapInfo.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/type_traits.h" #include #include #include #include #include namespace llvm { namespace detail { struct DenseSetEmpty {}; // Use the empty base class trick so we can create a DenseMap where the buckets // contain only a single item. template class DenseSetPair : public DenseSetEmpty { KeyT key; public: KeyT &getFirst() { return key; } const KeyT &getFirst() const { return key; } DenseSetEmpty &getSecond() { return *this; } const DenseSetEmpty &getSecond() const { return *this; } }; /// Base class for DenseSet and DenseSmallSet. /// /// MapTy should be either /// /// DenseMap> /// /// or the equivalent SmallDenseMap type. ValueInfoT must implement the /// DenseMapInfo "concept". template class DenseSetImpl { static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), "DenseMap buckets unexpectedly large!"); MapTy TheMap; template using const_arg_type_t = typename const_pointer_or_const_ref::type; public: using key_type = ValueT; using value_type = ValueT; using size_type = unsigned; explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {} DenseSetImpl(std::initializer_list Elems) : DenseSetImpl(PowerOf2Ceil(Elems.size())) { insert(Elems.begin(), Elems.end()); } bool empty() const { return TheMap.empty(); } size_type size() const { return TheMap.size(); } size_t getMemorySize() const { return TheMap.getMemorySize(); } /// Grow the DenseSet so that it has at least Size buckets. Will not shrink /// the Size of the set. void resize(size_t Size) { TheMap.resize(Size); } /// Grow the DenseSet so that it can contain at least \p NumEntries items /// before resizing again. void reserve(size_t Size) { TheMap.reserve(Size); } void clear() { TheMap.clear(); } /// Return 1 if the specified key is in the set, 0 otherwise. size_type count(const_arg_type_t V) const { return TheMap.count(V); } bool erase(const ValueT &V) { return TheMap.erase(V); } void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); } // Iterators. class ConstIterator; class Iterator { typename MapTy::iterator I; friend class DenseSetImpl; friend class ConstIterator; public: using difference_type = typename MapTy::iterator::difference_type; using value_type = ValueT; using pointer = value_type *; using reference = value_type &; using iterator_category = std::forward_iterator_tag; Iterator() = default; Iterator(const typename MapTy::iterator &i) : I(i) {} ValueT &operator*() { return I->getFirst(); } const ValueT &operator*() const { return I->getFirst(); } ValueT *operator->() { return &I->getFirst(); } const ValueT *operator->() const { return &I->getFirst(); } Iterator& operator++() { ++I; return *this; } Iterator operator++(int) { auto T = *this; ++I; return T; } bool operator==(const ConstIterator& X) const { return I == X.I; } bool operator!=(const ConstIterator& X) const { return I != X.I; } }; class ConstIterator { typename MapTy::const_iterator I; friend class DenseSetImpl; friend class Iterator; public: using difference_type = typename MapTy::const_iterator::difference_type; using value_type = ValueT; using pointer = const value_type *; using reference = const value_type &; using iterator_category = std::forward_iterator_tag; ConstIterator() = default; ConstIterator(const Iterator &B) : I(B.I) {} ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} const ValueT &operator*() const { return I->getFirst(); } const ValueT *operator->() const { return &I->getFirst(); } ConstIterator& operator++() { ++I; return *this; } ConstIterator operator++(int) { auto T = *this; ++I; return T; } bool operator==(const ConstIterator& X) const { return I == X.I; } bool operator!=(const ConstIterator& X) const { return I != X.I; } }; using iterator = Iterator; using const_iterator = ConstIterator; iterator begin() { return Iterator(TheMap.begin()); } iterator end() { return Iterator(TheMap.end()); } const_iterator begin() const { return ConstIterator(TheMap.begin()); } const_iterator end() const { return ConstIterator(TheMap.end()); } iterator find(const_arg_type_t V) { return Iterator(TheMap.find(V)); } const_iterator find(const_arg_type_t V) const { return ConstIterator(TheMap.find(V)); } /// Alternative version of find() which allows a different, and possibly less /// expensive, key type. /// The DenseMapInfo is responsible for supplying methods /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type /// used. template iterator find_as(const LookupKeyT &Val) { return Iterator(TheMap.find_as(Val)); } template const_iterator find_as(const LookupKeyT &Val) const { return ConstIterator(TheMap.find_as(Val)); } void erase(Iterator I) { return TheMap.erase(I.I); } void erase(ConstIterator CI) { return TheMap.erase(CI.I); } std::pair insert(const ValueT &V) { detail::DenseSetEmpty Empty; return TheMap.try_emplace(V, Empty); } std::pair insert(ValueT &&V) { detail::DenseSetEmpty Empty; return TheMap.try_emplace(std::move(V), Empty); } /// Alternative version of insert that uses a different (and possibly less /// expensive) key type. template std::pair insert_as(const ValueT &V, const LookupKeyT &LookupKey) { return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey); } template std::pair insert_as(ValueT &&V, const LookupKeyT &LookupKey) { return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey); } // Range insertion of values. template void insert(InputIt I, InputIt E) { for (; I != E; ++I) insert(*I); } }; /// Equality comparison for DenseSet. /// /// Iterates over elements of LHS confirming that each element is also a member /// of RHS, and that RHS contains no additional values. /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst /// case is O(N^2) (if every hash collides). template bool operator==(const DenseSetImpl &LHS, const DenseSetImpl &RHS) { if (LHS.size() != RHS.size()) return false; for (auto &E : LHS) if (!RHS.count(E)) return false; return true; } /// Inequality comparison for DenseSet. /// /// Equivalent to !(LHS == RHS). See operator== for performance notes. template bool operator!=(const DenseSetImpl &LHS, const DenseSetImpl &RHS) { return !(LHS == RHS); } } // end namespace detail /// Implements a dense probed hash-table based set. template > class DenseSet : public detail::DenseSetImpl< ValueT, DenseMap>, ValueInfoT> { using BaseT = detail::DenseSetImpl>, ValueInfoT>; public: using BaseT::BaseT; }; /// Implements a dense probed hash-table based set with some number of buckets /// stored inline. template > class SmallDenseSet : public detail::DenseSetImpl< ValueT, SmallDenseMap>, ValueInfoT> { using BaseT = detail::DenseSetImpl< ValueT, SmallDenseMap>, ValueInfoT>; public: using BaseT::BaseT; }; } // end namespace llvm #endif // LLVM_ADT_DENSESET_H