SmallSet.h revision 89502f086901acf6210b711f01726863f8445469
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 /// count - Return true if the element is in the set. 45 unsigned count(const T &V) const { 46 // Since the collection is small, just do a linear search. 47 for (iterator I = begin(), E = end(); I != E; ++I) 48 if (*I == V) 49 return 1; 50 return 0; 51 } 52 53 /// insert - Insert an element into the set if it isn't already there. 54 void insert(const T &V) { 55 if (count(V)) return; // Don't reinsert if it already exists. 56 Vector.push_back(V); 57 } 58 59 void erase(const T &V) { 60 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 61 if (*I == V) { 62 Vector.erase(I); 63 return; 64 } 65 } 66 67 void clear() { 68 Vector.clear(); 69 } 70 71}; 72 73 74} // end namespace llvm 75 76#endif 77