WPILibC++  unspecified
SmallSet.h
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/None.h"
18 #include "llvm/SmallPtrSet.h"
19 #include "llvm/SmallVector.h"
20 #include <set>
21 
22 namespace llvm {
23 
31 template <typename T, unsigned N, typename C = std::less<T> >
32 class SmallSet {
36  SmallVector<T, N> Vector;
37  std::set<T, C> Set;
38  typedef typename SmallVector<T, N>::const_iterator VIterator;
39  typedef typename SmallVector<T, N>::iterator mutable_iterator;
40 
41  // In small mode SmallPtrSet uses linear search for the elements, so it is
42  // not a good idea to choose this value too high. You may consider using a
43  // DenseSet<> instead if you expect many elements in the set.
44  static_assert(N <= 32, "N should be small");
45 
46 public:
47  typedef size_t size_type;
48  SmallSet() {}
49 
50  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
51  return Vector.empty() && Set.empty();
52  }
53 
54  size_type size() const {
55  return isSmall() ? Vector.size() : Set.size();
56  }
57 
59  size_type count(const T &V) const {
60  if (isSmall()) {
61  // Since the collection is small, just do a linear search.
62  return vfind(V) == Vector.end() ? 0 : 1;
63  } else {
64  return Set.count(V);
65  }
66  }
67 
73  // FIXME: Add iterators that abstract over the small and large form, and then
74  // return those here.
75  std::pair<NoneType, bool> insert(const T &V) {
76  if (!isSmall())
77  return std::make_pair(None, Set.insert(V).second);
78 
79  VIterator I = vfind(V);
80  if (I != Vector.end()) // Don't reinsert if it already exists.
81  return std::make_pair(None, false);
82  if (Vector.size() < N) {
83  Vector.push_back(V);
84  return std::make_pair(None, true);
85  }
86 
87  // Otherwise, grow from vector to set.
88  while (!Vector.empty()) {
89  Set.insert(Vector.back());
90  Vector.pop_back();
91  }
92  Set.insert(V);
93  return std::make_pair(None, true);
94  }
95 
96  template <typename IterT>
97  void insert(IterT I, IterT E) {
98  for (; I != E; ++I)
99  insert(*I);
100  }
101 
102  bool erase(const T &V) {
103  if (!isSmall())
104  return Set.erase(V);
105  for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
106  if (*I == V) {
107  Vector.erase(I);
108  return true;
109  }
110  return false;
111  }
112 
113  void clear() {
114  Vector.clear();
115  Set.clear();
116  }
117 
118 private:
119  bool isSmall() const { return Set.empty(); }
120 
121  VIterator vfind(const T &V) const {
122  for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
123  if (*I == V)
124  return I;
125  return Vector.end();
126  }
127 };
128 
131 template <typename PointeeType, unsigned N>
132 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
133 
134 } // end namespace llvm
135 
136 #endif
Definition: Path.inc:31
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:32
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:75
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:59
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:834