Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2007-2015 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/equally_split.h
  26.  *  This file is a GNU parallel extension to the Standard C++ Library.
  27.  */
  28.  
  29. // Written by Johannes Singler.
  30.  
  31. #ifndef _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H
  32. #define _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H 1
  33.  
  34. namespace __gnu_parallel
  35. {
  36.   /** @brief function to split a sequence into parts of almost equal size.
  37.    *
  38.    *  The resulting sequence __s of length __num_threads+1 contains the
  39.    *  splitting positions when splitting the range [0,__n) into parts of
  40.    *  almost equal size (plus minus 1).  The first entry is 0, the last
  41.    *  one n. There may result empty parts.
  42.    *  @param __n Number of elements
  43.    *  @param __num_threads Number of parts
  44.    *  @param __s Splitters
  45.    *  @returns End of __splitter sequence, i.e. @c __s+__num_threads+1 */
  46.   template<typename _DifferenceType, typename _OutputIterator>
  47.     _OutputIterator
  48.     __equally_split(_DifferenceType __n, _ThreadIndex __num_threads,
  49.                     _OutputIterator __s)
  50.     {
  51.       _DifferenceType __chunk_length = __n / __num_threads;
  52.       _DifferenceType __num_longer_chunks = __n % __num_threads;
  53.       _DifferenceType __pos = 0;
  54.       for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
  55.         {
  56.           *__s++ = __pos;
  57.           __pos += ((__i < __num_longer_chunks)
  58.                     ? (__chunk_length + 1) : __chunk_length);
  59.         }
  60.       *__s++ = __n;
  61.       return __s;
  62.     }
  63.  
  64.   /** @brief function to split a sequence into parts of almost equal size.
  65.    *
  66.    *  Returns the position of the splitting point between
  67.    *  thread number __thread_no (included) and
  68.    *  thread number __thread_no+1 (excluded).
  69.    *  @param __n Number of elements
  70.    *  @param __num_threads Number of parts
  71.    *  @param __thread_no Number of threads
  72.    *  @returns splitting point */
  73.   template<typename _DifferenceType>
  74.     _DifferenceType
  75.     __equally_split_point(_DifferenceType __n,
  76.                           _ThreadIndex __num_threads,
  77.                           _ThreadIndex __thread_no)
  78.     {
  79.       _DifferenceType __chunk_length = __n / __num_threads;
  80.       _DifferenceType __num_longer_chunks = __n % __num_threads;
  81.       if (__thread_no < __num_longer_chunks)
  82.         return __thread_no * (__chunk_length + 1);
  83.       else
  84.         return __num_longer_chunks * (__chunk_length + 1)
  85.           + (__thread_no - __num_longer_chunks) * __chunk_length;
  86.     }
  87. }
  88.  
  89. #endif /* _GLIBCXX_PARALLEL_EQUALLY_SPLIT_H */
  90.