libstdc++
search.h
Go to the documentation of this file.
1 // -*- 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/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 
42 namespace __gnu_parallel
43 {
44  /**
45  * @brief Precalculate advances for Knuth-Morris-Pratt algorithm.
46  * @param elements Begin iterator of sequence to search for.
47  * @param length Length of sequence to search for.
48  * @param advances Returned offsets.
49  */
50 template<typename RandomAccessIterator, typename _DifferenceTp>
51  void
52  calc_borders(RandomAccessIterator elements, _DifferenceTp length,
53  _DifferenceTp* off)
54  {
55  typedef _DifferenceTp difference_type;
56 
57  off[0] = -1;
58  if (length > 1)
59  off[1] = 0;
60  difference_type k = 0;
61  for (difference_type j = 2; j <= length; j++)
62  {
63  while ((k >= 0) && !(elements[k] == elements[j-1]))
64  k = off[k];
65  off[j] = ++k;
66  }
67  }
68 
69  // Generic parallel find algorithm (requires random access iterator).
70 
71  /** @brief Parallel std::search.
72  * @param begin1 Begin iterator of first sequence.
73  * @param end1 End iterator of first sequence.
74  * @param begin2 Begin iterator of second sequence.
75  * @param end2 End iterator of second sequence.
76  * @param pred Find predicate.
77  * @return Place of finding in first sequences. */
78 template<typename _RandomAccessIterator1,
79  typename _RandomAccessIterator2,
80  typename Pred>
81  _RandomAccessIterator1
82  search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1,
83  _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
84  Pred pred)
85  {
87  typedef typename traits_type::difference_type difference_type;
88 
89  _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2));
90 
91  difference_type pattern_length = end2 - begin2;
92 
93  // Pattern too short.
94  if(pattern_length <= 0)
95  return end1;
96 
97  // Last point to start search.
98  difference_type input_length = (end1 - begin1) - pattern_length;
99 
100  // Where is first occurrence of pattern? defaults to end.
101  difference_type result = (end1 - begin1);
102  difference_type *splitters;
103 
104  // Pattern too long.
105  if (input_length < 0)
106  return end1;
107 
108  omp_lock_t result_lock;
109  omp_init_lock(&result_lock);
110 
111  thread_index_t num_threads =
112  std::max<difference_type>(1,
113  std::min<difference_type>(input_length, get_max_threads()));
114 
115  difference_type advances[pattern_length];
116  calc_borders(begin2, pattern_length, advances);
117 
118 # pragma omp parallel num_threads(num_threads)
119  {
120 # pragma omp single
121  {
122  num_threads = omp_get_num_threads();
123  splitters = new difference_type[num_threads + 1];
124  equally_split(input_length, num_threads, splitters);
125  }
126 
127  thread_index_t iam = omp_get_thread_num();
128 
129  difference_type start = splitters[iam], stop = splitters[iam + 1];
130 
131  difference_type 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 =
159  (advances[pos_in_pattern] < 0) ? 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 */