include/llvm/ADT/SmallSet.h

   1 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SmallSet class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLSET_H
  15 #define LLVM_ADT_SMALLSET_H
  16
  17 #include "llvm/ADT/SmallVector.h"
  18
  19 namespace llvm {
  20
  21 /// SmallSet - This maintains a set of unique values, optimizing for the case
  22 /// when the set is small (less than N).  In this case, the set can be
  23 /// maintained with no mallocs.
  24 ///
  25 /// Note that this set does not guarantee that the elements in the set will be
  26 /// ordered.
  27 template <typename T, unsigned N>
  28 class SmallSet {
  29   SmallVector<T, N> Vector;
  30   typedef typename SmallVector<T, N>::iterator mutable_iterator;
  31 public:
  32   SmallSet() {}
  33
  34   // Support iteration.
  35   typedef typename SmallVector<T, N>::const_iterator iterator;
  36   typedef typename SmallVector<T, N>::const_iterator const_iterator;
  37
  38   iterator begin() const { return Vector.begin(); }
  39   iterator end() const { return Vector.end(); }
  40
  41   bool empty() const { return Vector.empty(); }
  42   unsigned size() const { return Vector.size(); }
  43
  44   /// count - Return true if the element is in the set.
  45   unsigned count(const T &V) const {
  46     // Since the collection is small, just do a linear search.
  47     for (iterator I = begin(), E = end(); I != E; ++I)
  48       if (*I == V)
  49         return 1;
  50     return 0;
  51   }
  52
  53   /// insert - Insert an element into the set if it isn't already there.
  54   void insert(const T &V) {
  55     if (count(V)) return;   // Don't reinsert if it already exists.
  56     Vector.push_back(V);
  57   }
  58
  59   void erase(const T &V) {
  60     for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
  61       if (*I == V) {
  62         Vector.erase(I);
  63         return;
  64       }
  65   }
  66
  67   void clear() {
  68     Vector.clear();
  69   }
  70
  71 };
  72
  73
  74 } // end namespace llvm
  75
  76 #endif