OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [parallel/] [sort.h] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe 
// -*- C++ -*-
2 
 
3 
// Copyright (C) 2007, 2008, 2009 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 terms
7 
// of the GNU General Public License as published by the Free Software
8 
// Foundation; either version 3, or (at your option) any later
9 
// version.
10 
 
11 
// This library is distributed in the hope that it will be useful, but
12 
// WITHOUT ANY WARRANTY; without even the implied warranty of
13 
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 
// 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 parallel/sort.h
26 
 *  @brief Parallel sorting algorithm switch.
27 
 *  This file is a GNU parallel extension to the Standard C++ Library.
28 
 */
29 
 
30 
// Written by Johannes Singler.
31 
 
32 
#ifndef _GLIBCXX_PARALLEL_SORT_H
33 
#define _GLIBCXX_PARALLEL_SORT_H 1
34 
 
35 
#include <parallel/basic_iterator.h>
36 
#include <parallel/features.h>
37 
#include <parallel/parallel.h>
38 
 
39 
#if _GLIBCXX_ASSERTIONS
40 
#include <parallel/checkers.h>
41 
#endif
42 
 
43 
#if _GLIBCXX_MERGESORT
44 
#include <parallel/multiway_mergesort.h>
45 
#endif
46 
 
47 
#if _GLIBCXX_QUICKSORT
48 
#include <parallel/quicksort.h>
49 
#endif
50 
 
51 
#if _GLIBCXX_BAL_QUICKSORT
52 
#include <parallel/balanced_quicksort.h>
53 
#endif
54 
 
