← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/gallium/frontends/clover/util/algorithm.hpp

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/frontends/clover/util/algorithm.hpp
1
 
//
2
 
// Copyright 2013 Francisco Jerez
3
 
//
4
 
// Permission is hereby granted, free of charge, to any person obtaining a
5
 
// copy of this software and associated documentation files (the "Software"),
6
 
// to deal in the Software without restriction, including without limitation
7
 
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
8
 
// and/or sell copies of the Software, and to permit persons to whom the
9
 
// Software is furnished to do so, subject to the following conditions:
10
 
//
11
 
// The above copyright notice and this permission notice shall be included in
12
 
// all copies or substantial portions of the Software.
13
 
//
14
 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15
 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16
 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17
 
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18
 
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19
 
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20
 
// OTHER DEALINGS IN THE SOFTWARE.
21
 
//
22
 
 
23
 
#ifndef CLOVER_UTIL_ALGORITHM_HPP
24
 
#define CLOVER_UTIL_ALGORITHM_HPP
25
 
 
26
 
#include <algorithm>
27
 
#include <sstream>
28
 
#include <stdexcept>
29
 
 
30
 
#include "util/range.hpp"
31
 
#include "util/functional.hpp"
32
 
 
33
 
namespace clover {
34
 
   namespace detail {
35
 
      template<typename R>
36
 
      using preferred_reference_type = decltype(*std::declval<R>().begin());
37
 
   }
38
 
 
39
 
   ///
40
 
   /// Return the first element in a range.
41
 
   ///
42
 
   template<typename R>
43
 
   detail::preferred_reference_type<R>
44
 
   head(R &&r) {
45
 
      assert(!r.empty());
46
 
      return r.front();
47
 
   }
48
 
 
49
 
   ///
50
 
   /// Return all elements in a range but the first.
51
 
   ///
52
 
   template<typename R>
53
 
   slice_range<R>
54
 
   tail(R &&r) {
55
 
      assert(!r.empty());
56
 
      return { std::forward<R>(r), 1, r.size() };
57
 
   }
58
 
 
59
 
   ///
60
 
   /// Return the only element in a range.
61
 
   ///
62
 
   template<typename R>
63
 
   detail::preferred_reference_type<R>
64
 
   unique(R &&r) {
65
 
      if (r.size() != 1)
66
 
         throw std::out_of_range("");
67
 
 
68
 
      return r.front();
69
 
   }
70
 
 
71
 
   ///
72
 
   /// Combine a variable number of ranges element-wise in a single
73
 
   /// range of tuples.
74
 
   ///
75
 
   template<typename... Rs>
76
 
   adaptor_range<zips, Rs...>
77
 
   zip(Rs &&... rs) {
78
 
      return map(zips(), std::forward<Rs>(rs)...);
79
 
   }
80
 
 
81
 
   ///
82
 
   /// Evaluate the elements of a range.
83
 
   ///
84
 
   /// Useful because most of the range algorithms evaluate their
85
 
   /// result lazily.
86
 
   ///
87
 
   template<typename R>
88
 
   void
89
 
   eval(R &&r) {
90
 
      for (auto i = r.begin(), e = r.end(); i != e; ++i)
91
 
         *i;
92
 
   }
93
 
 
94
 
   ///
95
 
   /// Apply functor \a f element-wise on a variable number of ranges
96
 
   /// \a rs.
97
 
   ///
98
 
   /// The functor \a f should take as many arguments as ranges are
99
 
   /// provided.
100
 
   ///
101
 
   template<typename F, typename... Rs>
102
 
   void
103
 
   for_each(F &&f, Rs &&... rs) {
104
 
      eval(map(std::forward<F>(f), std::forward<Rs>(rs)...));
105
 
   }
106
 
 
107
 
   ///
108
 
   /// Copy all elements from range \a r into an output container
109
 
   /// starting from iterator \a i.
110
 
   ///
111
 
   template<typename R, typename I>
112
 
   void
113
 
   copy(R &&r, I i) {
114
 
      for (detail::preferred_reference_type<R> x : r)
115
 
         *(i++) = x;
116
 
   }
117
 
 
118
 
   ///
119
 
   /// Reduce the elements of range \a r by applying functor \a f
120
 
   /// element by element.
121
 
   ///
122
 
   /// \a f should take an accumulator value (which is initialized to
123
 
   /// \a a) and an element value as arguments, and return an updated
124
 
   /// accumulator value.
125
 
   ///
126
 
   /// \returns The final value of the accumulator.
127
 
   ///
128
 
   template<typename F, typename A, typename R>
129
 
   A
130
 
   fold(F &&f, A a, R &&r) {
131
 
      for (detail::preferred_reference_type<R> x : r)
132
 
         a = f(a, x);
133
 
 
134
 
      return a;
135
 
   }
136
 
 
137
 
   ///
138
 
   /// Return how many elements of range \a r are equal to \a x.
139
 
   ///
140
 
   template<typename T, typename R>
141
 
   typename std::remove_reference<R>::type::size_type
142
 
