189502f086901acf6210b711f01726863f8445469Chris Lattner//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===// 289502f086901acf6210b711f01726863f8445469Chris Lattner// 389502f086901acf6210b711f01726863f8445469Chris Lattner// The LLVM Compiler Infrastructure 489502f086901acf6210b711f01726863f8445469Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 789502f086901acf6210b711f01726863f8445469Chris Lattner// 889502f086901acf6210b711f01726863f8445469Chris Lattner//===----------------------------------------------------------------------===// 989502f086901acf6210b711f01726863f8445469Chris Lattner// 1089502f086901acf6210b711f01726863f8445469Chris Lattner// This file defines the SmallSet class. 1189502f086901acf6210b711f01726863f8445469Chris Lattner// 1289502f086901acf6210b711f01726863f8445469Chris Lattner//===----------------------------------------------------------------------===// 1389502f086901acf6210b711f01726863f8445469Chris Lattner 1489502f086901acf6210b711f01726863f8445469Chris Lattner#ifndef LLVM_ADT_SMALLSET_H 1589502f086901acf6210b711f01726863f8445469Chris Lattner#define LLVM_ADT_SMALLSET_H 1689502f086901acf6210b711f01726863f8445469Chris Lattner 17b358f0254d7b6470b1ed84a97b601ef102b4e88eChris Lattner#include "llvm/ADT/SmallPtrSet.h" 18255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/SmallVector.h" 19a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner#include <set> 2089502f086901acf6210b711f01726863f8445469Chris Lattner 2189502f086901acf6210b711f01726863f8445469Chris Lattnernamespace llvm { 2289502f086901acf6210b711f01726863f8445469Chris Lattner 2389502f086901acf6210b711f01726863f8445469Chris Lattner/// SmallSet - This maintains a set of unique values, optimizing for the case 2489502f086901acf6210b711f01726863f8445469Chris Lattner/// when the set is small (less than N). In this case, the set can be 25a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner/// maintained with no mallocs. If the set gets large, we expand to using an 26a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner/// std::set to maintain reasonable lookup times. 2789502f086901acf6210b711f01726863f8445469Chris Lattner/// 28a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner/// Note that this set does not provide a way to iterate over members in the 29a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner/// set. 300fcccd4d45b593bc11e56ff5be36a04836749376Chris Lattnertemplate <typename T, unsigned N, typename C = std::less<T> > 3189502f086901acf6210b711f01726863f8445469Chris Lattnerclass SmallSet { 32a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner /// Use a SmallVector to hold the elements here (even though it will never 3375144f93eb7e4dbf22d308d21581ae255dd520c6Dan Gohman /// reach its 'large' stage) to avoid calling the default ctors of elements 34a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner /// we will never use. 3589502f086901acf6210b711f01726863f8445469Chris Lattner SmallVector<T, N> Vector; 360fcccd4d45b593bc11e56ff5be36a04836749376Chris Lattner std::set<T, C> Set; 37a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner typedef typename SmallVector<T, N>::const_iterator VIterator; 3889502f086901acf6210b711f01726863f8445469Chris Lattner typedef typename SmallVector<T, N>::iterator mutable_iterator; 3989502f086901acf6210b711f01726863f8445469Chris Lattnerpublic: 40cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef size_t size_type; 4189502f086901acf6210b711f01726863f8445469Chris Lattner SmallSet() {} 4289502f086901acf6210b711f01726863f8445469Chris Lattner 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Vector.empty() && Set.empty(); 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 47cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type size() const { 48a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return isSmall() ? Vector.size() : Set.size(); 49182907645c9c2da22dba78255f0c8541f5d9f50dChris Lattner } 503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// count - Return 1 if the element is in the set, 0 otherwise. 52cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type count(const T &V) const { 53a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (isSmall()) { 54a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner // Since the collection is small, just do a linear search. 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return vfind(V) == Vector.end() ? 0 : 1; 56a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner } else { 57a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return Set.count(V); 58a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner } 5989502f086901acf6210b711f01726863f8445469Chris Lattner } 603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6189502f086901acf6210b711f01726863f8445469Chris Lattner /// insert - Insert an element into the set if it isn't already there. 625cb04ae563edc3c46464a7aa00e24c05c524547bNadav Rotem /// Returns true if the element is inserted (it was not in the set before). 63bcabbfc310bfd3cd87836f7967d1d71713d91a1dChris Lattner bool insert(const T &V) { 64a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (!isSmall()) 65a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return Set.insert(V).second; 663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 67a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner VIterator I = vfind(V); 68a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (I != Vector.end()) // Don't reinsert if it already exists. 69bcabbfc310bfd3cd87836f7967d1d71713d91a1dChris Lattner return false; 70a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (Vector.size() < N) { 71a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner Vector.push_back(V); 72a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return true; 73a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner } 74a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner 75a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner // Otherwise, grow from vector to set. 76a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner while (!Vector.empty()) { 77a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner Set.insert(Vector.back()); 78a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner Vector.pop_back(); 79a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner } 80a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner Set.insert(V); 81bcabbfc310bfd3cd87836f7967d1d71713d91a1dChris Lattner return true; 8289502f086901acf6210b711f01726863f8445469Chris Lattner } 833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 84fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump template <typename IterT> 85fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump void insert(IterT I, IterT E) { 86fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump for (; I != E; ++I) 87fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump insert(*I); 88fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump } 89fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 90a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner bool erase(const T &V) { 91a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (!isSmall()) 927235928b45e6a353f6fcca8b9a40e83ab3420fb0Chris Lattner return Set.erase(V); 9389502f086901acf6210b711f01726863f8445469Chris Lattner for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 9489502f086901acf6210b711f01726863f8445469Chris Lattner if (*I == V) { 9589502f086901acf6210b711f01726863f8445469Chris Lattner Vector.erase(I); 96a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return true; 9789502f086901acf6210b711f01726863f8445469Chris Lattner } 98a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return false; 9989502f086901acf6210b711f01726863f8445469Chris Lattner } 1003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10189502f086901acf6210b711f01726863f8445469Chris Lattner void clear() { 10289502f086901acf6210b711f01726863f8445469Chris Lattner Vector.clear(); 103a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner Set.clear(); 104a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner } 105a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattnerprivate: 106a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner bool isSmall() const { return Set.empty(); } 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 108a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner VIterator vfind(const T &V) const { 109a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I) 110a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner if (*I == V) 111a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return I; 112a5b4760cbd23d49b6d94bc56d85b5a499fa54802Chris Lattner return Vector.end(); 11389502f086901acf6210b711f01726863f8445469Chris Lattner } 11489502f086901acf6210b711f01726863f8445469Chris Lattner}; 11589502f086901acf6210b711f01726863f8445469Chris Lattner 116b358f0254d7b6470b1ed84a97b601ef102b4e88eChris Lattner/// If this set is of pointer values, transparently switch over to using 117b358f0254d7b6470b1ed84a97b601ef102b4e88eChris Lattner/// SmallPtrSet for performance. 118b358f0254d7b6470b1ed84a97b601ef102b4e88eChris Lattnertemplate <typename PointeeType, unsigned N> 119b358f0254d7b6470b1ed84a97b601ef102b4e88eChris Lattnerclass SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {}; 12089502f086901acf6210b711f01726863f8445469Chris Lattner 12189502f086901acf6210b711f01726863f8445469Chris Lattner} // end namespace llvm 12289502f086901acf6210b711f01726863f8445469Chris Lattner 12389502f086901acf6210b711f01726863f8445469Chris Lattner#endif 124