Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp
Warning:line 306, column 26
Called C++ object pointer is uninitialized

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name AArch64MCTargetDesc.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Target/AArch64/MCTargetDesc -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64 -I lib/Target/AArch64 -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/.. -I lib/Target/AArch64/MCTargetDesc/.. -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -ferror-limit 19 -fvisibility=hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp

1//===-- AArch64MCTargetDesc.cpp - AArch64 Target Descriptions ---*- 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 provides AArch64 specific target descriptions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "AArch64MCTargetDesc.h"
14#include "AArch64ELFStreamer.h"
15#include "AArch64MCAsmInfo.h"
16#include "AArch64WinCOFFStreamer.h"
17#include "MCTargetDesc/AArch64AddressingModes.h"
18#include "MCTargetDesc/AArch64InstPrinter.h"
19#include "TargetInfo/AArch64TargetInfo.h"
20#include "llvm/DebugInfo/CodeView/CodeView.h"
21#include "llvm/MC/MCAsmBackend.h"
22#include "llvm/MC/MCCodeEmitter.h"
23#include "llvm/MC/MCInstrAnalysis.h"
24#include "llvm/MC/MCInstrInfo.h"
25#include "llvm/MC/MCObjectWriter.h"
26#include "llvm/MC/MCRegisterInfo.h"
27#include "llvm/MC/MCStreamer.h"
28#include "llvm/MC/MCSubtargetInfo.h"
29#include "llvm/MC/TargetRegistry.h"
30#include "llvm/Support/Endian.h"
31#include "llvm/Support/ErrorHandling.h"
32
33using namespace llvm;
34
35#define GET_INSTRINFO_MC_DESC
36#define GET_INSTRINFO_MC_HELPERS
37#define ENABLE_INSTR_PREDICATE_VERIFIER
38#include "AArch64GenInstrInfo.inc"
39
40#define GET_SUBTARGETINFO_MC_DESC
41#include "AArch64GenSubtargetInfo.inc"
42
43#define GET_REGINFO_MC_DESC
44#include "AArch64GenRegisterInfo.inc"
45
46static MCInstrInfo *createAArch64MCInstrInfo() {
47 MCInstrInfo *X = new MCInstrInfo();
48 InitAArch64MCInstrInfo(X);
49 return X;
50}
51
52static MCSubtargetInfo *
53createAArch64MCSubtargetInfo(const Triple &TT, StringRef CPU, StringRef FS) {
54 if (CPU.empty()) {
55 CPU = "generic";
56 if (FS.empty())
57 FS = "+v8a";
58
59 if (TT.isArm64e())
60 CPU = "apple-a12";
61 }
62
63 return createAArch64MCSubtargetInfoImpl(TT, CPU, /*TuneCPU*/ CPU, FS);
64}
65
66void AArch64_MC::initLLVMToCVRegMapping(MCRegisterInfo *MRI) {
67 // Mapping from CodeView to MC register id.
68 static const struct {
69 codeview::RegisterId CVReg;
70 MCPhysReg Reg;
71 } RegMap[] = {
72 {codeview::RegisterId::ARM64_W0, AArch64::W0},
73 {codeview::RegisterId::ARM64_W1, AArch64::W1},
74 {codeview::RegisterId::ARM64_W2, AArch64::W2},
75 {codeview::RegisterId::ARM64_W3, AArch64::W3},
76 {codeview::RegisterId::ARM64_W4, AArch64::W4},
77 {codeview::RegisterId::ARM64_W5, AArch64::W5},
78 {codeview::RegisterId::ARM64_W6, AArch64::W6},
79 {codeview::RegisterId::ARM64_W7, AArch64::W7},
80 {codeview::RegisterId::ARM64_W8, AArch64::W8},
81 {codeview::RegisterId::ARM64_W9, AArch64::W9},
82 {codeview::RegisterId::ARM64_W10, AArch64::W10},
83 {codeview::RegisterId::ARM64_W11, AArch64::W11},
84 {codeview::RegisterId::ARM64_W12, AArch64::W12},
85 {codeview::RegisterId::ARM64_W13, AArch64::W13},
86 {codeview::RegisterId::ARM64_W14, AArch64::W14},
87 {codeview::RegisterId::ARM64_W15, AArch64::W15},
88 {codeview::RegisterId::ARM64_W16, AArch64::W16},
89 {codeview::RegisterId::ARM64_W17, AArch64::W17},
90 {codeview::RegisterId::ARM64_W18, AArch64::W18},
91 {codeview::RegisterId::ARM64_W19, AArch64::W19},
92 {codeview::RegisterId::ARM64_W20, AArch64::W20},
93 {codeview::RegisterId::ARM64_W21, AArch64::W21},
94 {codeview::RegisterId::ARM64_W22, AArch64::W22},
95 {codeview::RegisterId::ARM64_W23, AArch64::W23},
96 {codeview::RegisterId::ARM64_W24, AArch64::W24},
97 {codeview::RegisterId::ARM64_W25, AArch64::W25},
98 {codeview::RegisterId::ARM64_W26, AArch64::W26},
99 {codeview::RegisterId::ARM64_W27, AArch64::W27},
100 {codeview::RegisterId::ARM64_W28, AArch64::W28},
101 {codeview::RegisterId::ARM64_W29, AArch64::W29},
102 {codeview::RegisterId::ARM64_W30, AArch64::W30},
103 {codeview::RegisterId::ARM64_WZR, AArch64::WZR},
104 {codeview::RegisterId::ARM64_X0, AArch64::X0},
105 {codeview::RegisterId::ARM64_X1, AArch64::X1},
106 {codeview::RegisterId::ARM64_X2, AArch64::X2},
107 {codeview::RegisterId::ARM64_X3, AArch64::X3},
108 {codeview::RegisterId::ARM64_X4, AArch64::X4},
109 {codeview::RegisterId::ARM64_X5, AArch64::X5},
110 {codeview::RegisterId::ARM64_X6, AArch64::X6},
111 {codeview::RegisterId::ARM64_X7, AArch64::X7},
112 {codeview::RegisterId::ARM64_X8, AArch64::X8},
113 {codeview::RegisterId::ARM64_X9, AArch64::X9},
114 {codeview::RegisterId::ARM64_X10, AArch64::X10},
115 {codeview::RegisterId::ARM64_X11, AArch64::X11},
116 {codeview::RegisterId::ARM64_X12, AArch64::X12},
117 {codeview::RegisterId::ARM64_X13, AArch64::X13},
118 {codeview::RegisterId::ARM64_X14, AArch64::X14},
119 {codeview::RegisterId::ARM64_X15, AArch64::X15},
120 {codeview::RegisterId::ARM64_X16, AArch64::X16},
121 {codeview::RegisterId::ARM64_X17, AArch64::X17},
122 {codeview::RegisterId::ARM64_X18, AArch64::X18},
123 {codeview::RegisterId::ARM64_X19, AArch64::X19},
124 {codeview::RegisterId::ARM64_X20, AArch64::X20},
125 {codeview::RegisterId::ARM64_X21, AArch64::X21},
126 {codeview::RegisterId::ARM64_X22, AArch64::X22},
127 {codeview::RegisterId::ARM64_X23, AArch64::X23},
128 {codeview::RegisterId::ARM64_X24, AArch64::X24},
129 {codeview::RegisterId::ARM64_X25, AArch64::X25},
130 {codeview::RegisterId::ARM64_X26, AArch64::X26},
131 {codeview::RegisterId::ARM64_X27, AArch64::X27},
132 {codeview::RegisterId::ARM64_X28, AArch64::X28},
133 {codeview::RegisterId::ARM64_FP, AArch64::FP},
134 {codeview::RegisterId::ARM64_LR, AArch64::LR},
135 {codeview::RegisterId::ARM64_SP, AArch64::SP},
136 {codeview::RegisterId::ARM64_ZR, AArch64::XZR},
137 {codeview::RegisterId::ARM64_NZCV, AArch64::NZCV},
138 {codeview::RegisterId::ARM64_S0, AArch64::S0},
139 {codeview::RegisterId::ARM64_S1, AArch64::S1},
140 {codeview::RegisterId::ARM64_S2, AArch64::S2},
141 {codeview::RegisterId::ARM64_S3, AArch64::S3},
142 {codeview::RegisterId::ARM64_S4, AArch64::S4},
143 {codeview::RegisterId::ARM64_S5, AArch64::S5},
144 {codeview::RegisterId::ARM64_S6, AArch64::S6},
145 {codeview::RegisterId::ARM64_S7, AArch64::S7},
146 {codeview::RegisterId::ARM64_S8, AArch64::S8},
147 {codeview::RegisterId::ARM64_S9, AArch64::S9},
148 {codeview::RegisterId::ARM64_S10, AArch64::S10},
149 {codeview::RegisterId::ARM64_S11, AArch64::S11},
150 {codeview::RegisterId::ARM64_S12, AArch64::S12},
151 {codeview::RegisterId::ARM64_S13, AArch64::S13},
152 {codeview::RegisterId::ARM64_S14, AArch64::S14},
153 {codeview::RegisterId::ARM64_S15, AArch64::S15},
154 {codeview::RegisterId::ARM64_S16, AArch64::S16},
155 {codeview::RegisterId::ARM64_S17, AArch64::S17},
156 {codeview::RegisterId::ARM64_S18, AArch64::S18},
157 {codeview::RegisterId::ARM64_S19, AArch64::S19},
158 {codeview::RegisterId::ARM64_S20, AArch64::S20},
159 {codeview::RegisterId::ARM64_S21, AArch64::S21},
160 {codeview::RegisterId::ARM64_S22, AArch64::S22},
161 {codeview::RegisterId::ARM64_S23, AArch64::S23},
162 {codeview::RegisterId::ARM64_S24, AArch64::S24},
163 {codeview::RegisterId::ARM64_S25, AArch64::S25},
164 {codeview::RegisterId::ARM64_S26, AArch64::S26},
165 {codeview::RegisterId::ARM64_S27, AArch64::S27},
166 {codeview::RegisterId::ARM64_S28, AArch64::S28},
167 {codeview::RegisterId::ARM64_S29, AArch64::S29},
168 {codeview::RegisterId::ARM64_S30, AArch64::S30},
169 {codeview::RegisterId::ARM64_S31, AArch64::S31},
170 {codeview::RegisterId::ARM64_D0, AArch64::D0},
171 {codeview::RegisterId::ARM64_D1, AArch64::D1},
172 {codeview::RegisterId::ARM64_D2, AArch64::D2},
173 {codeview::RegisterId::ARM64_D3, AArch64::D3},
174 {codeview::RegisterId::ARM64_D4, AArch64::D4},
175 {codeview::RegisterId::ARM64_D5, AArch64::D5},
176 {codeview::RegisterId::ARM64_D6, AArch64::D6},
177 {codeview::RegisterId::ARM64_D7, AArch64::D7},
178 {codeview::RegisterId::ARM64_D8, AArch64::D8},
179 {codeview::RegisterId::ARM64_D9, AArch64::D9},
180 {codeview::RegisterId::ARM64_D10, AArch64::D10},
181 {codeview::RegisterId::ARM64_D11, AArch64::D11},
182 {codeview::RegisterId::ARM64_D12, AArch64::D12},
183 {codeview::RegisterId::ARM64_D13, AArch64::D13},
184 {codeview::RegisterId::ARM64_D14, AArch64::D14},
185 {codeview::RegisterId::ARM64_D15, AArch64::D15},
186 {codeview::RegisterId::ARM64_D16, AArch64::D16},
187 {codeview::RegisterId::ARM64_D17, AArch64::D17},
188 {codeview::RegisterId::ARM64_D18, AArch64::D18},
189 {codeview::RegisterId::ARM64_D19, AArch64::D19},
190 {codeview::RegisterId::ARM64_D20, AArch64::D20},
191 {codeview::RegisterId::ARM64_D21, AArch64::D21},
192 {codeview::RegisterId::ARM64_D22, AArch64::D22},
193 {codeview::RegisterId::ARM64_D23, AArch64::D23},
194 {codeview::RegisterId::ARM64_D24, AArch64::D24},
195 {codeview::RegisterId::ARM64_D25, AArch64::D25},
196 {codeview::RegisterId::ARM64_D26, AArch64::D26},
197 {codeview::RegisterId::ARM64_D27, AArch64::D27},
198 {codeview::RegisterId::ARM64_D28, AArch64::D28},
199 {codeview::RegisterId::ARM64_D29, AArch64::D29},
200 {codeview::RegisterId::ARM64_D30, AArch64::D30},
201 {codeview::RegisterId::ARM64_D31, AArch64::D31},
202 {codeview::RegisterId::ARM64_Q0, AArch64::Q0},
203 {codeview::RegisterId::ARM64_Q1, AArch64::Q1},
204 {codeview::RegisterId::ARM64_Q2, AArch64::Q2},
205 {codeview::RegisterId::ARM64_Q3, AArch64::Q3},
206 {codeview::RegisterId::ARM64_Q4, AArch64::Q4},
207 {codeview::RegisterId::ARM64_Q5, AArch64::Q5},
208 {codeview::RegisterId::ARM64_Q6, AArch64::Q6},
209 {codeview::RegisterId::ARM64_Q7, AArch64::Q7},
210 {codeview::RegisterId::ARM64_Q8, AArch64::Q8},
211 {codeview::RegisterId::ARM64_Q9, AArch64::Q9},
212 {codeview::RegisterId::ARM64_Q10, AArch64::Q10},
213 {codeview::RegisterId::ARM64_Q11, AArch64::Q11},
214 {codeview::RegisterId::ARM64_Q12, AArch64::Q12},
215 {codeview::RegisterId::ARM64_Q13, AArch64::Q13},
216 {codeview::RegisterId::ARM64_Q14, AArch64::Q14},
217 {codeview::RegisterId::ARM64_Q15, AArch64::Q15},
218 {codeview::RegisterId::ARM64_Q16, AArch64::Q16},
219 {codeview::RegisterId::ARM64_Q17, AArch64::Q17},
220 {codeview::RegisterId::ARM64_Q18, AArch64::Q18},
221 {codeview::RegisterId::ARM64_Q19, AArch64::Q19},
222 {codeview::RegisterId::ARM64_Q20, AArch64::Q20},
223 {codeview::RegisterId::ARM64_Q21, AArch64::Q21},
224 {codeview::RegisterId::ARM64_Q22, AArch64::Q22},
225 {codeview::RegisterId::ARM64_Q23, AArch64::Q23},
226 {codeview::RegisterId::ARM64_Q24, AArch64::Q24},
227 {codeview::RegisterId::ARM64_Q25, AArch64::Q25},
228 {codeview::RegisterId::ARM64_Q26, AArch64::Q26},
229 {codeview::RegisterId::ARM64_Q27, AArch64::Q27},
230 {codeview::RegisterId::ARM64_Q28, AArch64::Q28},
231 {codeview::RegisterId::ARM64_Q29, AArch64::Q29},
232 {codeview::RegisterId::ARM64_Q30, AArch64::Q30},
233 {codeview::RegisterId::ARM64_Q31, AArch64::Q31},
234 {codeview::RegisterId::ARM64_B0, AArch64::B0},
235 {codeview::RegisterId::ARM64_B1, AArch64::B1},
236 {codeview::RegisterId::ARM64_B2, AArch64::B2},
237 {codeview::RegisterId::ARM64_B3, AArch64::B3},
238 {codeview::RegisterId::ARM64_B4, AArch64::B4},
239 {codeview::RegisterId::ARM64_B5, AArch64::B5},
240 {codeview::RegisterId::ARM64_B6, AArch64::B6},
241 {codeview::RegisterId::ARM64_B7, AArch64::B7},
242 {codeview::RegisterId::ARM64_B8, AArch64::B8},
243 {codeview::RegisterId::ARM64_B9, AArch64::B9},
244 {codeview::RegisterId::ARM64_B10, AArch64::B10},
245 {codeview::RegisterId::ARM64_B11, AArch64::B11},
246 {codeview::RegisterId::ARM64_B12, AArch64::B12},
247 {codeview::RegisterId::ARM64_B13, AArch64::B13},
248 {codeview::RegisterId::ARM64_B14, AArch64::B14},
249 {codeview::RegisterId::ARM64_B15, AArch64::B15},
250 {codeview::RegisterId::ARM64_B16, AArch64::B16},
251 {codeview::RegisterId::ARM64_B17, AArch64::B17},
252 {codeview::RegisterId::ARM64_B18, AArch64::B18},
253 {codeview::RegisterId::ARM64_B19, AArch64::B19},
254 {codeview::RegisterId::ARM64_B20, AArch64::B20},
255 {codeview::RegisterId::ARM64_B21, AArch64::B21},
256 {codeview::RegisterId::ARM64_B22, AArch64::B22},
257 {codeview::RegisterId::ARM64_B23, AArch64::B23},
258 {codeview::RegisterId::ARM64_B24, AArch64::B24},
259 {codeview::RegisterId::ARM64_B25, AArch64::B25},
260 {codeview::RegisterId::ARM64_B26, AArch64::B26},
261 {codeview::RegisterId::ARM64_B27, AArch64::B27},
262 {codeview::RegisterId::ARM64_B28, AArch64::B28},
263 {codeview::RegisterId::ARM64_B29, AArch64::B29},
264 {codeview::RegisterId::ARM64_B30, AArch64::B30},
265 {codeview::RegisterId::ARM64_B31, AArch64::B31},
266 {codeview::RegisterId::ARM64_H0, AArch64::H0},
267 {codeview::RegisterId::ARM64_H1, AArch64::H1},
268 {codeview::RegisterId::ARM64_H2, AArch64::H2},
269 {codeview::RegisterId::ARM64_H3, AArch64::H3},
270 {codeview::RegisterId::ARM64_H4, AArch64::H4},
271 {codeview::RegisterId::ARM64_H5, AArch64::H5},
272 {codeview::RegisterId::ARM64_H6, AArch64::H6},
273 {codeview::RegisterId::ARM64_H7, AArch64::H7},
274 {codeview::RegisterId::ARM64_H8, AArch64::H8},
275 {codeview::RegisterId::ARM64_H9, AArch64::H9},
276 {codeview::RegisterId::ARM64_H10, AArch64::H10},
277 {codeview::RegisterId::ARM64_H11, AArch64::H11},
278 {codeview::RegisterId::ARM64_H12, AArch64::H12},
279 {codeview::RegisterId::ARM64_H13, AArch64::H13},
280 {codeview::RegisterId::ARM64_H14, AArch64::H14},
281 {codeview::RegisterId::ARM64_H15, AArch64::H15},
282 {codeview::RegisterId::ARM64_H16, AArch64::H16},
283 {codeview::RegisterId::ARM64_H17, AArch64::H17},
284 {codeview::RegisterId::ARM64_H18, AArch64::H18},
285 {codeview::RegisterId::ARM64_H19, AArch64::H19},
286 {codeview::RegisterId::ARM64_H20, AArch64::H20},
287 {codeview::RegisterId::ARM64_H21, AArch64::H21},
288 {codeview::RegisterId::ARM64_H22, AArch64::H22},
289 {codeview::RegisterId::ARM64_H23, AArch64::H23},
290 {codeview::RegisterId::ARM64_H24, AArch64::H24},
291 {codeview::RegisterId::ARM64_H25, AArch64::H25},
292 {codeview::RegisterId::ARM64_H26, AArch64::H26},
293 {codeview::RegisterId::ARM64_H27, AArch64::H27},
294 {codeview::RegisterId::ARM64_H28, AArch64::H28},
295 {codeview::RegisterId::ARM64_H29, AArch64::H29},
296 {codeview::RegisterId::ARM64_H30, AArch64::H30},
297 {codeview::RegisterId::ARM64_H31, AArch64::H31},
298 };
299 for (const auto &I : RegMap)
300 MRI->mapLLVMRegToCVReg(I.Reg, static_cast<int>(I.CVReg));
301}
302
303bool AArch64_MC::isQForm(const MCInst &MI, const MCInstrInfo *MCII) {
304 const auto &FPR128 = AArch64MCRegisterClasses[AArch64::FPR128RegClassID];
305 return llvm::any_of(MI, [&](const MCOperand &Op) {
1
Uninitialized value stored to 'FPR128'
2
Calling 'any_of<const llvm::MCInst &, (lambda at /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp:305:27)>'
306 return Op.isReg() && FPR128.contains(Op.getReg());
12
Called C++ object pointer is uninitialized
307 });
308}
309
310bool AArch64_MC::isFpOrNEON(const MCInst &MI, const MCInstrInfo *MCII) {
311 const auto &FPR128 = AArch64MCRegisterClasses[AArch64::FPR128RegClassID];
312 const auto &FPR64 = AArch64MCRegisterClasses[AArch64::FPR64RegClassID];
313 const auto &FPR32 = AArch64MCRegisterClasses[AArch64::FPR32RegClassID];
314 const auto &FPR16 = AArch64MCRegisterClasses[AArch64::FPR16RegClassID];
315 const auto &FPR8 = AArch64MCRegisterClasses[AArch64::FPR8RegClassID];
316
317 auto IsFPR = [&](const MCOperand &Op) {
318 if (!Op.isReg())
319 return false;
320 auto Reg = Op.getReg();
321 return FPR128.contains(Reg) || FPR64.contains(Reg) || FPR32.contains(Reg) ||
322 FPR16.contains(Reg) || FPR8.contains(Reg);
323 };
324
325 return llvm::any_of(MI, IsFPR);
326}
327
328static MCRegisterInfo *createAArch64MCRegisterInfo(const Triple &Triple) {
329 MCRegisterInfo *X = new MCRegisterInfo();
330 InitAArch64MCRegisterInfo(X, AArch64::LR);
331 AArch64_MC::initLLVMToCVRegMapping(X);
332 return X;
333}
334
335static MCAsmInfo *createAArch64MCAsmInfo(const MCRegisterInfo &MRI,
336 const Triple &TheTriple,
337 const MCTargetOptions &Options) {
338 MCAsmInfo *MAI;
339 if (TheTriple.isOSBinFormatMachO())
340 MAI = new AArch64MCAsmInfoDarwin(TheTriple.getArch() == Triple::aarch64_32);
341 else if (TheTriple.isWindowsMSVCEnvironment())
342 MAI = new AArch64MCAsmInfoMicrosoftCOFF();
343 else if (TheTriple.isOSBinFormatCOFF())
344 MAI = new AArch64MCAsmInfoGNUCOFF();
345 else {
346 assert(TheTriple.isOSBinFormatELF() && "Invalid target")(static_cast <bool> (TheTriple.isOSBinFormatELF() &&
"Invalid target") ? void (0) : __assert_fail ("TheTriple.isOSBinFormatELF() && \"Invalid target\""
, "llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp"
, 346, __extension__ __PRETTY_FUNCTION__))
;
347 MAI = new AArch64MCAsmInfoELF(TheTriple);
348 }
349
350 // Initial state of the frame pointer is SP.
351 unsigned Reg = MRI.getDwarfRegNum(AArch64::SP, true);
352 MCCFIInstruction Inst = MCCFIInstruction::cfiDefCfa(nullptr, Reg, 0);
353 MAI->addInitialFrameState(Inst);
354
355 return MAI;
356}
357
358static MCInstPrinter *createAArch64MCInstPrinter(const Triple &T,
359 unsigned SyntaxVariant,
360 const MCAsmInfo &MAI,
361 const MCInstrInfo &MII,
362 const MCRegisterInfo &MRI) {
363 if (SyntaxVariant == 0)
364 return new AArch64InstPrinter(MAI, MII, MRI);
365 if (SyntaxVariant == 1)
366 return new AArch64AppleInstPrinter(MAI, MII, MRI);
367
368 return nullptr;
369}
370
371static MCStreamer *createELFStreamer(const Triple &T, MCContext &Ctx,
372 std::unique_ptr<MCAsmBackend> &&TAB,
373 std::unique_ptr<MCObjectWriter> &&OW,
374 std::unique_ptr<MCCodeEmitter> &&Emitter,
375 bool RelaxAll) {
376 return createAArch64ELFStreamer(Ctx, std::move(TAB), std::move(OW),
377 std::move(Emitter), RelaxAll);
378}
379
380static MCStreamer *createMachOStreamer(MCContext &Ctx,
381 std::unique_ptr<MCAsmBackend> &&TAB,
382 std::unique_ptr<MCObjectWriter> &&OW,
383 std::unique_ptr<MCCodeEmitter> &&Emitter,
384 bool RelaxAll,
385 bool DWARFMustBeAtTheEnd) {
386 return createMachOStreamer(Ctx, std::move(TAB), std::move(OW),
387 std::move(Emitter), RelaxAll, DWARFMustBeAtTheEnd,
388 /*LabelSections*/ true);
389}
390
391static MCStreamer *
392createWinCOFFStreamer(MCContext &Ctx, std::unique_ptr<MCAsmBackend> &&TAB,
393 std::unique_ptr<MCObjectWriter> &&OW,
394 std::unique_ptr<MCCodeEmitter> &&Emitter, bool RelaxAll,
395 bool IncrementalLinkerCompatible) {
396 return createAArch64WinCOFFStreamer(Ctx, std::move(TAB), std::move(OW),
397 std::move(Emitter), RelaxAll,
398 IncrementalLinkerCompatible);
399}
400
401namespace {
402
403class AArch64MCInstrAnalysis : public MCInstrAnalysis {
404public:
405 AArch64MCInstrAnalysis(const MCInstrInfo *Info) : MCInstrAnalysis(Info) {}
406
407 bool evaluateBranch(const MCInst &Inst, uint64_t Addr, uint64_t Size,
408 uint64_t &Target) const override {
409 // Search for a PC-relative argument.
410 // This will handle instructions like bcc (where the first argument is the
411 // condition code) and cbz (where it is a register).
412 const auto &Desc = Info->get(Inst.getOpcode());
413 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; i++) {
414 if (Desc.OpInfo[i].OperandType == MCOI::OPERAND_PCREL) {
415 int64_t Imm = Inst.getOperand(i).getImm() * 4;
416 Target = Addr + Imm;
417 return true;
418 }
419 }
420 return false;
421 }
422
423 std::vector<std::pair<uint64_t, uint64_t>>
424 findPltEntries(uint64_t PltSectionVA, ArrayRef<uint8_t> PltContents,
425 uint64_t GotPltSectionVA,
426 const Triple &TargetTriple) const override {
427 // Do a lightweight parsing of PLT entries.
428 std::vector<std::pair<uint64_t, uint64_t>> Result;
429 for (uint64_t Byte = 0, End = PltContents.size(); Byte + 7 < End;
430 Byte += 4) {
431 uint32_t Insn = support::endian::read32le(PltContents.data() + Byte);
432 uint64_t Off = 0;
433 // Check for optional bti c that prefixes adrp in BTI enabled entries
434 if (Insn == 0xd503245f) {
435 Off = 4;
436 Insn = support::endian::read32le(PltContents.data() + Byte + Off);
437 }
438 // Check for adrp.
439 if ((Insn & 0x9f000000) != 0x90000000)
440 continue;
441 Off += 4;
442 uint64_t Imm = (((PltSectionVA + Byte) >> 12) << 12) +
443 (((Insn >> 29) & 3) << 12) + (((Insn >> 5) & 0x3ffff) << 14);
444 uint32_t Insn2 =
445 support::endian::read32le(PltContents.data() + Byte + Off);
446 // Check for: ldr Xt, [Xn, #pimm].
447 if (Insn2 >> 22 == 0x3e5) {
448 Imm += ((Insn2 >> 10) & 0xfff) << 3;
449 Result.push_back(std::make_pair(PltSectionVA + Byte, Imm));
450 Byte += 4;
451 }
452 }
453 return Result;
454 }
455};
456
457} // end anonymous namespace
458
459static MCInstrAnalysis *createAArch64InstrAnalysis(const MCInstrInfo *Info) {
460 return new AArch64MCInstrAnalysis(Info);
461}
462
463// Force static initialization.
464extern "C" LLVM_EXTERNAL_VISIBILITY__attribute__((visibility("default"))) void LLVMInitializeAArch64TargetMC() {
465 for (Target *T : {&getTheAArch64leTarget(), &getTheAArch64beTarget(),
466 &getTheAArch64_32Target(), &getTheARM64Target(),
467 &getTheARM64_32Target()}) {
468 // Register the MC asm info.
469 RegisterMCAsmInfoFn X(*T, createAArch64MCAsmInfo);
470
471 // Register the MC instruction info.
472 TargetRegistry::RegisterMCInstrInfo(*T, createAArch64MCInstrInfo);
473
474 // Register the MC register info.
475 TargetRegistry::RegisterMCRegInfo(*T, createAArch64MCRegisterInfo);
476
477 // Register the MC subtarget info.
478 TargetRegistry::RegisterMCSubtargetInfo(*T, createAArch64MCSubtargetInfo);
479
480 // Register the MC instruction analyzer.
481 TargetRegistry::RegisterMCInstrAnalysis(*T, createAArch64InstrAnalysis);
482
483 // Register the MC Code Emitter
484 TargetRegistry::RegisterMCCodeEmitter(*T, createAArch64MCCodeEmitter);
485
486 // Register the obj streamers.
487 TargetRegistry::RegisterELFStreamer(*T, createELFStreamer);
488 TargetRegistry::RegisterMachOStreamer(*T, createMachOStreamer);
489 TargetRegistry::RegisterCOFFStreamer(*T, createWinCOFFStreamer);
490
491 // Register the obj target streamer.
492 TargetRegistry::RegisterObjectTargetStreamer(
493 *T, createAArch64ObjectTargetStreamer);
494
495 // Register the asm streamer.
496 TargetRegistry::RegisterAsmTargetStreamer(*T,
497 createAArch64AsmTargetStreamer);
498 // Register the MCInstPrinter.
499 TargetRegistry::RegisterMCInstPrinter(*T, createAArch64MCInstPrinter);
500 }
501
502 // Register the asm backend.
503 for (Target *T : {&getTheAArch64leTarget(), &getTheAArch64_32Target(),
504 &getTheARM64Target(), &getTheARM64_32Target()})
505 TargetRegistry::RegisterMCAsmBackend(*T, createAArch64leAsmBackend);
506 TargetRegistry::RegisterMCAsmBackend(getTheAArch64beTarget(),
507 createAArch64beAsmBackend);
508}

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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 contains some templates that are useful if you are working with
11/// the STL at all.
12///
13/// No library is required when using these functions.
14///
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/Optional.h"
22#include "llvm/ADT/STLArrayExtras.h"
23#include "llvm/ADT/STLForwardCompat.h"
24#include "llvm/ADT/STLFunctionalExtras.h"
25#include "llvm/ADT/identity.h"
26#include "llvm/ADT/iterator.h"
27#include "llvm/ADT/iterator_range.h"
28#include "llvm/Config/abi-breaking.h"
29#include "llvm/Support/ErrorHandling.h"
30#include <algorithm>
31#include <cassert>
32#include <cstddef>
33#include <cstdint>
34#include <cstdlib>
35#include <functional>
36#include <initializer_list>
37#include <iterator>
38#include <limits>
39#include <memory>
40#include <tuple>
41#include <type_traits>
42#include <utility>
43
44#ifdef EXPENSIVE_CHECKS
45#include <random> // for std::mt19937
46#endif
47
48namespace llvm {
49
50// Only used by compiler if both template types are the same. Useful when
51// using SFINAE to test for the existence of member functions.
52template <typename T, T> struct SameType;
53
54namespace detail {
55
56template <typename RangeT>
57using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
58
59template <typename RangeT>
60using ValueOfRange =
61 std::remove_reference_t<decltype(*std::begin(std::declval<RangeT &>()))>;
62
63} // end namespace detail
64
65//===----------------------------------------------------------------------===//
66// Extra additions to <type_traits>
67//===----------------------------------------------------------------------===//
68
69template <typename T> struct make_const_ptr {
70 using type = std::add_pointer_t<std::add_const_t<T>>;
71};
72
73template <typename T> struct make_const_ref {
74 using type = std::add_lvalue_reference_t<std::add_const_t<T>>;
75};
76
77namespace detail {
78template <class, template <class...> class Op, class... Args> struct detector {
79 using value_t = std::false_type;
80};
81template <template <class...> class Op, class... Args>
82struct detector<std::void_t<Op<Args...>>, Op, Args...> {
83 using value_t = std::true_type;
84};
85} // end namespace detail
86
87/// Detects if a given trait holds for some set of arguments 'Args'.
88/// For example, the given trait could be used to detect if a given type
89/// has a copy assignment operator:
90/// template<class T>
91/// using has_copy_assign_t = decltype(std::declval<T&>()
92/// = std::declval<const T&>());
93/// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
94template <template <class...> class Op, class... Args>
95using is_detected = typename detail::detector<void, Op, Args...>::value_t;
96
97/// This class provides various trait information about a callable object.
98/// * To access the number of arguments: Traits::num_args
99/// * To access the type of an argument: Traits::arg_t<Index>
100/// * To access the type of the result: Traits::result_t
101template <typename T, bool isClass = std::is_class<T>::value>
102struct function_traits : public function_traits<decltype(&T::operator())> {};
103
104/// Overload for class function types.
105template <typename ClassType, typename ReturnType, typename... Args>
106struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
107 /// The number of arguments to this function.
108 enum { num_args = sizeof...(Args) };
109
110 /// The result type of this function.
111 using result_t = ReturnType;
112
113 /// The type of an argument to this function.
114 template <size_t Index>
115 using arg_t = std::tuple_element_t<Index, std::tuple<Args...>>;
116};
117/// Overload for class function types.
118template <typename ClassType, typename ReturnType, typename... Args>
119struct function_traits<ReturnType (ClassType::*)(Args...), false>
120 : public function_traits<ReturnType (ClassType::*)(Args...) const> {};
121/// Overload for non-class function types.
122template <typename ReturnType, typename... Args>
123struct function_traits<ReturnType (*)(Args...), false> {
124 /// The number of arguments to this function.
125 enum { num_args = sizeof...(Args) };
126
127 /// The result type of this function.
128 using result_t = ReturnType;
129
130 /// The type of an argument to this function.
131 template <size_t i>
132 using arg_t = std::tuple_element_t<i, std::tuple<Args...>>;
133};
134template <typename ReturnType, typename... Args>
135struct function_traits<ReturnType (*const)(Args...), false>
136 : public function_traits<ReturnType (*)(Args...)> {};
137/// Overload for non-class function type references.
138template <typename ReturnType, typename... Args>
139struct function_traits<ReturnType (&)(Args...), false>
140 : public function_traits<ReturnType (*)(Args...)> {};
141
142/// traits class for checking whether type T is one of any of the given
143/// types in the variadic list.
144template <typename T, typename... Ts>
145using is_one_of = std::disjunction<std::is_same<T, Ts>...>;
146
147/// traits class for checking whether type T is a base class for all
148/// the given types in the variadic list.
149template <typename T, typename... Ts>
150using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>;
151
152namespace detail {
153template <typename T, typename... Us> struct TypesAreDistinct;
154template <typename T, typename... Us>
155struct TypesAreDistinct
156 : std::integral_constant<bool, !is_one_of<T, Us...>::value &&
157 TypesAreDistinct<Us...>::value> {};
158template <typename T> struct TypesAreDistinct<T> : std::true_type {};
159} // namespace detail
160
161/// Determine if all types in Ts are distinct.
162///
163/// Useful to statically assert when Ts is intended to describe a non-multi set
164/// of types.
165///
166/// Expensive (currently quadratic in sizeof(Ts...)), and so should only be
167/// asserted once per instantiation of a type which requires it.
168template <typename... Ts> struct TypesAreDistinct;
169template <> struct TypesAreDistinct<> : std::true_type {};
170template <typename... Ts>
171struct TypesAreDistinct
172 : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> {};
173
174/// Find the first index where a type appears in a list of types.
175///
176/// FirstIndexOfType<T, Us...>::value is the first index of T in Us.
177///
178/// Typically only meaningful when it is otherwise statically known that the
179/// type pack has no duplicate types. This should be guaranteed explicitly with
180/// static_assert(TypesAreDistinct<Us...>::value).
181///
182/// It is a compile-time error to instantiate when T is not present in Us, i.e.
183/// if is_one_of<T, Us...>::value is false.
184template <typename T, typename... Us> struct FirstIndexOfType;
185template <typename T, typename U, typename... Us>
186struct FirstIndexOfType<T, U, Us...>
187 : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {};
188template <typename T, typename... Us>
189struct FirstIndexOfType<T, T, Us...> : std::integral_constant<size_t, 0> {};
190
191/// Find the type at a given index in a list of types.
192///
193/// TypeAtIndex<I, Ts...> is the type at index I in Ts.
194template <size_t I, typename... Ts>
195using TypeAtIndex = std::tuple_element_t<I, std::tuple<Ts...>>;
196
197/// Helper which adds two underlying types of enumeration type.
198/// Implicit conversion to a common type is accepted.
199template <typename EnumTy1, typename EnumTy2,
200 typename UT1 = std::enable_if_t<std::is_enum<EnumTy1>::value,
201 std::underlying_type_t<EnumTy1>>,
202 typename UT2 = std::enable_if_t<std::is_enum<EnumTy2>::value,
203 std::underlying_type_t<EnumTy2>>>
204constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS) {
205 return static_cast<UT1>(LHS) + static_cast<UT2>(RHS);
206}
207
208//===----------------------------------------------------------------------===//
209// Extra additions to <iterator>
210//===----------------------------------------------------------------------===//
211
212namespace adl_detail {
213
214using std::begin;
215
216template <typename ContainerTy>
217decltype(auto) adl_begin(ContainerTy &&container) {
218 return begin(std::forward<ContainerTy>(container));
219}
220
221using std::end;
222
223template <typename ContainerTy>
224decltype(auto) adl_end(ContainerTy &&container) {
225 return end(std::forward<ContainerTy>(container));
226}
227
228using std::swap;
229
230template <typename T>
231void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
232 std::declval<T>()))) {
233 swap(std::forward<T>(lhs), std::forward<T>(rhs));
234}
235
236} // end namespace adl_detail
237
238template <typename ContainerTy>
239decltype(auto) adl_begin(ContainerTy &&container) {
240 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
241}
242
243template <typename ContainerTy>
244decltype(auto) adl_end(ContainerTy &&container) {
245 return adl_detail::adl_end(std::forward<ContainerTy>(container));
246}
247
248template <typename T>
249void adl_swap(T &&lhs, T &&rhs) noexcept(
250 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
251 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
252}
253
254/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
255template <typename T>
256constexpr bool empty(const T &RangeOrContainer) {
257 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
258}
259
260/// Returns true if the given container only contains a single element.
261template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
262 auto B = std::begin(C), E = std::end(C);
263 return B != E && std::next(B) == E;
264}
265
266/// Return a range covering \p RangeOrContainer with the first N elements
267/// excluded.
268template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {
269 return make_range(std::next(adl_begin(RangeOrContainer), N),
270 adl_end(RangeOrContainer));
271}
272
273/// Return a range covering \p RangeOrContainer with the last N elements
274/// excluded.
275template <typename T> auto drop_end(T &&RangeOrContainer, size_t N = 1) {
276 return make_range(adl_begin(RangeOrContainer),
277 std::prev(adl_end(RangeOrContainer), N));
278}
279
280// mapped_iterator - This is a simple iterator adapter that causes a function to
281// be applied whenever operator* is invoked on the iterator.
282
283template <typename ItTy, typename FuncTy,
284 typename ReferenceTy =
285 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
286class mapped_iterator
287 : public iterator_adaptor_base<
288 mapped_iterator<ItTy, FuncTy>, ItTy,
289 typename std::iterator_traits<ItTy>::iterator_category,
290 std::remove_reference_t<ReferenceTy>,
291 typename std::iterator_traits<ItTy>::difference_type,
292 std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
293public:
294 mapped_iterator(ItTy U, FuncTy F)
295 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
296
297 ItTy getCurrent() { return this->I; }
298
299 const FuncTy &getFunction() const { return F; }
300
301 ReferenceTy operator*() const { return F(*this->I); }
302
303private:
304 FuncTy F;
305};
306
307// map_iterator - Provide a convenient way to create mapped_iterators, just like
308// make_pair is useful for creating pairs...
309template <class ItTy, class FuncTy>
310inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
311 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
312}
313
314template <class ContainerTy, class FuncTy>
315auto map_range(ContainerTy &&C, FuncTy F) {
316 return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
317}
318
319/// A base type of mapped iterator, that is useful for building derived
320/// iterators that do not need/want to store the map function (as in
321/// mapped_iterator). These iterators must simply provide a `mapElement` method
322/// that defines how to map a value of the iterator to the provided reference
323/// type.
324template <typename DerivedT, typename ItTy, typename ReferenceTy>
325class mapped_iterator_base
326 : public iterator_adaptor_base<
327 DerivedT, ItTy,
328 typename std::iterator_traits<ItTy>::iterator_category,
329 std::remove_reference_t<ReferenceTy>,
330 typename std::iterator_traits<ItTy>::difference_type,
331 std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
332public:
333 using BaseT = mapped_iterator_base;
334
335 mapped_iterator_base(ItTy U)
336 : mapped_iterator_base::iterator_adaptor_base(std::move(U)) {}
337
338 ItTy getCurrent() { return this->I; }
339
340 ReferenceTy operator*() const {
341 return static_cast<const DerivedT &>(*this).mapElement(*this->I);
342 }
343};
344
345/// Helper to determine if type T has a member called rbegin().
346template <typename Ty> class has_rbegin_impl {
347 using yes = char[1];
348 using no = char[2];
349
350 template <typename Inner>
351 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
352
353 template <typename>
354 static no& test(...);
355
356public:
357 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
358};
359
360/// Metafunction to determine if T& or T has a member called rbegin().
361template <typename Ty>
362struct has_rbegin : has_rbegin_impl<std::remove_reference_t<Ty>> {};
363
364// Returns an iterator_range over the given container which iterates in reverse.
365template <typename ContainerTy> auto reverse(ContainerTy &&C) {
366 if constexpr (has_rbegin<ContainerTy>::value)
367 return make_range(C.rbegin(), C.rend());
368 else
369 return make_range(std::make_reverse_iterator(std::end(C)),
370 std::make_reverse_iterator(std::begin(C)));
371}
372
373/// An iterator adaptor that filters the elements of given inner iterators.
374///
375/// The predicate parameter should be a callable object that accepts the wrapped
376/// iterator's reference type and returns a bool. When incrementing or
377/// decrementing the iterator, it will call the predicate on each element and
378/// skip any where it returns false.
379///
380/// \code
381/// int A[] = { 1, 2, 3, 4 };
382/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
383/// // R contains { 1, 3 }.
384/// \endcode
385///
386/// Note: filter_iterator_base implements support for forward iteration.
387/// filter_iterator_impl exists to provide support for bidirectional iteration,
388/// conditional on whether the wrapped iterator supports it.
389template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
390class filter_iterator_base
391 : public iterator_adaptor_base<
392 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
393 WrappedIteratorT,
394 typename std::common_type<
395 IterTag, typename std::iterator_traits<
396 WrappedIteratorT>::iterator_category>::type> {
397 using BaseT = typename filter_iterator_base::iterator_adaptor_base;
398
399protected:
400 WrappedIteratorT End;
401 PredicateT Pred;
402
403 void findNextValid() {
404 while (this->I != End && !Pred(*this->I))
405 BaseT::operator++();
406 }
407
408 // Construct the iterator. The begin iterator needs to know where the end
409 // is, so that it can properly stop when it gets there. The end iterator only
410 // needs the predicate to support bidirectional iteration.
411 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
412 PredicateT Pred)
413 : BaseT(Begin), End(End), Pred(Pred) {
414 findNextValid();
415 }
416
417public:
418 using BaseT::operator++;
419
420 filter_iterator_base &operator++() {
421 BaseT::operator++();
422 findNextValid();
423 return *this;
424 }
425
426 decltype(auto) operator*() const {
427 assert(BaseT::wrapped() != End && "Cannot dereference end iterator!")(static_cast <bool> (BaseT::wrapped() != End &&
"Cannot dereference end iterator!") ? void (0) : __assert_fail
("BaseT::wrapped() != End && \"Cannot dereference end iterator!\""
, "llvm/include/llvm/ADT/STLExtras.h", 427, __extension__ __PRETTY_FUNCTION__
))
;
428 return BaseT::operator*();
429 }
430
431 decltype(auto) operator->() const {
432 assert(BaseT::wrapped() != End && "Cannot dereference end iterator!")(static_cast <bool> (BaseT::wrapped() != End &&
"Cannot dereference end iterator!") ? void (0) : __assert_fail
("BaseT::wrapped() != End && \"Cannot dereference end iterator!\""
, "llvm/include/llvm/ADT/STLExtras.h", 432, __extension__ __PRETTY_FUNCTION__
))
;
433 return BaseT::operator->();
434 }
435};
436
437/// Specialization of filter_iterator_base for forward iteration only.
438template <typename WrappedIteratorT, typename PredicateT,
439 typename IterTag = std::forward_iterator_tag>
440class filter_iterator_impl
441 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
442public:
443 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
444 PredicateT Pred)
445 : filter_iterator_impl::filter_iterator_base(Begin, End, Pred) {}
446};
447
448/// Specialization of filter_iterator_base for bidirectional iteration.
449template <typename WrappedIteratorT, typename PredicateT>
450class filter_iterator_impl<WrappedIteratorT, PredicateT,
451 std::bidirectional_iterator_tag>
452 : public filter_iterator_base<WrappedIteratorT, PredicateT,
453 std::bidirectional_iterator_tag> {
454 using BaseT = typename filter_iterator_impl::filter_iterator_base;
455
456 void findPrevValid() {
457 while (!this->Pred(*this->I))
458 BaseT::operator--();
459 }
460
461public:
462 using BaseT::operator--;
463
464 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
465 PredicateT Pred)
466 : BaseT(Begin, End, Pred) {}
467
468 filter_iterator_impl &operator--() {
469 BaseT::operator--();
470 findPrevValid();
471 return *this;
472 }
473};
474
475namespace detail {
476
477template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
478 using type = std::forward_iterator_tag;
479};
480
481template <> struct fwd_or_bidi_tag_impl<true> {
482 using type = std::bidirectional_iterator_tag;
483};
484
485/// Helper which sets its type member to forward_iterator_tag if the category
486/// of \p IterT does not derive from bidirectional_iterator_tag, and to
487/// bidirectional_iterator_tag otherwise.
488template <typename IterT> struct fwd_or_bidi_tag {
489 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
490 std::bidirectional_iterator_tag,
491 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
492};
493
494} // namespace detail
495
496/// Defines filter_iterator to a suitable specialization of
497/// filter_iterator_impl, based on the underlying iterator's category.
498template <typename WrappedIteratorT, typename PredicateT>
499using filter_iterator = filter_iterator_impl<
500 WrappedIteratorT, PredicateT,
501 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
502
503/// Convenience function that takes a range of elements and a predicate,
504/// and return a new filter_iterator range.
505///
506/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
507/// lifetime of that temporary is not kept by the returned range object, and the
508/// temporary is going to be dropped on the floor after the make_iterator_range
509/// full expression that contains this function call.
510template <typename RangeT, typename PredicateT>
511iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
512make_filter_range(RangeT &&Range, PredicateT Pred) {
513 using FilterIteratorT =
514 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
515 return make_range(
516 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
517 std::end(std::forward<RangeT>(Range)), Pred),
518 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
519 std::end(std::forward<RangeT>(Range)), Pred));
520}
521
522/// A pseudo-iterator adaptor that is designed to implement "early increment"
523/// style loops.
524///
525/// This is *not a normal iterator* and should almost never be used directly. It
526/// is intended primarily to be used with range based for loops and some range
527/// algorithms.
528///
529/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
530/// somewhere between them. The constraints of these iterators are:
531///
532/// - On construction or after being incremented, it is comparable and
533/// dereferencable. It is *not* incrementable.
534/// - After being dereferenced, it is neither comparable nor dereferencable, it
535/// is only incrementable.
536///
537/// This means you can only dereference the iterator once, and you can only
538/// increment it once between dereferences.
539template <typename WrappedIteratorT>
540class early_inc_iterator_impl
541 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
542 WrappedIteratorT, std::input_iterator_tag> {
543 using BaseT = typename early_inc_iterator_impl::iterator_adaptor_base;
544
545 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
546
547protected:
548#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
549 bool IsEarlyIncremented = false;
550#endif
551
552public:
553 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
554
555 using BaseT::operator*;
556 decltype(*std::declval<WrappedIteratorT>()) operator*() {
557#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
558 assert(!IsEarlyIncremented && "Cannot dereference twice!")(static_cast <bool> (!IsEarlyIncremented && "Cannot dereference twice!"
) ? void (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot dereference twice!\""
, "llvm/include/llvm/ADT/STLExtras.h", 558, __extension__ __PRETTY_FUNCTION__
))
;
559 IsEarlyIncremented = true;
560#endif
561 return *(this->I)++;
562 }
563
564 using BaseT::operator++;
565 early_inc_iterator_impl &operator++() {
566#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
567 assert(IsEarlyIncremented && "Cannot increment before dereferencing!")(static_cast <bool> (IsEarlyIncremented && "Cannot increment before dereferencing!"
) ? void (0) : __assert_fail ("IsEarlyIncremented && \"Cannot increment before dereferencing!\""
, "llvm/include/llvm/ADT/STLExtras.h", 567, __extension__ __PRETTY_FUNCTION__
))
;
568 IsEarlyIncremented = false;
569#endif
570 return *this;
571 }
572
573 friend bool operator==(const early_inc_iterator_impl &LHS,
574 const early_inc_iterator_impl &RHS) {
575#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
576 assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!")(static_cast <bool> (!LHS.IsEarlyIncremented &&
"Cannot compare after dereferencing!") ? void (0) : __assert_fail
("!LHS.IsEarlyIncremented && \"Cannot compare after dereferencing!\""
, "llvm/include/llvm/ADT/STLExtras.h", 576, __extension__ __PRETTY_FUNCTION__
))
;
577#endif
578 return (const BaseT &)LHS == (const BaseT &)RHS;
579 }
580};
581
582/// Make a range that does early increment to allow mutation of the underlying
583/// range without disrupting iteration.
584///
585/// The underlying iterator will be incremented immediately after it is
586/// dereferenced, allowing deletion of the current node or insertion of nodes to
587/// not disrupt iteration provided they do not invalidate the *next* iterator --
588/// the current iterator can be invalidated.
589///
590/// This requires a very exact pattern of use that is only really suitable to
591/// range based for loops and other range algorithms that explicitly guarantee
592/// to dereference exactly once each element, and to increment exactly once each
593/// element.
594template <typename RangeT>
595iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
596make_early_inc_range(RangeT &&Range) {
597 using EarlyIncIteratorT =
598 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
599 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
600 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
601}
602
603// forward declarations required by zip_shortest/zip_first/zip_longest
604template <typename R, typename UnaryPredicate>
605bool all_of(R &&range, UnaryPredicate P);
606template <typename R, typename UnaryPredicate>
607bool any_of(R &&range, UnaryPredicate P);
608
609namespace detail {
610
611using std::declval;
612
613// We have to alias this since inlining the actual type at the usage site
614// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
615template<typename... Iters> struct ZipTupleType {
616 using type = std::tuple<decltype(*declval<Iters>())...>;
617};
618
619template <typename ZipType, typename... Iters>
620using zip_traits = iterator_facade_base<
621 ZipType,
622 typename std::common_type<
623 std::bidirectional_iterator_tag,
624 typename std::iterator_traits<Iters>::iterator_category...>::type,
625 // ^ TODO: Implement random access methods.
626 typename ZipTupleType<Iters...>::type,
627 typename std::iterator_traits<
628 std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type,
629 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
630 // inner iterators have the same difference_type. It would fail if, for
631 // instance, the second field's difference_type were non-numeric while the
632 // first is.
633 typename ZipTupleType<Iters...>::type *,
634 typename ZipTupleType<Iters...>::type>;
635
636template <typename ZipType, typename... Iters>
637struct zip_common : public zip_traits<ZipType, Iters...> {
638 using Base = zip_traits<ZipType, Iters...>;
639 using value_type = typename Base::value_type;
640
641 std::tuple<Iters...> iterators;
642
643protected:
644 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
645 return value_type(*std::get<Ns>(iterators)...);
646 }
647
648 template <size_t... Ns>
649 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
650 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
651 }
652
653 template <size_t... Ns>
654 decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
655 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
656 }
657
658 template <size_t... Ns>
659 bool test_all_equals(const zip_common &other,
660 std::index_sequence<Ns...>) const {
661 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) ==
662 std::get<Ns>(other.iterators)...},
663 identity<bool>{});
664 }
665
666public:
667 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
668
669 value_type operator*() const {
670 return deref(std::index_sequence_for<Iters...>{});
671 }
672
673 ZipType &operator++() {
674 iterators = tup_inc(std::index_sequence_for<Iters...>{});
675 return *reinterpret_cast<ZipType *>(this);
676 }
677
678 ZipType &operator--() {
679 static_assert(Base::IsBidirectional,
680 "All inner iterators must be at least bidirectional.");
681 iterators = tup_dec(std::index_sequence_for<Iters...>{});
682 return *reinterpret_cast<ZipType *>(this);
683 }
684
685 /// Return true if all the iterator are matching `other`'s iterators.
686 bool all_equals(zip_common &other) {
687 return test_all_equals(other, std::index_sequence_for<Iters...>{});
688 }
689};
690
691template <typename... Iters>
692struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
693 using Base = zip_common<zip_first<Iters...>, Iters...>;
694
695 bool operator==(const zip_first<Iters...> &other) const {
696 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
697 }
698
699 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
700};
701
702template <typename... Iters>
703class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
704 template <size_t... Ns>
705 bool test(const zip_shortest<Iters...> &other,
706 std::index_sequence<Ns...>) const {
707 return all_of(llvm::ArrayRef<bool>({std::get<Ns>(this->iterators) !=
708 std::get<Ns>(other.iterators)...}),
709 identity<bool>{});
710 }
711
712public:
713 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
714
715 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
716
717 bool operator==(const zip_shortest<Iters...> &other) const {
718 return !test(other, std::index_sequence_for<Iters...>{});
719 }
720};
721
722template <template <typename...> class ItType, typename... Args> class zippy {
723public:
724 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
725 using iterator_category = typename iterator::iterator_category;
726 using value_type = typename iterator::value_type;
727 using difference_type = typename iterator::difference_type;
728 using pointer = typename iterator::pointer;
729 using reference = typename iterator::reference;
730
731private:
732 std::tuple<Args...> ts;
733
734 template <size_t... Ns>
735 iterator begin_impl(std::index_sequence<Ns...>) const {
736 return iterator(std::begin(std::get<Ns>(ts))...);
737 }
738 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
739 return iterator(std::end(std::get<Ns>(ts))...);
740 }
741
742public:
743 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
744
745 iterator begin() const {
746 return begin_impl(std::index_sequence_for<Args...>{});
747 }
748 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
749};
750
751} // end namespace detail
752
753/// zip iterator for two or more iteratable types.
754template <typename T, typename U, typename... Args>
755detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
756 Args &&... args) {
757 return detail::zippy<detail::zip_shortest, T, U, Args...>(
758 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
759}
760
761/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
762/// be the shortest.
763template <typename T, typename U, typename... Args>
764detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
765 Args &&... args) {
766 return detail::zippy<detail::zip_first, T, U, Args...>(
767 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
768}
769
770namespace detail {
771template <typename Iter>
772Iter next_or_end(const Iter &I, const Iter &End) {
773 if (I == End)
774 return End;
775 return std::next(I);
776}
777
778template <typename Iter>
779auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
780 std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
781 if (I == End)
782 return None;
783 return *I;
784}
785
786template <typename Iter> struct ZipLongestItemType {
787 using type = llvm::Optional<std::remove_const_t<
788 std::remove_reference_t<decltype(*std::declval<Iter>())>>>;
789};
790
791template <typename... Iters> struct ZipLongestTupleType {
792 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
793};
794
795template <typename... Iters>
796class zip_longest_iterator
797 : public iterator_facade_base<
798 zip_longest_iterator<Iters...>,
799 typename std::common_type<
800 std::forward_iterator_tag,
801 typename std::iterator_traits<Iters>::iterator_category...>::type,
802 typename ZipLongestTupleType<Iters...>::type,
803 typename std::iterator_traits<
804 std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type,
805 typename ZipLongestTupleType<Iters...>::type *,
806 typename ZipLongestTupleType<Iters...>::type> {
807public:
808 using value_type = typename ZipLongestTupleType<Iters...>::type;
809
810private:
811 std::tuple<Iters...> iterators;
812 std::tuple<Iters...> end_iterators;
813
814 template <size_t... Ns>
815 bool test(const zip_longest_iterator<Iters...> &other,
816 std::index_sequence<Ns...>) const {
817 return llvm::any_of(
818 std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
819 std::get<Ns>(other.iterators)...},
820 identity<bool>{});
821 }
822
823 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
824 return value_type(
825 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
826 }
827
828 template <size_t... Ns>
829 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
830 return std::tuple<Iters...>(
831 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
832 }
833
834public:
835 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
836 : iterators(std::forward<Iters>(ts.first)...),
837 end_iterators(std::forward<Iters>(ts.second)...) {}
838
839 value_type operator*() const {
840 return deref(std::index_sequence_for<Iters...>{});
841 }
842
843 zip_longest_iterator<Iters...> &operator++() {
844 iterators = tup_inc(std::index_sequence_for<Iters...>{});
845 return *this;
846 }
847
848 bool operator==(const zip_longest_iterator<Iters...> &other) const {
849 return !test(other, std::index_sequence_for<Iters...>{});
850 }
851};
852
853template <typename... Args> class zip_longest_range {
854public:
855 using iterator =
856 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
857 using iterator_category = typename iterator::iterator_category;
858 using value_type = typename iterator::value_type;
859 using difference_type = typename iterator::difference_type;
860 using pointer = typename iterator::pointer;
861 using reference = typename iterator::reference;
862
863private:
864 std::tuple<Args...> ts;
865
866 template <size_t... Ns>
867 iterator begin_impl(std::index_sequence<Ns...>) const {
868 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
869 adl_end(std::get<Ns>(ts)))...);
870 }
871
872 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
873 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
874 adl_end(std::get<Ns>(ts)))...);
875 }
876
877public:
878 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
879
880 iterator begin() const {
881 return begin_impl(std::index_sequence_for<Args...>{});
882 }
883 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
884};
885} // namespace detail
886
887/// Iterate over two or more iterators at the same time. Iteration continues
888/// until all iterators reach the end. The llvm::Optional only contains a value
889/// if the iterator has not reached the end.
890template <typename T, typename U, typename... Args>
891detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
892 Args &&... args) {
893 return detail::zip_longest_range<T, U, Args...>(
894 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
895}
896
897/// Iterator wrapper that concatenates sequences together.
898///
899/// This can concatenate different iterators, even with different types, into
900/// a single iterator provided the value types of all the concatenated
901/// iterators expose `reference` and `pointer` types that can be converted to
902/// `ValueT &` and `ValueT *` respectively. It doesn't support more
903/// interesting/customized pointer or reference types.
904///
905/// Currently this only supports forward or higher iterator categories as
906/// inputs and always exposes a forward iterator interface.
907template <typename ValueT, typename... IterTs>
908class concat_iterator
909 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
910 std::forward_iterator_tag, ValueT> {
911 using BaseT = typename concat_iterator::iterator_facade_base;
912
913 /// We store both the current and end iterators for each concatenated
914 /// sequence in a tuple of pairs.
915 ///
916 /// Note that something like iterator_range seems nice at first here, but the
917 /// range properties are of little benefit and end up getting in the way
918 /// because we need to do mutation on the current iterators.
919 std::tuple<IterTs...> Begins;
920 std::tuple<IterTs...> Ends;
921
922 /// Attempts to increment a specific iterator.
923 ///
924 /// Returns true if it was able to increment the iterator. Returns false if
925 /// the iterator is already at the end iterator.
926 template <size_t Index> bool incrementHelper() {
927 auto &Begin = std::get<Index>(Begins);
928 auto &End = std::get<Index>(Ends);
929 if (Begin == End)
930 return false;
931
932 ++Begin;
933 return true;
934 }
935
936 /// Increments the first non-end iterator.
937 ///
938 /// It is an error to call this with all iterators at the end.
939 template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
940 // Build a sequence of functions to increment each iterator if possible.
941 bool (concat_iterator::*IncrementHelperFns[])() = {
942 &concat_iterator::incrementHelper<Ns>...};
943
944 // Loop over them, and stop as soon as we succeed at incrementing one.
945 for (auto &IncrementHelperFn : IncrementHelperFns)
946 if ((this->*IncrementHelperFn)())
947 return;
948
949 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "llvm/include/llvm/ADT/STLExtras.h", 949)
;
950 }
951
952 /// Returns null if the specified iterator is at the end. Otherwise,
953 /// dereferences the iterator and returns the address of the resulting
954 /// reference.
955 template <size_t Index> ValueT *getHelper() const {
956 auto &Begin = std::get<Index>(Begins);
957 auto &End = std::get<Index>(Ends);
958 if (Begin == End)
959 return nullptr;
960
961 return &*Begin;
962 }
963
964 /// Finds the first non-end iterator, dereferences, and returns the resulting
965 /// reference.
966 ///
967 /// It is an error to call this with all iterators at the end.
968 template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
969 // Build a sequence of functions to get from iterator if possible.
970 ValueT *(concat_iterator::*GetHelperFns[])() const = {
971 &concat_iterator::getHelper<Ns>...};
972
973 // Loop over them, and return the first result we find.
974 for (auto &GetHelperFn : GetHelperFns)
975 if (ValueT *P = (this->*GetHelperFn)())
976 return *P;
977
978 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "llvm/include/llvm/ADT/STLExtras.h", 978)
;
979 }
980
981public:
982 /// Constructs an iterator from a sequence of ranges.
983 ///
984 /// We need the full range to know how to switch between each of the
985 /// iterators.
986 template <typename... RangeTs>
987 explicit concat_iterator(RangeTs &&... Ranges)
988 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
989
990 using BaseT::operator++;
991
992 concat_iterator &operator++() {
993 increment(std::index_sequence_for<IterTs...>());
994 return *this;
995 }
996
997 ValueT &operator*() const {
998 return get(std::index_sequence_for<IterTs...>());
999 }
1000
1001 bool operator==(const concat_iterator &RHS) const {
1002 return Begins == RHS.Begins && Ends == RHS.Ends;
1003 }
1004};
1005
1006namespace detail {
1007
1008/// Helper to store a sequence of ranges being concatenated and access them.
1009///
1010/// This is designed to facilitate providing actual storage when temporaries
1011/// are passed into the constructor such that we can use it as part of range
1012/// based for loops.
1013template <typename ValueT, typename... RangeTs> class concat_range {
1014public:
1015 using iterator =
1016 concat_iterator<ValueT,
1017 decltype(std::begin(std::declval<RangeTs &>()))...>;
1018
1019private:
1020 std::tuple<RangeTs...> Ranges;
1021
1022 template <size_t... Ns>
1023 iterator begin_impl(std::index_sequence<Ns...>) {
1024 return iterator(std::get<Ns>(Ranges)...);
1025 }
1026 template <size_t... Ns>
1027 iterator begin_impl(std::index_sequence<Ns...>) const {
1028 return iterator(std::get<Ns>(Ranges)...);
1029 }
1030 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
1031 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1032 std::end(std::get<Ns>(Ranges)))...);
1033 }
1034 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
1035 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1036 std::end(std::get<Ns>(Ranges)))...);
1037 }
1038
1039public:
1040 concat_range(RangeTs &&... Ranges)
1041 : Ranges(std::forward<RangeTs>(Ranges)...) {}
1042
1043 iterator begin() {
1044 return begin_impl(std::index_sequence_for<RangeTs...>{});
1045 }
1046 iterator begin() const {
1047 return begin_impl(std::index_sequence_for<RangeTs...>{});
1048 }
1049 iterator end() {
1050 return end_impl(std::index_sequence_for<RangeTs...>{});
1051 }
1052 iterator end() const {
1053 return end_impl(std::index_sequence_for<RangeTs...>{});
1054 }
1055};
1056
1057} // end namespace detail
1058
1059/// Concatenated range across two or more ranges.
1060///
1061/// The desired value type must be explicitly specified.
1062template <typename ValueT, typename... RangeTs>
1063detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1064 static_assert(sizeof...(RangeTs) > 1,
1065 "Need more than one range to concatenate!");
1066 return detail::concat_range<ValueT, RangeTs...>(
1067 std::forward<RangeTs>(Ranges)...);
1068}
1069
1070/// A utility class used to implement an iterator that contains some base object
1071/// and an index. The iterator moves the index but keeps the base constant.
1072template <typename DerivedT, typename BaseT, typename T,
1073 typename PointerT = T *, typename ReferenceT = T &>
1074class indexed_accessor_iterator
1075 : public llvm::iterator_facade_base<DerivedT,
1076 std::random_access_iterator_tag, T,
1077 std::ptrdiff_t, PointerT, ReferenceT> {
1078public:
1079 ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
1080 assert(base == rhs.base && "incompatible iterators")(static_cast <bool> (base == rhs.base && "incompatible iterators"
) ? void (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "llvm/include/llvm/ADT/STLExtras.h", 1080, __extension__ __PRETTY_FUNCTION__
))
;
1081 return index - rhs.index;
1082 }
1083 bool operator==(const indexed_accessor_iterator &rhs) const {
1084 return base == rhs.base && index == rhs.index;
1085 }
1086 bool operator<(const indexed_accessor_iterator &rhs) const {
1087 assert(base == rhs.base && "incompatible iterators")(static_cast <bool> (base == rhs.base && "incompatible iterators"
) ? void (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "llvm/include/llvm/ADT/STLExtras.h", 1087, __extension__ __PRETTY_FUNCTION__
))
;
1088 return index < rhs.index;
1089 }
1090
1091 DerivedT &operator+=(ptrdiff_t offset) {
1092 this->index += offset;
1093 return static_cast<DerivedT &>(*this);
1094 }
1095 DerivedT &operator-=(ptrdiff_t offset) {
1096 this->index -= offset;
1097 return static_cast<DerivedT &>(*this);
1098 }
1099
1100 /// Returns the current index of the iterator.
1101 ptrdiff_t getIndex() const { return index; }
1102
1103 /// Returns the current base of the iterator.
1104 const BaseT &getBase() const { return base; }
1105
1106protected:
1107 indexed_accessor_iterator(BaseT base, ptrdiff_t index)
1108 : base(base), index(index) {}
1109 BaseT base;
1110 ptrdiff_t index;
1111};
1112
1113namespace detail {
1114/// The class represents the base of a range of indexed_accessor_iterators. It
1115/// provides support for many different range functionalities, e.g.
1116/// drop_front/slice/etc.. Derived range classes must implement the following
1117/// static methods:
1118/// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1119/// - Dereference an iterator pointing to the base object at the given
1120/// index.
1121/// * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1122/// - Return a new base that is offset from the provide base by 'index'
1123/// elements.
1124template <typename DerivedT, typename BaseT, typename T,
1125 typename PointerT = T *, typename ReferenceT = T &>
1126class indexed_accessor_range_base {
1127public:
1128 using RangeBaseT = indexed_accessor_range_base;
1129
1130 /// An iterator element of this range.
1131 class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1132 PointerT, ReferenceT> {
1133 public:
1134 // Index into this iterator, invoking a static method on the derived type.
1135 ReferenceT operator*() const {
1136 return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1137 }
1138
1139 private:
1140 iterator(BaseT owner, ptrdiff_t curIndex)
1141 : iterator::indexed_accessor_iterator(owner, curIndex) {}
1142
1143 /// Allow access to the constructor.
1144 friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1145 ReferenceT>;
1146 };
1147
1148 indexed_accessor_range_base(iterator begin, iterator end)
1149 : base(offset_base(begin.getBase(), begin.getIndex())),
1150 count(end.getIndex() - begin.getIndex()) {}
1151 indexed_accessor_range_base(const iterator_range<iterator> &range)
1152 : indexed_accessor_range_base(range.begin(), range.end()) {}
1153 indexed_accessor_range_base(BaseT base, ptrdiff_t count)
1154 : base(base), count(count) {}
1155
1156 iterator begin() const { return iterator(base, 0); }
1157 iterator end() const { return iterator(base, count); }
1158 ReferenceT operator[](size_t Index) const {
1159 assert(Index < size() && "invalid index for value range")(static_cast <bool> (Index < size() && "invalid index for value range"
) ? void (0) : __assert_fail ("Index < size() && \"invalid index for value range\""
, "llvm/include/llvm/ADT/STLExtras.h", 1159, __extension__ __PRETTY_FUNCTION__
))
;
1160 return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index));
1161 }
1162 ReferenceT front() const {
1163 assert(!empty() && "expected non-empty range")(static_cast <bool> (!empty() && "expected non-empty range"
) ? void (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "llvm/include/llvm/ADT/STLExtras.h", 1163, __extension__ __PRETTY_FUNCTION__
))
;
1164 return (*this)[0];
1165 }
1166 ReferenceT back() const {
1167 assert(!empty() && "expected non-empty range")(static_cast <bool> (!empty() && "expected non-empty range"
) ? void (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "llvm/include/llvm/ADT/STLExtras.h", 1167, __extension__ __PRETTY_FUNCTION__
))
;
1168 return (*this)[size() - 1];
1169 }
1170
1171 /// Compare this range with another.
1172 template <typename OtherT>
1173 friend bool operator==(const indexed_accessor_range_base &lhs,
1174 const OtherT &rhs) {
1175 return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1176 }
1177 template <typename OtherT>
1178 friend bool operator!=(const indexed_accessor_range_base &lhs,
1179 const OtherT &rhs) {
1180 return !(lhs == rhs);
1181 }
1182
1183 /// Return the size of this range.
1184 size_t size() const { return count; }
1185
1186 /// Return if the range is empty.
1187 bool empty() const { return size() == 0; }
1188
1189 /// Drop the first N elements, and keep M elements.
1190 DerivedT slice(size_t n, size_t m) const {
1191 assert(n + m <= size() && "invalid size specifiers")(static_cast <bool> (n + m <= size() && "invalid size specifiers"
) ? void (0) : __assert_fail ("n + m <= size() && \"invalid size specifiers\""
, "llvm/include/llvm/ADT/STLExtras.h", 1191, __extension__ __PRETTY_FUNCTION__
))
;
1192 return DerivedT(offset_base(base, n), m);
1193 }
1194
1195 /// Drop the first n elements.
1196 DerivedT drop_front(size_t n = 1) const {
1197 assert(size() >= n && "Dropping more elements than exist")(static_cast <bool> (size() >= n && "Dropping more elements than exist"
) ? void (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "llvm/include/llvm/ADT/STLExtras.h", 1197, __extension__ __PRETTY_FUNCTION__
))
;
1198 return slice(n, size() - n);
1199 }
1200 /// Drop the last n elements.
1201 DerivedT drop_back(size_t n = 1) const {
1202 assert(size() >= n && "Dropping more elements than exist")(static_cast <bool> (size() >= n && "Dropping more elements than exist"
) ? void (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "llvm/include/llvm/ADT/STLExtras.h", 1202, __extension__ __PRETTY_FUNCTION__
))
;
1203 return DerivedT(base, size() - n);
1204 }
1205
1206 /// Take the first n elements.
1207 DerivedT take_front(size_t n = 1) const {
1208 return n < size() ? drop_back(size() - n)
1209 : static_cast<const DerivedT &>(*this);
1210 }
1211
1212 /// Take the last n elements.
1213 DerivedT take_back(size_t n = 1) const {
1214 return n < size() ? drop_front(size() - n)
1215 : static_cast<const DerivedT &>(*this);
1216 }
1217
1218 /// Allow conversion to any type accepting an iterator_range.
1219 template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1220 RangeT, iterator_range<iterator>>::value>>
1221 operator RangeT() const {
1222 return RangeT(iterator_range<iterator>(*this));
1223 }
1224
1225 /// Returns the base of this range.
1226 const BaseT &getBase() const { return base; }
1227
1228private:
1229 /// Offset the given base by the given amount.
1230 static BaseT offset_base(const BaseT &base, size_t n) {
1231 return n == 0 ? base : DerivedT::offset_base(base, n);
1232 }
1233
1234protected:
1235 indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
1236 indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
1237 indexed_accessor_range_base &
1238 operator=(const indexed_accessor_range_base &) = default;
1239
1240 /// The base that owns the provided range of values.
1241 BaseT base;
1242 /// The size from the owning range.
1243 ptrdiff_t count;
1244};
1245} // end namespace detail
1246
1247/// This class provides an implementation of a range of
1248/// indexed_accessor_iterators where the base is not indexable. Ranges with
1249/// bases that are offsetable should derive from indexed_accessor_range_base
1250/// instead. Derived range classes are expected to implement the following
1251/// static method:
1252/// * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1253/// - Dereference an iterator pointing to a parent base at the given index.
1254template <typename DerivedT, typename BaseT, typename T,
1255 typename PointerT = T *, typename ReferenceT = T &>
1256class indexed_accessor_range
1257 : public detail::indexed_accessor_range_base<
1258 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1259public:
1260 indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
1261 : detail::indexed_accessor_range_base<
1262 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1263 std::make_pair(base, startIndex), count) {}
1264 using detail::indexed_accessor_range_base<
1265 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1266 ReferenceT>::indexed_accessor_range_base;
1267
1268 /// Returns the current base of the range.
1269 const BaseT &getBase() const { return this->base.first; }
1270
1271 /// Returns the current start index of the range.
1272 ptrdiff_t getStartIndex() const { return this->base.second; }
1273
1274 /// See `detail::indexed_accessor_range_base` for details.
1275 static std::pair<BaseT, ptrdiff_t>
1276 offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1277 // We encode the internal base as a pair of the derived base and a start
1278 // index into the derived base.
1279 return std::make_pair(base.first, base.second + index);
1280 }
1281 /// See `detail::indexed_accessor_range_base` for details.
1282 static ReferenceT
1283 dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1284 ptrdiff_t index) {
1285 return DerivedT::dereference(base.first, base.second + index);
1286 }
1287};
1288
1289namespace detail {
1290/// Return a reference to the first or second member of a reference. Otherwise,
1291/// return a copy of the member of a temporary.
1292///
1293/// When passing a range whose iterators return values instead of references,
1294/// the reference must be dropped from `decltype((elt.first))`, which will
1295/// always be a reference, to avoid returning a reference to a temporary.
1296template <typename EltTy, typename FirstTy> class first_or_second_type {
1297public:
1298 using type =
1299 typename std::conditional_t<std::is_reference<EltTy>::value, FirstTy,
1300 std::remove_reference_t<FirstTy>>;
1301};
1302} // end namespace detail
1303
1304/// Given a container of pairs, return a range over the first elements.
1305template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
1306 using EltTy = decltype((*std::begin(c)));
1307 return llvm::map_range(std::forward<ContainerTy>(c),
1308 [](EltTy elt) -> typename detail::first_or_second_type<
1309 EltTy, decltype((elt.first))>::type {
1310 return elt.first;
1311 });
1312}
1313
1314/// Given a container of pairs, return a range over the second elements.
1315template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1316 using EltTy = decltype((*std::begin(c)));
1317 return llvm::map_range(
1318 std::forward<ContainerTy>(c),
1319 [](EltTy elt) ->
1320 typename detail::first_or_second_type<EltTy,
1321 decltype((elt.second))>::type {
1322 return elt.second;
1323 });
1324}
1325
1326//===----------------------------------------------------------------------===//
1327// Extra additions to <utility>
1328//===----------------------------------------------------------------------===//
1329
1330/// Function object to check whether the first component of a std::pair
1331/// compares less than the first component of another std::pair.
1332struct less_first {
1333 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1334 return std::less<>()(lhs.first, rhs.first);
1335 }
1336};
1337
1338/// Function object to check whether the second component of a std::pair
1339/// compares less than the second component of another std::pair.
1340struct less_second {
1341 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1342 return std::less<>()(lhs.second, rhs.second);
1343 }
1344};
1345
1346/// \brief Function object to apply a binary function to the first component of
1347/// a std::pair.
1348template<typename FuncTy>
1349struct on_first {
1350 FuncTy func;
1351
1352 template <typename T>
1353 decltype(auto) operator()(const T &lhs, const T &rhs) const {
1354 return func(lhs.first, rhs.first);
1355 }
1356};
1357
1358/// Utility type to build an inheritance chain that makes it easy to rank
1359/// overload candidates.
1360template <int N> struct rank : rank<N - 1> {};
1361template <> struct rank<0> {};
1362
1363/// traits class for checking whether type T is one of any of the given
1364/// types in the variadic list.
1365template <typename T, typename... Ts>
1366using is_one_of = std::disjunction<std::is_same<T, Ts>...>;
1367
1368/// traits class for checking whether type T is a base class for all
1369/// the given types in the variadic list.
1370template <typename T, typename... Ts>
1371using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>;
1372
1373namespace detail {
1374template <typename... Ts> struct Visitor;
1375
1376template <typename HeadT, typename... TailTs>
1377struct Visitor<HeadT, TailTs...> : remove_cvref_t<HeadT>, Visitor<TailTs...> {
1378 explicit constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
1379 : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)),
1380 Visitor<TailTs...>(std::forward<TailTs>(Tail)...) {}
1381 using remove_cvref_t<HeadT>::operator();
1382 using Visitor<TailTs...>::operator();
1383};
1384
1385template <typename HeadT> struct Visitor<HeadT> : remove_cvref_t<HeadT> {
1386 explicit constexpr Visitor(HeadT &&Head)
1387 : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)) {}
1388 using remove_cvref_t<HeadT>::operator();
1389};
1390} // namespace detail
1391
1392/// Returns an opaquely-typed Callable object whose operator() overload set is
1393/// the sum of the operator() overload sets of each CallableT in CallableTs.
1394///
1395/// The type of the returned object derives from each CallableT in CallableTs.
1396/// The returned object is constructed by invoking the appropriate copy or move
1397/// constructor of each CallableT, as selected by overload resolution on the
1398/// corresponding argument to makeVisitor.
1399///
1400/// Example:
1401///
1402/// \code
1403/// auto visitor = makeVisitor([](auto) { return "unhandled type"; },
1404/// [](int i) { return "int"; },
1405/// [](std::string s) { return "str"; });
1406/// auto a = visitor(42); // `a` is now "int".
1407/// auto b = visitor("foo"); // `b` is now "str".
1408/// auto c = visitor(3.14f); // `c` is now "unhandled type".
1409/// \endcode
1410///
1411/// Example of making a visitor with a lambda which captures a move-only type:
1412///
1413/// \code
1414/// std::unique_ptr<FooHandler> FH = /* ... */;
1415/// auto visitor = makeVisitor(
1416/// [FH{std::move(FH)}](Foo F) { return FH->handle(F); },
1417/// [](int i) { return i; },
1418/// [](std::string s) { return atoi(s); });
1419/// \endcode
1420template <typename... CallableTs>
1421constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) {
1422 return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...);
1423}
1424
1425//===----------------------------------------------------------------------===//
1426// Extra additions to <algorithm>
1427//===----------------------------------------------------------------------===//
1428
1429// We have a copy here so that LLVM behaves the same when using different
1430// standard libraries.
1431template <class Iterator, class RNG>
1432void shuffle(Iterator first, Iterator last, RNG &&g) {
1433 // It would be better to use a std::uniform_int_distribution,
1434 // but that would be stdlib dependent.
1435 typedef
1436 typename std::iterator_traits<Iterator>::difference_type difference_type;
1437 for (auto size = last - first; size > 1; ++first, (void)--size) {
1438 difference_type offset = g() % size;
1439 // Avoid self-assignment due to incorrect assertions in libstdc++
1440 // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
1441 if (offset != difference_type(0))
1442 std::iter_swap(first, first + offset);
1443 }
1444}
1445
1446/// Adapt std::less<T> for array_pod_sort.
1447template<typename T>
1448inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1449 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1450 *reinterpret_cast<const T*>(P2)))
1451 return -1;
1452 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1453 *reinterpret_cast<const T*>(P1)))
1454 return 1;
1455 return 0;
1456}
1457
1458/// get_array_pod_sort_comparator - This is an internal helper function used to
1459/// get type deduction of T right.
1460template<typename T>
1461inline int (*get_array_pod_sort_comparator(const T &))
1462 (const void*, const void*) {
1463 return array_pod_sort_comparator<T>;
1464}
1465
1466#ifdef EXPENSIVE_CHECKS
1467namespace detail {
1468
1469inline unsigned presortShuffleEntropy() {
1470 static unsigned Result(std::random_device{}());
1471 return Result;
1472}
1473
1474template <class IteratorTy>
1475inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1476 std::mt19937 Generator(presortShuffleEntropy());
1477 llvm::shuffle(Start, End, Generator);
1478}
1479
1480} // end namespace detail
1481#endif
1482
1483/// array_pod_sort - This sorts an array with the specified start and end
1484/// extent. This is just like std::sort, except that it calls qsort instead of
1485/// using an inlined template. qsort is slightly slower than std::sort, but
1486/// most sorts are not performance critical in LLVM and std::sort has to be
1487/// template instantiated for each type, leading to significant measured code
1488/// bloat. This function should generally be used instead of std::sort where
1489/// possible.
1490///
1491/// This function assumes that you have simple POD-like types that can be
1492/// compared with std::less and can be moved with memcpy. If this isn't true,
1493/// you should use std::sort.
1494///
1495/// NOTE: If qsort_r were portable, we could allow a custom comparator and
1496/// default to std::less.
1497template<class IteratorTy>
1498inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1499 // Don't inefficiently call qsort with one element or trigger undefined
1500 // behavior with an empty sequence.
1501 auto NElts = End - Start;
1502 if (NElts <= 1) return;
1503#ifdef EXPENSIVE_CHECKS
1504 detail::presortShuffle<IteratorTy>(Start, End);
1505#endif
1506 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1507}
1508
1509template <class IteratorTy>
1510inline void array_pod_sort(
1511 IteratorTy Start, IteratorTy End,
1512 int (*Compare)(
1513 const typename std::iterator_traits<IteratorTy>::value_type *,
1514 const typename std::iterator_traits<IteratorTy>::value_type *)) {
1515 // Don't inefficiently call qsort with one element or trigger undefined
1516 // behavior with an empty sequence.
1517 auto NElts = End - Start;
1518 if (NElts <= 1) return;
1519#ifdef EXPENSIVE_CHECKS
1520 detail::presortShuffle<IteratorTy>(Start, End);
1521#endif
1522 qsort(&*Start, NElts, sizeof(*Start),
1523 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1524}
1525
1526namespace detail {
1527template <typename T>
1528// We can use qsort if the iterator type is a pointer and the underlying value
1529// is trivially copyable.
1530using sort_trivially_copyable = std::conjunction<
1531 std::is_pointer<T>,
1532 std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1533} // namespace detail
1534
1535// Provide wrappers to std::sort which shuffle the elements before sorting
1536// to help uncover non-deterministic behavior (PR35135).
1537template <typename IteratorTy>
1538inline void sort(IteratorTy Start, IteratorTy End) {
1539 if constexpr (detail::sort_trivially_copyable<IteratorTy>::value) {
1540 // Forward trivially copyable types to array_pod_sort. This avoids a large
1541 // amount of code bloat for a minor performance hit.
1542 array_pod_sort(Start, End);
1543 } else {
1544#ifdef EXPENSIVE_CHECKS
1545 detail::presortShuffle<IteratorTy>(Start, End);
1546#endif
1547 std::sort(Start, End);
1548 }
1549}
1550
1551template <typename Container> inline void sort(Container &&C) {
1552 llvm::sort(adl_begin(C), adl_end(C));
1553}
1554
1555template <typename IteratorTy, typename Compare>
1556inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1557#ifdef EXPENSIVE_CHECKS
1558 detail::presortShuffle<IteratorTy>(Start, End);
1559#endif
1560 std::sort(Start, End, Comp);
1561}
1562
1563template <typename Container, typename Compare>
1564inline void sort(Container &&C, Compare Comp) {
1565 llvm::sort(adl_begin(C), adl_end(C), Comp);
1566}
1567
1568/// Get the size of a range. This is a wrapper function around std::distance
1569/// which is only enabled when the operation is O(1).
1570template <typename R>
1571auto size(R &&Range,
1572 std::enable_if_t<
1573 std::is_base_of<std::random_access_iterator_tag,
1574 typename std::iterator_traits<decltype(
1575 Range.begin())>::iterator_category>::value,
1576 void> * = nullptr) {
1577 return std::distance(Range.begin(), Range.end());
1578}
1579
1580/// Provide wrappers to std::for_each which take ranges instead of having to
1581/// pass begin/end explicitly.
1582template <typename R, typename UnaryFunction>
1583UnaryFunction for_each(R &&Range, UnaryFunction F) {
1584 return std::for_each(adl_begin(Range), adl_end(Range), F);
1585}
1586
1587/// Provide wrappers to std::all_of which take ranges instead of having to pass
1588/// begin/end explicitly.
1589template <typename R, typename UnaryPredicate>
1590bool all_of(R &&Range, UnaryPredicate P) {
1591 return std::all_of(adl_begin(Range), adl_end(Range), P);
1592}
1593
1594/// Provide wrappers to std::any_of which take ranges instead of having to pass
1595/// begin/end explicitly.
1596template <typename R, typename UnaryPredicate>
1597bool any_of(R &&Range, UnaryPredicate P) {
1598 return std::any_of(adl_begin(Range), adl_end(Range), P);
3
Calling 'any_of<const llvm::MCOperand *, (lambda at /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp:305:27)>'
1599}
1600
1601/// Provide wrappers to std::none_of which take ranges instead of having to pass
1602/// begin/end explicitly.
1603template <typename R, typename UnaryPredicate>
1604bool none_of(R &&Range, UnaryPredicate P) {
1605 return std::none_of(adl_begin(Range), adl_end(Range), P);
1606}
1607
1608/// Provide wrappers to std::find which take ranges instead of having to pass
1609/// begin/end explicitly.
1610template <typename R, typename T> auto find(R &&Range, const T &Val) {
1611 return std::find(adl_begin(Range), adl_end(Range), Val);
1612}
1613
1614/// Provide wrappers to std::find_if which take ranges instead of having to pass
1615/// begin/end explicitly.
1616template <typename R, typename UnaryPredicate>
1617auto find_if(R &&Range, UnaryPredicate P) {
1618 return std::find_if(adl_begin(Range), adl_end(Range), P);
1619}
1620
1621template <typename R, typename UnaryPredicate>
1622auto find_if_not(R &&Range, UnaryPredicate P) {
1623 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1624}
1625
1626/// Provide wrappers to std::remove_if which take ranges instead of having to
1627/// pass begin/end explicitly.
1628template <typename R, typename UnaryPredicate>
1629auto remove_if(R &&Range, UnaryPredicate P) {
1630 return std::remove_if(adl_begin(Range), adl_end(Range), P);
1631}
1632
1633/// Provide wrappers to std::copy_if which take ranges instead of having to
1634/// pass begin/end explicitly.
1635template <typename R, typename OutputIt, typename UnaryPredicate>
1636OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1637 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1638}
1639
1640template <typename R, typename OutputIt>
1641OutputIt copy(R &&Range, OutputIt Out) {
1642 return std::copy(adl_begin(Range), adl_end(Range), Out);
1643}
1644
1645/// Provide wrappers to std::replace_copy_if which take ranges instead of having
1646/// to pass begin/end explicitly.
1647template <typename R, typename OutputIt, typename UnaryPredicate, typename T>
1648OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P,
1649 const T &NewValue) {
1650 return std::replace_copy_if(adl_begin(Range), adl_end(Range), Out, P,
1651 NewValue);
1652}
1653
1654/// Provide wrappers to std::replace_copy which take ranges instead of having to
1655/// pass begin/end explicitly.
1656template <typename R, typename OutputIt, typename T>
1657OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue,
1658 const T &NewValue) {
1659 return std::replace_copy(adl_begin(Range), adl_end(Range), Out, OldValue,
1660 NewValue);
1661}
1662
1663/// Provide wrappers to std::move which take ranges instead of having to
1664/// pass begin/end explicitly.
1665template <typename R, typename OutputIt>
1666OutputIt move(R &&Range, OutputIt Out) {
1667 return std::move(adl_begin(Range), adl_end(Range), Out);
1668}
1669
1670/// Wrapper function around std::find to detect if an element exists
1671/// in a container.
1672template <typename R, typename E>
1673bool is_contained(R &&Range, const E &Element) {
1674 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1675}
1676
1677template <typename T>
1678constexpr bool is_contained(std::initializer_list<T> Set, T Value) {
1679 // TODO: Use std::find when we switch to C++20.
1680 for (T V : Set)
1681 if (V == Value)
1682 return true;
1683 return false;
1684}
1685
1686/// Wrapper function around std::is_sorted to check if elements in a range \p R
1687/// are sorted with respect to a comparator \p C.
1688template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
1689 return std::is_sorted(adl_begin(Range), adl_end(Range), C);
1690}
1691
1692/// Wrapper function around std::is_sorted to check if elements in a range \p R
1693/// are sorted in non-descending order.
1694template <typename R> bool is_sorted(R &&Range) {
1695 return std::is_sorted(adl_begin(Range), adl_end(Range));
1696}
1697
1698/// Wrapper function around std::count to count the number of times an element
1699/// \p Element occurs in the given range \p Range.
1700template <typename R, typename E> auto count(R &&Range, const E &Element) {
1701 return std::count(adl_begin(Range), adl_end(Range), Element);
1702}
1703
1704/// Wrapper function around std::count_if to count the number of times an
1705/// element satisfying a given predicate occurs in a range.
1706template <typename R, typename UnaryPredicate>
1707auto count_if(R &&Range, UnaryPredicate P) {
1708 return std::count_if(adl_begin(Range), adl_end(Range), P);
1709}
1710
1711/// Wrapper function around std::transform to apply a function to a range and
1712/// store the result elsewhere.
1713template <typename R, typename OutputIt, typename UnaryFunction>
1714OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) {
1715 return std::transform(adl_begin(Range), adl_end(Range), d_first, F);
1716}
1717
1718/// Provide wrappers to std::partition which take ranges instead of having to
1719/// pass begin/end explicitly.
1720template <typename R, typename UnaryPredicate>
1721auto partition(R &&Range, UnaryPredicate P) {
1722 return std::partition(adl_begin(Range), adl_end(Range), P);
1723}
1724
1725/// Provide wrappers to std::lower_bound which take ranges instead of having to
1726/// pass begin/end explicitly.
1727template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
1728 return std::lower_bound(adl_begin(Range), adl_end(Range),
1729 std::forward<T>(Value));
1730}
1731
1732template <typename R, typename T, typename Compare>
1733auto lower_bound(R &&Range, T &&Value, Compare C) {
1734 return std::lower_bound(adl_begin(Range), adl_end(Range),
1735 std::forward<T>(Value), C);
1736}
1737
1738/// Provide wrappers to std::upper_bound which take ranges instead of having to
1739/// pass begin/end explicitly.
1740template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
1741 return std::upper_bound(adl_begin(Range), adl_end(Range),
1742 std::forward<T>(Value));
1743}
1744
1745template <typename R, typename T, typename Compare>
1746auto upper_bound(R &&Range, T &&Value, Compare C) {
1747 return std::upper_bound(adl_begin(Range), adl_end(Range),
1748 std::forward<T>(Value), C);
1749}
1750
1751template <typename R>
1752void stable_sort(R &&Range) {
1753 std::stable_sort(adl_begin(Range), adl_end(Range));
1754}
1755
1756template <typename R, typename Compare>
1757void stable_sort(R &&Range, Compare C) {
1758 std::stable_sort(adl_begin(Range), adl_end(Range), C);
1759}
1760
1761/// Binary search for the first iterator in a range where a predicate is false.
1762/// Requires that C is always true below some limit, and always false above it.
1763template <typename R, typename Predicate,
1764 typename Val = decltype(*adl_begin(std::declval<R>()))>
1765auto partition_point(R &&Range, Predicate P) {
1766 return std::partition_point(adl_begin(Range), adl_end(Range), P);
1767}
1768
1769template<typename Range, typename Predicate>
1770auto unique(Range &&R, Predicate P) {
1771 return std::unique(adl_begin(R), adl_end(R), P);
1772}
1773
1774/// Wrapper function around std::equal to detect if pair-wise elements between
1775/// two ranges are the same.
1776template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
1777 return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
1778 adl_end(RRange));
1779}
1780
1781/// Returns true if all elements in Range are equal or when the Range is empty.
1782template <typename R> bool all_equal(R &&Range) {
1783 auto Begin = adl_begin(Range);
1784 auto End = adl_end(Range);
1785 return Begin == End || std::equal(Begin + 1, End, Begin);
1786}
1787
1788/// Returns true if all Values in the initializer lists are equal or the list
1789// is empty.
1790template <typename T> bool all_equal(std::initializer_list<T> Values) {
1791 return all_equal<std::initializer_list<T>>(std::move(Values));
1792}
1793
1794/// Returns true if Range consists of the same value repeated multiple times.
1795template <typename R>
1796LLVM_DEPRECATED(__attribute__((deprecated("Use 'all_equal(Range)' or '!empty(Range) && all_equal(Range)' instead."
, "all_equal")))
1797 "Use 'all_equal(Range)' or '!empty(Range) && all_equal(Range)' instead.",__attribute__((deprecated("Use 'all_equal(Range)' or '!empty(Range) && all_equal(Range)' instead."
, "all_equal")))
1798 "all_equal")__attribute__((deprecated("Use 'all_equal(Range)' or '!empty(Range) && all_equal(Range)' instead."
, "all_equal")))
1799bool is_splat(R &&Range) {
1800 return !llvm::empty(Range) && all_equal(Range);
1801}
1802
1803/// Returns true if Values consists of the same value repeated multiple times.
1804template <typename T>
1805LLVM_DEPRECATED(__attribute__((deprecated("Use 'all_equal(Values)' or '!empty(Values) && all_equal(Values)' instead."
, "all_equal")))
1806 "Use 'all_equal(Values)' or '!empty(Values) && all_equal(Values)' instead.",__attribute__((deprecated("Use 'all_equal(Values)' or '!empty(Values) && all_equal(Values)' instead."
, "all_equal")))
1807 "all_equal")__attribute__((deprecated("Use 'all_equal(Values)' or '!empty(Values) && all_equal(Values)' instead."
, "all_equal")))
1808bool is_splat(std::initializer_list<T> Values) {
1809 return is_splat<std::initializer_list<T>>(std::move(Values));
1810}
1811
1812/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1813/// `erase_if` which is equivalent to:
1814///
1815/// C.erase(remove_if(C, pred), C.end());
1816///
1817/// This version works for any container with an erase method call accepting
1818/// two iterators.
1819template <typename Container, typename UnaryPredicate>
1820void erase_if(Container &C, UnaryPredicate P) {
1821 C.erase(remove_if(C, P), C.end());
1822}
1823
1824/// Wrapper function to remove a value from a container:
1825///
1826/// C.erase(remove(C.begin(), C.end(), V), C.end());
1827template <typename Container, typename ValueType>
1828void erase_value(Container &C, ValueType V) {
1829 C.erase(std::remove(C.begin(), C.end(), V), C.end());
1830}
1831
1832/// Wrapper function to append a range to a container.
1833///
1834/// C.insert(C.end(), R.begin(), R.end());
1835template <typename Container, typename Range>
1836inline void append_range(Container &C, Range &&R) {
1837 C.insert(C.end(), R.begin(), R.end());
1838}
1839
1840/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1841/// the range [ValIt, ValEnd) (which is not from the same container).
1842template<typename Container, typename RandomAccessIterator>
1843void replace(Container &Cont, typename Container::iterator ContIt,
1844 typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1845 RandomAccessIterator ValEnd) {
1846 while (true) {
1847 if (ValIt == ValEnd) {
1848 Cont.erase(ContIt, ContEnd);
1849 return;
1850 } else if (ContIt == ContEnd) {
1851 Cont.insert(ContIt, ValIt, ValEnd);
1852 return;
1853 }
1854 *ContIt++ = *ValIt++;
1855 }
1856}
1857
1858/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1859/// the range R.
1860template<typename Container, typename Range = std::initializer_list<
1861 typename Container::value_type>>
1862void replace(Container &Cont, typename Container::iterator ContIt,
1863 typename Container::iterator ContEnd, Range R) {
1864 replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1865}
1866
1867/// An STL-style algorithm similar to std::for_each that applies a second
1868/// functor between every pair of elements.
1869///
1870/// This provides the control flow logic to, for example, print a
1871/// comma-separated list:
1872/// \code
1873/// interleave(names.begin(), names.end(),
1874/// [&](StringRef name) { os << name; },
1875/// [&] { os << ", "; });
1876/// \endcode
1877template <typename ForwardIterator, typename UnaryFunctor,
1878 typename NullaryFunctor,
1879 typename = std::enable_if_t<
1880 !std::is_constructible<StringRef, UnaryFunctor>::value &&
1881 !std::is_constructible<StringRef, NullaryFunctor>::value>>
1882inline void interleave(ForwardIterator begin, ForwardIterator end,
1883 UnaryFunctor each_fn, NullaryFunctor between_fn) {
1884 if (begin == end)
1885 return;
1886 each_fn(*begin);
1887 ++begin;
1888 for (; begin != end; ++begin) {
1889 between_fn();
1890 each_fn(*begin);
1891 }
1892}
1893
1894template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
1895 typename = std::enable_if_t<
1896 !std::is_constructible<StringRef, UnaryFunctor>::value &&
1897 !std::is_constructible<StringRef, NullaryFunctor>::value>>
1898inline void interleave(const Container &c, UnaryFunctor each_fn,
1899 NullaryFunctor between_fn) {
1900 interleave(c.begin(), c.end(), each_fn, between_fn);
1901}
1902
1903/// Overload of interleave for the common case of string separator.
1904template <typename Container, typename UnaryFunctor, typename StreamT,
1905 typename T = detail::ValueOfRange<Container>>
1906inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
1907 const StringRef &separator) {
1908 interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
1909}
1910template <typename Container, typename StreamT,
1911 typename T = detail::ValueOfRange<Container>>
1912inline void interleave(const Container &c, StreamT &os,
1913 const StringRef &separator) {
1914 interleave(
1915 c, os, [&](const T &a) { os << a; }, separator);
1916}
1917
1918template <typename Container, typename UnaryFunctor, typename StreamT,
1919 typename T = detail::ValueOfRange<Container>>
1920inline void interleaveComma(const Container &c, StreamT &os,
1921 UnaryFunctor each_fn) {
1922 interleave(c, os, each_fn, ", ");
1923}
1924template <typename Container, typename StreamT,
1925 typename T = detail::ValueOfRange<Container>>
1926inline void interleaveComma(const Container &c, StreamT &os) {
1927 interleaveComma(c, os, [&](const T &a) { os << a; });
1928}
1929
1930//===----------------------------------------------------------------------===//
1931// Extra additions to <memory>
1932//===----------------------------------------------------------------------===//
1933
1934struct FreeDeleter {
1935 void operator()(void* v) {
1936 ::free(v);
1937 }
1938};
1939
1940template<typename First, typename Second>
1941struct pair_hash {
1942 size_t operator()(const std::pair<First, Second> &P) const {
1943 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1944 }
1945};
1946
1947/// Binary functor that adapts to any other binary functor after dereferencing
1948/// operands.
1949template <typename T> struct deref {
1950 T func;
1951
1952 // Could be further improved to cope with non-derivable functors and
1953 // non-binary functors (should be a variadic template member function
1954 // operator()).
1955 template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
1956 assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "llvm/include/llvm/ADT/STLExtras.h", 1956, __extension__ __PRETTY_FUNCTION__
))
;
1957 assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "llvm/include/llvm/ADT/STLExtras.h", 1957, __extension__ __PRETTY_FUNCTION__
))
;
1958 return func(*lhs, *rhs);
1959 }
1960};
1961
1962namespace detail {
1963
1964template <typename R> class enumerator_iter;
1965
1966template <typename R> struct result_pair {
1967 using value_reference =
1968 typename std::iterator_traits<IterOfRange<R>>::reference;
1969
1970 friend class enumerator_iter<R>;
1971
1972 result_pair() = default;
1973 result_pair(std::size_t Index, IterOfRange<R> Iter)
1974 : Index(Index), Iter(Iter) {}
1975
1976 result_pair(const result_pair<R> &Other)
1977 : Index(Other.Index), Iter(Other.Iter) {}
1978 result_pair &operator=(const result_pair &Other) {
1979 Index = Other.Index;
1980 Iter = Other.Iter;
1981 return *this;
1982 }
1983
1984 std::size_t index() const { return Index; }
1985 value_reference value() const { return *Iter; }
1986
1987private:
1988 std::size_t Index = std::numeric_limits<std::size_t>::max();
1989 IterOfRange<R> Iter;
1990};
1991
1992template <std::size_t i, typename R>
1993decltype(auto) get(const result_pair<R> &Pair) {
1994 static_assert(i < 2);
1995 if constexpr (i == 0) {
1996 return Pair.index();
1997 } else {
1998 return Pair.value();
1999 }
2000}
2001
2002template <typename R>
2003class enumerator_iter
2004 : public iterator_facade_base<enumerator_iter<R>, std::forward_iterator_tag,
2005 const result_pair<R>> {
2006 using result_type = result_pair<R>;
2007
2008public:
2009 explicit enumerator_iter(IterOfRange<R> EndIter)
2010 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
2011
2012 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
2013 : Result(Index, Iter) {}
2014
2015 const result_type &operator*() const { return Result; }
2016
2017 enumerator_iter &operator++() {
2018 assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "llvm/include/llvm/ADT/STLExtras.h", 2018, __extension__ __PRETTY_FUNCTION__
))
;
2019 ++Result.Iter;
2020 ++Result.Index;
2021 return *this;
2022 }
2023
2024 bool operator==(const enumerator_iter &RHS) const {
2025 // Don't compare indices here, only iterators. It's possible for an end
2026 // iterator to have different indices depending on whether it was created
2027 // by calling std::end() versus incrementing a valid iterator.
2028 return Result.Iter == RHS.Result.Iter;
2029 }
2030
2031 enumerator_iter(const enumerator_iter &Other) : Result(Other.Result) {}
2032 enumerator_iter &operator=(const enumerator_iter &Other) {
2033 Result = Other.Result;
2034 return *this;
2035 }
2036
2037private:
2038 result_type Result;
2039};
2040
2041template <typename R> class enumerator {
2042public:
2043 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
2044
2045 enumerator_iter<R> begin() {
2046 return enumerator_iter<R>(0, std::begin(TheRange));
2047 }
2048 enumerator_iter<R> begin() const {
2049 return enumerator_iter<R>(0, std::begin(TheRange));
2050 }
2051
2052 enumerator_iter<R> end() {
2053 return enumerator_iter<R>(std::end(TheRange));
2054 }
2055 enumerator_iter<R> end() const {
2056 return enumerator_iter<R>(std::end(TheRange));
2057 }
2058
2059private:
2060 R TheRange;
2061};
2062
2063} // end namespace detail
2064
2065/// Given an input range, returns a new range whose values are are pair (A,B)
2066/// such that A is the 0-based index of the item in the sequence, and B is
2067/// the value from the original sequence. Example:
2068///
2069/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
2070/// for (auto X : enumerate(Items)) {
2071/// printf("Item %d - %c\n", X.index(), X.value());
2072/// }
2073///
2074/// or using structured bindings:
2075///
2076/// for (auto [Index, Value] : enumerate(Items)) {
2077/// printf("Item %d - %c\n", Index, Value);
2078/// }
2079///
2080/// Output:
2081/// Item 0 - A
2082/// Item 1 - B
2083/// Item 2 - C
2084/// Item 3 - D
2085///
2086template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
2087 return detail::enumerator<R>(std::forward<R>(TheRange));
2088}
2089
2090namespace detail {
2091
2092template <typename Predicate, typename... Args>
2093bool all_of_zip_predicate_first(Predicate &&P, Args &&...args) {
2094 auto z = zip(args...);
2095 auto it = z.begin();
2096 auto end = z.end();
2097 while (it != end) {
2098 if (!std::apply([&](auto &&...args) { return P(args...); }, *it))
2099 return false;
2100 ++it;
2101 }
2102 return it.all_equals(end);
2103}
2104
2105// Just an adaptor to switch the order of argument and have the predicate before
2106// the zipped inputs.
2107template <typename... ArgsThenPredicate, size_t... InputIndexes>
2108bool all_of_zip_predicate_last(
2109 std::tuple<ArgsThenPredicate...> argsThenPredicate,
2110 std::index_sequence<InputIndexes...>) {
2111 auto constexpr OutputIndex =
2112 std::tuple_size<decltype(argsThenPredicate)>::value - 1;
2113 return all_of_zip_predicate_first(std::get<OutputIndex>(argsThenPredicate),
2114 std::get<InputIndexes>(argsThenPredicate)...);
2115}
2116
2117} // end namespace detail
2118
2119/// Compare two zipped ranges using the provided predicate (as last argument).
2120/// Return true if all elements satisfy the predicate and false otherwise.
2121// Return false if the zipped iterator aren't all at end (size mismatch).
2122template <typename... ArgsAndPredicate>
2123bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) {
2124 return detail::all_of_zip_predicate_last(
2125 std::forward_as_tuple(argsAndPredicate...),
2126 std::make_index_sequence<sizeof...(argsAndPredicate) - 1>{});
2127}
2128
2129/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
2130/// time. Not meant for use with random-access iterators.
2131/// Can optionally take a predicate to filter lazily some items.
2132template <typename IterTy,
2133 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2134bool hasNItems(
2135 IterTy &&Begin, IterTy &&End, unsigned N,
2136 Pred &&ShouldBeCounted =
2137 [](const decltype(*std::declval<IterTy>()) &) { return true; },
2138 std::enable_if_t<
2139 !std::is_base_of<std::random_access_iterator_tag,
2140 typename std::iterator_traits<std::remove_reference_t<
2141 decltype(Begin)>>::iterator_category>::value,
2142 void> * = nullptr) {
2143 for (; N; ++Begin) {
2144 if (Begin == End)
2145 return false; // Too few.
2146 N -= ShouldBeCounted(*Begin);
2147 }
2148 for (; Begin != End; ++Begin)
2149 if (ShouldBeCounted(*Begin))
2150 return false; // Too many.
2151 return true;
2152}
2153
2154/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
2155/// time. Not meant for use with random-access iterators.
2156/// Can optionally take a predicate to lazily filter some items.
2157template <typename IterTy,
2158 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2159bool hasNItemsOrMore(
2160 IterTy &&Begin, IterTy &&End, unsigned N,
2161 Pred &&ShouldBeCounted =
2162 [](const decltype(*std::declval<IterTy>()) &) { return true; },
2163 std::enable_if_t<
2164 !std::is_base_of<std::random_access_iterator_tag,
2165 typename std::iterator_traits<std::remove_reference_t<
2166 decltype(Begin)>>::iterator_category>::value,
2167 void> * = nullptr) {
2168 for (; N; ++Begin) {
2169 if (Begin == End)
2170 return false; // Too few.
2171 N -= ShouldBeCounted(*Begin);
2172 }
2173 return true;
2174}
2175
2176/// Returns true if the sequence [Begin, End) has N or less items. Can
2177/// optionally take a predicate to lazily filter some items.
2178template <typename IterTy,
2179 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2180bool hasNItemsOrLess(
2181 IterTy &&Begin, IterTy &&End, unsigned N,
2182 Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
2183 return true;
2184 }) {
2185 assert(N != std::numeric_limits<unsigned>::max())(static_cast <bool> (N != std::numeric_limits<unsigned
>::max()) ? void (0) : __assert_fail ("N != std::numeric_limits<unsigned>::max()"
, "llvm/include/llvm/ADT/STLExtras.h", 2185, __extension__ __PRETTY_FUNCTION__
))
;
2186 return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
2187}
2188
2189/// Returns true if the given container has exactly N items
2190template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
2191 return hasNItems(std::begin(C), std::end(C), N);
2192}
2193
2194/// Returns true if the given container has N or more items
2195template <typename ContainerTy>
2196bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
2197 return hasNItemsOrMore(std::begin(C), std::end(C), N);
2198}
2199
2200/// Returns true if the given container has N or less items
2201template <typename ContainerTy>
2202bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
2203 return hasNItemsOrLess(std::begin(C), std::end(C), N);
2204}
2205
2206/// Returns a raw pointer that represents the same address as the argument.
2207///
2208/// This implementation can be removed once we move to C++20 where it's defined
2209/// as std::to_address().
2210///
2211/// The std::pointer_traits<>::to_address(p) variations of these overloads has
2212/// not been implemented.
2213template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
2214template <class T> constexpr T *to_address(T *P) { return P; }
2215
2216} // end namespace llvm
2217
2218namespace std {
2219template <typename R>
2220struct tuple_size<llvm::detail::result_pair<R>>
2221 : std::integral_constant<std::size_t, 2> {};
2222
2223template <std::size_t i, typename R>
2224struct tuple_element<i, llvm::detail::result_pair<R>>
2225 : std::conditional<i == 0, std::size_t,
2226 typename llvm::detail::result_pair<R>::value_reference> {
2227};
2228
2229} // namespace std
2230
2231#endif // LLVM_ADT_STLEXTRAS_H

