xwininfo fontconfig libX11 libXdmcp libfontenc libxcb libxcb/xcb-proto mesalib xserver xkeyboard-config mkfontscale git update 22 Feb 2015

xserver          commit 3a06faf3fcdb7451125a46181f9152e8e59e9770
libxcb           commit e3ec1f74637237ce500dfd0ca59f2e422da4e019
libxcb/xcb-proto commit 4c550465934164aab2449a125f75f4ca07816233
xkeyboard-config commit 26f344c93f8c6141e9233eb68088ba4fd56bc9ef
libX11           commit c8e19b393defd53f046ddc2da3a16881221b3c34
libXdmcp         commit 9f4cac7656b221ce2a8f97e7bd31e5e23126d001
libfontenc       commit de1843aaf76015c9d99416f3122d169fe331b849
mkfontscale      commit 87d628f8eec170ec13bb9feefb1ce05aed07d1d6
xwininfo         commit 0c49f8f2bd56b1e77721e81030ea948386dcdf4e
fontconfig       commit d6d5adeb7940c0d0beb86489c2a1c2ce59e5c044
mesa             commit 4359954d842caa2a9f8d4b50d70ecc789884b68b

15 files changed, 1359 insertions, 53 deletions

diff --git a/mesalib/src/util/Makefile.am b/mesalib/src/util/Makefile.am
index c7e183e8d..9af233059 100644
--- a/mesalib/src/util/Makefile.am
+++ b/mesalib/src/util/Makefile.am
@@ -31,12 +31,21 @@ libmesautil_la_CPPFLAGS = \
 	-I$(top_srcdir)/src \
 	-I$(top_srcdir)/src/mapi \
 	-I$(top_srcdir)/src/mesa \
+	-I$(top_srcdir)/src/gallium/include \
+	-I$(top_srcdir)/src/gallium/auxiliary \
+	$(SHA1_CFLAGS) \
 	$(VISIBILITY_CFLAGS)
 
 libmesautil_la_SOURCES = \
 	$(MESA_UTIL_FILES) \
 	$(MESA_UTIL_GENERATED_FILES)
 
+if ENABLE_SHADER_CACHE
+libmesautil_la_SOURCES += $(MESA_UTIL_SHADER_CACHE_FILES)
+endif
+
+libmesautil_la_LIBADD = $(SHA1_LIBS)
+
 check_PROGRAMS = u_atomic_test
 TESTS = $(check_PROGRAMS)
 
diff --git a/mesalib/src/util/Makefile.sources b/mesalib/src/util/Makefile.sources
index 5f87fc32a..560ea836a 100644
--- a/mesalib/src/util/Makefile.sources
+++ b/mesalib/src/util/Makefile.sources
@@ -1,4 +1,9 @@
+MESA_UTIL_SHADER_CACHE_FILES := \
+	mesa-sha1.c \
+	mesa-sha1.h
+
 MESA_UTIL_FILES :=	\
+	bitset.h \
 	format_srgb.h \
 	hash_table.c	\
 	hash_table.h \
@@ -9,6 +14,9 @@ MESA_UTIL_FILES :=	\
 	register_allocate.h \
 	rgtc.c \
 	rgtc.h \
+	set.c \
+	set.h \
+	simple_list.h \
 	strtod.cpp \
 	strtod.h \
 	texcompress_rgtc_tmp.h \
diff --git a/mesalib/src/util/SConscript b/mesalib/src/util/SConscript
index 34b9a2dea..84bd7a1e1 100644
--- a/mesalib/src/util/SConscript
+++ b/mesalib/src/util/SConscript
@@ -11,6 +11,8 @@ env.Prepend(CPPPATH = [
     '#src',
     '#src/mapi',
     '#src/mesa',
+    '#src/gallium/include',
+    '#src/gallium/auxiliary',
     '#src/util',
 ])
 
@@ -29,6 +31,11 @@ mesautil_sources = (
     source_lists['MESA_UTIL_GENERATED_FILES']
 )
 
