]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
5817ff8e | 3 | // Copyright (C) 2007, 2008 Free Software Foundation, Inc. |
c2ba9709 JS |
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/search.h | |
32 | * @brief Parallel implementation base for std::search() and | |
33 | * std::search_n(). | |
34 | * This file is a GNU parallel extension to the Standard C++ Library. | |
35 | */ | |
36 | ||
37 | // Written by Felix Putze. | |
38 | ||
39 | #ifndef _GLIBCXX_PARALLEL_SEARCH_H | |
40 | #define _GLIBCXX_PARALLEL_SEARCH_H 1 | |
41 | ||
42 | #include <bits/stl_algobase.h> | |
43 | ||
44 | #include <parallel/parallel.h> | |
45 | #include <parallel/equally_split.h> | |
46 | ||
47 | ||
48 | namespace __gnu_parallel | |
49 | { | |
50 | /** | |
51 | * @brief Precalculate advances for Knuth-Morris-Pratt algorithm. | |
52 | * @param elements Begin iterator of sequence to search for. | |
53 | * @param length Length of sequence to search for. | |
54 | * @param advances Returned offsets. | |
55 | */ | |
e683ee2a | 56 | template<typename RandomAccessIterator, typename _DifferenceTp> |
c2ba9709 | 57 | void |
6f95a65a | 58 | calc_borders(RandomAccessIterator elements, _DifferenceTp length, |
e683ee2a | 59 | _DifferenceTp* off) |
c2ba9709 JS |
60 | { |
61 | typedef _DifferenceTp difference_type; | |
62 | ||
63 | off[0] = -1; | |
64 | if (length > 1) | |
65 | off[1] = 0; | |
66 | difference_type k = 0; | |
67 | for (difference_type j = 2; j <= length; j++) | |
68 | { | |
e683ee2a JS |
69 | while ((k >= 0) && !(elements[k] == elements[j-1])) |
70 | k = off[k]; | |
71 | off[j] = ++k; | |
c2ba9709 JS |
72 | } |
73 | } | |
74 | ||
75 | // Generic parallel find algorithm (requires random access iterator). | |
76 | ||
77 | /** @brief Parallel std::search. | |
78 | * @param begin1 Begin iterator of first sequence. | |
79 | * @param end1 End iterator of first sequence. | |
80 | * @param begin2 Begin iterator of second sequence. | |
81 | * @param end2 End iterator of second sequence. | |
82 | * @param pred Find predicate. | |
83 | * @return Place of finding in first sequences. */ | |
5817ff8e PC |
84 | template<typename _RandomAccessIterator1, |
85 | typename _RandomAccessIterator2, | |
86 | typename Pred> | |
c2ba9709 JS |
87 | _RandomAccessIterator1 |
88 | search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, | |
e683ee2a JS |
89 | _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, |
90 | Pred pred) | |
c2ba9709 JS |
91 | { |
92 | typedef std::iterator_traits<_RandomAccessIterator1> traits_type; | |
93 | typedef typename traits_type::difference_type difference_type; | |
94 | ||
95 | _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2)); | |
96 | ||
97 | difference_type pattern_length = end2 - begin2; | |
98 | ||
99 | // Pattern too short. | |
100 | if(pattern_length <= 0) | |
101 | return end1; | |
102 | ||
103 | // Last point to start search. | |
104 | difference_type input_length = (end1 - begin1) - pattern_length; | |
105 | ||
a3e6b31a | 106 | // Where is first occurrence of pattern? defaults to end. |
59b567fb | 107 | difference_type result = (end1 - begin1); |
e683ee2a | 108 | difference_type *splitters; |
c2ba9709 JS |
109 | |
110 | // Pattern too long. | |
111 | if (input_length < 0) | |
112 | return end1; | |
113 | ||
59b567fb JS |
114 | omp_lock_t result_lock; |
115 | omp_init_lock(&result_lock); | |
116 | ||
e683ee2a JS |
117 | thread_index_t num_threads = |
118 | std::max<difference_type>(1, | |
119 | std::min<difference_type>(input_length, get_max_threads())); | |
c2ba9709 JS |
120 | |
121 | difference_type advances[pattern_length]; | |
122 | calc_borders(begin2, pattern_length, advances); | |
123 | ||
e683ee2a JS |
124 | # pragma omp parallel num_threads(num_threads) |
125 | { | |
126 | # pragma omp single | |
127 | { | |
128 | num_threads = omp_get_num_threads(); | |
129 | splitters = new difference_type[num_threads + 1]; | |
130 | equally_split(input_length, num_threads, splitters); | |
131 | } | |
132 | ||
133 | thread_index_t iam = omp_get_thread_num(); | |
134 | ||
135 | difference_type start = splitters[iam], stop = splitters[iam + 1]; | |
136 | ||
137 | difference_type pos_in_pattern = 0; | |
138 | bool found_pattern = false; | |
139 | ||
140 | while (start <= stop && !found_pattern) | |
141 | { | |
142 | // Get new value of result. | |
143 | #pragma omp flush(result) | |
144 | // No chance for this thread to find first occurrence. | |
145 | if (result < start) | |
146 | break; | |
147 | while (pred(begin1[start + pos_in_pattern], | |
148 | begin2[pos_in_pattern])) | |
149 | { | |
150 | ++pos_in_pattern; | |
151 | if (pos_in_pattern == pattern_length) | |
152 | { | |
153 | // Found new candidate for result. | |
154 | omp_set_lock(&result_lock); | |
155 | result = std::min(result, start); | |
156 | omp_unset_lock(&result_lock); | |
157 | ||
158 | found_pattern = true; | |
159 | break; | |
160 | } | |
161 | } | |
162 | // Make safe jump. | |
163 | start += (pos_in_pattern - advances[pos_in_pattern]); | |
164 | pos_in_pattern = | |
165 | (advances[pos_in_pattern] < 0) ? 0 : advances[pos_in_pattern]; | |
166 | } | |
167 | } //parallel | |
c2ba9709 | 168 | |
59b567fb JS |
169 | omp_destroy_lock(&result_lock); |
170 | ||
e683ee2a JS |
171 | delete[] splitters; |
172 | ||
c2ba9709 | 173 | // Return iterator on found element. |
59b567fb | 174 | return (begin1 + result); |
c2ba9709 JS |
175 | } |
176 | } // end namespace | |
177 | ||
cbcd1e45 | 178 | #endif /* _GLIBCXX_PARALLEL_SEARCH_H */ |