l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/algobase.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/algobase.h
  32  *  @brief Parallel STL function calls corresponding to the
  33  *  stl_algobase.h header.  The functions defined here mainly do case
  34  *  switches and call the actual parallelized versions in other files.
  35  *  Inlining policy: Functions that basically only contain one
  36  *  function call, are declared inline.
  37  *  This file is a GNU parallel extension to the Standard C++ Library.
  38  */
  39
  40 // Written by Johannes Singler and Felix Putze.
  41
  42 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
  43 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
  44
  45 #include <bits/stl_algobase.h>
  46 #include <parallel/base.h>
  47 #include <parallel/tags.h>
  48 #include <parallel/settings.h>
  49 #include <parallel/find.h>
  50 #include <parallel/find_selectors.h>
  51
  52 namespace std
  53 {
  54 namespace __parallel
  55 {
  56   // NB: equal and lexicographical_compare require mismatch.
  57
  58   // Sequential fallback
  59   template<typename InputIterator1, typename InputIterator2>
  60     inline pair<InputIterator1, InputIterator2>
  61     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
  62              __gnu_parallel::sequential_tag)
  63     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
  64
  65   // Sequential fallback
  66   template<typename InputIterator1, typename InputIterator2,
  67            typename Predicate>
  68     inline pair<InputIterator1, InputIterator2>
  69     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
  70              Predicate pred, __gnu_parallel::sequential_tag)
  71     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
  72
  73   // Sequential fallback for input iterator case
  74   template<typename InputIterator1, typename InputIterator2,
  75            typename Predicate, typename IteratorTag1, typename IteratorTag2>
  76     inline pair<InputIterator1, InputIterator2>
  77     mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
  78                     InputIterator2 begin2, Predicate pred, IteratorTag1,
  79                     IteratorTag2)
  80     { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
  81
  82   // Parallel mismatch for random access iterators
  83   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
  84            typename Predicate>
  85     pair<RandomAccessIterator1, RandomAccessIterator2>
  86     mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
  87                     RandomAccessIterator2 begin2, Predicate pred,
  88                     random_access_iterator_tag, random_access_iterator_tag)
  89     {
  90       if (_GLIBCXX_PARALLEL_CONDITION(true))
  91         {
  92           RandomAccessIterator1 res =
  93             __gnu_parallel::find_template(begin1, end1, begin2, pred,
  94                                           __gnu_parallel::
  95                                           mismatch_selector()).first;
  96           return make_pair(res , begin2 + (res - begin1));
  97         }
  98       else
  99         return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
 100     }
 101
 102   // Public interface
 103   template<typename InputIterator1, typename InputIterator2>
 104     inline pair<InputIterator1, InputIterator2>
 105     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 106     {
 107       typedef std::iterator_traits<InputIterator1> iterator1_traits;
 108       typedef std::iterator_traits<InputIterator2> iterator2_traits;
 109       typedef typename iterator1_traits::value_type value1_type;
 110       typedef typename iterator2_traits::value_type value2_type;
 111       typedef typename iterator1_traits::iterator_category iterator1_category;
 112       typedef typename iterator2_traits::iterator_category iterator2_category;
 113
 114       typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
 115
 116       return mismatch_switch(begin1, end1, begin2, equal_to_type(),
 117                              iterator1_category(), iterator2_category());
 118     }
 119
 120   // Public interface
 121   template<typename InputIterator1, typename InputIterator2,
 122            typename Predicate>
 123     inline pair<InputIterator1, InputIterator2>
 124     mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 125              Predicate pred)
 126     {
 127       typedef std::iterator_traits<InputIterator1> iterator1_traits;
 128       typedef std::iterator_traits<InputIterator2> iterator2_traits;
 129       typedef typename iterator1_traits::iterator_category iterator1_category;
 130       typedef typename iterator2_traits::iterator_category iterator2_category;
 131
 132       return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
 133                              iterator2_category());
 134     }
 135
 136   // Sequential fallback
 137   template<typename InputIterator1, typename InputIterator2>
 138     inline bool
 139     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 140           __gnu_parallel::sequential_tag)
 141     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
 142
 143   // Sequential fallback
 144   template<typename InputIterator1, typename InputIterator2,
 145            typename Predicate>
 146     inline bool
 147     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 148           Predicate pred, __gnu_parallel::sequential_tag)
 149     { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
 150
 151   // Public interface
 152   template<typename InputIterator1, typename InputIterator2>
 153     inline bool
 154     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 155     { return mismatch(begin1, end1, begin2).first == end1; }
 156
 157   // Public interface
 158   template<typename InputIterator1, typename InputIterator2,
 159            typename Predicate>
 160     inline bool
 161     equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 162           Predicate pred)
 163     { return mismatch(begin1, end1, begin2, pred).first == end1; }
 164
 165   // Sequential fallback
 166   template<typename InputIterator1, typename InputIterator2>
 167     inline bool
 168     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 169                             InputIterator2 begin2, InputIterator2 end2,
 170                             __gnu_parallel::sequential_tag)
 171     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 172                                                      begin2, end2); }
 173
 174   // Sequential fallback
 175   template<typename InputIterator1, typename InputIterator2,
 176            typename Predicate>
 177     inline bool
 178     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 179                             InputIterator2 begin2, InputIterator2 end2,
 180                             Predicate pred, __gnu_parallel::sequential_tag)
 181     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 182                                                      begin2, end2, pred); }
 183
 184   // Sequential fallback for input iterator case
 185   template<typename InputIterator1, typename InputIterator2,
 186            typename Predicate, typename IteratorTag1, typename IteratorTag2>
 187     inline bool
 188     lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
 189                                    InputIterator2 begin2, InputIterator2 end2,
 190                                    Predicate pred, IteratorTag1, IteratorTag2)
 191     { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 192                                                      begin2, end2, pred); }
 193
 194   // Parallel lexicographical_compare for random access iterators
 195   // Limitation: Both valuetypes must be the same
 196   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 197            typename Predicate>
 198     bool
 199     lexicographical_compare_switch(RandomAccessIterator1 begin1,
 200                                    RandomAccessIterator1 end1,
 201                                    RandomAccessIterator2 begin2,
 202                                    RandomAccessIterator2 end2, Predicate pred,
 203                                    random_access_iterator_tag,
 204                                    random_access_iterator_tag)
 205     {
 206       if (_GLIBCXX_PARALLEL_CONDITION(true))
 207         {
 208           typedef iterator_traits<RandomAccessIterator1> traits1_type;
 209           typedef typename traits1_type::value_type value1_type;
 210
 211           typedef iterator_traits<RandomAccessIterator2> traits2_type;
 212           typedef typename traits2_type::value_type value2_type;
 213
 214           typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
 215                                                   value2_type> equal_type;
 216
 217           // Longer sequence in first place.
 218           if ((end1 - begin1) < (end2 - begin2))
 219             {
 220               typedef pair<RandomAccessIterator1, RandomAccessIterator2>
 221                 pair_type;
 222               pair_type mm = mismatch_switch(begin1, end1, begin2,
 223                                              equal_type(pred),
 224                                              random_access_iterator_tag(),
 225                                              random_access_iterator_tag());
 226
 227               return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
 228             }
 229           else
 230             {
 231               typedef pair<RandomAccessIterator2, RandomAccessIterator1>
 232                 pair_type;
 233               pair_type mm = mismatch_switch(begin2, end2, begin1,
 234                                              equal_type(pred),
 235                                              random_access_iterator_tag(),
 236                                              random_access_iterator_tag());
 237
 238               return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
 239             }
 240         }
 241       else
 242         return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
 243                                                        begin2, end2, pred);
 244     }
 245
 246   // Public interface
 247   template<typename InputIterator1, typename InputIterator2>
 248     inline bool
 249     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 250                             InputIterator2 begin2, InputIterator2 end2)
 251     {
 252       typedef iterator_traits<InputIterator1> traits1_type;
 253       typedef typename traits1_type::value_type value1_type;
 254       typedef typename traits1_type::iterator_category iterator1_category;
 255
 256       typedef iterator_traits<InputIterator2> traits2_type;
 257       typedef typename traits2_type::value_type value2_type;
 258       typedef typename traits2_type::iterator_category iterator2_category;
 259       typedef __gnu_parallel::less<value1_type, value2_type> less_type;
 260
 261       return lexicographical_compare_switch(begin1, end1, begin2, end2,
 262                                             less_type(), iterator1_category(),
 263                                             iterator2_category());
 264     }
 265
 266   // Public interface
 267   template<typename InputIterator1, typename InputIterator2,
 268            typename Predicate>
 269     inline bool
 270     lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
 271                             InputIterator2 begin2, InputIterator2 end2,
 272                             Predicate pred)
 273     {
 274       typedef iterator_traits<InputIterator1> traits1_type;
 275       typedef typename traits1_type::iterator_category iterator1_category;
 276
 277       typedef iterator_traits<InputIterator2> traits2_type;
 278       typedef typename traits2_type::iterator_category iterator2_category;
 279
 280       return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
 281                                             iterator1_category(),
 282                                             iterator2_category());
 283     }
 284 } // end namespace
 285 } // end namespace
 286
 287 #endif /* _GLIBCXX_ALGOBASE_H */