+# XXX We don't yet have scons support for detecting any of the various
+# HAVE_SHA1_* definitions, so for now simply disable the shader cache.
+if False:
+    mesautil_sources += source_lists['MESA_UTIL_SHADER_CACHE_FILES']
+
 mesautil = env.ConvenienceLibrary(
     target = 'mesautil',
     source = mesautil_sources,
diff --git a/mesalib/src/util/bitset.h b/mesalib/src/util/bitset.h
new file mode 100644
index 000000000..17c5d5d25
--- /dev/null
+++ b/mesalib/src/util/bitset.h
@@ -0,0 +1,99 @@
+/*
+ * Mesa 3-D graphics library
+ *
+ * Copyright (C) 2006  Brian Paul   All Rights Reserved.
+ *
+ * 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.
+ */
+
+/**
+ * \file bitset.h
+ * \brief Bitset of arbitrary size definitions.
+ * \author Michal Krol
+ */
+
+#ifndef BITSET_H
+#define BITSET_H
+
+#include "util/u_math.h"
+
+/****************************************************************************
+ * generic bitset implementation
+ */
+
+#define BITSET_WORD unsigned int
+#define BITSET_WORDBITS (sizeof (BITSET_WORD) * 8)
+
+/* bitset declarations
+ */
+#define BITSET_WORDS(bits) (((bits) + BITSET_WORDBITS - 1) / BITSET_WORDBITS)
+#define BITSET_DECLARE(name, bits) BITSET_WORD name[BITSET_WORDS(bits)]
+
+/* bitset operations
+ */
+#define BITSET_COPY(x, y) memcpy( (x), (y), sizeof (x) )
+#define BITSET_EQUAL(x, y) (memcmp( (x), (y), sizeof (x) ) == 0)
+#define BITSET_ZERO(x) memset( (x), 0, sizeof (x) )
+#define BITSET_ONES(x) memset( (x), 0xff, sizeof (x) )
+
+#define BITSET_BITWORD(b) ((b) / BITSET_WORDBITS)
+#define BITSET_BIT(b) (1 << ((b) % BITSET_WORDBITS))
+
+/* single bit operations
+ */
+#define BITSET_TEST(x, b) ((x)[BITSET_BITWORD(b)] & BITSET_BIT(b))
+#define BITSET_SET(x, b) ((x)[BITSET_BITWORD(b)] |= BITSET_BIT(b))
+#define BITSET_CLEAR(x, b) ((x)[BITSET_BITWORD(b)] &= ~BITSET_BIT(b))
+
+#define BITSET_MASK(b) ((b) == BITSET_WORDBITS ? ~0 : BITSET_BIT(b) - 1)
+#define BITSET_RANGE(b, e) (BITSET_MASK((e) + 1) & ~BITSET_MASK(b))
+
+/* bit range operations
+ */
+#define BITSET_TEST_RANGE(x, b, e) \
+   (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
+   ((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) : \
+   (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0))
+#define BITSET_SET_RANGE(x, b, e) \
+   (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
+   ((x)[BITSET_BITWORD(b)] |= BITSET_RANGE(b, e)) : \
+   (assert (!"BITSET_SET_RANGE: bit range crosses word boundary"), 0))
+#define BITSET_CLEAR_RANGE(x, b, e) \
+   (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
+   ((x)[BITSET_BITWORD(b)] &= ~BITSET_RANGE(b, e)) : \
+   (assert (!"BITSET_CLEAR_RANGE: bit range crosses word boundary"), 0))
+
+/* Get first bit set in a bitset.
+ */
+static inline int
+__bitset_ffs(const BITSET_WORD *x, int n)
+{
+   int i;
+
+   for (i = 0; i < n; i++) {
+      if (x[i])
+	 return ffs(x[i]) + BITSET_WORDBITS * i;
+   }
+
+   return 0;
+}
+
+#define BITSET_FFS(x) __bitset_ffs(x, Elements(x))
+
+#endif
diff --git a/mesalib/src/util/hash_table.c b/mesalib/src/util/hash_table.c
index 0ad038377..3247593c1 100644
--- a/mesalib/src/util/hash_table.c
+++ b/mesalib/src/util/hash_table.c
@@ -232,7 +232,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
                   const void *key, void *data);
 
 static void
-_mesa_hash_table_rehash(struct hash_table *ht, int new_size_index)
+_mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
 {
    struct hash_table old_ht;
    struct hash_entry *table, *entry;
@@ -267,6 +267,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
                   const void *key, void *data)
 {
    uint32_t start_hash_address, hash_address;
+   struct hash_entry *available_entry = NULL;
 
    if (ht->entries >= ht->max_entries) {
       _mesa_hash_table_rehash(ht, ht->size_index + 1);
@@ -281,13 +282,11 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
       uint32_t double_hash;
 
       if (!entry_is_present(ht, entry)) {
-         if (entry_is_deleted(ht, entry))
-            ht->deleted_entries--;
-         entry->hash = hash;
-         entry->key = key;
-         entry->data = data;
-         ht->entries++;
-         return entry;
+         /* Stash the first available entry we find */
+         if (available_entry == NULL)
+            available_entry = entry;
+         if (entry_is_free(entry))
+            break;
       }
 
       /* Implement replacement when another insert happens
@@ -314,6 +313,16 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
       hash_address = (hash_address + double_hash) % ht->size;
    } while (hash_address != start_hash_address);
 
+   if (available_entry) {
+      if (entry_is_deleted(ht, available_entry))
+         ht->deleted_entries--;
+      available_entry->hash = hash;
+      available_entry->key = key;
+      available_entry->data = data;
+      ht->entries++;
+      return available_entry;
+   }
+
    /* We could hit here if a required resize failed. An unchecked-malloc
     * application could ignore this result.
     */
@@ -334,8 +343,8 @@ _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
 }
 
 struct hash_entry *
-_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash,
-                                  const void *key, void *data)
+_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
+                                   const void *key, void *data)
 {
    assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
    return hash_table_insert(ht, hash, key, data);
@@ -431,27 +440,18 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
 uint32_t
 _mesa_hash_data(const void *data, size_t size)
 {
-   uint32_t hash = 2166136261ul;
-   const uint8_t *bytes = data;
-
-   while (size-- != 0) {
-      hash ^= *bytes;
-      hash = hash * 0x01000193;
-      bytes++;
-   }
-
-   return hash;
+   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
+                                          data, size);
 }
 
 /** FNV-1a string hash implementation */
 uint32_t
 _mesa_hash_string(const char *key)
 {
-   uint32_t hash = 2166136261ul;
+   uint32_t hash = _mesa_fnv32_1a_offset_bias;
 
    while (*key != 0) {
-      hash ^= *key;
-      hash = hash * 0x01000193;
+      hash = _mesa_fnv32_1a_accumulate(hash, *key);
       key++;
    }
 
diff --git a/mesalib/src/util/hash_table.h b/mesalib/src/util/hash_table.h
index 5561e1584..eb9dbc333 100644
--- a/mesalib/src/util/hash_table.h
+++ b/mesalib/src/util/hash_table.h
@@ -70,8 +70,8 @@ void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
 struct hash_entry *
 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
 struct hash_entry *
-_mesa_hash_table_insert_with_hash(struct hash_table *ht, uint32_t hash,
-                                  const void *key, void *data);
+_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
+                                   const void *key, void *data);
 struct hash_entry *
 _mesa_hash_table_search(struct hash_table *ht, const void *key);
 struct hash_entry *
@@ -101,6 +101,25 @@ static inline uint32_t _mesa_hash_pointer(const void *pointer)
    return _mesa_hash_data(&pointer, sizeof(pointer));
 }
 
