10b57cec5SDimitry Andric //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 81fd87a68SDimitry Andric /// 91fd87a68SDimitry Andric /// \file 101fd87a68SDimitry Andric /// This file defines the DenseSet and SmallDenseSet classes. 111fd87a68SDimitry Andric /// 120b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #ifndef LLVM_ADT_DENSESET_H 150b57cec5SDimitry Andric #define LLVM_ADT_DENSESET_H 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 180b57cec5SDimitry Andric #include "llvm/ADT/DenseMapInfo.h" 190b57cec5SDimitry Andric #include "llvm/Support/MathExtras.h" 200b57cec5SDimitry Andric #include "llvm/Support/type_traits.h" 210b57cec5SDimitry Andric #include <cstddef> 220b57cec5SDimitry Andric #include <initializer_list> 230b57cec5SDimitry Andric #include <iterator> 240b57cec5SDimitry Andric #include <utility> 250b57cec5SDimitry Andric 260b57cec5SDimitry Andric namespace llvm { 270b57cec5SDimitry Andric 280b57cec5SDimitry Andric namespace detail { 290b57cec5SDimitry Andric 300b57cec5SDimitry Andric struct DenseSetEmpty {}; 310b57cec5SDimitry Andric 320b57cec5SDimitry Andric // Use the empty base class trick so we can create a DenseMap where the buckets 330b57cec5SDimitry Andric // contain only a single item. 340b57cec5SDimitry Andric template <typename KeyT> class DenseSetPair : public DenseSetEmpty { 350b57cec5SDimitry Andric KeyT key; 360b57cec5SDimitry Andric 370b57cec5SDimitry Andric public: getFirst()380b57cec5SDimitry Andric KeyT &getFirst() { return key; } getFirst()390b57cec5SDimitry Andric const KeyT &getFirst() const { return key; } getSecond()400b57cec5SDimitry Andric DenseSetEmpty &getSecond() { return *this; } getSecond()410b57cec5SDimitry Andric const DenseSetEmpty &getSecond() const { return *this; } 420b57cec5SDimitry Andric }; 430b57cec5SDimitry Andric 440b57cec5SDimitry Andric /// Base class for DenseSet and DenseSmallSet. 450b57cec5SDimitry Andric /// 460b57cec5SDimitry Andric /// MapTy should be either 470b57cec5SDimitry Andric /// 480b57cec5SDimitry Andric /// DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 490b57cec5SDimitry Andric /// detail::DenseSetPair<ValueT>> 500b57cec5SDimitry Andric /// 510b57cec5SDimitry Andric /// or the equivalent SmallDenseMap type. ValueInfoT must implement the 520b57cec5SDimitry Andric /// DenseMapInfo "concept". 530b57cec5SDimitry Andric template <typename ValueT, typename MapTy, typename ValueInfoT> 540b57cec5SDimitry Andric class DenseSetImpl { 550b57cec5SDimitry Andric static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), 560b57cec5SDimitry Andric "DenseMap buckets unexpectedly large!"); 570b57cec5SDimitry Andric MapTy TheMap; 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric template <typename T> 600b57cec5SDimitry Andric using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; 610b57cec5SDimitry Andric 620b57cec5SDimitry Andric public: 630b57cec5SDimitry Andric using key_type = ValueT; 640b57cec5SDimitry Andric using value_type = ValueT; 650b57cec5SDimitry Andric using size_type = unsigned; 660b57cec5SDimitry Andric TheMap(InitialReserve)670b57cec5SDimitry Andric explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {} 680b57cec5SDimitry Andric 695ffd83dbSDimitry Andric template <typename InputIt> DenseSetImpl(const InputIt & I,const InputIt & E)705ffd83dbSDimitry Andric DenseSetImpl(const InputIt &I, const InputIt &E) 715ffd83dbSDimitry Andric : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) { 725ffd83dbSDimitry Andric insert(I, E); 735ffd83dbSDimitry Andric } 745ffd83dbSDimitry Andric DenseSetImpl(std::initializer_list<ValueT> Elems)750b57cec5SDimitry Andric DenseSetImpl(std::initializer_list<ValueT> Elems) 760b57cec5SDimitry Andric : DenseSetImpl(PowerOf2Ceil(Elems.size())) { 770b57cec5SDimitry Andric insert(Elems.begin(), Elems.end()); 780b57cec5SDimitry Andric } 790b57cec5SDimitry Andric empty()800b57cec5SDimitry Andric bool empty() const { return TheMap.empty(); } size()810b57cec5SDimitry Andric size_type size() const { return TheMap.size(); } getMemorySize()820b57cec5SDimitry Andric size_t getMemorySize() const { return TheMap.getMemorySize(); } 830b57cec5SDimitry Andric 840b57cec5SDimitry Andric /// Grow the DenseSet so that it has at least Size buckets. Will not shrink 850b57cec5SDimitry Andric /// the Size of the set. resize(size_t Size)860b57cec5SDimitry Andric void resize(size_t Size) { TheMap.resize(Size); } 870b57cec5SDimitry Andric 880b57cec5SDimitry Andric /// Grow the DenseSet so that it can contain at least \p NumEntries items 890b57cec5SDimitry Andric /// before resizing again. reserve(size_t Size)900b57cec5SDimitry Andric void reserve(size_t Size) { TheMap.reserve(Size); } 910b57cec5SDimitry Andric clear()920b57cec5SDimitry Andric void clear() { 930b57cec5SDimitry Andric TheMap.clear(); 940b57cec5SDimitry Andric } 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric /// Return 1 if the specified key is in the set, 0 otherwise. count(const_arg_type_t<ValueT> V)970b57cec5SDimitry Andric size_type count(const_arg_type_t<ValueT> V) const { 980b57cec5SDimitry Andric return TheMap.count(V); 990b57cec5SDimitry Andric } 1000b57cec5SDimitry Andric erase(const ValueT & V)1010b57cec5SDimitry Andric bool erase(const ValueT &V) { 1020b57cec5SDimitry Andric return TheMap.erase(V); 1030b57cec5SDimitry Andric } 1040b57cec5SDimitry Andric swap(DenseSetImpl & RHS)1050b57cec5SDimitry Andric void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); } 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric // Iterators. 1080b57cec5SDimitry Andric 1090b57cec5SDimitry Andric class ConstIterator; 1100b57cec5SDimitry Andric 1110b57cec5SDimitry Andric class Iterator { 1120b57cec5SDimitry Andric typename MapTy::iterator I; 1130b57cec5SDimitry Andric friend class DenseSetImpl; 1140b57cec5SDimitry Andric friend class ConstIterator; 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andric public: 1170b57cec5SDimitry Andric using difference_type = typename MapTy::iterator::difference_type; 1180b57cec5SDimitry Andric using value_type = ValueT; 1190b57cec5SDimitry Andric using pointer = value_type *; 1200b57cec5SDimitry Andric using reference = value_type &; 1210b57cec5SDimitry Andric using iterator_category = std::forward_iterator_tag; 1220b57cec5SDimitry Andric 1230b57cec5SDimitry Andric Iterator() = default; Iterator(const typename MapTy::iterator & i)1240b57cec5SDimitry Andric Iterator(const typename MapTy::iterator &i) : I(i) {} 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric ValueT &operator*() { return I->getFirst(); } 1270b57cec5SDimitry Andric const ValueT &operator*() const { return I->getFirst(); } 1280b57cec5SDimitry Andric ValueT *operator->() { return &I->getFirst(); } 1290b57cec5SDimitry Andric const ValueT *operator->() const { return &I->getFirst(); } 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric Iterator& operator++() { ++I; return *this; } 1320b57cec5SDimitry Andric Iterator operator++(int) { auto T = *this; ++I; return T; } 133e8d8bef9SDimitry Andric friend bool operator==(const Iterator &X, const Iterator &Y) { 134e8d8bef9SDimitry Andric return X.I == Y.I; 135e8d8bef9SDimitry Andric } 136e8d8bef9SDimitry Andric friend bool operator!=(const Iterator &X, const Iterator &Y) { 137e8d8bef9SDimitry Andric return X.I != Y.I; 138e8d8bef9SDimitry Andric } 1390b57cec5SDimitry Andric }; 1400b57cec5SDimitry Andric 1410b57cec5SDimitry Andric class ConstIterator { 1420b57cec5SDimitry Andric typename MapTy::const_iterator I; 1430b57cec5SDimitry Andric friend class DenseSetImpl; 1440b57cec5SDimitry Andric friend class Iterator; 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andric public: 1470b57cec5SDimitry Andric using difference_type = typename MapTy::const_iterator::difference_type; 1480b57cec5SDimitry Andric using value_type = ValueT; 1490b57cec5SDimitry Andric using pointer = const value_type *; 1500b57cec5SDimitry Andric using reference = const value_type &; 1510b57cec5SDimitry Andric using iterator_category = std::forward_iterator_tag; 1520b57cec5SDimitry Andric 1530b57cec5SDimitry Andric ConstIterator() = default; ConstIterator(const Iterator & B)1540b57cec5SDimitry Andric ConstIterator(const Iterator &B) : I(B.I) {} ConstIterator(const typename MapTy::const_iterator & i)1550b57cec5SDimitry Andric ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} 1560b57cec5SDimitry Andric 1570b57cec5SDimitry Andric const ValueT &operator*() const { return I->getFirst(); } 1580b57cec5SDimitry Andric const ValueT *operator->() const { return &I->getFirst(); } 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andric ConstIterator& operator++() { ++I; return *this; } 1610b57cec5SDimitry Andric ConstIterator operator++(int) { auto T = *this; ++I; return T; } 162e8d8bef9SDimitry Andric friend bool operator==(const ConstIterator &X, const ConstIterator &Y) { 163e8d8bef9SDimitry Andric return X.I == Y.I; 164e8d8bef9SDimitry Andric } 165e8d8bef9SDimitry Andric friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) { 166e8d8bef9SDimitry Andric return X.I != Y.I; 167e8d8bef9SDimitry Andric } 1680b57cec5SDimitry Andric }; 1690b57cec5SDimitry Andric 1700b57cec5SDimitry Andric using iterator = Iterator; 1710b57cec5SDimitry Andric using const_iterator = ConstIterator; 1720b57cec5SDimitry Andric begin()1730b57cec5SDimitry Andric iterator begin() { return Iterator(TheMap.begin()); } end()1740b57cec5SDimitry Andric iterator end() { return Iterator(TheMap.end()); } 1750b57cec5SDimitry Andric begin()1760b57cec5SDimitry Andric const_iterator begin() const { return ConstIterator(TheMap.begin()); } end()1770b57cec5SDimitry Andric const_iterator end() const { return ConstIterator(TheMap.end()); } 1780b57cec5SDimitry Andric find(const_arg_type_t<ValueT> V)1790b57cec5SDimitry Andric iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); } find(const_arg_type_t<ValueT> V)1800b57cec5SDimitry Andric const_iterator find(const_arg_type_t<ValueT> V) const { 1810b57cec5SDimitry Andric return ConstIterator(TheMap.find(V)); 1820b57cec5SDimitry Andric } 1830b57cec5SDimitry Andric 184e8d8bef9SDimitry Andric /// Check if the set contains the given element. contains(const_arg_type_t<ValueT> V)185e8d8bef9SDimitry Andric bool contains(const_arg_type_t<ValueT> V) const { 186e8d8bef9SDimitry Andric return TheMap.find(V) != TheMap.end(); 187e8d8bef9SDimitry Andric } 188e8d8bef9SDimitry Andric 1890b57cec5SDimitry Andric /// Alternative version of find() which allows a different, and possibly less 1900b57cec5SDimitry Andric /// expensive, key type. 1910b57cec5SDimitry Andric /// The DenseMapInfo is responsible for supplying methods 1920b57cec5SDimitry Andric /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type 1930b57cec5SDimitry Andric /// used. 1940b57cec5SDimitry Andric template <class LookupKeyT> find_as(const LookupKeyT & Val)1950b57cec5SDimitry Andric iterator find_as(const LookupKeyT &Val) { 1960b57cec5SDimitry Andric return Iterator(TheMap.find_as(Val)); 1970b57cec5SDimitry Andric } 1980b57cec5SDimitry Andric template <class LookupKeyT> find_as(const LookupKeyT & Val)1990b57cec5SDimitry Andric const_iterator find_as(const LookupKeyT &Val) const { 2000b57cec5SDimitry Andric return ConstIterator(TheMap.find_as(Val)); 2010b57cec5SDimitry Andric } 2020b57cec5SDimitry Andric erase(Iterator I)2030b57cec5SDimitry Andric void erase(Iterator I) { return TheMap.erase(I.I); } erase(ConstIterator CI)2040b57cec5SDimitry Andric void erase(ConstIterator CI) { return TheMap.erase(CI.I); } 2050b57cec5SDimitry Andric insert(const ValueT & V)2060b57cec5SDimitry Andric std::pair<iterator, bool> insert(const ValueT &V) { 2070b57cec5SDimitry Andric detail::DenseSetEmpty Empty; 2080b57cec5SDimitry Andric return TheMap.try_emplace(V, Empty); 2090b57cec5SDimitry Andric } 2100b57cec5SDimitry Andric insert(ValueT && V)2110b57cec5SDimitry Andric std::pair<iterator, bool> insert(ValueT &&V) { 2120b57cec5SDimitry Andric detail::DenseSetEmpty Empty; 2130b57cec5SDimitry Andric return TheMap.try_emplace(std::move(V), Empty); 2140b57cec5SDimitry Andric } 2150b57cec5SDimitry Andric 2160b57cec5SDimitry Andric /// Alternative version of insert that uses a different (and possibly less 2170b57cec5SDimitry Andric /// expensive) key type. 2180b57cec5SDimitry Andric template <typename LookupKeyT> insert_as(const ValueT & V,const LookupKeyT & LookupKey)2190b57cec5SDimitry Andric std::pair<iterator, bool> insert_as(const ValueT &V, 2200b57cec5SDimitry Andric const LookupKeyT &LookupKey) { 2210b57cec5SDimitry Andric return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey); 2220b57cec5SDimitry Andric } 2230b57cec5SDimitry Andric template <typename LookupKeyT> insert_as(ValueT && V,const LookupKeyT & LookupKey)2240b57cec5SDimitry Andric std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) { 2250b57cec5SDimitry Andric return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey); 2260b57cec5SDimitry Andric } 2270b57cec5SDimitry Andric 2280b57cec5SDimitry Andric // Range insertion of values. 2290b57cec5SDimitry Andric template<typename InputIt> insert(InputIt I,InputIt E)2300b57cec5SDimitry Andric void insert(InputIt I, InputIt E) { 2310b57cec5SDimitry Andric for (; I != E; ++I) 2320b57cec5SDimitry Andric insert(*I); 2330b57cec5SDimitry Andric } 2340b57cec5SDimitry Andric }; 2350b57cec5SDimitry Andric 2360b57cec5SDimitry Andric /// Equality comparison for DenseSet. 2370b57cec5SDimitry Andric /// 2380b57cec5SDimitry Andric /// Iterates over elements of LHS confirming that each element is also a member 2390b57cec5SDimitry Andric /// of RHS, and that RHS contains no additional values. 2400b57cec5SDimitry Andric /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst 2410b57cec5SDimitry Andric /// case is O(N^2) (if every hash collides). 2420b57cec5SDimitry Andric template <typename ValueT, typename MapTy, typename ValueInfoT> 2430b57cec5SDimitry Andric bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS, 2440b57cec5SDimitry Andric const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) { 2450b57cec5SDimitry Andric if (LHS.size() != RHS.size()) 2460b57cec5SDimitry Andric return false; 2470b57cec5SDimitry Andric 2480b57cec5SDimitry Andric for (auto &E : LHS) 2490b57cec5SDimitry Andric if (!RHS.count(E)) 2500b57cec5SDimitry Andric return false; 2510b57cec5SDimitry Andric 2520b57cec5SDimitry Andric return true; 2530b57cec5SDimitry Andric } 2540b57cec5SDimitry Andric 2550b57cec5SDimitry Andric /// Inequality comparison for DenseSet. 2560b57cec5SDimitry Andric /// 2570b57cec5SDimitry Andric /// Equivalent to !(LHS == RHS). See operator== for performance notes. 2580b57cec5SDimitry Andric template <typename ValueT, typename MapTy, typename ValueInfoT> 2590b57cec5SDimitry Andric bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS, 2600b57cec5SDimitry Andric const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) { 2610b57cec5SDimitry Andric return !(LHS == RHS); 2620b57cec5SDimitry Andric } 2630b57cec5SDimitry Andric 2640b57cec5SDimitry Andric } // end namespace detail 2650b57cec5SDimitry Andric 2660b57cec5SDimitry Andric /// Implements a dense probed hash-table based set. 2670b57cec5SDimitry Andric template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>> 2680b57cec5SDimitry Andric class DenseSet : public detail::DenseSetImpl< 2690b57cec5SDimitry Andric ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 2700b57cec5SDimitry Andric detail::DenseSetPair<ValueT>>, 2710b57cec5SDimitry Andric ValueInfoT> { 2720b57cec5SDimitry Andric using BaseT = 2730b57cec5SDimitry Andric detail::DenseSetImpl<ValueT, 2740b57cec5SDimitry Andric DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, 2750b57cec5SDimitry Andric detail::DenseSetPair<ValueT>>, 2760b57cec5SDimitry Andric ValueInfoT>; 2770b57cec5SDimitry Andric 2780b57cec5SDimitry Andric public: 2790b57cec5SDimitry Andric using BaseT::BaseT; 2800b57cec5SDimitry Andric }; 2810b57cec5SDimitry Andric 2820b57cec5SDimitry Andric /// Implements a dense probed hash-table based set with some number of buckets 2830b57cec5SDimitry Andric /// stored inline. 2840b57cec5SDimitry Andric template <typename ValueT, unsigned InlineBuckets = 4, 2850b57cec5SDimitry Andric typename ValueInfoT = DenseMapInfo<ValueT>> 2860b57cec5SDimitry Andric class SmallDenseSet 2870b57cec5SDimitry Andric : public detail::DenseSetImpl< 2880b57cec5SDimitry Andric ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, 2890b57cec5SDimitry Andric ValueInfoT, detail::DenseSetPair<ValueT>>, 2900b57cec5SDimitry Andric ValueInfoT> { 2910b57cec5SDimitry Andric using BaseT = detail::DenseSetImpl< 2920b57cec5SDimitry Andric ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, 2930b57cec5SDimitry Andric ValueInfoT, detail::DenseSetPair<ValueT>>, 2940b57cec5SDimitry Andric ValueInfoT>; 2950b57cec5SDimitry Andric 2960b57cec5SDimitry Andric public: 2970b57cec5SDimitry Andric using BaseT::BaseT; 2980b57cec5SDimitry Andric }; 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andric } // end namespace llvm 3010b57cec5SDimitry Andric 3020b57cec5SDimitry Andric #endif // LLVM_ADT_DENSESET_H 303