SmallSet.h revision b358f0254d7b6470b1ed84a97b601ef102b4e88e
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#include "llvm/ADT/SmallPtrSet.h" 19#include <set> 20 21namespace llvm { 22 23/// SmallSet - This maintains a set of unique values, optimizing for the case 24/// when the set is small (less than N). In this case, the set can be 25/// maintained with no mallocs. If the set gets large, we expand to using an 26/// std::set to maintain reasonable lookup times. 27/// 28/// Note that this set does not provide a way to iterate over members in the 29/// set. 30template <typename T, unsigned N> 31class SmallSet { 32 /// Use a SmallVector to hold the elements here (even though it will never 33 /// reach it's 'large' stage) to avoid calling the default ctors of elements 34 /// we will never use. 35 SmallVector<T, N> Vector; 36 std::set<T> Set; 37 typedef typename SmallVector<T, N>::const_iterator VIterator; 38 typedef typename SmallVector<T, N>::iterator mutable_iterator; 39public: 40 SmallSet() {} 41 42 bool empty() const { return Vector.empty() && Set.empty(); } 43 unsigned size() const { 44 return isSmall() ? Vector.size() : Set.size(); 45 } 46 47 /// count - Return true if the element is in the set. 48 bool count(const T &V) const { 49 if (isSmall()) { 50 // Since the collection is small, just do a linear search. 51 return vfind(V) != Vector.end(); 52 } else { 53 return Set.count(V); 54 } 55 } 56 57 /// insert - Insert an element into the set if it isn't already there. 58 bool insert(const T &V) { 59 if (!isSmall()) 60 return Set.insert(V).second; 61 62 VIterator I = vfind(V); 63 if (I != Vector.end()) // Don't reinsert if it already exists. 64 return false; 65 if (Vector.size() < N) { 66 Vector.push_back(V); 67 return true; 68 } 69 70 // Otherwise, grow from vector to set. 71 while (!Vector.empty()) { 72 Set.insert(Vector.back()); 73 Vector.pop_back(); 74 } 75 Set.insert(V); 76 return true; 77 } 78 79 bool erase(const T &V) { 80 if (!isSmall()) 81 return Set.erase(V).second; 82 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 83 if (*I == V) { 84 Vector.erase(I); 85 return true; 86 } 87 return false; 88 } 89 90 void clear() { 91 Vector.clear(); 92 Set.clear(); 93 } 94private: 95 bool isSmall() const { return Set.empty(); } 96 97 VIterator vfind(const T &V) const { 98 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 99 if (*I == V) 100 return I; 101 return Vector.end(); 102 } 103}; 104 105/// If this set is of pointer values, transparently switch over to using 106/// SmallPtrSet for performance. 107template <typename PointeeType, unsigned N> 108class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 109 110} // end namespace llvm 111 112#endif 113