1*e4b17023SJohn Marino // -*- C++ -*- 2*e4b17023SJohn Marino 3*e4b17023SJohn Marino // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 4*e4b17023SJohn Marino // 5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free 6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the terms 7*e4b17023SJohn Marino // of the GNU General Public License as published by the Free Software 8*e4b17023SJohn Marino // Foundation; either version 3, or (at your option) any later 9*e4b17023SJohn Marino // version. 10*e4b17023SJohn Marino 11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, but 12*e4b17023SJohn Marino // WITHOUT ANY WARRANTY; without even the implied warranty of 13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*e4b17023SJohn Marino // General Public License for more details. 15*e4b17023SJohn Marino 16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional 17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version 18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation. 19*e4b17023SJohn Marino 20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and 21*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program; 22*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>. 24*e4b17023SJohn Marino 25*e4b17023SJohn Marino /** @file parallel/types.h 26*e4b17023SJohn Marino * @brief Basic types and typedefs. 27*e4b17023SJohn Marino * This file is a GNU parallel extension to the Standard C++ Library. 28*e4b17023SJohn Marino */ 29*e4b17023SJohn Marino 30*e4b17023SJohn Marino // Written by Johannes Singler and Felix Putze. 31*e4b17023SJohn Marino 32*e4b17023SJohn Marino #ifndef _GLIBCXX_PARALLEL_TYPES_H 33*e4b17023SJohn Marino #define _GLIBCXX_PARALLEL_TYPES_H 1 34*e4b17023SJohn Marino 35*e4b17023SJohn Marino #include <cstdlib> 36*e4b17023SJohn Marino #include <limits> 37*e4b17023SJohn Marino #include <tr1/cstdint> 38*e4b17023SJohn Marino 39*e4b17023SJohn Marino namespace __gnu_parallel 40*e4b17023SJohn Marino { 41*e4b17023SJohn Marino // Enumerated types. 42*e4b17023SJohn Marino 43*e4b17023SJohn Marino /// Run-time equivalents for the compile-time tags. 44*e4b17023SJohn Marino enum _Parallelism 45*e4b17023SJohn Marino { 46*e4b17023SJohn Marino /// Not parallel. 47*e4b17023SJohn Marino sequential, 48*e4b17023SJohn Marino 49*e4b17023SJohn Marino /// Parallel unbalanced (equal-sized chunks). 50*e4b17023SJohn Marino parallel_unbalanced, 51*e4b17023SJohn Marino 52*e4b17023SJohn Marino /// Parallel balanced (work-stealing). 53*e4b17023SJohn Marino parallel_balanced, 54*e4b17023SJohn Marino 55*e4b17023SJohn Marino /// Parallel with OpenMP dynamic load-balancing. 56*e4b17023SJohn Marino parallel_omp_loop, 57*e4b17023SJohn Marino 58*e4b17023SJohn Marino /// Parallel with OpenMP static load-balancing. 59*e4b17023SJohn Marino parallel_omp_loop_static, 60*e4b17023SJohn Marino 61*e4b17023SJohn Marino /// Parallel with OpenMP taskqueue construct. 62*e4b17023SJohn Marino parallel_taskqueue 63*e4b17023SJohn Marino }; 64*e4b17023SJohn Marino 65*e4b17023SJohn Marino /// Strategies for run-time algorithm selection: 66*e4b17023SJohn Marino // force_sequential, force_parallel, heuristic. 67*e4b17023SJohn Marino enum _AlgorithmStrategy 68*e4b17023SJohn Marino { 69*e4b17023SJohn Marino heuristic, 70*e4b17023SJohn Marino force_sequential, 71*e4b17023SJohn Marino force_parallel 72*e4b17023SJohn Marino }; 73*e4b17023SJohn Marino 74*e4b17023SJohn Marino /// Sorting algorithms: 75*e4b17023SJohn Marino // multi-way mergesort, quicksort, load-balanced quicksort. 76*e4b17023SJohn Marino enum _SortAlgorithm 77*e4b17023SJohn Marino { 78*e4b17023SJohn Marino MWMS, 79*e4b17023SJohn Marino QS, 80*e4b17023SJohn Marino QS_BALANCED 81*e4b17023SJohn Marino }; 82*e4b17023SJohn Marino 83*e4b17023SJohn Marino /// Merging algorithms: 84*e4b17023SJohn Marino // bubblesort-alike, loser-tree variants, enum __sentinel. 85*e4b17023SJohn Marino enum _MultiwayMergeAlgorithm 86*e4b17023SJohn Marino { 87*e4b17023SJohn Marino LOSER_TREE 88*e4b17023SJohn Marino }; 89*e4b17023SJohn Marino 90*e4b17023SJohn Marino /// Partial sum algorithms: recursive, linear. 91*e4b17023SJohn Marino enum _PartialSumAlgorithm 92*e4b17023SJohn Marino { 93*e4b17023SJohn Marino RECURSIVE, 94*e4b17023SJohn Marino LINEAR 95*e4b17023SJohn Marino }; 96*e4b17023SJohn Marino 97*e4b17023SJohn Marino /// Sorting/merging algorithms: sampling, __exact. 98*e4b17023SJohn Marino enum _SplittingAlgorithm 99*e4b17023SJohn Marino { 100*e4b17023SJohn Marino SAMPLING, 101*e4b17023SJohn Marino EXACT 102*e4b17023SJohn Marino }; 103*e4b17023SJohn Marino 104*e4b17023SJohn Marino /// Find algorithms: 105*e4b17023SJohn Marino // growing blocks, equal-sized blocks, equal splitting. 106*e4b17023SJohn Marino enum _FindAlgorithm 107*e4b17023SJohn Marino { 108*e4b17023SJohn Marino GROWING_BLOCKS, 109*e4b17023SJohn Marino CONSTANT_SIZE_BLOCKS, 110*e4b17023SJohn Marino EQUAL_SPLIT 111*e4b17023SJohn Marino }; 112*e4b17023SJohn Marino 113*e4b17023SJohn Marino /** 114*e4b17023SJohn Marino * @brief Unsigned integer to index __elements. 115*e4b17023SJohn Marino * The total number of elements for each algorithm must fit into this type. 116*e4b17023SJohn Marino */ 117*e4b17023SJohn Marino typedef uint64_t _SequenceIndex; 118*e4b17023SJohn Marino 119*e4b17023SJohn Marino /** 120*e4b17023SJohn Marino * @brief Unsigned integer to index a thread number. 121*e4b17023SJohn Marino * The maximum thread number (for each processor) must fit into this type. 122*e4b17023SJohn Marino */ 123*e4b17023SJohn Marino typedef uint16_t _ThreadIndex; 124*e4b17023SJohn Marino 125*e4b17023SJohn Marino // XXX atomics interface? 126*e4b17023SJohn Marino /// Longest compare-and-swappable integer type on this platform. 127*e4b17023SJohn Marino typedef int64_t _CASable; 128*e4b17023SJohn Marino 129*e4b17023SJohn Marino /// Number of bits of _CASable. 130*e4b17023SJohn Marino static const int _CASable_bits = std::numeric_limits<_CASable>::digits; 131*e4b17023SJohn Marino 132*e4b17023SJohn Marino /// ::_CASable with the right half of bits set to 1. 133*e4b17023SJohn Marino static const _CASable _CASable_mask = 134*e4b17023SJohn Marino ((_CASable(1) << (_CASable_bits / 2)) - 1); 135*e4b17023SJohn Marino } 136*e4b17023SJohn Marino 137*e4b17023SJohn Marino #endif /* _GLIBCXX_PARALLEL_TYPES_H */ 138