/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_algo.h

1// Algorithm implementation -*- C++ -*-
2
3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_algo.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{algorithm}
54 */
55
56#ifndef _STL_ALGO_H1
57#define _STL_ALGO_H1 1
58
59#include <cstdlib> // for rand
60#include <bits/algorithmfwd.h>
61#include <bits/stl_heap.h>
62#include <bits/stl_tempbuf.h> // for _Temporary_buffer
63#include <bits/predefined_ops.h>
64
65#if __cplusplus201703L >= 201103L
66#include <bits/uniform_int_dist.h>
67#endif
68
69// See concept_check.h for the __glibcxx_*_requires macros.
70
71namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
72{
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
74
75 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76 template<typename _Iterator, typename _Compare>
77 _GLIBCXX20_CONSTEXPR
78 void
79 __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
80 _Iterator __c, _Compare __comp)
81 {
82 if (__comp(__a, __b))
83 {
84 if (__comp(__b, __c))
85 std::iter_swap(__result, __b);
86 else if (__comp(__a, __c))
87 std::iter_swap(__result, __c);
88 else
89 std::iter_swap(__result, __a);
90 }
91 else if (__comp(__a, __c))
92 std::iter_swap(__result, __a);
93 else if (__comp(__b, __c))
94 std::iter_swap(__result, __c);
95 else
96 std::iter_swap(__result, __b);
97 }
98
99 /// Provided for stable_partition to use.
100 template<typename _InputIterator, typename _Predicate>
101 _GLIBCXX20_CONSTEXPR
102 inline _InputIterator
103 __find_if_not(_InputIterator __first, _InputIterator __last,
104 _Predicate __pred)
105 {
106 return std::__find_if(__first, __last,
107 __gnu_cxx::__ops::__negate(__pred),
108 std::__iterator_category(__first));
109 }
110
111 /// Like find_if_not(), but uses and updates a count of the
112 /// remaining range length instead of comparing against an end
113 /// iterator.
114 template<typename _InputIterator, typename _Predicate, typename _Distance>
115 _GLIBCXX20_CONSTEXPR
116 _InputIterator
117 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
118 {
119 for (; __len; --__len, (void) ++__first)
120 if (!__pred(__first))
121 break;
122 return __first;
123 }
124
125 // set_difference
126 // set_intersection
127 // set_symmetric_difference
128 // set_union
129 // for_each
130 // find
131 // find_if
132 // find_first_of
133 // adjacent_find
134 // count
135 // count_if
136 // search
137
138 template<typename _ForwardIterator1, typename _ForwardIterator2,
139 typename _BinaryPredicate>
140 _GLIBCXX20_CONSTEXPR
141 _ForwardIterator1
142 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
143 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
144 _BinaryPredicate __predicate)
145 {
146 // Test for empty ranges
147 if (__first1 == __last1 || __first2 == __last2)
148 return __first1;
149
150 // Test for a pattern of length 1.
151 _ForwardIterator2 __p1(__first2);
152 if (++__p1 == __last2)
153 return std::__find_if(__first1, __last1,
154 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
155
156 // General case.
157 _ForwardIterator1 __current = __first1;
158
159 for (;;)
160 {
161 __first1 =
162 std::__find_if(__first1, __last1,
163 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
164
165 if (__first1 == __last1)
166 return __last1;
167
168 _ForwardIterator2 __p = __p1;
169 __current = __first1;
170 if (++__current == __last1)
171 return __last1;
172
173 while (__predicate(__current, __p))
174 {
175 if (++__p == __last2)
176 return __first1;
177 if (++__current == __last1)
178 return __last1;
179 }
180 ++__first1;
181 }
182 return __first1;
183 }
184
185 // search_n
186
187 /**
188 * This is an helper function for search_n overloaded for forward iterators.
189 */
190 template<typename _ForwardIterator, typename _Integer,
191 typename _UnaryPredicate>
192 _GLIBCXX20_CONSTEXPR
193 _ForwardIterator
194 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
195 _Integer __count, _UnaryPredicate __unary_pred,
196 std::forward_iterator_tag)
197 {
198 __first = std::__find_if(__first, __last, __unary_pred);
199 while (__first != __last)
200 {
201 typename iterator_traits<_ForwardIterator>::difference_type
202 __n = __count;
203 _ForwardIterator __i = __first;
204 ++__i;
205 while (__i != __last && __n != 1 && __unary_pred(__i))
206 {
207 ++__i;
208 --__n;
209 }
210 if (__n == 1)
211 return __first;
212 if (__i == __last)
213 return __last;
214 __first = std::__find_if(++__i, __last, __unary_pred);
215 }
216 return __last;
217 }
218
219 /**
220 * This is an helper function for search_n overloaded for random access
221 * iterators.
222 */
223 template<typename _RandomAccessIter, typename _Integer,
224 typename _UnaryPredicate>
225 _GLIBCXX20_CONSTEXPR
226 _RandomAccessIter
227 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
228 _Integer __count, _UnaryPredicate __unary_pred,
229 std::random_access_iterator_tag)
230 {
231 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
232 _DistanceType;
233
234 _DistanceType __tailSize = __last - __first;
235 _DistanceType __remainder = __count;
236
237 while (__remainder <= __tailSize) // the main loop...
238 {
239 __first += __remainder;
240 __tailSize -= __remainder;
241 // __first here is always pointing to one past the last element of
242 // next possible match.
243 _RandomAccessIter __backTrack = __first;
244 while (__unary_pred(--__backTrack))
245 {
246 if (--__remainder == 0)
247 return (__first - __count); // Success
248 }
249 __remainder = __count + 1 - (__first - __backTrack);
250 }
251 return __last; // Failure
252 }
253
254 template<typename _ForwardIterator, typename _Integer,
255 typename _UnaryPredicate>
256 _GLIBCXX20_CONSTEXPR
257 _ForwardIterator
258 __search_n(_ForwardIterator __first, _ForwardIterator __last,
259 _Integer __count,
260 _UnaryPredicate __unary_pred)
261 {
262 if (__count <= 0)
263 return __first;
264
265 if (__count == 1)
266 return std::__find_if(__first, __last, __unary_pred);
267
268 return std::__search_n_aux(__first, __last, __count, __unary_pred,
269 std::__iterator_category(__first));
270 }
271
272 // find_end for forward iterators.
273 template<typename _ForwardIterator1, typename _ForwardIterator2,
274 typename _BinaryPredicate>
275 _GLIBCXX20_CONSTEXPR
276 _ForwardIterator1
277 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
278 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
279 forward_iterator_tag, forward_iterator_tag,
280 _BinaryPredicate __comp)
281 {
282 if (__first2 == __last2)
283 return __last1;
284
285 _ForwardIterator1 __result = __last1;
286 while (1)
287 {
288 _ForwardIterator1 __new_result
289 = std::__search(__first1, __last1, __first2, __last2, __comp);
290 if (__new_result == __last1)
291 return __result;
292 else
293 {
294 __result = __new_result;
295 __first1 = __new_result;
296 ++__first1;
297 }
298 }
299 }
300
301 // find_end for bidirectional iterators (much faster).
302 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
303 typename _BinaryPredicate>
304 _GLIBCXX20_CONSTEXPR
305 _BidirectionalIterator1
306 __find_end(_BidirectionalIterator1 __first1,
307 _BidirectionalIterator1 __last1,
308 _BidirectionalIterator2 __first2,
309 _BidirectionalIterator2 __last2,
310 bidirectional_iterator_tag, bidirectional_iterator_tag,
311 _BinaryPredicate __comp)
312 {
313 // concept requirements
314 __glibcxx_function_requires(_BidirectionalIteratorConcept<
315 _BidirectionalIterator1>)
316 __glibcxx_function_requires(_BidirectionalIteratorConcept<
317 _BidirectionalIterator2>)
318
319 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
320 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
321
322 _RevIterator1 __rlast1(__first1);
323 _RevIterator2 __rlast2(__first2);
324 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
325 _RevIterator2(__last2), __rlast2,
326 __comp);
327
328 if (__rresult == __rlast1)
329 return __last1;
330 else
331 {
332 _BidirectionalIterator1 __result = __rresult.base();
333 std::advance(__result, -std::distance(__first2, __last2));
334 return __result;
335 }
336 }
337
338 /**
339 * @brief Find last matching subsequence in a sequence.
340 * @ingroup non_mutating_algorithms
341 * @param __first1 Start of range to search.
342 * @param __last1 End of range to search.
343 * @param __first2 Start of sequence to match.
344 * @param __last2 End of sequence to match.
345 * @return The last iterator @c i in the range
346 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
347 * @p *(__first2+N) for each @c N in the range @p
348 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
349 *
350 * Searches the range @p [__first1,__last1) for a sub-sequence that
351 * compares equal value-by-value with the sequence given by @p
352 * [__first2,__last2) and returns an iterator to the __first
353 * element of the sub-sequence, or @p __last1 if the sub-sequence
354 * is not found. The sub-sequence will be the last such
355 * subsequence contained in [__first1,__last1).
356 *
357 * Because the sub-sequence must lie completely within the range @p
358 * [__first1,__last1) it must start at a position less than @p
359 * __last1-(__last2-__first2) where @p __last2-__first2 is the
360 * length of the sub-sequence. This means that the returned
361 * iterator @c i will be in the range @p
362 * [__first1,__last1-(__last2-__first2))
363 */
364 template<typename _ForwardIterator1, typename _ForwardIterator2>
365 _GLIBCXX20_CONSTEXPR
366 inline _ForwardIterator1
367 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
368 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
369 {
370 // concept requirements
371 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
372 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
373 __glibcxx_function_requires(_EqualOpConcept<
374 typename iterator_traits<_ForwardIterator1>::value_type,
375 typename iterator_traits<_ForwardIterator2>::value_type>)
376 __glibcxx_requires_valid_range(__first1, __last1);
377 __glibcxx_requires_valid_range(__first2, __last2);
378
379 return std::__find_end(__first1, __last1, __first2, __last2,
380 std::__iterator_category(__first1),
381 std::__iterator_category(__first2),
382 __gnu_cxx::__ops::__iter_equal_to_iter());
383 }
384
385 /**
386 * @brief Find last matching subsequence in a sequence using a predicate.
387 * @ingroup non_mutating_algorithms
388 * @param __first1 Start of range to search.
389 * @param __last1 End of range to search.
390 * @param __first2 Start of sequence to match.
391 * @param __last2 End of sequence to match.
392 * @param __comp The predicate to use.
393 * @return The last iterator @c i in the range @p
394 * [__first1,__last1-(__last2-__first2)) such that @c
395 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
396 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
397 * exists.
398 *
399 * Searches the range @p [__first1,__last1) for a sub-sequence that
400 * compares equal value-by-value with the sequence given by @p
401 * [__first2,__last2) using comp as a predicate and returns an
402 * iterator to the first element of the sub-sequence, or @p __last1
403 * if the sub-sequence is not found. The sub-sequence will be the
404 * last such subsequence contained in [__first,__last1).
405 *
406 * Because the sub-sequence must lie completely within the range @p
407 * [__first1,__last1) it must start at a position less than @p
408 * __last1-(__last2-__first2) where @p __last2-__first2 is the
409 * length of the sub-sequence. This means that the returned
410 * iterator @c i will be in the range @p
411 * [__first1,__last1-(__last2-__first2))
412 */
413 template<typename _ForwardIterator1, typename _ForwardIterator2,
414 typename _BinaryPredicate>
415 _GLIBCXX20_CONSTEXPR
416 inline _ForwardIterator1
417 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
418 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
419 _BinaryPredicate __comp)
420 {
421 // concept requirements
422 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
423 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
424 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
425 typename iterator_traits<_ForwardIterator1>::value_type,
426 typename iterator_traits<_ForwardIterator2>::value_type>)
427 __glibcxx_requires_valid_range(__first1, __last1);
428 __glibcxx_requires_valid_range(__first2, __last2);
429
430 return std::__find_end(__first1, __last1, __first2, __last2,
431 std::__iterator_category(__first1),
432 std::__iterator_category(__first2),
433 __gnu_cxx::__ops::__iter_comp_iter(__comp));
434 }
435
436#if __cplusplus201703L >= 201103L
437 /**
438 * @brief Checks that a predicate is true for all the elements
439 * of a sequence.
440 * @ingroup non_mutating_algorithms
441 * @param __first An input iterator.
442 * @param __last An input iterator.
443 * @param __pred A predicate.
444 * @return True if the check is true, false otherwise.
445 *
446 * Returns true if @p __pred is true for each element in the range
447 * @p [__first,__last), and false otherwise.
448 */
449 template<typename _InputIterator, typename _Predicate>
450 _GLIBCXX20_CONSTEXPR
451 inline bool
452 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
453 { return __last == std::find_if_not(__first, __last, __pred); }
454
455 /**
456 * @brief Checks that a predicate is false for all the elements
457 * of a sequence.
458 * @ingroup non_mutating_algorithms
459 * @param __first An input iterator.
460 * @param __last An input iterator.
461 * @param __pred A predicate.
462 * @return True if the check is true, false otherwise.
463 *
464 * Returns true if @p __pred is false for each element in the range
465 * @p [__first,__last), and false otherwise.
466 */
467 template<typename _InputIterator, typename _Predicate>
468 _GLIBCXX20_CONSTEXPR
469 inline bool
470 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
471 { return __last == _GLIBCXX_STD_Astd::find_if(__first, __last, __pred); }
5
Calling 'find_if<const llvm::MCOperand *, (lambda at /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp:305:27)>'
472
473 /**
474 * @brief Checks that a predicate is true for at least one element
475 * of a sequence.
476 * @ingroup non_mutating_algorithms
477 * @param __first An input iterator.
478 * @param __last An input iterator.
479 * @param __pred A predicate.
480 * @return True if the check is true, false otherwise.
481 *
482 * Returns true if an element exists in the range @p
483 * [__first,__last) such that @p __pred is true, and false
484 * otherwise.
485 */
486 template<typename _InputIterator, typename _Predicate>
487 _GLIBCXX20_CONSTEXPR
488 inline bool
489 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
490 { return !std::none_of(__first, __last, __pred); }
4
Calling 'none_of<const llvm::MCOperand *, (lambda at /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Target/AArch64/MCTargetDesc/AArch64MCTargetDesc.cpp:305:27)>'
491
492 /**
493 * @brief Find the first element in a sequence for which a
494 * predicate is false.
495 * @ingroup non_mutating_algorithms
496 * @param __first An input iterator.
497 * @param __last An input iterator.
498 * @param __pred A predicate.
499 * @return The first iterator @c i in the range @p [__first,__last)
500 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
501 */
502 template<typename _InputIterator, typename _Predicate>
503 _GLIBCXX20_CONSTEXPR
504 inline _InputIterator
505 find_if_not(_InputIterator __first, _InputIterator __last,
506 _Predicate __pred)
507 {
508 // concept requirements
509 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
510 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
511 typename iterator_traits<_InputIterator>::value_type>)
512 __glibcxx_requires_valid_range(__first, __last);
513 return std::__find_if_not(__first, __last,
514 __gnu_cxx::__ops::__pred_iter(__pred));
515 }
516
517 /**
518 * @brief Checks whether the sequence is partitioned.
519 * @ingroup mutating_algorithms
520 * @param __first An input iterator.
521 * @param __last An input iterator.
522 * @param __pred A predicate.
523 * @return True if the range @p [__first,__last) is partioned by @p __pred,
524 * i.e. if all elements that satisfy @p __pred appear before those that
525 * do not.
526 */
527 template<typename _InputIterator, typename _Predicate>
528 _GLIBCXX20_CONSTEXPR
529 inline bool
530 is_partitioned(_InputIterator __first, _InputIterator __last,
531 _Predicate __pred)
532 {
533 __first = std::find_if_not(__first, __last, __pred);
534 if (__first == __last)
535 return true;
536 ++__first;
537 return std::none_of(__first, __last, __pred);
538 }
539
540 /**
541 * @brief Find the partition point of a partitioned range.
542 * @ingroup mutating_algorithms
543 * @param __first An iterator.
544 * @param __last Another iterator.
545 * @param __pred A predicate.
546 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
547 * and @p none_of(mid, __last, __pred) are both true.
548 */
549 template<typename _ForwardIterator, typename _Predicate>
550 _GLIBCXX20_CONSTEXPR
551 _ForwardIterator
552 partition_point(_ForwardIterator __first, _ForwardIterator __last,
553 _Predicate __pred)
554 {
555 // concept requirements
556 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
557 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
558 typename iterator_traits<_ForwardIterator>::value_type>)
559
560 // A specific debug-mode test will be necessary...
561 __glibcxx_requires_valid_range(__first, __last);
562
563 typedef typename iterator_traits<_ForwardIterator>::difference_type
564 _DistanceType;
565
566 _DistanceType __len = std::distance(__first, __last);
567
568 while (__len > 0)
569 {
570 _DistanceType __half = __len >> 1;
571 _ForwardIterator __middle = __first;
572 std::advance(__middle, __half);
573 if (__pred(*__middle))
574 {
575 __first = __middle;
576 ++__first;
577 __len = __len - __half - 1;
578 }
579 else
580 __len = __half;
581 }
582 return __first;
583 }
584#endif
585
586 template<typename _InputIterator, typename _OutputIterator,
587 typename _Predicate>
588 _GLIBCXX20_CONSTEXPR
589 _OutputIterator
590 __remove_copy_if(_InputIterator __first, _InputIterator __last,
591 _OutputIterator __result, _Predicate __pred)
592 {
593 for (; __first != __last; ++__first)
594 if (!__pred(__first))
595 {
596 *__result = *__first;
597 ++__result;
598 }
599 return __result;
600 }
601
602 /**
603 * @brief Copy a sequence, removing elements of a given value.
604 * @ingroup mutating_algorithms
605 * @param __first An input iterator.
606 * @param __last An input iterator.
607 * @param __result An output iterator.
608 * @param __value The value to be removed.
609 * @return An iterator designating the end of the resulting sequence.
610 *
611 * Copies each element in the range @p [__first,__last) not equal
612 * to @p __value to the range beginning at @p __result.
613 * remove_copy() is stable, so the relative order of elements that
614 * are copied is unchanged.
615 */
616 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
617 _GLIBCXX20_CONSTEXPR
618 inline _OutputIterator
619 remove_copy(_InputIterator __first, _InputIterator __last,
620 _OutputIterator __result, const _Tp& __value)
621 {
622 // concept requirements
623 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
624 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
625 typename iterator_traits<_InputIterator>::value_type>)
626 __glibcxx_function_requires(_EqualOpConcept<
627 typename iterator_traits<_InputIterator>::value_type, _Tp>)
628 __glibcxx_requires_valid_range(__first, __last);
629
630 return std::__remove_copy_if(__first, __last, __result,
631 __gnu_cxx::__ops::__iter_equals_val(__value));
632 }
633
634 /**
635 * @brief Copy a sequence, removing elements for which a predicate is true.
636 * @ingroup mutating_algorithms
637 * @param __first An input iterator.
638 * @param __last An input iterator.
639 * @param __result An output iterator.
640 * @param __pred A predicate.
641 * @return An iterator designating the end of the resulting sequence.
642 *
643 * Copies each element in the range @p [__first,__last) for which
644 * @p __pred returns false to the range beginning at @p __result.
645 *
646 * remove_copy_if() is stable, so the relative order of elements that are
647 * copied is unchanged.
648 */
649 template<typename _InputIterator, typename _OutputIterator,
650 typename _Predicate>
651 _GLIBCXX20_CONSTEXPR
652 inline _OutputIterator
653 remove_copy_if(_InputIterator __first, _InputIterator __last,
654 _OutputIterator __result, _Predicate __pred)
655 {
656 // concept requirements
657 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
658 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
659 typename iterator_traits<_InputIterator>::value_type>)
660 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
661 typename iterator_traits<_InputIterator>::value_type>)
662 __glibcxx_requires_valid_range(__first, __last);
663
664 return std::__remove_copy_if(__first, __last, __result,
665 __gnu_cxx::__ops::__pred_iter(__pred));
666 }
667
668#if __cplusplus201703L >= 201103L
669 /**
670 * @brief Copy the elements of a sequence for which a predicate is true.
671 * @ingroup mutating_algorithms
672 * @param __first An input iterator.
673 * @param __last An input iterator.
674 * @param __result An output iterator.
675 * @param __pred A predicate.
676 * @return An iterator designating the end of the resulting sequence.
677 *
678 * Copies each element in the range @p [__first,__last) for which
679 * @p __pred returns true to the range beginning at @p __result.
680 *
681 * copy_if() is stable, so the relative order of elements that are
682 * copied is unchanged.
683 */
684 template<typename _InputIterator, typename _OutputIterator,
685 typename _Predicate>
686 _GLIBCXX20_CONSTEXPR
687 _OutputIterator
688 copy_if(_InputIterator __first, _InputIterator __last,
689 _OutputIterator __result, _Predicate __pred)
690 {
691 // concept requirements
692 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
693 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
694 typename iterator_traits<_InputIterator>::value_type>)
695 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
696 typename iterator_traits<_InputIterator>::value_type>)
697 __glibcxx_requires_valid_range(__first, __last);
698
699 for (; __first != __last; ++__first)
700 if (__pred(*__first))
701 {
702 *__result = *__first;
703 ++__result;
704 }
705 return __result;
706 }
707
708 template<typename _InputIterator, typename _Size, typename _OutputIterator>
709 _GLIBCXX20_CONSTEXPR
710 _OutputIterator
711 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
712 {
713 if (__n > 0)
714 {
715 while (true)
716 {
717 *__result = *__first;
718 ++__result;
719 if (--__n > 0)
720 ++__first;
721 else
722 break;
723 }
724 }
725 return __result;
726 }
727
728 template<typename _CharT, typename _Size>
729 __enable_if_t<__is_char<_CharT>::__value, _CharT*>
730 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
731 _Size, _CharT*);
732
733 template<typename _InputIterator, typename _Size, typename _OutputIterator>
734 _GLIBCXX20_CONSTEXPR
735 _OutputIterator
736 __copy_n(_InputIterator __first, _Size __n,
737 _OutputIterator __result, input_iterator_tag)
738 {
739 return std::__niter_wrap(__result,
740 __copy_n_a(__first, __n,
741 std::__niter_base(__result)));
742 }
743
744 template<typename _RandomAccessIterator, typename _Size,
745 typename _OutputIterator>
746 _GLIBCXX20_CONSTEXPR
747 inline _OutputIterator
748 __copy_n(_RandomAccessIterator __first, _Size __n,
749 _OutputIterator __result, random_access_iterator_tag)
750 { return std::copy(__first, __first + __n, __result); }
751
752 /**
753 * @brief Copies the range [first,first+n) into [result,result+n).
754 * @ingroup mutating_algorithms
755 * @param __first An input iterator.
756 * @param __n The number of elements to copy.
757 * @param __result An output iterator.
758 * @return result+n.
759 *
760 * This inline function will boil down to a call to @c memmove whenever
761 * possible. Failing that, if random access iterators are passed, then the
762 * loop count will be known (and therefore a candidate for compiler
763 * optimizations such as unrolling).
764 */
765 template<typename _InputIterator, typename _Size, typename _OutputIterator>
766 _GLIBCXX20_CONSTEXPR
767 inline _OutputIterator
768 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
769 {
770 // concept requirements
771 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
772 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
773 typename iterator_traits<_InputIterator>::value_type>)
774 __glibcxx_requires_can_increment(__first, __n);
775 __glibcxx_requires_can_increment(__result, __n);
776
777 return std::__copy_n(__first, __n, __result,
778 std::__iterator_category(__first));
779 }
780
781 /**
782 * @brief Copy the elements of a sequence to separate output sequences
783 * depending on the truth value of a predicate.
784 * @ingroup mutating_algorithms
785 * @param __first An input iterator.
786 * @param __last An input iterator.
787 * @param __out_true An output iterator.
788 * @param __out_false An output iterator.
789 * @param __pred A predicate.
790 * @return A pair designating the ends of the resulting sequences.
791 *
792 * Copies each element in the range @p [__first,__last) for which
793 * @p __pred returns true to the range beginning at @p out_true
794 * and each element for which @p __pred returns false to @p __out_false.
795 */
796 template<typename _InputIterator, typename _OutputIterator1,
797 typename _OutputIterator2, typename _Predicate>
798 _GLIBCXX20_CONSTEXPR
799 pair<_OutputIterator1, _OutputIterator2>
800 partition_copy(_InputIterator __first, _InputIterator __last,
801 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
802 _Predicate __pred)
803 {
804 // concept requirements
805 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
806 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
807 typename iterator_traits<_InputIterator>::value_type>)
808 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
809 typename iterator_traits<_InputIterator>::value_type>)
810 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
811 typename iterator_traits<_InputIterator>::value_type>)
812 __glibcxx_requires_valid_range(__first, __last);
813
814 for (; __first != __last; ++__first)
815 if (__pred(*__first))
816 {
817 *__out_true = *__first;
818 ++__out_true;
819 }
820 else
821 {
822 *__out_false = *__first;
823 ++__out_false;
824 }
825
826 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
827 }
828#endif // C++11
829
830 template<typename _ForwardIterator, typename _Predicate>
831 _GLIBCXX20_CONSTEXPR
832 _ForwardIterator
833 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
834 _Predicate __pred)
835 {
836 __first = std::__find_if(__first, __last, __pred);
837 if (__first == __last)
838 return __first;
839 _ForwardIterator __result = __first;
840 ++__first;
841 for (; __first != __last; ++__first)
842 if (!__pred(__first))
843 {
844 *__result = _GLIBCXX_MOVE(*__first)std::move(*__first);
845 ++__result;
846 }
847 return __result;
848 }
849
850 /**
851 * @brief Remove elements from a sequence.
852 * @ingroup mutating_algorithms
853 * @param __first An input iterator.
854 * @param __last An input iterator.
855 * @param __value The value to be removed.
856 * @return An iterator designating the end of the resulting sequence.
857 *
858 * All elements equal to @p __value are removed from the range
859 * @p [__first,__last).
860 *
861 * remove() is stable, so the relative order of elements that are
862 * not removed is unchanged.
863 *
864 * Elements between the end of the resulting sequence and @p __last
865 * are still present, but their value is unspecified.
866 */
867 template<typename _ForwardIterator, typename _Tp>
868 _GLIBCXX20_CONSTEXPR
869 inline _ForwardIterator
870 remove(_ForwardIterator __first, _ForwardIterator __last,
871 const _Tp& __value)
872 {
873 // concept requirements
874 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
875 _ForwardIterator>)
876 __glibcxx_function_requires(_EqualOpConcept<
877 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
878 __glibcxx_requires_valid_range(__first, __last);
879
880 return std::__remove_if(__first, __last,
881 __gnu_cxx::__ops::__iter_equals_val(__value));
882 }
883
884 /**
885 * @brief Remove elements from a sequence using a predicate.
886 * @ingroup mutating_algorithms
887 * @param __first A forward iterator.
888 * @param __last A forward iterator.
889 * @param __pred A predicate.
890 * @return An iterator designating the end of the resulting sequence.
891 *
892 * All elements for which @p __pred returns true are removed from the range
893 * @p [__first,__last).
894 *
895 * remove_if() is stable, so the relative order of elements that are
896 * not removed is unchanged.
897 *
898 * Elements between the end of the resulting sequence and @p __last
899 * are still present, but their value is unspecified.
900 */
901 template<typename _ForwardIterator, typename _Predicate>
902 _GLIBCXX20_CONSTEXPR
903 inline _ForwardIterator
904 remove_if(_ForwardIterator __first, _ForwardIterator __last,
905 _Predicate __pred)
906 {
907 // concept requirements
908 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
909 _ForwardIterator>)
910 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
911 typename iterator_traits<_ForwardIterator>::value_type>)
912 __glibcxx_requires_valid_range(__first, __last);
913
914 return std::__remove_if(__first, __last,
915 __gnu_cxx::__ops::__pred_iter(__pred));
916 }
917
918 template<typename _ForwardIterator, typename _BinaryPredicate>
919 _GLIBCXX20_CONSTEXPR
920 _ForwardIterator
921 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
922 _BinaryPredicate __binary_pred)
923 {
924 if (__first == __last)
925 return __last;
926 _ForwardIterator __next = __first;
927 while (++__next != __last)
928 {
929 if (__binary_pred(__first, __next))
930 return __first;
931 __first = __next;
932 }
933 return __last;
934 }
935
936 template<typename _ForwardIterator, typename _BinaryPredicate>
937 _GLIBCXX20_CONSTEXPR
938 _ForwardIterator
939 __unique(_ForwardIterator __first, _ForwardIterator __last,
940 _BinaryPredicate __binary_pred)
941 {
942 // Skip the beginning, if already unique.
943 __first = std::__adjacent_find(__first, __last, __binary_pred);
944 if (__first == __last)
945 return __last;
946
947 // Do the real copy work.
948 _ForwardIterator __dest = __first;
949 ++__first;
950 while (++__first != __last)
951 if (!__binary_pred(__dest, __first))
952 *++__dest = _GLIBCXX_MOVE(*__first)std::move(*__first);
953 return ++__dest;
954 }
955
956 /**
957 * @brief Remove consecutive duplicate values from a sequence.
958 * @ingroup mutating_algorithms
959 * @param __first A forward iterator.
960 * @param __last A forward iterator.
961 * @return An iterator designating the end of the resulting sequence.
962 *
963 * Removes all but the first element from each group of consecutive
964 * values that compare equal.
965 * unique() is stable, so the relative order of elements that are
966 * not removed is unchanged.
967 * Elements between the end of the resulting sequence and @p __last
968 * are still present, but their value is unspecified.
969 */
970 template<typename _ForwardIterator>
971 _GLIBCXX20_CONSTEXPR
972 inline _ForwardIterator
973 unique(_ForwardIterator __first, _ForwardIterator __last)
974 {
975 // concept requirements
976 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
977 _ForwardIterator>)
978 __glibcxx_function_requires(_EqualityComparableConcept<
979 typename iterator_traits<_ForwardIterator>::value_type>)
980 __glibcxx_requires_valid_range(__first, __last);
981
982 return std::__unique(__first, __last,
983 __gnu_cxx::__ops::__iter_equal_to_iter());
984 }
985
986 /**
987 * @brief Remove consecutive values from a sequence using a predicate.
988 * @ingroup mutating_algorithms
989 * @param __first A forward iterator.
990 * @param __last A forward iterator.
991 * @param __binary_pred A binary predicate.
992 * @return An iterator designating the end of the resulting sequence.
993 *
994 * Removes all but the first element from each group of consecutive
995 * values for which @p __binary_pred returns true.
996 * unique() is stable, so the relative order of elements that are
997 * not removed is unchanged.
998 * Elements between the end of the resulting sequence and @p __last
999 * are still present, but their value is unspecified.
1000 */
1001 template<typename _ForwardIterator, typename _BinaryPredicate>
1002 _GLIBCXX20_CONSTEXPR
1003 inline _ForwardIterator
1004 unique(_ForwardIterator __first, _ForwardIterator __last,
1005 _BinaryPredicate __binary_pred)
1006 {
1007 // concept requirements
1008 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1009 _ForwardIterator>)
1010 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1011 typename iterator_traits<_ForwardIterator>::value_type,
1012 typename iterator_traits<_ForwardIterator>::value_type>)
1013 __glibcxx_requires_valid_range(__first, __last);
1014
1015 return std::__unique(__first, __last,
1016 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1017 }
1018
1019 /**
1020 * This is an uglified
1021 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1022 * _BinaryPredicate)
1023 * overloaded for forward iterators and output iterator as result.
1024 */
1025 template<typename _ForwardIterator, typename _OutputIterator,
1026 typename _BinaryPredicate>
1027 _GLIBCXX20_CONSTEXPR
1028 _OutputIterator
1029 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1030 _OutputIterator __result, _BinaryPredicate __binary_pred,
1031 forward_iterator_tag, output_iterator_tag)
1032 {
1033 // concept requirements -- iterators already checked
1034 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1035 typename iterator_traits<_ForwardIterator>::value_type,
1036 typename iterator_traits<_ForwardIterator>::value_type>)
1037
1038 _ForwardIterator __next = __first;
1039 *__result = *__first;
1040 while (++__next != __last)
1041 if (!__binary_pred(__first, __next))
1042 {
1043 __first = __next;
1044 *++__result = *__first;
1045 }
1046 return ++__result;
1047 }
1048
1049 /**
1050 * This is an uglified
1051 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1052 * _BinaryPredicate)
1053 * overloaded for input iterators and output iterator as result.
1054 */
1055 template<typename _InputIterator, typename _OutputIterator,
1056 typename _BinaryPredicate>
1057 _GLIBCXX20_CONSTEXPR
1058 _OutputIterator
1059 __unique_copy(_InputIterator __first, _InputIterator __last,
1060 _OutputIterator __result, _BinaryPredicate __binary_pred,
1061 input_iterator_tag, output_iterator_tag)
1062 {
1063 // concept requirements -- iterators already checked
1064 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1065 typename iterator_traits<_InputIterator>::value_type,
1066 typename iterator_traits<_InputIterator>::value_type>)
1067
1068 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1069 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1070 __rebound_pred
1071 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1072 *__result = __value;
1073 while (++__first != __last)
1074 if (!__rebound_pred(__first, __value))
1075 {
1076 __value = *__first;
1077 *++__result = __value;
1078 }
1079 return ++__result;
1080 }
1081
1082 /**
1083 * This is an uglified
1084 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1085 * _BinaryPredicate)
1086 * overloaded for input iterators and forward iterator as result.
1087 */
1088 template<typename _InputIterator, typename _ForwardIterator,
1089 typename _BinaryPredicate>
1090 _GLIBCXX20_CONSTEXPR
1091 _ForwardIterator
1092 __unique_copy(_InputIterator __first, _InputIterator __last,
1093 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1094 input_iterator_tag, forward_iterator_tag)
1095 {
1096 // concept requirements -- iterators already checked
1097 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1098 typename iterator_traits<_ForwardIterator>::value_type,
1099 typename iterator_traits<_InputIterator>::value_type>)
1100 *__result = *__first;
1101 while (++__first != __last)
1102 if (!__binary_pred(__result, __first))
1103 *++__result = *__first;
1104 return ++__result;
1105 }
1106
1107 /**
1108 * This is an uglified reverse(_BidirectionalIterator,
1109 * _BidirectionalIterator)
1110 * overloaded for bidirectional iterators.
1111 */
1112 template<typename _BidirectionalIterator>
1113 _GLIBCXX20_CONSTEXPR
1114 void
1115 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1116 bidirectional_iterator_tag)
1117 {
1118 while (true)
1119 if (__first == __last || __first == --__last)
1120 return;
1121 else
1122 {
1123 std::iter_swap(__first, __last);
1124 ++__first;
1125 }
1126 }
1127
1128 /**
1129 * This is an uglified reverse(_BidirectionalIterator,
1130 * _BidirectionalIterator)
1131 * overloaded for random access iterators.
1132 */
1133 template<typename _RandomAccessIterator>
1134 _GLIBCXX20_CONSTEXPR
1135 void
1136 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1137 random_access_iterator_tag)
1138 {
1139 if (__first == __last)
1140 return;
1141 --__last;
1142 while (__first < __last)
1143 {
1144 std::iter_swap(__first, __last);
1145 ++__first;
1146 --__last;
1147 }
1148 }
1149
1150 /**
1151 * @brief Reverse a sequence.
1152 * @ingroup mutating_algorithms
1153 * @param __first A bidirectional iterator.
1154 * @param __last A bidirectional iterator.
1155 * @return reverse() returns no value.
1156 *
1157 * Reverses the order of the elements in the range @p [__first,__last),
1158 * so that the first element becomes the last etc.
1159 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1160 * swaps @p *(__first+i) and @p *(__last-(i+1))
1161 */
1162 template<typename _BidirectionalIterator>
1163 _GLIBCXX20_CONSTEXPR
1164 inline void
1165 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1166 {
1167 // concept requirements
1168 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1169 _BidirectionalIterator>)
1170 __glibcxx_requires_valid_range(__first, __last);
1171 std::__reverse(__first, __last, std::__iterator_category(__first));
1172 }
1173
1174 /**
1175 * @brief Copy a sequence, reversing its elements.
1176 * @ingroup mutating_algorithms
1177 * @param __first A bidirectional iterator.
1178 * @param __last A bidirectional iterator.
1179 * @param __result An output iterator.
1180 * @return An iterator designating the end of the resulting sequence.
1181 *
1182 * Copies the elements in the range @p [__first,__last) to the
1183 * range @p [__result,__result+(__last-__first)) such that the
1184 * order of the elements is reversed. For every @c i such that @p
1185 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1186 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1187 * The ranges @p [__first,__last) and @p
1188 * [__result,__result+(__last-__first)) must not overlap.
1189 */
1190 template<typename _BidirectionalIterator, typename _OutputIterator>
1191 _GLIBCXX20_CONSTEXPR
1192 _OutputIterator
1193 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1194 _OutputIterator __result)
1195 {
1196 // concept requirements
1197 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1198 _BidirectionalIterator>)
1199 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1200 typename iterator_traits<_BidirectionalIterator>::value_type>)
1201 __glibcxx_requires_valid_range(__first, __last);
1202
1203 while (__first != __last)
1204 {
1205 --__last;
1206 *__result = *__last;
1207 ++__result;
1208 }
1209 return __result;
1210 }
1211
1212 /**
1213 * This is a helper function for the rotate algorithm specialized on RAIs.
1214 * It returns the greatest common divisor of two integer values.
1215 */
1216 template<typename _EuclideanRingElement>
1217 _GLIBCXX20_CONSTEXPR
1218 _EuclideanRingElement
1219 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1220 {
1221 while (__n != 0)
1222 {
1223 _EuclideanRingElement __t = __m % __n;
1224 __m = __n;
1225 __n = __t;
1226 }
1227 return __m;
1228 }
1229
1230 inline namespace _V2
1231 {
1232
1233 /// This is a helper function for the rotate algorithm.
1234 template<typename _ForwardIterator>
1235 _GLIBCXX20_CONSTEXPR
1236 _ForwardIterator
1237 __rotate(_ForwardIterator __first,
1238 _ForwardIterator __middle,
1239 _ForwardIterator __last,
1240 forward_iterator_tag)
1241 {
1242 if (__first == __middle)
1243 return __last;
1244 else if (__last == __middle)
1245 return __first;
1246
1247 _ForwardIterator __first2 = __middle;
1248 do
1249 {
1250 std::iter_swap(__first, __first2);
1251 ++__first;
1252 ++__first2;
1253 if (__first == __middle)
1254 __middle = __first2;
1255 }
1256 while (__first2 != __last);
1257
1258 _ForwardIterator __ret = __first;
1259
1260 __first2 = __middle;
1261
1262 while (__first2 != __last)
1263 {
1264 std::iter_swap(__first, __first2);
1265 ++__first;
1266 ++__first2;
1267 if (__first == __middle)
1268 __middle = __first2;
1269 else if (__first2 == __last)
1270 __first2 = __middle;
1271 }
1272 return __ret;
1273 }
1274
1275 /// This is a helper function for the rotate algorithm.
1276 template<typename _BidirectionalIterator>
1277 _GLIBCXX20_CONSTEXPR
1278 _BidirectionalIterator
1279 __rotate(_BidirectionalIterator __first,
1280 _BidirectionalIterator __middle,
1281 _BidirectionalIterator __last,
1282 bidirectional_iterator_tag)
1283 {
1284 // concept requirements
1285 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1286 _BidirectionalIterator>)
1287
1288 if (__first == __middle)
1289 return __last;
1290 else if (__last == __middle)
1291 return __first;
1292
1293 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1294 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1295
1296 while (__first != __middle && __middle != __last)
1297 {
1298 std::iter_swap(__first, --__last);
1299 ++__first;
1300 }
1301
1302 if (__first == __middle)
1303 {
1304 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1305 return __last;
1306 }
1307 else
1308 {
1309 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1310 return __first;
1311 }
1312 }
1313
1314 /// This is a helper function for the rotate algorithm.
1315 template<typename _RandomAccessIterator>
1316 _GLIBCXX20_CONSTEXPR
1317 _RandomAccessIterator
1318 __rotate(_RandomAccessIterator __first,
1319 _RandomAccessIterator __middle,
1320 _RandomAccessIterator __last,
1321 random_access_iterator_tag)
1322 {
1323 // concept requirements
1324 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1325 _RandomAccessIterator>)
1326
1327 if (__first == __middle)
1328 return __last;
1329 else if (__last == __middle)
1330 return __first;
1331
1332 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1333 _Distance;
1334 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1335 _ValueType;
1336
1337 _Distance __n = __last - __first;
1338 _Distance __k = __middle - __first;
1339
1340 if (__k == __n - __k)
1341 {
1342 std::swap_ranges(__first, __middle, __middle);
1343 return __middle;
1344 }
1345
1346 _RandomAccessIterator __p = __first;
1347 _RandomAccessIterator __ret = __first + (__last - __middle);
1348
1349 for (;;)
1350 {
1351 if (__k < __n - __k)
1352 {
1353 if (__is_pod(_ValueType) && __k == 1)
1354 {
1355 _ValueType __t = _GLIBCXX_MOVE(*__p)std::move(*__p);
1356 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p)std::move(__p + 1, __p + __n, __p);
1357 *(__p + __n - 1) = _GLIBCXX_MOVE(__t)std::move(__t);
1358 return __ret;
1359 }
1360 _RandomAccessIterator __q = __p + __k;
1361 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1362 {
1363 std::iter_swap(__p, __q);
1364 ++__p;
1365 ++__q;
1366 }
1367 __n %= __k;
1368 if (__n == 0)
1369 return __ret;
1370 std::swap(__n, __k);
1371 __k = __n - __k;
1372 }
1373 else
1374 {
1375 __k = __n - __k;
1376 if (__is_pod(_ValueType) && __k == 1)
1377 {
1378 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1))std::move(*(__p + __n - 1));
1379 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n)std::move_backward(__p, __p + __n - 1, __p + __n);
1380 *__p = _GLIBCXX_MOVE(__t)std::move(__t);
1381 return __ret;
1382 }
1383 _RandomAccessIterator __q = __p + __n;
1384 __p = __q - __k;
1385 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1386 {
1387 --__p;
1388 --__q;
1389 std::iter_swap(__p, __q);
1390 }
1391 __n %= __k;
1392 if (__n == 0)
1393 return __ret;
1394 std::swap(__n, __k);
1395 }
1396 }
1397 }
1398
1399 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1400 // DR 488. rotate throws away useful information
1401 /**
1402 * @brief Rotate the elements of a sequence.
1403 * @ingroup mutating_algorithms
1404 * @param __first A forward iterator.
1405 * @param __middle A forward iterator.
1406 * @param __last A forward iterator.
1407 * @return first + (last - middle).
1408 *
1409 * Rotates the elements of the range @p [__first,__last) by
1410 * @p (__middle - __first) positions so that the element at @p __middle
1411 * is moved to @p __first, the element at @p __middle+1 is moved to
1412 * @p __first+1 and so on for each element in the range
1413 * @p [__first,__last).
1414 *
1415 * This effectively swaps the ranges @p [__first,__middle) and
1416 * @p [__middle,__last).
1417 *
1418 * Performs
1419 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1420 * for each @p n in the range @p [0,__last-__first).
1421 */
1422 template<typename _ForwardIterator>
1423 _GLIBCXX20_CONSTEXPR
1424 inline _ForwardIterator
1425 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1426 _ForwardIterator __last)
1427 {
1428 // concept requirements
1429 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1430 _ForwardIterator>)
1431 __glibcxx_requires_valid_range(__first, __middle);
1432 __glibcxx_requires_valid_range(__middle, __last);
1433
1434 return std::__rotate(__first, __middle, __last,
1435 std::__iterator_category(__first));
1436 }
1437
1438 } // namespace _V2
1439
1440 /**
1441 * @brief Copy a sequence, rotating its elements.
1442 * @ingroup mutating_algorithms
1443 * @param __first A forward iterator.
1444 * @param __middle A forward iterator.
1445 * @param __last A forward iterator.
1446 * @param __result An output iterator.
1447 * @return An iterator designating the end of the resulting sequence.
1448 *
1449 * Copies the elements of the range @p [__first,__last) to the
1450 * range beginning at @result, rotating the copied elements by
1451 * @p (__middle-__first) positions so that the element at @p __middle
1452 * is moved to @p __result, the element at @p __middle+1 is moved
1453 * to @p __result+1 and so on for each element in the range @p
1454 * [__first,__last).
1455 *
1456 * Performs
1457 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1458 * for each @p n in the range @p [0,__last-__first).
1459 */
1460 template<typename _ForwardIterator, typename _OutputIterator>
1461 _GLIBCXX20_CONSTEXPR
1462 inline _OutputIterator
1463 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1464 _ForwardIterator __last, _OutputIterator __result)
1465 {
1466 // concept requirements
1467 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1468 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1469 typename iterator_traits<_ForwardIterator>::value_type>)
1470 __glibcxx_requires_valid_range(__first, __middle);
1471 __glibcxx_requires_valid_range(__middle, __last);
1472
1473 return std::copy(__first, __middle,
1474 std::copy(__middle, __last, __result));
1475 }
1476
1477 /// This is a helper function...
1478 template<typename _ForwardIterator, typename _Predicate>
1479 _GLIBCXX20_CONSTEXPR
1480 _ForwardIterator
1481 __partition(_ForwardIterator __first, _ForwardIterator __last,
1482 _Predicate __pred, forward_iterator_tag)
1483 {
1484 if (__first == __last)
1485 return __first;
1486
1487 while (__pred(*__first))
1488 if (++__first == __last)
1489 return __first;
1490
1491 _ForwardIterator __next = __first;
1492
1493 while (++__next != __last)
1494 if (__pred(*__next))
1495 {
1496 std::iter_swap(__first, __next);
1497 ++__first;
1498 }
1499
1500 return __first;
1501 }
1502
1503 /// This is a helper function...
1504 template<typename _BidirectionalIterator, typename _Predicate>
1505 _GLIBCXX20_CONSTEXPR
1506 _BidirectionalIterator
1507 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1508 _Predicate __pred, bidirectional_iterator_tag)
1509 {
1510 while (true)
1511 {
1512 while (true)
1513 if (__first == __last)
1514 return __first;
1515 else if (__pred(*__first))
1516 ++__first;
1517 else
1518 break;
1519 --__last;
1520 while (true)
1521 if (__first == __last)
1522 return __first;
1523 else if (!bool(__pred(*__last)))
1524 --__last;
1525 else
1526 break;
1527 std::iter_swap(__first, __last);
1528 ++__first;
1529 }
1530 }
1531
1532 // partition
1533
1534 /// This is a helper function...
1535 /// Requires __first != __last and !__pred(__first)
1536 /// and __len == distance(__first, __last).
1537 ///
1538 /// !__pred(__first) allows us to guarantee that we don't
1539 /// move-assign an element onto itself.
1540 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1541 typename _Distance>
1542 _ForwardIterator
1543 __stable_partition_adaptive(_ForwardIterator __first,
1544 _ForwardIterator __last,
1545 _Predicate __pred, _Distance __len,
1546 _Pointer __buffer,
1547 _Distance __buffer_size)
1548 {
1549 if (__len == 1)
1550 return __first;
1551
1552 if (__len <= __buffer_size)
1553 {
1554 _ForwardIterator __result1 = __first;
1555 _Pointer __result2 = __buffer;
1556
1557 // The precondition guarantees that !__pred(__first), so
1558 // move that element to the buffer before starting the loop.
1559 // This ensures that we only call __pred once per element.
1560 *__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1561 ++__result2;
1562 ++__first;
1563 for (; __first != __last; ++__first)
1564 if (__pred(__first))
1565 {
1566 *__result1 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1567 ++__result1;
1568 }
1569 else
1570 {
1571 *__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1572 ++__result2;
1573 }
1574
1575 _GLIBCXX_MOVE3(__buffer, __result2, __result1)std::move(__buffer, __result2, __result1);
1576 return __result1;
1577 }
1578
1579 _ForwardIterator __middle = __first;
1580 std::advance(__middle, __len / 2);
1581 _ForwardIterator __left_split =
1582 std::__stable_partition_adaptive(__first, __middle, __pred,
1583 __len / 2, __buffer,
1584 __buffer_size);
1585
1586 // Advance past true-predicate values to satisfy this
1587 // function's preconditions.
1588 _Distance __right_len = __len - __len / 2;
1589 _ForwardIterator __right_split =
1590 std::__find_if_not_n(__middle, __right_len, __pred);
1591
1592 if (__right_len)
1593 __right_split =
1594 std::__stable_partition_adaptive(__right_split, __last, __pred,
1595 __right_len,
1596 __buffer, __buffer_size);
1597
1598 return std::rotate(__left_split, __middle, __right_split);
1599 }
1600
1601 template<typename _ForwardIterator, typename _Predicate>
1602 _ForwardIterator
1603 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1604 _Predicate __pred)
1605 {
1606 __first = std::__find_if_not(__first, __last, __pred);
1607
1608 if (__first == __last)
1609 return __first;
1610
1611 typedef typename iterator_traits<_ForwardIterator>::value_type
1612 _ValueType;
1613 typedef typename iterator_traits<_ForwardIterator>::difference_type
1614 _DistanceType;
1615
1616 _Temporary_buffer<_ForwardIterator, _ValueType>
1617 __buf(__first, std::distance(__first, __last));
1618 return
1619 std::__stable_partition_adaptive(__first, __last, __pred,
1620 _DistanceType(__buf.requested_size()),
1621 __buf.begin(),
1622 _DistanceType(__buf.size()));
1623 }
1624
1625 /**
1626 * @brief Move elements for which a predicate is true to the beginning
1627 * of a sequence, preserving relative ordering.
1628 * @ingroup mutating_algorithms
1629 * @param __first A forward iterator.
1630 * @param __last A forward iterator.
1631 * @param __pred A predicate functor.
1632 * @return An iterator @p middle such that @p __pred(i) is true for each
1633 * iterator @p i in the range @p [first,middle) and false for each @p i
1634 * in the range @p [middle,last).
1635 *
1636 * Performs the same function as @p partition() with the additional
1637 * guarantee that the relative ordering of elements in each group is
1638 * preserved, so any two elements @p x and @p y in the range
1639 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1640 * relative ordering after calling @p stable_partition().
1641 */
1642 template<typename _ForwardIterator, typename _Predicate>
1643 inline _ForwardIterator
1644 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1645 _Predicate __pred)
1646 {
1647 // concept requirements
1648 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1649 _ForwardIterator>)
1650 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1651 typename iterator_traits<_ForwardIterator>::value_type>)
1652 __glibcxx_requires_valid_range(__first, __last);
1653
1654 return std::__stable_partition(__first, __last,
1655 __gnu_cxx::__ops::__pred_iter(__pred));
1656 }
1657
1658 /// This is a helper function for the sort routines.
1659 template<typename _RandomAccessIterator, typename _Compare>
1660 _GLIBCXX20_CONSTEXPR
1661 void
1662 __heap_select(_RandomAccessIterator __first,
1663 _RandomAccessIterator __middle,
1664 _RandomAccessIterator __last, _Compare __comp)
1665 {
1666 std::__make_heap(__first, __middle, __comp);
1667 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1668 if (__comp(__i, __first))
1669 std::__pop_heap(__first, __middle, __i, __comp);
1670 }
1671
1672 // partial_sort
1673
1674 template<typename _InputIterator, typename _RandomAccessIterator,
1675 typename _Compare>
1676 _GLIBCXX20_CONSTEXPR
1677 _RandomAccessIterator
1678 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1679 _RandomAccessIterator __result_first,
1680 _RandomAccessIterator __result_last,
1681 _Compare __comp)
1682 {
1683 typedef typename iterator_traits<_InputIterator>::value_type
1684 _InputValueType;
1685 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1686 typedef typename _RItTraits::difference_type _DistanceType;
1687
1688 if (__result_first == __result_last)
1689 return __result_last;
1690 _RandomAccessIterator __result_real_last = __result_first;
1691 while (__first != __last && __result_real_last != __result_last)
1692 {
1693 *__result_real_last = *__first;
1694 ++__result_real_last;
1695 ++__first;
1696 }
1697
1698 std::__make_heap(__result_first, __result_real_last, __comp);
1699 while (__first != __last)
1700 {
1701 if (__comp(__first, __result_first))
1702 std::__adjust_heap(__result_first, _DistanceType(0),
1703 _DistanceType(__result_real_last
1704 - __result_first),
1705 _InputValueType(*__first), __comp);
1706 ++__first;
1707 }
1708 std::__sort_heap(__result_first, __result_real_last, __comp);
1709 return __result_real_last;
1710 }
1711
1712 /**
1713 * @brief Copy the smallest elements of a sequence.
1714 * @ingroup sorting_algorithms
1715 * @param __first An iterator.
1716 * @param __last Another iterator.
1717 * @param __result_first A random-access iterator.
1718 * @param __result_last Another random-access iterator.
1719 * @return An iterator indicating the end of the resulting sequence.
1720 *
1721 * Copies and sorts the smallest N values from the range @p [__first,__last)
1722 * to the range beginning at @p __result_first, where the number of
1723 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1724 * @p (__result_last-__result_first).
1725 * After the sort if @e i and @e j are iterators in the range
1726 * @p [__result_first,__result_first+N) such that i precedes j then
1727 * *j<*i is false.
1728 * The value returned is @p __result_first+N.
1729 */
1730 template<typename _InputIterator, typename _RandomAccessIterator>
1731 _GLIBCXX20_CONSTEXPR
1732 inline _RandomAccessIterator
1733 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1734 _RandomAccessIterator __result_first,
1735 _RandomAccessIterator __result_last)
1736 {
1737#ifdef _GLIBCXX_CONCEPT_CHECKS
1738 typedef typename iterator_traits<_InputIterator>::value_type
1739 _InputValueType;
1740 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1741 _OutputValueType;
1742#endif
1743
1744 // concept requirements
1745 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1746 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1747 _OutputValueType>)
1748 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1749 _OutputValueType>)
1750 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1751 __glibcxx_requires_valid_range(__first, __last);
1752 __glibcxx_requires_irreflexive(__first, __last);
1753 __glibcxx_requires_valid_range(__result_first, __result_last);
1754
1755 return std::__partial_sort_copy(__first, __last,
1756 __result_first, __result_last,
1757 __gnu_cxx::__ops::__iter_less_iter());
1758 }
1759
1760 /**
1761 * @brief Copy the smallest elements of a sequence using a predicate for
1762 * comparison.
1763 * @ingroup sorting_algorithms
1764 * @param __first An input iterator.
1765 * @param __last Another input iterator.
1766 * @param __result_first A random-access iterator.
1767 * @param __result_last Another random-access iterator.
1768 * @param __comp A comparison functor.
1769 * @return An iterator indicating the end of the resulting sequence.
1770 *
1771 * Copies and sorts the smallest N values from the range @p [__first,__last)
1772 * to the range beginning at @p result_first, where the number of
1773 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1774 * @p (__result_last-__result_first).
1775 * After the sort if @e i and @e j are iterators in the range
1776 * @p [__result_first,__result_first+N) such that i precedes j then
1777 * @p __comp(*j,*i) is false.
1778 * The value returned is @p __result_first+N.
1779 */
1780 template<typename _InputIterator, typename _RandomAccessIterator,
1781 typename _Compare>
1782 _GLIBCXX20_CONSTEXPR
1783 inline _RandomAccessIterator
1784 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1785 _RandomAccessIterator __result_first,
1786 _RandomAccessIterator __result_last,
1787 _Compare __comp)
1788 {
1789#ifdef _GLIBCXX_CONCEPT_CHECKS
1790 typedef typename iterator_traits<_InputIterator>::value_type
1791 _InputValueType;
1792 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1793 _OutputValueType;
1794#endif
1795
1796 // concept requirements
1797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1799 _RandomAccessIterator>)
1800 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1801 _OutputValueType>)
1802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1803 _InputValueType, _OutputValueType>)
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 _OutputValueType, _OutputValueType>)
1806 __glibcxx_requires_valid_range(__first, __last);
1807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1808 __glibcxx_requires_valid_range(__result_first, __result_last);
1809
1810 return std::__partial_sort_copy(__first, __last,
1811 __result_first, __result_last,
1812 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1813 }
1814
1815 /// This is a helper function for the sort routine.
1816 template<typename _RandomAccessIterator, typename _Compare>
1817 _GLIBCXX20_CONSTEXPR
1818 void
1819 __unguarded_linear_insert(_RandomAccessIterator __last,
1820 _Compare __comp)
1821 {
1822 typename iterator_traits<_RandomAccessIterator>::value_type
1823 __val = _GLIBCXX_MOVE(*__last)std::move(*__last);
1824 _RandomAccessIterator __next = __last;
1825 --__next;
1826 while (__comp(__val, __next))
1827 {
1828 *__last = _GLIBCXX_MOVE(*__next)std::move(*__next);
1829 __last = __next;
1830 --__next;
1831 }
1832 *__last = _GLIBCXX_MOVE(__val)std::move(__val);
1833 }
1834
1835 /// This is a helper function for the sort routine.
1836 template<typename _RandomAccessIterator, typename _Compare>
1837 _GLIBCXX20_CONSTEXPR
1838 void
1839 __insertion_sort(_RandomAccessIterator __first,
1840 _RandomAccessIterator __last, _Compare __comp)
1841 {
1842 if (__first == __last) return;
1843
1844 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1845 {
1846 if (__comp(__i, __first))
1847 {
1848 typename iterator_traits<_RandomAccessIterator>::value_type
1849 __val = _GLIBCXX_MOVE(*__i)std::move(*__i);
1850 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1)std::move_backward(__first, __i, __i + 1);
1851 *__first = _GLIBCXX_MOVE(__val)std::move(__val);
1852 }
1853 else
1854 std::__unguarded_linear_insert(__i,
1855 __gnu_cxx::__ops::__val_comp_iter(__comp));
1856 }
1857 }
1858
1859 /// This is a helper function for the sort routine.
1860 template<typename _RandomAccessIterator, typename _Compare>
1861 _GLIBCXX20_CONSTEXPR
1862 inline void
1863 __unguarded_insertion_sort(_RandomAccessIterator __first,
1864 _RandomAccessIterator __last, _Compare __comp)
1865 {
1866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1867 std::__unguarded_linear_insert(__i,
1868 __gnu_cxx::__ops::__val_comp_iter(__comp));
1869 }
1870
1871 /**
1872 * @doctodo
1873 * This controls some aspect of the sort routines.
1874 */
1875 enum { _S_threshold = 16 };
1876
1877 /// This is a helper function for the sort routine.
1878 template<typename _RandomAccessIterator, typename _Compare>
1879 _GLIBCXX20_CONSTEXPR
1880 void
1881 __final_insertion_sort(_RandomAccessIterator __first,
1882 _RandomAccessIterator __last, _Compare __comp)
1883 {
1884 if (__last - __first > int(_S_threshold))
1885 {
1886 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1887 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1888 __comp);
1889 }
1890 else
1891 std::__insertion_sort(__first, __last, __comp);
1892 }
1893
1894 /// This is a helper function...
1895 template<typename _RandomAccessIterator, typename _Compare>
1896 _GLIBCXX20_CONSTEXPR
1897 _RandomAccessIterator
1898 __unguarded_partition(_RandomAccessIterator __first,
1899 _RandomAccessIterator __last,
1900 _RandomAccessIterator __pivot, _Compare __comp)
1901 {
1902 while (true)
1903 {
1904 while (__comp(__first, __pivot))
1905 ++__first;
1906 --__last;
1907 while (__comp(__pivot, __last))
1908 --__last;
1909 if (!(__first < __last))
1910 return __first;
1911 std::iter_swap(__first, __last);
1912 ++__first;
1913 }
1914 }
1915
1916 /// This is a helper function...
1917 template<typename _RandomAccessIterator, typename _Compare>
1918 _GLIBCXX20_CONSTEXPR
1919 inline _RandomAccessIterator
1920 __unguarded_partition_pivot(_RandomAccessIterator __first,
1921 _RandomAccessIterator __last, _Compare __comp)
1922 {
1923 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1924 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1925 __comp);
1926 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1927 }
1928
1929 template<typename _RandomAccessIterator, typename _Compare>
1930 _GLIBCXX20_CONSTEXPR
1931 inline void
1932 __partial_sort(_RandomAccessIterator __first,
1933 _RandomAccessIterator __middle,
1934 _RandomAccessIterator __last,
1935 _Compare __comp)
1936 {
1937 std::__heap_select(__first, __middle, __last, __comp);
1938 std::__sort_heap(__first, __middle, __comp);
1939 }
1940
1941 /// This is a helper function for the sort routine.
1942 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1943 _GLIBCXX20_CONSTEXPR
1944 void
1945 __introsort_loop(_RandomAccessIterator __first,
1946 _RandomAccessIterator __last,
1947 _Size __depth_limit, _Compare __comp)
1948 {
1949 while (__last - __first > int(_S_threshold))
1950 {
1951 if (__depth_limit == 0)
1952 {
1953 std::__partial_sort(__first, __last, __last, __comp);
1954 return;
1955 }
1956 --__depth_limit;
1957 _RandomAccessIterator __cut =
1958 std::__unguarded_partition_pivot(__first, __last, __comp);
1959 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1960 __last = __cut;
1961 }
1962 }
1963
1964 // sort
1965
1966 template<typename _RandomAccessIterator, typename _Compare>
1967 _GLIBCXX20_CONSTEXPR
1968 inline void
1969 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1970 _Compare __comp)
1971 {
1972 if (__first != __last)
1973 {
1974 std::__introsort_loop(__first, __last,
1975 std::__lg(__last - __first) * 2,
1976 __comp);
1977 std::__final_insertion_sort(__first, __last, __comp);
1978 }
1979 }
1980
1981 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1982 _GLIBCXX20_CONSTEXPR
1983 void
1984 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1985 _RandomAccessIterator __last, _Size __depth_limit,
1986 _Compare __comp)
1987 {
1988 while (__last - __first > 3)
1989 {
1990 if (__depth_limit == 0)
1991 {
1992 std::__heap_select(__first, __nth + 1, __last, __comp);
1993 // Place the nth largest element in its final position.
1994 std::iter_swap(__first, __nth);
1995 return;
1996 }
1997 --__depth_limit;
1998 _RandomAccessIterator __cut =
1999 std::__unguarded_partition_pivot(__first, __last, __comp);
2000 if (__cut <= __nth)
2001 __first = __cut;
2002 else
2003 __last = __cut;
2004 }
2005 std::__insertion_sort(__first, __last, __comp);
2006 }
2007
2008 // nth_element
2009
2010 // lower_bound moved to stl_algobase.h
2011
2012 /**
2013 * @brief Finds the first position in which @p __val could be inserted
2014 * without changing the ordering.
2015 * @ingroup binary_search_algorithms
2016 * @param __first An iterator.
2017 * @param __last Another iterator.
2018 * @param __val The search term.
2019 * @param __comp A functor to use for comparisons.
2020 * @return An iterator pointing to the first element <em>not less
2021 * than</em> @p __val, or end() if every element is less
2022 * than @p __val.
2023 * @ingroup binary_search_algorithms
2024 *
2025 * The comparison function should have the same effects on ordering as
2026 * the function used for the initial sort.
2027 */
2028 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2029 _GLIBCXX20_CONSTEXPR
2030 inline _ForwardIterator
2031 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2032 const _Tp& __val, _Compare __comp)
2033 {
2034 // concept requirements
2035 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2036 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2037 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2038 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2039 __val, __comp);
2040
2041 return std::__lower_bound(__first, __last, __val,
2042 __gnu_cxx::__ops::__iter_comp_val(__comp));
2043 }
2044
2045 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2046 _GLIBCXX20_CONSTEXPR
2047 _ForwardIterator
2048 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2049 const _Tp& __val, _Compare __comp)
2050 {
2051 typedef typename iterator_traits<_ForwardIterator>::difference_type
2052 _DistanceType;
2053
2054 _DistanceType __len = std::distance(__first, __last);
2055
2056 while (__len > 0)
2057 {
2058 _DistanceType __half = __len >> 1;
2059 _ForwardIterator __middle = __first;
2060 std::advance(__middle, __half);
2061 if (__comp(__val, __middle))
2062 __len = __half;
2063 else
2064 {
2065 __first = __middle;
2066 ++__first;
2067 __len = __len - __half - 1;
2068 }
2069 }
2070 return __first;
2071 }
2072
2073 /**
2074 * @brief Finds the last position in which @p __val could be inserted
2075 * without changing the ordering.
2076 * @ingroup binary_search_algorithms
2077 * @param __first An iterator.
2078 * @param __last Another iterator.
2079 * @param __val The search term.
2080 * @return An iterator pointing to the first element greater than @p __val,
2081 * or end() if no elements are greater than @p __val.
2082 * @ingroup binary_search_algorithms
2083 */
2084 template<typename _ForwardIterator, typename _Tp>
2085 _GLIBCXX20_CONSTEXPR
2086 inline _ForwardIterator
2087 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2088 const _Tp& __val)
2089 {
2090 // concept requirements
2091 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2092 __glibcxx_function_requires(_LessThanOpConcept<
2093 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2094 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2095
2096 return std::__upper_bound(__first, __last, __val,
2097 __gnu_cxx::__ops::__val_less_iter());
2098 }
2099
2100 /**
2101 * @brief Finds the last position in which @p __val could be inserted
2102 * without changing the ordering.
2103 * @ingroup binary_search_algorithms
2104 * @param __first An iterator.
2105 * @param __last Another iterator.
2106 * @param __val The search term.
2107 * @param __comp A functor to use for comparisons.
2108 * @return An iterator pointing to the first element greater than @p __val,
2109 * or end() if no elements are greater than @p __val.
2110 * @ingroup binary_search_algorithms
2111 *
2112 * The comparison function should have the same effects on ordering as
2113 * the function used for the initial sort.
2114 */
2115 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2116 _GLIBCXX20_CONSTEXPR
2117 inline _ForwardIterator
2118 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2119 const _Tp& __val, _Compare __comp)
2120 {
2121 // concept requirements
2122 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2123 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2124 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2125 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2126 __val, __comp);
2127
2128 return std::__upper_bound(__first, __last, __val,
2129 __gnu_cxx::__ops::__val_comp_iter(__comp));
2130 }
2131
2132 template<typename _ForwardIterator, typename _Tp,
2133 typename _CompareItTp, typename _CompareTpIt>
2134 _GLIBCXX20_CONSTEXPR
2135 pair<_ForwardIterator, _ForwardIterator>
2136 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2137 const _Tp& __val,
2138 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2139 {
2140 typedef typename iterator_traits<_ForwardIterator>::difference_type
2141 _DistanceType;
2142
2143 _DistanceType __len = std::distance(__first, __last);
2144
2145 while (__len > 0)
2146 {
2147 _DistanceType __half = __len >> 1;
2148 _ForwardIterator __middle = __first;
2149 std::advance(__middle, __half);
2150 if (__comp_it_val(__middle, __val))
2151 {
2152 __first = __middle;
2153 ++__first;
2154 __len = __len - __half - 1;
2155 }
2156 else if (__comp_val_it(__val, __middle))
2157 __len = __half;
2158 else
2159 {
2160 _ForwardIterator __left
2161 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2162 std::advance(__first, __len);
2163 _ForwardIterator __right
2164 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2165 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2166 }
2167 }
2168 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2169 }
2170
2171 /**
2172 * @brief Finds the largest subrange in which @p __val could be inserted
2173 * at any place in it without changing the ordering.
2174 * @ingroup binary_search_algorithms
2175 * @param __first An iterator.
2176 * @param __last Another iterator.
2177 * @param __val The search term.
2178 * @return An pair of iterators defining the subrange.
2179 * @ingroup binary_search_algorithms
2180 *
2181 * This is equivalent to
2182 * @code
2183 * std::make_pair(lower_bound(__first, __last, __val),
2184 * upper_bound(__first, __last, __val))
2185 * @endcode
2186 * but does not actually call those functions.
2187 */
2188 template<typename _ForwardIterator, typename _Tp>
2189 _GLIBCXX20_CONSTEXPR
2190 inline pair<_ForwardIterator, _ForwardIterator>
2191 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2192 const _Tp& __val)
2193 {
2194 // concept requirements
2195 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2196 __glibcxx_function_requires(_LessThanOpConcept<
2197 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2198 __glibcxx_function_requires(_LessThanOpConcept<
2199 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2200 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2201 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2202
2203 return std::__equal_range(__first, __last, __val,
2204 __gnu_cxx::__ops::__iter_less_val(),
2205 __gnu_cxx::__ops::__val_less_iter());
2206 }
2207
2208 /**
2209 * @brief Finds the largest subrange in which @p __val could be inserted
2210 * at any place in it without changing the ordering.
2211 * @param __first An iterator.
2212 * @param __last Another iterator.
2213 * @param __val The search term.
2214 * @param __comp A functor to use for comparisons.
2215 * @return An pair of iterators defining the subrange.
2216 * @ingroup binary_search_algorithms
2217 *
2218 * This is equivalent to
2219 * @code
2220 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2221 * upper_bound(__first, __last, __val, __comp))
2222 * @endcode
2223 * but does not actually call those functions.
2224 */
2225 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2226 _GLIBCXX20_CONSTEXPR
2227 inline pair<_ForwardIterator, _ForwardIterator>
2228 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2229 const _Tp& __val, _Compare __comp)
2230 {
2231 // concept requirements
2232 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2234 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2235 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2236 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2237 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2238 __val, __comp);
2239 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2240 __val, __comp);
2241
2242 return std::__equal_range(__first, __last, __val,
2243 __gnu_cxx::__ops::__iter_comp_val(__comp),
2244 __gnu_cxx::__ops::__val_comp_iter(__comp));
2245 }
2246
2247 /**
2248 * @brief Determines whether an element exists in a range.
2249 * @ingroup binary_search_algorithms
2250 * @param __first An iterator.
2251 * @param __last Another iterator.
2252 * @param __val The search term.
2253 * @return True if @p __val (or its equivalent) is in [@p
2254 * __first,@p __last ].
2255 *
2256 * Note that this does not actually return an iterator to @p __val. For
2257 * that, use std::find or a container's specialized find member functions.
2258 */
2259 template<typename _ForwardIterator, typename _Tp>
2260 _GLIBCXX20_CONSTEXPR
2261 bool
2262 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2263 const _Tp& __val)
2264 {
2265 // concept requirements
2266 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2267 __glibcxx_function_requires(_LessThanOpConcept<
2268 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2269 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2270 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2271
2272 _ForwardIterator __i
2273 = std::__lower_bound(__first, __last, __val,
2274 __gnu_cxx::__ops::__iter_less_val());
2275 return __i != __last && !(__val < *__i);
2276 }
2277
2278 /**
2279 * @brief Determines whether an element exists in a range.
2280 * @ingroup binary_search_algorithms
2281 * @param __first An iterator.
2282 * @param __last Another iterator.
2283 * @param __val The search term.
2284 * @param __comp A functor to use for comparisons.
2285 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2286 *
2287 * Note that this does not actually return an iterator to @p __val. For
2288 * that, use std::find or a container's specialized find member functions.
2289 *
2290 * The comparison function should have the same effects on ordering as
2291 * the function used for the initial sort.
2292 */
2293 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2294 _GLIBCXX20_CONSTEXPR
2295 bool
2296 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2297 const _Tp& __val, _Compare __comp)
2298 {
2299 // concept requirements
2300 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2301 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2302 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2303 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2304 __val, __comp);
2305 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2306 __val, __comp);
2307
2308 _ForwardIterator __i
2309 = std::__lower_bound(__first, __last, __val,
2310 __gnu_cxx::__ops::__iter_comp_val(__comp));
2311 return __i != __last && !bool(__comp(__val, *__i));
2312 }
2313
2314 // merge
2315
2316 /// This is a helper function for the __merge_adaptive routines.
2317 template<typename _InputIterator1, typename _InputIterator2,
2318 typename _OutputIterator, typename _Compare>
2319 void
2320 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2321 _InputIterator2 __first2, _InputIterator2 __last2,
2322 _OutputIterator __result, _Compare __comp)
2323 {
2324 while (__first1 != __last1 && __first2 != __last2)
2325 {
2326 if (__comp(__first2, __first1))
2327 {
2328 *__result = _GLIBCXX_MOVE(*__first2)std::move(*__first2);
2329 ++__first2;
2330 }
2331 else
2332 {
2333 *__result = _GLIBCXX_MOVE(*__first1)std::move(*__first1);
2334 ++__first1;
2335 }
2336 ++__result;
2337 }
2338 if (__first1 != __last1)
2339 _GLIBCXX_MOVE3(__first1, __last1, __result)std::move(__first1, __last1, __result);
2340 }
2341
2342 /// This is a helper function for the __merge_adaptive routines.
2343 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2344 typename _BidirectionalIterator3, typename _Compare>
2345 void
2346 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2347 _BidirectionalIterator1 __last1,
2348 _BidirectionalIterator2 __first2,
2349 _BidirectionalIterator2 __last2,
2350 _BidirectionalIterator3 __result,
2351 _Compare __comp)
2352 {
2353 if (__first1 == __last1)
2354 {
2355 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result)std::move_backward(__first2, __last2, __result);
2356 return;
2357 }
2358 else if (__first2 == __last2)
2359 return;
2360
2361 --__last1;
2362 --__last2;
2363 while (true)
2364 {
2365 if (__comp(__last2, __last1))
2366 {
2367 *--__result = _GLIBCXX_MOVE(*__last1)std::move(*__last1);
2368 if (__first1 == __last1)
2369 {
2370 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result)std::move_backward(__first2, ++__last2, __result);
2371 return;
2372 }
2373 --__last1;
2374 }
2375 else
2376 {
2377 *--__result = _GLIBCXX_MOVE(*__last2)std::move(*__last2);
2378 if (__first2 == __last2)
2379 return;
2380 --__last2;
2381 }
2382 }
2383 }
2384
2385 /// This is a helper function for the merge routines.
2386 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2387 typename _Distance>
2388 _BidirectionalIterator1
2389 __rotate_adaptive(_BidirectionalIterator1 __first,
2390 _BidirectionalIterator1 __middle,
2391 _BidirectionalIterator1 __last,
2392 _Distance __len1, _Distance __len2,
2393 _BidirectionalIterator2 __buffer,
2394 _Distance __buffer_size)
2395 {
2396 _BidirectionalIterator2 __buffer_end;
2397 if (__len1 > __len2 && __len2 <= __buffer_size)
2398 {
2399 if (__len2)
2400 {
2401 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
2402 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last)std::move_backward(__first, __middle, __last);
2403 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first)std::move(__buffer, __buffer_end, __first);
2404 }
2405 else
2406 return __first;
2407 }
2408 else if (__len1 <= __buffer_size)
2409 {
2410 if (__len1)
2411 {
2412 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
2413 _GLIBCXX_MOVE3(__middle, __last, __first)std::move(__middle, __last, __first);
2414 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last)std::move_backward(__buffer, __buffer_end, __last);
2415 }
2416 else
2417 return __last;
2418 }
2419 else
2420 return std::rotate(__first, __middle, __last);
2421 }
2422
2423 /// This is a helper function for the merge routines.
2424 template<typename _BidirectionalIterator, typename _Distance,
2425 typename _Pointer, typename _Compare>
2426 void
2427 __merge_adaptive(_BidirectionalIterator __first,
2428 _BidirectionalIterator __middle,
2429 _BidirectionalIterator __last,
2430 _Distance __len1, _Distance __len2,
2431 _Pointer __buffer, _Distance __buffer_size,
2432 _Compare __comp)
2433 {
2434 if (__len1 <= __len2 && __len1 <= __buffer_size)
2435 {
2436 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
2437 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2438 __first, __comp);
2439 }
2440 else if (__len2 <= __buffer_size)
2441 {
2442 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
2443 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2444 __buffer_end, __last, __comp);
2445 }
2446 else
2447 {
2448 _BidirectionalIterator __first_cut = __first;
2449 _BidirectionalIterator __second_cut = __middle;
2450 _Distance __len11 = 0;
2451 _Distance __len22 = 0;
2452 if (__len1 > __len2)
2453 {
2454 __len11 = __len1 / 2;
2455 std::advance(__first_cut, __len11);
2456 __second_cut
2457 = std::__lower_bound(__middle, __last, *__first_cut,
2458 __gnu_cxx::__ops::__iter_comp_val(__comp));
2459 __len22 = std::distance(__middle, __second_cut);
2460 }
2461 else
2462 {
2463 __len22 = __len2 / 2;
2464 std::advance(__second_cut, __len22);
2465 __first_cut
2466 = std::__upper_bound(__first, __middle, *__second_cut,
2467 __gnu_cxx::__ops::__val_comp_iter(__comp));
2468 __len11 = std::distance(__first, __first_cut);
2469 }
2470
2471 _BidirectionalIterator __new_middle
2472 = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2473 __len1 - __len11, __len22, __buffer,
2474 __buffer_size);
2475 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2476 __len22, __buffer, __buffer_size, __comp);
2477 std::__merge_adaptive(__new_middle, __second_cut, __last,
2478 __len1 - __len11,
2479 __len2 - __len22, __buffer,
2480 __buffer_size, __comp);
2481 }
2482 }
2483
2484 /// This is a helper function for the merge routines.
2485 template<typename _BidirectionalIterator, typename _Distance,
2486 typename _Compare>
2487 void
2488 __merge_without_buffer(_BidirectionalIterator __first,
2489 _BidirectionalIterator __middle,
2490 _BidirectionalIterator __last,
2491 _Distance __len1, _Distance __len2,
2492 _Compare __comp)
2493 {
2494 if (__len1 == 0 || __len2 == 0)
2495 return;
2496
2497 if (__len1 + __len2 == 2)
2498 {
2499 if (__comp(__middle, __first))
2500 std::iter_swap(__first, __middle);
2501 return;
2502 }
2503
2504 _BidirectionalIterator __first_cut = __first;
2505 _BidirectionalIterator __second_cut = __middle;
2506 _Distance __len11 = 0;
2507 _Distance __len22 = 0;
2508 if (__len1 > __len2)
2509 {
2510 __len11 = __len1 / 2;
2511 std::advance(__first_cut, __len11);
2512 __second_cut
2513 = std::__lower_bound(__middle, __last, *__first_cut,
2514 __gnu_cxx::__ops::__iter_comp_val(__comp));
2515 __len22 = std::distance(__middle, __second_cut);
2516 }
2517 else
2518 {
2519 __len22 = __len2 / 2;
2520 std::advance(__second_cut, __len22);
2521 __first_cut
2522 = std::__upper_bound(__first, __middle, *__second_cut,
2523 __gnu_cxx::__ops::__val_comp_iter(__comp));
2524 __len11 = std::distance(__first, __first_cut);
2525 }
2526
2527 _BidirectionalIterator __new_middle
2528 = std::rotate(__first_cut, __middle, __second_cut);
2529 std::__merge_without_buffer(__first, __first_cut, __new_middle,
2530 __len11, __len22, __comp);
2531 std::__merge_without_buffer(__new_middle, __second_cut, __last,
2532 __len1 - __len11, __len2 - __len22, __comp);
2533 }
2534
2535 template<typename _BidirectionalIterator, typename _Compare>
2536 void
2537 __inplace_merge(_BidirectionalIterator __first,
2538 _BidirectionalIterator __middle,
2539 _BidirectionalIterator __last,
2540 _Compare __comp)
2541 {
2542 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2543 _ValueType;
2544 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2545 _DistanceType;
2546
2547 if (__first == __middle || __middle == __last)
2548 return;
2549
2550 const _DistanceType __len1 = std::distance(__first, __middle);
2551 const _DistanceType __len2 = std::distance(__middle, __last);
2552
2553 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2554 _TmpBuf __buf(__first, __len1 + __len2);
2555
2556 if (__buf.begin() == 0)
2557 std::__merge_without_buffer
2558 (__first, __middle, __last, __len1, __len2, __comp);
2559 else
2560 std::__merge_adaptive
2561 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2562 _DistanceType(__buf.size()), __comp);
2563 }
2564
2565 /**
2566 * @brief Merges two sorted ranges in place.
2567 * @ingroup sorting_algorithms
2568 * @param __first An iterator.
2569 * @param __middle Another iterator.
2570 * @param __last Another iterator.
2571 * @return Nothing.
2572 *
2573 * Merges two sorted and consecutive ranges, [__first,__middle) and
2574 * [__middle,__last), and puts the result in [__first,__last). The
2575 * output will be sorted. The sort is @e stable, that is, for
2576 * equivalent elements in the two ranges, elements from the first
2577 * range will always come before elements from the second.
2578 *
2579 * If enough additional memory is available, this takes (__last-__first)-1
2580 * comparisons. Otherwise an NlogN algorithm is used, where N is
2581 * distance(__first,__last).
2582 */
2583 template<typename _BidirectionalIterator>
2584 inline void
2585 inplace_merge(_BidirectionalIterator __first,
2586 _BidirectionalIterator __middle,
2587 _BidirectionalIterator __last)
2588 {
2589 // concept requirements
2590 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2591 _BidirectionalIterator>)
2592 __glibcxx_function_requires(_LessThanComparableConcept<
2593 typename iterator_traits<_BidirectionalIterator>::value_type>)
2594 __glibcxx_requires_sorted(__first, __middle);
2595 __glibcxx_requires_sorted(__middle, __last);
2596 __glibcxx_requires_irreflexive(__first, __last);
2597
2598 std::__inplace_merge(__first, __middle, __last,
2599 __gnu_cxx::__ops::__iter_less_iter());
2600 }
2601
2602 /**
2603 * @brief Merges two sorted ranges in place.
2604 * @ingroup sorting_algorithms
2605 * @param __first An iterator.
2606 * @param __middle Another iterator.
2607 * @param __last Another iterator.
2608 * @param __comp A functor to use for comparisons.
2609 * @return Nothing.
2610 *
2611 * Merges two sorted and consecutive ranges, [__first,__middle) and
2612 * [middle,last), and puts the result in [__first,__last). The output will
2613 * be sorted. The sort is @e stable, that is, for equivalent
2614 * elements in the two ranges, elements from the first range will always
2615 * come before elements from the second.
2616 *
2617 * If enough additional memory is available, this takes (__last-__first)-1
2618 * comparisons. Otherwise an NlogN algorithm is used, where N is
2619 * distance(__first,__last).
2620 *
2621 * The comparison function should have the same effects on ordering as
2622 * the function used for the initial sort.
2623 */
2624 template<typename _BidirectionalIterator, typename _Compare>
2625 inline void
2626 inplace_merge(_BidirectionalIterator __first,
2627 _BidirectionalIterator __middle,
2628 _BidirectionalIterator __last,
2629 _Compare __comp)
2630 {
2631 // concept requirements
2632 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2633 _BidirectionalIterator>)
2634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2635 typename iterator_traits<_BidirectionalIterator>::value_type,
2636 typename iterator_traits<_BidirectionalIterator>::value_type>)
2637 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2638 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2639 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2640
2641 std::__inplace_merge(__first, __middle, __last,
2642 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2643 }
2644
2645
2646 /// This is a helper function for the __merge_sort_loop routines.
2647 template<typename _InputIterator, typename _OutputIterator,
2648 typename _Compare>
2649 _OutputIterator
2650 __move_merge(_InputIterator __first1, _InputIterator __last1,
2651 _InputIterator __first2, _InputIterator __last2,
2652 _OutputIterator __result, _Compare __comp)
2653 {
2654 while (__first1 != __last1 && __first2 != __last2)
2655 {
2656 if (__comp(__first2, __first1))
2657 {
2658 *__result = _GLIBCXX_MOVE(*__first2)std::move(*__first2);
2659 ++__first2;
2660 }
2661 else
2662 {
2663 *__result = _GLIBCXX_MOVE(*__first1)std::move(*__first1);
2664 ++__first1;
2665 }
2666 ++__result;
2667 }
2668 return _GLIBCXX_MOVE3(__first2, __last2,std::move(__first2, __last2, std::move(__first1, __last1, __result
))
2669 _GLIBCXX_MOVE3(__first1, __last1,std::move(__first2, __last2, std::move(__first1, __last1, __result
))
2670 __result))std::move(__first2, __last2, std::move(__first1, __last1, __result
))
;
2671 }
2672
2673 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2674 typename _Distance, typename _Compare>
2675 void
2676 __merge_sort_loop(_RandomAccessIterator1 __first,
2677 _RandomAccessIterator1 __last,
2678 _RandomAccessIterator2 __result, _Distance __step_size,
2679 _Compare __comp)
2680 {
2681 const _Distance __two_step = 2 * __step_size;
2682
2683 while (__last - __first >= __two_step)
2684 {
2685 __result = std::__move_merge(__first, __first + __step_size,
2686 __first + __step_size,
2687 __first + __two_step,
2688 __result, __comp);
2689 __first += __two_step;
2690 }
2691 __step_size = std::min(_Distance(__last - __first), __step_size);
2692
2693 std::__move_merge(__first, __first + __step_size,
2694 __first + __step_size, __last, __result, __comp);
2695 }
2696
2697 template<typename _RandomAccessIterator, typename _Distance,
2698 typename _Compare>
2699 _GLIBCXX20_CONSTEXPR
2700 void
2701 __chunk_insertion_sort(_RandomAccessIterator __first,
2702 _RandomAccessIterator __last,
2703 _Distance __chunk_size, _Compare __comp)
2704 {
2705 while (__last - __first >= __chunk_size)
2706 {
2707 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2708 __first += __chunk_size;
2709 }
2710 std::__insertion_sort(__first, __last, __comp);
2711 }
2712
2713 enum { _S_chunk_size = 7 };
2714
2715 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2716 void
2717 __merge_sort_with_buffer(_RandomAccessIterator __first,
2718 _RandomAccessIterator __last,
2719 _Pointer __buffer, _Compare __comp)
2720 {
2721 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2722 _Distance;
2723
2724 const _Distance __len = __last - __first;
2725 const _Pointer __buffer_last = __buffer + __len;
2726
2727 _Distance __step_size = _S_chunk_size;
2728 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2729
2730 while (__step_size < __len)
2731 {
2732 std::__merge_sort_loop(__first, __last, __buffer,
2733 __step_size, __comp);
2734 __step_size *= 2;
2735 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2736 __step_size, __comp);
2737 __step_size *= 2;
2738 }
2739 }
2740
2741 template<typename _RandomAccessIterator, typename _Pointer,
2742 typename _Distance, typename _Compare>
2743 void
2744 __stable_sort_adaptive(_RandomAccessIterator __first,
2745 _RandomAccessIterator __last,
2746 _Pointer __buffer, _Distance __buffer_size,
2747 _Compare __comp)
2748 {
2749 const _Distance __len = (__last - __first + 1) / 2;
2750 const _RandomAccessIterator __middle = __first + __len;
2751 if (__len > __buffer_size)
2752 {
2753 std::__stable_sort_adaptive(__first, __middle, __buffer,
2754 __buffer_size, __comp);
2755 std::__stable_sort_adaptive(__middle, __last, __buffer,
2756 __buffer_size, __comp);
2757 }
2758 else
2759 {
2760 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2761 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2762 }
2763 std::__merge_adaptive(__first, __middle, __last,
2764 _Distance(__middle - __first),
2765 _Distance(__last - __middle),
2766 __buffer, __buffer_size,
2767 __comp);
2768 }
2769
2770 /// This is a helper function for the stable sorting routines.
2771 template<typename _RandomAccessIterator, typename _Compare>
2772 void
2773 __inplace_stable_sort(_RandomAccessIterator __first,
2774 _RandomAccessIterator __last, _Compare __comp)
2775 {
2776 if (__last - __first < 15)
2777 {
2778 std::__insertion_sort(__first, __last, __comp);
2779 return;
2780 }
2781 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2782 std::__inplace_stable_sort(__first, __middle, __comp);
2783 std::__inplace_stable_sort(__middle, __last, __comp);
2784 std::__merge_without_buffer(__first, __middle, __last,
2785 __middle - __first,
2786 __last - __middle,
2787 __comp);
2788 }
2789
2790 // stable_sort
2791
2792 // Set algorithms: includes, set_union, set_intersection, set_difference,
2793 // set_symmetric_difference. All of these algorithms have the precondition
2794 // that their input ranges are sorted and the postcondition that their output
2795 // ranges are sorted.
2796
2797 template<typename _InputIterator1, typename _InputIterator2,
2798 typename _Compare>
2799 _GLIBCXX20_CONSTEXPR
2800 bool
2801 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2802 _InputIterator2 __first2, _InputIterator2 __last2,
2803 _Compare __comp)
2804 {
2805 while (__first1 != __last1 && __first2 != __last2)
2806 if (__comp(__first2, __first1))
2807 return false;
2808 else if (__comp(__first1, __first2))
2809 ++__first1;
2810 else
2811 {
2812 ++__first1;
2813 ++__first2;
2814 }
2815
2816 return __first2 == __last2;
2817 }
2818
2819 /**
2820 * @brief Determines whether all elements of a sequence exists in a range.
2821 * @param __first1 Start of search range.
2822 * @param __last1 End of search range.
2823 * @param __first2 Start of sequence
2824 * @param __last2 End of sequence.
2825 * @return True if each element in [__first2,__last2) is contained in order
2826 * within [__first1,__last1). False otherwise.
2827 * @ingroup set_algorithms
2828 *
2829 * This operation expects both [__first1,__last1) and
2830 * [__first2,__last2) to be sorted. Searches for the presence of
2831 * each element in [__first2,__last2) within [__first1,__last1).
2832 * The iterators over each range only move forward, so this is a
2833 * linear algorithm. If an element in [__first2,__last2) is not
2834 * found before the search iterator reaches @p __last2, false is
2835 * returned.
2836 */
2837 template<typename _InputIterator1, typename _InputIterator2>
2838 _GLIBCXX20_CONSTEXPR
2839 inline bool
2840 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2841 _InputIterator2 __first2, _InputIterator2 __last2)
2842 {
2843 // concept requirements
2844 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2845 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2846 __glibcxx_function_requires(_LessThanOpConcept<
2847 typename iterator_traits<_InputIterator1>::value_type,
2848 typename iterator_traits<_InputIterator2>::value_type>)
2849 __glibcxx_function_requires(_LessThanOpConcept<
2850 typename iterator_traits<_InputIterator2>::value_type,
2851 typename iterator_traits<_InputIterator1>::value_type>)
2852 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2853 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2854 __glibcxx_requires_irreflexive2(__first1, __last1);
2855 __glibcxx_requires_irreflexive2(__first2, __last2);
2856
2857 return std::__includes(__first1, __last1, __first2, __last2,
2858 __gnu_cxx::__ops::__iter_less_iter());
2859 }
2860
2861 /**
2862 * @brief Determines whether all elements of a sequence exists in a range
2863 * using comparison.
2864 * @ingroup set_algorithms
2865 * @param __first1 Start of search range.
2866 * @param __last1 End of search range.
2867 * @param __first2 Start of sequence
2868 * @param __last2 End of sequence.
2869 * @param __comp Comparison function to use.
2870 * @return True if each element in [__first2,__last2) is contained
2871 * in order within [__first1,__last1) according to comp. False
2872 * otherwise. @ingroup set_algorithms
2873 *
2874 * This operation expects both [__first1,__last1) and
2875 * [__first2,__last2) to be sorted. Searches for the presence of
2876 * each element in [__first2,__last2) within [__first1,__last1),
2877 * using comp to decide. The iterators over each range only move
2878 * forward, so this is a linear algorithm. If an element in
2879 * [__first2,__last2) is not found before the search iterator
2880 * reaches @p __last2, false is returned.
2881 */
2882 template<typename _InputIterator1, typename _InputIterator2,
2883 typename _Compare>
2884 _GLIBCXX20_CONSTEXPR
2885 inline bool
2886 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2887 _InputIterator2 __first2, _InputIterator2 __last2,
2888 _Compare __comp)
2889 {
2890 // concept requirements
2891 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2893 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2894 typename iterator_traits<_InputIterator1>::value_type,
2895 typename iterator_traits<_InputIterator2>::value_type>)
2896 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2897 typename iterator_traits<_InputIterator2>::value_type,
2898 typename iterator_traits<_InputIterator1>::value_type>)
2899 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2900 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2901 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2902 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2903
2904 return std::__includes(__first1, __last1, __first2, __last2,
2905 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2906 }
2907
2908 // nth_element
2909 // merge
2910 // set_difference
2911 // set_intersection
2912 // set_union
2913 // stable_sort
2914 // set_symmetric_difference
2915 // min_element
2916 // max_element
2917
2918 template<typename _BidirectionalIterator, typename _Compare>
2919 _GLIBCXX20_CONSTEXPR
2920 bool
2921 __next_permutation(_BidirectionalIterator __first,
2922 _BidirectionalIterator __last, _Compare __comp)
2923 {
2924 if (__first == __last)
2925 return false;
2926 _BidirectionalIterator __i = __first;
2927 ++__i;
2928 if (__i == __last)
2929 return false;
2930 __i = __last;
2931 --__i;
2932
2933 for(;;)
2934 {
2935 _BidirectionalIterator __ii = __i;
2936 --__i;
2937 if (__comp(__i, __ii))
2938 {
2939 _BidirectionalIterator __j = __last;
2940 while (!__comp(__i, --__j))
2941 {}
2942 std::iter_swap(__i, __j);
2943 std::__reverse(__ii, __last,
2944 std::__iterator_category(__first));
2945 return true;
2946 }
2947 if (__i == __first)
2948 {
2949 std::__reverse(__first, __last,
2950 std::__iterator_category(__first));
2951 return false;
2952 }
2953 }
2954 }
2955
2956 /**
2957 * @brief Permute range into the next @e dictionary ordering.
2958 * @ingroup sorting_algorithms
2959 * @param __first Start of range.
2960 * @param __last End of range.
2961 * @return False if wrapped to first permutation, true otherwise.
2962 *
2963 * Treats all permutations of the range as a set of @e dictionary sorted
2964 * sequences. Permutes the current sequence into the next one of this set.
2965 * Returns true if there are more sequences to generate. If the sequence
2966 * is the largest of the set, the smallest is generated and false returned.
2967 */
2968 template<typename _BidirectionalIterator>
2969 _GLIBCXX20_CONSTEXPR
2970 inline bool
2971 next_permutation(_BidirectionalIterator __first,
2972 _BidirectionalIterator __last)
2973 {
2974 // concept requirements
2975 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2976 _BidirectionalIterator>)
2977 __glibcxx_function_requires(_LessThanComparableConcept<
2978 typename iterator_traits<_BidirectionalIterator>::value_type>)
2979 __glibcxx_requires_valid_range(__first, __last);
2980 __glibcxx_requires_irreflexive(__first, __last);
2981
2982 return std::__next_permutation
2983 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2984 }
2985
2986 /**
2987 * @brief Permute range into the next @e dictionary ordering using
2988 * comparison functor.
2989 * @ingroup sorting_algorithms
2990 * @param __first Start of range.
2991 * @param __last End of range.
2992 * @param __comp A comparison functor.
2993 * @return False if wrapped to first permutation, true otherwise.
2994 *
2995 * Treats all permutations of the range [__first,__last) as a set of
2996 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2997 * sequence into the next one of this set. Returns true if there are more
2998 * sequences to generate. If the sequence is the largest of the set, the
2999 * smallest is generated and false returned.
3000 */
3001 template<typename _BidirectionalIterator, typename _Compare>
3002 _GLIBCXX20_CONSTEXPR
3003 inline bool
3004 next_permutation(_BidirectionalIterator __first,
3005 _BidirectionalIterator __last, _Compare __comp)
3006 {
3007 // concept requirements
3008 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3009 _BidirectionalIterator>)
3010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3011 typename iterator_traits<_BidirectionalIterator>::value_type,
3012 typename iterator_traits<_BidirectionalIterator>::value_type>)
3013 __glibcxx_requires_valid_range(__first, __last);
3014 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3015
3016 return std::__next_permutation
3017 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3018 }
3019
3020 template<typename _BidirectionalIterator, typename _Compare>
3021 _GLIBCXX20_CONSTEXPR
3022 bool
3023 __prev_permutation(_BidirectionalIterator __first,
3024 _BidirectionalIterator __last, _Compare __comp)
3025 {
3026 if (__first == __last)
3027 return false;
3028 _BidirectionalIterator __i = __first;
3029 ++__i;
3030 if (__i == __last)
3031 return false;
3032 __i = __last;
3033 --__i;
3034
3035 for(;;)
3036 {
3037 _BidirectionalIterator __ii = __i;
3038 --__i;
3039 if (__comp(__ii, __i))
3040 {
3041 _BidirectionalIterator __j = __last;
3042 while (!__comp(--__j, __i))
3043 {}
3044 std::iter_swap(__i, __j);
3045 std::__reverse(__ii, __last,
3046 std::__iterator_category(__first));
3047 return true;
3048 }
3049 if (__i == __first)
3050 {
3051 std::__reverse(__first, __last,
3052 std::__iterator_category(__first));
3053 return false;
3054 }
3055 }
3056 }
3057
3058 /**
3059 * @brief Permute range into the previous @e dictionary ordering.
3060 * @ingroup sorting_algorithms
3061 * @param __first Start of range.
3062 * @param __last End of range.
3063 * @return False if wrapped to last permutation, true otherwise.
3064 *
3065 * Treats all permutations of the range as a set of @e dictionary sorted
3066 * sequences. Permutes the current sequence into the previous one of this
3067 * set. Returns true if there are more sequences to generate. If the
3068 * sequence is the smallest of the set, the largest is generated and false
3069 * returned.
3070 */
3071 template<typename _BidirectionalIterator>
3072 _GLIBCXX20_CONSTEXPR
3073 inline bool
3074 prev_permutation(_BidirectionalIterator __first,
3075 _BidirectionalIterator __last)
3076 {
3077 // concept requirements
3078 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3079 _BidirectionalIterator>)
3080 __glibcxx_function_requires(_LessThanComparableConcept<
3081 typename iterator_traits<_BidirectionalIterator>::value_type>)
3082 __glibcxx_requires_valid_range(__first, __last);
3083 __glibcxx_requires_irreflexive(__first, __last);
3084
3085 return std::__prev_permutation(__first, __last,
3086 __gnu_cxx::__ops::__iter_less_iter());
3087 }
3088
3089 /**
3090 * @brief Permute range into the previous @e dictionary ordering using
3091 * comparison functor.
3092 * @ingroup sorting_algorithms
3093 * @param __first Start of range.
3094 * @param __last End of range.
3095 * @param __comp A comparison functor.
3096 * @return False if wrapped to last permutation, true otherwise.
3097 *
3098 * Treats all permutations of the range [__first,__last) as a set of
3099 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3100 * sequence into the previous one of this set. Returns true if there are
3101 * more sequences to generate. If the sequence is the smallest of the set,
3102 * the largest is generated and false returned.
3103 */
3104 template<typename _BidirectionalIterator, typename _Compare>
3105 _GLIBCXX20_CONSTEXPR
3106 inline bool
3107 prev_permutation(_BidirectionalIterator __first,
3108 _BidirectionalIterator __last, _Compare __comp)
3109 {
3110 // concept requirements
3111 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3112 _BidirectionalIterator>)
3113 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3114 typename iterator_traits<_BidirectionalIterator>::value_type,
3115 typename iterator_traits<_BidirectionalIterator>::value_type>)
3116 __glibcxx_requires_valid_range(__first, __last);
3117 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3118
3119 return std::__prev_permutation(__first, __last,
3120 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3121 }
3122
3123 // replace
3124 // replace_if
3125
3126 template<typename _InputIterator, typename _OutputIterator,
3127 typename _Predicate, typename _Tp>
3128 _GLIBCXX20_CONSTEXPR
3129 _OutputIterator
3130 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3131 _OutputIterator __result,
3132 _Predicate __pred, const _Tp& __new_value)
3133 {
3134 for (; __first != __last; ++__first, (void)++__result)
3135 if (__pred(__first))
3136 *__result = __new_value;
3137 else
3138 *__result = *__first;
3139 return __result;
3140 }
3141
3142 /**
3143 * @brief Copy a sequence, replacing each element of one value with another
3144 * value.
3145 * @param __first An input iterator.
3146 * @param __last An input iterator.
3147 * @param __result An output iterator.
3148 * @param __old_value The value to be replaced.
3149 * @param __new_value The replacement value.
3150 * @return The end of the output sequence, @p result+(last-first).
3151 *
3152 * Copies each element in the input range @p [__first,__last) to the
3153 * output range @p [__result,__result+(__last-__first)) replacing elements
3154 * equal to @p __old_value with @p __new_value.
3155 */
3156 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3157 _GLIBCXX20_CONSTEXPR
3158 inline _OutputIterator
3159 replace_copy(_InputIterator __first, _InputIterator __last,
3160 _OutputIterator __result,
3161 const _Tp& __old_value, const _Tp& __new_value)
3162 {
3163 // concept requirements
3164 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3165 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3166 typename iterator_traits<_InputIterator>::value_type>)
3167 __glibcxx_function_requires(_EqualOpConcept<
3168 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3169 __glibcxx_requires_valid_range(__first, __last);
3170
3171 return std::__replace_copy_if(__first, __last, __result,
3172 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3173 __new_value);
3174 }
3175
3176 /**
3177 * @brief Copy a sequence, replacing each value for which a predicate
3178 * returns true with another value.
3179 * @ingroup mutating_algorithms
3180 * @param __first An input iterator.
3181 * @param __last An input iterator.
3182 * @param __result An output iterator.
3183 * @param __pred A predicate.
3184 * @param __new_value The replacement value.
3185 * @return The end of the output sequence, @p __result+(__last-__first).
3186 *
3187 * Copies each element in the range @p [__first,__last) to the range
3188 * @p [__result,__result+(__last-__first)) replacing elements for which
3189 * @p __pred returns true with @p __new_value.
3190 */
3191 template<typename _InputIterator, typename _OutputIterator,
3192 typename _Predicate, typename _Tp>
3193 _GLIBCXX20_CONSTEXPR
3194 inline _OutputIterator
3195 replace_copy_if(_InputIterator __first, _InputIterator __last,
3196 _OutputIterator __result,
3197 _Predicate __pred, const _Tp& __new_value)
3198 {
3199 // concept requirements
3200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3202 typename iterator_traits<_InputIterator>::value_type>)
3203 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3204 typename iterator_traits<_InputIterator>::value_type>)
3205 __glibcxx_requires_valid_range(__first, __last);
3206
3207 return std::__replace_copy_if(__first, __last, __result,
3208 __gnu_cxx::__ops::__pred_iter(__pred),
3209 __new_value);
3210 }
3211
3212#if __cplusplus201703L >= 201103L
3213 /**
3214 * @brief Determines whether the elements of a sequence are sorted.
3215 * @ingroup sorting_algorithms
3216 * @param __first An iterator.
3217 * @param __last Another iterator.
3218 * @return True if the elements are sorted, false otherwise.
3219 */
3220 template<typename _ForwardIterator>
3221 _GLIBCXX20_CONSTEXPR
3222 inline bool
3223 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3224 { return std::is_sorted_until(__first, __last) == __last; }
3225
3226 /**
3227 * @brief Determines whether the elements of a sequence are sorted
3228 * according to a comparison functor.
3229 * @ingroup sorting_algorithms
3230 * @param __first An iterator.
3231 * @param __last Another iterator.
3232 * @param __comp A comparison functor.
3233 * @return True if the elements are sorted, false otherwise.
3234 */
3235 template<typename _ForwardIterator, typename _Compare>
3236 _GLIBCXX20_CONSTEXPR
3237 inline bool
3238 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3239 _Compare __comp)
3240 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3241
3242 template<typename _ForwardIterator, typename _Compare>
3243 _GLIBCXX20_CONSTEXPR
3244 _ForwardIterator
3245 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3246 _Compare __comp)
3247 {
3248 if (__first == __last)
3249 return __last;
3250
3251 _ForwardIterator __next = __first;
3252 for (++__next; __next != __last; __first = __next, (void)++__next)
3253 if (__comp(__next, __first))
3254 return __next;
3255 return __next;
3256 }
3257
3258 /**
3259 * @brief Determines the end of a sorted sequence.
3260 * @ingroup sorting_algorithms
3261 * @param __first An iterator.
3262 * @param __last Another iterator.
3263 * @return An iterator pointing to the last iterator i in [__first, __last)
3264 * for which the range [__first, i) is sorted.
3265 */
3266 template<typename _ForwardIterator>
3267 _GLIBCXX20_CONSTEXPR
3268 inline _ForwardIterator
3269 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3270 {
3271 // concept requirements
3272 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3273 __glibcxx_function_requires(_LessThanComparableConcept<
3274 typename iterator_traits<_ForwardIterator>::value_type>)
3275 __glibcxx_requires_valid_range(__first, __last);
3276 __glibcxx_requires_irreflexive(__first, __last);
3277
3278 return std::__is_sorted_until(__first, __last,
3279 __gnu_cxx::__ops::__iter_less_iter());
3280 }
3281
3282 /**
3283 * @brief Determines the end of a sorted sequence using comparison functor.
3284 * @ingroup sorting_algorithms
3285 * @param __first An iterator.
3286 * @param __last Another iterator.
3287 * @param __comp A comparison functor.
3288 * @return An iterator pointing to the last iterator i in [__first, __last)
3289 * for which the range [__first, i) is sorted.
3290 */
3291 template<typename _ForwardIterator, typename _Compare>
3292 _GLIBCXX20_CONSTEXPR
3293 inline _ForwardIterator
3294 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3295 _Compare __comp)
3296 {
3297 // concept requirements
3298 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3299 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3300 typename iterator_traits<_ForwardIterator>::value_type,
3301 typename iterator_traits<_ForwardIterator>::value_type>)
3302 __glibcxx_requires_valid_range(__first, __last);
3303 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3304
3305 return std::__is_sorted_until(__first, __last,
3306 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3307 }
3308
3309 /**
3310 * @brief Determines min and max at once as an ordered pair.
3311 * @ingroup sorting_algorithms
3312 * @param __a A thing of arbitrary type.
3313 * @param __b Another thing of arbitrary type.
3314 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3315 * __b) otherwise.
3316 */
3317 template<typename _Tp>
3318 _GLIBCXX14_CONSTEXPRconstexpr
3319 inline pair<const _Tp&, const _Tp&>
3320 minmax(const _Tp& __a, const _Tp& __b)
3321 {
3322 // concept requirements
3323 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3324
3325 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3326 : pair<const _Tp&, const _Tp&>(__a, __b);
3327 }
3328
3329 /**
3330 * @brief Determines min and max at once as an ordered pair.
3331 * @ingroup sorting_algorithms
3332 * @param __a A thing of arbitrary type.
3333 * @param __b Another thing of arbitrary type.
3334 * @param __comp A @link comparison_functors comparison functor @endlink.
3335 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3336 * __b) otherwise.
3337 */
3338 template<typename _Tp, typename _Compare>
3339 _GLIBCXX14_CONSTEXPRconstexpr
3340 inline pair<const _Tp&, const _Tp&>
3341 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3342 {
3343 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3344 : pair<const _Tp&, const _Tp&>(__a, __b);
3345 }
3346
3347 template<typename _ForwardIterator, typename _Compare>
3348