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/search.h
  26.  *  @brief Parallel implementation base for std::search() and
  27.  *  std::search_n().
  28.  *  This file is a GNU parallel extension to the Standard C++ Library.
  29.  */
  30.  
  31. // Written by Felix Putze.
  32.  
  33. #ifndef _GLIBCXX_PARALLEL_SEARCH_H
  34. #define _GLIBCXX_PARALLEL_SEARCH_H 1
  35.  
  36. #include <bits/stl_algobase.h>
  37.  
  38. #include <parallel/parallel.h>
  39. #include <parallel/equally_split.h>
  40.  
  41. namespace __gnu_parallel
  42. {
  43.   /**
  44.    *  @brief Precalculate __advances for Knuth-Morris-Pratt algorithm.
  45.    *  @param __elements Begin iterator of sequence to search for.
  46.    *  @param __length Length of sequence to search for.
  47.    *  @param __off Returned __offsets.
  48.    */
  49.   template<typename _RAIter, typename _DifferenceTp>
  50.     void
  51.     __calc_borders(_RAIter __elements, _DifferenceTp __length,
  52.                    _DifferenceTp* __off)
  53.     {
  54.       typedef _DifferenceTp _DifferenceType;
  55.  
  56.       __off[0] = -1;
  57.       if (__length > 1)
  58.         __off[1] = 0;
  59.       _DifferenceType __k = 0;
  60.       for (_DifferenceType __j = 2; __j <= __length; __j++)
  61.         {
  62.           while ((__k >= 0) && !(__elements[__k] == __elements[__j-1]))
  63.             __k = __off[__k];
  64.           __off[__j] = ++__k;
  65.         }
  66.     }
  67.  
  68.   // Generic parallel find algorithm (requires random access iterator).
  69.  
  70.   /** @brief Parallel std::search.
  71.    *  @param __begin1 Begin iterator of first sequence.
  72.    *  @param __end1 End iterator of first sequence.
  73.    *  @param __begin2 Begin iterator of second sequence.
  74.    *  @param __end2 End iterator of second sequence.
  75.    *  @param __pred Find predicate.
  76.    *  @return Place of finding in first sequences. */
  77.   template<typename __RAIter1,
  78.            typename __RAIter2,
  79.            typename _Pred>
  80.     __RAIter1
  81.     __search_template(__RAIter1 __begin1, __RAIter1 __end1,
  82.                       __RAIter2 __begin2, __RAIter2 __end2,
  83.                       _Pred __pred)
  84.     {
  85.       typedef std::iterator_traits<__RAIter1> _TraitsType;
  86.       typedef typename _TraitsType::difference_type _DifferenceType;
  87.  
  88.       _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2));
  89.  
  90.       _DifferenceType __pattern_length = __end2 - __begin2;
  91.  
  92.       // Pattern too short.
  93.       if(__pattern_length <= 0)
  94.         return __end1;
  95.  
  96.       // Last point to start search.
  97.       _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length;
  98.  
  99.       // Where is first occurrence of pattern? defaults to end.
  100.       _DifferenceType __result = (__end1 - __begin1);
  101.       _DifferenceType *__splitters;
  102.  
  103.       // Pattern too long.
  104.       if (__input_length < 0)
  105.         return __end1;
  106.  
  107.       omp_lock_t __result_lock;
  108.       omp_init_lock(&__result_lock);
  109.  
  110.       _ThreadIndex __num_threads = std::max<_DifferenceType>
  111.         (1, std::min<_DifferenceType>(__input_length,
  112.                                       __get_max_threads()));
  113.  
  114.       _DifferenceType __advances[__pattern_length];
  115.       __calc_borders(__begin2, __pattern_length, __advances);
  116.  
  117. #     pragma omp parallel num_threads(__num_threads)
  118.       {
  119. #       pragma omp single
  120.         {
  121.           __num_threads = omp_get_num_threads();
  122.           __splitters = new _DifferenceType[__num_threads + 1];
  123.           __equally_split(__input_length, __num_threads, __splitters);
  124.         }
  125.  
  126.         _ThreadIndex __iam = omp_get_thread_num();
  127.  
  128.         _DifferenceType __start = __splitters[__iam],
  129.                          __stop = __splitters[__iam + 1];
  130.  
  131.         _DifferenceType __pos_in_pattern = 0;
  132.         bool __found_pattern = false;
  133.  
  134.         while (__start <= __stop && !__found_pattern)
  135.           {
  136.             // Get new value of result.
  137. #pragma omp flush(__result)
  138.             // No chance for this thread to find first occurrence.
  139.             if (__result < __start)
  140.               break;
  141.             while (__pred(__begin1[__start + __pos_in_pattern],
  142.                           __begin2[__pos_in_pattern]))
  143.               {
  144.                 ++__pos_in_pattern;
  145.                 if (__pos_in_pattern == __pattern_length)
  146.                   {
  147.                     // Found new candidate for result.
  148.                     omp_set_lock(&__result_lock);
  149.                     __result = std::min(__result, __start);
  150.                     omp_unset_lock(&__result_lock);
  151.  
  152.                     __found_pattern = true;
  153.                     break;
  154.                   }
  155.               }
  156.             // Make safe jump.
  157.             __start += (__pos_in_pattern - __advances[__pos_in_pattern]);
  158.             __pos_in_pattern = (__advances[__pos_in_pattern] < 0
  159.                                 ? 0 : __advances[__pos_in_pattern]);
  160.           }
  161.       } //parallel
  162.  
  163.       omp_destroy_lock(&__result_lock);
  164.  
  165.       delete[] __splitters;
  166.      
  167.       // Return iterator on found element.
  168.       return (__begin1 + __result);
  169.     }
  170. } // end namespace
  171.  
  172. #endif /* _GLIBCXX_PARALLEL_SEARCH_H */
  173.