/home/arjun/llvm-project/llvm/include/llvm/ADT/SetVector.h

Source (jump to first uncovered line)
//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements a set that has insertion order iteration
// characteristics. This is useful for keeping a set of things that need to be
// visited later but in a deterministic order (insertion order). The interface
// is purposefully minimal.
//
// This file defines SetVector and SmallSetVector, which performs no allocations
// if the SetVector has less than a certain number of elements.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_SETVECTOR_H
#define LLVM_ADT_SETVECTOR_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>

namespace llvm {

/// A vector that has set insertion semantics.
///
/// This adapter class provides a way to keep a set of things that also has the
/// property of a deterministic iteration order. The order of iteration is the
/// order of insertion.
template <typename T, typename Vector = std::vector<T>,
          typename Set = DenseSet<T>>
class SetVector {
public:
  using value_type = T;
  using key_type = T;
  using reference = T&;
  using const_reference = const T&;
  using set_type = Set;
  using vector_type = Vector;
  using iterator = typename vector_type::const_iterator;
  using const_iterator = typename vector_type::const_iterator;
  using reverse_iterator = typename vector_type::const_reverse_iterator;
  using const_reverse_iterator = typename vector_type::const_reverse_iterator;
  using size_type = typename vector_type::size_type;

  /// Construct an empty SetVector
  SetVector() = default;

  /// Initialize a SetVector with a range of elements
  template<typename It>
  SetVector(It Start, It End) {
    insert(Start, End);
  }

  ArrayRef<T> getArrayRef() const { return vector_; }

  /// Clear the SetVector and return the underlying vector.
  Vector takeVector() {
    set_.clear();
    return std::move(vector_);
  }

  /// Determine if the SetVector is empty or not.
  bool empty() const {
    return vector_.empty();
  }

  /// Determine the number of elements in the SetVector.
  size_type size() const {
    return vector_.size();
  }

  /// Get an iterator to the beginning of the SetVector.
  iterator begin() {
    return vector_.begin();
  }

  /// Get a const_iterator to the beginning of the SetVector.
  const_iterator begin() const {
    return vector_.begin();
  }

  /// Get an iterator to the end of the SetVector.
  iterator end() {
    return vector_.end();
  }

  /// Get a const_iterator to the end of the SetVector.
  const_iterator end() const {
    return vector_.end();
  }

  /// Get an reverse_iterator to the end of the SetVector.
  reverse_iterator rbegin() {
    return vector_.rbegin();
  }

  /// Get a const_reverse_iterator to the end of the SetVector.
  const_reverse_iterator rbegin() const {
    return vector_.rbegin();
  }

  /// Get a reverse_iterator to the beginning of the SetVector.
  reverse_iterator rend() {
    return vector_.rend();
  }

  /// Get a const_reverse_iterator to the beginning of the SetVector.
  const_reverse_iterator rend() const {
    return vector_.rend();
  }

  /// Return the first element of the SetVector.
  const T &front() const {
    assert(!empty() && "Cannot call front() on empty SetVector!");
    return vector_.front();
  }

  /// Return the last element of the SetVector.
  const T &back() const {
    assert(!empty() && "Cannot call back() on empty SetVector!");
    return vector_.back();
  }

  /// Index into the SetVector.
  const_reference operator[](size_type n) const {
    assert(n < vector_.size() && "SetVector access out of range!");
    return vector_[n];
  }

  /// Insert a new element into the SetVector.
  /// \returns true if the element was inserted into the SetVector.
  bool insert(const value_type &X) {
    bool result = set_.insert(X).second;
    if (result)
      vector_.push_back(X);
    return result;
  }

  /// Insert a range of elements into the SetVector.
  template<typename It>
  void insert(It Start, It End) {
    for (; Start != End; ++Start)
      if (set_.insert(*Start).second)
        vector_.push_back(*Start);
  }

  /// Remove an item from the set vector.
  bool remove(const value_type& X) {
    if (set_.erase(X)) {
      typename vector_type::iterator I = find(vector_, X);
      assert(I != vector_.end() && "Corrupted SetVector instances!");
      vector_.erase(I);
      return true;
    }
    return false;
  }

