Home | History | Annotate | Download | only in ADT 
      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 
     14 #ifndef LLVM_ADT_DENSESET_H
     15 #define LLVM_ADT_DENSESET_H
     16 
     17 #include "llvm/ADT/DenseMap.h"
     18 
     19 namespace llvm {
     20 
     21 /// DenseSet - This implements a dense probed hash-table based set.
     22 ///
     23 /// FIXME: This is currently implemented directly in terms of DenseMap, this
     24 /// should be optimized later if there is a need.
     25 template<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> >
     26 class DenseSet {
     27   typedef DenseMap<ValueT, char, ValueInfoT> MapTy;
     28   MapTy TheMap;
     29 public:
     30   DenseSet(const DenseSet &Other) : TheMap(Other.TheMap) {}
     31   explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
     32 
     33   bool empty() const { return TheMap.empty(); }
     34   unsigned size() const { return TheMap.size(); }
     35 
     36   /// Grow the denseset so that it has at least Size buckets. Does not shrink
     37   void resize(size_t Size) { TheMap.resize(Size); }
     38 
     39   void clear() {
     40     TheMap.clear();
     41   }
     42 
     43   bool count(const ValueT &V) const {
     44     return TheMap.count(V);
     45   }
     46 
     47   bool erase(const ValueT &V) {
     48     return TheMap.erase(V);
     49   }
     50 
     51   void swap(DenseSet& RHS) {
     52     TheMap.swap(RHS.TheMap);
     53   }
     54 
     55   DenseSet &operator=(const DenseSet &RHS) {
     56     TheMap = RHS.TheMap;
     57     return *this;
     58   }
     59 
     60   // Iterators.
     61 
     62   class Iterator {
     63     typename MapTy::iterator I;
     64     friend class DenseSet;
     65   public:
     66     typedef typename MapTy::iterator::difference_type difference_type;
     67     typedef ValueT value_type;
     68     typedef value_type *pointer;
     69     typedef value_type &reference;
     70     typedef std::forward_iterator_tag iterator_category;
     71 
     72     Iterator(const typename MapTy::iterator &i) : I(i) {}
     73 
     74     ValueT& operator*() { return I->first; }
     75     ValueT* operator->() { return &I->first; }
     76 
     77     Iterator& operator++() { ++I; return *this; }
     78     bool operator==(const Iterator& X) const { return I == X.I; }
     79     bool operator!=(const Iterator& X) const { return I != X.I; }
     80   };
     81 
     82   class ConstIterator {
     83     typename MapTy::const_iterator I;
     84     friend class DenseSet;
     85   public:
     86     typedef typename MapTy::const_iterator::difference_type difference_type;
     87     typedef ValueT value_type;
     88     typedef value_type *pointer;
     89     typedef value_type &reference;
     90     typedef std::forward_iterator_tag iterator_category;
     91 
     92     ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
     93 
     94     const ValueT& operator*() { return I->first; }
     95     const ValueT* operator->() { return &I->first; }
     96 
     97     ConstIterator& operator++() { ++I; return *this; }
     98     bool operator==(const ConstIterator& X) const { return I == X.I; }
     99     bool operator!=(const ConstIterator& X) const { return I != X.I; }
    100   };
    101 
    102   typedef Iterator      iterator;
    103   typedef ConstIterator const_iterator;
    104 
    105   iterator begin() { return Iterator(TheMap.begin()); }
    106   iterator end() { return Iterator(TheMap.end()); }
    107 
    108   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
    109   const_iterator end() const { return ConstIterator(TheMap.end()); }
    110 
    111   iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }
    112   void erase(Iterator I) { return TheMap.erase(I.I); }
    113   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
    114 
    115   std::pair<iterator, bool> insert(const ValueT &V) {
    116     return TheMap.insert(std::make_pair(V, 0));
    117   }
    118 
    119   // Range insertion of values.
    120   template<typename InputIt>
    121   void insert(InputIt I, InputIt E) {
    122     for (; I != E; ++I)
    123       insert(*I);
    124   }
    125 };
    126 
    127 } // end namespace llvm
    128 
    129 #endif
    130