SmallSet.h revision cd81d94322a39503e4a3e87b6ee03d4fcb3465fb
1//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/SmallPtrSet.h" 18#include "llvm/ADT/SmallVector.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, typename C = std::less<T> > 31class SmallSet { 32 /// Use a SmallVector to hold the elements here (even though it will never 33 /// reach its 'large' stage) to avoid calling the default ctors of elements 34 /// we will never use. 35 SmallVector<T, N> Vector; 36 std::set<T, C> Set; 37 typedef typename SmallVector<T, N>::const_iterator VIterator; 38 typedef typename SmallVector<T, N>::iterator mutable_iterator; 39public: 40 typedef size_t size_type; 41 SmallSet() {} 42 43 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 44 return Vector.empty() && Set.empty(); 45 } 46 47 size_type size() const { 48 return isSmall() ? Vector.size() : Set.size(); 49 } 50 51 /// count - Return 1 if the element is in the set, 0 otherwise. 52 size_type count(const T &V) const { 53 if (isSmall()) { 54 // Since the collection is small, just do a linear search. 55 return vfind(V) == Vector.end() ? 0 : 1; 56 } else { 57 return Set.count(V); 58 } 59 } 60 61 /// insert - Insert an element into the set if it isn't already there. 62 /// Returns true if the element is inserted (it was not in the set before). 63 bool insert(const T &V) { 64 if (!isSmall()) 65 return Set.insert(V).second; 66 67 VIterator I = vfind(V); 68 if (I != Vector.end()) // Don't reinsert if it already exists. 69 return false; 70 if (Vector.size() < N) { 71 Vector.push_back(V); 72 return true; 73 } 74 75 // Otherwise, grow from vector to set. 76 while (!Vector.empty()) { 77 Set.insert(Vector.back()); 78 Vector.pop_back(); 79 } 80 Set.insert(V); 81 return true; 82 } 83 84 template <typename IterT> 85 void insert(IterT I, IterT E) { 86 for (; I != E; ++I) 87 insert(*I); 88 } 89 90 bool erase(const T &V) { 91 if (!isSmall()) 92 return Set.erase(V); 93 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 94 if (*I == V) { 95 Vector.erase(I); 96 return true; 97 } 98 return false; 99 } 100 101 void clear() { 102 Vector.clear(); 103 Set.clear(); 104 } 105private: 106 bool isSmall() const { return Set.empty(); } 107 108 VIterator vfind(const T &V) const { 109 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 110 if (*I == V) 111 return I; 112 return Vector.end(); 113 } 114}; 115 116/// If this set is of pointer values, transparently switch over to using 117/// SmallPtrSet for performance. 118template <typename PointeeType, unsigned N> 119class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 120 121} // end namespace llvm 122 123#endif 124