DenseSet.h 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
  1. //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- C++ -*-===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // This file defines the DenseSet class.
  11. //
  12. //===----------------------------------------------------------------------===//
  13. #ifndef LLVM_ADT_DENSESET_H
  14. #define LLVM_ADT_DENSESET_H
  15. #include "llvm/ADT/DenseMap.h"
  16. namespace llvm {
  17. namespace detail {
  18. struct DenseSetEmpty {};
  19. // Use the empty base class trick so we can create a DenseMap where the buckets
  20. // contain only a single item.
  21. template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
  22. KeyT key;
  23. public:
  24. KeyT &getFirst() { return key; }
  25. const KeyT &getFirst() const { return key; }
  26. DenseSetEmpty &getSecond() { return *this; }
  27. const DenseSetEmpty &getSecond() const { return *this; }
  28. };
  29. }
  30. /// DenseSet - This implements a dense probed hash-table based set.
  31. template<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> >
  32. class DenseSet {
  33. typedef DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
  34. detail::DenseSetPair<ValueT>> MapTy;
  35. static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
  36. "DenseMap buckets unexpectedly large!");
  37. MapTy TheMap;
  38. public:
  39. typedef ValueT key_type;
  40. typedef ValueT value_type;
  41. typedef unsigned size_type;
  42. explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
  43. bool empty() const { return TheMap.empty(); }
  44. size_type size() const { return TheMap.size(); }
  45. size_t getMemorySize() const { return TheMap.getMemorySize(); }
  46. /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
  47. /// the Size of the set.
  48. void resize(size_t Size) { TheMap.resize(Size); }
  49. void clear() {
  50. TheMap.clear();
  51. }
  52. /// Return 1 if the specified key is in the set, 0 otherwise.
  53. size_type count(const ValueT &V) const {
  54. return TheMap.count(V);
  55. }
  56. bool erase(const ValueT &V) {
  57. return TheMap.erase(V);
  58. }
  59. void swap(DenseSet& RHS) {
  60. TheMap.swap(RHS.TheMap);
  61. }
  62. // Iterators.
  63. class Iterator {
  64. typename MapTy::iterator I;
  65. friend class DenseSet;
  66. public:
  67. typedef typename MapTy::iterator::difference_type difference_type;
  68. typedef ValueT value_type;
  69. typedef value_type *pointer;
  70. typedef value_type &reference;
  71. typedef std::forward_iterator_tag iterator_category;
  72. Iterator(const typename MapTy::iterator &i) : I(i) {}
  73. ValueT &operator*() { return I->getFirst(); }
  74. ValueT *operator->() { return &I->getFirst(); }
  75. Iterator& operator++() { ++I; return *this; }
  76. bool operator==(const Iterator& X) const { return I == X.I; }
  77. bool operator!=(const Iterator& X) const { return I != X.I; }
  78. };
  79. class ConstIterator {
  80. typename MapTy::const_iterator I;
  81. friend class DenseSet;
  82. public:
  83. typedef typename MapTy::const_iterator::difference_type difference_type;
  84. typedef ValueT value_type;
  85. typedef value_type *pointer;
  86. typedef value_type &reference;
  87. typedef std::forward_iterator_tag iterator_category;
  88. ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
  89. const ValueT &operator*() { return I->getFirst(); }
  90. const ValueT *operator->() { return &I->getFirst(); }
  91. ConstIterator& operator++() { ++I; return *this; }
  92. bool operator==(const ConstIterator& X) const { return I == X.I; }
  93. bool operator!=(const ConstIterator& X) const { return I != X.I; }
  94. };
  95. typedef Iterator iterator;
  96. typedef ConstIterator const_iterator;
  97. iterator begin() { return Iterator(TheMap.begin()); }
  98. iterator end() { return Iterator(TheMap.end()); }
  99. const_iterator begin() const { return ConstIterator(TheMap.begin()); }
  100. const_iterator end() const { return ConstIterator(TheMap.end()); }
  101. iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }
  102. /// Alternative version of find() which allows a different, and possibly less
  103. /// expensive, key type.
  104. /// The DenseMapInfo is responsible for supplying methods
  105. /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
  106. /// used.
  107. template <class LookupKeyT>
  108. iterator find_as(const LookupKeyT &Val) {
  109. return Iterator(TheMap.find_as(Val));
  110. }
  111. template <class LookupKeyT>
  112. const_iterator find_as(const LookupKeyT &Val) const {
  113. return ConstIterator(TheMap.find_as(Val));
  114. }
  115. void erase(Iterator I) { return TheMap.erase(I.I); }
  116. void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
  117. std::pair<iterator, bool> insert(const ValueT &V) {
  118. detail::DenseSetEmpty Empty;
  119. return TheMap.insert(std::make_pair(V, Empty));
  120. }
  121. // Range insertion of values.
  122. template<typename InputIt>
  123. void insert(InputIt I, InputIt E) {
  124. for (; I != E; ++I)
  125. insert(*I);
  126. }
  127. };
  128. } // end namespace llvm
  129. #endif