SmallSet.h revision 193323
1193323Sed//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the SmallSet class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_SMALLSET_H 15193323Sed#define LLVM_ADT_SMALLSET_H 16193323Sed 17193323Sed#include "llvm/ADT/SmallVector.h" 18193323Sed#include "llvm/ADT/SmallPtrSet.h" 19193323Sed#include <set> 20193323Sed 21193323Sednamespace llvm { 22193323Sed 23193323Sed/// SmallSet - This maintains a set of unique values, optimizing for the case 24193323Sed/// when the set is small (less than N). In this case, the set can be 25193323Sed/// maintained with no mallocs. If the set gets large, we expand to using an 26193323Sed/// std::set to maintain reasonable lookup times. 27193323Sed/// 28193323Sed/// Note that this set does not provide a way to iterate over members in the 29193323Sed/// set. 30193323Sedtemplate <typename T, unsigned N> 31193323Sedclass SmallSet { 32193323Sed /// Use a SmallVector to hold the elements here (even though it will never 33193323Sed /// reach it's 'large' stage) to avoid calling the default ctors of elements 34193323Sed /// we will never use. 35193323Sed SmallVector<T, N> Vector; 36193323Sed std::set<T> Set; 37193323Sed typedef typename SmallVector<T, N>::const_iterator VIterator; 38193323Sed typedef typename SmallVector<T, N>::iterator mutable_iterator; 39193323Sedpublic: 40193323Sed SmallSet() {} 41193323Sed 42193323Sed bool empty() const { return Vector.empty() && Set.empty(); } 43193323Sed unsigned size() const { 44193323Sed return isSmall() ? Vector.size() : Set.size(); 45193323Sed } 46193323Sed 47193323Sed /// count - Return true if the element is in the set. 48193323Sed bool count(const T &V) const { 49193323Sed if (isSmall()) { 50193323Sed // Since the collection is small, just do a linear search. 51193323Sed return vfind(V) != Vector.end(); 52193323Sed } else { 53193323Sed return Set.count(V); 54193323Sed } 55193323Sed } 56193323Sed 57193323Sed /// insert - Insert an element into the set if it isn't already there. 58193323Sed bool insert(const T &V) { 59193323Sed if (!isSmall()) 60193323Sed return Set.insert(V).second; 61193323Sed 62193323Sed VIterator I = vfind(V); 63193323Sed if (I != Vector.end()) // Don't reinsert if it already exists. 64193323Sed return false; 65193323Sed if (Vector.size() < N) { 66193323Sed Vector.push_back(V); 67193323Sed return true; 68193323Sed } 69193323Sed 70193323Sed // Otherwise, grow from vector to set. 71193323Sed while (!Vector.empty()) { 72193323Sed Set.insert(Vector.back()); 73193323Sed Vector.pop_back(); 74193323Sed } 75193323Sed Set.insert(V); 76193323Sed return true; 77193323Sed } 78193323Sed 79193323Sed template <typename IterT> 80193323Sed void insert(IterT I, IterT E) { 81193323Sed for (; I != E; ++I) 82193323Sed insert(*I); 83193323Sed } 84193323Sed 85193323Sed bool erase(const T &V) { 86193323Sed if (!isSmall()) 87193323Sed return Set.erase(V); 88193323Sed for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 89193323Sed if (*I == V) { 90193323Sed Vector.erase(I); 91193323Sed return true; 92193323Sed } 93193323Sed return false; 94193323Sed } 95193323Sed 96193323Sed void clear() { 97193323Sed Vector.clear(); 98193323Sed Set.clear(); 99193323Sed } 100193323Sedprivate: 101193323Sed bool isSmall() const { return Set.empty(); } 102193323Sed 103193323Sed VIterator vfind(const T &V) const { 104193323Sed for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 105193323Sed if (*I == V) 106193323Sed return I; 107193323Sed return Vector.end(); 108193323Sed } 109193323Sed}; 110193323Sed 111193323Sed/// If this set is of pointer values, transparently switch over to using 112193323Sed/// SmallPtrSet for performance. 113193323Sedtemplate <typename PointeeType, unsigned N> 114193323Sedclass SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 115193323Sed 116193323Sed} // end namespace llvm 117193323Sed 118193323Sed#endif 119