LLVM API Documentation

SmallSet.h
Go to the documentation of this file.
00001 //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the SmallSet class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_SMALLSET_H
00015 #define LLVM_ADT_SMALLSET_H
00016 
00017 #include "llvm/ADT/SmallPtrSet.h"
00018 #include "llvm/ADT/SmallVector.h"
00019 #include <set>
00020 
00021 namespace llvm {
00022 
00023 /// SmallSet - This maintains a set of unique values, optimizing for the case
00024 /// when the set is small (less than N).  In this case, the set can be
00025 /// maintained with no mallocs.  If the set gets large, we expand to using an
00026 /// std::set to maintain reasonable lookup times.
00027 ///
00028 /// Note that this set does not provide a way to iterate over members in the
00029 /// set.
00030 template <typename T, unsigned N,  typename C = std::less<T> >
00031 class SmallSet {
00032   /// Use a SmallVector to hold the elements here (even though it will never
00033   /// reach its 'large' stage) to avoid calling the default ctors of elements
00034   /// we will never use.
00035   SmallVector<T, N> Vector;
00036   std::set<T, C> Set;
00037   typedef typename SmallVector<T, N>::const_iterator VIterator;
00038   typedef typename SmallVector<T, N>::iterator mutable_iterator;
00039 public:
00040   SmallSet() {}
00041 
00042   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
00043     return Vector.empty() && Set.empty();
00044   }
00045 
00046   unsigned size() const {
00047     return isSmall() ? Vector.size() : Set.size();
00048   }
00049 
00050   /// count - Return 1 if the element is in the set, 0 otherwise.
00051   unsigned count(const T &V) const {
00052     if (isSmall()) {
00053       // Since the collection is small, just do a linear search.
00054       return vfind(V) == Vector.end() ? 0 : 1;
00055     } else {
00056       return Set.count(V);
00057     }
00058   }
00059 
00060   /// insert - Insert an element into the set if it isn't already there.
00061   /// Returns true if the element is inserted (it was not in the set before).
00062   bool insert(const T &V) {
00063     if (!isSmall())
00064       return Set.insert(V).second;
00065 
00066     VIterator I = vfind(V);
00067     if (I != Vector.end())    // Don't reinsert if it already exists.
00068       return false;
00069     if (Vector.size() < N) {
00070       Vector.push_back(V);
00071       return true;
00072     }
00073 
00074     // Otherwise, grow from vector to set.
00075     while (!Vector.empty()) {
00076       Set.insert(Vector.back());
00077       Vector.pop_back();
00078     }
00079     Set.insert(V);
00080     return true;
00081   }
00082 
00083   template <typename IterT>
00084   void insert(IterT I, IterT E) {
00085     for (; I != E; ++I)
00086       insert(*I);
00087   }
00088   
00089   bool erase(const T &V) {
00090     if (!isSmall())
00091       return Set.erase(V);
00092     for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
00093       if (*I == V) {
00094         Vector.erase(I);
00095         return true;
00096       }
00097     return false;
00098   }
00099 
00100   void clear() {
00101     Vector.clear();
00102     Set.clear();
00103   }
00104 private:
00105   bool isSmall() const { return Set.empty(); }
00106 
00107   VIterator vfind(const T &V) const {
00108     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
00109       if (*I == V)
00110         return I;
00111     return Vector.end();
00112   }
00113 };
00114 
00115 /// If this set is of pointer values, transparently switch over to using
00116 /// SmallPtrSet for performance.
00117 template <typename PointeeType, unsigned N>
00118 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
00119 
00120 } // end namespace llvm
00121 
00122 #endif