55 
namespace __gnu_parallel
56 
{
57 
  //prototype
58 
  template<bool __stable, typename _RAIter,
59 
           typename _Compare, typename _Parallelism>
60 
    void
61 
    __parallel_sort(_RAIter __begin, _RAIter __end,
62 
                    _Compare __comp, _Parallelism __parallelism);
63 
 
64 
  /**
65 
   *  @brief Choose multiway mergesort, splitting variant at run-time,
66 
   *  for parallel sorting.
67 
   *  @param __begin Begin iterator of input sequence.
68 
   *  @param __end End iterator of input sequence.
69 
   *  @param __comp Comparator.
70 
   *  @tparam __stable Sort stable.
71 
   *  @callgraph
72 
   */
73 
  template<bool __stable, typename _RAIter, typename _Compare>
74 
    inline void
75 
    __parallel_sort(_RAIter __begin, _RAIter __end,
76 
                    _Compare __comp, multiway_mergesort_tag __parallelism)
77 
    {
78 
      _GLIBCXX_CALL(__end - __begin)
79 
 
80 
      if(_Settings::get().sort_splitting == EXACT)
81 
        parallel_sort_mwms<__stable, true>
82 
          (__begin, __end, __comp, __parallelism.__get_num_threads());
83 
      else
84 
        parallel_sort_mwms<__stable, false>
85 
          (__begin, __end, __comp, __parallelism.__get_num_threads());
86 
    }
87 
 
88 
  /**
89 
   *  @brief Choose multiway mergesort with exact splitting,
90 
   *  for parallel sorting.
91 
   *  @param __begin Begin iterator of input sequence.
92 
   *  @param __end End iterator of input sequence.
93 
   *  @param __comp Comparator.
94 
   *  @tparam __stable Sort stable.
95 
   *  @callgraph
96 
   */
97 
  template<bool __stable, typename _RAIter, typename _Compare>
98 
    inline void
99 
    __parallel_sort(_RAIter __begin, _RAIter __end,
100 
                    _Compare __comp,
101 
                    multiway_mergesort_exact_tag __parallelism)
102 
    {
103 
      _GLIBCXX_CALL(__end - __begin)
104 
 
105 
      parallel_sort_mwms<__stable, true>
106 
        (__begin, __end, __comp, __parallelism.__get_num_threads());
107 
    }
108 
 
109 
  /**
110 
   *  @brief Choose multiway mergesort with splitting by sampling,
111 
   *  for parallel sorting.
112 
   *  @param __begin Begin iterator of input sequence.
113 
   *  @param __end End iterator of input sequence.
114 
   *  @param __comp Comparator.
115 
   *  @tparam __stable Sort stable.
116 
   *  @callgraph
117 
   */
118 
  template<bool __stable, typename _RAIter, typename _Compare>
119 
    inline void
120 
    __parallel_sort(_RAIter __begin, _RAIter __end,
121 
                    _Compare __comp,
122 
                    multiway_mergesort_sampling_tag __parallelism)
123 
    {
124 
      _GLIBCXX_CALL(__end - __begin)
125 
 
126 
      parallel_sort_mwms<__stable, false>
127 
      (__begin, __end, __comp, __parallelism.__get_num_threads());
128 
    }
129 
 
130 
  /**
131 
   *  @brief Choose quicksort for parallel sorting.
132 
   *  @param __begin Begin iterator of input sequence.
133 
   *  @param __end End iterator of input sequence.
134 
   *  @param __comp Comparator.
135 
   *  @tparam __stable Sort stable.
136 
   *  @callgraph
137 
   */
138 
  template<bool __stable, typename _RAIter, typename _Compare>
139 
    inline void
140 
    __parallel_sort(_RAIter __begin, _RAIter __end,
141 
                    _Compare __comp, quicksort_tag __parallelism)
142 
    {
143 
      _GLIBCXX_CALL(__end - __begin)
144 
 
145 
      _GLIBCXX_PARALLEL_ASSERT(__stable == false);
146 
 
147 
      __parallel_sort_qs(__begin, __end, __comp,
148 
                         __parallelism.__get_num_threads());
149 
    }
150 
 
151 
  /**
152 
   *  @brief Choose balanced quicksort for parallel sorting.
153 
   *  @param __begin Begin iterator of input sequence.
154 
   *  @param __end End iterator of input sequence.
155 
   *  @param __comp Comparator.
156 
   *  @tparam __stable Sort stable.
157 
   *  @callgraph
158 
   */
159 
   template<bool __stable, typename _RAIter, typename _Compare>
160 
     inline void
161 
     __parallel_sort(_RAIter __begin, _RAIter __end,
162 
                     _Compare __comp, balanced_quicksort_tag __parallelism)
163 
     {
164 
       _GLIBCXX_CALL(__end - __begin)
165 
 
166 
       _GLIBCXX_PARALLEL_ASSERT(__stable == false);
167 
 
168 
       __parallel_sort_qsb(__begin, __end, __comp,
169 
                           __parallelism.__get_num_threads());
170 
     }
171 
 
172 
  /**
173 
   *  @brief Choose multiway mergesort with exact splitting,
174 
   *  for parallel sorting.
175 
   *  @param __begin Begin iterator of input sequence.
176 
   *  @param __end End iterator of input sequence.
177 
   *  @param __comp Comparator.
178 
   *  @tparam __stable Sort stable.
179 
   *  @callgraph
180 
   */
181 
  template<bool __stable, typename _RAIter, typename _Compare>
182 
    inline void
183 
    __parallel_sort(_RAIter __begin, _RAIter __end,
184 
                    _Compare __comp, default_parallel_tag __parallelism)
185 
    {
186 
      _GLIBCXX_CALL(__end - __begin)
187 
 
188 
      __parallel_sort<__stable>
189 
        (__begin, __end, __comp,
190 
         multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
191 
    }
192 
 
193 
  /**
194 
   *  @brief Choose a parallel sorting algorithm.
195 
   *  @param __begin Begin iterator of input sequence.
196 
   *  @param __end End iterator of input sequence.
197 
   *  @param __comp Comparator.
198 
   *  @tparam __stable Sort stable.
199 
   *  @callgraph
200 
   */
201 
  template<bool __stable, typename _RAIter, typename _Compare>
202 
    inline void
203 
    __parallel_sort(_RAIter __begin, _RAIter __end,
204 
                    _Compare __comp, parallel_tag __parallelism)
205 
    {
206 
      _GLIBCXX_CALL(__end - __begin)
207 
      typedef std::iterator_traits<_RAIter> _TraitsType;
208 
      typedef typename _TraitsType::value_type _ValueType;
209 
      typedef typename _TraitsType::difference_type _DifferenceType;
210 
 
211 
      if (false) ;
212 
#if _GLIBCXX_MERGESORT
213 
      else if (__stable || _Settings::get().sort_algorithm == MWMS)
214 
        {
215 
          if(_Settings::get().sort_splitting == EXACT)
216 
            parallel_sort_mwms<__stable, true>
217 
              (__begin, __end, __comp, __parallelism.__get_num_threads());
218 
          else
219 
            parallel_sort_mwms<false, false>
220 
              (__begin, __end, __comp, __parallelism.__get_num_threads());
221 
        }
222 
#endif
223 
#if _GLIBCXX_QUICKSORT
224 
      else if (_Settings::get().sort_algorithm == QS)
225 
        __parallel_sort_qs(__begin, __end, __comp,
226 
                           __parallelism.__get_num_threads());
227 
#endif
228 
#if _GLIBCXX_BAL_QUICKSORT
229 
      else if (_Settings::get().sort_algorithm == QS_BALANCED)
230 
        __parallel_sort_qsb(__begin, __end, __comp,
231 
                            __parallelism.__get_num_threads());
232 
#endif
233 
      else
234 
        __gnu_sequential::sort(__begin, __end, __comp);
235 
    }
236 
} // end namespace __gnu_parallel
237 
 
238 
#endif /* _GLIBCXX_PARALLEL_SORT_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.