SmallSet.h revision 182907645c9c2da22dba78255f0c8541f5d9f50d
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 19namespace llvm { 20 21/// SmallSet - This maintains a set of unique values, optimizing for the case 22/// when the set is small (less than N). In this case, the set can be 23/// maintained with no mallocs. 24/// 25/// Note that this set does not guarantee that the elements in the set will be 26/// ordered. 27template <typename T, unsigned N> 28class SmallSet { 29 SmallVector<T, N> Vector; 30 typedef typename SmallVector<T, N>::iterator mutable_iterator; 31public: 32 SmallSet() {} 33 34 // Support iteration. 35 typedef typename SmallVector<T, N>::const_iterator iterator; 36 typedef typename SmallVector<T, N>::const_iterator const_iterator; 37 38 iterator begin() const { return Vector.begin(); } 39 iterator end() const { return Vector.end(); } 40 41 bool empty() const { return Vector.empty(); } 42 unsigned size() const { return Vector.size(); } 43 44 iterator find(const T &V) const { 45 for (iterator I = begin(), E = end(); I != E; ++I) 46 if (*I == V) 47 return I; 48 return end(); 49 } 50 51 /// count - Return true if the element is in the set. 52 unsigned count(const T &V) const { 53 // Since the collection is small, just do a linear search. 54 return find(V) != end(); 55 } 56 57 /// insert - Insert an element into the set if it isn't already there. 58 std::pair<iterator,bool> insert(const T &V) { 59 iterator I = find(V); 60 if (I == end()) // Don't reinsert if it already exists. 61 return std::make_pair(I, false); 62 Vector.push_back(V); 63 return std::make_pair(end()-1, true); 64 } 65 66 void erase(const T &V) { 67 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 68 if (*I == V) { 69 Vector.erase(I); 70 return; 71 } 72 } 73 74 void clear() { 75 Vector.clear(); 76 } 77 78}; 79 80 81} // end namespace llvm 82 83#endif 84