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 17252723Sdim#include "llvm/ADT/SmallPtrSet.h" 18193323Sed#include "llvm/ADT/SmallVector.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. 30235633Sdimtemplate <typename T, unsigned N, typename C = std::less<T> > 31193323Sedclass SmallSet { 32193323Sed /// Use a SmallVector to hold the elements here (even though it will never 33198090Srdivacky /// reach its 'large' stage) to avoid calling the default ctors of elements 34193323Sed /// we will never use. 35193323Sed SmallVector<T, N> Vector; 36235633Sdim std::set<T, C> 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. 58252723Sdim /// Returns true if the element is inserted (it was not in the set before). 59193323Sed bool insert(const T &V) { 60193323Sed if (!isSmall()) 61193323Sed return Set.insert(V).second; 62193323Sed 63193323Sed VIterator I = vfind(V); 64193323Sed if (I != Vector.end()) // Don't reinsert if it already exists. 65193323Sed return false; 66193323Sed if (Vector.size() < N) { 67193323Sed Vector.push_back(V); 68193323Sed return true; 69193323Sed } 70193323Sed 71193323Sed // Otherwise, grow from vector to set. 72193323Sed while (!Vector.empty()) { 73193323Sed Set.insert(Vector.back()); 74193323Sed Vector.pop_back(); 75193323Sed } 76193323Sed Set.insert(V); 77193323Sed return true; 78193323Sed } 79193323Sed 80193323Sed template <typename IterT> 81193323Sed void insert(IterT I, IterT E) { 82193323Sed for (; I != E; ++I) 83193323Sed insert(*I); 84193323Sed } 85193323Sed 86193323Sed bool erase(const T &V) { 87193323Sed if (!isSmall()) 88193323Sed return Set.erase(V); 89193323Sed for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 90193323Sed if (*I == V) { 91193323Sed Vector.erase(I); 92193323Sed return true; 93193323Sed } 94193323Sed return false; 95193323Sed } 96193323Sed 97193323Sed void clear() { 98193323Sed Vector.clear(); 99193323Sed Set.clear(); 100193323Sed } 101193323Sedprivate: 102193323Sed bool isSmall() const { return Set.empty(); } 103193323Sed 104193323Sed VIterator vfind(const T &V) const { 105193323Sed for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 106193323Sed if (*I == V) 107193323Sed return I; 108193323Sed return Vector.end(); 109193323Sed } 110193323Sed}; 111193323Sed 112193323Sed/// If this set is of pointer values, transparently switch over to using 113193323Sed/// SmallPtrSet for performance. 114193323Sedtemplate <typename PointeeType, unsigned N> 115193323Sedclass SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 116193323Sed 117193323Sed} // end namespace llvm 118193323Sed 119193323Sed#endif 120