Bug Summary

File:llvm/lib/MCA/HardwareUnits/ResourceManager.cpp
Warning:line 71, column 29
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'unsigned long long'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ResourceManager.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D 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-14/lib/clang/14.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 -O2 -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 -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -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-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp

→
1//===--------------------- ResourceManager.cpp ------------------*- 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/// \file
9///
10/// The classes here represent processor resource units and their management
11/// strategy. These classes are managed by the Scheduler.
12///
13//===----------------------------------------------------------------------===//
14
15#include "llvm/MCA/HardwareUnits/ResourceManager.h"
16#include "llvm/MCA/Support.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/raw_ostream.h"
19
20namespace llvm {
21namespace mca {
22
23#define DEBUG_TYPE"llvm-mca" "llvm-mca"
24ResourceStrategy::~ResourceStrategy() = default;
25
26static uint64_t selectImpl(uint64_t CandidateMask,
27 uint64_t &NextInSequenceMask) {
28 // The upper bit set in CandidateMask identifies our next candidate resource.
29 CandidateMask = 1ULL << getResourceStateIndex(CandidateMask);
30 NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
31 return CandidateMask;
32}
33
34uint64_t DefaultResourceStrategy::select(uint64_t ReadyMask) {
35 // This method assumes that ReadyMask cannot be zero.
36 uint64_t CandidateMask = ReadyMask & NextInSequenceMask;
37 if (CandidateMask)
38 return selectImpl(CandidateMask, NextInSequenceMask);
39
40 NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
41 RemovedFromNextInSequence = 0;
42 CandidateMask = ReadyMask & NextInSequenceMask;
43 if (CandidateMask)
44 return selectImpl(CandidateMask, NextInSequenceMask);
45
46 NextInSequenceMask = ResourceUnitMask;
47 CandidateMask = ReadyMask & NextInSequenceMask;
48 return selectImpl(CandidateMask, NextInSequenceMask);
49}
50
51void DefaultResourceStrategy::used(uint64_t Mask) {
52 if (Mask > NextInSequenceMask) {
53 RemovedFromNextInSequence |= Mask;
54 return;
55 }
56
57 NextInSequenceMask &= (~Mask);
58 if (NextInSequenceMask)
59 return;
60
61 NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
62 RemovedFromNextInSequence = 0;
63}
64
65ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
66 uint64_t Mask)
67 : ProcResourceDescIndex(Index), ResourceMask(Mask),
68 BufferSize(Desc.BufferSize), IsAGroup(countPopulation(ResourceMask) > 1) {
8
←
Assuming the condition is true
→
69 if (IsAGroup
8.1
Field 'IsAGroup' is true
8.1
Field 'IsAGroup' is true
8.1
Field 'IsAGroup' is true
8.1
Field 'IsAGroup' is true
) {
9
←
Taking true branch
→
70 ResourceSizeMask =
71 ResourceMask ^ 1ULL << getResourceStateIndex(ResourceMask);
10
←
Calling 'getResourceStateIndex'
→
12
←
Returning from 'getResourceStateIndex'
→
13
←
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'unsigned long long'
72 } else {
73 ResourceSizeMask = (1ULL << Desc.NumUnits) - 1;
74 }
75 ReadyMask = ResourceSizeMask;
76 AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
77 Unavailable = false;
78}
79
80bool ResourceState::isReady(unsigned NumUnits) const {
81 return (!isReserved() || isADispatchHazard()) &&
82 countPopulation(ReadyMask) >= NumUnits;
83}
84
85ResourceStateEvent ResourceState::isBufferAvailable() const {
86 if (isADispatchHazard() && isReserved())
87 return RS_RESERVED;
88 if (!isBuffered() || AvailableSlots)
89 return RS_BUFFER_AVAILABLE;
90 return RS_BUFFER_UNAVAILABLE;
91}
92
93#ifndef NDEBUG1
94void ResourceState::dump() const {
95 dbgs() << "MASK=" << format_hex(ResourceMask, 16)
96 << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
97 << ", RDYMASK=" << format_hex(ReadyMask, 16)
98 << ", BufferSize=" << BufferSize
99 << ", AvailableSlots=" << AvailableSlots
100 << ", Reserved=" << Unavailable << '\n';
101}
102#endif
103
104static std::unique_ptr<ResourceStrategy>
105getStrategyFor(const ResourceState &RS) {
106 if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
107 return std::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
108 return std::unique_ptr<ResourceStrategy>(nullptr);
109}
110
111ResourceManager::ResourceManager(const MCSchedModel &SM)
112 : Resources(SM.getNumProcResourceKinds() - 1),
113 Strategies(SM.getNumProcResourceKinds() - 1),
114 Resource2Groups(SM.getNumProcResourceKinds() - 1, 0),
115 ProcResID2Mask(SM.getNumProcResourceKinds(), 0),
116 ResIndex2ProcResID(SM.getNumProcResourceKinds() - 1, 0),
117 ProcResUnitMask(0), ReservedResourceGroups(0), AvailableBuffers(~0ULL),
118 ReservedBuffers(0) {
119 computeProcResourceMasks(SM, ProcResID2Mask);
120
121 // initialize vector ResIndex2ProcResID.
122 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
1
Assuming 'I' is < 'E'
→
2
←
Loop condition is true. Entering loop body
→
3
←
Assuming 'I' is >= 'E'
→
4
←
Loop condition is false. Execution continues on line 127
→
123 unsigned Index = getResourceStateIndex(ProcResID2Mask[I]);
124 ResIndex2ProcResID[Index] = I;
125 }
126
127 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
5
←
Loop condition is true. Entering loop body
→
128 uint64_t Mask = ProcResID2Mask[I];
129 unsigned Index = getResourceStateIndex(Mask);
130 Resources[Index] =
131 std::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
6
←
Calling 'make_unique<llvm::mca::ResourceState, const llvm::MCProcResourceDesc &, unsigned int &, unsigned long &>'
→
132 Strategies[Index] = getStrategyFor(*Resources[Index]);
133 }
134
135 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
136 uint64_t Mask = ProcResID2Mask[I];
137 unsigned Index = getResourceStateIndex(Mask);
138 const ResourceState &RS = *Resources[Index];
139 if (!RS.isAResourceGroup()) {
140 ProcResUnitMask |= Mask;
141 continue;
142 }
143
144 uint64_t GroupMaskIdx = 1ULL << Index;
145 Mask -= GroupMaskIdx;
146 while (Mask) {
147 // Extract lowest set isolated bit.
148 uint64_t Unit = Mask & (-Mask);
149 unsigned IndexUnit = getResourceStateIndex(Unit);
150 Resource2Groups[IndexUnit] |= GroupMaskIdx;
151 Mask ^= Unit;
152 }
153 }
154
155 AvailableProcResUnits = ProcResUnitMask;
156}
157
158void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
159 uint64_t ResourceMask) {
160 unsigned Index = getResourceStateIndex(ResourceMask);
161 assert(Index < Resources.size() && "Invalid processor resource index!")(static_cast<void> (0));
162 assert(S && "Unexpected null strategy in input!")(static_cast<void> (0));
163 Strategies[Index] = std::move(S);
164}
165
166unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167 return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168}
169
170unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
171 return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
172}
173
174// Returns the actual resource consumed by this Use.
175// First, is the primary resource ID.
176// Second, is the specific sub-resource ID.
177ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
178 unsigned Index = getResourceStateIndex(ResourceID);
179 assert(Index < Resources.size() && "Invalid resource use!")(static_cast<void> (0));
180 ResourceState &RS = *Resources[Index];
181 assert(RS.isReady() && "No available units to select!")(static_cast<void> (0));
182
183 // Special case where RS is not a group, and it only declares a single
184 // resource unit.
185 if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
186 return std::make_pair(ResourceID, RS.getReadyMask());
187
188 uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
189 if (RS.isAResourceGroup())
190 return selectPipe(SubResourceID);
191 return std::make_pair(ResourceID, SubResourceID);
192}
193
194void ResourceManager::use(const ResourceRef &RR) {
195 // Mark the sub-resource referenced by RR as used.
196 unsigned RSID = getResourceStateIndex(RR.first);
197 ResourceState &RS = *Resources[RSID];
198 RS.markSubResourceAsUsed(RR.second);
199 // Remember to update the resource strategy for non-group resources with
200 // multiple units.
201 if (RS.getNumUnits() > 1)
202 Strategies[RSID]->used(RR.second);
203
204 // If there are still available units in RR.first,
205 // then we are done.
206 if (RS.isReady())
207 return;
208
209 AvailableProcResUnits ^= RR.first;
210
211 // Notify groups that RR.first is no longer available.
212 uint64_t Users = Resource2Groups[RSID];
213 while (Users) {
214 // Extract lowest set isolated bit.
215 unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
216 ResourceState &CurrentUser = *Resources[GroupIndex];
217 CurrentUser.markSubResourceAsUsed(RR.first);
218 Strategies[GroupIndex]->used(RR.first);
219 // Reset lowest set bit.
220 Users &= Users - 1;
221 }
222}
223
224void ResourceManager::release(const ResourceRef &RR) {
225 unsigned RSID = getResourceStateIndex(RR.first);
226 ResourceState &RS = *Resources[RSID];
227 bool WasFullyUsed = !RS.isReady();
228 RS.releaseSubResource(RR.second);
229 if (!WasFullyUsed)
230 return;
231
232 AvailableProcResUnits ^= RR.first;
233
234 // Notify groups that RR.first is now available again.
235 uint64_t Users = Resource2Groups[RSID];
236 while (Users) {
237 unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
238 ResourceState &CurrentUser = *Resources[GroupIndex];
239 CurrentUser.releaseSubResource(RR.first);
240 Users &= Users - 1;
241 }
242}
243
244ResourceStateEvent
245ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
246 if (ConsumedBuffers & ReservedBuffers)
247 return ResourceStateEvent::RS_RESERVED;
248 if (ConsumedBuffers & (~AvailableBuffers))
249 return ResourceStateEvent::RS_BUFFER_UNAVAILABLE;
250 return ResourceStateEvent::RS_BUFFER_AVAILABLE;
251}
252
253void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
254 while (ConsumedBuffers) {
255 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
256 ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
257 ConsumedBuffers ^= CurrentBuffer;
258 assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE)(static_cast<void> (0));
259 if (!RS.reserveBuffer())
260 AvailableBuffers ^= CurrentBuffer;
261 if (RS.isADispatchHazard()) {
262 // Reserve this buffer now, and release it once pipeline resources
263 // consumed by the instruction become available again.
264 // We do this to simulate an in-order dispatch/issue of instructions.
265 ReservedBuffers ^= CurrentBuffer;
266 }
267 }
268}
269
270void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
271 AvailableBuffers |= ConsumedBuffers;
272 while (ConsumedBuffers) {
273 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
274 ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
275 ConsumedBuffers ^= CurrentBuffer;
276 RS.releaseBuffer();
277 // Do not unreserve dispatch hazard resource buffers. Wait until all
278 // pipeline resources have been freed too.
279 }
280}
281
282uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
283 uint64_t BusyResourceMask = 0;
284 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
285 unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
286 unsigned Index = getResourceStateIndex(E.first);
287 if (!Resources[Index]->isReady(NumUnits))
288 BusyResourceMask |= E.first;
289 }
290
291 uint64_t ImplicitUses = Desc.ImplicitlyUsedProcResUnits;
292 while (ImplicitUses) {
293 uint64_t Use = ImplicitUses & -ImplicitUses;
294 ImplicitUses ^= Use;
295 unsigned Index = getResourceStateIndex(Use);
296 if (!Resources[Index]->isReady(/* NumUnits */ 1))
297 BusyResourceMask |= Index;
298 }
299
300 BusyResourceMask &= ProcResUnitMask;
301 if (BusyResourceMask)
302 return BusyResourceMask;
303 return Desc.UsedProcResGroups & ReservedResourceGroups;
304}
305
306void ResourceManager::issueInstruction(
307 const InstrDesc &Desc,
308 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
309 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
310 const CycleSegment &CS = R.second.CS;
311 if (!CS.size()) {
312 releaseResource(R.first);
313 continue;
314 }
315
316 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!")(static_cast<void> (0));
317 if (!R.second.isReserved()) {
318 ResourceRef Pipe = selectPipe(R.first);
319 use(Pipe);
320 BusyResources[Pipe] += CS.size();
321 Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
322 Pipe, ResourceCycles(CS.size())));
323 } else {
324 assert((countPopulation(R.first) > 1) && "Expected a group!")(static_cast<void> (0));
325 // Mark this group as reserved.
326 assert(R.second.isReserved())(static_cast<void> (0));
327 reserveResource(R.first);
328 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
329 }
330 }
331}
332
333void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
334 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
335 if (BR.second)
336 BR.second--;
337 if (!BR.second) {
338 // Release this resource.
339 const ResourceRef &RR = BR.first;
340
341 if (countPopulation(RR.first) == 1)
342 release(RR);
343 releaseResource(RR.first);
344 ResourcesFreed.push_back(RR);
345 }
346 }
347
348 for (const ResourceRef &RF : ResourcesFreed)
349 BusyResources.erase(RF);
350}
351
352void ResourceManager::reserveResource(uint64_t ResourceID) {
353 const unsigned Index = getResourceStateIndex(ResourceID);
354 ResourceState &Resource = *Resources[Index];
355 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&(static_cast<void> (0))
356 "Unexpected resource state found!")(static_cast<void> (0));
357 Resource.setReserved();
358 ReservedResourceGroups ^= 1ULL << Index;
359}
360
361void ResourceManager::releaseResource(uint64_t ResourceID) {
362 const unsigned Index = getResourceStateIndex(ResourceID);
363 ResourceState &Resource = *Resources[Index];
364 Resource.clearReserved();
365 if (Resource.isAResourceGroup())
366 ReservedResourceGroups ^= 1ULL << Index;
367 // Now it is safe to release dispatch/issue resources.
368 if (Resource.isADispatchHazard())
369 ReservedBuffers ^= 1ULL << Index;
370}
371
372} // namespace mca
373} // namespace llvm
←

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