+static const uint32_t _mesa_fnv32_1a_offset_bias = 2166136261u;
+
+static inline uint32_t
+_mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
+{
+   const uint8_t *bytes = (const uint8_t *)data;
+
+   while (size-- != 0) {
+      hash ^= *bytes;
+      hash = hash * 0x01000193;
+      bytes++;
+   }
+
+   return hash;
+}
+
+#define _mesa_fnv32_1a_accumulate(hash, expr) \
+   _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr))
+
 /**
  * This foreach function is safe against deletion (which just replaces
  * an entry's data with the deleted marker), but not against insertion
diff --git a/mesalib/src/util/macros.h b/mesalib/src/util/macros.h
index 5fc672953..eec8b9352 100644
--- a/mesalib/src/util/macros.h
+++ b/mesalib/src/util/macros.h
@@ -82,7 +82,7 @@ do {                        \
 #endif
 
 #ifndef unreachable
-#define unreachable(str)
+#define unreachable(str) assert(!str)
 #endif
 
 /**
diff --git a/mesalib/src/util/mesa-sha1.c b/mesalib/src/util/mesa-sha1.c
new file mode 100644
index 000000000..fa2819377
--- /dev/null
+++ b/mesalib/src/util/mesa-sha1.c
@@ -0,0 +1,316 @@
+/* Copyright © 2007 Carl Worth
+ * Copyright © 2009 Jeremy Huddleston, Julien Cristau, and Matthieu Herrb
+ * Copyright © 2009-2010 Mikhail Gusarov
+ * Copyright © 2012 Yaakov Selkowitz and Keith Packard
+ * Copyright © 2014 Intel Corporation
+ *
+ * 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 (including the next
+ * paragraph) 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 "mesa-sha1.h"
+
+#if defined(HAVE_SHA1_IN_LIBMD)  /* Use libmd for SHA1 */ \
+	|| defined(HAVE_SHA1_IN_LIBC)   /* Use libc for SHA1 */
+
+#include <sha1.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   SHA1_CTX *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+
+   SHA1Init(ctx);
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   SHA1_CTX *sha1_ctx = (SHA1_CTX *) ctx;
+
+   SHA1Update(sha1_ctx, data, size);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   SHA1_CTX *sha1_ctx = (SHA1_CTX *) ctx;
+
+   SHA1Final(result, sha1_ctx);
+   free(sha1_ctx);
+   return 1;
+}
+
+#elif defined(HAVE_SHA1_IN_COMMONCRYPTO)        /* Use CommonCrypto for SHA1 */
+
+#include <CommonCrypto/CommonDigest.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   CC_SHA1_CTX *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+
+   CC_SHA1_Init(ctx);
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   CC_SHA1_CTX *sha1_ctx = (CC_SHA1_CTX *) ctx;
+
+   CC_SHA1_Update(sha1_ctx, data, size);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   CC_SHA1_CTX *sha1_ctx = (CC_SHA1_CTX *) ctx;
+
+   CC_SHA1_Final(result, sha1_ctx);
+   free(sha1_ctx);
+   return 1;
+}
+
+#elif defined(HAVE_SHA1_IN_CRYPTOAPI)        /* Use CryptoAPI for SHA1 */
+
+#define WIN32_LEAN_AND_MEAN
+#include <windows.h>
+#include <wincrypt.h>
+
+static HCRYPTPROV hProv;
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   HCRYPTHASH *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+
+   CryptAcquireContext(&hProv, NULL, MS_DEF_PROV, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
+   CryptCreateHash(hProv, CALG_SHA1, 0, 0, ctx);
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   HCRYPTHASH *hHash = (HCRYPTHASH *) ctx;
+
+   CryptHashData(*hHash, data, size, 0);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   HCRYPTHASH *hHash = (HCRYPTHASH *) ctx;
+   DWORD len = 20;
+
+   CryptGetHashParam(*hHash, HP_HASHVAL, result, &len, 0);
+   CryptDestroyHash(*hHash);
+   CryptReleaseContext(hProv, 0);
+   free(ctx);
+   return 1;
+}
+
+#elif defined(HAVE_SHA1_IN_LIBNETTLE)   /* Use libnettle for SHA1 */
+
+#include <nettle/sha.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   struct sha1_ctx *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+   sha1_init(ctx);
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   sha1_update((struct sha1_ctx *) ctx, size, data);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   sha1_digest((struct sha1_ctx *) ctx, 20, result);
+   free(ctx);
+   return 1;
+}
+
+#elif defined(HAVE_SHA1_IN_LIBGCRYPT)   /* Use libgcrypt for SHA1 */
+
+#include <gcrypt.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   static int init;
+   gcry_md_hd_t h;
+   gcry_error_t err;
+
+   if (!init) {
+      if (!gcry_check_version(NULL))
+         return NULL;
+      gcry_control(GCRYCTL_DISABLE_SECMEM, 0);
+      gcry_control(GCRYCTL_INITIALIZATION_FINISHED, 0);
+      init = 1;
+   }
+
+   err = gcry_md_open(&h, GCRY_MD_SHA1, 0);
+   if (err)
+      return NULL;
+   return (struct mesa_sha1 *) h;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   gcry_md_hd_t h = (gcry_md_hd_t) ctx;
+
+   gcry_md_write(h, data, size);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   gcry_md_hd_t h = (gcry_md_hd_t) ctx;
+
+   memcpy(result, gcry_md_read(h, GCRY_MD_SHA1), 20);
+   gcry_md_close(h);
+   return 1;
+}
+
+#elif defined(HAVE_SHA1_IN_LIBSHA1)     /* Use libsha1 */
+
+#include <libsha1.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   sha1_ctx *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+   sha1_begin(ctx);
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   sha1_hash(data, size, (sha1_ctx *) ctx);
+   return 1;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   sha1_end(result, (sha1_ctx *) ctx);
+   free(ctx);
+   return 1;
+}
+
+#else                           /* Use OpenSSL's libcrypto */
+
+#include <stddef.h>             /* buggy openssl/sha.h wants size_t */
+#include <openssl/sha.h>
+
+struct mesa_sha1 *
+_mesa_sha1_init(void)
+{
+   int ret;
+   SHA_CTX *ctx = malloc(sizeof(*ctx));
+
+   if (!ctx)
+      return NULL;
+   ret = SHA1_Init(ctx);
+   if (!ret) {
+      free(ctx);
+      return NULL;
+   }
+   return (struct mesa_sha1 *) ctx;
+}
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size)
+{
+   int ret;
+   SHA_CTX *sha_ctx = (SHA_CTX *) ctx;
+
+   ret = SHA1_Update(sha_ctx, data, size);
+   if (!ret)
+      free(sha_ctx);
+   return ret;
+}
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20])
+{
+   int ret;
+   SHA_CTX *sha_ctx = (SHA_CTX *) ctx;
+
+   ret = SHA1_Final(result, (SHA_CTX *) sha_ctx);
+   free(sha_ctx);
+   return ret;
+}
+
+#endif
+
+void
+_mesa_sha1_compute(const void *data, size_t size, unsigned char result[20])
+{
+   struct mesa_sha1 *ctx;
+
+   ctx = _mesa_sha1_init();
+   _mesa_sha1_update(ctx, data, size);
+   _mesa_sha1_final(ctx, result);
+}
+
+char *
+_mesa_sha1_format(char *buf, const unsigned char *sha1)
+{
+   static const char hex_digits[] = "0123456789abcdef";
+   int i;
+
+   for (i = 0; i < 40; i += 2) {
+      buf[i] = hex_digits[sha1[i >> 1] >> 4];
+      buf[i + 1] = hex_digits[sha1[i >> 1] & 0x0f];
+   }
+   buf[i] = '\0';
+
+   return buf;
+}
diff --git a/mesalib/src/util/mesa-sha1.h b/mesalib/src/util/mesa-sha1.h
new file mode 100644
index 000000000..1599405cd
--- /dev/null
+++ b/mesalib/src/util/mesa-sha1.h
@@ -0,0 +1,53 @@
+/* Copyright © 2014 Intel Corporation
+ *
+ * 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 (including the next
+ * paragraph) 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 SHA1_H
+#define SHA1_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdlib.h>
+
+struct mesa_sha1;
+
+struct mesa_sha1 *
+_mesa_sha1_init(void);
+
+int
+_mesa_sha1_update(struct mesa_sha1 *ctx, const void *data, int size);
+
+int
+_mesa_sha1_final(struct mesa_sha1 *ctx, unsigned char result[20]);
+
+char *
+_mesa_sha1_format(char *buf, const unsigned char *sha1);
+
+void
+_mesa_sha1_compute(const void *data, size_t size, unsigned char result[20]);
+
+#ifdef __cplusplus
+} /* extern C */
+#endif
+
+#endif
diff --git a/mesalib/src/util/register_allocate.c b/mesalib/src/util/register_allocate.c
index af7a20c09..684ee5d6c 100644
--- a/mesalib/src/util/register_allocate.c
+++ b/mesalib/src/util/register_allocate.c
@@ -76,7 +76,7 @@
 #include "main/imports.h"
 #include "main/macros.h"
 #include "main/mtypes.h"
