aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/util
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/util')
-rw-r--r--mesalib/src/util/.gitignore1
-rw-r--r--mesalib/src/util/Makefile.am13
-rw-r--r--mesalib/src/util/Makefile.sources18
-rw-r--r--mesalib/src/util/SConscript16
-rw-r--r--mesalib/src/util/bitset.h99
-rw-r--r--mesalib/src/util/hash_table.c117
-rw-r--r--mesalib/src/util/hash_table.h38
-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.c16
-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.h261
-rw-r--r--mesalib/src/util/u_atomic_test.c157
16 files changed, 1754 insertions, 55 deletions
diff --git a/mesalib/src/util/.gitignore b/mesalib/src/util/.gitignore
index e945ecbb5..ecf4985fe 100644
--- a/mesalib/src/util/.gitignore
+++ b/mesalib/src/util/.gitignore
@@ -1 +1,2 @@
format_srgb.c
+u_atomic_test
diff --git a/mesalib/src/util/Makefile.am b/mesalib/src/util/Makefile.am
index 8d5f90e97..9af233059 100644
--- a/mesalib/src/util/Makefile.am
+++ b/mesalib/src/util/Makefile.am
@@ -31,14 +31,27 @@ 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)
+
BUILT_SOURCES = $(MESA_UTIL_GENERATED_FILES)
CLEANFILES = $(BUILT_SOURCES)
+EXTRA_DIST = format_srgb.py SConscript
format_srgb.c: $(srcdir)/format_srgb.py
$(AM_V_GEN) $(PYTHON2) $< > $@
diff --git a/mesalib/src/util/Makefile.sources b/mesalib/src/util/Makefile.sources
index 9e274241d..560ea836a 100644
--- a/mesalib/src/util/Makefile.sources
+++ b/mesalib/src/util/Makefile.sources
@@ -1,10 +1,26 @@
+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 \
+ macros.h \
ralloc.c \
+ ralloc.h \
register_allocate.c \
register_allocate.h \
rgtc.c \
- strtod.cpp
+ rgtc.h \
+ set.c \
+ set.h \
+ simple_list.h \
+ strtod.cpp \
+ strtod.h \
+ texcompress_rgtc_tmp.h \
+ u_atomic.h
MESA_UTIL_GENERATED_FILES = \
format_srgb.c
diff --git a/mesalib/src/util/SConscript b/mesalib/src/util/SConscript
index ade1d6c6c..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,
@@ -36,3 +43,12 @@ mesautil = env.ConvenienceLibrary(
env.Alias('mesautil', mesautil)
Export('mesautil')
+
+
+# http://www.scons.org/wiki/UnitTests
+u_atomic_test = env.Program(
+ target = 'u_atomic_test',
+ source = ['u_atomic_test.c'],
+)
+alias = env.Alias("u_atomic_test", u_atomic_test, u_atomic_test[0].abspath)
+AlwaysBuild(alias)
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 920bdfd33..3247593c1 100644
--- a/mesalib/src/util/hash_table.c
+++ b/mesalib/src/util/hash_table.c
@@ -42,6 +42,7 @@
#include <stdlib.h>
#include <string.h>
+#include <assert.h>
#include "hash_table.h"
#include "ralloc.h"
@@ -110,6 +111,7 @@ entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
struct hash_table *
_mesa_hash_table_create(void *mem_ctx,
+ uint32_t (*key_hash_function)(const void *key),
bool (*key_equals_function)(const void *a,
const void *b))
{
@@ -123,6 +125,7 @@ _mesa_hash_table_create(void *mem_ctx,
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 hash_entry, ht->size);
ht->entries = 0;
@@ -176,15 +179,8 @@ _mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key)
ht->deleted_key = deleted_key;
}
-/**
- * Finds a hash table entry with the given key and hash of that key.
- *
- * Returns NULL if no entry is found. Note that the data pointer may be
- * modified by the user.
- */
-struct hash_entry *
-_mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
- const void *key)
+static struct hash_entry *
+hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
{
uint32_t start_hash_address = hash % ht->size;
uint32_t hash_address = start_hash_address;
@@ -210,8 +206,33 @@ _mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
return NULL;
}
+/**
+ * Finds a hash table entry with the given key and hash of that key.
+ *
+ * Returns NULL if no entry is found. Note that the data pointer may be
+ * modified by the user.
+ */
+struct hash_entry *
+_mesa_hash_table_search(struct hash_table *ht, const void *key)
+{
+ assert(ht->key_hash_function);
+ return hash_table_search(ht, ht->key_hash_function(key), key);
+}
+
+struct hash_entry *
+_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
+ const void *key)
+{
+ assert(ht->key_hash_function == NULL || hash == ht->key_hash_function(key));
+ return hash_table_search(ht, hash, key);
+}
+
+static struct hash_entry *
+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;
@@ -235,24 +256,18 @@ _mesa_hash_table_rehash(struct hash_table *ht, int new_size_index)
ht->deleted_entries = 0;
hash_table_foreach(&old_ht, entry) {
- _mesa_hash_table_insert(ht, entry->hash,
- entry->key, entry->data);
+ hash_table_insert(ht, entry->hash, entry->key, entry->data);
}
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.
- */
-struct hash_entry *
-_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
- const void *key, void *data)
+static struct hash_entry *
+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);
@@ -267,13 +282,11 @@ _mesa_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
@@ -300,6 +313,16 @@ _mesa_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.
*/
@@ -307,6 +330,27 @@ _mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
}
/**
+ * 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.
+ */
+struct hash_entry *
+_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data)
+{
+ assert(ht->key_hash_function);
+ return hash_table_insert(ht, ht->key_hash_function(key), key, data);
+}
+
+struct hash_entry *
+_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);
+}
+
+/**
* This function deletes the given hash table entry.
*
* Note that deletion doesn't otherwise modify the table, so an iteration over
@@ -396,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 d6b6ebf40..eb9dbc333 100644
--- a/mesalib/src/util/hash_table.h
+++ b/mesalib/src/util/hash_table.h
@@ -46,6 +46,7 @@ struct hash_entry {
struct hash_table {
struct hash_entry *table;
+ uint32_t (*key_hash_function)(const void *key);
bool (*key_equals_function)(const void *a, const void *b);
const void *deleted_key;
uint32_t size;
@@ -58,6 +59,7 @@ struct hash_table {
struct hash_table *
_mesa_hash_table_create(void *mem_ctx,
+ uint32_t (*key_hash_function)(const void *key),
bool (*key_equals_function)(const void *a,
const void *b));
void _mesa_hash_table_destroy(struct hash_table *ht,
@@ -66,11 +68,15 @@ void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
const void *deleted_key);
struct hash_entry *
-_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
- const void *key, void *data);
+_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
struct hash_entry *
-_mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
- const void *key);
+_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 *
+_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
+ const void *key);
void _mesa_hash_table_remove(struct hash_table *ht,
struct hash_entry *entry);
@@ -85,11 +91,35 @@ uint32_t _mesa_hash_string(const char *key);
bool _mesa_key_string_equal(const void *a, const void *b);
bool _mesa_key_pointer_equal(const void *a, const void *b);
+static inline uint32_t _mesa_key_hash_string(const void *key)
+{
+ return _mesa_hash_string((const char *)key);
+}
+
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 6cf7ce721..684ee5d6c 100644
--- a/mesalib/src/util/register_allocate.c
+++ b/mesalib/src/util/register_allocate.c
@@ -76,10 +76,10 @@
#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 ~0
+#define NO_REG ~0U
struct ra_reg {
BITSET_WORD *conflicts;
@@ -251,7 +251,7 @@ void
ra_add_transitive_reg_conflict(struct ra_regs *regs,
unsigned int base_reg, unsigned int reg)
{
- int i;
+ unsigned int i;
ra_add_reg_conflict(regs, reg, base_reg);
@@ -328,7 +328,7 @@ ra_set_finalize(struct ra_regs *regs, unsigned int **q_values)
for (rc = 0; rc < regs->count; rc++) {
int conflicts = 0;
- int i;
+ unsigned int i;
if (!reg_belongs_to_class(rc, regs->classes[c]))
continue;
@@ -374,7 +374,7 @@ ra_alloc_interference_graph(struct ra_regs *regs, unsigned int count)
struct ra_graph *g;
unsigned int i;
- g = rzalloc(regs, struct ra_graph);
+ g = rzalloc(NULL, struct ra_graph);
g->regs = regs;
g->nodes = rzalloc_array(g, struct ra_node, count);
g->count = count;
@@ -481,7 +481,7 @@ ra_simplify(struct ra_graph *g)
}
}
- if (!progress && best_optimistic_node != ~0) {
+ if (!progress && best_optimistic_node != ~0U) {
decrement_q(g, best_optimistic_node);
g->stack[g->stack_count] = best_optimistic_node;
g->stack_count++;
@@ -501,10 +501,10 @@ ra_simplify(struct ra_graph *g)
static bool
ra_select(struct ra_graph *g)
{
- int i;
int start_search_reg = 0;
while (g->stack_count != 0) {
+ unsigned int i;
unsigned int ri;
unsigned int r = -1;
int n = g->stack[g->stack_count - 1];
@@ -585,7 +585,7 @@ ra_set_node_reg(struct ra_graph *g, unsigned int n, unsigned int reg)
static float
ra_get_spill_benefit(struct ra_graph *g, unsigned int n)
{
- int j;
+ unsigned int j;
float benefit = 0;
int n_class = g->nodes[n].class;
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
new file mode 100644
index 000000000..d15398e1e
--- /dev/null
+++ b/mesalib/src/util/u_atomic.h
@@ -0,0 +1,261 @@
+/**
+ * Many similar implementations exist. See for example libwsbm
+ * or the linux kernel include/atomic.h
+ *
+ * No copyright claimed on this file.
+ *
+ */
+
+#ifndef U_ATOMIC_H
+#define U_ATOMIC_H
+
+#include <stdbool.h>
+
+/* Favor OS-provided implementations.
+ *
+ * Where no OS-provided implementation is available, fall back to
+ * locally coded assembly, compiler intrinsic or ultimately a
+ * mutex-based implementation.
+ */
+#if defined(__sun)
+#define PIPE_ATOMIC_OS_SOLARIS
+#elif defined(_MSC_VER)
+#define PIPE_ATOMIC_MSVC_INTRINSIC
+#elif defined(__GNUC__)
+#define PIPE_ATOMIC_GCC_INTRINSIC
+#else
+#error "Unsupported platform"
+#endif
+
+
+/* Implementation using GCC-provided synchronization intrinsics
+ */
+#if defined(PIPE_ATOMIC_GCC_INTRINSIC)
+
+#define PIPE_ATOMIC "GCC Sync Intrinsics"
+
+#define p_atomic_set(_v, _i) (*(_v) = (_i))
+#define p_atomic_read(_v) (*(_v))
+#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) \
+ __sync_val_compare_and_swap((v), (old), (_new))
+
+#endif
+
+
+
+/* Unlocked version for single threaded environments, such as some
+ * windows kernel modules.
+ */
+#if defined(PIPE_ATOMIC_OS_UNLOCKED)
+
+#define PIPE_ATOMIC "Unlocked"
+
+#define p_atomic_set(_v, _i) (*(_v) = (_i))
+#define p_atomic_read(_v) (*(_v))
+#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))
+
+#endif
+
+
+#if defined(PIPE_ATOMIC_MSVC_INTRINSIC)
+
+#define PIPE_ATOMIC "MSVC Intrinsics"
+
+/* 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.
+ */
+#ifndef WIN32_LEAN_AND_MEAN
+#define WIN32_LEAN_AND_MEAN 1
+#endif
+#include <windows.h>
+#include <intrin.h>
+#include <assert.h>
+
+#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
+ * better to use templates / function overloading, instead of decltype magic.
+ * Therefore, we rely on implicit casting to LONGLONG for the functions that return
+ */
+
+#define p_atomic_set(_v, _i) (*(_v) = (_i))
+#define p_atomic_read(_v) (*(_v))
+
+#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_inc_return(_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)) : \
+ (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)) : \
+ (assert(!"should not get here"), 0))
+
+#endif
+
+#if defined(PIPE_ATOMIC_OS_SOLARIS)
+
+#define PIPE_ATOMIC "Solaris OS atomic functions"
+
+#include <atomic.h>
+#include <assert.h>
+
+#define p_atomic_set(_v, _i) (*(_v) = (_i))
+#define p_atomic_read(_v) (*(_v))
+
+#define p_atomic_dec_zero(v) (\
+ sizeof(*v) == sizeof(uint8_t) ? atomic_dec_8_nv ((uint8_t *)(v)) == 0 : \
+ sizeof(*v) == sizeof(uint16_t) ? atomic_dec_16_nv((uint16_t *)(v)) == 0 : \
+ sizeof(*v) == sizeof(uint32_t) ? atomic_dec_32_nv((uint32_t *)(v)) == 0 : \
+ sizeof(*v) == sizeof(uint64_t) ? atomic_dec_64_nv((uint64_t *)(v)) == 0 : \
+ (assert(!"should not get here"), 0))
+
+#define p_atomic_inc(v) (void) (\
+ sizeof(*v) == sizeof(uint8_t) ? atomic_inc_8 ((uint8_t *)(v)) : \
+ sizeof(*v) == sizeof(uint16_t) ? atomic_inc_16((uint16_t *)(v)) : \
+ sizeof(*v) == sizeof(uint32_t) ? atomic_inc_32((uint32_t *)(v)) : \
+ 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)) \
+ 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)) : \
+ sizeof(*v) == sizeof(uint64_t) ? atomic_inc_64_nv((uint64_t *)(v)) : \
+ (assert(!"should not get here"), 0))
+
+#define p_atomic_dec(v) ((void) \
+ sizeof(*v) == sizeof(uint8_t) ? atomic_dec_8 ((uint8_t *)(v)) : \
+ sizeof(*v) == sizeof(uint16_t) ? atomic_dec_16((uint16_t *)(v)) : \
+ sizeof(*v) == sizeof(uint32_t) ? atomic_dec_32((uint32_t *)(v)) : \
+ 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)) \
+ 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_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)) : \
+ sizeof(*v) == sizeof(uint64_t) ? atomic_cas_64((uint64_t *)(v), (uint64_t)(old), (uint64_t)(_new)) : \
+ (assert(!"should not get here"), 0))
+
+#endif
+
+#ifndef PIPE_ATOMIC
+#error "No pipe_atomic implementation selected"
+#endif
+
+
+
+#endif /* U_ATOMIC_H */
diff --git a/mesalib/src/util/u_atomic_test.c b/mesalib/src/util/u_atomic_test.c
new file mode 100644
index 000000000..939cfe445
--- /dev/null
+++ b/mesalib/src/util/u_atomic_test.c
@@ -0,0 +1,157 @@
+/**************************************************************************
+ *
+ * Copyright 2014 VMware, Inc.
+ * 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, sub license, 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 NON-INFRINGEMENT.
+ * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS 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.
+ *
+ **************************************************************************/
+
+
+/* Force assertions, even on debug builds. */
+#undef NDEBUG
+
+
+#include <stdint.h>
+#include <inttypes.h>
+#include <assert.h>
+
+#include "u_atomic.h"
+
+
+/* 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); \
+ assert(v == ones && "p_atomic_set"); \
+ \
+ r = p_atomic_read(&v); \
+ assert(r == ones && "p_atomic_read"); \
+ \
+ v = ones; \
+ r = p_atomic_cmpxchg(&v, 0, 1); \
+ assert(v == ones && "p_atomic_cmpxchg"); \
+ assert(r == ones && "p_atomic_cmpxchg"); \
+ r = p_atomic_cmpxchg(&v, ones, 0); \
+ assert(v == 0 && "p_atomic_cmpxchg"); \
+ assert(r == ones && "p_atomic_cmpxchg"); \
+ \
+ (void) r; \
+ }
+
+
+/* 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_8bits(type, ones) \
+ \
+ static void test_atomic_##type (void) { \
+ type v, r; \
+ bool b; \
+ \
+ test_atomic_8bits_##type(); \
+ \
+ v = 2; \
+ b = p_atomic_dec_zero(&v); \
+ assert(v == 1 && "p_atomic_dec_zero"); \
+ assert(b == false && "p_atomic_dec_zero"); \
+ b = p_atomic_dec_zero(&v); \
+ assert(v == 0 && "p_atomic_dec_zero"); \
+ assert(b == true && "p_atomic_dec_zero"); \
+ b = p_atomic_dec_zero(&v); \
+ assert(v == ones && "p_atomic_dec_zero"); \
+ assert(b == false && "p_atomic_dec_zero"); \
+ \
+ v = ones; \
+ p_atomic_inc(&v); \
+ assert(v == 0 && "p_atomic_inc"); \
+ \
+ v = ones; \
+ r = p_atomic_inc_return(&v); \
+ assert(v == 0 && "p_atomic_inc_return"); \
+ assert(r == v && "p_atomic_inc_return"); \
+ \
+ v = 0; \
+ p_atomic_dec(&v); \
+ assert(v == ones && "p_atomic_dec"); \
+ \
+ v = 0; \
+ r = p_atomic_dec_return(&v); \
+ assert(v == ones && "p_atomic_dec_return"); \
+ assert(r == v && "p_atomic_dec_return"); \
+ \
+ (void) r; \
+ (void) b; \
+ }
+
+
+test_atomic(int, -1)
+test_atomic(unsigned, ~0U)
+
+test_atomic(int16_t, INT16_C(-1))
+test_atomic(uint16_t, UINT16_C(0xffff))
+test_atomic(int32_t, INT32_C(-1))
+test_atomic(uint32_t, UINT32_C(0xffffffff))
+test_atomic(int64_t, INT64_C(-1))
+test_atomic(uint64_t, UINT64_C(0xffffffffffffffff))
+
+test_atomic_8bits(int8_t, INT8_C(-1))
+test_atomic_8bits(uint8_t, UINT8_C(0xff))
+test_atomic_assign(bool, true)
+
+int
+main()
+{
+ test_atomic_int();
+ test_atomic_unsigned();
+
+ test_atomic_int16_t();
+ test_atomic_uint16_t();
+ test_atomic_int32_t();
+ test_atomic_uint32_t();
+ test_atomic_int64_t();
+ test_atomic_uint64_t();
+
+ test_atomic_8bits_int8_t();
+ test_atomic_8bits_uint8_t();
+ test_atomic_assign_bool();
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-06 16:23:32 +0000