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/SmallVector.h"
00018 #include "llvm/ADT/SmallPtrSet.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>
00031 class SmallSet {
00032   /// Use a SmallVector to hold the elements here (even though it will never
00033   /// reach it's 'large' stage) to avoid calling the default ctors of elements
00034   /// we will never use.
00035   SmallVector<T, N> Vector;
00036   std::set<T> 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 empty() const { return Vector.empty() && Set.empty(); }
00043   unsigned size() const {
00044     return isSmall() ? Vector.size() : Set.size();
00045   }
00046 
00047   /// count - Return true if the element is in the set.
00048   bool count(const T &V) const {
00049     if (isSmall()) {
00050       // Since the collection is small, just do a linear search.
00051       return vfind(V) != Vector.end();
00052     } else {
00053       return Set.count(V);
00054     }
00055   }
00056 
00057   /// insert - Insert an element into the set if it isn't already there.
00058   bool insert(const T &V) {
00059     if (!isSmall())
00060       return Set.insert(V).second;
00061 
00062     VIterator I = vfind(V);
00063     if (I != Vector.end())    // Don't reinsert if it already exists.
00064       return false;
00065     if (Vector.size() < N) {
00066       Vector.push_back(V);
00067       return true;
00068     }
00069 
00070     // Otherwise, grow from vector to set.
00071     while (!Vector.empty()) {
00072       Set.insert(Vector.back());
00073       Vector.pop_back();
00074     }
00075     Set.insert(V);
00076     return true;
00077   }
00078 
00079   template <typename IterT>
00080   void insert(IterT I, IterT E) {
00081     for (; I != E; ++I)
00082       insert(*I);
00083   }
00084   
00085   bool erase(const T &V) {
00086     if (!isSmall())
00087       return Set.erase(V);
00088     for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
00089       if (*I == V) {
00090         Vector.erase(I);
00091         return true;
00092       }
00093     return false;
00094   }
00095 
00096   void clear() {
00097     Vector.clear();
00098     Set.clear();
00099   }
00100 private:
00101   bool isSmall() const { return Set.empty(); }
00102 
00103   VIterator vfind(const T &V) const {
00104     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
00105       if (*I == V)
00106         return I;
00107     return Vector.end();
00108   }
00109 };
00110 
00111 /// If this set is of pointer values, transparently switch over to using
00112 /// SmallPtrSet for performance.
00113 template <typename PointeeType, unsigned N>
00114 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
00115 
00116 } // end namespace llvm
00117 
00118 #endif