   count(T &&x, R &&r) {
143
 
      typename std::remove_reference<R>::type::size_type n = 0;
144
 
 
145
 
      for (detail::preferred_reference_type<R> y : r) {
146
 
         if (x == y)
147
 
            n++;
148
 
      }
149
 
 
150
 
      return n;
151
 
   }
152
 
 
153
 
   ///
154
 
   /// Return the first element in range \a r for which predicate \a f
155
 
   /// evaluates to true.
156
 
   ///
157
 
   template<typename F, typename R>
158
 
   detail::preferred_reference_type<R>
159
 
   find(F &&f, R &&r) {
160
 
      for (detail::preferred_reference_type<R> x : r) {
161
 
         if (f(x))
162
 
            return x;
163
 
      }
164
 
 
165
 
      throw std::out_of_range("");
166
 
   }
167
 
 
168
 
   ///
169
 
   /// Return true if the element-wise application of predicate \a f
170
 
   /// on \a rs evaluates to true for all elements.
171
 
   ///
172
 
   template<typename F, typename... Rs>
173
 
   bool
174
 
   all_of(F &&f, Rs &&... rs) {
175
 
      for (auto b : map(f, rs...)) {
176
 
         if (!b)
177
 
            return false;
178
 
      }
179
 
 
180
 
      return true;
181
 
   }
182
 
 
183
 
   ///
184
 
   /// Return true if the element-wise application of predicate \a f
185
 
   /// on \a rs evaluates to true for any element.
186
 
   ///
187
 
   template<typename F, typename... Rs>
188
 
   bool
189
 
   any_of(F &&f, Rs &&... rs) {
190
 
      for (auto b : map(f, rs...)) {
191
 
         if (b)
192
 
            return true;
193
 
      }
194
 
 
195
 
      return false;
196
 
   }
197
 
 
198
 
   ///
199
 
   /// Erase elements for which predicate \a f evaluates to true from
200
 
   /// container \a r.
201
 
   ///
202
 
   template<typename F, typename R>
203
 
   void
204
 
   erase_if(F &&f, R &&r) {
205
 
      auto i = r.begin(), e = r.end();
206
 
 
207
 
      for (auto j = r.begin(); j != e; ++j) {
208
 
         if (!f(*j)) {
209
 
            if (j != i)
210
 
               *i = std::move(*j);
211
 
            ++i;
212
 
         }
213
 
      }
214
 
 
215
 
      r.erase(i, e);
216
 
   }
217
 
 
218
 
   ///
219
 
   /// Build a vector of string from a space separated string
220
 
   /// quoted parts content is preserved and unquoted
221
 
   ///
222
 
   inline std::vector<std::string>
223
 
   tokenize(const std::string &s) {
224
 
      std::vector<std::string> ss;
225
 
      std::ostringstream oss;
226
 
 
227
 
      // OpenCL programs can pass a quoted argument, most frequently the
228
 
      // include path. This is useful so that path containing spaces is
229
 
      // treated as a single argument instead of being split by the spaces.
230
 
      // Additionally, the argument should also be unquoted before being
231
 
      // passed to the compiler. We avoid using std::string::replace here to
232
 
      // remove quotes, as the single and double quote characters can be a
233
 
      // part of the file name.
234
 
      bool escape_next = false;
235
 
      bool in_quote_double = false;
236
 
      bool in_quote_single = false;
237
 
 
238
 
      for (auto c : s) {
239
 
         if (escape_next) {
240
 
            oss.put(c);
241
 
            escape_next = false;
242
 
         } else if (c == '\\') {
243
 
            escape_next = true;
244
 
         } else if (c == '"' && !in_quote_single) {
245
 
            in_quote_double = !in_quote_double;
246
 
         } else if (c == '\'' && !in_quote_double) {
247
 
            in_quote_single = !in_quote_single;
248
 
         } else if (c != ' ' || in_quote_single || in_quote_double) {
249
 
            oss.put(c);
250
 
         } else if (oss.tellp() > 0) {
251
 
            ss.emplace_back(oss.str());
252
 
            oss.str("");
253
 
         }
254
 
      }
255
 
 
256
 
      if (oss.tellp() > 0)
257
 
         ss.emplace_back(oss.str());
258
 
 
259
 
      if (in_quote_double || in_quote_single)
260
 
         throw invalid_build_options_error();
261
 
 
262
 
      return ss;
263
 
   }
264
 
 
265
 
   ///
266
 
   /// Build a \a sep separated string from a vector of T
267
 
   ///
268
 
   template<typename T>
269
 
   std::string
270
 
   detokenize(const std::vector<T> &ss, const std::string &sep) {
271
 
      std::string r;
272
 
 
273
 
      for (const auto &s : ss)
274
 
         r += (r.empty() ? "" : sep) + std::to_string(s);
275
 
 
276
 
      return r;
277
 
   }
278
 
 
279
 
   ///
280
 
   /// Build a \a sep separated string from a vector of string
281
 
   ///
282
 
   template <>
283
 
   inline std::string
284
 
   detokenize(const std::vector<std::string> &ss, const std::string &sep) {
285
 
      std::string r;
286
 
 
287
 
      for (const auto &s : ss)
288
 
         r += (r.empty() || s.empty() ? "" : sep) + s;
289
 
 
290
 
      return r;
291
 
   }
292
 
}
293
 
 
294
 
#endif