LLVM 20.0.0git
SetOperations.h
Go to the documentation of this file.
1//===-- llvm/ADT/SetOperations.h - Generic Set Operations -------*- 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/// \file
10/// This file defines generic set operations that may be used on set's of
11/// different types, and different element types.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_SETOPERATIONS_H
16#define LLVM_ADT_SETOPERATIONS_H
17
18#include "llvm/ADT/STLExtras.h"
19
20namespace llvm {
21
22namespace detail {
23template <typename Set, typename Fn>
25 decltype(std::declval<Set>().remove_if(std::declval<Fn>()));
26
27template <typename Set, typename Fn>
28static constexpr bool HasMemberRemoveIf =
30
31template <typename Set>
33 decltype(std::declval<Set>().erase(std::declval<Set>().begin()));
34
35template <typename Set>
36static constexpr bool HasMemberEraseIter =
38
39} // namespace detail
40
41/// set_union(A, B) - Compute A := A u B, return whether A changed.
42///
43template <class S1Ty, class S2Ty> bool set_union(S1Ty &S1, const S2Ty &S2) {
44 bool Changed = false;
45
46 for (const auto &E : S2)
47 if (S1.insert(E).second)
48 Changed = true;
49
50 return Changed;
51}
52
53/// set_intersect(A, B) - Compute A := A ^ B
54/// Identical to set_intersection, except that it works on set<>'s and
55/// is nicer to use. Functionally, this iterates through S1, removing
56/// elements that are not contained in S2.
57///
58template <class S1Ty, class S2Ty> void set_intersect(S1Ty &S1, const S2Ty &S2) {
59 auto Pred = [&S2](const auto &E) { return !S2.count(E); };
60 if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) {
61 S1.remove_if(Pred);
62 } else {
63 typename S1Ty::iterator Next;
64 for (typename S1Ty::iterator I = S1.begin(); I != S1.end(); I = Next) {
65 Next = std::next(I);
66 if (!S2.count(*I))
67 S1.erase(I); // Erase element if not in S2
68 }
69 }
70}
71
72template <class S1Ty, class S2Ty>
73S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2) {
74 S1Ty Result;
75 for (const auto &E : S1)
76 if (S2.count(E))
77 Result.insert(E);
78 return Result;
79}
80
81/// set_intersection(A, B) - Return A ^ B
82template <class S1Ty, class S2Ty>
83S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2) {
84 if (S1.size() < S2.size())
85 return set_intersection_impl(S1, S2);
86 else
87 return set_intersection_impl(S2, S1);
88}
89
90/// set_difference(A, B) - Return A - B
91///
92template <class S1Ty, class S2Ty>
93S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) {
94 S1Ty Result;
95 for (const auto &E : S1)
96 if (!S2.count(E)) // if the element is not in set2
97 Result.insert(E);
98 return Result;
99}
100
101/// set_subtract(A, B) - Compute A := A - B
102///
103/// Selects the set to iterate based on the relative sizes of A and B for better
104/// efficiency.
105///
106template <class S1Ty, class S2Ty> void set_subtract(S1Ty &S1, const S2Ty &S2) {
107 // If S1 is smaller than S2, iterate on S1 provided that S2 supports efficient
108 // lookups via contains(). Note that a couple callers pass a vector for S2,
109 // which doesn't support contains(), and wouldn't be efficient if it did.
110 using ElemTy = decltype(*S1.begin());
111 if constexpr (detail::HasMemberContains<S2Ty, ElemTy>) {
112 auto Pred = [&S2](const auto &E) { return S2.contains(E); };
113 if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) {
114 if (S1.size() < S2.size()) {
115 S1.remove_if(Pred);
116 return;
117 }
118 } else if constexpr (detail::HasMemberEraseIter<S1Ty>) {
119 if (S1.size() < S2.size()) {
120 typename S1Ty::iterator Next;
121 for (typename S1Ty::iterator SI = S1.begin(), SE = S1.end(); SI != SE;
122 SI = Next) {
123 Next = std::next(SI);
124 if (S2.contains(*SI))
125 S1.erase(SI);
126 }
127 return;
128 }
129 }
130 }
131
132 for (const auto &E : S2)
133 S1.erase(E);
134}
135
136/// set_subtract(A, B, C, D) - Compute A := A - B, set C to the elements of B
137/// removed from A (A ^ B), and D to the elements of B not found in and removed
138/// from A (B - A).
139template <class S1Ty, class S2Ty>
140void set_subtract(S1Ty &S1, const S2Ty &S2, S1Ty &Removed, S1Ty &Remaining) {
141 for (const auto &E : S2)
142 if (S1.erase(E))
143 Removed.insert(E);
144 else
145 Remaining.insert(E);
146}
147
148/// set_is_subset(A, B) - Return true iff A in B
149///
150template <class S1Ty, class S2Ty>
151bool set_is_subset(const S1Ty &S1, const S2Ty &S2) {
152 if (S1.size() > S2.size())
153 return false;
154 for (const auto It : S1)
155 if (!S2.count(It))
156 return false;
157 return true;
158}
159
160} // namespace llvm
161
162#endif
static const LLT S1
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains some templates that are useful if you are working with the STL at all.
decltype(std::declval< Set >().remove_if(std::declval< Fn >())) check_has_member_remove_if_t
Definition: SetOperations.h:25
decltype(std::declval< Set >().erase(std::declval< Set >().begin())) check_has_member_erase_iter_t
Definition: SetOperations.h:33
static constexpr bool HasMemberRemoveIf
Definition: SetOperations.h:28
static constexpr bool HasMemberEraseIter
Definition: SetOperations.h:36
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
Definition: SetOperations.h:58
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void set_subtract(S1Ty &S1, const S2Ty &S2)
set_subtract(A, B) - Compute A := A - B
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
Definition: STLExtras.h:79
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
Definition: SetOperations.h:43
S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2)
set_intersection(A, B) - Return A ^ B
Definition: SetOperations.h:83
S1Ty set_difference(const S1Ty &S1, const S2Ty &S2)
set_difference(A, B) - Return A - B
Definition: SetOperations.h:93
S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2)
Definition: SetOperations.h:73