summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorFrancisco Jerez <[email protected]>2013-10-06 13:47:19 -0700
committerFrancisco Jerez <[email protected]>2013-10-21 10:47:02 -0700
commite93efa0d505e0337629b178d970e369c0745911d (patch)
treedc79b204fdbf5e2c3c152b9466e3d5f7ca892086 /src
parent7baad4b99656c7b9d992bd7626bda2e719412cff (diff)
clover: Import new utility library.
Tested-by: Tom Stellard <[email protected]>
Diffstat (limited to 'src')
-rw-r--r--src/gallium/state_trackers/clover/Doxyfile2
-rw-r--r--src/gallium/state_trackers/clover/Makefile.sources10
-rw-r--r--src/gallium/state_trackers/clover/util/adaptor.hpp183
-rw-r--r--src/gallium/state_trackers/clover/util/algebra.hpp160
-rw-r--r--src/gallium/state_trackers/clover/util/algorithm.hpp206
-rw-r--r--src/gallium/state_trackers/clover/util/compat.cpp38
-rw-r--r--src/gallium/state_trackers/clover/util/compat.hpp328
-rw-r--r--src/gallium/state_trackers/clover/util/functional.hpp375
-rw-r--r--src/gallium/state_trackers/clover/util/lazy.hpp161
-rw-r--r--src/gallium/state_trackers/clover/util/pointer.hpp157
-rw-r--r--src/gallium/state_trackers/clover/util/range.hpp421
-rw-r--r--src/gallium/state_trackers/clover/util/tuple.hpp117
12 files changed, 2157 insertions, 1 deletions
diff --git a/src/gallium/state_trackers/clover/Doxyfile b/src/gallium/state_trackers/clover/Doxyfile
index 50250e75672..19337bbd656 100644
--- a/src/gallium/state_trackers/clover/Doxyfile
+++ b/src/gallium/state_trackers/clover/Doxyfile
@@ -610,7 +610,7 @@ WARN_LOGFILE =
# directories like "/usr/src/myproject". Separate the files or directories
# with spaces.
-INPUT = api/ core/
+INPUT = api/ core/ util/
# This tag can be used to specify the character encoding of the source files
# that doxygen parses. Internally doxygen uses the UTF-8 encoding, which is
diff --git a/src/gallium/state_trackers/clover/Makefile.sources b/src/gallium/state_trackers/clover/Makefile.sources
index fd23d78b11f..e148ec8e584 100644
--- a/src/gallium/state_trackers/clover/Makefile.sources
+++ b/src/gallium/state_trackers/clover/Makefile.sources
@@ -1,4 +1,14 @@
CPP_SOURCES := \
+ util/adaptor.hpp \
+ util/algebra.hpp \
+ util/algorithm.hpp \
+ util/compat.cpp \
+ util/compat.hpp \
+ util/functional.hpp \
+ util/lazy.hpp \
+ util/pointer.hpp \
+ util/range.hpp \
+ util/tuple.hpp \
core/base.hpp \
core/compat.hpp \
core/compiler.hpp \
diff --git a/src/gallium/state_trackers/clover/util/adaptor.hpp b/src/gallium/state_trackers/clover/util/adaptor.hpp
new file mode 100644
index 00000000000..fafb01fe9e7
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/adaptor.hpp
@@ -0,0 +1,183 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_ADAPTOR_HPP
+#define CLOVER_UTIL_ADAPTOR_HPP
+
+#include <iterator>
+
+#include "util/tuple.hpp"
+#include "util/pointer.hpp"
+#include "util/functional.hpp"
+
+namespace clover {
+ namespace detail {
+ ///
+ /// Implementation of the iterator concept that transforms the
+ /// value of the source iterators \a Is on dereference by use of
+ /// a functor \a F.
+ ///
+ /// The exact category of the resulting iterator should be the
+ /// least common denominator of the source iterator categories.
+ ///
+ template<typename F, typename... Is>
+ class iterator_adaptor {
+ public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef typename std::result_of<
+ F(typename std::iterator_traits<Is>::reference...)
+ >::type reference;
+ typedef typename std::remove_reference<reference>::type value_type;
+ typedef pseudo_ptr<value_type> pointer;
+ typedef std::ptrdiff_t difference_type;
+
+ iterator_adaptor() {
+ }
+
+ iterator_adaptor(F f, std::tuple<Is...> &&its) :
+ f(f), its(std::move(its)) {
+ }
+
+ reference
+ operator*() const {
+ return tuple::apply(f, tuple::map(derefs(), its));
+ }
+
+ iterator_adaptor &
+ operator++() {
+ tuple::map(preincs(), its);
+ return *this;
+ }
+
+ iterator_adaptor
+ operator++(int) {
+ auto jt = *this;
+ ++*this;
+ return jt;
+ }
+
+ bool
+ operator==(const iterator_adaptor &jt) const {
+ return its == jt.its;
+ }
+
+ bool
+ operator!=(const iterator_adaptor &jt) const {
+ return its != jt.its;
+ }
+
+ pointer
+ operator->() const {
+ return { **this };
+ }
+
+ iterator_adaptor &
+ operator--() {
+ tuple::map(predecs(), its);
+ return *this;
+ }
+
+ iterator_adaptor
+ operator--(int) {
+ auto jt = *this;
+ --*this;
+ return jt;
+ }
+
+ iterator_adaptor &
+ operator+=(difference_type n) {
+ tuple::map(advances_by(n), its);
+ return *this;
+ }
+
+ iterator_adaptor &
+ operator-=(difference_type n) {
+ tuple::map(advances_by(n), its);
+ return *this;
+ }
+
+ iterator_adaptor
+ operator+(difference_type n) const {
+ auto jt = *this;
+ jt += n;
+ return jt;
+ }
+
+ iterator_adaptor
+ operator-(difference_type n) const {
+ auto jt = *this;
+ jt -= n;
+ return jt;
+ }
+
+ difference_type
+ operator-(const iterator_adaptor &jt) const {
+ return std::get<0>(its) - std::get<0>(jt.its);
+ }
+
+ reference
+ operator[](difference_type n) const {
+ return *(*this + n);
+ }
+
+ bool
+ operator<(iterator_adaptor &jt) const {
+ return *this - jt < 0;
+ }
+
+ bool
+ operator>(iterator_adaptor &jt) const {
+ return *this - jt > 0;
+ }
+
+ bool
+ operator>=(iterator_adaptor &jt) const {
+ return !(*this < jt);
+ }
+
+ bool
+ operator<=(iterator_adaptor &jt) const {
+ return !(*this > jt);
+ }
+
+ protected:
+ F f;
+ std::tuple<Is...> its;
+ };
+
+ template<typename F, typename... Is>
+ iterator_adaptor<F, Is...>
+ operator+(typename iterator_adaptor<F, Is...>::difference_type n,
+ const iterator_adaptor<F, Is...> &jt) {
+ return (jt + n);
+ }
+
+ template<typename F, typename... Is>
+ iterator_adaptor<F, Is...>
+ operator-(typename iterator_adaptor<F, Is...>::difference_type n,
+ const iterator_adaptor<F, Is...> &jt) {
+ return (jt - n);
+ }
+ }
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/algebra.hpp b/src/gallium/state_trackers/clover/util/algebra.hpp
new file mode 100644
index 00000000000..43a9d8bbf5f
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/algebra.hpp
@@ -0,0 +1,160 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_ALGEBRA_HPP
+#define CLOVER_UTIL_ALGEBRA_HPP
+
+#include <type_traits>
+
+#include "util/range.hpp"
+#include "util/functional.hpp"
+
+namespace clover {
+ ///
+ /// Class that identifies vectors (in the linear-algebraic sense).
+ ///
+ /// There should be a definition of this class for each type that
+ /// makes sense as vector arithmetic operand.
+ ///
+ template<typename V, typename = void>
+ struct vector_traits;
+
+ ///
+ /// References of vectors are vectors.
+ ///
+ template<typename T>
+ struct vector_traits<T &, typename vector_traits<T>::enable> {
+ typedef void enable;
+ };
+
+ ///
+ /// Constant vectors are vectors.
+ ///
+ template<typename T>
+ struct vector_traits<const T, typename vector_traits<T>::enable> {
+ typedef void enable;
+ };
+
+ ///
+ /// Arrays of arithmetic types are vectors.
+ ///
+ template<typename T, std::size_t N>
+ struct vector_traits<std::array<T, N>,
+ typename std::enable_if<
+ std::is_arithmetic<T>::value>::type> {
+ typedef void enable;
+ };
+
+ namespace detail {
+ template<typename... Ts>
+ struct are_defined {
+ typedef void enable;
+ };
+ }
+
+ ///
+ /// The result of mapping a vector is a vector.
+ ///
+ template<typename F, typename... Vs>
+ struct vector_traits<adaptor_range<F, Vs...>,
+ typename detail::are_defined<
+ typename vector_traits<Vs>::enable...>::enable> {
+ typedef void enable;
+ };
+
+ ///
+ /// Vector sum.
+ ///
+ template<typename U, typename V,
+ typename = typename vector_traits<U>::enable,
+ typename = typename vector_traits<V>::enable>
+ adaptor_range<plus, U, V>
+ operator+(U &&u, V &&v) {
+ return map(plus(), std::forward<U>(u), std::forward<V>(v));
+ }
+
+ ///
+ /// Vector difference.
+ ///
+ template<typename U, typename V,
+ typename = typename vector_traits<U>::enable,
+ typename = typename vector_traits<V>::enable>
+ adaptor_range<minus, U, V>
+ operator-(U &&u, V &&v) {
+ return map(minus(), std::forward<U>(u), std::forward<V>(v));
+ }
+
+ ///
+ /// Scalar multiplication.
+ ///
+ template<typename U, typename T,
+ typename = typename vector_traits<U>::enable>
+ adaptor_range<multiplies_by_t<T>, U>
+ operator*(U &&u, T &&a) {
+ return map(multiplies_by<T>(std::forward<T>(a)), std::forward<U>(u));
+ }
+
+ ///
+ /// Scalar multiplication.
+ ///
+ template<typename U, typename T,
+ typename = typename vector_traits<U>::enable>
+ adaptor_range<multiplies_by_t<T>, U>
+ operator*(T &&a, U &&u) {
+ return map(multiplies_by<T>(std::forward<T>(a)), std::forward<U>(u));
+ }
+
+ ///
+ /// Additive inverse.
+ ///
+ template<typename U,
+ typename = typename vector_traits<U>::enable>
+ adaptor_range<negate, U>
+ operator-(U &&u) {
+ return map(negate(), std::forward<U>(u));
+ }
+
+ namespace detail {
+ template<typename U, typename V>
+ using dot_type = typename std::common_type<
+ typename std::remove_reference<U>::type::value_type,
+ typename std::remove_reference<V>::type::value_type
+ >::type;
+ }
+
+ ///
+ /// Dot product of two vectors.
+ ///
+ /// It can also do matrix multiplication if \a u or \a v is a
+ /// vector of vectors.
+ ///
+ template<typename U, typename V,
+ typename = typename vector_traits<U>::enable,
+ typename = typename vector_traits<V>::enable>
+ detail::dot_type<U, V>
+ dot(U &&u, V &&v) {
+ return fold(plus(), detail::dot_type<U, V>(),
+ map(multiplies(), u, v));
+ }
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/algorithm.hpp b/src/gallium/state_trackers/clover/util/algorithm.hpp
new file mode 100644
index 00000000000..4eb90cffa9f
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/algorithm.hpp
@@ -0,0 +1,206 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_ALGORITHM_HPP
+#define CLOVER_UTIL_ALGORITHM_HPP
+
+#include <algorithm>
+#include <stdexcept>
+
+#include "util/range.hpp"
+#include "util/functional.hpp"
+
+namespace clover {
+ namespace detail {
+ template<typename R>
+ using preferred_reference_type = decltype(*std::declval<R>().begin());
+ }
+
+ ///
+ /// Return the first element in a range.
+ ///
+ template<typename R>
+ detail::preferred_reference_type<R>
+ head(R &&r) {
+ assert(!r.empty());
+ return r.front();
+ }
+
+ ///
+ /// Return all elements in a range but the first.
+ ///
+ template<typename R>
+ slice_range<R>
+ tail(R &&r) {
+ assert(!r.empty());
+ return { std::forward<R>(r), 1, r.size() };
+ }
+
+ ///
+ /// Combine a variable number of ranges element-wise in a single
+ /// range of tuples.
+ ///
+ template<typename... Rs>
+ adaptor_range<zips, Rs...>
+ zip(Rs &&... rs) {
+ return map(zips(), std::forward<Rs>(rs)...);
+ }
+
+ ///
+ /// Evaluate the elements of a range.
+ ///
+ /// Useful because most of the range algorithms evaluate their
+ /// result lazily.
+ ///
+ template<typename R>
+ void
+ eval(R &&r) {
+ for (auto i = r.begin(), e = r.end(); i != e; ++i)
+ *i;
+ }
+
+ ///
+ /// Apply functor \a f element-wise on a variable number of ranges
+ /// \a rs.
+ ///
+ /// The functor \a f should take as many arguments as ranges are
+ /// provided.
+ ///
+ template<typename F, typename... Rs>
+ void
+ for_each(F &&f, Rs &&... rs) {
+ eval(map(std::forward<F>(f), std::forward<Rs>(rs)...));
+ }
+
+ ///
+ /// Copy all elements from range \a r into an output container
+ /// starting from iterator \a i.
+ ///
+ template<typename R, typename I>
+ void
+ copy(R &&r, I i) {
+ for (detail::preferred_reference_type<R> x : r)
+ *(i++) = x;
+ }
+
+ ///
+ /// Reduce the elements of range \a r by applying functor \a f
+ /// element by element.
+ ///
+ /// \a f should take an accumulator value (which is initialized to
+ /// \a a) and an element value as arguments, and return an updated
+ /// accumulator value.
+ ///
+ /// \returns The final value of the accumulator.
+ ///
+ template<typename F, typename A, typename R>
+ A
+ fold(F &&f, A a, R &&r) {
+ for (detail::preferred_reference_type<R> x : r)
+ a = f(a, x);
+
+ return a;
+ }
+
+ ///
+ /// Return how many elements of range \a r are equal to \a x.
+ ///
+ template<typename T, typename R>
+ typename std::remove_reference<R>::type::size_type
+ count(T &&x, R &&r) {
+ typename std::remove_reference<R>::type::size_type n = 0;
+
+ for (detail::preferred_reference_type<R> y : r) {
+ if (x == y)
+ n++;
+ }
+
+ return n;
+ }
+
+ ///
+ /// Return the first element in range \a r for which predicate \a f
+ /// evaluates to true.
+ ///
+ template<typename F, typename R>
+ detail::preferred_reference_type<R>
+ find(F &&f, R &&r) {
+ for (detail::preferred_reference_type<R> x : r) {
+ if (f(x))
+ return x;
+ }
+
+ throw std::out_of_range("");
+ }
+
+ ///
+ /// Return true if the element-wise application of predicate \a f
+ /// on \a rs evaluates to true for all elements.
+ ///
+ template<typename F, typename... Rs>
+ bool
+ all_of(F &&f, Rs &&... rs) {
+ for (auto b : map(f, rs...)) {
+ if (!b)
+ return false;
+ }
+
+ return true;
+ }
+
+ ///
+ /// Return true if the element-wise application of predicate \a f
+ /// on \a rs evaluates to true for any element.
+ ///
+ template<typename F, typename... Rs>
+ bool
+ any_of(F &&f, Rs &&... rs) {
+ for (auto b : map(f, rs...)) {
+ if (b)
+ return true;
+ }
+
+ return false;
+ }
+
+ ///
+ /// Erase elements for which predicate \a f evaluates to true from
+ /// container \a r.
+ ///
+ template<typename F, typename R>
+ void
+ erase_if(F &&f, R &&r) {
+ auto i = r.begin(), e = r.end();
+
+ for (auto j = r.begin(); j != e; ++j) {
+ if (!f(*j)) {
+ if (j != i)
+ *i = std::move(*j);
+ ++i;
+ }
+ }
+
+ r.erase(i, e);
+ }
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/compat.cpp b/src/gallium/state_trackers/clover/util/compat.cpp
new file mode 100644
index 00000000000..80d5b3ecf82
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/compat.cpp
@@ -0,0 +1,38 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#include "util/compat.hpp"
+
+using namespace clover::compat;
+
+exception::~exception() {
+}
+
+const char *
+exception::what() const {
+ return "";
+}
+
+const char *
+runtime_error::what() const {
+ return _what.c_str();
+}
diff --git a/src/gallium/state_trackers/clover/util/compat.hpp b/src/gallium/state_trackers/clover/util/compat.hpp
new file mode 100644
index 00000000000..e68d9df2969
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/compat.hpp
@@ -0,0 +1,328 @@
+//
+// Copyright 2012 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_COMPAT_HPP
+#define CLOVER_UTIL_COMPAT_HPP
+
+#include <new>
+#include <cstring>
+#include <cstdlib>
+#include <string>
+#include <stdint.h>
+
+namespace clover {
+ namespace compat {
+ // XXX - For cases where we can't rely on STL... I.e. the
+ // interface between code compiled as C++98 and C++11
+ // source. Get rid of this as soon as everything can be
+ // compiled as C++11.
+
+ template<typename T>
+ class vector {
+ protected:
+ static T *
+ alloc(int n, const T *q, int m) {
+ T *p = reinterpret_cast<T *>(std::malloc(n * sizeof(T)));
+
+ for (int i = 0; i < m; ++i)
+ new(&p[i]) T(q[i]);
+
+ return p;
+ }
+
+ static void
+ free(int n, T *p) {
+ for (int i = 0; i < n; ++i)
+ p[i].~T();
+
+ std::free(p);
+ }
+
+ public:
+ typedef T *iterator;
+ typedef const T *const_iterator;
+ typedef T value_type;
+ typedef T &reference;
+ typedef const T &const_reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::size_t size_type;
+
+ vector() : p(NULL), n(0) {
+ }
+
+ vector(const vector &v) : p(alloc(v.n, v.p, v.n)), n(v.n) {
+ }
+
+ vector(iterator p, size_type n) : p(alloc(n, p, n)), n(n) {
+ }
+
+ template<typename C>
+ vector(const C &v) :
+ p(alloc(v.size(), &*v.begin(), v.size())), n(v.size()) {
+ }
+
+ ~vector() {
+ free(n, p);
+ }
+
+ vector &
+ operator=(const vector &v) {
+ free(n, p);
+
+ p = alloc(v.n, v.p, v.n);
+ n = v.n;
+
+ return *this;
+ }
+
+ void
+ reserve(size_type m) {
+ if (n < m) {
+ T *q = alloc(m, p, n);
+ free(n, p);
+
+ p = q;
+ n = m;
+ }
+ }
+
+ void
+ resize(size_type m, T x = T()) {
+ size_type n = size();
+
+ reserve(m);
+
+ for (size_type i = n; i < m; ++i)
+ new(&p[i]) T(x);
+ }
+
+ void
+ push_back(const T &x) {
+ size_type n = size();
+ reserve(n + 1);
+ new(&p[n]) T(x);
+ }
+
+ size_type
+ size() const {
+ return n;
+ }
+
+ iterator
+ begin() {
+ return p;
+ }
+
+ const_iterator
+ begin() const {
+ return p;
+ }
+
+ iterator
+ end() {
+ return p + n;
+ }
+
+ const_iterator
+ end() const {
+ return p + n;
+ }
+
+ reference
+ operator[](size_type i) {
+ return p[i];
+ }
+
+ const_reference
+ operator[](size_type i) const {
+ return p[i];
+ }
+
+ private:
+ iterator p;
+ size_type n;
+ };
+
+ template<typename T>
+ class vector_ref {
+ public:
+ typedef T *iterator;
+ typedef const T *const_iterator;
+ typedef T value_type;
+ typedef T &reference;
+ typedef const T &const_reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::size_t size_type;
+
+ vector_ref(iterator p, size_type n) : p(p), n(n) {
+ }
+
+ template<typename C>
+ vector_ref(C &v) : p(&*v.begin()), n(v.size()) {
+ }
+
+ size_type
+ size() const {
+ return n;
+ }
+
+ iterator
+ begin() {
+ return p;
+ }
+
+ const_iterator
+ begin() const {
+ return p;
+ }
+
+ iterator
+ end() {
+ return p + n;
+ }
+
+ const_iterator
+ end() const {
+ return p + n;
+ }
+
+ reference
+ operator[](int i) {
+ return p[i];
+ }
+
+ const_reference
+ operator[](int i) const {
+ return p[i];
+ }
+
+ private:
+ iterator p;
+ size_type n;
+ };
+
+ class istream {
+ public:
+ typedef vector_ref<const unsigned char> buffer_t;
+
+ class error {
+ public:
+ virtual ~error() {}
+ };
+
+ istream(const buffer_t &buf) : buf(buf), offset(0) {}
+
+ void
+ read(char *p, size_t n) {
+ if (offset + n > buf.size())
+ throw error();
+
+ std::memcpy(p, buf.begin() + offset, n);
+ offset += n;
+ }
+
+ private:
+ const buffer_t &buf;
+ size_t offset;
+ };
+
+ class ostream {
+ public:
+ typedef vector<unsigned char> buffer_t;
+
+ ostream(buffer_t &buf) : buf(buf), offset(buf.size()) {}
+
+ void
+ write(const char *p, size_t n) {
+ buf.resize(offset + n);
+ std::memcpy(buf.begin() + offset, p, n);
+ offset += n;
+ }
+
+ private:
+ buffer_t &buf;
+ size_t offset;
+ };
+
+ class string : public vector_ref<const char> {
+ public:
+ string(const char *p) : vector_ref(p, std::strlen(p)) {
+ }
+
+ template<typename C>
+ string(const C &v) : vector_ref(v) {
+ }
+
+ operator std::string() const {
+ return std::string(begin(), end());
+ }
+
+ const char *
+ c_str() const {
+ return begin();
+ }
+
+ const char *
+ find(const string &s) const {
+ for (size_t i = 0; i + s.size() < size(); ++i) {
+ if (!std::memcmp(begin() + i, s.begin(), s.size()))
+ return begin() + i;
+ }
+
+ return end();
+ }
+ };
+
+ template<typename T>
+ bool
+ operator==(const vector_ref<T> &a, const vector_ref<T> &b) {
+ if (a.size() != b.size())
+ return false;
+
+ for (size_t i = 0; i < a.size(); ++i)
+ if (a[i] != b[i])
+ return false;
+
+ return true;
+ }
+
+ class exception {
+ public:
+ exception() {}
+ virtual ~exception();
+
+ virtual const char *what() const;
+ };
+
+ class runtime_error : public exception {
+ public:
+ runtime_error(const string &what) : _what(what) {}
+
+ virtual const char *what() const;
+
+ protected:
+ string _what;
+ };
+ }
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/functional.hpp b/src/gallium/state_trackers/clover/util/functional.hpp
new file mode 100644
index 00000000000..8e0b483a78f
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/functional.hpp
@@ -0,0 +1,375 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_FUNCTIONAL_HPP
+#define CLOVER_UTIL_FUNCTIONAL_HPP
+
+#include <type_traits>
+
+namespace clover {
+ struct identity {
+ template<typename T>
+ typename std::remove_reference<T>::type
+ operator()(T &&x) const {
+ return x;
+ }
+ };
+
+ struct plus {
+ template<typename T, typename S>
+ typename std::common_type<T, S>::type
+ operator()(T x, S y) const {
+ return x + y;
+ }
+ };
+
+ struct minus {
+ template<typename T, typename S>
+ typename std::common_type<T, S>::type
+ operator()(T x, S y) const {
+ return x - y;
+ }
+ };
+
+ struct negate {
+ template<typename T>
+ T
+ operator()(T x) const {
+ return -x;
+ }
+ };
+
+ struct multiplies {
+ template<typename T, typename S>
+ typename std::common_type<T, S>::type
+ operator()(T x, S y) const {
+ return x * y;
+ }
+ };
+
+ struct divides {
+ template<typename T, typename S>
+ typename std::common_type<T, S>::type
+ operator()(T x, S y) const {
+ return x / y;
+ }
+ };
+
+ struct modulus {
+ template<typename T, typename S>
+ typename std::common_type<T, S>::type
+ operator()(T x, S y) const {
+ return x % y;
+ }
+ };
+
+ struct minimum {
+ template<typename T>
+ T
+ operator()(T x) const {
+ return x;
+ }
+
+ template<typename T, typename... Ts>
+ T
+ operator()(T x, Ts... xs) const {
+ T y = minimum()(xs...);
+ return x < y ? x : y;
+ }
+ };
+
+ struct maximum {
+ template<typename T>
+ T
+ operator()(T x) const {
+ return x;
+ }
+
+ template<typename T, typename... Ts>
+ T
+ operator()(T x, Ts... xs) const {
+ T y = maximum()(xs...);
+ return x < y ? y : x;
+ }
+ };
+
+ struct preincs {
+ template<typename T>
+ T &
+ operator()(T &x) const {
+ return ++x;
+ }
+ };
+
+ struct predecs {
+ template<typename T>
+ T &
+ operator()(T &x) const {
+ return --x;
+ }
+ };
+
+ template<typename T>
+ class multiplies_by_t {
+ public:
+ multiplies_by_t(T x) : x(x) {
+ }
+
+ template<typename S>
+ typename std::common_type<T, S>::type
+ operator()(S y) const {
+ return x * y;
+ }
+
+ private:
+ T x;
+ };
+
+ template<typename T>
+ multiplies_by_t<T>
+ multiplies_by(T x) {
+ return { x };
+ }
+
+ template<typename T>
+ class preincs_by_t {
+ public:
+ preincs_by_t(T n) : n(n) {
+ }
+
+ template<typename S>
+ S &
+ operator()(S &x) const {
+ return x += n;
+ }
+
+ private:
+ T n;
+ };
+
+ template<typename T>
+ preincs_by_t<T>
+ preincs_by(T n) {
+ return { n };
+ }
+
+ template<typename T>
+ class predecs_by_t {
+ public:
+ predecs_by_t(T n) : n(n) {
+ }
+
+ template<typename S>
+ S &
+ operator()(S &x) const {
+ return x -= n;
+ }
+
+ private:
+ T n;
+ };
+
+ template<typename T>
+ predecs_by_t<T>
+ predecs_by(T n) {
+ return { n };
+ }
+
+ struct greater {
+ template<typename T, typename S>
+ bool
+ operator()(T x, S y) const {
+ return x > y;
+ }
+ };
+
+ struct derefs {
+ template<typename T>
+ auto
+ operator()(T &&x) const -> decltype(*x) {
+ return *x;
+ }
+ };
+
+ struct addresses {
+ template<typename T>
+ T *
+ operator()(T &x) const {
+ return &x;
+ }
+
+ template<typename T>
+ T *
+ operator()(std::reference_wrapper<T> x) const {
+ return &x.get();
+ }
+ };
+
+ struct begins {
+ template<typename T>
+ auto
+ operator()(T &x) const -> decltype(x.begin()) {
+ return x.begin();
+ }
+ };
+
+ struct ends {
+ template<typename T>
+ auto
+ operator()(T &x) const -> decltype(x.end()) {
+ return x.end();
+ }
+ };
+
+ struct sizes {
+ template<typename T>
+ auto
+ operator()(T &x) const -> decltype(x.size()) {
+ return x.size();
+ }
+ };
+
+ template<typename T>
+ class advances_by_t {
+ public:
+ advances_by_t(T n) : n(n) {
+ }
+
+ template<typename S>
+ S
+ operator()(S &&it) const {
+ std::advance(it, n);
+ return it;
+ }
+
+ private:
+ T n;
+ };
+
+ template<typename T>
+ advances_by_t<T>
+ advances_by(T n) {
+ return { n };
+ }
+
+ struct zips {
+ template<typename... Ts>
+ std::tuple<Ts...>
+ operator()(Ts &&... xs) const {
+ return std::tuple<Ts...>(std::forward<Ts>(xs)...);
+ }
+ };
+
+ struct is_zero {
+ template<typename T>
+ bool
+ operator()(const T &x) const {
+ return x == 0;
+ }
+ };
+
+ struct keys {
+ template<typename P>
+ typename std::remove_reference<P>::type::first_type &
+ operator()(P &&p) const {
+ return p.first;
+ }
+ };
+
+ struct values {
+ template<typename P>
+ typename std::remove_reference<P>::type::second_type &
+ operator()(P &&p) const {
+ return p.second;
+ }
+ };
+
+ class name_equals {
+ public:
+ name_equals(const std::string &name) : name(name) {
+ }
+
+ template<typename T>
+ bool
+ operator()(const T &x) const {
+ return std::string(x.name.begin(), x.name.end()) == name;
+ }
+
+ private:
+ const std::string &name;
+ };
+
+ template<typename T>
+ class key_equals_t {
+ public:
+ key_equals_t(T &&x) : x(x) {
+ }
+
+ template<typename S>
+ bool
+ operator()(const std::pair<T, S> &p) const {
+ return p.first == x;
+ }
+
+ private:
+ T x;
+ };
+
+ template<typename T>
+ key_equals_t<T>
+ key_equals(T &&x) {
+ return { std::forward<T>(x) };
+ }
+
+ template<typename T>
+ class type_equals_t {
+ public:
+ type_equals_t(T type) : type(type) {
+ }
+
+ template<typename S>
+ bool
+ operator()(const S &x) const {
+ return x.type == type;
+ }
+
+ private:
+ T type;
+ };
+
+ template<typename T>
+ type_equals_t<T>
+ type_equals(T x) {
+ return { x };
+ }
+
+ struct interval_overlaps {
+ template<typename T>
+ bool
+ operator()(T x0, T x1, T y0, T y1) {
+ return ((x0 <= y0 && y0 < x1) ||
+ (y0 <= x0 && x0 < y1));
+ }
+ };
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/lazy.hpp b/src/gallium/state_trackers/clover/util/lazy.hpp
new file mode 100644
index 00000000000..e32a8f8b1b9
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/lazy.hpp
@@ -0,0 +1,161 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_LAZY_HPP
+#define CLOVER_UTIL_LAZY_HPP
+
+#include <type_traits>
+#include <stdexcept>
+#include <memory>
+
+namespace clover {
+ namespace detail {
+ template<typename T>
+ class basic_lazy {
+ public:
+ virtual
+ ~basic_lazy() {
+ }
+
+ virtual basic_lazy *
+ clone() const = 0;
+
+ virtual
+ operator T() const = 0;
+ };
+
+ template<typename T, typename F>
+ class deferred_lazy : public basic_lazy<T> {
+ public:
+ template<typename G>
+ deferred_lazy(G &&f) : f(new F(std::forward<G>(f))) {
+ }
+
+ virtual basic_lazy<T> *
+ clone() const {
+ return new deferred_lazy(*this);
+ }
+
+ operator T() const {
+ if (f) {
+ x = (*f)();
+ f = {};
+ }
+
+ return x;
+ }
+
+ private:
+ mutable std::shared_ptr<F> f;
+ mutable T x;
+ };
+
+ template<typename T>
+ class strict_lazy : public basic_lazy<T> {
+ public:
+ template<typename S>
+ strict_lazy(S &&x) : x(std::forward<S>(x)) {
+ }
+
+ virtual basic_lazy<T> *
+ clone() const {
+ return new strict_lazy(*this);
+ }
+
+ operator T() const {
+ return x;
+ }
+
+ private:
+ T x;
+ };
+ }
+
+ ///
+ /// Object that represents a value of type \a T that is calculated
+ /// lazily as soon as it is required.
+ ///
+ template<typename T>
+ class lazy {
+ public:
+ class undefined_error : std::logic_error {
+ public:
+ undefined_error() : std::logic_error("") {
+ }
+ };
+
+ ///
+ /// Initialize to some fixed value \a x which isn't calculated
+ /// lazily.
+ ///
+ lazy(T x) : obj(new detail::strict_lazy<T>(x)) {
+ }
+
+ ///
+ /// Initialize by providing a functor \a f that will calculate
+ /// the value on-demand.
+ ///
+ template<typename F>
+ lazy(F &&f) : obj(new detail::deferred_lazy<
+ T, typename std::remove_reference<F>::type
+ >(std::forward<F>(f))) {
+ }
+
+ ///
+ /// Initialize to undefined.
+ ///
+ lazy() : lazy([]() {
+ throw undefined_error();
+ return T();
+ }) {
+ }
+
+ lazy(const lazy &other) : obj(obj->clone()) {
+ }
+
+ lazy(lazy &&other) : obj(NULL) {
+ std::swap(obj, other.obj);
+ }
+
+ ~lazy() {
+ delete obj;
+ }
+
+ lazy &
+ operator=(lazy other) {
+ std::swap(obj, other.obj);
+ return *this;
+ }
+
+ ///
+ /// Evaluate the value.
+ ///
+ operator T() const {
+ return *obj;
+ }
+
+ private:
+ detail::basic_lazy<T> *obj;
+ };
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/pointer.hpp b/src/gallium/state_trackers/clover/util/pointer.hpp
new file mode 100644
index 00000000000..f0c5b1618a5
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/pointer.hpp
@@ -0,0 +1,157 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_POINTER_HPP
+#define CLOVER_UTIL_POINTER_HPP
+
+#include <atomic>
+
+namespace clover {
+ ///
+ /// Base class for objects that support reference counting.
+ ///
+ class ref_counter {
+ public:
+ ref_counter() : _ref_count(1) {}
+
+ unsigned
+ ref_count() {
+ return _ref_count;
+ }
+
+ void
+ retain() {
+ _ref_count++;
+ }
+
+ bool
+ release() {
+ return (--_ref_count) == 0;
+ }
+
+ private:
+ std::atomic<unsigned> _ref_count;
+ };
+
+ ///
+ /// Intrusive smart pointer for objects that implement the
+ /// clover::ref_counter interface.
+ ///
+ template<typename T>
+ class ref_ptr {
+ public:
+ ref_ptr(T *q = NULL) : p(NULL) {
+ reset(q);
+ }
+
+ ref_ptr(const ref_ptr<T> &ref) : p(NULL) {
+ reset(ref.p);
+ }
+
+ ~ref_ptr() {
+ reset(NULL);
+ }
+
+ void
+ reset(T *q = NULL) {
+ if (q)
+ q->retain();
+ if (p && p->release())
+ delete p;
+ p = q;
+ }
+
+ ref_ptr &
+ operator=(const ref_ptr &ref) {
+ reset(ref.p);
+ return *this;
+ }
+
+ T &
+ operator*() const {
+ return *p;
+ }
+
+ T *
+ operator->() const {
+ return p;
+ }
+
+ explicit operator bool() const {
+ return p;
+ }
+
+ private:
+ T *p;
+ };
+
+ ///
+ /// Transfer the caller's ownership of a reference-counted object
+ /// to a clover::ref_ptr smart pointer.
+ ///
+ template<typename T>
+ inline ref_ptr<T>
+ transfer(T *p) {
+ ref_ptr<T> ref { p };
+ p->release();
+ return ref;
+ }
+
+ ///
+ /// Class that implements the usual pointer interface but in fact
+ /// contains the object it seems to be pointing to.
+ ///
+ template<typename T>
+ class pseudo_ptr {
+ public:
+ pseudo_ptr(T x) : x(x) {
+ }
+
+ pseudo_ptr(const pseudo_ptr &p) : x(p.x) {
+ }
+
+ pseudo_ptr &
+ operator=(const pseudo_ptr &p) {
+ x = p.x;
+ return *this;
+ }
+
+ T &
+ operator*() {
+ return x;
+ }
+
+ T *
+ operator->() {
+ return &x;
+ }
+
+ explicit operator bool() const {
+ return true;
+ }
+
+ private:
+ T x;
+ };
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/range.hpp b/src/gallium/state_trackers/clover/util/range.hpp
new file mode 100644
index 00000000000..151992ed8f4
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/range.hpp
@@ -0,0 +1,421 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_RANGE_HPP
+#define CLOVER_UTIL_RANGE_HPP
+
+#include <array>
+#include <vector>
+
+#include "util/adaptor.hpp"
+
+namespace clover {
+ ///
+ /// Class that identifies container types where the elements of a
+ /// range can be stored by the type conversion operator.
+ ///
+ /// \a T identifies the range element type.
+ ///
+ template<typename T, typename V>
+ struct range_store_traits;
+
+ template<typename T>
+ struct range_store_traits<T, std::vector<T>> {
+ typedef void enable;
+
+ template<typename R>
+ static std::vector<T>
+ create(const R &r) {
+ return { r.begin(), r.end() };
+ }
+ };
+
+ template<typename T, std::size_t N>
+ struct range_store_traits<T, std::array<T, N>> {
+ typedef void enable;
+
+ template<typename R>
+ static std::array<T, N>
+ create(const R &r) {
+ std::array<T, N> v;
+ assert(r.size() == v.size());
+ copy(r, v.begin());
+ return v;
+ }
+ };
+
+ namespace detail {
+ ///
+ /// Common functionality that is shared by other implementations
+ /// of the container concept.
+ ///
+ template<typename R, typename I, typename CI>
+ class basic_range {
+ public:
+ typedef I iterator;
+ typedef CI const_iterator;
+ typedef typename std::iterator_traits<iterator>::value_type value_type;
+ typedef typename std::iterator_traits<iterator>::reference
+ reference;
+ typedef typename std::iterator_traits<const_iterator>::reference
+ const_reference;
+ typedef typename std::iterator_traits<iterator>::difference_type
+ difference_type;
+ typedef std::size_t size_type;
+
+ bool
+ operator==(const basic_range &r) const {
+ return *static_cast<const R *>(this) == r;
+ }
+
+ bool
+ operator!=(const basic_range &r) const {
+ return !(*this == r);
+ }
+
+ iterator
+ begin() {
+ return static_cast<R *>(this)->begin();
+ }
+
+ iterator
+ end() {
+ return static_cast<R *>(this)->end();
+ }
+
+ const_iterator
+ begin() const {
+ return static_cast<const R *>(this)->begin();
+ }
+
+ const_iterator
+ end() const {
+ return static_cast<const R *>(this)->end();
+ }
+
+ std::reverse_iterator<iterator>
+ rbegin() {
+ return { begin() };
+ }
+
+ std::reverse_iterator<iterator>
+ rend() {
+ return { end() };
+ }
+
+ reference
+ front() {
+ return *begin();
+ }
+
+ reference
+ back() {
+ return *(end() - 1);
+ }
+
+ bool
+ empty() const {
+ return begin() == end();
+ }
+
+ reference
+ at(size_type i) {
+ if (i >= static_cast<const R *>(this)->size())
+ throw std::out_of_range("");
+
+ return begin()[i];
+ }
+
+ const_reference
+ at(size_type i) const {
+ if (i >= static_cast<const R *>(this)->size())
+ throw std::out_of_range("");
+
+ return begin()[i];
+ }
+
+ reference
+ operator[](size_type i) {
+ return begin()[i];
+ }
+
+ const_reference
+ operator[](size_type i) const {
+ return begin()[i];
+ }
+
+ template<typename V>
+ using store_traits = range_store_traits<
+ typename std::remove_cv<value_type>::type, V
+ >;
+
+ template<typename V,
+ typename = typename store_traits<V>::enable>
+ operator V() const {
+ return store_traits<V>::create(*static_cast<const R *>(this));
+ }
+ };
+ }
+
+ ///
+ /// Range that contains all elements delimited by an iterator pair
+ /// (\a i, \a j). Use range() as convenience constructor.
+ ///
+ template<typename I>
+ class iterator_range : public detail::basic_range<iterator_range<I>, I, I> {
+ public:
+ typedef detail::basic_range<iterator_range<I>, I, I> super;
+
+ iterator_range() : i(), j() {
+ }
+
+ iterator_range(I i, I j) : i(i), j(j) {
+ }
+
+ bool
+ operator==(const iterator_range &r) const {
+ return i == r.i && j == r.j;
+ }
+
+ I
+ begin() const {
+ return i;
+ }
+
+ I
+ end() const {
+ return j;
+ }
+
+ typename super::size_type
+ size() const {
+ return end() - begin();
+ }
+
+ private:
+ I i, j;
+ };
+
+ namespace detail {
+ template<typename T>
+ using preferred_iterator_type = decltype(std::declval<T>().begin());
+
+ template<typename F, typename... Os>
+ using adaptor_iterator = detail::iterator_adaptor<
+ F, preferred_iterator_type<Os>...>;
+
+ template<typename F, typename... Os>
+ using adaptor_const_iterator = detail::iterator_adaptor<
+ F, preferred_iterator_type<const Os>...>;
+ }
+
+ ///
+ /// Range that transforms the contents of a number of source ranges
+ /// \a os element-wise by using the provided functor \a f. Use
+ /// map() as convenience constructor.
+ ///
+ template<typename F, typename... Os>
+ class adaptor_range :
+ public detail::basic_range<adaptor_range<F, Os...>,
+ detail::adaptor_iterator<F, Os...>,
+ detail::adaptor_const_iterator<F, Os...>> {
+ public:
+ typedef detail::basic_range<adaptor_range<F, Os...>,
+ detail::adaptor_iterator<F, Os...>,
+ detail::adaptor_const_iterator<F, Os...>
+ > super;
+
+ template<typename G, typename... Rs>
+ adaptor_range(G &&f, Rs &&... os) :
+ f(std::forward<G>(f)), os(std::forward<Rs>(os)...) {
+ }
+
+ bool
+ operator==(const adaptor_range &r) const {
+ return f == r.f && os == r.os;
+ }
+
+ detail::adaptor_iterator<F, Os...>
+ begin() {
+ return { f, tuple::map(begins(), os) };
+ }
+
+ detail::adaptor_iterator<F, Os...>
+ end() {
+ return { f, tuple::map(advances_by(size()),
+ tuple::map(begins(), os)) };
+ }
+
+ detail::adaptor_const_iterator<F, Os...>
+ begin() const {
+ return { f, tuple::map(begins(), os) };
+ }
+
+ detail::adaptor_const_iterator<F, Os...>
+ end() const {
+ return { f, tuple::map(ends(), os) };
+ }
+
+ typename super::size_type
+ size() const {
+ return tuple::apply(minimum(), tuple::map(sizes(), os));
+ }
+
+ private:
+ F f;
+ std::tuple<Os...> os;
+ };
+
+ ///
+ /// Range that contains all elements delimited by the index pair
+ /// (\a i, \a j) in the source range \a r. Use slice() as
+ /// convenience constructor.
+ ///
+ template<typename O>
+ class slice_range :
+ public detail::basic_range<slice_range<O>,
+ detail::preferred_iterator_type<O>,
+ detail::preferred_iterator_type<const O>> {
+ public:
+ typedef detail::basic_range<slice_range<O>,
+ detail::preferred_iterator_type<O>,
+ detail::preferred_iterator_type<const O>
+ > super;
+
+ template<typename R>
+ slice_range(R &&r, typename super::size_type i,
+ typename super::size_type j) :
+ o(std::forward<R>(r)), i(i), j(j) {
+ }
+
+ bool
+ operator==(const slice_range &r) const {
+ return o == r.o && i == r.i && j == r.j;
+ }
+
+ typename super::iterator
+ begin() {
+ return std::next(o.begin(), i);
+ }
+
+ typename super::iterator
+ end() {
+ return std::next(o.begin(), j);
+ }
+
+ typename super::const_iterator
+ begin() const {
+ return std::next(o.begin(), i);
+ }
+
+ typename super::const_iterator
+ end() const {
+ return std::next(o.begin(), j);
+ }
+
+ typename super::size_type
+ size() const {
+ return j - i;
+ }
+
+ private:
+ O o;
+ typename super::size_type i, j;
+ };
+
+ ///
+ /// Create a range from an iterator pair (\a i, \a j).
+ ///
+ /// \sa iterator_range.
+ ///
+ template<typename T>
+ iterator_range<T>
+ range(T i, T j) {
+ return { i, j };
+ }
+
+ ///
+ /// Create a range of \a n elements starting from iterator \a i.
+ ///
+ /// \sa iterator_range.
+ ///
+ template<typename T>
+ iterator_range<T>
+ range(T i, typename std::iterator_traits<T>::difference_type n) {
+ return { i, i + n };
+ }
+
+ ///
+ /// Create a range by transforming the contents of a number of
+ /// source ranges \a rs element-wise using a provided functor \a f.
+ ///
+ /// \sa adaptor_range.
+ ///
+ template<typename F, typename... Rs>
+ adaptor_range<F, Rs...>
+ map(F &&f, Rs &&... rs) {
+ return { std::forward<F>(f), std::forward<Rs>(rs)... };
+ }
+
+ ///
+ /// Create a range identical to another range \a r.
+ ///
+ template<typename R>
+ adaptor_range<identity, R>
+ range(R &&r) {
+ return { identity(), std::forward<R>(r) };
+ }
+
+ ///
+ /// Create a range by taking the elements delimited by the index
+ /// pair (\a i, \a j) in a source range \a r.
+ ///
+ /// \sa slice_range.
+ ///
+ template<typename R>
+ slice_range<R>
+ slice(R &&r, typename slice_range<R>::size_type i,
+ typename slice_range<R>::size_type j) {
+ return { std::forward<R>(r), i, j };
+ }
+
+ ///
+ /// Range that behaves as a vector of references of type \a T.
+ ///
+ /// Useful because STL containers cannot contain references to
+ /// objects as elements.
+ ///
+ template<typename T>
+ class ref_vector : public adaptor_range<derefs, std::vector<T *>> {
+ public:
+ ref_vector(std::initializer_list<std::reference_wrapper<T>> il) :
+ adaptor_range<derefs, std::vector<T *>>(derefs(), map(addresses(), il)) {
+ }
+
+ template<typename R>
+ ref_vector(R &&r) : adaptor_range<derefs, std::vector<T *>>(
+ derefs(), map(addresses(), std::forward<R>(r))) {
+ }
+ };
+}
+
+#endif
diff --git a/src/gallium/state_trackers/clover/util/tuple.hpp b/src/gallium/state_trackers/clover/util/tuple.hpp
new file mode 100644
index 00000000000..bd49684a314
--- /dev/null
+++ b/src/gallium/state_trackers/clover/util/tuple.hpp
@@ -0,0 +1,117 @@
+//
+// Copyright 2013 Francisco Jerez
+//
+// Permission is hereby granted, free of charge, to any person obtaining a
+// copy of this software and associated documentation files (the "Software"),
+// to deal in the Software without restriction, including without limitation
+// the rights to use, copy, modify, merge, publish, distribute, sublicense,
+// and/or sell copies of the Software, and to permit persons to whom the
+// Software is furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#ifndef CLOVER_UTIL_TUPLE_HPP
+#define CLOVER_UTIL_TUPLE_HPP
+
+#include <tuple>
+
+namespace clover {
+ namespace tuple {
+ ///
+ /// Static sequence of integers.
+ ///
+ template<int... Is>
+ struct integral_sequence;
+
+ ///
+ /// Static sequence containing all integers from 0 to N-1.
+ ///
+ template<int N, int... Is>
+ struct enumerate {
+ typedef typename enumerate<N-1, N-1, Is...>::type
+ type;
+ };
+
+ template<int... Is>
+ struct enumerate<0, Is...> {
+ typedef integral_sequence<Is...> type;
+ };
+
+ namespace detail {
+ template<typename F, typename T,
+ typename E = typename enumerate<std::tuple_size<
+ typename std::remove_reference<T>::type>::value
+ >::type>
+ struct _apply;
+
+ template<typename F, typename T, int... Is>
+ struct _apply<F, T, integral_sequence<Is...>> {
+ typedef typename std::remove_reference<F>::type func_type;
+ typedef decltype(
+ std::declval<func_type>()(std::get<Is>(std::declval<T &&>())...)
+ ) value_type;
+
+ static value_type
+ eval(F &&f, T &&t) {
+ return f(std::get<Is>(std::forward<T>(t))...);
+ }
+ };
+ }
+
+ ///
+ /// Evaluate function \a f with the elements of tuple \a t
+ /// expanded as arguments.
+ ///
+ template<typename F, typename T>
+ typename detail::_apply<F, T>::value_type
+ apply(F &&f, T &&t) {
+ return detail::_apply<F, T>::eval(std::forward<F>(f),
+ std::forward<T>(t));
+ }
+
+ namespace detail {
+ template<typename F, typename T,
+ typename E = typename enumerate<std::tuple_size<
+ typename std::remove_reference<T>::type>::value
+ >::type>
+ struct _map;
+
+ template<typename F, typename T, int... Is>
+ struct _map<F, T, integral_sequence<Is...>> {
+ typedef typename std::remove_reference<F>::type func_type;
+ typedef std::tuple<
+ decltype(std::declval<func_type>()(
+ std::get<Is>(std::declval<T &&>())))...
+ > value_type;
+
+ static value_type
+ eval(F &&f, T &&t) {
+ return value_type(f(std::get<Is>(std::forward<T>(t)))...);
+ }
+ };
+ }
+
+ ///
+ /// Evaluate function \a f on each element of the tuple \a t and
+ /// return the resulting values as a new tuple.
+ ///
+ template<typename F, typename T>
+ typename detail::_map<F, T>::value_type
+ map(F &&f, T &&t) {
+ return detail::_map<F, T>::eval(std::forward<F>(f),
+ std::forward<T>(t));
+ }
+ }
+}
+
+#endif