1// Raw memory manipulators -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996,1997 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52/** @file stl_uninitialized.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 55 */ 56 57#ifndef _STL_UNINITIALIZED_H 58#define _STL_UNINITIALIZED_H 1 59 60_GLIBCXX_BEGIN_NAMESPACE(std) 61 62 template<bool> 63 struct __uninitialized_copy 64 { 65 template<typename _InputIterator, typename _ForwardIterator> 66 static _ForwardIterator 67 uninitialized_copy(_InputIterator __first, _InputIterator __last, 68 _ForwardIterator __result) 69 { 70 _ForwardIterator __cur = __result; 71 __try 72 { 73 for (; __first != __last; ++__first, ++__cur) 74 std::_Construct(&*__cur, *__first); 75 return __cur; 76 } 77 __catch(...) 78 { 79 std::_Destroy(__result, __cur); 80 __throw_exception_again; 81 } 82 } 83 }; 84 85 template<> 86 struct __uninitialized_copy<true> 87 { 88 template<typename _InputIterator, typename _ForwardIterator> 89 static _ForwardIterator 90 uninitialized_copy(_InputIterator __first, _InputIterator __last, 91 _ForwardIterator __result) 92 { return std::copy(__first, __last, __result); } 93 }; 94 95 /** 96 * @brief Copies the range [first,last) into result. 97 * @param first An input iterator. 98 * @param last An input iterator. 99 * @param result An output iterator. 100 * @return result + (first - last) 101 * 102 * Like copy(), but does not require an initialized output range. 103 */ 104 template<typename _InputIterator, typename _ForwardIterator> 105 inline _ForwardIterator 106 uninitialized_copy(_InputIterator __first, _InputIterator __last, 107 _ForwardIterator __result) 108 { 109 typedef typename iterator_traits<_InputIterator>::value_type 110 _ValueType1; 111 typedef typename iterator_traits<_ForwardIterator>::value_type 112 _ValueType2; 113 114 return std::__uninitialized_copy<(__is_pod(_ValueType1) 115 && __is_pod(_ValueType2))>:: 116 uninitialized_copy(__first, __last, __result); 117 } 118 119 120 template<bool> 121 struct __uninitialized_fill 122 { 123 template<typename _ForwardIterator, typename _Tp> 124 static void 125 uninitialized_fill(_ForwardIterator __first, 126 _ForwardIterator __last, const _Tp& __x) 127 { 128 _ForwardIterator __cur = __first; 129 __try 130 { 131 for (; __cur != __last; ++__cur) 132 std::_Construct(&*__cur, __x); 133 } 134 __catch(...) 135 { 136 std::_Destroy(__first, __cur); 137 __throw_exception_again; 138 } 139 } 140 }; 141 142 template<> 143 struct __uninitialized_fill<true> 144 { 145 template<typename _ForwardIterator, typename _Tp> 146 static void 147 uninitialized_fill(_ForwardIterator __first, 148 _ForwardIterator __last, const _Tp& __x) 149 { std::fill(__first, __last, __x); } 150 }; 151 152 /** 153 * @brief Copies the value x into the range [first,last). 154 * @param first An input iterator. 155 * @param last An input iterator. 156 * @param x The source value. 157 * @return Nothing. 158 * 159 * Like fill(), but does not require an initialized output range. 160 */ 161 template<typename _ForwardIterator, typename _Tp> 162 inline void 163 uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, 164 const _Tp& __x) 165 { 166 typedef typename iterator_traits<_ForwardIterator>::value_type 167 _ValueType; 168 169 std::__uninitialized_fill<__is_pod(_ValueType)>:: 170 uninitialized_fill(__first, __last, __x); 171 } 172 173 174 template<bool> 175 struct __uninitialized_construct_range_dispatch 176 { 177 template<typename _ForwardIterator, typename _Tp> 178 static void 179 __ucr(_ForwardIterator __first, _ForwardIterator __last, 180 _Tp& __value) 181 { 182 if(__first == __last) 183 return; 184 185 _ForwardIterator __cur = __first; 186 __try 187 { 188 std::_Construct(&*__first, _GLIBCXX_MOVE(__value)); 189 _ForwardIterator __prev = __cur; 190 ++__cur; 191 for(; __cur != __last; ++__cur, ++__prev) 192 std::_Construct(&*__cur, _GLIBCXX_MOVE(*__prev)); 193 __value = _GLIBCXX_MOVE(*__prev); 194 } 195 __catch(...) 196 { 197 std::_Destroy(__first, __cur); 198 __throw_exception_again; 199 } 200 } 201 }; 202 203 template<> 204 struct __uninitialized_construct_range_dispatch<true> 205 { 206 template<typename _ForwardIterator, typename _Tp> 207 static void 208 __ucr(_ForwardIterator, _ForwardIterator, _Tp&) { } 209 }; 210 211 // Constructs objects in the range [first, last). 212 // Note that while these new objects will take valid values, 213 // their exact value is not defined. In particular they may 214 // be 'moved from'. 215 // 216 // While __value may altered during this algorithm, it will have 217 // the same value when the algorithm finishes, unless one of the 218 // constructions throws. 219 // 220 // Requirements: _ForwardIterator::value_type(_Tp&&) is valid. 221 template<typename _ForwardIterator, typename _Tp> 222 inline void 223 __uninitialized_construct_range(_ForwardIterator __first, 224 _ForwardIterator __last, 225 _Tp& __value) 226 { 227 typedef typename std::iterator_traits<_ForwardIterator>::value_type 228 _ValueType; 229 230 std::__uninitialized_construct_range_dispatch< 231 __has_trivial_constructor(_ValueType)>:: 232 __ucr(__first, __last, __value); 233 } 234 235 236 template<bool> 237 struct __uninitialized_fill_n 238 { 239 template<typename _ForwardIterator, typename _Size, typename _Tp> 240 static void 241 uninitialized_fill_n(_ForwardIterator __first, _Size __n, 242 const _Tp& __x) 243 { 244 _ForwardIterator __cur = __first; 245 __try 246 { 247 for (; __n > 0; --__n, ++__cur) 248 std::_Construct(&*__cur, __x); 249 } 250 __catch(...) 251 { 252 std::_Destroy(__first, __cur); 253 __throw_exception_again; 254 } 255 } 256 }; 257 258 template<> 259 struct __uninitialized_fill_n<true> 260 { 261 template<typename _ForwardIterator, typename _Size, typename _Tp> 262 static void 263 uninitialized_fill_n(_ForwardIterator __first, _Size __n, 264 const _Tp& __x) 265 { std::fill_n(__first, __n, __x); } 266 }; 267 268 /** 269 * @brief Copies the value x into the range [first,first+n). 270 * @param first An input iterator. 271 * @param n The number of copies to make. 272 * @param x The source value. 273 * @return Nothing. 274 * 275 * Like fill_n(), but does not require an initialized output range. 276 */ 277 template<typename _ForwardIterator, typename _Size, typename _Tp> 278 inline void 279 uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 280 { 281 typedef typename iterator_traits<_ForwardIterator>::value_type 282 _ValueType; 283 284 std::__uninitialized_fill_n<__is_pod(_ValueType)>:: 285 uninitialized_fill_n(__first, __n, __x); 286 } 287 288 // Extensions: versions of uninitialized_copy, uninitialized_fill, 289 // and uninitialized_fill_n that take an allocator parameter. 290 // We dispatch back to the standard versions when we're given the 291 // default allocator. For nondefault allocators we do not use 292 // any of the POD optimizations. 293 294 template<typename _InputIterator, typename _ForwardIterator, 295 typename _Allocator> 296 _ForwardIterator 297 __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, 298 _ForwardIterator __result, _Allocator& __alloc) 299 { 300 _ForwardIterator __cur = __result; 301 __try 302 { 303 for (; __first != __last; ++__first, ++__cur) 304 __alloc.construct(&*__cur, *__first); 305 return __cur; 306 } 307 __catch(...) 308 { 309 std::_Destroy(__result, __cur, __alloc); 310 __throw_exception_again; 311 } 312 } 313 314 template<typename _InputIterator, typename _ForwardIterator, typename _Tp> 315 inline _ForwardIterator 316 __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, 317 _ForwardIterator __result, allocator<_Tp>&) 318 { return std::uninitialized_copy(__first, __last, __result); } 319 320 template<typename _InputIterator, typename _ForwardIterator, 321 typename _Allocator> 322 inline _ForwardIterator 323 __uninitialized_move_a(_InputIterator __first, _InputIterator __last, 324 _ForwardIterator __result, _Allocator& __alloc) 325 { 326 return std::__uninitialized_copy_a(_GLIBCXX_MAKE_MOVE_ITERATOR(__first), 327 _GLIBCXX_MAKE_MOVE_ITERATOR(__last), 328 __result, __alloc); 329 } 330 331 template<typename _ForwardIterator, typename _Tp, typename _Allocator> 332 void 333 __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last, 334 const _Tp& __x, _Allocator& __alloc) 335 { 336 _ForwardIterator __cur = __first; 337 __try 338 { 339 for (; __cur != __last; ++__cur) 340 __alloc.construct(&*__cur, __x); 341 } 342 __catch(...) 343 { 344 std::_Destroy(__first, __cur, __alloc); 345 __throw_exception_again; 346 } 347 } 348 349 template<typename _ForwardIterator, typename _Tp, typename _Tp2> 350 inline void 351 __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last, 352 const _Tp& __x, allocator<_Tp2>&) 353 { std::uninitialized_fill(__first, __last, __x); } 354 355 template<typename _ForwardIterator, typename _Size, typename _Tp, 356 typename _Allocator> 357 void 358 __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 359 const _Tp& __x, _Allocator& __alloc) 360 { 361 _ForwardIterator __cur = __first; 362 __try 363 { 364 for (; __n > 0; --__n, ++__cur) 365 __alloc.construct(&*__cur, __x); 366 } 367 __catch(...) 368 { 369 std::_Destroy(__first, __cur, __alloc); 370 __throw_exception_again; 371 } 372 } 373 374 template<typename _ForwardIterator, typename _Size, typename _Tp, 375 typename _Tp2> 376 inline void 377 __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 378 const _Tp& __x, allocator<_Tp2>&) 379 { std::uninitialized_fill_n(__first, __n, __x); } 380 381 382 // Extensions: __uninitialized_copy_move, __uninitialized_move_copy, 383 // __uninitialized_fill_move, __uninitialized_move_fill. 384 // All of these algorithms take a user-supplied allocator, which is used 385 // for construction and destruction. 386 387 // __uninitialized_copy_move 388 // Copies [first1, last1) into [result, result + (last1 - first1)), and 389 // move [first2, last2) into 390 // [result, result + (last1 - first1) + (last2 - first2)). 391 template<typename _InputIterator1, typename _InputIterator2, 392 typename _ForwardIterator, typename _Allocator> 393 inline _ForwardIterator 394 __uninitialized_copy_move(_InputIterator1 __first1, 395 _InputIterator1 __last1, 396 _InputIterator2 __first2, 397 _InputIterator2 __last2, 398 _ForwardIterator __result, 399 _Allocator& __alloc) 400 { 401 _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1, 402 __result, 403 __alloc); 404 __try 405 { 406 return std::__uninitialized_move_a(__first2, __last2, __mid, __alloc); 407 } 408 __catch(...) 409 { 410 std::_Destroy(__result, __mid, __alloc); 411 __throw_exception_again; 412 } 413 } 414 415 // __uninitialized_move_copy 416 // Moves [first1, last1) into [result, result + (last1 - first1)), and 417 // copies [first2, last2) into 418 // [result, result + (last1 - first1) + (last2 - first2)). 419 template<typename _InputIterator1, typename _InputIterator2, 420 typename _ForwardIterator, typename _Allocator> 421 inline _ForwardIterator 422 __uninitialized_move_copy(_InputIterator1 __first1, 423 _InputIterator1 __last1, 424 _InputIterator2 __first2, 425 _InputIterator2 __last2, 426 _ForwardIterator __result, 427 _Allocator& __alloc) 428 { 429 _ForwardIterator __mid = std::__uninitialized_move_a(__first1, __last1, 430 __result, 431 __alloc); 432 __try 433 { 434 return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc); 435 } 436 __catch(...) 437 { 438 std::_Destroy(__result, __mid, __alloc); 439 __throw_exception_again; 440 } 441 } 442 443 // __uninitialized_fill_move 444 // Fills [result, mid) with x, and moves [first, last) into 445 // [mid, mid + (last - first)). 446 template<typename _ForwardIterator, typename _Tp, typename _InputIterator, 447 typename _Allocator> 448 inline _ForwardIterator 449 __uninitialized_fill_move(_ForwardIterator __result, _ForwardIterator __mid, 450 const _Tp& __x, _InputIterator __first, 451 _InputIterator __last, _Allocator& __alloc) 452 { 453 std::__uninitialized_fill_a(__result, __mid, __x, __alloc); 454 __try 455 { 456 return std::__uninitialized_move_a(__first, __last, __mid, __alloc); 457 } 458 __catch(...) 459 { 460 std::_Destroy(__result, __mid, __alloc); 461 __throw_exception_again; 462 } 463 } 464 465 // __uninitialized_move_fill 466 // Moves [first1, last1) into [first2, first2 + (last1 - first1)), and 467 // fills [first2 + (last1 - first1), last2) with x. 468 template<typename _InputIterator, typename _ForwardIterator, typename _Tp, 469 typename _Allocator> 470 inline void 471 __uninitialized_move_fill(_InputIterator __first1, _InputIterator __last1, 472 _ForwardIterator __first2, 473 _ForwardIterator __last2, const _Tp& __x, 474 _Allocator& __alloc) 475 { 476 _ForwardIterator __mid2 = std::__uninitialized_move_a(__first1, __last1, 477 __first2, 478 __alloc); 479 __try 480 { 481 std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc); 482 } 483 __catch(...) 484 { 485 std::_Destroy(__first2, __mid2, __alloc); 486 __throw_exception_again; 487 } 488 } 489 490#ifdef __GXX_EXPERIMENTAL_CXX0X__ 491 template<typename _InputIterator, typename _Size, 492 typename _ForwardIterator> 493 _ForwardIterator 494 __uninitialized_copy_n(_InputIterator __first, _Size __n, 495 _ForwardIterator __result, input_iterator_tag) 496 { 497 _ForwardIterator __cur = __result; 498 __try 499 { 500 for (; __n > 0; --__n, ++__first, ++__cur) 501 ::new(static_cast<void*>(&*__cur)) typename 502 iterator_traits<_ForwardIterator>::value_type(*__first); 503 return __cur; 504 } 505 __catch(...) 506 { 507 std::_Destroy(__result, __cur); 508 __throw_exception_again; 509 } 510 } 511 512 template<typename _RandomAccessIterator, typename _Size, 513 typename _ForwardIterator> 514 inline _ForwardIterator 515 __uninitialized_copy_n(_RandomAccessIterator __first, _Size __n, 516 _ForwardIterator __result, 517 random_access_iterator_tag) 518 { return std::uninitialized_copy(__first, __first + __n, __result); } 519 520 /** 521 * @brief Copies the range [first,first+n) into result. 522 * @param first An input iterator. 523 * @param n The number of elements to copy. 524 * @param result An output iterator. 525 * @return result + n 526 * 527 * Like copy_n(), but does not require an initialized output range. 528 */ 529 template<typename _InputIterator, typename _Size, typename _ForwardIterator> 530 inline _ForwardIterator 531 uninitialized_copy_n(_InputIterator __first, _Size __n, 532 _ForwardIterator __result) 533 { return std::__uninitialized_copy_n(__first, __n, __result, 534 std::__iterator_category(__first)); } 535#endif 536 537_GLIBCXX_END_NAMESPACE 538 539#endif /* _STL_UNINITIALIZED_H */ 540