→
1// Vector 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_vector.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{vector}
54 */
55
56#ifndef _STL_VECTOR_H1
57#define _STL_VECTOR_H1 1
58
59#include <bits/stl_iterator_base_funcs.h>
60#include <bits/functexcept.h>
61#include <bits/concept_check.h>
62#if __cplusplus201402L >= 201103L
63#include <initializer_list>
64#endif
65#if __cplusplus201402L > 201703L
66# include <compare>
67#endif
68
69#include <debug/assertions.h>
70
71#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
72extern "C" void
73__sanitizer_annotate_contiguous_container(const void*, const void*,
74 const void*, const void*);
75#endif
76
77namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
78{
79_GLIBCXX_BEGIN_NAMESPACE_VERSION
80_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
81
82 /// See bits/stl_deque.h's _Deque_base for an explanation.
83 template<typename _Tp, typename _Alloc>
84 struct _Vector_base
85 {
86 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
87 rebind<_Tp>::other _Tp_alloc_type;
88 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
89 pointer;
90
91 struct _Vector_impl_data
92 {
93 pointer _M_start;
94 pointer _M_finish;
95 pointer _M_end_of_storage;
96
97 _Vector_impl_data() _GLIBCXX_NOEXCEPTnoexcept
98 : _M_start(), _M_finish(), _M_end_of_storage()
99 { }
100
101#if __cplusplus201402L >= 201103L
102 _Vector_impl_data(_Vector_impl_data&& __x) noexcept
103 : _M_start(__x._M_start), _M_finish(__x._M_finish),
104 _M_end_of_storage(__x._M_end_of_storage)
105 { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); }
106#endif
107
108 void
109 _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPTnoexcept
110 {
111 _M_start = __x._M_start;
112 _M_finish = __x._M_finish;
113 _M_end_of_storage = __x._M_end_of_storage;
114 }
115
116 void
117 _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPTnoexcept
118 {
119 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
120 // information used by TBAA.
121 _Vector_impl_data __tmp;
122 __tmp._M_copy_data(*this);
123 _M_copy_data(__x);
124 __x._M_copy_data(__tmp);
125 }
126 };
127
128 struct _Vector_impl
129 : public _Tp_alloc_type, public _Vector_impl_data
130 {
131 _Vector_impl() _GLIBCXX_NOEXCEPT_IF(noexcept(is_nothrow_default_constructible<_Tp_alloc_type>
::value)
132 is_nothrow_default_constructible<_Tp_alloc_type>::value)noexcept(is_nothrow_default_constructible<_Tp_alloc_type>
::value)
133 : _Tp_alloc_type()
134 { }
135
136 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPTnoexcept
137 : _Tp_alloc_type(__a)
138 { }
139
140#if __cplusplus201402L >= 201103L
141 // Not defaulted, to enforce noexcept(true) even when
142 // !is_nothrow_move_constructible<_Tp_alloc_type>.
143 _Vector_impl(_Vector_impl&& __x) noexcept
144 : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x))
145 { }
146
147 _Vector_impl(_Tp_alloc_type&& __a) noexcept
148 : _Tp_alloc_type(std::move(__a))
149 { }
150
151 _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept
152 : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv))
153 { }
154#endif
155
156#if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
157 template<typename = _Tp_alloc_type>
158 struct _Asan
159 {
160 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>
161 ::size_type size_type;
162
163 static void _S_shrink(_Vector_impl&, size_type) { }
164 static void _S_on_dealloc(_Vector_impl&) { }
165
166 typedef _Vector_impl& _Reinit;
167
168 struct _Grow
169 {
170 _Grow(_Vector_impl&, size_type) { }
171 void _M_grew(size_type) { }
172 };
173 };
174
175 // Enable ASan annotations for memory obtained from std::allocator.
176 template<typename _Up>
177 struct _Asan<allocator<_Up> >
178 {
179 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>
180 ::size_type size_type;
181
182 // Adjust ASan annotation for [_M_start, _M_end_of_storage) to
183 // mark end of valid region as __curr instead of __prev.
184 static void
185 _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr)
186 {
187 __sanitizer_annotate_contiguous_container(__impl._M_start,
188 __impl._M_end_of_storage, __prev, __curr);
189 }
190
191 static void
192 _S_grow(_Vector_impl& __impl, size_type __n)
193 { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); }
194
195 static void
196 _S_shrink(_Vector_impl& __impl, size_type __n)
197 { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); }
198
199 static void
200 _S_on_dealloc(_Vector_impl& __impl)
201 {
202 if (__impl._M_start)
203 _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage);
204 }
205
206 // Used on reallocation to tell ASan unused capacity is invalid.
207 struct _Reinit
208 {
209 explicit _Reinit(_Vector_impl& __impl) : _M_impl(__impl)
210 {
211 // Mark unused capacity as valid again before deallocating it.
212 _S_on_dealloc(_M_impl);
213 }
214
215 ~_Reinit()
216 {
217 // Mark unused capacity as invalid after reallocation.
218 if (_M_impl._M_start)
219 _S_adjust(_M_impl, _M_impl._M_end_of_storage,
220 _M_impl._M_finish);
221 }
222
223 _Vector_impl& _M_impl;
224
225#if __cplusplus201402L >= 201103L
226 _Reinit(const _Reinit&) = delete;
227 _Reinit& operator=(const _Reinit&) = delete;
228#endif
229 };
230
231 // Tell ASan when unused capacity is initialized to be valid.
232 struct _Grow
233 {
234 _Grow(_Vector_impl& __impl, size_type __n)
235 : _M_impl(__impl), _M_n(__n)
236 { _S_grow(_M_impl, __n); }
237
238 ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); }
239
240 void _M_grew(size_type __n) { _M_n -= __n; }
241
242#if __cplusplus201402L >= 201103L
243 _Grow(const _Grow&) = delete;
244 _Grow& operator=(const _Grow&) = delete;
245#endif
246 private:
247 _Vector_impl& _M_impl;
248 size_type _M_n;
249 };
250 };
251
252#define _GLIBCXX_ASAN_ANNOTATE_REINIT \
253 typename _Base::_Vector_impl::template _Asan<>::_Reinit const \
254 __attribute__((__unused__)) __reinit_guard(this->_M_impl)
255#define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \
256 typename _Base::_Vector_impl::template _Asan<>::_Grow \
257 __attribute__((__unused__)) __grow_guard(this->_M_impl, (n))
258#define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n)
259#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \
260 _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n)
261#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \
262 _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl)
263#else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR)
264#define _GLIBCXX_ASAN_ANNOTATE_REINIT
265#define _GLIBCXX_ASAN_ANNOTATE_GROW(n)
266#define _GLIBCXX_ASAN_ANNOTATE_GREW(n)
267#define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n)
268#define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC
269#endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR
270 };
271
272 public:
273 typedef _Alloc allocator_type;
274
275 _Tp_alloc_type&
276 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPTnoexcept
277 { return this->_M_impl; }
278
279 const _Tp_alloc_type&
280 _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPTnoexcept
281 { return this->_M_impl; }
282
283 allocator_type
284 get_allocator() const _GLIBCXX_NOEXCEPTnoexcept
285 { return allocator_type(_M_get_Tp_allocator()); }
286
287#if __cplusplus201402L >= 201103L
288 _Vector_base() = default;
289#else
290 _Vector_base() { }
291#endif
292
293 _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPTnoexcept
294 : _M_impl(__a) { }
295
296 // Kept for ABI compatibility.
297#if !_GLIBCXX_INLINE_VERSION0
298 _Vector_base(size_t __n)
299 : _M_impl()
300 { _M_create_storage(__n); }
301#endif
302
303 _Vector_base(size_t __n, const allocator_type& __a)
304 : _M_impl(__a)
305 { _M_create_storage(__n); }
306
307#if __cplusplus201402L >= 201103L
308 _Vector_base(_Vector_base&&) = default;
309
310 // Kept for ABI compatibility.
311# if !_GLIBCXX_INLINE_VERSION0
312 _Vector_base(_Tp_alloc_type&& __a) noexcept
313 : _M_impl(std::move(__a)) { }
314
315 _Vector_base(_Vector_base&& __x, const allocator_type& __a)
316 : _M_impl(__a)
317 {
318 if (__x.get_allocator() == __a)
319 this->_M_impl._M_swap_data(__x._M_impl);
320 else
321 {
322 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
323 _M_create_storage(__n);
324 }
325 }
326# endif
327
328 _Vector_base(const allocator_type& __a, _Vector_base&& __x)
329 : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl))
330 { }
331#endif
332
333 ~_Vector_base() _GLIBCXX_NOEXCEPTnoexcept
334 {
335 _M_deallocate(_M_impl._M_start,
336 _M_impl._M_end_of_storage - _M_impl._M_start);
337 }
338
339 public:
340 _Vector_impl _M_impl;
341
342 pointer
343 _M_allocate(size_t __n)
344 {
345 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
346 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
347 }
348
349 void
350 _M_deallocate(pointer __p, size_t __n)
351 {
352 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
353 if (__p)
354 _Tr::deallocate(_M_impl, __p, __n);
355 }
356
357 protected:
358 void
359 _M_create_storage(size_t __n)
360 {
361 this->_M_impl._M_start = this->_M_allocate(__n);
362 this->_M_impl._M_finish = this->_M_impl._M_start;
363 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
364 }
365 };
366
367 /**
368 * @brief A standard container which offers fixed time access to
369 * individual elements in any order.
370 *
371 * @ingroup sequences
372 *
373 * @tparam _Tp Type of element.
374 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
375 *
376 * Meets the requirements of a <a href="tables.html#65">container</a>, a
377 * <a href="tables.html#66">reversible container</a>, and a
378 * <a href="tables.html#67">sequence</a>, including the
379 * <a href="tables.html#68">optional sequence requirements</a> with the
380 * %exception of @c push_front and @c pop_front.
381 *
382 * In some terminology a %vector can be described as a dynamic
383 * C-style array, it offers fast and efficient access to individual
384 * elements in any order and saves the user from worrying about
385 * memory and size allocation. Subscripting ( @c [] ) access is
386 * also provided as with C-style arrays.
387 */
388 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
389 class vector : protected _Vector_base<_Tp, _Alloc>
390 {
391#ifdef _GLIBCXX_CONCEPT_CHECKS
392 // Concept requirements.
393 typedef typename _Alloc::value_type _Alloc_value_type;
394# if __cplusplus201402L < 201103L
395 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
396# endif
397 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
398#endif
399
400#if __cplusplus201402L >= 201103L
401 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
402 "std::vector must have a non-const, non-volatile value_type");
403# if __cplusplus201402L > 201703L || defined __STRICT_ANSI__1
404 static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
405 "std::vector must have the same value_type as its allocator");
406# endif
407#endif
408
409 typedef _Vector_base<_Tp, _Alloc> _Base;
410 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
411 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
412
413 public:
414 typedef _Tp value_type;
415 typedef typename _Base::pointer pointer;
416 typedef typename _Alloc_traits::const_pointer const_pointer;
417 typedef typename _Alloc_traits::reference reference;
418 typedef typename _Alloc_traits::const_reference const_reference;
419 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
420 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
421 const_iterator;
422 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
423 typedef std::reverse_iterator<iterator> reverse_iterator;
424 typedef size_t size_type;
425 typedef ptrdiff_t difference_type;
426 typedef _Alloc allocator_type;
427
428 private:
429#if __cplusplus201402L >= 201103L
430 static constexpr bool
431 _S_nothrow_relocate(true_type)
432 {
433 return noexcept(std::__relocate_a(std::declval<pointer>(),
434 std::declval<pointer>(),
435 std::declval<pointer>(),
436 std::declval<_Tp_alloc_type&>()));
437 }
438
439 static constexpr bool
440 _S_nothrow_relocate(false_type)
441 { return false; }
442
443 static constexpr bool
444 _S_use_relocate()
445 {
446 // Instantiating std::__relocate_a might cause an error outside the
447 // immediate context (in __relocate_object_a's noexcept-specifier),
448 // so only do it if we know the type can be move-inserted into *this.
449 return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{});
450 }
451
452 static pointer
453 _S_do_relocate(pointer __first, pointer __last, pointer __result,
454 _Tp_alloc_type& __alloc, true_type) noexcept
455 {
456 return std::__relocate_a(__first, __last, __result, __alloc);
457 }
458
459 static pointer
460 _S_do_relocate(pointer, pointer, pointer __result,
461 _Tp_alloc_type&, false_type) noexcept
462 { return __result; }
463
464 static pointer
465 _S_relocate(pointer __first, pointer __last, pointer __result,
466 _Tp_alloc_type& __alloc) noexcept
467 {
468 using __do_it = __bool_constant<_S_use_relocate()>;
469 return _S_do_relocate(__first, __last, __result, __alloc, __do_it{});
470 }
471#endif // C++11
472
473 protected:
474 using _Base::_M_allocate;
475 using _Base::_M_deallocate;
476 using _Base::_M_impl;
477 using _Base::_M_get_Tp_allocator;
478
479 public:
480 // [23.2.4.1] construct/copy/destroy
481 // (assign() and get_allocator() are also listed in this section)
482
483 /**
484 * @brief Creates a %vector with no elements.
485 */
486#if __cplusplus201402L >= 201103L
487 vector() = default;
488#else
489 vector() { }
490#endif
491
492 /**
493 * @brief Creates a %vector with no elements.
494 * @param __a An allocator object.
495 */
496 explicit
497 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPTnoexcept
498 : _Base(__a) { }
499
500#if __cplusplus201402L >= 201103L
501 /**
502 * @brief Creates a %vector with default constructed elements.
503 * @param __n The number of elements to initially create.
504 * @param __a An allocator.
505 *
506 * This constructor fills the %vector with @a __n default
507 * constructed elements.
508 */
509 explicit
510 vector(size_type __n, const allocator_type& __a = allocator_type())
511 : _Base(_S_check_init_len(__n, __a), __a)
512 { _M_default_initialize(__n); }
513
514 /**
515 * @brief Creates a %vector with copies of an exemplar element.
516 * @param __n The number of elements to initially create.
517 * @param __value An element to copy.
518 * @param __a An allocator.
519 *
520 * This constructor fills the %vector with @a __n copies of @a __value.
521 */
522 vector(size_type __n, const value_type& __value,
523 const allocator_type& __a = allocator_type())
524 : _Base(_S_check_init_len(__n, __a), __a)
525 { _M_fill_initialize(__n, __value); }
526#else
527 /**
528 * @brief Creates a %vector with copies of an exemplar element.
529 * @param __n The number of elements to initially create.
530 * @param __value An element to copy.
531 * @param __a An allocator.
532 *
533 * This constructor fills the %vector with @a __n copies of @a __value.
534 */
535 explicit
536 vector(size_type __n, const value_type& __value = value_type(),
537 const allocator_type& __a = allocator_type())
538 : _Base(_S_check_init_len(__n, __a), __a)
539 { _M_fill_initialize(__n, __value); }
540#endif
541
542 /**
543 * @brief %Vector copy constructor.
544 * @param __x A %vector of identical element and allocator types.
545 *
546 * All the elements of @a __x are copied, but any unused capacity in
547 * @a __x will not be copied
548 * (i.e. capacity() == size() in the new %vector).
549 *
550 * The newly-created %vector uses a copy of the allocator object used
551 * by @a __x (unless the allocator traits dictate a different object).
552 */
553 vector(const vector& __x)
554 : _Base(__x.size(),
555 _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
556 {
557 this->_M_impl._M_finish =
558 std::__uninitialized_copy_a(__x.begin(), __x.end(),
559 this->_M_impl._M_start,
560 _M_get_Tp_allocator());
561 }
562
563#if __cplusplus201402L >= 201103L
564 /**
565 * @brief %Vector move constructor.
566 *
567 * The newly-created %vector contains the exact contents of the
568 * moved instance.
569 * The contents of the moved instance are a valid, but unspecified
570 * %vector.
571 */
572 vector(vector&&) noexcept = default;
573
574 /// Copy constructor with alternative allocator
575 vector(const vector& __x, const allocator_type& __a)
576 : _Base(__x.size(), __a)
577 {
578 this->_M_impl._M_finish =
579 std::__uninitialized_copy_a(__x.begin(), __x.end(),
580 this->_M_impl._M_start,
581 _M_get_Tp_allocator());
582 }
583
584 private:
585 vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
586 : _Base(__m, std::move(__rv))
587 { }
588
589 vector(vector&& __rv, const allocator_type& __m, false_type)
590 : _Base(__m)
591 {
592 if (__rv.get_allocator() == __m)
593 this->_M_impl._M_swap_data(__rv._M_impl);
594 else if (!__rv.empty())
595 {
596 this->_M_create_storage(__rv.size());
597 this->_M_impl._M_finish =
598 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
599 this->_M_impl._M_start,
600 _M_get_Tp_allocator());
601 __rv.clear();
602 }
603 }
604
605 public:
606 /// Move constructor with alternative allocator
607 vector(vector&& __rv, const allocator_type& __m)
608 noexcept( noexcept(
609 vector(std::declval<vector&&>(), std::declval<const allocator_type&>(),
610 std::declval<typename _Alloc_traits::is_always_equal>())) )
611 : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{})
612 { }
613
614 /**
615 * @brief Builds a %vector from an initializer list.
616 * @param __l An initializer_list.
617 * @param __a An allocator.
618 *
619 * Create a %vector consisting of copies of the elements in the
620 * initializer_list @a __l.
621 *
622 * This will call the element type's copy constructor N times
623 * (where N is @a __l.size()) and do no memory reallocation.
624 */
625 vector(initializer_list<value_type> __l,
626 const allocator_type& __a = allocator_type())
627 : _Base(__a)
628 {
629 _M_range_initialize(__l.begin(), __l.end(),
630 random_access_iterator_tag());
631 }
632#endif
633
634 /**
635 * @brief Builds a %vector from a range.
636 * @param __first An input iterator.
637 * @param __last An input iterator.
638 * @param __a An allocator.
639 *
640 * Create a %vector consisting of copies of the elements from
641 * [first,last).
642 *
643 * If the iterators are forward, bidirectional, or
644 * random-access, then this will call the elements' copy
645 * constructor N times (where N is distance(first,last)) and do
646 * no memory reallocation. But if only input iterators are
647 * used, then this will do at most 2N calls to the copy
648 * constructor, and logN memory reallocations.
649 */
650#if __cplusplus201402L >= 201103L
651 template<typename _InputIterator,
652 typename = std::_RequireInputIter<_InputIterator>>
653 vector(_InputIterator __first, _InputIterator __last,
654 const allocator_type& __a = allocator_type())
655 : _Base(__a)
656 {
657 _M_range_initialize(__first, __last,
658 std::__iterator_category(__first));
659 }
660#else
661 template<typename _InputIterator>
662 vector(_InputIterator __first, _InputIterator __last,
663 const allocator_type& __a = allocator_type())
664 : _Base(__a)
665 {
666 // Check whether it's an integral type. If so, it's not an iterator.
667 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
668 _M_initialize_dispatch(__first, __last, _Integral());
669 }
670#endif
671
672 /**
673 * The dtor only erases the elements, and note that if the
674 * elements themselves are pointers, the pointed-to memory is
675 * not touched in any way. Managing the pointer is the user's
676 * responsibility.
677 */
678 ~vector() _GLIBCXX_NOEXCEPTnoexcept
679 {
680 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
681 _M_get_Tp_allocator());
682 _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
683 }
684
685 /**
686 * @brief %Vector assignment operator.
687 * @param __x A %vector of identical element and allocator types.
688 *
689 * All the elements of @a __x are copied, but any unused capacity in
690 * @a __x will not be copied.
691 *
692 * Whether the allocator is copied depends on the allocator traits.
693 */
694 vector&
695 operator=(const vector& __x);
696
697#if __cplusplus201402L >= 201103L
698 /**
699 * @brief %Vector move assignment operator.
700 * @param __x A %vector of identical element and allocator types.
701 *
702 * The contents of @a __x are moved into this %vector (without copying,
703 * if the allocators permit it).
704 * Afterwards @a __x is a valid, but unspecified %vector.
705 *
706 * Whether the allocator is moved depends on the allocator traits.
707 */
708 vector&
709 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
710 {
711 constexpr bool __move_storage =
712 _Alloc_traits::_S_propagate_on_move_assign()
713 || _Alloc_traits::_S_always_equal();
714 _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
715 return *this;
716 }
717
718 /**
719 * @brief %Vector list assignment operator.
720 * @param __l An initializer_list.
721 *
722 * This function fills a %vector with copies of the elements in the
723 * initializer list @a __l.
724 *
725 * Note that the assignment completely changes the %vector and
726 * that the resulting %vector's size is the same as the number
727 * of elements assigned.
728 */
729 vector&
730 operator=(initializer_list<value_type> __l)
731 {
732 this->_M_assign_aux(__l.begin(), __l.end(),
733 random_access_iterator_tag());
734 return *this;
735 }
736#endif
737
738 /**
739 * @brief Assigns a given value to a %vector.
740 * @param __n Number of elements to be assigned.
741 * @param __val Value to be assigned.
742 *
743 * This function fills a %vector with @a __n copies of the given
744 * value. Note that the assignment completely changes the
745 * %vector and that the resulting %vector's size is the same as
746 * the number of elements assigned.
747 */
748 void
749 assign(size_type __n, const value_type& __val)
750 { _M_fill_assign(__n, __val); }
751
752 /**
753 * @brief Assigns a range to a %vector.
754 * @param __first An input iterator.
755 * @param __last An input iterator.
756 *
757 * This function fills a %vector with copies of the elements in the
758 * range [__first,__last).
759 *
760 * Note that the assignment completely changes the %vector and
761 * that the resulting %vector's size is the same as the number
762 * of elements assigned.
763 */
764#if __cplusplus201402L >= 201103L
765 template<typename _InputIterator,
766 typename = std::_RequireInputIter<_InputIterator>>
767 void
768 assign(_InputIterator __first, _InputIterator __last)
769 { _M_assign_dispatch(__first, __last, __false_type()); }
770#else
771 template<typename _InputIterator>
772 void
773 assign(_InputIterator __first, _InputIterator __last)
774 {
775 // Check whether it's an integral type. If so, it's not an iterator.
776 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
777 _M_assign_dispatch(__first, __last, _Integral());
778 }
779#endif
780
781#if __cplusplus201402L >= 201103L
782 /**
783 * @brief Assigns an initializer list to a %vector.
784 * @param __l An initializer_list.
785 *
786 * This function fills a %vector with copies of the elements in the
787 * initializer list @a __l.
788 *
789 * Note that the assignment completely changes the %vector and
790 * that the resulting %vector's size is the same as the number
791 * of elements assigned.
792 */
793 void
794 assign(initializer_list<value_type> __l)
795 {
796 this->_M_assign_aux(__l.begin(), __l.end(),
797 random_access_iterator_tag());
798 }
799#endif
800
801 /// Get a copy of the memory allocation object.
802 using _Base::get_allocator;
803
804 // iterators
805 /**
806 * Returns a read/write iterator that points to the first
807 * element in the %vector. Iteration is done in ordinary
808 * element order.
809 */
810 iterator
811 begin() _GLIBCXX_NOEXCEPTnoexcept
812 { return iterator(this->_M_impl._M_start); }
813
814 /**
815 * Returns a read-only (constant) iterator that points to the
816 * first element in the %vector. Iteration is done in ordinary
817 * element order.
818 */
819 const_iterator
820 begin() const _GLIBCXX_NOEXCEPTnoexcept
821 { return const_iterator(this->_M_impl._M_start); }
822
823 /**
824 * Returns a read/write iterator that points one past the last
825 * element in the %vector. Iteration is done in ordinary
826 * element order.
827 */
828 iterator
829 end() _GLIBCXX_NOEXCEPTnoexcept
830 { return iterator(this->_M_impl._M_finish); }
831
832 /**
833 * Returns a read-only (constant) iterator that points one past
834 * the last element in the %vector. Iteration is done in
835 * ordinary element order.
836 */
837 const_iterator
838 end() const _GLIBCXX_NOEXCEPTnoexcept
839 { return const_iterator(this->_M_impl._M_finish); }
840
841 /**
842 * Returns a read/write reverse iterator that points to the
843 * last element in the %vector. Iteration is done in reverse
844 * element order.
845 */
846 reverse_iterator
847 rbegin() _GLIBCXX_NOEXCEPTnoexcept
848 { return reverse_iterator(end()); }
849
850 /**
851 * Returns a read-only (constant) reverse iterator that points
852 * to the last element in the %vector. Iteration is done in
853 * reverse element order.
854 */
855 const_reverse_iterator
856 rbegin() const _GLIBCXX_NOEXCEPTnoexcept
857 { return const_reverse_iterator(end()); }
858
859 /**
860 * Returns a read/write reverse iterator that points to one
861 * before the first element in the %vector. Iteration is done
862 * in reverse element order.
863 */
864 reverse_iterator
865 rend() _GLIBCXX_NOEXCEPTnoexcept
866 { return reverse_iterator(begin()); }
867
868 /**
869 * Returns a read-only (constant) reverse iterator that points
870 * to one before the first element in the %vector. Iteration
871 * is done in reverse element order.
872 */
873 const_reverse_iterator
874 rend() const _GLIBCXX_NOEXCEPTnoexcept
875 { return const_reverse_iterator(begin()); }
876
877#if __cplusplus201402L >= 201103L
878 /**
879 * Returns a read-only (constant) iterator that points to the
880 * first element in the %vector. Iteration is done in ordinary
881 * element order.
882 */
883 const_iterator
884 cbegin() const noexcept
885 { return const_iterator(this->_M_impl._M_start); }
886
887 /**
888 * Returns a read-only (constant) iterator that points one past
889 * the last element in the %vector. Iteration is done in
890 * ordinary element order.
891 */
892 const_iterator
893 cend() const noexcept
894 { return const_iterator(this->_M_impl._M_finish); }
895
896 /**
897 * Returns a read-only (constant) reverse iterator that points
898 * to the last element in the %vector. Iteration is done in
899 * reverse element order.
900 */
901 const_reverse_iterator
902 crbegin() const noexcept
903 { return const_reverse_iterator(end()); }
904
905 /**
906 * Returns a read-only (constant) reverse iterator that points
907 * to one before the first element in the %vector. Iteration
908 * is done in reverse element order.
909 */
910 const_reverse_iterator
911 crend() const noexcept
912 { return const_reverse_iterator(begin()); }
913#endif
914
915 // [23.2.4.2] capacity
916 /** Returns the number of elements in the %vector. */
917 size_type
918 size() const _GLIBCXX_NOEXCEPTnoexcept
919 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
920
921 /** Returns the size() of the largest possible %vector. */
922 size_type
923 max_size() const _GLIBCXX_NOEXCEPTnoexcept
924 { return _S_max_size(_M_get_Tp_allocator()); }
925
926#if __cplusplus201402L >= 201103L
927 /**
928 * @brief Resizes the %vector to the specified number of elements.
929 * @param __new_size Number of elements the %vector should contain.
930 *
931 * This function will %resize the %vector to the specified
932 * number of elements. If the number is smaller than the
933 * %vector's current size the %vector is truncated, otherwise
934 * default constructed elements are appended.
935 */
936 void
937 resize(size_type __new_size)
938 {
939 if (__new_size > size())
940 _M_default_append(__new_size - size());
941 else if (__new_size < size())
942 _M_erase_at_end(this->_M_impl._M_start + __new_size);
943 }
944
945 /**
946 * @brief Resizes the %vector to the specified number of elements.
947 * @param __new_size Number of elements the %vector should contain.
948 * @param __x Data with which new elements should be populated.
949 *
950 * This function will %resize the %vector to the specified
951 * number of elements. If the number is smaller than the
952 * %vector's current size the %vector is truncated, otherwise
953 * the %vector is extended and new elements are populated with
954 * given data.
955 */
956 void
957 resize(size_type __new_size, const value_type& __x)
958 {
959 if (__new_size > size())
960 _M_fill_insert(end(), __new_size - size(), __x);
961 else if (__new_size < size())
962 _M_erase_at_end(this->_M_impl._M_start + __new_size);
963 }
964#else
965 /**
966 * @brief Resizes the %vector to the specified number of elements.
967 * @param __new_size Number of elements the %vector should contain.
968 * @param __x Data with which new elements should be populated.
969 *
970 * This function will %resize the %vector to the specified
971 * number of elements. If the number is smaller than the
972 * %vector's current size the %vector is truncated, otherwise
973 * the %vector is extended and new elements are populated with
974 * given data.
975 */
976 void
977 resize(size_type __new_size, value_type __x = value_type())
978 {
979 if (__new_size > size())
980 _M_fill_insert(end(), __new_size - size(), __x);
981 else if (__new_size < size())
982 _M_erase_at_end(this->_M_impl._M_start + __new_size);
983 }
984#endif
985
986#if __cplusplus201402L >= 201103L
987 /** A non-binding request to reduce capacity() to size(). */
988 void
989 shrink_to_fit()
990 { _M_shrink_to_fit(); }
991#endif
992
993 /**
994 * Returns the total number of elements that the %vector can
995 * hold before needing to allocate more memory.
996 */
997 size_type
998 capacity() const _GLIBCXX_NOEXCEPTnoexcept
999 { return size_type(this->_M_impl._M_end_of_storage
1000 - this->_M_impl._M_start); }
1001
1002 /**
1003 * Returns true if the %vector is empty. (Thus begin() would
1004 * equal end().)
1005 */
1006 _GLIBCXX_NODISCARD bool
1007 empty() const _GLIBCXX_NOEXCEPTnoexcept
1008 { return begin() == end(); }
1009
1010 /**
1011 * @brief Attempt to preallocate enough memory for specified number of
1012 * elements.
1013 * @param __n Number of elements required.
1014 * @throw std::length_error If @a n exceeds @c max_size().
1015 *
1016 * This function attempts to reserve enough memory for the
1017 * %vector to hold the specified number of elements. If the
1018 * number requested is more than max_size(), length_error is
1019 * thrown.
1020 *
1021 * The advantage of this function is that if optimal code is a
1022 * necessity and the user can determine the number of elements
1023 * that will be required, the user can reserve the memory in
1024 * %advance, and thus prevent a possible reallocation of memory
1025 * and copying of %vector data.
1026 */
1027 void
1028 reserve(size_type __n);
1029
1030 // element access
1031 /**
1032 * @brief Subscript access to the data contained in the %vector.
1033 * @param __n The index of the element for which data should be
1034 * accessed.
1035 * @return Read/write reference to data.
1036 *
1037 * This operator allows for easy, array-style, data access.
1038 * Note that data access with this operator is unchecked and
1039 * out_of_range lookups are not defined. (For checked lookups
1040 * see at().)
1041 */
1042 reference
1043 operator[](size_type __n) _GLIBCXX_NOEXCEPTnoexcept
1044 {
1045 __glibcxx_requires_subscript(__n);
1046 return *(this->_M_impl._M_start + __n);
1047 }
1048
1049 /**
1050 * @brief Subscript access to the data contained in the %vector.
1051 * @param __n The index of the element for which data should be
1052 * accessed.
1053 * @return Read-only (constant) reference to data.
1054 *
1055 * This operator allows for easy, array-style, data access.
1056 * Note that data access with this operator is unchecked and
1057 * out_of_range lookups are not defined. (For checked lookups
1058 * see at().)
1059 */
1060 const_reference
1061 operator[](size_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1062 {
1063 __glibcxx_requires_subscript(__n);
1064 return *(this->_M_impl._M_start + __n);
1065 }
1066
1067 protected:
1068 /// Safety check used only from at().
1069 void
1070 _M_range_check(size_type __n) const
1071 {
1072 if (__n >= this->size())
1073 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "("vector::_M_range_check: __n " "(which is %zu) >= this->size() "
"(which is %zu)")
1074 "(which is %zu) >= this->size() "("vector::_M_range_check: __n " "(which is %zu) >= this->size() "
"(which is %zu)")
1075 "(which is %zu)")("vector::_M_range_check: __n " "(which is %zu) >= this->size() "
"(which is %zu)"),
1076 __n, this->size());
1077 }
1078
1079 public:
1080 /**
1081 * @brief Provides access to the data contained in the %vector.
1082 * @param __n The index of the element for which data should be
1083 * accessed.
1084 * @return Read/write reference to data.
1085 * @throw std::out_of_range If @a __n is an invalid index.
1086 *
1087 * This function provides for safer data access. The parameter
1088 * is first checked that it is in the range of the vector. The
1089 * function throws out_of_range if the check fails.
1090 */
1091 reference
1092 at(size_type __n)
1093 {
1094 _M_range_check(__n);
1095 return (*this)[__n];
1096 }
1097
1098 /**
1099 * @brief Provides access to the data contained in the %vector.
1100 * @param __n The index of the element for which data should be
1101 * accessed.
1102 * @return Read-only (constant) reference to data.
1103 * @throw std::out_of_range If @a __n is an invalid index.
1104 *
1105 * This function provides for safer data access. The parameter
1106 * is first checked that it is in the range of the vector. The
1107 * function throws out_of_range if the check fails.
1108 */
1109 const_reference
1110 at(size_type __n) const
1111 {
1112 _M_range_check(__n);
1113 return (*this)[__n];
1114 }
1115
1116 /**
1117 * Returns a read/write reference to the data at the first
1118 * element of the %vector.
1119 */
1120 reference
1121 front() _GLIBCXX_NOEXCEPTnoexcept
1122 {
1123 __glibcxx_requires_nonempty();
1124 return *begin();
1125 }
1126
1127 /**
1128 * Returns a read-only (constant) reference to the data at the first
1129 * element of the %vector.
1130 */
1131 const_reference
1132 front() const _GLIBCXX_NOEXCEPTnoexcept
1133 {
1134 __glibcxx_requires_nonempty();
1135 return *begin();
1136 }
1137
1138 /**
1139 * Returns a read/write reference to the data at the last
1140 * element of the %vector.
1141 */
1142 reference
1143 back() _GLIBCXX_NOEXCEPTnoexcept
1144 {
1145 __glibcxx_requires_nonempty();
1146 return *(end() - 1);
1147 }
1148
1149 /**
1150 * Returns a read-only (constant) reference to the data at the
1151 * last element of the %vector.
1152 */
1153 const_reference
1154 back() const _GLIBCXX_NOEXCEPTnoexcept
1155 {
1156 __glibcxx_requires_nonempty();
1157 return *(end() - 1);
1158 }
1159
1160 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1161 // DR 464. Suggestion for new member functions in standard containers.
1162 // data access
1163 /**
1164 * Returns a pointer such that [data(), data() + size()) is a valid
1165 * range. For a non-empty %vector, data() == &front().
1166 */
1167 _Tp*
1168 data() _GLIBCXX_NOEXCEPTnoexcept
1169 { return _M_data_ptr(this->_M_impl._M_start); }
1170
1171 const _Tp*
1172 data() const _GLIBCXX_NOEXCEPTnoexcept
1173 { return _M_data_ptr(this->_M_impl._M_start); }
1174
1175 // [23.2.4.3] modifiers
1176 /**
1177 * @brief Add data to the end of the %vector.
1178 * @param __x Data to be added.
1179 *
1180 * This is a typical stack operation. The function creates an
1181 * element at the end of the %vector and assigns the given data
1182 * to it. Due to the nature of a %vector this operation can be
1183 * done in constant time if the %vector has preallocated space
1184 * available.
1185 */
1186 void
1187 push_back(const value_type& __x)
1188 {
1189 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
1190 {
1191 _GLIBCXX_ASAN_ANNOTATE_GROW(1);
1192 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
1193 __x);
1194 ++this->_M_impl._M_finish;
1195 _GLIBCXX_ASAN_ANNOTATE_GREW(1);
1196 }
1197 else
1198 _M_realloc_insert(end(), __x);
1199 }
1200
1201#if __cplusplus201402L >= 201103L
1202 void
1203 push_back(value_type&& __x)
1204 { emplace_back(std::move(__x)); }
1205
1206 template<typename... _Args>
1207#if __cplusplus201402L > 201402L
1208 reference
1209#else
1210 void
1211#endif
1212 emplace_back(_Args&&... __args);
1213#endif
1214
1215 /**
1216 * @brief Removes last element.
1217 *
1218 * This is a typical stack operation. It shrinks the %vector by one.
1219 *
1220 * Note that no data is returned, and if the last element's
1221 * data is needed, it should be retrieved before pop_back() is
1222 * called.
1223 */
1224 void
1225 pop_back() _GLIBCXX_NOEXCEPTnoexcept
1226 {
1227 __glibcxx_requires_nonempty();
1228 --this->_M_impl._M_finish;
1229 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
1230 _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
1231 }
1232
1233#if __cplusplus201402L >= 201103L
1234 /**
1235 * @brief Inserts an object in %vector before specified iterator.
1236 * @param __position A const_iterator into the %vector.
1237 * @param __args Arguments.
1238 * @return An iterator that points to the inserted data.
1239 *
1240 * This function will insert an object of type T constructed
1241 * with T(std::forward<Args>(args)...) before the specified location.
1242 * Note that this kind of operation could be expensive for a %vector
1243 * and if it is frequently used the user should consider using
1244 * std::list.
1245 */
1246 template<typename... _Args>
1247 iterator
1248 emplace(const_iterator __position, _Args&&... __args)
1249 { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
1250
1251 /**
1252 * @brief Inserts given value into %vector before specified iterator.
1253 * @param __position A const_iterator into the %vector.
1254 * @param __x Data to be inserted.
1255 * @return An iterator that points to the inserted data.
1256 *
1257 * This function will insert a copy of the given value before
1258 * the specified location. Note that this kind of operation
1259 * could be expensive for a %vector and if it is frequently
1260 * used the user should consider using std::list.
1261 */
1262 iterator
1263 insert(const_iterator __position, const value_type& __x);
1264#else
1265 /**
1266 * @brief Inserts given value into %vector before specified iterator.
1267 * @param __position An iterator into the %vector.
1268 * @param __x Data to be inserted.
1269 * @return An iterator that points to the inserted data.
1270 *
1271 * This function will insert a copy of the given value before
1272 * the specified location. Note that this kind of operation
1273 * could be expensive for a %vector and if it is frequently
1274 * used the user should consider using std::list.
1275 */
1276 iterator
1277 insert(iterator __position, const value_type& __x);
1278#endif
1279
1280#if __cplusplus201402L >= 201103L
1281 /**
1282 * @brief Inserts given rvalue into %vector before specified iterator.
1283 * @param __position A const_iterator into the %vector.
1284 * @param __x Data to be inserted.
1285 * @return An iterator that points to the inserted data.
1286 *
1287 * This function will insert a copy of the given rvalue before
1288 * the specified location. Note that this kind of operation
1289 * could be expensive for a %vector and if it is frequently
1290 * used the user should consider using std::list.
1291 */
1292 iterator
1293 insert(const_iterator __position, value_type&& __x)
1294 { return _M_insert_rval(__position, std::move(__x)); }
1295
1296 /**
1297 * @brief Inserts an initializer_list into the %vector.
1298 * @param __position An iterator into the %vector.
1299 * @param __l An initializer_list.
1300 *
1301 * This function will insert copies of the data in the
1302 * initializer_list @a l into the %vector before the location
1303 * specified by @a position.
1304 *
1305 * Note that this kind of operation could be expensive for a
1306 * %vector and if it is frequently used the user should
1307 * consider using std::list.
1308 */
1309 iterator
1310 insert(const_iterator __position, initializer_list<value_type> __l)
1311 {
1312 auto __offset = __position - cbegin();
1313 _M_range_insert(begin() + __offset, __l.begin(), __l.end(),
1314 std::random_access_iterator_tag());
1315 return begin() + __offset;
1316 }
1317#endif
1318
1319#if __cplusplus201402L >= 201103L
1320 /**
1321 * @brief Inserts a number of copies of given data into the %vector.
1322 * @param __position A const_iterator into the %vector.
1323 * @param __n Number of elements to be inserted.
1324 * @param __x Data to be inserted.
1325 * @return An iterator that points to the inserted data.
1326 *
1327 * This function will insert a specified number of copies of
1328 * the given data before the location specified by @a position.
1329 *
1330 * Note that this kind of operation could be expensive for a
1331 * %vector and if it is frequently used the user should
1332 * consider using std::list.
1333 */
1334 iterator
1335 insert(const_iterator __position, size_type __n, const value_type& __x)
1336 {
1337 difference_type __offset = __position - cbegin();
1338 _M_fill_insert(begin() + __offset, __n, __x);
1339 return begin() + __offset;
1340 }
1341#else
1342 /**
1343 * @brief Inserts a number of copies of given data into the %vector.
1344 * @param __position An iterator into the %vector.
1345 * @param __n Number of elements to be inserted.
1346 * @param __x Data to be inserted.
1347 *
1348 * This function will insert a specified number of copies of
1349 * the given data before the location specified by @a position.
1350 *
1351 * Note that this kind of operation could be expensive for a
1352 * %vector and if it is frequently used the user should
1353 * consider using std::list.
1354 */
1355 void
1356 insert(iterator __position, size_type __n, const value_type& __x)
1357 { _M_fill_insert(__position, __n, __x); }
1358#endif
1359
1360#if __cplusplus201402L >= 201103L
1361 /**
1362 * @brief Inserts a range into the %vector.
1363 * @param __position A const_iterator into the %vector.
1364 * @param __first An input iterator.
1365 * @param __last An input iterator.
1366 * @return An iterator that points to the inserted data.
1367 *
1368 * This function will insert copies of the data in the range
1369 * [__first,__last) into the %vector before the location specified
1370 * by @a pos.
1371 *
1372 * Note that this kind of operation could be expensive for a
1373 * %vector and if it is frequently used the user should
1374 * consider using std::list.
1375 */
1376 template<typename _InputIterator,
1377 typename = std::_RequireInputIter<_InputIterator>>
1378 iterator
1379 insert(const_iterator __position, _InputIterator __first,
1380 _InputIterator __last)
1381 {
1382 difference_type __offset = __position - cbegin();
1383 _M_insert_dispatch(begin() + __offset,
1384 __first, __last, __false_type());
1385 return begin() + __offset;
1386 }
1387#else
1388 /**
1389 * @brief Inserts a range into the %vector.
1390 * @param __position An iterator into the %vector.
1391 * @param __first An input iterator.
1392 * @param __last An input iterator.
1393 *
1394 * This function will insert copies of the data in the range
1395 * [__first,__last) into the %vector before the location specified
1396 * by @a pos.
1397 *
1398 * Note that this kind of operation could be expensive for a
1399 * %vector and if it is frequently used the user should
1400 * consider using std::list.
1401 */
1402 template<typename _InputIterator>
1403 void
1404 insert(iterator __position, _InputIterator __first,
1405 _InputIterator __last)
1406 {
1407 // Check whether it's an integral type. If so, it's not an iterator.
1408 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1409 _M_insert_dispatch(__position, __first, __last, _Integral());
1410 }
1411#endif
1412
1413 /**
1414 * @brief Remove element at given position.
1415 * @param __position Iterator pointing to element to be erased.
1416 * @return An iterator pointing to the next element (or end()).
1417 *
1418 * This function will erase the element at the given position and thus
1419 * shorten the %vector by one.
1420 *
1421 * Note This operation could be expensive and if it is
1422 * frequently used the user should consider using std::list.
1423 * The user is also cautioned that this function only erases
1424 * the element, and that if the element is itself a pointer,
1425 * the pointed-to memory is not touched in any way. Managing
1426 * the pointer is the user's responsibility.
1427 */
1428 iterator
1429#if __cplusplus201402L >= 201103L
1430 erase(const_iterator __position)
1431 { return _M_erase(begin() + (__position - cbegin())); }
1432#else
1433 erase(iterator __position)
1434 { return _M_erase(__position); }
1435#endif
1436
1437 /**
1438 * @brief Remove a range of elements.
1439 * @param __first Iterator pointing to the first element to be erased.
1440 * @param __last Iterator pointing to one past the last element to be
1441 * erased.
1442 * @return An iterator pointing to the element pointed to by @a __last
1443 * prior to erasing (or end()).
1444 *
1445 * This function will erase the elements in the range
1446 * [__first,__last) and shorten the %vector accordingly.
1447 *
1448 * Note This operation could be expensive and if it is
1449 * frequently used the user should consider using std::list.
1450 * The user is also cautioned that this function only erases
1451 * the elements, and that if the elements themselves are
1452 * pointers, the pointed-to memory is not touched in any way.
1453 * Managing the pointer is the user's responsibility.
1454 */
1455 iterator
1456#if __cplusplus201402L >= 201103L
1457 erase(const_iterator __first, const_iterator __last)
1458 {
1459 const auto __beg = begin();
1460 const auto __cbeg = cbegin();
1461 return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
1462 }
1463#else
1464 erase(iterator __first, iterator __last)
1465 { return _M_erase(__first, __last); }
1466#endif
1467
1468 /**
1469 * @brief Swaps data with another %vector.
1470 * @param __x A %vector of the same element and allocator types.
1471 *
1472 * This exchanges the elements between two vectors in constant time.
1473 * (Three pointers, so it should be quite fast.)
1474 * Note that the global std::swap() function is specialized such that
1475 * std::swap(v1,v2) will feed to this function.
1476 *
1477 * Whether the allocators are swapped depends on the allocator traits.
1478 */
1479 void
1480 swap(vector& __x) _GLIBCXX_NOEXCEPTnoexcept
1481 {
1482#if __cplusplus201402L >= 201103L
1483 __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
1484 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
1485#endif
1486 this->_M_impl._M_swap_data(__x._M_impl);
1487 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1488 __x._M_get_Tp_allocator());
1489 }
1490
1491 /**
1492 * Erases all the elements. Note that this function only erases the
1493 * elements, and that if the elements themselves are pointers, the
1494 * pointed-to memory is not touched in any way. Managing the pointer is
1495 * the user's responsibility.
1496 */
1497 void
1498 clear() _GLIBCXX_NOEXCEPTnoexcept
1499 { _M_erase_at_end(this->_M_impl._M_start); }
1500
1501 protected:
1502 /**
1503 * Memory expansion handler. Uses the member allocation function to
1504 * obtain @a n bytes of memory, and then copies [first,last) into it.
1505 */
1506 template<typename _ForwardIterator>
1507 pointer
1508 _M_allocate_and_copy(size_type __n,
1509 _ForwardIterator __first, _ForwardIterator __last)
1510 {
1511 pointer __result = this->_M_allocate(__n);
1512 __tryif (true)
1513 {
1514 std::__uninitialized_copy_a(__first, __last, __result,
1515 _M_get_Tp_allocator());
1516 return __result;
1517 }
1518 __catch(...)if (false)
1519 {
1520 _M_deallocate(__result, __n);
1521 __throw_exception_again;
1522 }
1523 }
1524
1525
1526 // Internal constructor functions follow.
1527
1528 // Called by the range constructor to implement [23.1.1]/9
1529
1530#if __cplusplus201402L < 201103L
1531 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1532 // 438. Ambiguity in the "do the right thing" clause
1533 template<typename _Integer>
1534 void
1535 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1536 {
1537 this->_M_impl._M_start = _M_allocate(_S_check_init_len(
1538 static_cast<size_type>(__n), _M_get_Tp_allocator()));
1539 this->_M_impl._M_end_of_storage =
1540 this->_M_impl._M_start + static_cast<size_type>(__n);
1541 _M_fill_initialize(static_cast<size_type>(__n), __value);
1542 }
1543
1544 // Called by the range constructor to implement [23.1.1]/9
1545 template<typename _InputIterator>
1546 void
1547 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1548 __false_type)
1549 {
1550 _M_range_initialize(__first, __last,
1551 std::__iterator_category(__first));
1552 }
1553#endif
1554
1555 // Called by the second initialize_dispatch above
1556 template<typename _InputIterator>
1557 void
1558 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1559 std::input_iterator_tag)
1560 {
1561 __tryif (true) {
1562 for (; __first != __last; ++__first)
1563#if __cplusplus201402L >= 201103L
1564 emplace_back(*__first);
1565#else
1566 push_back(*__first);
1567#endif
1568 } __catch(...)if (false) {
1569 clear();
1570 __throw_exception_again;
1571 }
1572 }
1573
1574 // Called by the second initialize_dispatch above
1575 template<typename _ForwardIterator>
1576 void
1577 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1578 std::forward_iterator_tag)
1579 {
1580 const size_type __n = std::distance(__first, __last);
1581 this->_M_impl._M_start
1582 = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
1583 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1584 this->_M_impl._M_finish =
1585 std::__uninitialized_copy_a(__first, __last,
1586 this->_M_impl._M_start,
1587 _M_get_Tp_allocator());
1588 }
1589
1590 // Called by the first initialize_dispatch above and by the
1591 // vector(n,value,a) constructor.
1592 void
1593 _M_fill_initialize(size_type __n, const value_type& __value)
1594 {
1595 this->_M_impl._M_finish =
1596 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1597 _M_get_Tp_allocator());
1598 }
1599
1600#if __cplusplus201402L >= 201103L
1601 // Called by the vector(n) constructor.
1602 void
1603 _M_default_initialize(size_type __n)
1604 {
1605 this->_M_impl._M_finish =
1606 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1607 _M_get_Tp_allocator());
1608 }
1609#endif
1610
1611 // Internal assign functions follow. The *_aux functions do the actual
1612 // assignment work for the range versions.
1613
1614 // Called by the range assign to implement [23.1.1]/9
1615
1616 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1617 // 438. Ambiguity in the "do the right thing" clause
1618 template<typename _Integer>
1619 void
1620 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1621 { _M_fill_assign(__n, __val); }
1622
1623 // Called by the range assign to implement [23.1.1]/9
1624 template<typename _InputIterator>
1625 void
1626 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1627 __false_type)
1628 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1629
1630 // Called by the second assign_dispatch above
1631 template<typename _InputIterator>
1632 void
1633 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1634 std::input_iterator_tag);
1635
1636 // Called by the second assign_dispatch above
1637 template<typename _ForwardIterator>
1638 void
1639 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1640 std::forward_iterator_tag);
1641
1642 // Called by assign(n,t), and the range assign when it turns out
1643 // to be the same thing.
1644 void
1645 _M_fill_assign(size_type __n, const value_type& __val);
1646
1647 // Internal insert functions follow.
1648
1649 // Called by the range insert to implement [23.1.1]/9
1650
1651 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1652 // 438. Ambiguity in the "do the right thing" clause
1653 template<typename _Integer>
1654 void
1655 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1656 __true_type)
1657 { _M_fill_insert(__pos, __n, __val); }
1658
1659 // Called by the range insert to implement [23.1.1]/9
1660 template<typename _InputIterator>
1661 void
1662 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1663 _InputIterator __last, __false_type)
1664 {
1665 _M_range_insert(__pos, __first, __last,
1666 std::__iterator_category(__first));
1667 }
1668
1669 // Called by the second insert_dispatch above
1670 template<typename _InputIterator>
1671 void
1672 _M_range_insert(iterator __pos, _InputIterator __first,
1673 _InputIterator __last, std::input_iterator_tag);
1674
1675 // Called by the second insert_dispatch above
1676 template<typename _ForwardIterator>
1677 void
1678 _M_range_insert(iterator __pos, _ForwardIterator __first,
1679 _ForwardIterator __last, std::forward_iterator_tag);
1680
1681 // Called by insert(p,n,x), and the range insert when it turns out to be
1682 // the same thing.
1683 void
1684 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1685
1686#if __cplusplus201402L >= 201103L
1687 // Called by resize(n).
1688 void
1689 _M_default_append(size_type __n);
1690
1691 bool
1692 _M_shrink_to_fit();
1693#endif
1694
1695#if __cplusplus201402L < 201103L
1696 // Called by insert(p,x)
1697 void
1698 _M_insert_aux(iterator __position, const value_type& __x);
1699
1700 void
1701 _M_realloc_insert(iterator __position, const value_type& __x);
1702#else
1703 // A value_type object constructed with _Alloc_traits::construct()
1704 // and destroyed with _Alloc_traits::destroy().
1705 struct _Temporary_value
1706 {
1707 template<typename... _Args>
1708 explicit
1709 _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
1710 {
1711 _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
1712 std::forward<_Args>(__args)...);
1713 }
1714
1715 ~_Temporary_value()
1716 { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
1717
1718 value_type&
1719 _M_val() { return *_M_ptr(); }
1720
1721 private:
1722 _Tp*
1723 _M_ptr() { return reinterpret_cast<_Tp*>(&__buf); }
1724
1725 vector* _M_this;
1726 typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
1727 };
1728
1729 // Called by insert(p,x) and other functions when insertion needs to
1730 // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
1731 template<typename _Arg>
1732 void
1733 _M_insert_aux(iterator __position, _Arg&& __arg);
1734
1735 template<typename... _Args>
1736 void
1737 _M_realloc_insert(iterator __position, _Args&&... __args);
1738
1739 // Either move-construct at the end, or forward to _M_insert_aux.
1740 iterator
1741 _M_insert_rval(const_iterator __position, value_type&& __v);
1742
1743 // Try to emplace at the end, otherwise forward to _M_insert_aux.
1744 template<typename... _Args>
1745 iterator
1746 _M_emplace_aux(const_iterator __position, _Args&&... __args);
1747
1748 // Emplacing an rvalue of the correct type can use _M_insert_rval.
1749 iterator
1750 _M_emplace_aux(const_iterator __position, value_type&& __v)
1751 { return _M_insert_rval(__position, std::move(__v)); }
1752#endif
1753
1754 // Called by _M_fill_insert, _M_insert_aux etc.
1755 size_type
1756 _M_check_len(size_type __n, const char* __s) const
1757 {
1758 if (max_size() - size() < __n)
1759 __throw_length_error(__N(__s)(__s));
1760
1761 const size_type __len = size() + (std::max)(size(), __n);
1762 return (__len < size() || __len > max_size()) ? max_size() : __len;
1763 }
1764
1765 // Called by constructors to check initial size.
1766 static size_type
1767 _S_check_init_len(size_type __n, const allocator_type& __a)
1768 {
1769 if (__n > _S_max_size(_Tp_alloc_type(__a)))
1770 __throw_length_error(
1771 __N("cannot create std::vector larger than max_size()")("cannot create std::vector larger than max_size()"));
1772 return __n;
1773 }
1774
1775 static size_type
1776 _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPTnoexcept
1777 {
1778 // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
1779 // and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
1780 // (even if std::allocator_traits::max_size says we can).
1781 const size_t __diffmax
1782 = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
1783 const size_t __allocmax = _Alloc_traits::max_size(__a);
1784 return (std::min)(__diffmax, __allocmax);
1785 }
1786
1787 // Internal erase functions follow.
1788
1789 // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
1790 // _M_assign_aux.
1791 void
1792 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPTnoexcept
1793 {
1794 if (size_type __n = this->_M_impl._M_finish - __pos)
1795 {
1796 std::_Destroy(__pos, this->_M_impl._M_finish,
1797 _M_get_Tp_allocator());
1798 this->_M_impl._M_finish = __pos;
1799 _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n);
1800 }
1801 }
1802
1803 iterator
1804 _M_erase(iterator __position);
1805
1806 iterator
1807 _M_erase(iterator __first, iterator __last);
1808
1809#if __cplusplus201402L >= 201103L
1810 private:
1811 // Constant-time move assignment when source object's memory can be
1812 // moved, either because the source's allocator will move too
1813 // or because the allocators are equal.
1814 void
1815 _M_move_assign(vector&& __x, true_type) noexcept
1816 {
1817 vector __tmp(get_allocator());
1818 this->_M_impl._M_swap_data(__x._M_impl);
1819 __tmp._M_impl._M_swap_data(__x._M_impl);
1820 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1821 }
1822
1823 // Do move assignment when it might not be possible to move source
1824 // object's memory, resulting in a linear-time operation.
1825 void
1826 _M_move_assign(vector&& __x, false_type)
1827 {
1828 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1829 _M_move_assign(std::move(__x), true_type());
1830 else
1831 {
1832 // The rvalue's allocator cannot be moved and is not equal,
1833 // so we need to individually move each element.
1834 this->_M_assign_aux(std::make_move_iterator(__x.begin()),
1835 std::make_move_iterator(__x.end()),
1836 std::random_access_iterator_tag());
1837 __x.clear();
1838 }
1839 }
1840#endif
1841
1842 template<typename _Up>
1843 _Up*
1844 _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPTnoexcept
1845 { return __ptr; }
1846
1847#if __cplusplus201402L >= 201103L
1848 template<typename _Ptr>
1849 typename std::pointer_traits<_Ptr>::element_type*
1850 _M_data_ptr(_Ptr __ptr) const
1851 { return empty() ? nullptr : std::__to_address(__ptr); }
1852#else
1853 template<typename _Up>
1854 _Up*
1855 _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPTnoexcept
1856 { return __ptr; }
1857
1858 template<typename _Ptr>
1859 value_type*
1860 _M_data_ptr(_Ptr __ptr)
1861 { return empty() ? (value_type*)0 : __ptr.operator->(); }
1862
1863 template<typename _Ptr>
1864 const value_type*
1865 _M_data_ptr(_Ptr __ptr) const
1866 { return empty() ? (const value_type*)0 : __ptr.operator->(); }
1867#endif
1868 };
1869
1870#if __cpp_deduction_guides >= 201606
1871 template<typename _InputIterator, typename _ValT
1872 = typename iterator_traits<_InputIterator>::value_type,
1873 typename _Allocator = allocator<_ValT>,
1874 typename = _RequireInputIter<_InputIterator>,
1875 typename = _RequireAllocator<_Allocator>>
1876 vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
1877 -> vector<_ValT, _Allocator>;
1878#endif
1879
1880 /**
1881 * @brief Vector equality comparison.
1882 * @param __x A %vector.
1883 * @param __y A %vector of the same type as @a __x.
1884 * @return True iff the size and elements of the vectors are equal.
1885 *
1886 * This is an equivalence relation. It is linear in the size of the
1887 * vectors. Vectors are considered equivalent if their sizes are equal,
1888 * and if corresponding elements compare equal.
1889 */
1890 template<typename _Tp, typename _Alloc>
1891 inline bool
1892 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1893 { return (__x.size() == __y.size()
1894 && std::equal(__x.begin(), __x.end(), __y.begin())); }
1895
1896#if __cpp_lib_three_way_comparison
1897 /**
1898 * @brief Vector ordering relation.
1899 * @param __x A `vector`.
1900 * @param __y A `vector` of the same type as `__x`.
1901 * @return A value indicating whether `__x` is less than, equal to,
1902 * greater than, or incomparable with `__y`.
1903 *
1904 * See `std::lexicographical_compare_three_way()` for how the determination
1905 * is made. This operator is used to synthesize relational operators like
1906 * `<` and `>=` etc.
1907 */
1908 template<typename _Tp, typename _Alloc>
1909 inline __detail::__synth3way_t<_Tp>
1910 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1911 {
1912 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1913 __y.begin(), __y.end(),
1914 __detail::__synth3way);
1915 }
1916#else
1917 /**
1918 * @brief Vector ordering relation.
1919 * @param __x A %vector.
1920 * @param __y A %vector of the same type as @a __x.
1921 * @return True iff @a __x is lexicographically less than @a __y.
1922 *
1923 * This is a total ordering relation. It is linear in the size of the
1924 * vectors. The elements must be comparable with @c <.
1925 *
1926 * See std::lexicographical_compare() for how the determination is made.
1927 */
1928 template<typename _Tp, typename _Alloc>
1929 inline bool
1930 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1931 { return std::lexicographical_compare(__x.begin(), __x.end(),
1932 __y.begin(), __y.end()); }
1933
1934 /// Based on operator==
1935 template<typename _Tp, typename _Alloc>
1936 inline bool
1937 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1938 { return !(__x == __y); }
1939
1940 /// Based on operator<
1941 template<typename _Tp, typename _Alloc>
1942 inline bool
1943 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1944 { return __y < __x; }
1945
1946 /// Based on operator<
1947 template<typename _Tp, typename _Alloc>
1948 inline bool
1949 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1950 { return !(__y < __x); }
1951
1952 /// Based on operator<
1953 template<typename _Tp, typename _Alloc>
1954 inline bool
1955 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
1956 { return !(__x < __y); }
1957#endif // three-way comparison
1958
1959 /// See std::vector::swap().
1960 template<typename _Tp, typename _Alloc>
1961 inline void
1962 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
1963 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))noexcept(noexcept(__x.swap(__y)))
1964 { __x.swap(__y); }
1965
1966_GLIBCXX_END_NAMESPACE_CONTAINER
1967
1968#if __cplusplus201402L >= 201703L
1969 namespace __detail::__variant
1970 {
1971 template<typename> struct _Never_valueless_alt; // see <variant>
1972
1973 // Provide the strong exception-safety guarantee when emplacing a
1974 // vector into a variant, but only if move assignment cannot throw.
1975 template<typename _Tp, typename _Alloc>
1976 struct _Never_valueless_alt<_GLIBCXX_STD_Cstd::vector<_Tp, _Alloc>>
1977 : std::is_nothrow_move_assignable<_GLIBCXX_STD_Cstd::vector<_Tp, _Alloc>>
1978 { };
1979 } // namespace __detail::__variant
1980#endif // C++17
1981
1982_GLIBCXX_END_NAMESPACE_VERSION
1983} // namespace std
1984
1985#endif /* _STL_VECTOR_H */
←

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