-#include "main/bitset.h"
+#include "util/bitset.h"
 #include "register_allocate.h"
 
 #define NO_REG ~0U
diff --git a/mesalib/src/util/set.c b/mesalib/src/util/set.c
new file mode 100644
index 000000000..f01f8699a
--- /dev/null
+++ b/mesalib/src/util/set.c
@@ -0,0 +1,391 @@
+/*
+ * Copyright © 2009-2012 Intel Corporation
+ * Copyright © 1988-2004 Keith Packard and Bart Massey.
+ *
+ * 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 (including the next
+ * paragraph) 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.
+ *
+ * Except as contained in this notice, the names of the authors
+ * or their institutions shall not be used in advertising or
+ * otherwise to promote the sale, use or other dealings in this
+ * Software without prior written authorization from the
+ * authors.
+ *
+ * Authors:
+ *    Eric Anholt <eric@anholt.net>
+ *    Keith Packard <keithp@keithp.com>
+ */
+
+#include <stdlib.h>
+#include <assert.h>
+
+#include "macros.h"
+#include "ralloc.h"
+#include "set.h"
+
+/*
+ * From Knuth -- a good choice for hash/rehash values is p, p-2 where
+ * p and p-2 are both prime.  These tables are sized to have an extra 10%
+ * free to avoid exponential performance degradation as the hash table fills
+ */
+
+uint32_t deleted_key_value;
+const void *deleted_key = &deleted_key_value;
+
+static const struct {
+   uint32_t max_entries, size, rehash;
+} hash_sizes[] = {
+   { 2,            5,            3            },
+   { 4,            7,            5            },
+   { 8,            13,           11           },
+   { 16,           19,           17           },
+   { 32,           43,           41           },
+   { 64,           73,           71           },
+   { 128,          151,          149          },
+   { 256,          283,          281          },
+   { 512,          571,          569          },
+   { 1024,         1153,         1151         },
+   { 2048,         2269,         2267         },
+   { 4096,         4519,         4517         },
+   { 8192,         9013,         9011         },
+   { 16384,        18043,        18041        },
+   { 32768,        36109,        36107        },
+   { 65536,        72091,        72089        },
+   { 131072,       144409,       144407       },
+   { 262144,       288361,       288359       },
+   { 524288,       576883,       576881       },
+   { 1048576,      1153459,      1153457      },
+   { 2097152,      2307163,      2307161      },
+   { 4194304,      4613893,      4613891      },
+   { 8388608,      9227641,      9227639      },
+   { 16777216,     18455029,     18455027     },
+   { 33554432,     36911011,     36911009     },
+   { 67108864,     73819861,     73819859     },
+   { 134217728,    147639589,    147639587    },
+   { 268435456,    295279081,    295279079    },
+   { 536870912,    590559793,    590559791    },
+   { 1073741824,   1181116273,   1181116271   },
+   { 2147483648ul, 2362232233ul, 2362232231ul }
+};
+
+static int
+entry_is_free(struct set_entry *entry)
+{
+   return entry->key == NULL;
+}
+
+static int
+entry_is_deleted(struct set_entry *entry)
+{
+   return entry->key == deleted_key;
+}
+
+static int
+entry_is_present(struct set_entry *entry)
+{
+   return entry->key != NULL && entry->key != deleted_key;
+}
+
+struct set *
+_mesa_set_create(void *mem_ctx,
+                 uint32_t (*key_hash_function)(const void *key),
+                 bool (*key_equals_function)(const void *a,
+                                             const void *b))
+{
+   struct set *ht;
+
+   ht = ralloc(mem_ctx, struct set);
+   if (ht == NULL)
+      return NULL;
+
+   ht->size_index = 0;
+   ht->size = hash_sizes[ht->size_index].size;
+   ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->max_entries = hash_sizes[ht->size_index].max_entries;
+   ht->key_hash_function = key_hash_function;
+   ht->key_equals_function = key_equals_function;
+   ht->table = rzalloc_array(ht, struct set_entry, ht->size);
+   ht->entries = 0;
+   ht->deleted_entries = 0;
+
+   if (ht->table == NULL) {
+      ralloc_free(ht);
+      return NULL;
+   }
+
+   return ht;
+}
+
+/**
+ * Frees the given set.
+ *
+ * If delete_function is passed, it gets called on each entry present before
+ * freeing.
+ */
+void
+_mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
+{
+   if (!ht)
+      return;
+
+   if (delete_function) {
+      struct set_entry *entry;
+
+      set_foreach (ht, entry) {
+         delete_function(entry);
+      }
+   }
+   ralloc_free(ht->table);
+   ralloc_free(ht);
+}
+
+/**
+ * Finds a set entry with the given key and hash of that key.
+ *
+ * Returns NULL if no entry is found.
+ */
+static struct set_entry *
+set_search(const struct set *ht, uint32_t hash, const void *key)
+{
+   uint32_t hash_address;
+
+   hash_address = hash % ht->size;
+   do {
+      uint32_t double_hash;
+
+      struct set_entry *entry = ht->table + hash_address;
+
+      if (entry_is_free(entry)) {
+         return NULL;
+      } else if (entry_is_present(entry) && entry->hash == hash) {
+         if (ht->key_equals_function(key, entry->key)) {
+            return entry;
+         }
+      }
+
+      double_hash = 1 + hash % ht->rehash;
+
+      hash_address = (hash_address + double_hash) % ht->size;
+   } while (hash_address != hash % ht->size);
+
+   return NULL;
+}
+
+struct set_entry *
+_mesa_set_search(const struct set *set, const void *key)
+{
+   assert(set->key_hash_function);
+   return set_search(set, set->key_hash_function(key), key);
+}
+
+struct set_entry *
+_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
+                            const void *key)
+{
+   assert(set->key_hash_function == NULL ||
+          hash == set->key_hash_function(key));
+   return set_search(set, hash, key);
+}
+
+static struct set_entry *
+set_add(struct set *ht, uint32_t hash, const void *key);
+
+static void
+set_rehash(struct set *ht, unsigned new_size_index)
+{
+   struct set old_ht;
+   struct set_entry *table, *entry;
+
+   if (new_size_index >= ARRAY_SIZE(hash_sizes))
+      return;
+
+   table = rzalloc_array(ht, struct set_entry,
+                         hash_sizes[new_size_index].size);
+   if (table == NULL)
+      return;
+
+   old_ht = *ht;
+
+   ht->table = table;
+   ht->size_index = new_size_index;
+   ht->size = hash_sizes[ht->size_index].size;
+   ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->max_entries = hash_sizes[ht->size_index].max_entries;
+   ht->entries = 0;
+   ht->deleted_entries = 0;
+
+   for (entry = old_ht.table;
+        entry != old_ht.table + old_ht.size;
+        entry++) {
+      if (entry_is_present(entry)) {
+         set_add(ht, entry->hash, entry->key);
+      }
+   }
+
+   ralloc_free(old_ht.table);
+}
+
+/**
+ * Inserts the key with the given hash into the table.
+ *
+ * Note that insertion may rearrange the table on a resize or rehash,
+ * so previously found hash_entries are no longer valid after this function.
+ */
+static struct set_entry *
+set_add(struct set *ht, uint32_t hash, const void *key)
+{
+   uint32_t hash_address;
+   struct set_entry *available_entry = NULL;
+
+   if (ht->entries >= ht->max_entries) {
+      set_rehash(ht, ht->size_index + 1);
+   } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
+      set_rehash(ht, ht->size_index);
+   }
+
+   hash_address = hash % ht->size;
+   do {
+      struct set_entry *entry = ht->table + hash_address;
+      uint32_t double_hash;
+
+      if (!entry_is_present(entry)) {
+         /* Stash the first available entry we find */
+         if (available_entry == NULL)
+            available_entry = entry;
+         if (entry_is_free(entry))
+            break;
+      }
+
+      /* Implement replacement when another insert happens
+       * with a matching key.  This is a relatively common
+       * feature of hash tables, with the alternative
+       * generally being "insert the new value as well, and
+       * return it first when the key is searched for".
+       *
+       * Note that the hash table doesn't have a delete callback.
+       * If freeing of old keys is required to avoid memory leaks,
+       * perform a search before inserting.
+       */
+      if (entry->hash == hash &&
+          ht->key_equals_function(key, entry->key)) {
+         entry->key = key;
+         return entry;
+      }
+
+      double_hash = 1 + hash % ht->rehash;
+
+      hash_address = (hash_address + double_hash) % ht->size;
+   } while (hash_address != hash % ht->size);
+
+   if (available_entry) {
+      if (entry_is_deleted(available_entry))
+         ht->deleted_entries--;
+      available_entry->hash = hash;
+      available_entry->key = key;
+      ht->entries++;
+      return available_entry;
+   }
+
+   /* We could hit here if a required resize failed. An unchecked-malloc
+    * application could ignore this result.
+    */
+   return NULL;
+}
+
+struct set_entry *
+_mesa_set_add(struct set *set, const void *key)
+{
+   assert(set->key_hash_function);
+   return set_add(set, set->key_hash_function(key), key);
+}
+
+struct set_entry *
+_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
+{
+   assert(set->key_hash_function == NULL ||
+          hash == set->key_hash_function(key));
+   return set_add(set, hash, key);
+}
+
+/**
+ * This function deletes the given hash table entry.
+ *
+ * Note that deletion doesn't otherwise modify the table, so an iteration over
+ * the table deleting entries is safe.
+ */
+void
+_mesa_set_remove(struct set *ht, struct set_entry *entry)
+{
+   if (!entry)
+      return;
+
+   entry->key = deleted_key;
+   ht->entries--;
+   ht->deleted_entries++;
+}
+
+/**
+ * This function is an iterator over the hash table.
+ *
+ * Pass in NULL for the first entry, as in the start of a for loop.  Note that
+ * an iteration over the table is O(table_size) not O(entries).
+ */
+struct set_entry *
+_mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
+{
+   if (entry == NULL)
+      entry = ht->table;
+   else
+      entry = entry + 1;
+
+   for (; entry != ht->table + ht->size; entry++) {
+      if (entry_is_present(entry)) {
+         return entry;
+      }
+   }
+
+   return NULL;
+}
+
+struct set_entry *
+_mesa_set_random_entry(struct set *ht,
+                       int (*predicate)(struct set_entry *entry))
+{
+   struct set_entry *entry;
+   uint32_t i = rand() % ht->size;
+
+   if (ht->entries == 0)
+      return NULL;
+
+   for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
+      if (entry_is_present(entry) &&
+          (!predicate || predicate(entry))) {
+         return entry;
+      }
+   }
+
+   for (entry = ht->table; entry != ht->table + i; entry++) {
+      if (entry_is_present(entry) &&
+          (!predicate || predicate(entry))) {
+         return entry;
+      }
+   }
+
+   return NULL;
+}
diff --git a/mesalib/src/util/set.h b/mesalib/src/util/set.h
new file mode 100644
index 000000000..9acd2c28c
--- /dev/null
+++ b/mesalib/src/util/set.h
@@ -0,0 +1,100 @@
+/*
+ * Copyright © 2009-2012 Intel Corporation
+ *
+ * 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 (including the next
+ * paragraph) 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.
+ *
+ * Authors:
+ *    Eric Anholt <eric@anholt.net>
+ *
+ */
+
+#ifndef _SET_H
+#define _SET_H
+
+#include <inttypes.h>
+#include <stdbool.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct set_entry {
+   uint32_t hash;
+   const void *key;
+};
+
+struct set {
+   void *mem_ctx;
+   struct set_entry *table;
+   uint32_t (*key_hash_function)(const void *key);
+   bool (*key_equals_function)(const void *a, const void *b);
+   uint32_t size;
+   uint32_t rehash;
+   uint32_t max_entries;
+   uint32_t size_index;
+   uint32_t entries;
+   uint32_t deleted_entries;
+};
+
+struct set *
+_mesa_set_create(void *mem_ctx,
+                 uint32_t (*key_hash_function)(const void *key),
+                 bool (*key_equals_function)(const void *a,
+                                             const void *b));
+void
+_mesa_set_destroy(struct set *set,
+                  void (*delete_function)(struct set_entry *entry));
+
+struct set_entry *
+_mesa_set_add(struct set *set, const void *key);
+struct set_entry *
+_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key);
+
+struct set_entry *
+_mesa_set_search(const struct set *set, const void *key);
+struct set_entry *
+_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
+                            const void *key);
+
+void
+_mesa_set_remove(struct set *set, struct set_entry *entry);
+
+struct set_entry *
+_mesa_set_next_entry(const struct set *set, struct set_entry *entry);
+
+struct set_entry *
+_mesa_set_random_entry(struct set *set,
+                       int (*predicate)(struct set_entry *entry));
+
+/**
+ * This foreach function is safe against deletion, but not against
+ * insertion (which may rehash the set, making entry a dangling
+ * pointer).
+ */
+#define set_foreach(set, entry)                          \
+   for (entry = _mesa_set_next_entry(set, NULL);  \
+        entry != NULL;                                   \
+        entry = _mesa_set_next_entry(set, entry))
+
+#ifdef __cplusplus
+} /* extern C */
+#endif
+
+#endif /* _SET_H */
diff --git a/mesalib/src/util/simple_list.h b/mesalib/src/util/simple_list.h
new file mode 100644
index 000000000..5f261612a
--- /dev/null
+++ b/mesalib/src/util/simple_list.h
@@ -0,0 +1,211 @@
+/**
+ * \file simple_list.h
+ * Simple macros for type-safe, intrusive lists.
+ *
+ *  Intended to work with a list sentinal which is created as an empty
+ *  list.  Insert & delete are O(1).
+ *  
+ * \author
+ *  (C) 1997, Keith Whitwell
+ */
+
+/*
+ * Mesa 3-D graphics library
+ *
+ * Copyright (C) 1999-2001  Brian Paul   All Rights Reserved.
+ *
+ * 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 _SIMPLE_LIST_H
+#define _SIMPLE_LIST_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct simple_node {
+   struct simple_node *next;
+   struct simple_node *prev;
+};
+
+/**
+ * Remove an element from list.
+ *
+ * \param elem element to remove.
+ */
+#define remove_from_list(elem)			\
+do {						\
+   (elem)->next->prev = (elem)->prev;		\
+   (elem)->prev->next = (elem)->next;		\
+   make_empty_list(elem);			\
+} while (0)
+
+/**
+ * Insert an element to the list head.
+ *
+ * \param list list.
+ * \param elem element to insert.
+ */
+#define insert_at_head(list, elem)		\
+do {						\
+   (elem)->prev = list;				\
+   (elem)->next = (list)->next;			\
+   (list)->next->prev = elem;			\
+   (list)->next = elem;				\
+} while(0)
+
+/**
+ * Insert an element to the list tail.
+ *
+ * \param list list.
+ * \param elem element to insert.
+ */
+#define insert_at_tail(list, elem)		\
+do {						\
+   (elem)->next = list;				\
+   (elem)->prev = (list)->prev;			\
+   (list)->prev->next = elem;			\
+   (list)->prev = elem;				\
+} while(0)
+
+/**
+ * Move an element to the list head.
+ *
+ * \param list list.
+ * \param elem element to move.
+ */
+#define move_to_head(list, elem)		\
+do {						\
+   remove_from_list(elem);			\
+   insert_at_head(list, elem);			\
+} while (0)
+
+/**
+ * Move an element to the list tail.
+ *
+ * \param list list.
+ * \param elem element to move.
+ */
+#define move_to_tail(list, elem)		\
+do {						\
+   remove_from_list(elem);			\
+   insert_at_tail(list, elem);			\
+} while (0)
+
+/**
+ * Make a empty list empty.
+ *
+ * \param sentinal list (sentinal element).
+ */
+#define make_empty_list(sentinal)		\
+do {						\
+   (sentinal)->next = sentinal;			\
+   (sentinal)->prev = sentinal;			\
+} while (0)
+
+/**
+ * Get list first element.
+ *
+ * \param list list.
+ *
+ * \return pointer to first element.
+ */
+#define first_elem(list)       ((list)->next)
+
+/**
+ * Get list last element.
+ *
+ * \param list list.
+ *
+ * \return pointer to last element.
+ */
+#define last_elem(list)        ((list)->prev)
+
+/**
+ * Get next element.
+ *
+ * \param elem element.
+ *
+ * \return pointer to next element.
+ */
+#define next_elem(elem)        ((elem)->next)
+
+/**
+ * Get previous element.
+ *
+ * \param elem element.
+ *
+ * \return pointer to previous element.
+ */
+#define prev_elem(elem)        ((elem)->prev)
+
+/**
+ * Test whether element is at end of the list.
+ * 
+ * \param list list.
+ * \param elem element.
+ * 
+ * \return non-zero if element is at end of list, or zero otherwise.
+ */
+#define at_end(list, elem)     ((elem) == (list))
+
+/**
+ * Test if a list is empty.
+ * 
+ * \param list list.
+ * 
+ * \return non-zero if list empty, or zero otherwise.
+ */
+#define is_empty_list(list)    ((list)->next == (list))
+
+/**
+ * Walk through the elements of a list.
+ *
+ * \param ptr pointer to the current element.
+ * \param list list.
+ *
+ * \note It should be followed by a { } block or a single statement, as in a \c
+ * for loop.
+ */
+#define foreach(ptr, list)     \
+        for( ptr=(list)->next ;  ptr!=list ;  ptr=(ptr)->next )
+
+/**
+ * Walk through the elements of a list.
+ *
+ * Same as #foreach but lets you unlink the current value during a list
+ * traversal.  Useful for freeing a list, element by element.
+ * 
+ * \param ptr pointer to the current element.
+ * \param t temporary pointer.
+ * \param list list.
+ *
+ * \note It should be followed by a { } block or a single statement, as in a \c
+ * for loop.
+ */
+#define foreach_s(ptr, t, list)   \
+        for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/mesalib/src/util/u_atomic.h b/mesalib/src/util/u_atomic.h
index 401003638..d15398e1e 100644
--- a/mesalib/src/util/u_atomic.h
+++ b/mesalib/src/util/u_atomic.h
@@ -39,6 +39,7 @@
 #define p_atomic_dec_zero(v) (__sync_sub_and_fetch((v), 1) == 0)
 #define p_atomic_inc(v) (void) __sync_add_and_fetch((v), 1)
 #define p_atomic_dec(v) (void) __sync_sub_and_fetch((v), 1)