  /// Erase a single element from the set vector.
  /// \returns an iterator pointing to the next element that followed the
  /// element erased. This is the end of the SetVector if the last element is
  /// erased.
  iterator erase(iterator I) {
    const key_type &V = *I;
    assert(set_.count(V) && "Corrupted SetVector instances!");
    set_.erase(V);

    // FIXME: No need to use the non-const iterator when built with
    // std::vector.erase(const_iterator) as defined in C++11. This is for
    // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
    auto NI = vector_.begin();
    std::advance(NI, std::distance<iterator>(NI, I));

    return vector_.erase(NI);
  }

  /// Remove items from the set vector based on a predicate function.
  ///
  /// This is intended to be equivalent to the following code, if we could
  /// write it:
  ///
  /// \code
  ///   V.erase(remove_if(V, P), V.end());
  /// \endcode
  ///
  /// However, SetVector doesn't expose non-const iterators, making any
  /// algorithm like remove_if impossible to use.
  ///
  /// \returns true if any element is removed.
  template <typename UnaryPredicate>
  bool remove_if(UnaryPredicate P) {
    typename vector_type::iterator I =
        llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
    if (I == vector_.end())
      return false;
    vector_.erase(I, vector_.end());
    return true;
  }

  /// Count the number of elements of a given key in the SetVector.
  /// \returns 0 if the element is not in the SetVector, 1 if it is.
  size_type count(const key_type &key) const {
    return set_.count(key);
  }

  /// Completely clear the SetVector
  void clear() {
    set_.clear();
    vector_.clear();
  }

  /// Remove the last element of the SetVector.
  void pop_back() {
    assert(!empty() && "Cannot remove an element from an empty SetVector!");
    set_.erase(back());
    vector_.pop_back();
  }

  LLVM_NODISCARD T pop_back_val() {
    T Ret = back();
    pop_back();
    return Ret;
  }

  bool operator==(const SetVector &that) const {
    return vector_ == that.vector_;
  }

  bool operator!=(const SetVector &that) const {
    return vector_ != that.vector_;
  }

  /// Compute This := This u S, return whether 'This' changed.
  /// TODO: We should be able to use set_union from SetOperations.h, but
  ///       SetVector interface is inconsistent with DenseSet.
  template <class STy>
  bool set_union(const STy &S) {
    bool Changed = false;

    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
         ++SI)
      if (insert(*SI))
        Changed = true;

    return Changed;
  }

  /// Compute This := This - B
  /// TODO: We should be able to use set_subtract from SetOperations.h, but
  ///       SetVector interface is inconsistent with DenseSet.
  template <class STy>
  void set_subtract(const STy &S) {
    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
         ++SI)
      remove(*SI);
  }

private:
  /// A wrapper predicate designed for use with std::remove_if.
  ///
  /// This predicate wraps a predicate suitable for use with std::remove_if to
  /// call set_.erase(x) on each element which is slated for removal.
  template <typename UnaryPredicate>
  class TestAndEraseFromSet {
    UnaryPredicate P;
    set_type &set_;

  public:
    TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
        : P(std::move(P)), set_(set_) {}

    template <typename ArgumentT>
    bool operator()(const ArgumentT &Arg) {
      if (P(Arg)) {
        set_.erase(Arg);
        return true;
      }
      return false;
    }
  };

  set_type set_;         ///< The set.
  vector_type vector_;   ///< The vector.
};

/// A SetVector that performs no allocations if smaller than
/// a certain size.
template <typename T, unsigned N>
class SmallSetVector
    : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
public:
  SmallSetVector() = default;

  /// Initialize a SmallSetVector with a range of elements
  template<typename It>
  SmallSetVector(It Start, It End) {
    this->insert(Start, End);
  }
};

} // end namespace llvm

#endif // LLVM_ADT_SETVECTOR_H

Coverage Report

Created: 2020-06-26 05:44