→
1// unique_ptr implementation -*- C++ -*-
2
3// Copyright (C) 2008-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/** @file bits/unique_ptr.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{memory}
28 */
29
30#ifndef _UNIQUE_PTR_H1
31#define _UNIQUE_PTR_H1 1
32
33#include <bits/c++config.h>
34#include <debug/assertions.h>
35#include <type_traits>
36#include <utility>
37#include <tuple>
38#include <bits/stl_function.h>
39#include <bits/functional_hash.h>
40#if __cplusplus201402L > 201703L
41# include <compare>
42# include <ostream>
43#endif
44
45namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
46{
47_GLIBCXX_BEGIN_NAMESPACE_VERSION
48
49 /**
50 * @addtogroup pointer_abstractions
51 * @{
52 */
53
54#if _GLIBCXX_USE_DEPRECATED1
55#pragma GCC diagnostic push
56#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
57 template<typename> class auto_ptr;
58#pragma GCC diagnostic pop
59#endif
60
61 /// Primary template of default_delete, used by unique_ptr for single objects
62 template<typename _Tp>
63 struct default_delete
64 {
65 /// Default constructor
66 constexpr default_delete() noexcept = default;
67
68 /** @brief Converting constructor.
69 *
70 * Allows conversion from a deleter for objects of another type, `_Up`,
71 * only if `_Up*` is convertible to `_Tp*`.
72 */
73 template<typename _Up,
74 typename = _Require<is_convertible<_Up*, _Tp*>>>
75 default_delete(const default_delete<_Up>&) noexcept { }
76
77 /// Calls `delete __ptr`
78 void
79 operator()(_Tp* __ptr) const
80 {
81 static_assert(!is_void<_Tp>::value,
82 "can't delete pointer to incomplete type");
83 static_assert(sizeof(_Tp)>0,
84 "can't delete pointer to incomplete type");
85 delete __ptr;
86 }
87 };
88
89 // _GLIBCXX_RESOLVE_LIB_DEFECTS
90 // DR 740 - omit specialization for array objects with a compile time length
91
92 /// Specialization of default_delete for arrays, used by `unique_ptr<T[]>`
93 template<typename _Tp>
94 struct default_delete<_Tp[]>
95 {
96 public:
97 /// Default constructor
98 constexpr default_delete() noexcept = default;
99
100 /** @brief Converting constructor.
101 *
102 * Allows conversion from a deleter for arrays of another type, such as
103 * a const-qualified version of `_Tp`.
104 *
105 * Conversions from types derived from `_Tp` are not allowed because
106 * it is undefined to `delete[]` an array of derived types through a
107 * pointer to the base type.
108 */
109 template<typename _Up,
110 typename = _Require<is_convertible<_Up(*)[], _Tp(*)[]>>>
111 default_delete(const default_delete<_Up[]>&) noexcept { }
112
113 /// Calls `delete[] __ptr`
114 template<typename _Up>
115 typename enable_if<is_convertible<_Up(*)[], _Tp(*)[]>::value>::type
116 operator()(_Up* __ptr) const
117 {
118 static_assert(sizeof(_Tp)>0,
119 "can't delete pointer to incomplete type");
120 delete [] __ptr;
121 }
122 };
123
124 /// @cond undocumented
125
126 // Manages the pointer and deleter of a unique_ptr
127 template <typename _Tp, typename _Dp>
128 class __uniq_ptr_impl
129 {
130 template <typename _Up, typename _Ep, typename = void>
131 struct _Ptr
132 {
133 using type = _Up*;
134 };
135
136 template <typename _Up, typename _Ep>
137 struct
138 _Ptr<_Up, _Ep, __void_t<typename remove_reference<_Ep>::type::pointer>>
139 {
140 using type = typename remove_reference<_Ep>::type::pointer;
141 };
142
143 public:
144 using _DeleterConstraint = enable_if<
145 __and_<__not_<is_pointer<_Dp>>,
146 is_default_constructible<_Dp>>::value>;
147
148 using pointer = typename _Ptr<_Tp, _Dp>::type;
149
150 static_assert( !is_rvalue_reference<_Dp>::value,
151 "unique_ptr's deleter type must be a function object type"
152 " or an lvalue reference type" );
153
154 __uniq_ptr_impl() = default;
155 __uniq_ptr_impl(pointer __p) : _M_t() { _M_ptr() = __p; }
156
157 template<typename _Del>
158 __uniq_ptr_impl(pointer __p, _Del&& __d)
159 : _M_t(__p, std::forward<_Del>(__d)) { }
160
161 __uniq_ptr_impl(__uniq_ptr_impl&& __u) noexcept
162 : _M_t(std::move(__u._M_t))
163 { __u._M_ptr() = nullptr; }
164
165 __uniq_ptr_impl& operator=(__uniq_ptr_impl&& __u) noexcept
166 {
167 reset(__u.release());
168 _M_deleter() = std::forward<_Dp>(__u._M_deleter());
169 return *this;
170 }
171
172 pointer& _M_ptr() { return std::get<0>(_M_t); }
173 pointer _M_ptr() const { return std::get<0>(_M_t); }
174 _Dp& _M_deleter() { return std::get<1>(_M_t); }
175 const _Dp& _M_deleter() const { return std::get<1>(_M_t); }
176
177 void reset(pointer __p) noexcept
178 {
179 const pointer __old_p = _M_ptr();
180 _M_ptr() = __p;
181 if (__old_p)
182 _M_deleter()(__old_p);
183 }
184
185 pointer release() noexcept
186 {
187 pointer __p = _M_ptr();
188 _M_ptr() = nullptr;
189 return __p;
190 }
191
192 void
193 swap(__uniq_ptr_impl& __rhs) noexcept
194 {
195 using std::swap;
196 swap(this->_M_ptr(), __rhs._M_ptr());
197 swap(this->_M_deleter(), __rhs._M_deleter());
198 }
199
200 private:
201 tuple<pointer, _Dp> _M_t;
202 };
203
204 // Defines move construction + assignment as either defaulted or deleted.
205 template <typename _Tp, typename _Dp,
206 bool = is_move_constructible<_Dp>::value,
207 bool = is_move_assignable<_Dp>::value>
208 struct __uniq_ptr_data : __uniq_ptr_impl<_Tp, _Dp>
209 {
210 using __uniq_ptr_impl<_Tp, _Dp>::__uniq_ptr_impl;
211 __uniq_ptr_data(__uniq_ptr_data&&) = default;
212 __uniq_ptr_data& operator=(__uniq_ptr_data&&) = default;
213 };
214
215 template <typename _Tp, typename _Dp>
216 struct __uniq_ptr_data<_Tp, _Dp, true, false> : __uniq_ptr_impl<_Tp, _Dp>
217 {
218 using __uniq_ptr_impl<_Tp, _Dp>::__uniq_ptr_impl;
219 __uniq_ptr_data(__uniq_ptr_data&&) = default;
220 __uniq_ptr_data& operator=(__uniq_ptr_data&&) = delete;
221 };
222
223 template <typename _Tp, typename _Dp>
224 struct __uniq_ptr_data<_Tp, _Dp, false, true> : __uniq_ptr_impl<_Tp, _Dp>
225 {
226 using __uniq_ptr_impl<_Tp, _Dp>::__uniq_ptr_impl;
227 __uniq_ptr_data(__uniq_ptr_data&&) = delete;
228 __uniq_ptr_data& operator=(__uniq_ptr_data&&) = default;
229 };
230
231 template <typename _Tp, typename _Dp>
232 struct __uniq_ptr_data<_Tp, _Dp, false, false> : __uniq_ptr_impl<_Tp, _Dp>
233 {
234 using __uniq_ptr_impl<_Tp, _Dp>::__uniq_ptr_impl;
235 __uniq_ptr_data(__uniq_ptr_data&&) = delete;
236 __uniq_ptr_data& operator=(__uniq_ptr_data&&) = delete;
237 };
238 /// @endcond
239
240 /// 20.7.1.2 unique_ptr for single objects.
241 template <typename _Tp, typename _Dp = default_delete<_Tp>>
242 class unique_ptr
243 {
244 template <typename _Up>
245 using _DeleterConstraint =
246 typename __uniq_ptr_impl<_Tp, _Up>::_DeleterConstraint::type;
247
248 __uniq_ptr_data<_Tp, _Dp> _M_t;
249
250 public:
251 using pointer = typename __uniq_ptr_impl<_Tp, _Dp>::pointer;
252 using element_type = _Tp;
253 using deleter_type = _Dp;
254
255 private:
256 // helper template for detecting a safe conversion from another
257 // unique_ptr
258 template<typename _Up, typename _Ep>
259 using __safe_conversion_up = __and_<
260 is_convertible<typename unique_ptr<_Up, _Ep>::pointer, pointer>,
261 __not_<is_array<_Up>>
262 >;
263
264 public:
265 // Constructors.
266
267 /// Default constructor, creates a unique_ptr that owns nothing.
268 template<typename _Del = _Dp, typename = _DeleterConstraint<_Del>>
269 constexpr unique_ptr() noexcept
270 : _M_t()
271 { }
272
273 /** Takes ownership of a pointer.
274 *
275 * @param __p A pointer to an object of @c element_type
276 *
277 * The deleter will be value-initialized.
278 */
279 template<typename _Del = _Dp, typename = _DeleterConstraint<_Del>>
280 explicit
281 unique_ptr(pointer __p) noexcept
282 : _M_t(__p)
283 { }
284
285 /** Takes ownership of a pointer.
286 *
287 * @param __p A pointer to an object of @c element_type
288 * @param __d A reference to a deleter.
289 *
290 * The deleter will be initialized with @p __d
291 */
292 template<typename _Del = deleter_type,
293 typename = _Require<is_copy_constructible<_Del>>>
294 unique_ptr(pointer __p, const deleter_type& __d) noexcept
295 : _M_t(__p, __d) { }
296
297 /** Takes ownership of a pointer.
298 *
299 * @param __p A pointer to an object of @c element_type
300 * @param __d An rvalue reference to a (non-reference) deleter.
301 *
302 * The deleter will be initialized with @p std::move(__d)
303 */
304 template<typename _Del = deleter_type,
305 typename = _Require<is_move_constructible<_Del>>>
306 unique_ptr(pointer __p,
307 __enable_if_t<!is_lvalue_reference<_Del>::value,
308 _Del&&> __d) noexcept
309 : _M_t(__p, std::move(__d))
310 { }
311
312 template<typename _Del = deleter_type,
313 typename _DelUnref = typename remove_reference<_Del>::type>
314 unique_ptr(pointer,
315 __enable_if_t<is_lvalue_reference<_Del>::value,
316 _DelUnref&&>) = delete;
317
318 /// Creates a unique_ptr that owns nothing.
319 template<typename _Del = _Dp, typename = _DeleterConstraint<_Del>>
320 constexpr unique_ptr(nullptr_t) noexcept
321 : _M_t()
322 { }
323
324 // Move constructors.
325
326 /// Move constructor.
327 unique_ptr(unique_ptr&&) = default;
328
329 /** @brief Converting constructor from another type
330 *
331 * Requires that the pointer owned by @p __u is convertible to the
332 * type of pointer owned by this object, @p __u does not own an array,
333 * and @p __u has a compatible deleter type.
334 */
335 template<typename _Up, typename _Ep, typename = _Require<
336 __safe_conversion_up<_Up, _Ep>,
337 typename conditional<is_reference<_Dp>::value,
338 is_same<_Ep, _Dp>,
339 is_convertible<_Ep, _Dp>>::type>>
340 unique_ptr(unique_ptr<_Up, _Ep>&& __u) noexcept
341 : _M_t(__u.release(), std::forward<_Ep>(__u.get_deleter()))
342 { }
343
344#if _GLIBCXX_USE_DEPRECATED1
345#pragma GCC diagnostic push
346#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
347 /// Converting constructor from @c auto_ptr
348 template<typename _Up, typename = _Require<
349 is_convertible<_Up*, _Tp*>, is_same<_Dp, default_delete<_Tp>>>>
350 unique_ptr(auto_ptr<_Up>&& __u) noexcept;
351#pragma GCC diagnostic pop
352#endif
353
354 /// Destructor, invokes the deleter if the stored pointer is not null.
355 ~unique_ptr() noexcept
356 {
357 static_assert(__is_invocable<deleter_type&, pointer>::value,
358 "unique_ptr's deleter must be invocable with a pointer");
359 auto& __ptr = _M_t._M_ptr();
360 if (__ptr != nullptr)
361 get_deleter()(std::move(__ptr));
362 __ptr = pointer();
363 }
364
365 // Assignment.
366
367 /** @brief Move assignment operator.
368 *
369 * Invokes the deleter if this object owns a pointer.
370 */
371 unique_ptr& operator=(unique_ptr&&) = default;
372
373 /** @brief Assignment from another type.
374 *
375 * @param __u The object to transfer ownership from, which owns a
376 * convertible pointer to a non-array object.
377 *
378 * Invokes the deleter if this object owns a pointer.
379 */
380 template<typename _Up, typename _Ep>
381 typename enable_if< __and_<
382 __safe_conversion_up<_Up, _Ep>,
383 is_assignable<deleter_type&, _Ep&&>
384 >::value,
385 unique_ptr&>::type
386 operator=(unique_ptr<_Up, _Ep>&& __u) noexcept
387 {
388 reset(__u.release());
389 get_deleter() = std::forward<_Ep>(__u.get_deleter());
390 return *this;
391 }
392
393 /// Reset the %unique_ptr to empty, invoking the deleter if necessary.
394 unique_ptr&
395 operator=(nullptr_t) noexcept
396 {
397 reset();
398 return *this;
399 }
400
401 // Observers.
402
403 /// Dereference the stored pointer.
404 typename add_lvalue_reference<element_type>::type
405 operator*() const
406 {
407 __glibcxx_assert(get() != pointer());
408 return *get();
409 }
410
411 /// Return the stored pointer.
412 pointer
413 operator->() const noexcept
414 {
415 _GLIBCXX_DEBUG_PEDASSERT(get() != pointer());
416 return get();
417 }
418
419 /// Return the stored pointer.
420 pointer
421 get() const noexcept
422 { return _M_t._M_ptr(); }
423
424 /// Return a reference to the stored deleter.
425 deleter_type&
426 get_deleter() noexcept
427 { return _M_t._M_deleter(); }
428
429 /// Return a reference to the stored deleter.
430 const deleter_type&
431 get_deleter() const noexcept
432 { return _M_t._M_deleter(); }
433
434 /// Return @c true if the stored pointer is not null.
435 explicit operator bool() const noexcept
436 { return get() == pointer() ? false : true; }
437
438 // Modifiers.
439
440 /// Release ownership of any stored pointer.
441 pointer
442 release() noexcept
443 { return _M_t.release(); }
444
445 /** @brief Replace the stored pointer.
446 *
447 * @param __p The new pointer to store.
448 *
449 * The deleter will be invoked if a pointer is already owned.
450 */
451 void
452 reset(pointer __p = pointer()) noexcept
453 {
454 static_assert(__is_invocable<deleter_type&, pointer>::value,
455 "unique_ptr's deleter must be invocable with a pointer");
456 _M_t.reset(std::move(__p));
457 }
458
459 /// Exchange the pointer and deleter with another object.
460 void
461 swap(unique_ptr& __u) noexcept
462 {
463 static_assert(__is_swappable<_Dp>::value, "deleter must be swappable");
464 _M_t.swap(__u._M_t);
465 }
466
467 // Disable copy from lvalue.
468 unique_ptr(const unique_ptr&) = delete;
469 unique_ptr& operator=(const unique_ptr&) = delete;
470 };
471
472 /// 20.7.1.3 unique_ptr for array objects with a runtime length
473 // [unique.ptr.runtime]
474 // _GLIBCXX_RESOLVE_LIB_DEFECTS
475 // DR 740 - omit specialization for array objects with a compile time length
476 template<typename _Tp, typename _Dp>
477 class unique_ptr<_Tp[], _Dp>
478 {
479 template <typename _Up>
480 using _DeleterConstraint =
481 typename __uniq_ptr_impl<_Tp, _Up>::_DeleterConstraint::type;
482
483 __uniq_ptr_data<_Tp, _Dp> _M_t;
484
485 template<typename _Up>
486 using __remove_cv = typename remove_cv<_Up>::type;
487
488 // like is_base_of<_Tp, _Up> but false if unqualified types are the same
489 template<typename _Up>
490 using __is_derived_Tp
491 = __and_< is_base_of<_Tp, _Up>,
492 __not_<is_same<__remove_cv<_Tp>, __remove_cv<_Up>>> >;
493
494 public:
495 using pointer = typename __uniq_ptr_impl<_Tp, _Dp>::pointer;
496 using element_type = _Tp;
497 using deleter_type = _Dp;
498
499 // helper template for detecting a safe conversion from another
500 // unique_ptr
501 template<typename _Up, typename _Ep,
502 typename _UPtr = unique_ptr<_Up, _Ep>,
503 typename _UP_pointer = typename _UPtr::pointer,
504 typename _UP_element_type = typename _UPtr::element_type>
505 using __safe_conversion_up = __and_<
506 is_array<_Up>,
507 is_same<pointer, element_type*>,
508 is_same<_UP_pointer, _UP_element_type*>,
509 is_convertible<_UP_element_type(*)[], element_type(*)[]>
510 >;
511
512 // helper template for detecting a safe conversion from a raw pointer
513 template<typename _Up>
514 using __safe_conversion_raw = __and_<
515 __or_<__or_<is_same<_Up, pointer>,
516 is_same<_Up, nullptr_t>>,
517 __and_<is_pointer<_Up>,
518 is_same<pointer, element_type*>,
519 is_convertible<
520 typename remove_pointer<_Up>::type(*)[],
521 element_type(*)[]>
522 >
523 >
524 >;
525
526 // Constructors.
527
528 /// Default constructor, creates a unique_ptr that owns nothing.
529 template<typename _Del = _Dp, typename = _DeleterConstraint<_Del>>
530 constexpr unique_ptr() noexcept
531 : _M_t()
532 { }
533
534 /** Takes ownership of a pointer.
535 *
536 * @param __p A pointer to an array of a type safely convertible
537 * to an array of @c element_type
538 *
539 * The deleter will be value-initialized.
540 */
541 template<typename _Up,
542 typename _Vp = _Dp,
543 typename = _DeleterConstraint<_Vp>,
544 typename = typename enable_if<
545 __safe_conversion_raw<_Up>::value, bool>::type>
546 explicit
547 unique_ptr(_Up __p) noexcept
548 : _M_t(__p)
549 { }
550
551 /** Takes ownership of a pointer.
552 *
553 * @param __p A pointer to an array of a type safely convertible
554 * to an array of @c element_type
555 * @param __d A reference to a deleter.
556 *
557 * The deleter will be initialized with @p __d
558 */
559 template<typename _Up, typename _Del = deleter_type,
560 typename = _Require<__safe_conversion_raw<_Up>,
561 is_copy_constructible<_Del>>>
562 unique_ptr(_Up __p, const deleter_type& __d) noexcept
563 : _M_t(__p, __d) { }
564
565 /** Takes ownership of a pointer.
566 *
567 * @param __p A pointer to an array of a type safely convertible
568 * to an array of @c element_type
569 * @param __d A reference to a deleter.
570 *
571 * The deleter will be initialized with @p std::move(__d)
572 */
573 template<typename _Up, typename _Del = deleter_type,
574 typename = _Require<__safe_conversion_raw<_Up>,
575 is_move_constructible<_Del>>>
576 unique_ptr(_Up __p,
577 __enable_if_t<!is_lvalue_reference<_Del>::value,
578 _Del&&> __d) noexcept
579 : _M_t(std::move(__p), std::move(__d))
580 { }
581
582 template<typename _Up, typename _Del = deleter_type,
583 typename _DelUnref = typename remove_reference<_Del>::type,
584 typename = _Require<__safe_conversion_raw<_Up>>>
585 unique_ptr(_Up,
586 __enable_if_t<is_lvalue_reference<_Del>::value,
587 _DelUnref&&>) = delete;
588
589 /// Move constructor.
590 unique_ptr(unique_ptr&&) = default;
591
592 /// Creates a unique_ptr that owns nothing.
593 template<typename _Del = _Dp, typename = _DeleterConstraint<_Del>>
594 constexpr unique_ptr(nullptr_t) noexcept
595 : _M_t()
596 { }
597
598 template<typename _Up, typename _Ep, typename = _Require<
599 __safe_conversion_up<_Up, _Ep>,
600 typename conditional<is_reference<_Dp>::value,
601 is_same<_Ep, _Dp>,
602 is_convertible<_Ep, _Dp>>::type>>
603 unique_ptr(unique_ptr<_Up, _Ep>&& __u) noexcept
604 : _M_t(__u.release(), std::forward<_Ep>(__u.get_deleter()))
605 { }
606
607 /// Destructor, invokes the deleter if the stored pointer is not null.
608 ~unique_ptr()
609 {
610 auto& __ptr = _M_t._M_ptr();
611 if (__ptr != nullptr)
612 get_deleter()(__ptr);
613 __ptr = pointer();
614 }
615
616 // Assignment.
617
618 /** @brief Move assignment operator.
619 *
620 * Invokes the deleter if this object owns a pointer.
621 */
622 unique_ptr&
623 operator=(unique_ptr&&) = default;
624
625 /** @brief Assignment from another type.
626 *
627 * @param __u The object to transfer ownership from, which owns a
628 * convertible pointer to an array object.
629 *
630 * Invokes the deleter if this object owns a pointer.
631 */
632 template<typename _Up, typename _Ep>
633 typename
634 enable_if<__and_<__safe_conversion_up<_Up, _Ep>,
635 is_assignable<deleter_type&, _Ep&&>
636 >::value,
637 unique_ptr&>::type
638 operator=(unique_ptr<_Up, _Ep>&& __u) noexcept
639 {
640 reset(__u.release());
641 get_deleter() = std::forward<_Ep>(__u.get_deleter());
642 return *this;
643 }
644
645 /// Reset the %unique_ptr to empty, invoking the deleter if necessary.
646 unique_ptr&
647 operator=(nullptr_t) noexcept
648 {
649 reset();
650 return *this;
651 }
652
653 // Observers.
654
655 /// Access an element of owned array.
656 typename std::add_lvalue_reference<element_type>::type
657 operator[](size_t __i) const
658 {
659 __glibcxx_assert(get() != pointer());
660 return get()[__i];
661 }
662
663 /// Return the stored pointer.
664 pointer
665 get() const noexcept
666 { return _M_t._M_ptr(); }
667
668 /// Return a reference to the stored deleter.
669 deleter_type&
670 get_deleter() noexcept
671 { return _M_t._M_deleter(); }
672
673 /// Return a reference to the stored deleter.
674 const deleter_type&
675 get_deleter() const noexcept
676 { return _M_t._M_deleter(); }
677
678 /// Return @c true if the stored pointer is not null.
679 explicit operator bool() const noexcept
680 { return get() == pointer() ? false : true; }
681
682 // Modifiers.
683
684 /// Release ownership of any stored pointer.
685 pointer
686 release() noexcept
687 { return _M_t.release(); }
688
689 /** @brief Replace the stored pointer.
690 *
691 * @param __p The new pointer to store.
692 *
693 * The deleter will be invoked if a pointer is already owned.
694 */
695 template <typename _Up,
696 typename = _Require<
697 __or_<is_same<_Up, pointer>,
698 __and_<is_same<pointer, element_type*>,
699 is_pointer<_Up>,
700 is_convertible<
701 typename remove_pointer<_Up>::type(*)[],
702 element_type(*)[]
703 >
704 >
705 >
706 >>
707 void
708 reset(_Up __p) noexcept
709 { _M_t.reset(std::move(__p)); }
710
711 void reset(nullptr_t = nullptr) noexcept
712 { reset(pointer()); }
713
714 /// Exchange the pointer and deleter with another object.
715 void
716 swap(unique_ptr& __u) noexcept
717 {
718 static_assert(__is_swappable<_Dp>::value, "deleter must be swappable");
719 _M_t.swap(__u._M_t);
720 }
721
722 // Disable copy from lvalue.
723 unique_ptr(const unique_ptr&) = delete;
724 unique_ptr& operator=(const unique_ptr&) = delete;
725 };
726
727 /// @relates unique_ptr @{
728
729 /// Swap overload for unique_ptr
730 template<typename _Tp, typename _Dp>
731 inline
732#if __cplusplus201402L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
733 // Constrained free swap overload, see p0185r1
734 typename enable_if<__is_swappable<_Dp>::value>::type
735#else
736 void
737#endif
738 swap(unique_ptr<_Tp, _Dp>& __x,
739 unique_ptr<_Tp, _Dp>& __y) noexcept
740 { __x.swap(__y); }
741
742#if __cplusplus201402L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
743 template<typename _Tp, typename _Dp>
744 typename enable_if<!__is_swappable<_Dp>::value>::type
745 swap(unique_ptr<_Tp, _Dp>&,
746 unique_ptr<_Tp, _Dp>&) = delete;
747#endif
748
749 /// Equality operator for unique_ptr objects, compares the owned pointers
750 template<typename _Tp, typename _Dp,
751 typename _Up, typename _Ep>
752 _GLIBCXX_NODISCARD inline bool
753 operator==(const unique_ptr<_Tp, _Dp>& __x,
754 const unique_ptr<_Up, _Ep>& __y)
755 { return __x.get() == __y.get(); }
756
757 /// unique_ptr comparison with nullptr
758 template<typename _Tp, typename _Dp>
759 _GLIBCXX_NODISCARD inline bool
760 operator==(const unique_ptr<_Tp, _Dp>& __x, nullptr_t) noexcept
761 { return !__x; }
762
763#ifndef __cpp_lib_three_way_comparison
764 /// unique_ptr comparison with nullptr
765 template<typename _Tp, typename _Dp>
766 _GLIBCXX_NODISCARD inline bool
767 operator==(nullptr_t, const unique_ptr<_Tp, _Dp>& __x) noexcept
768 { return !__x; }
769
770 /// Inequality operator for unique_ptr objects, compares the owned pointers
771 template<typename _Tp, typename _Dp,
772 typename _Up, typename _Ep>
773 _GLIBCXX_NODISCARD inline bool
774 operator!=(const unique_ptr<_Tp, _Dp>& __x,
775 const unique_ptr<_Up, _Ep>& __y)
776 { return __x.get() != __y.get(); }
777
778 /// unique_ptr comparison with nullptr
779 template<typename _Tp, typename _Dp>
780 _GLIBCXX_NODISCARD inline bool
781 operator!=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t) noexcept
782 { return (bool)__x; }
783
784 /// unique_ptr comparison with nullptr
785 template<typename _Tp, typename _Dp>
786 _GLIBCXX_NODISCARD inline bool
787 operator!=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x) noexcept
788 { return (bool)__x; }
789#endif // three way comparison
790
791 /// Relational operator for unique_ptr objects, compares the owned pointers
792 template<typename _Tp, typename _Dp,
793 typename _Up, typename _Ep>
794 _GLIBCXX_NODISCARD inline bool
795 operator<(const unique_ptr<_Tp, _Dp>& __x,
796 const unique_ptr<_Up, _Ep>& __y)
797 {
798 typedef typename
799 std::common_type<typename unique_ptr<_Tp, _Dp>::pointer,
800 typename unique_ptr<_Up, _Ep>::pointer>::type _CT;
801 return std::less<_CT>()(__x.get(), __y.get());
802 }
803
804 /// unique_ptr comparison with nullptr
805 template<typename _Tp, typename _Dp>
806 _GLIBCXX_NODISCARD inline bool
807 operator<(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
808 {
809 return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(__x.get(),
810 nullptr);
811 }
812
813 /// unique_ptr comparison with nullptr
814 template<typename _Tp, typename _Dp>
815 _GLIBCXX_NODISCARD inline bool
816 operator<(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
817 {
818 return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(nullptr,
819 __x.get());
820 }
821
822 /// Relational operator for unique_ptr objects, compares the owned pointers
823 template<typename _Tp, typename _Dp,
824 typename _Up, typename _Ep>
825 _GLIBCXX_NODISCARD inline bool
826 operator<=(const unique_ptr<_Tp, _Dp>& __x,
827 const unique_ptr<_Up, _Ep>& __y)
828 { return !(__y < __x); }
829
830 /// unique_ptr comparison with nullptr
831 template<typename _Tp, typename _Dp>
832 _GLIBCXX_NODISCARD inline bool
833 operator<=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
834 { return !(nullptr < __x); }
835
836 /// unique_ptr comparison with nullptr
837 template<typename _Tp, typename _Dp>
838 _GLIBCXX_NODISCARD inline bool
839 operator<=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
840 { return !(__x < nullptr); }
841
842 /// Relational operator for unique_ptr objects, compares the owned pointers
843 template<typename _Tp, typename _Dp,
844 typename _Up, typename _Ep>
845 _GLIBCXX_NODISCARD inline bool
846 operator>(const unique_ptr<_Tp, _Dp>& __x,
847 const unique_ptr<_Up, _Ep>& __y)
848 { return (__y < __x); }
849
850 /// unique_ptr comparison with nullptr
851 template<typename _Tp, typename _Dp>
852 _GLIBCXX_NODISCARD inline bool
853 operator>(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
854 {
855 return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(nullptr,
856 __x.get());
857 }
858
859 /// unique_ptr comparison with nullptr
860 template<typename _Tp, typename _Dp>
861 _GLIBCXX_NODISCARD inline bool
862 operator>(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
863 {
864 return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(__x.get(),
865 nullptr);
866 }
867
868 /// Relational operator for unique_ptr objects, compares the owned pointers
869 template<typename _Tp, typename _Dp,
870 typename _Up, typename _Ep>
871 _GLIBCXX_NODISCARD inline bool
872 operator>=(const unique_ptr<_Tp, _Dp>& __x,
873 const unique_ptr<_Up, _Ep>& __y)
874 { return !(__x < __y); }
875
876 /// unique_ptr comparison with nullptr
877 template<typename _Tp, typename _Dp>
878 _GLIBCXX_NODISCARD inline bool
879 operator>=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
880 { return !(__x < nullptr); }
881
882 /// unique_ptr comparison with nullptr
883 template<typename _Tp, typename _Dp>
884 _GLIBCXX_NODISCARD inline bool
885 operator>=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
886 { return !(nullptr < __x); }
887
888#ifdef __cpp_lib_three_way_comparison
889 template<typename _Tp, typename _Dp, typename _Up, typename _Ep>
890 requires three_way_comparable_with<typename unique_ptr<_Tp, _Dp>::pointer,
891 typename unique_ptr<_Up, _Ep>::pointer>
892 inline
893 compare_three_way_result_t<typename unique_ptr<_Tp, _Dp>::pointer,
894 typename unique_ptr<_Up, _Ep>::pointer>
895 operator<=>(const unique_ptr<_Tp, _Dp>& __x,
896 const unique_ptr<_Up, _Ep>& __y)
897 { return compare_three_way()(__x.get(), __y.get()); }
898
899 template<typename _Tp, typename _Dp>
900 requires three_way_comparable<typename unique_ptr<_Tp, _Dp>::pointer>
901 inline
902 compare_three_way_result_t<typename unique_ptr<_Tp, _Dp>::pointer>
903 operator<=>(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
904 {
905 using pointer = typename unique_ptr<_Tp, _Dp>::pointer;
906 return compare_three_way()(__x.get(), static_cast<pointer>(nullptr));
907 }
908#endif
909 // @} relates unique_ptr
910
911 /// @cond undocumented
912 template<typename _Up, typename _Ptr = typename _Up::pointer,
913 bool = __poison_hash<_Ptr>::__enable_hash_call>
914 struct __uniq_ptr_hash
915#if ! _GLIBCXX_INLINE_VERSION0
916 : private __poison_hash<_Ptr>
917#endif
918 {
919 size_t
920 operator()(const _Up& __u) const
921 noexcept(noexcept(std::declval<hash<_Ptr>>()(std::declval<_Ptr>())))
922 { return hash<_Ptr>()(__u.get()); }
923 };
924
925 template<typename _Up, typename _Ptr>
926 struct __uniq_ptr_hash<_Up, _Ptr, false>
927 : private __poison_hash<_Ptr>
928 { };
929 /// @endcond
930
931 /// std::hash specialization for unique_ptr.
932 template<typename _Tp, typename _Dp>
933 struct hash<unique_ptr<_Tp, _Dp>>
934 : public __hash_base<size_t, unique_ptr<_Tp, _Dp>>,
935 public __uniq_ptr_hash<unique_ptr<_Tp, _Dp>>
936 { };
937
938#if __cplusplus201402L >= 201402L
939 /// @relates unique_ptr @{
940#define __cpp_lib_make_unique201304 201304
941
942 /// @cond undocumented
943
944 template<typename _Tp>
945 struct _MakeUniq
946 { typedef unique_ptr<_Tp> __single_object; };
947
948 template<typename _Tp>
949 struct _MakeUniq<_Tp[]>
950 { typedef unique_ptr<_Tp[]> __array; };
951
952 template<typename _Tp, size_t _Bound>
953 struct _MakeUniq<_Tp[_Bound]>
954 { struct __invalid_type { }; };
955
956 /// @endcond
957
958 /// std::make_unique for single objects
959 template<typename _Tp, typename... _Args>
960 inline typename _MakeUniq<_Tp>::__single_object
961 make_unique(_Args&&... __args)
962 { return unique_ptr<_Tp>(new _Tp(std::forward<_Args>(__args)...)); }
7
←
Calling constructor for 'ResourceState'
→
963
964 /// std::make_unique for arrays of unknown bound
965 template<typename _Tp>
966 inline typename _MakeUniq<_Tp>::__array
967 make_unique(size_t __num)
968 { return unique_ptr<_Tp>(new remove_extent_t<_Tp>[__num]()); }
969
970 /// Disable std::make_unique for arrays of known bound
971 template<typename _Tp, typename... _Args>
972 inline typename _MakeUniq<_Tp>::__invalid_type
973 make_unique(_Args&&...) = delete;
974 // @} relates unique_ptr
975#endif // C++14
976
977#if __cplusplus201402L > 201703L && __cpp_concepts
978 // _GLIBCXX_RESOLVE_LIB_DEFECTS
979 // 2948. unique_ptr does not define operator<< for stream output
980 /// Stream output operator for unique_ptr
981 template<typename _CharT, typename _Traits, typename _Tp, typename _Dp>
982 inline basic_ostream<_CharT, _Traits>&
983 operator<<(basic_ostream<_CharT, _Traits>& __os,
984 const unique_ptr<_Tp, _Dp>& __p)
985 requires requires { __os << __p.get(); }
986 {
987 __os << __p.get();
988 return __os;
989 }
990#endif // C++20
991
992 // @} group pointer_abstractions
993
994#if __cplusplus201402L >= 201703L
995 namespace __detail::__variant
996 {
997 template<typename> struct _Never_valueless_alt; // see <variant>
998
999 // Provide the strong exception-safety guarantee when emplacing a
1000 // unique_ptr into a variant.
1001 template<typename _Tp, typename _Del>
1002 struct _Never_valueless_alt<std::unique_ptr<_Tp, _Del>>
1003 : std::true_type
1004 { };
1005 } // namespace __detail::__variant
1006#endif // C++17
1007
1008_GLIBCXX_END_NAMESPACE_VERSION
1009} // namespace
1010
1011#endif /* _UNIQUE_PTR_H */
←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/MCA/Support.h

1//===--------------------- Support.h ----------------------------*- 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/// \file
9///
10/// Helper functions used by various pipeline components.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_MCA_SUPPORT_H
15#define LLVM_MCA_SUPPORT_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/MC/MCSchedule.h"
20#include "llvm/Support/Error.h"
21#include "llvm/Support/MathExtras.h"
22
23namespace llvm {
24namespace mca {
25
26template <typename T>
27class InstructionError : public ErrorInfo<InstructionError<T>> {
28public:
29 static char ID;
30 std::string Message;
31 const T &Inst;
32
33 InstructionError(std::string M, const T &MCI)
34 : Message(std::move(M)), Inst(MCI) {}
35
36 void log(raw_ostream &OS) const override { OS << Message; }
37
38 std::error_code convertToErrorCode() const override {
39 return inconvertibleErrorCode();
40 }
41};
42
43template <typename T> char InstructionError<T>::ID;
44
45/// This class represents the number of cycles per resource (fractions of
46/// cycles). That quantity is managed here as a ratio, and accessed via the
47/// double cast-operator below. The two quantities, number of cycles and
48/// number of resources, are kept separate. This is used by the
49/// ResourcePressureView to calculate the average resource cycles
50/// per instruction/iteration.
51class ResourceCycles {
52 unsigned Numerator, Denominator;
53
54public:
55 ResourceCycles() : Numerator(0), Denominator(1) {}
56 ResourceCycles(unsigned Cycles, unsigned ResourceUnits = 1)
57 : Numerator(Cycles), Denominator(ResourceUnits) {}
58
59 operator double() const {
60 assert(Denominator && "Invalid denominator (must be non-zero).")(static_cast<void> (0));
61 return (Denominator == 1) ? Numerator : (double)Numerator / Denominator;
62 }
63
64 unsigned getNumerator() const { return Numerator; }
65 unsigned getDenominator() const { return Denominator; }
66
67 // Add the components of RHS to this instance. Instead of calculating
68 // the final value here, we keep track of the numerator and denominator
69 // separately, to reduce floating point error.
70 ResourceCycles &operator+=(const ResourceCycles &RHS);
71};
72
73/// Populates vector Masks with processor resource masks.
74///
75/// The number of bits set in a mask depends on the processor resource type.
76/// Each processor resource mask has at least one bit set. For groups, the
77/// number of bits set in the mask is equal to the cardinality of the group plus
78/// one. Excluding the most significant bit, the remaining bits in the mask
79/// identify processor resources that are part of the group.
80///
81/// Example:
82///
83/// ResourceA -- Mask: 0b001
84/// ResourceB -- Mask: 0b010
85/// ResourceAB -- Mask: 0b100 U (ResourceA::Mask | ResourceB::Mask) == 0b111
86///
87/// ResourceAB is a processor resource group containing ResourceA and ResourceB.
88/// Each resource mask uniquely identifies a resource; both ResourceA and
89/// ResourceB only have one bit set.
90/// ResourceAB is a group; excluding the most significant bit in the mask, the
91/// remaining bits identify the composition of the group.
92///
93/// Resource masks are used by the ResourceManager to solve set membership
94/// problems with simple bit manipulation operations.
95void computeProcResourceMasks(const MCSchedModel &SM,
96 MutableArrayRef<uint64_t> Masks);
97
98// Returns the index of the highest bit set. For resource masks, the position of
99// the highest bit set can be used to construct a resource mask identifier.
100inline unsigned getResourceStateIndex(uint64_t Mask) {
101 assert(Mask && "Processor Resource Mask cannot be zero!")(static_cast<void> (0));
102 return (std::numeric_limits<uint64_t>::digits - countLeadingZeros(Mask)) - 1;
11
←
Returning the value 4294967295
→
103}
104
105/// Compute the reciprocal block throughput from a set of processor resource
106/// cycles. The reciprocal block throughput is computed as the MAX between:
107/// - NumMicroOps / DispatchWidth
108/// - ProcResourceCycles / #ProcResourceUnits (for every consumed resource).
109double computeBlockRThroughput(const MCSchedModel &SM, unsigned DispatchWidth,
110 unsigned NumMicroOps,
111 ArrayRef<unsigned> ProcResourceUsage);
112} // namespace mca
113} // namespace llvm
114
115#endif // LLVM_MCA_SUPPORT_H