/usr/include/llvm-6.0/llvm/ADT/SmallSet.h is in llvm-6.0-dev 1:6.0-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the SmallSet class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_SMALLSET_H
#define LLVM_ADT_SMALLSET_H
#include "llvm/ADT/None.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include <cstddef>
#include <functional>
#include <set>
#include <utility>
namespace llvm {
/// SmallSet - This maintains a set of unique values, optimizing for the case
/// when the set is small (less than N). In this case, the set can be
/// maintained with no mallocs. If the set gets large, we expand to using an
/// std::set to maintain reasonable lookup times.
///
/// Note that this set does not provide a way to iterate over members in the
/// set.
template <typename T, unsigned N, typename C = std::less<T>>
class SmallSet {
/// Use a SmallVector to hold the elements here (even though it will never
/// reach its 'large' stage) to avoid calling the default ctors of elements
/// we will never use.
SmallVector<T, N> Vector;
std::set<T, C> Set;
using VIterator = typename SmallVector<T, N>::const_iterator;
using mutable_iterator = typename SmallVector<T, N>::iterator;
// In small mode SmallPtrSet uses linear search for the elements, so it is
// not a good idea to choose this value too high. You may consider using a
// DenseSet<> instead if you expect many elements in the set.
static_assert(N <= 32, "N should be small");
public:
using size_type = size_t;
SmallSet() = default;
LLVM_NODISCARD bool empty() const {
return Vector.empty() && Set.empty();
}
size_type size() const {
return isSmall() ? Vector.size() : Set.size();
}
/// count - Return 1 if the element is in the set, 0 otherwise.
size_type count(const T &V) const {
if (isSmall()) {
// Since the collection is small, just do a linear search.
return vfind(V) == Vector.end() ? 0 : 1;
} else {
return Set.count(V);
}
}
/// insert - Insert an element into the set if it isn't already there.
/// Returns true if the element is inserted (it was not in the set before).
/// The first value of the returned pair is unused and provided for
/// partial compatibility with the standard library self-associative container
/// concept.
// FIXME: Add iterators that abstract over the small and large form, and then
// return those here.
std::pair<NoneType, bool> insert(const T &V) {
if (!isSmall())
return std::make_pair(None, Set.insert(V).second);
VIterator I = vfind(V);
if (I != Vector.end()) // Don't reinsert if it already exists.
return std::make_pair(None, false);
if (Vector.size() < N) {
Vector.push_back(V);
return std::make_pair(None, true);
}
// Otherwise, grow from vector to set.
while (!Vector.empty()) {
Set.insert(Vector.back());
Vector.pop_back();
}
Set.insert(V);
return std::make_pair(None, true);
}
template <typename IterT>
void insert(IterT I, IterT E) {
for (; I != E; ++I)
insert(*I);
}
bool erase(const T &V) {
if (!isSmall())
return Set.erase(V);
for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
if (*I == V) {
Vector.erase(I);
return true;
}
return false;
}
void clear() {
Vector.clear();
Set.clear();
}
private:
bool isSmall() const { return Set.empty(); }
VIterator vfind(const T &V) const {
for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
if (*I == V)
return I;
return Vector.end();
}
};
/// If this set is of pointer values, transparently switch over to using
/// SmallPtrSet for performance.
template <typename PointeeType, unsigned N>
class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
} // end namespace llvm
#endif // LLVM_ADT_SMALLSET_H
|