aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/util
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/util')
-rw-r--r--mesalib/src/util/Makefile.am9
-rw-r--r--mesalib/src/util/Makefile.sources8
-rw-r--r--mesalib/src/util/SConscript7
-rw-r--r--mesalib/src/util/bitset.h99
-rw-r--r--mesalib/src/util/hash_table.c46
-rw-r--r--mesalib/src/util/hash_table.h23
-rw-r--r--mesalib/src/util/macros.h2
-rw-r--r--mesalib/src/util/mesa-sha1.c316
-rw-r--r--mesalib/src/util/mesa-sha1.h53
-rw-r--r--mesalib/src/util/register_allocate.c2
-rw-r--r--mesalib/src/util/set.c391
-rw-r--r--mesalib/src/util/set.h100
-rw-r--r--mesalib/src/util/simple_list.h211
-rw-r--r--mesalib/src/util/u_atomic.h105
-rw-r--r--mesalib/src/util/u_atomic_test.c40
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;
}