multiway_mergesort.h revision 1.11
1103285Sikob// -*- C++ -*- 2113584Ssimokawa 3113584Ssimokawa// Copyright (C) 2007-2020 Free Software Foundation, Inc. 4103285Sikob// 5103285Sikob// This file is part of the GNU ISO C++ Library. This library is free 6103285Sikob// software; you can redistribute it and/or modify it under the terms 7103285Sikob// of the GNU General Public License as published by the Free Software 8103285Sikob// Foundation; either version 3, or (at your option) any later 9103285Sikob// version. 10103285Sikob 11103285Sikob// This library is distributed in the hope that it will be useful, but 12103285Sikob// WITHOUT ANY WARRANTY; without even the implied warranty of 13103285Sikob// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14103285Sikob// General Public License for more details. 15103285Sikob 16103285Sikob// Under Section 7 of GPL version 3, you are granted additional 17103285Sikob// permissions described in the GCC Runtime Library Exception, version 18103285Sikob// 3.1, as published by the Free Software Foundation. 19103285Sikob 20103285Sikob// You should have received a copy of the GNU General Public License and 21103285Sikob// a copy of the GCC Runtime Library Exception along with this program; 22103285Sikob// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23103285Sikob// <http://www.gnu.org/licenses/>. 24103285Sikob 25103285Sikob/** @file parallel/multiway_mergesort.h 26103285Sikob * @brief Parallel multiway merge sort. 27103285Sikob * This file is a GNU parallel extension to the Standard C++ Library. 28103285Sikob */ 29103285Sikob 30103285Sikob// Written by Johannes Singler. 31103285Sikob 32103285Sikob#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 33103285Sikob#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1 34103285Sikob 35103285Sikob#include <vector> 36103285Sikob 37103285Sikob#include <parallel/basic_iterator.h> 38103285Sikob#include <bits/stl_algo.h> 39103285Sikob#include <parallel/parallel.h> 40103285Sikob#include <parallel/multiway_merge.h> 41103285Sikob 42103285Sikobnamespace __gnu_parallel 43103285Sikob{ 44103285Sikob /** @brief Subsequence description. */ 45117732Ssimokawa template<typename _DifferenceTp> 46117126Sscottl struct _Piece 47117126Sscottl { 48117732Ssimokawa typedef _DifferenceTp _DifferenceType; 49103285Sikob 50112136Ssimokawa /** @brief Begin of subsequence. */ 51112136Ssimokawa _DifferenceType _M_begin; 52112136Ssimokawa 53103285Sikob /** @brief End of subsequence. */ 54103285Sikob _DifferenceType _M_end; 55103285Sikob }; 56103285Sikob 57103285Sikob /** @brief Data accessed by all threads. 58103285Sikob * 59103285Sikob * PMWMS = parallel multiway mergesort */ 60103285Sikob template<typename _RAIter> 61103285Sikob struct _PMWMSSortingData 62103285Sikob { 63103285Sikob typedef std::iterator_traits<_RAIter> _TraitsType; 64103285Sikob typedef typename _TraitsType::value_type _ValueType; 65103285Sikob typedef typename _TraitsType::difference_type _DifferenceType; 66103285Sikob 67113584Ssimokawa /** @brief Number of threads involved. */ 68103285Sikob _ThreadIndex _M_num_threads; 69120660Ssimokawa 70103285Sikob /** @brief Input __begin. */ 71103285Sikob _RAIter _M_source; 72103285Sikob 73103285Sikob /** @brief Start indices, per thread. */ 74111615Ssimokawa _DifferenceType* _M_starts; 75103285Sikob 76113584Ssimokawa /** @brief Storage in which to sort. */ 77113584Ssimokawa _ValueType** _M_temporary; 78113584Ssimokawa 79103285Sikob /** @brief Samples. */ 80113584Ssimokawa _ValueType* _M_samples; 81111615Ssimokawa 82111615Ssimokawa /** @brief Offsets to add to the found positions. */ 83111615Ssimokawa _DifferenceType* _M_offsets; 84111615Ssimokawa 85111615Ssimokawa /** @brief Pieces of data to merge @c [thread][__sequence] */ 86111615Ssimokawa std::vector<_Piece<_DifferenceType> >* _M_pieces; 87111615Ssimokawa }; 88120660Ssimokawa 89111615Ssimokawa /** 90111615Ssimokawa * @brief Select _M_samples from a sequence. 91111615Ssimokawa * @param __sd Pointer to algorithm data. _Result will be placed in 92103285Sikob * @c __sd->_M_samples. 93120660Ssimokawa * @param __num_samples Number of _M_samples to select. 94120660Ssimokawa */ 95120660Ssimokawa template<typename _RAIter, typename _DifferenceTp> 96120660Ssimokawa void 97103285Sikob __determine_samples(_PMWMSSortingData<_RAIter>* __sd, 98103285Sikob _DifferenceTp __num_samples) 99120660Ssimokawa { 100103285Sikob typedef std::iterator_traits<_RAIter> _TraitsType; 101120660Ssimokawa typedef typename _TraitsType::value_type _ValueType; 102103285Sikob typedef _DifferenceTp _DifferenceType; 103103285Sikob 104120660Ssimokawa _ThreadIndex __iam = omp_get_thread_num(); 105103285Sikob 106103285Sikob _DifferenceType* __es = new _DifferenceType[__num_samples + 2]; 107111203Ssimokawa 108103285Sikob __equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam], 109103285Sikob __num_samples + 1, __es); 110111199Ssimokawa 111103285Sikob for (_DifferenceType __i = 0; __i < __num_samples; ++__i) 112103285Sikob ::new(&(__sd->_M_samples[__iam * __num_samples + __i])) 113103285Sikob _ValueType(__sd->_M_source[__sd->_M_starts[__iam] 114103285Sikob + __es[__i + 1]]); 115103285Sikob 116103285Sikob delete[] __es; 117103285Sikob } 118103285Sikob 119103285Sikob /** @brief Split consistently. */ 120103285Sikob template<bool __exact, typename _RAIter, 121103285Sikob typename _Compare, typename _SortingPlacesIterator> 122103285Sikob struct _SplitConsistently 123113584Ssimokawa { }; 124113584Ssimokawa 125113584Ssimokawa /** @brief Split by exact splitting. */ 126113584Ssimokawa template<typename _RAIter, typename _Compare, 127113584Ssimokawa typename _SortingPlacesIterator> 128113584Ssimokawa struct _SplitConsistently<true, _RAIter, _Compare, _SortingPlacesIterator> 129103285Sikob { 130103285Sikob void 131103285Sikob operator()(const _ThreadIndex __iam, 132113584Ssimokawa _PMWMSSortingData<_RAIter>* __sd, 133120660Ssimokawa _Compare& __comp, 134113584Ssimokawa const typename 135120660Ssimokawa std::iterator_traits<_RAIter>::difference_type 136103285Sikob __num_samples) const 137113584Ssimokawa { 138103285Sikob# pragma omp barrier 139103285Sikob 140113584Ssimokawa std::vector<std::pair<_SortingPlacesIterator, 141103285Sikob _SortingPlacesIterator> > 142103285Sikob __seqs(__sd->_M_num_threads); 143113584Ssimokawa for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++) 144103285Sikob __seqs[__s] = std::make_pair(__sd->_M_temporary[__s], 145103285Sikob __sd->_M_temporary[__s] 146103285Sikob + (__sd->_M_starts[__s + 1] 147114732Ssimokawa - __sd->_M_starts[__s])); 148110336Ssimokawa 149103285Sikob std::vector<_SortingPlacesIterator> __offsets(__sd->_M_num_threads); 150110336Ssimokawa 151103285Sikob // if not last thread 152103285Sikob if (__iam < __sd->_M_num_threads - 1) 153103285Sikob multiseq_partition(__seqs.begin(), __seqs.end(), 154103285Sikob __sd->_M_starts[__iam + 1], __offsets.begin(), 155103285Sikob __comp); 156110336Ssimokawa 157114732Ssimokawa for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++) 158108503Ssimokawa { 159108503Ssimokawa // for each sequence 160120842Ssimokawa if (__iam < (__sd->_M_num_threads - 1)) 161120842Ssimokawa __sd->_M_pieces[__iam][__seq]._M_end 162120842Ssimokawa = __offsets[__seq] - __seqs[__seq].first; 163103285Sikob else 164103285Sikob // very end of this sequence 165113584Ssimokawa __sd->_M_pieces[__iam][__seq]._M_end = 166113584Ssimokawa __sd->_M_starts[__seq + 1] - __sd->_M_starts[__seq]; 167111615Ssimokawa } 168113584Ssimokawa 169103285Sikob# pragma omp barrier 170113584Ssimokawa 171103285Sikob for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++) 172103285Sikob { 173103285Sikob // For each sequence. 174103285Sikob if (__iam > 0) 175103285Sikob __sd->_M_pieces[__iam][__seq]._M_begin = 176103285Sikob __sd->_M_pieces[__iam - 1][__seq]._M_end; 177103285Sikob else 178103285Sikob // Absolute beginning. 179103285Sikob __sd->_M_pieces[__iam][__seq]._M_begin = 0; 180103285Sikob } 181103285Sikob } 182103285Sikob }; 183111615Ssimokawa 184111615Ssimokawa /** @brief Split by sampling. */ 185111615Ssimokawa template<typename _RAIter, typename _Compare, 186120660Ssimokawa typename _SortingPlacesIterator> 187111615Ssimokawa struct _SplitConsistently<false, _RAIter, _Compare, _SortingPlacesIterator> 188113584Ssimokawa { 189113584Ssimokawa void 190103285Sikob operator()(const _ThreadIndex __iam, 191103285Sikob _PMWMSSortingData<_RAIter>* __sd, 192103285Sikob _Compare& __comp, 193103285Sikob const typename 194103285Sikob std::iterator_traits<_RAIter>::difference_type 195111615Ssimokawa __num_samples) const 196103285Sikob { 197103285Sikob typedef std::iterator_traits<_RAIter> _TraitsType; 198103285Sikob typedef typename _TraitsType::value_type _ValueType; 199103285Sikob typedef typename _TraitsType::difference_type _DifferenceType; 200103285Sikob 201103285Sikob __determine_samples(__sd, __num_samples); 202114732Ssimokawa 203103285Sikob# pragma omp barrier 204103285Sikob 205103285Sikob# pragma omp single 206113584Ssimokawa __gnu_sequential::sort(__sd->_M_samples, 207103285Sikob __sd->_M_samples 208103285Sikob + (__num_samples * __sd->_M_num_threads), 209103285Sikob __comp); 210113584Ssimokawa 211103285Sikob# pragma omp barrier 212111615Ssimokawa 213110145Ssimokawa for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s) 214114732Ssimokawa { 215103285Sikob // For each sequence. 216111615Ssimokawa if (__num_samples * __iam > 0) 217111615Ssimokawa __sd->_M_pieces[__iam][__s]._M_begin = 218111615Ssimokawa std::lower_bound(__sd->_M_temporary[__s], 219111615Ssimokawa __sd->_M_temporary[__s] 220103285Sikob + (__sd->_M_starts[__s + 1] 221108281Ssimokawa - __sd->_M_starts[__s]), 222103285Sikob __sd->_M_samples[__num_samples * __iam], 223103285Sikob __comp) 224103285Sikob - __sd->_M_temporary[__s]; 225103285Sikob else 226111615Ssimokawa // Absolute beginning. 227111615Ssimokawa __sd->_M_pieces[__iam][__s]._M_begin = 0; 228103285Sikob 229103285Sikob if ((__num_samples * (__iam + 1)) < 230103285Sikob (__num_samples * __sd->_M_num_threads)) 231103285Sikob __sd->_M_pieces[__iam][__s]._M_end = 232103285Sikob std::lower_bound(__sd->_M_temporary[__s], 233103285Sikob __sd->_M_temporary[__s] 234103285Sikob + (__sd->_M_starts[__s + 1] 235103285Sikob - __sd->_M_starts[__s]), 236103285Sikob __sd->_M_samples[__num_samples * (__iam + 1)], 237103285Sikob __comp) 238103285Sikob - __sd->_M_temporary[__s]; 239103285Sikob else 240103285Sikob // Absolute end. 241103285Sikob __sd->_M_pieces[__iam][__s]._M_end = (__sd->_M_starts[__s + 1] 242103285Sikob - __sd->_M_starts[__s]); 243103285Sikob } 244103285Sikob } 245103285Sikob }; 246103285Sikob 247103285Sikob template<bool __stable, typename _RAIter, typename _Compare> 248103285Sikob struct __possibly_stable_sort 249103285Sikob { }; 250103285Sikob 251103285Sikob template<typename _RAIter, typename _Compare> 252103285Sikob struct __possibly_stable_sort<true, _RAIter, _Compare> 253103285Sikob { 254103285Sikob void operator()(const _RAIter& __begin, 255103285Sikob const _RAIter& __end, _Compare& __comp) const 256103285Sikob { __gnu_sequential::stable_sort(__begin, __end, __comp); } 257103285Sikob }; 258103285Sikob 259103285Sikob template<typename _RAIter, typename _Compare> 260103285Sikob struct __possibly_stable_sort<false, _RAIter, _Compare> 261103285Sikob { 262103285Sikob void operator()(const _RAIter __begin, 263103285Sikob const _RAIter __end, _Compare& __comp) const 264103285Sikob { __gnu_sequential::sort(__begin, __end, __comp); } 265103285Sikob }; 266103285Sikob 267103285Sikob template<bool __stable, typename _Seq_RAIter, 268103285Sikob typename _RAIter, typename _Compare, 269103285Sikob typename _DiffType> 270103285Sikob struct __possibly_stable_multiway_merge 271103285Sikob { }; 272103285Sikob 273103285Sikob template<typename _Seq_RAIter, typename _RAIter, 274103285Sikob typename _Compare, typename _DiffType> 275103285Sikob struct __possibly_stable_multiway_merge<true, _Seq_RAIter, 276103285Sikob _RAIter, _Compare, _DiffType> 277103285Sikob { 278103285Sikob void operator()(const _Seq_RAIter& __seqs_begin, 279103285Sikob const _Seq_RAIter& __seqs_end, 280103285Sikob const _RAIter& __target, 281103285Sikob _Compare& __comp, 282103285Sikob _DiffType __length_am) const 283103285Sikob { stable_multiway_merge(__seqs_begin, __seqs_end, __target, 284103285Sikob __length_am, __comp, sequential_tag()); } 285103285Sikob }; 286103285Sikob 287103285Sikob template<typename _Seq_RAIter, typename _RAIter, 288103285Sikob typename _Compare, typename _DiffType> 289103285Sikob struct __possibly_stable_multiway_merge<false, _Seq_RAIter, 290103285Sikob _RAIter, _Compare, _DiffType> 291103285Sikob { 292103285Sikob void operator()(const _Seq_RAIter& __seqs_begin, 293103285Sikob const _Seq_RAIter& __seqs_end, 294103285Sikob const _RAIter& __target, 295103285Sikob _Compare& __comp, 296103285Sikob _DiffType __length_am) const 297103285Sikob { multiway_merge(__seqs_begin, __seqs_end, __target, __length_am, 298103285Sikob __comp, sequential_tag()); } 299103285Sikob }; 300103285Sikob 301120660Ssimokawa /** @brief PMWMS code executed by each thread. 302111615Ssimokawa * @param __sd Pointer to algorithm data. 303111615Ssimokawa * @param __comp Comparator. 304111615Ssimokawa */ 305103285Sikob template<bool __stable, bool __exact, typename _RAIter, 306103285Sikob typename _Compare> 307103285Sikob void 308103285Sikob parallel_sort_mwms_pu(_PMWMSSortingData<_RAIter>* __sd, 309103285Sikob _Compare& __comp) 310103285Sikob { 311103285Sikob typedef std::iterator_traits<_RAIter> _TraitsType; 312103285Sikob typedef typename _TraitsType::value_type _ValueType; 313103285Sikob typedef typename _TraitsType::difference_type _DifferenceType; 314103285Sikob 315103285Sikob _ThreadIndex __iam = omp_get_thread_num(); 316103285Sikob 317103285Sikob // Length of this thread's chunk, before merging. 318103285Sikob _DifferenceType __length_local = 319103285Sikob __sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam]; 320103285Sikob 321103285Sikob // Sort in temporary storage, leave space for sentinel. 322103285Sikob 323103285Sikob typedef _ValueType* _SortingPlacesIterator; 324108503Ssimokawa 325108503Ssimokawa __sd->_M_temporary[__iam] = 326103285Sikob static_cast<_ValueType*>(::operator new(sizeof(_ValueType) 327103285Sikob * (__length_local + 1))); 328103285Sikob 329103285Sikob // Copy there. 330103285Sikob std::uninitialized_copy(__sd->_M_source + __sd->_M_starts[__iam], 331103285Sikob __sd->_M_source + __sd->_M_starts[__iam] 332103285Sikob + __length_local, 333103285Sikob __sd->_M_temporary[__iam]); 334103285Sikob 335103285Sikob __possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>() 336103285Sikob (__sd->_M_temporary[__iam], 337103285Sikob __sd->_M_temporary[__iam] + __length_local, 338103285Sikob __comp); 339103285Sikob 340110184Ssimokawa // Invariant: locally sorted subsequence in sd->_M_temporary[__iam], 341110184Ssimokawa // __sd->_M_temporary[__iam] + __length_local. 342110184Ssimokawa 343110184Ssimokawa // No barrier here: Synchronization is done by the splitting routine. 344110184Ssimokawa 345110184Ssimokawa _DifferenceType __num_samples = 346110184Ssimokawa _Settings::get().sort_mwms_oversampling * __sd->_M_num_threads - 1; 347110184Ssimokawa _SplitConsistently<__exact, _RAIter, _Compare, _SortingPlacesIterator>() 348110184Ssimokawa (__iam, __sd, __comp, __num_samples); 349110184Ssimokawa 350110184Ssimokawa // Offset from __target __begin, __length after merging. 351110184Ssimokawa _DifferenceType __offset = 0, __length_am = 0; 352110184Ssimokawa for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++) 353110184Ssimokawa { 354110184Ssimokawa __length_am += (__sd->_M_pieces[__iam][__s]._M_end 355110184Ssimokawa - __sd->_M_pieces[__iam][__s]._M_begin); 356110184Ssimokawa __offset += __sd->_M_pieces[__iam][__s]._M_begin; 357110184Ssimokawa } 358110184Ssimokawa 359110184Ssimokawa typedef std::vector< 360110184Ssimokawa std::pair<_SortingPlacesIterator, _SortingPlacesIterator> > 361110184Ssimokawa _SeqVector; 362110184Ssimokawa _SeqVector __seqs(__sd->_M_num_threads); 363110184Ssimokawa 364110184Ssimokawa for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s) 365110184Ssimokawa { 366110184Ssimokawa __seqs[__s] = 367110184Ssimokawa std::make_pair(__sd->_M_temporary[__s] 368110184Ssimokawa + __sd->_M_pieces[__iam][__s]._M_begin, 369110184Ssimokawa __sd->_M_temporary[__s] 370110184Ssimokawa + __sd->_M_pieces[__iam][__s]._M_end); 371110184Ssimokawa } 372110184Ssimokawa 373110184Ssimokawa __possibly_stable_multiway_merge< 374110184Ssimokawa __stable, typename _SeqVector::iterator, 375110184Ssimokawa _RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(), 376110184Ssimokawa __sd->_M_source + __offset, __comp, 377110184Ssimokawa __length_am); 378110184Ssimokawa 379110184Ssimokawa# pragma omp barrier 380110184Ssimokawa 381110184Ssimokawa for (_DifferenceType __i = 0; __i < __length_local; ++__i) 382110184Ssimokawa __sd->_M_temporary[__iam][__i].~_ValueType(); 383110184Ssimokawa ::operator delete(__sd->_M_temporary[__iam]); 384110184Ssimokawa } 385110184Ssimokawa 386110184Ssimokawa /** @brief PMWMS main call. 387110184Ssimokawa * @param __begin Begin iterator of sequence. 388110184Ssimokawa * @param __end End iterator of sequence. 389110184Ssimokawa * @param __comp Comparator. 390110184Ssimokawa * @param __num_threads Number of threads to use. 391110184Ssimokawa */ 392103285Sikob template<bool __stable, bool __exact, typename _RAIter, 393103285Sikob typename _Compare> 394103285Sikob void 395108503Ssimokawa parallel_sort_mwms(_RAIter __begin, _RAIter __end, 396103285Sikob _Compare __comp, 397103285Sikob _ThreadIndex __num_threads) 398108503Ssimokawa { 399108503Ssimokawa _GLIBCXX_CALL(__end - __begin) 400103285Sikob 401103285Sikob typedef std::iterator_traits<_RAIter> _TraitsType; 402103285Sikob typedef typename _TraitsType::value_type _ValueType; 403103285Sikob typedef typename _TraitsType::difference_type _DifferenceType; 404110184Ssimokawa 405110184Ssimokawa _DifferenceType __n = __end - __begin; 406110184Ssimokawa 407103285Sikob if (__n <= 1) 408103285Sikob return; 409103285Sikob 410103285Sikob // at least one element per thread 411103285Sikob if (__num_threads > __n) 412103285Sikob __num_threads = static_cast<_ThreadIndex>(__n); 413103285Sikob 414111704Ssimokawa // shared variables 415114069Ssimokawa _PMWMSSortingData<_RAIter> __sd; 416114069Ssimokawa _DifferenceType* __starts; 417114069Ssimokawa _DifferenceType __size; 418114069Ssimokawa 419103285Sikob# pragma omp parallel num_threads(__num_threads) 420103285Sikob { 421103285Sikob __num_threads = omp_get_num_threads(); //no more threads than requested 422103285Sikob 423103285Sikob# pragma omp single 424114069Ssimokawa { 425111615Ssimokawa __sd._M_num_threads = __num_threads; 426111704Ssimokawa __sd._M_source = __begin; 427111704Ssimokawa 428111704Ssimokawa __sd._M_temporary = new _ValueType*[__num_threads]; 429113584Ssimokawa 430113584Ssimokawa if (!__exact) 431111615Ssimokawa { 432111615Ssimokawa __size = 433111615Ssimokawa (_Settings::get().sort_mwms_oversampling * __num_threads - 1) 434111615Ssimokawa * __num_threads; 435103285Sikob __sd._M_samples = static_cast<_ValueType*> 436108503Ssimokawa (::operator new(__size * sizeof(_ValueType))); 437108503Ssimokawa } 438108503Ssimokawa else 439108503Ssimokawa __sd._M_samples = 0; 440108503Ssimokawa 441108503Ssimokawa __sd._M_offsets = new _DifferenceType[__num_threads - 1]; 442108503Ssimokawa __sd._M_pieces 443110839Ssimokawa = new std::vector<_Piece<_DifferenceType> >[__num_threads]; 444108642Ssimokawa for (_ThreadIndex __s = 0; __s < __num_threads; ++__s) 445108642Ssimokawa __sd._M_pieces[__s].resize(__num_threads); 446108642Ssimokawa __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1]; 447108503Ssimokawa 448108503Ssimokawa _DifferenceType __chunk_length = __n / __num_threads; 449108503Ssimokawa _DifferenceType __split = __n % __num_threads; 450108503Ssimokawa _DifferenceType __pos = 0; 451110839Ssimokawa for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) 452110839Ssimokawa { 453110839Ssimokawa __starts[__i] = __pos; 454110839Ssimokawa __pos += ((__i < __split) 455108503Ssimokawa ? (__chunk_length + 1) : __chunk_length); 456103285Sikob } 457103285Sikob __starts[__num_threads] = __pos; 458103285Sikob } //single 459103285Sikob 460103285Sikob // Now sort in parallel. 461103285Sikob parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp); 462103285Sikob } //parallel 463103285Sikob 464111615Ssimokawa delete[] __starts; 465108503Ssimokawa delete[] __sd._M_temporary; 466103285Sikob 467108503Ssimokawa if (!__exact) 468108503Ssimokawa { 469108503Ssimokawa for (_DifferenceType __i = 0; __i < __size; ++__i) 470108503Ssimokawa __sd._M_samples[__i].~_ValueType(); 471108503Ssimokawa ::operator delete(__sd._M_samples); 472110839Ssimokawa } 473110839Ssimokawa 474110839Ssimokawa delete[] __sd._M_offsets; 475110839Ssimokawa delete[] __sd._M_pieces; 476110839Ssimokawa } 477113584Ssimokawa 478113584Ssimokawa} //namespace __gnu_parallel 479119196Ssimokawa 480113584Ssimokawa#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H */ 481113584Ssimokawa