llvm/ADT/DenseSet.h

0001 //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the DenseSet and SmallDenseSet classes.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_DENSESET_H
0015 #define LLVM_ADT_DENSESET_H
0016
0017 #include "llvm/ADT/DenseMap.h"
0018 #include "llvm/ADT/DenseMapInfo.h"
0019 #include "llvm/Support/MathExtras.h"
0020 #include "llvm/Support/type_traits.h"
0021 #include <cstddef>
0022 #include <initializer_list>
0023 #include <iterator>
0024 #include <utility>
0025
0026 namespace llvm {
0027
0028 namespace detail {
0029
0030 struct DenseSetEmpty {};
0031
0032 // Use the empty base class trick so we can create a DenseMap where the buckets
0033 // contain only a single item.
0034 template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
0035   KeyT key;
0036
0037 public:
0038   KeyT &getFirst() { return key; }
0039   const KeyT &getFirst() const { return key; }
0040   DenseSetEmpty &getSecond() { return *this; }
0041   const DenseSetEmpty &getSecond() const { return *this; }
0042 };
0043
0044 /// Base class for DenseSet and DenseSmallSet.
0045 ///
0046 /// MapTy should be either
0047 ///
0048 ///   DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
0049 ///            detail::DenseSetPair<ValueT>>
0050 ///
0051 /// or the equivalent SmallDenseMap type.  ValueInfoT must implement the
0052 /// DenseMapInfo "concept".
0053 template <typename ValueT, typename MapTy, typename ValueInfoT>
0054 class DenseSetImpl {
0055   static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
0056                 "DenseMap buckets unexpectedly large!");
0057   MapTy TheMap;
0058
0059   template <typename T>
0060   using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
0061
0062 public:
0063   using key_type = ValueT;
0064   using value_type = ValueT;
0065   using size_type = unsigned;
0066
0067   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
0068
0069   template <typename InputIt>
0070   DenseSetImpl(const InputIt &I, const InputIt &E)
0071       : DenseSetImpl(PowerOf2Ceil(std::distance(I, E))) {
0072     insert(I, E);
0073   }
0074
0075   DenseSetImpl(std::initializer_list<ValueT> Elems)
0076       : DenseSetImpl(PowerOf2Ceil(Elems.size())) {
0077     insert(Elems.begin(), Elems.end());
0078   }
0079
0080   bool empty() const { return TheMap.empty(); }
0081   size_type size() const { return TheMap.size(); }
0082   size_t getMemorySize() const { return TheMap.getMemorySize(); }
0083
0084   /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
0085   /// the Size of the set.
0086   void resize(size_t Size) { TheMap.resize(Size); }
0087
0088   /// Grow the DenseSet so that it can contain at least \p NumEntries items
0089   /// before resizing again.
0090   void reserve(size_t Size) { TheMap.reserve(Size); }
0091
0092   void clear() { TheMap.clear(); }
0093
0094   /// Return 1 if the specified key is in the set, 0 otherwise.
0095   size_type count(const_arg_type_t<ValueT> V) const { return TheMap.count(V); }
0096
0097   bool erase(const ValueT &V) { return TheMap.erase(V); }
0098
0099   void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
0100
0101   // Iterators.
0102
0103   class ConstIterator;
0104
0105   class Iterator {
0106     typename MapTy::iterator I;
0107     friend class DenseSetImpl;
0108     friend class ConstIterator;
0109
0110   public:
0111     using difference_type = typename MapTy::iterator::difference_type;
0112     using value_type = ValueT;
0113     using pointer = value_type *;
0114     using reference = value_type &;
0115     using iterator_category = std::forward_iterator_tag;
0116
0117     Iterator() = default;
0118     Iterator(const typename MapTy::iterator &i) : I(i) {}
0119
0120     ValueT &operator*() { return I->getFirst(); }
0121     const ValueT &operator*() const { return I->getFirst(); }
0122     ValueT *operator->() { return &I->getFirst(); }
0123     const ValueT *operator->() const { return &I->getFirst(); }
0124
0125     Iterator &operator++() {
0126       ++I;
0127       return *this;
0128     }
0129     Iterator operator++(int) {
0130       auto T = *this;
0131       ++I;
0132       return T;
0133     }
0134     friend bool operator==(const Iterator &X, const Iterator &Y) {
0135       return X.I == Y.I;
0136     }
0137     friend bool operator!=(const Iterator &X, const Iterator &Y) {
0138       return X.I != Y.I;
0139     }
0140   };
0141
0142   class ConstIterator {
0143     typename MapTy::const_iterator I;
0144     friend class DenseSetImpl;
0145     friend class Iterator;
0146
0147   public:
0148     using difference_type = typename MapTy::const_iterator::difference_type;
0149     using value_type = ValueT;
0150     using pointer = const value_type *;
0151     using reference = const value_type &;
0152     using iterator_category = std::forward_iterator_tag;
0153
0154     ConstIterator() = default;
0155     ConstIterator(const Iterator &B) : I(B.I) {}
0156     ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
0157
0158     const ValueT &operator*() const { return I->getFirst(); }
0159     const ValueT *operator->() const { return &I->getFirst(); }
0160
0161     ConstIterator &operator++() {
0162       ++I;
0163       return *this;
0164     }
0165     ConstIterator operator++(int) {
0166       auto T = *this;
0167       ++I;
0168       return T;
0169     }
0170     friend bool operator==(const ConstIterator &X, const ConstIterator &Y) {
0171       return X.I == Y.I;
0172     }
0173     friend bool operator!=(const ConstIterator &X, const ConstIterator &Y) {
0174       return X.I != Y.I;
0175     }
0176   };
0177
0178   using iterator = Iterator;
0179   using const_iterator = ConstIterator;
0180
0181   iterator begin() { return Iterator(TheMap.begin()); }
0182   iterator end() { return Iterator(TheMap.end()); }
0183
0184   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
0185   const_iterator end() const { return ConstIterator(TheMap.end()); }
0186
0187   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
0188   const_iterator find(const_arg_type_t<ValueT> V) const {
0189     return ConstIterator(TheMap.find(V));
0190   }
0191
0192   /// Check if the set contains the given element.
0193   bool contains(const_arg_type_t<ValueT> V) const {
0194     return TheMap.find(V) != TheMap.end();
0195   }
0196
0197   /// Alternative version of find() which allows a different, and possibly less
0198   /// expensive, key type.
0199   /// The DenseMapInfo is responsible for supplying methods
0200   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
0201   /// used.
0202   template <class LookupKeyT> iterator find_as(const LookupKeyT &Val) {
0203     return Iterator(TheMap.find_as(Val));
0204   }
0205   template <class LookupKeyT>
0206   const_iterator find_as(const LookupKeyT &Val) const {
0207     return ConstIterator(TheMap.find_as(Val));
0208   }
0209
0210   void erase(Iterator I) { return TheMap.erase(I.I); }
0211   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
0212
0213   std::pair<iterator, bool> insert(const ValueT &V) {
0214     detail::DenseSetEmpty Empty;
0215     return TheMap.try_emplace(V, Empty);
0216   }
0217
0218   std::pair<iterator, bool> insert(ValueT &&V) {
0219     detail::DenseSetEmpty Empty;
0220     return TheMap.try_emplace(std::move(V), Empty);
0221   }
0222
0223   /// Alternative version of insert that uses a different (and possibly less
0224   /// expensive) key type.
0225   template <typename LookupKeyT>
0226   std::pair<iterator, bool> insert_as(const ValueT &V,
0227                                       const LookupKeyT &LookupKey) {
0228     return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
0229   }
0230   template <typename LookupKeyT>
0231   std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
0232     return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
0233   }
0234
0235   // Range insertion of values.
0236   template <typename InputIt> void insert(InputIt I, InputIt E) {
0237     for (; I != E; ++I)
0238       insert(*I);
0239   }
0240 };
0241
0242 /// Equality comparison for DenseSet.
0243 ///
0244 /// Iterates over elements of LHS confirming that each element is also a member
0245 /// of RHS, and that RHS contains no additional values.
0246 /// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst
0247 /// case is O(N^2) (if every hash collides).
0248 template <typename ValueT, typename MapTy, typename ValueInfoT>
0249 bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
0250                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
0251   if (LHS.size() != RHS.size())
0252     return false;
0253
0254   for (auto &E : LHS)
0255     if (!RHS.count(E))
0256       return false;
0257
0258   return true;
0259 }
0260
0261 /// Inequality comparison for DenseSet.
0262 ///
0263 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
0264 template <typename ValueT, typename MapTy, typename ValueInfoT>
0265 bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
0266                 const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
0267   return !(LHS == RHS);
0268 }
0269
0270 } // end namespace detail
0271
0272 /// Implements a dense probed hash-table based set.
0273 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
0274 class DenseSet : public detail::DenseSetImpl<
0275                      ValueT,
0276                      DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
0277                               detail::DenseSetPair<ValueT>>,
0278                      ValueInfoT> {
0279   using BaseT =
0280       detail::DenseSetImpl<ValueT,
0281                            DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
0282                                     detail::DenseSetPair<ValueT>>,
0283                            ValueInfoT>;
0284
0285 public:
0286   using BaseT::BaseT;
0287 };
0288
0289 /// Implements a dense probed hash-table based set with some number of buckets
0290 /// stored inline.
0291 template <typename ValueT, unsigned InlineBuckets = 4,
0292           typename ValueInfoT = DenseMapInfo<ValueT>>
0293 class SmallDenseSet
0294     : public detail::DenseSetImpl<
0295           ValueT,
0296           SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
0297                         ValueInfoT, detail::DenseSetPair<ValueT>>,
0298           ValueInfoT> {
0299   using BaseT = detail::DenseSetImpl<
0300       ValueT,
0301       SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT,
0302                     detail::DenseSetPair<ValueT>>,
0303       ValueInfoT>;
0304
0305 public:
0306   using BaseT::BaseT;
0307 };
0308
0309 } // end namespace llvm
0310
0311 #endif // LLVM_ADT_DENSESET_H