+#define p_atomic_add(v, i) (void) __sync_add_and_fetch((v), (i))
 #define p_atomic_inc_return(v) __sync_add_and_fetch((v), 1)
 #define p_atomic_dec_return(v) __sync_sub_and_fetch((v), 1)
 #define p_atomic_cmpxchg(v, old, _new) \
@@ -60,6 +61,7 @@
 #define p_atomic_dec_zero(_v) (p_atomic_dec_return(_v) == 0)
 #define p_atomic_inc(_v) ((void) p_atomic_inc_return(_v))
 #define p_atomic_dec(_v) ((void) p_atomic_dec_return(_v))
+#define p_atomic_add(_v, _i) (*(_v) = *(_v) + (_i))
 #define p_atomic_inc_return(_v) (++(*(_v)))
 #define p_atomic_dec_return(_v) (--(*(_v)))
 #define p_atomic_cmpxchg(_v, _old, _new) (*(_v) == (_old) ? (*(_v) = (_new), (_old)) : *(_v))
@@ -71,8 +73,8 @@
 
 #define PIPE_ATOMIC "MSVC Intrinsics"
 
-/* We use the Windows header's Interlocked* functions instead of the
- * _Interlocked* intrinsics wherever we can, as support for the latter varies
+/* We use the Windows header's Interlocked*64 functions instead of the
+ * _Interlocked*64 intrinsics wherever we can, as support for the latter varies
  * with target CPU, whereas Windows headers take care of all portability
  * issues: using intrinsics where available, falling back to library
  * implementations where not.
@@ -84,7 +86,64 @@
 #include <intrin.h>
 #include <assert.h>
 
-#pragma intrinsic(_InterlockedCompareExchange8)
+#if _MSC_VER < 1600
+
+/* Implement _InterlockedCompareExchange8 in terms of _InterlockedCompareExchange16 */
+static __inline char
+_InterlockedCompareExchange8(char volatile *destination8, char exchange8, char comparand8)
+{
+   INT_PTR destinationAddr = (INT_PTR)destination8;
+   short volatile *destination16 = (short volatile *)(destinationAddr & ~1);
+   const short shift8 = (destinationAddr & 1) * 8;
+   const short mask8 = 0xff << shift8;
+   short initial16 = *destination16;
+   char initial8 = initial16 >> shift8;
+   while (initial8 == comparand8) {
+      /* initial *destination8 matches, so try exchange it while keeping the
+       * neighboring byte untouched */
+      short exchange16 = (initial16 & ~mask8) | ((short)exchange8 << shift8);
+      short comparand16 = initial16;
+      short initial16 = _InterlockedCompareExchange16(destination16, exchange16, comparand16);
+      if (initial16 == comparand16) {
+         /* succeeded */
+         return comparand8;
+      }
+      /* something changed, retry with the new initial value */
+      initial8 = initial16 >> shift8;
+   }
+   return initial8;
+}
+
+/* Implement _InterlockedExchangeAdd16 in terms of _InterlockedCompareExchange16 */
+static __inline short
+_InterlockedExchangeAdd16(short volatile *addend, short value)
+{
+   short initial = *addend;
+   short comparand;
+   do {
+      short exchange = initial + value;
+      comparand = initial;
+      /* if *addend==comparand then *addend=exchange, return original *addend */
+      initial = _InterlockedCompareExchange16(addend, exchange, comparand);
+   } while(initial != comparand);
+   return comparand;
+}
+
+/* Implement _InterlockedExchangeAdd8 in terms of _InterlockedCompareExchange8 */
+static __inline char
+_InterlockedExchangeAdd8(char volatile *addend, char value)
+{
+   char initial = *addend;
+   char comparand;
+   do {
+      char exchange = initial + value;
+      comparand = initial;
+      initial = _InterlockedCompareExchange8(addend, exchange, comparand);
+   } while(initial != comparand);
+   return comparand;
+}
+
+#endif /* _MSC_VER < 1600 */
 
 /* MSVC supports decltype keyword, but it's only supported on C++ and doesn't
  * quite work here; and if a C++-only solution is worthwhile, then it would be
@@ -102,25 +161,32 @@
    ((void) p_atomic_inc_return(_v))
 
 #define p_atomic_inc_return(_v) (\
-   sizeof *(_v) == sizeof(short)   ? InterlockedIncrement16((short *)  (_v)) : \
-   sizeof *(_v) == sizeof(long)    ? InterlockedIncrement  ((long *)   (_v)) : \
-   sizeof *(_v) == sizeof(__int64) ? InterlockedIncrement64((__int64 *)(_v)) : \
+   sizeof *(_v) == sizeof(short)   ? _InterlockedIncrement16((short *)  (_v)) : \
+   sizeof *(_v) == sizeof(long)    ? _InterlockedIncrement  ((long *)   (_v)) : \
+   sizeof *(_v) == sizeof(__int64) ? InterlockedIncrement64 ((__int64 *)(_v)) : \
                                      (assert(!"should not get here"), 0))
 
 #define p_atomic_dec(_v) \
    ((void) p_atomic_dec_return(_v))
 
 #define p_atomic_dec_return(_v) (\
-   sizeof *(_v) == sizeof(short)   ? InterlockedDecrement16((short *)  (_v)) : \
-   sizeof *(_v) == sizeof(long)    ? InterlockedDecrement  ((long *)   (_v)) : \
-   sizeof *(_v) == sizeof(__int64) ? InterlockedDecrement64((__int64 *)(_v)) : \
+   sizeof *(_v) == sizeof(short)   ? _InterlockedDecrement16((short *)  (_v)) : \
+   sizeof *(_v) == sizeof(long)    ? _InterlockedDecrement  ((long *)   (_v)) : \
+   sizeof *(_v) == sizeof(__int64) ? InterlockedDecrement64 ((__int64 *)(_v)) : \
+                                     (assert(!"should not get here"), 0))
+
+#define p_atomic_add(_v, _i) (\
+   sizeof *(_v) == sizeof(char)    ? _InterlockedExchangeAdd8 ((char *)   (_v), (_i)) : \
+   sizeof *(_v) == sizeof(short)   ? _InterlockedExchangeAdd16((short *)  (_v), (_i)) : \
+   sizeof *(_v) == sizeof(long)    ? _InterlockedExchangeAdd  ((long *)   (_v), (_i)) : \
+   sizeof *(_v) == sizeof(__int64) ? InterlockedExchangeAdd64((__int64 *)(_v), (_i)) : \
                                      (assert(!"should not get here"), 0))
 
 #define p_atomic_cmpxchg(_v, _old, _new) (\
-   sizeof *(_v) == sizeof(char)    ? _InterlockedCompareExchange8((char *)   (_v), (char)   (_new), (char)   (_old)) : \
-   sizeof *(_v) == sizeof(short)   ? InterlockedCompareExchange16((short *)  (_v), (short)  (_new), (short)  (_old)) : \
-   sizeof *(_v) == sizeof(long)    ? InterlockedCompareExchange  ((long *)   (_v), (long)   (_new), (long)   (_old)) : \
-   sizeof *(_v) == sizeof(__int64) ? InterlockedCompareExchange64((__int64 *)(_v), (__int64)(_new), (__int64)(_old)) : \
+   sizeof *(_v) == sizeof(char)    ? _InterlockedCompareExchange8 ((char *)   (_v), (char)   (_new), (char)   (_old)) : \
+   sizeof *(_v) == sizeof(short)   ? _InterlockedCompareExchange16((short *)  (_v), (short)  (_new), (short)  (_old)) : \
+   sizeof *(_v) == sizeof(long)    ? _InterlockedCompareExchange  ((long *)   (_v), (long)   (_new), (long)   (_old)) : \
+   sizeof *(_v) == sizeof(__int64) ? InterlockedCompareExchange64 ((__int64 *)(_v), (__int64)(_new), (__int64)(_old)) : \
                                      (assert(!"should not get here"), 0))
 
 #endif
@@ -149,7 +215,7 @@
    sizeof(*v) == sizeof(uint64_t) ? atomic_inc_64((uint64_t *)(v)) : \
                                     (assert(!"should not get here"), 0))
 
-#define p_atomic_inc_return(v) ((typeof(*v)) \
+#define p_atomic_inc_return(v) ((__typeof(*v)) \
    sizeof(*v) == sizeof(uint8_t)  ? atomic_inc_8_nv ((uint8_t  *)(v)) : \
    sizeof(*v) == sizeof(uint16_t) ? atomic_inc_16_nv((uint16_t *)(v)) : \
    sizeof(*v) == sizeof(uint32_t) ? atomic_inc_32_nv((uint32_t *)(v)) : \
@@ -163,14 +229,21 @@
    sizeof(*v) == sizeof(uint64_t) ? atomic_dec_64((uint64_t *)(v)) : \
                                     (assert(!"should not get here"), 0))
 
-#define p_atomic_dec_return(v) ((typeof(*v)) \
+#define p_atomic_dec_return(v) ((__typeof(*v)) \
    sizeof(*v) == sizeof(uint8_t)  ? atomic_dec_8_nv ((uint8_t  *)(v)) : \
    sizeof(*v) == sizeof(uint16_t) ? atomic_dec_16_nv((uint16_t *)(v)) : \
    sizeof(*v) == sizeof(uint32_t) ? atomic_dec_32_nv((uint32_t *)(v)) : \
    sizeof(*v) == sizeof(uint64_t) ? atomic_dec_64_nv((uint64_t *)(v)) : \
                                     (assert(!"should not get here"), 0))
 
-#define p_atomic_cmpxchg(v, old, _new) ((typeof(*v)) \
+#define p_atomic_add(v, i) ((void)				     \
+   sizeof(*v) == sizeof(uint8_t)  ? atomic_add_8 ((uint8_t  *)(v), (i)) : \
+   sizeof(*v) == sizeof(uint16_t) ? atomic_add_16((uint16_t *)(v), (i)) : \
+   sizeof(*v) == sizeof(uint32_t) ? atomic_add_32((uint32_t *)(v), (i)) : \
+   sizeof(*v) == sizeof(uint64_t) ? atomic_add_64((uint64_t *)(v), (i)) : \
+                                    (assert(!"should not get here"), 0))
+
+#define p_atomic_cmpxchg(v, old, _new) ((__typeof(*v)) \
    sizeof(*v) == sizeof(uint8_t)  ? atomic_cas_8 ((uint8_t  *)(v), (uint8_t )(old), (uint8_t )(_new)) : \
    sizeof(*v) == sizeof(uint16_t) ? atomic_cas_16((uint16_t *)(v), (uint16_t)(old), (uint16_t)(_new)) : \
    sizeof(*v) == sizeof(uint32_t) ? atomic_cas_32((uint32_t *)(v), (uint32_t)(old), (uint32_t)(_new)) : \
diff --git a/mesalib/src/util/u_atomic_test.c b/mesalib/src/util/u_atomic_test.c
index 4845e753e..939cfe445 100644
--- a/mesalib/src/util/u_atomic_test.c
+++ b/mesalib/src/util/u_atomic_test.c
@@ -37,8 +37,9 @@
 #include "u_atomic.h"
 
 
-#define test_atomic_cmpxchg(type, ones) \
-   static void test_atomic_cmpxchg_##type (void) { \
+/* Test only assignment-like operations, which are supported on all types */
+#define test_atomic_assign(type, ones) \
+   static void test_atomic_assign_##type (void) { \
       type v, r; \
       \
       p_atomic_set(&v, ones); \
