clover: Import new utility library.

Tested-by: Tom Stellard <[email protected]>

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