Line	Count	Source (jump to first uncovered line)
1		//===- llvm/ADT/SetVector.h - Set with insert order iteration ---- C++ --===//
2		//
3		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4		// See https://llvm.org/LICENSE.txt for license information.
5		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6		//
7		//===----------------------------------------------------------------------===//
8		//
9		// This file implements a set that has insertion order iteration
10		// characteristics. This is useful for keeping a set of things that need to be
11		// visited later but in a deterministic order (insertion order). The interface
12		// is purposefully minimal.
13		//
14		// This file defines SetVector and SmallSetVector, which performs no allocations
15		// if the SetVector has less than a certain number of elements.
16		//
17		//===----------------------------------------------------------------------===//
18
19		#ifndef LLVM_ADT_SETVECTOR_H
20		#define LLVM_ADT_SETVECTOR_H
21
22		#include "llvm/ADT/ArrayRef.h"
23		#include "llvm/ADT/DenseSet.h"
24		#include "llvm/ADT/STLExtras.h"
25		#include "llvm/Support/Compiler.h"
26		#include <algorithm>
27		#include <cassert>
28		#include <iterator>
29		#include <vector>
30
31		namespace llvm {
32
33		/// A vector that has set insertion semantics.
34		///
35		/// This adapter class provides a way to keep a set of things that also has the
36		/// property of a deterministic iteration order. The order of iteration is the
37		/// order of insertion.
38		template <typename T, typename Vector = std::vector<T>,
39		typename Set = DenseSet<T>>
40		class SetVector {
41		public:
42		using value_type = T;
43		using key_type = T;
44		using reference = T&;
45		using const_reference = const T&;
46		using set_type = Set;
47		using vector_type = Vector;
48		using iterator = typename vector_type::const_iterator;
49		using const_iterator = typename vector_type::const_iterator;
50		using reverse_iterator = typename vector_type::const_reverse_iterator;
51		using const_reverse_iterator = typename vector_type::const_reverse_iterator;
52		using size_type = typename vector_type::size_type;
53
54		/// Construct an empty SetVector
55	0	SetVector() = default; Unexecuted instantiation: _ZN4llvm9SetVectorIjSt6vectorIjSaIjEENS_8DenseSetIjNS_12DenseMapInfoIjEEEEEC2Ev Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir9AttributeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEEC2Ev Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir4TypeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEEC2Ev Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir8LocationENS_11SmallVectorIS2_Lj4EEENS_13SmallDenseSetIS2_Lj4ENS_12DenseMapInfoIS2_EEEEEC2Ev Unexecuted instantiation: _ZN4llvm9SetVectorIPN4mlir9OperationENS_11SmallVectorIS3_Lj4EEENS_11SmallPtrSetIS3_Lj4EEEEC2Ev
56
57		/// Initialize a SetVector with a range of elements
58		template<typename It>
59		SetVector(It Start, It End) {
60		insert(Start, End);
61		}
62
63	0	ArrayRef<T> getArrayRef() const { return vector_; }
64
65		/// Clear the SetVector and return the underlying vector.
66		Vector takeVector() {
67		set_.clear();
68		return std::move(vector_);
69		}
70
71		/// Determine if the SetVector is empty or not.
72	0	bool empty() const {
73	0	return vector_.empty();
74	0	}
75
76		/// Determine the number of elements in the SetVector.
77		size_type size() const {
78		return vector_.size();
79		}
80
81		/// Get an iterator to the beginning of the SetVector.
82		iterator begin() {
83		return vector_.begin();
84		}
85
86		/// Get a const_iterator to the beginning of the SetVector.
87	0	const_iterator begin() const {
88	0	return vector_.begin();
89	0	} Unexecuted instantiation: _ZNK4llvm9SetVectorIN4mlir9AttributeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE5beginEv Unexecuted instantiation: _ZNK4llvm9SetVectorIN4mlir4TypeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE5beginEv
90
91		/// Get an iterator to the end of the SetVector.
92		iterator end() {
93		return vector_.end();
94		}
95
96		/// Get a const_iterator to the end of the SetVector.
97	0	const_iterator end() const {
98	0	return vector_.end();
99	0	} Unexecuted instantiation: _ZNK4llvm9SetVectorIN4mlir9AttributeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE3endEv Unexecuted instantiation: _ZNK4llvm9SetVectorIN4mlir4TypeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE3endEv
100
101		/// Get an reverse_iterator to the end of the SetVector.
102		reverse_iterator rbegin() {
103		return vector_.rbegin();
104		}
105
106		/// Get a const_reverse_iterator to the end of the SetVector.
107		const_reverse_iterator rbegin() const {
108		return vector_.rbegin();
109		}
110
111		/// Get a reverse_iterator to the beginning of the SetVector.
112		reverse_iterator rend() {
113		return vector_.rend();
114		}
115
116		/// Get a const_reverse_iterator to the beginning of the SetVector.
117		const_reverse_iterator rend() const {
118		return vector_.rend();
119		}
120
121		/// Return the first element of the SetVector.
122		const T &front() const {
123		assert(!empty() && "Cannot call front() on empty SetVector!");
124		return vector_.front();
125		}
126
127		/// Return the last element of the SetVector.
128		const T &back() const {
129		assert(!empty() && "Cannot call back() on empty SetVector!");
130		return vector_.back();
131		}
132
133		/// Index into the SetVector.
134		const_reference operator[](size_type n) const {
135		assert(n < vector_.size() && "SetVector access out of range!");
136		return vector_[n];
137		}
138
139		/// Insert a new element into the SetVector.
140		/// \returns true if the element was inserted into the SetVector.
141	0	bool insert(const value_type &X) {
142	0	bool result = set_.insert(X).second;
143	0	if (result)
144	0	vector_.push_back(X);
145	0	return result;
146	0	} Unexecuted instantiation: _ZN4llvm9SetVectorIjSt6vectorIjSaIjEENS_8DenseSetIjNS_12DenseMapInfoIjEEEEE6insertERKj Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir4TypeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE6insertERKS2_ Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir9AttributeESt6vectorIS2_SaIS2_EENS_8DenseSetIS2_NS_12DenseMapInfoIS2_EEEEE6insertERKS2_ Unexecuted instantiation: _ZN4llvm9SetVectorIN4mlir8LocationENS_11SmallVectorIS2_Lj4EEENS_13SmallDenseSetIS2_Lj4ENS_12DenseMapInfoIS2_EEEEE6insertERKS2_ Unexecuted instantiation: _ZN4llvm9SetVectorIPN4mlir9OperationENS_11SmallVectorIS3_Lj4EEENS_11SmallPtrSetIS3_Lj4EEEE6insertERKS3_
147
148		/// Insert a range of elements into the SetVector.
149		template<typename It>
150	0	void insert(It Start, It End) {
151	0	for (; Start != End; ++Start)
152	0	if (set_.insert(*Start).second)
153	0	vector_.push_back(*Start);
154	0	}
155
156		/// Remove an item from the set vector.
157		bool remove(const value_type& X) {
158		if (set_.erase(X)) {
159		typename vector_type::iterator I = find(vector_, X);
160		assert(I != vector_.end() && "Corrupted SetVector instances!");
161		vector_.erase(I);
162		return true;
163		}
164		return false;
165		}
166
167		/// Erase a single element from the set vector.
168		/// \returns an iterator pointing to the next element that followed the
169		/// element erased. This is the end of the SetVector if the last element is
170		/// erased.
171		iterator erase(iterator I) {
172		const key_type &V = *I;
173		assert(set_.count(V) && "Corrupted SetVector instances!");
174		set_.erase(V);
175
176		// FIXME: No need to use the non-const iterator when built with
177		// std::vector.erase(const_iterator) as defined in C++11. This is for
178		// compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
179		auto NI = vector_.begin();
180		std::advance(NI, std::distance<iterator>(NI, I));
181
182		return vector_.erase(NI);
183		}
184
185		/// Remove items from the set vector based on a predicate function.
186		///
187		/// This is intended to be equivalent to the following code, if we could
188		/// write it:
189		///
190		/// \code
191		/// V.erase(remove_if(V, P), V.end());
192		/// \endcode
193		///
194		/// However, SetVector doesn't expose non-const iterators, making any
195		/// algorithm like remove_if impossible to use.
196		///
197		/// \returns true if any element is removed.
198		template <typename UnaryPredicate>
199		bool remove_if(UnaryPredicate P) {
200		typename vector_type::iterator I =
201		llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
202		if (I == vector_.end())
203		return false;
204		vector_.erase(I, vector_.end());
205		return true;
206		}
207
208		/// Count the number of elements of a given key in the SetVector.
209		/// \returns 0 if the element is not in the SetVector, 1 if it is.
210	0	size_type count(const key_type &key) const {
211	0	return set_.count(key);
212	0	} Unexecuted instantiation: _ZNK4llvm9SetVectorIjSt6vectorIjSaIjEENS_8DenseSetIjNS_12DenseMapInfoIjEEEEE5countERKj Unexecuted instantiation: _ZNK4llvm9SetVectorIPN4mlir9OperationENS_11SmallVectorIS3_Lj4EEENS_11SmallPtrSetIS3_Lj4EEEE5countERKS3_
213
214		/// Completely clear the SetVector
215		void clear() {
216		set_.clear();
217		vector_.clear();
218		}
219
220		/// Remove the last element of the SetVector.
221		void pop_back() {
222		assert(!empty() && "Cannot remove an element from an empty SetVector!");
223		set_.erase(back());
224		vector_.pop_back();
225		}
226
227		LLVM_NODISCARD T pop_back_val() {
228		T Ret = back();
229		pop_back();
230		return Ret;
231		}
232
233		bool operator==(const SetVector &that) const {
234		return vector_ == that.vector_;
235		}
236
237		bool operator!=(const SetVector &that) const {
238		return vector_ != that.vector_;
239		}
240
241		/// Compute This := This u S, return whether 'This' changed.
242		/// TODO: We should be able to use set_union from SetOperations.h, but
243		/// SetVector interface is inconsistent with DenseSet.
244		template <class STy>
245		bool set_union(const STy &S) {
246		bool Changed = false;
247
248		for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
249		++SI)
250		if (insert(*SI))
251		Changed = true;
252
253		return Changed;
254		}
255
256		/// Compute This := This - B
257		/// TODO: We should be able to use set_subtract from SetOperations.h, but
258		/// SetVector interface is inconsistent with DenseSet.
259		template <class STy>
260		void set_subtract(const STy &S) {
261		for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
262		++SI)
263		remove(*SI);
264		}
265
266		private:
267		/// A wrapper predicate designed for use with std::remove_if.
268		///
269		/// This predicate wraps a predicate suitable for use with std::remove_if to
270		/// call set_.erase(x) on each element which is slated for removal.
271		template <typename UnaryPredicate>
272		class TestAndEraseFromSet {
273		UnaryPredicate P;
274		set_type &set_;
275
276		public:
277		TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
278		: P(std::move(P)), set_(set_) {}
279
280		template <typename ArgumentT>
281		bool operator()(const ArgumentT &Arg) {
282		if (P(Arg)) {
283		set_.erase(Arg);
284		return true;
285		}
286		return false;
287		}
288		};
289
290		set_type set_; ///< The set.
291		vector_type vector_; ///< The vector.
292		};
293
294		/// A SetVector that performs no allocations if smaller than
295		/// a certain size.
296		template <typename T, unsigned N>
297		class SmallSetVector
298		: public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
299		public:
300	0	SmallSetVector() = default;
301
302		/// Initialize a SmallSetVector with a range of elements
303		template<typename It>
304		SmallSetVector(It Start, It End) {
305		this->insert(Start, End);
306		}
307		};
308
309		} // end namespace llvm
310
311		#endif // LLVM_ADT_SETVECTOR_H