@@ -59,14 +60,33 @@
    }
 
 
+/* Test arithmetic operations that are supported on 8 bits integer types */
+#define test_atomic_8bits(type, ones) \
+   test_atomic_assign(type, ones) \
+   \
+   static void test_atomic_8bits_##type (void) { \
+      type v, r; \
+      \
+      test_atomic_assign_##type(); \
+      \
+      v = 23; \
+      p_atomic_add(&v, 42); \
+      r = p_atomic_read(&v); \
+      assert(r == 65 && "p_atomic_add"); \
+      \
+      (void) r; \
+   }
+
+
+/* Test all operations */
 #define test_atomic(type, ones) \
-   test_atomic_cmpxchg(type, ones) \
+   test_atomic_8bits(type, ones) \
    \
    static void test_atomic_##type (void) { \
       type v, r; \
       bool b; \
       \
-      test_atomic_cmpxchg_##type(); \
+      test_atomic_8bits_##type(); \
       \
       v = 2; \
       b = p_atomic_dec_zero(&v); \
@@ -112,9 +132,9 @@ test_atomic(uint32_t, UINT32_C(0xffffffff))
 test_atomic(int64_t, INT64_C(-1))
 test_atomic(uint64_t, UINT64_C(0xffffffffffffffff))
 
-test_atomic_cmpxchg(int8_t, INT8_C(-1))
-test_atomic_cmpxchg(uint8_t, UINT8_C(0xff))
-test_atomic_cmpxchg(bool, true)
+test_atomic_8bits(int8_t, INT8_C(-1))
+test_atomic_8bits(uint8_t, UINT8_C(0xff))
+test_atomic_assign(bool, true)
 
 int
 main()
@@ -129,9 +149,9 @@ main()
    test_atomic_int64_t();
    test_atomic_uint64_t();
 
-   test_atomic_cmpxchg_int8_t();
-   test_atomic_cmpxchg_uint8_t();
-   test_atomic_cmpxchg_bool();
+   test_atomic_8bits_int8_t();
+   test_atomic_8bits_uint8_t();
+   test_atomic_assign_bool();
 
    return 0;
 }