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