summaryrefslogtreecommitdiffstats
path: root/libdimension/base
diff options
context:
space:
mode:
Diffstat (limited to 'libdimension/base')
-rw-r--r--libdimension/base/array.c33
-rw-r--r--libdimension/base/dictionary.c228
-rw-r--r--libdimension/base/error.c144
-rw-r--r--libdimension/base/inline.c43
-rw-r--r--libdimension/base/malloc.c94
-rw-r--r--libdimension/base/pool.c177
-rw-r--r--libdimension/base/profile.c168
7 files changed, 887 insertions, 0 deletions
diff --git a/libdimension/base/array.c b/libdimension/base/array.c
new file mode 100644
index 0000000..d8faed7
--- /dev/null
+++ b/libdimension/base/array.c
@@ -0,0 +1,33 @@
+/*************************************************************************
+ * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Non-inline array functions.
+ */
+
+#include "dimension/base.h"
+
+void
+dmnsn_array_cleanup(void *ptr)
+{
+ dmnsn_array *array = ptr;
+ dmnsn_free(array->ptr);
+}
diff --git a/libdimension/base/dictionary.c b/libdimension/base/dictionary.c
new file mode 100644
index 0000000..6e99abd
--- /dev/null
+++ b/libdimension/base/dictionary.c
@@ -0,0 +1,228 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Associative arrays, implemented with PATRICIA tries.
+ */
+
+#include "dimension/base.h"
+
+struct dmnsn_dictionary {
+ size_t obj_size; ///< The size of the objects in the trie.
+ char *prefix; ///< The local string prefix of the current node.
+ void *value; ///< The node's stored object, if it's a leaf.
+ dmnsn_array *children; ///< The node's children.
+};
+
+dmnsn_dictionary *
+dmnsn_new_dictionary(size_t obj_size)
+{
+ dmnsn_dictionary *dict = DMNSN_MALLOC(dmnsn_dictionary);
+ dict->obj_size = obj_size;
+ dict->prefix = dmnsn_strdup("");
+ dict->value = NULL;
+ dict->children = DMNSN_NEW_ARRAY(dmnsn_dictionary *);
+ return dict;
+}
+
+void
+dmnsn_delete_dictionary(dmnsn_dictionary *dict)
+{
+ if (dict) {
+ dmnsn_free(dict->prefix);
+ dmnsn_free(dict->value);
+ DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) {
+ dmnsn_delete_dictionary(*subtrie);
+ }
+ dmnsn_delete_array(dict->children);
+
+ dmnsn_free(dict);
+ }
+}
+
+bool
+dmnsn_dictionary_get(const dmnsn_dictionary *dict, const char *key, void *obj)
+{
+ const void *value = dmnsn_dictionary_at(dict, key);
+ if (value) {
+ memcpy(obj, value, dict->obj_size);
+ return true;
+ } else {
+ return false;
+ }
+}
+
+void *
+dmnsn_dictionary_at(const dmnsn_dictionary *dict, const char *key)
+{
+ // PATRICIA trie search: O(k), where k is the length of the longest string in
+ // the trie.
+
+ size_t len = strlen(dict->prefix);
+ if (strncmp(key, dict->prefix, len) != 0)
+ return NULL;
+ key += len;
+
+ while (true) {
+ if (*key == '\0' && dict->value) {
+ return dict->value;
+ } else {
+ dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie;
+ ptrdiff_t size = dmnsn_array_size(dict->children);
+ for (subtrie = first; subtrie - first < size; ++subtrie) {
+ len = strlen((*subtrie)->prefix);
+ if (strncmp(key, (*subtrie)->prefix, len) == 0) {
+ dict = *subtrie;
+ key += len;
+ break;
+ }
+ }
+
+ if (subtrie - first == size)
+ break;
+ }
+ }
+
+ return NULL;
+}
+
+void
+dmnsn_dictionary_insert(dmnsn_dictionary *dict, const char *key,
+ const void *obj)
+{
+ // PATRICIA trie insertion: O(k), where k is the length of the longest string
+ // in the trie.
+
+ while (true) {
+ if (dict->prefix[0] == '\0' && !dict->value
+ && dmnsn_array_size(dict->children) == 0)
+ {
+ // Replace an empty tree with a single-element tree
+ dict->prefix = dmnsn_realloc(dict->prefix, strlen(key) + 1);
+ strcpy(dict->prefix, key);
+
+ dict->value = dmnsn_malloc(dict->obj_size);
+ memcpy(dict->value, obj, dict->obj_size);
+ break;
+ }
+
+ char *prefix = dict->prefix;
+ while (*prefix == *key && *prefix && *key) {
+ ++prefix;
+ ++key;
+ }
+
+ if (*key == '\0' && *prefix == '\0') {
+ // Complete match
+ if (!dict->value) {
+ dict->value = dmnsn_malloc(dict->obj_size);
+ }
+ memcpy(dict->value, obj, dict->obj_size);
+ break;
+ } else if (*prefix == '\0') {
+ // Partial match; key starts with prefix
+ dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie;
+ ptrdiff_t size = dmnsn_array_size(dict->children);
+ for (subtrie = first; subtrie - first < size; ++subtrie) {
+ if ((*subtrie)->prefix[0] == key[0]) {
+ dict = *subtrie;
+ break;
+ }
+ }
+
+ if (subtrie - first == size) {
+ // No submatch found, add a new child
+ dmnsn_dictionary *child = dmnsn_new_dictionary(dict->obj_size);
+ dmnsn_array_push(dict->children, &child);
+ dict = child;
+ }
+ } else {
+ // Split the tree
+ dmnsn_dictionary *copy = dmnsn_new_dictionary(dict->obj_size);
+ copy->prefix = dmnsn_realloc(copy->prefix, strlen(prefix) + 1);
+ strcpy(copy->prefix, prefix);
+ *prefix = '\0';
+
+ copy->value = dict->value;
+ dict->value = NULL;
+
+ dmnsn_array *temp = copy->children;
+ copy->children = dict->children;
+ dict->children = temp;
+
+ dmnsn_dictionary *subtrie = dmnsn_new_dictionary(dict->obj_size);
+ dmnsn_array_push(dict->children, &copy);
+ dmnsn_array_push(dict->children, &subtrie);
+ dict = subtrie;
+ }
+ }
+}
+
+bool
+dmnsn_dictionary_remove(dmnsn_dictionary *dict, const char *key)
+{
+ // PATRICIA trie removal: O(k), where k is the length of the longest string
+ // in the trie.
+
+ // This implementation doesn't actually collapse the tree back upwards if a
+ // node is left with only one child, to reduce complexity.
+
+ size_t len = strlen(dict->prefix);
+ if (strncmp(key, dict->prefix, len) != 0)
+ return false;
+ key += len;
+
+ while (true) {
+ if (*key == '\0' && dict->value) {
+ dmnsn_free(dict->value);
+ dict->value = NULL;
+ return true;
+ } else {
+ dmnsn_dictionary **first = dmnsn_array_first(dict->children), **subtrie;
+ ptrdiff_t size = dmnsn_array_size(dict->children);
+ for (subtrie = first; subtrie - first < size; ++subtrie) {
+ len = strlen((*subtrie)->prefix);
+ if (strncmp(key, (*subtrie)->prefix, len) == 0) {
+ dict = *subtrie;
+ key += len;
+ break;
+ }
+ }
+
+ if (subtrie - first == size)
+ break;
+ }
+ }
+
+ return false;
+}
+
+void
+dmnsn_dictionary_apply(dmnsn_dictionary *dict, dmnsn_callback_fn *callback)
+{
+ if (dict->value) {
+ callback(dict->value);
+ }
+
+ DMNSN_ARRAY_FOREACH (dmnsn_dictionary **, subtrie, dict->children) {
+ dmnsn_dictionary_apply(*subtrie, callback);
+ }
+}
diff --git a/libdimension/base/error.c b/libdimension/base/error.c
new file mode 100644
index 0000000..6b8d18e
--- /dev/null
+++ b/libdimension/base/error.c
@@ -0,0 +1,144 @@
+/*************************************************************************
+ * Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Error handling.
+ */
+
+#include "internal.h"
+#include "internal/platform.h"
+#include <errno.h>
+#include <pthread.h>
+#include <stdatomic.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/// Report internal errors in this file.
+#define DMNSN_LOCAL_ERROR(str) \
+ do { \
+ fprintf(stderr, "Dimension ERROR: %s, %s:%u: %s\n", \
+ DMNSN_FUNC, __FILE__, __LINE__, (str)); \
+ abort(); \
+ } while (0)
+
+/// The default fatal error handler.
+static void dmnsn_default_fatal_error_fn(void);
+
+/// The current fatal error handler.
+static atomic(dmnsn_fatal_error_fn *) dmnsn_fatal = ATOMIC_VAR_INIT(dmnsn_default_fatal_error_fn);
+
+/// The current resilience.
+static atomic_bool dmnsn_always_die = ATOMIC_VAR_INIT(false);
+
+void
+dmnsn_report_impl(bool die, const char *func, const char *file, unsigned int line, const char *str)
+{
+ // Save the value of errno
+ int err = errno;
+
+ bool always_die = atomic_load(&dmnsn_always_die);
+
+ // Print the diagnostic string
+ fprintf(stderr, "Dimension %s: %s, %s:%u: %s\n",
+ die ? "ERROR" : "WARNING", func, file, line, str);
+
+ // Print the value of errno
+ if (err != 0) {
+ fprintf(stderr, "Last error: %d", err);
+#if DMNSN_STRERROR_R
+ char errbuf[256];
+ if (strerror_r(err, errbuf, 256) == 0) {
+ fprintf(stderr, " (%s)", errbuf);
+ }
+#elif DMNSN_SYS_ERRLIST
+ if (err >= 0 && err < sys_nerr) {
+ fprintf(stderr, " (%s)", sys_errlist[err]);
+ }
+#endif
+ fprintf(stderr, "\n");
+ }
+
+ // Print a stack trace to standard error
+ dmnsn_backtrace(stderr);
+
+ // Call the fatal error handler if needed
+ if (die || always_die) {
+ static __thread bool thread_exiting = false;
+
+ if (thread_exiting) {
+ if (die) {
+ // Prevent infinite recursion if the fatal error function itself calls
+ // dmnsn_error() (not dmnsn_warning())
+ DMNSN_LOCAL_ERROR("Error raised while in error handler, aborting.");
+ }
+ } else {
+ thread_exiting = true;
+
+ dmnsn_fatal_error_fn *fatal = dmnsn_get_fatal_error_fn();
+ fatal();
+ DMNSN_LOCAL_ERROR("Fatal error handler didn't exit.");
+ }
+ }
+}
+
+void
+dmnsn_report_warning(const char *func, const char *file, unsigned int line, const char *str)
+{
+ dmnsn_report_impl(false, func, file, line, str);
+}
+
+DMNSN_NORETURN
+dmnsn_report_error(const char *func, const char *file, unsigned int line, const char *str)
+{
+ dmnsn_report_impl(true, func, file, line, str);
+ DMNSN_UNREACHABLE();
+}
+
+void
+dmnsn_die_on_warnings(bool always_die)
+{
+ atomic_store(&dmnsn_always_die, always_die);
+}
+
+dmnsn_fatal_error_fn *
+dmnsn_get_fatal_error_fn(void)
+{
+ dmnsn_fatal_error_fn *fatal = atomic_load(&dmnsn_fatal);
+ return fatal;
+}
+
+void
+dmnsn_set_fatal_error_fn(dmnsn_fatal_error_fn *fatal)
+{
+ atomic_store(&dmnsn_fatal, fatal);
+}
+
+static void
+dmnsn_default_fatal_error_fn(void)
+{
+ if (dmnsn_is_main_thread()) {
+ exit(EXIT_FAILURE);
+ } else {
+ pthread_exit(NULL);
+ }
+}
diff --git a/libdimension/base/inline.c b/libdimension/base/inline.c
new file mode 100644
index 0000000..b0622fe
--- /dev/null
+++ b/libdimension/base/inline.c
@@ -0,0 +1,43 @@
+/*************************************************************************
+ * Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Emit definitions of inline functions, if necessary.
+ */
+
+// Set DMNSN_INLINE to produce definitions of inline functions, emitted here,
+// if needed
+#ifdef __cplusplus
+ // C++ inline semantics
+ #define DMNSN_INLINE inline
+#elif __STDC_VERSION__ >= 199901L
+ // C99 inline semantics
+ #define DMNSN_INLINE
+#elif defined(__GNUC__)
+ // GCC inline semantics
+ #define DMNSN_INLINE __inline__
+#else
+ // Unknown C - mark functions static and hope the compiler is smart enough to
+ // inline them
+ #define DMNSN_INLINE static
+#endif
+
+#include "dimension.h"
diff --git a/libdimension/base/malloc.c b/libdimension/base/malloc.c
new file mode 100644
index 0000000..6aaf68c
--- /dev/null
+++ b/libdimension/base/malloc.c
@@ -0,0 +1,94 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Dynamic memory.
+ */
+
+#include "internal.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdatomic.h>
+
+#if DMNSN_DEBUG
+static atomic_size_t dmnsn_allocs = ATOMIC_VAR_INIT(0);
+#endif
+
+void *
+dmnsn_malloc(size_t size)
+{
+ void *ptr = malloc(size);
+ if (!ptr) {
+ dmnsn_error("Memory allocation failed.");
+ }
+
+#if DMNSN_DEBUG
+ atomic_fetch_add(&dmnsn_allocs, 1);
+#endif
+
+ return ptr;
+}
+
+void *
+dmnsn_realloc(void *ptr, size_t size)
+{
+#if DMNSN_DEBUG
+ if (!ptr) {
+ atomic_fetch_add(&dmnsn_allocs, 1);
+ }
+#endif
+
+ ptr = realloc(ptr, size);
+ if (!ptr) {
+ dmnsn_error("Memory allocation failed.");
+ }
+ return ptr;
+}
+
+char *
+dmnsn_strdup(const char *s)
+{
+ char *copy = dmnsn_malloc(strlen(s) + 1);
+ strcpy(copy, s);
+ return copy;
+}
+
+void
+dmnsn_free(void *ptr)
+{
+#if DMNSN_DEBUG
+ if (ptr) {
+ atomic_fetch_sub(&dmnsn_allocs, 1);
+ }
+#endif
+
+ free(ptr);
+}
+
+#if DMNSN_DEBUG
+DMNSN_LATE_DESTRUCTOR static void
+dmnsn_leak_check(void)
+{
+ if (atomic_load_explicit(&dmnsn_allocs, memory_order_relaxed) > 0) {
+ dmnsn_warning("Leaking memory.");
+ }
+}
+#endif
diff --git a/libdimension/base/pool.c b/libdimension/base/pool.c
new file mode 100644
index 0000000..4bfdd7d
--- /dev/null
+++ b/libdimension/base/pool.c
@@ -0,0 +1,177 @@
+/*************************************************************************
+ * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Memory pool implementation.
+ */
+
+#include "internal.h"
+#include "internal/concurrency.h"
+#include <stdatomic.h>
+
+/// Number of pointers per block, we want a block to fit in a single page.
+#define DMNSN_POOL_BLOCK_SIZE (4096/sizeof(void *) - 4)
+/// Number of pointers per tidy block
+#define DMNSN_TIDY_BLOCK_SIZE ((4096 - 4*sizeof(void *))/(sizeof(void *) + sizeof(dmnsn_callback_fn *)))
+
+/// A single block in a thread-specific pool.
+typedef struct dmnsn_pool_block {
+ /// Current index into allocs[].
+ size_t i;
+ /// All allocations in the current block.
+ void *allocs[DMNSN_POOL_BLOCK_SIZE];
+ /// Tail pointer to the previous block in the global chain.
+ struct dmnsn_pool_block *prev;
+} dmnsn_pool_block;
+
+/// A single tidy block in a thread-specific pool.
+typedef struct dmnsn_tidy_block {
+ /// Current index into allocs[].
+ size_t i;
+ /// All allocations in the current block.
+ void *allocs[DMNSN_TIDY_BLOCK_SIZE];
+ /// All cleanup callbacks in the current block.
+ dmnsn_callback_fn *cleanup_fns[DMNSN_TIDY_BLOCK_SIZE];
+ /// Tail pointer to the previous tidy block in the global chain.
+ struct dmnsn_tidy_block *prev;
+} dmnsn_tidy_block;
+
+/// dmnsn_pool implementation.
+struct dmnsn_pool {
+ /// Thread-local regular block.
+ pthread_key_t thread_block;
+ /// Thread-local tidy block.
+ pthread_key_t thread_tidy_block;
+
+ /// Global chain of regular blocks.
+ atomic(dmnsn_pool_block *) chain;
+ /// Global chain of tidy blocks.
+ atomic(dmnsn_tidy_block *) tidy_chain;
+};
+
+dmnsn_pool *
+dmnsn_new_pool(void)
+{
+ dmnsn_pool *pool = DMNSN_MALLOC(dmnsn_pool);
+
+ dmnsn_key_create(&pool->thread_block, NULL);
+ dmnsn_key_create(&pool->thread_tidy_block, NULL);
+
+ atomic_store_explicit(&pool->chain, NULL, memory_order_relaxed);
+ atomic_store_explicit(&pool->tidy_chain, NULL, memory_order_relaxed);
+
+ return pool;
+}
+
+void *
+dmnsn_palloc(dmnsn_pool *pool, size_t size)
+{
+ dmnsn_pool_block *old_block = pthread_getspecific(pool->thread_block);
+
+ dmnsn_pool_block *new_block = old_block;
+ if (dmnsn_unlikely(!old_block || old_block->i == DMNSN_POOL_BLOCK_SIZE)) {
+ new_block = DMNSN_MALLOC(dmnsn_pool_block);
+ new_block->i = 0;
+ }
+
+ void *result = dmnsn_malloc(size);
+ new_block->allocs[new_block->i++] = result;
+
+ if (dmnsn_unlikely(new_block != old_block)) {
+ dmnsn_setspecific(pool->thread_block, new_block);
+
+ // Atomically update pool->chain
+ dmnsn_pool_block *old_chain = atomic_exchange(&pool->chain, new_block);
+ new_block->prev = old_chain;
+ }
+
+ return result;
+}
+
+void *
+dmnsn_palloc_tidy(dmnsn_pool *pool, size_t size, dmnsn_callback_fn *cleanup_fn)
+{
+ dmnsn_assert(cleanup_fn != NULL, "NULL cleanup_fn");
+
+ dmnsn_tidy_block *old_block = pthread_getspecific(pool->thread_tidy_block);
+
+ dmnsn_tidy_block *new_block = old_block;
+ if (dmnsn_unlikely(!old_block || old_block->i == DMNSN_TIDY_BLOCK_SIZE)) {
+ new_block = DMNSN_MALLOC(dmnsn_tidy_block);
+ new_block->i = 0;
+ }
+
+ void *result = dmnsn_malloc(size);
+
+ size_t i = new_block->i;
+ new_block->allocs[i] = result;
+ new_block->cleanup_fns[i] = cleanup_fn;
+ ++new_block->i;
+
+ if (dmnsn_unlikely(new_block != old_block)) {
+ dmnsn_setspecific(pool->thread_tidy_block, new_block);
+
+ // Atomically update pool->tidy_chain
+ dmnsn_tidy_block *old_chain = atomic_exchange(&pool->tidy_chain, new_block);
+ new_block->prev = old_chain;
+ }
+
+ return result;
+}
+
+void
+dmnsn_delete_pool(dmnsn_pool *pool)
+{
+ if (!pool) {
+ return;
+ }
+
+ dmnsn_pool_block *block = atomic_load_explicit(&pool->chain, memory_order_relaxed);
+ while (block) {
+ // Free all the allocations
+ for (size_t i = block->i; i-- > 0;) {
+ dmnsn_free(block->allocs[i]);
+ }
+
+ // Free the block itself and go to the previous one
+ dmnsn_pool_block *saved = block;
+ block = block->prev;
+ dmnsn_free(saved);
+ }
+
+ dmnsn_tidy_block *tidy_block = atomic_load_explicit(&pool->tidy_chain, memory_order_relaxed);
+ while (tidy_block) {
+ // Free all the allocations
+ for (size_t i = tidy_block->i; i-- > 0;) {
+ void *ptr = tidy_block->allocs[i];
+ tidy_block->cleanup_fns[i](ptr);
+ dmnsn_free(ptr);
+ }
+
+ // Free the block itself and go to the previous one
+ dmnsn_tidy_block *saved = tidy_block;
+ tidy_block = tidy_block->prev;
+ dmnsn_free(saved);
+ }
+
+ dmnsn_key_delete(pool->thread_tidy_block);
+ dmnsn_free(pool);
+}
diff --git a/libdimension/base/profile.c b/libdimension/base/profile.c
new file mode 100644
index 0000000..87f27c1
--- /dev/null
+++ b/libdimension/base/profile.c
@@ -0,0 +1,168 @@
+/*************************************************************************
+ * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @file
+ * Branch profile accounting.
+ */
+
+#include "internal.h"
+#include "internal/concurrency.h"
+#include <inttypes.h>
+#include <pthread.h>
+#include <stdio.h>
+
+/// Information on one predicted branch.
+typedef struct {
+ char *location;
+ uint64_t predicted, branches;
+} dmnsn_branch;
+
+/// Count of mispredicted branches.
+static dmnsn_dictionary *dmnsn_profile = NULL;
+/// Mutex which protects \c dmnsn_profile.
+static pthread_mutex_t dmnsn_profile_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+/// Thread-local count of mispredicted branches.
+static pthread_key_t dmnsn_thread_profile;
+/// Initialize the thread-specific pointer exactly once.
+static pthread_once_t dmnsn_thread_profile_once = PTHREAD_ONCE_INIT;
+
+/// Add thread-specific profile data to the global counts.
+static void
+dmnsn_profile_globalize(void *ptr)
+{
+ dmnsn_branch *branch = ptr;
+ dmnsn_branch *global = dmnsn_dictionary_at(dmnsn_profile, branch->location);
+ if (global) {
+ global->predicted += branch->predicted;
+ global->branches += branch->branches;
+ dmnsn_free(branch->location);
+ } else {
+ dmnsn_dictionary_insert(dmnsn_profile, branch->location, branch);
+ }
+}
+
+/// Destructor function for thread-specific profile data.
+static void
+dmnsn_delete_thread_profile(void *ptr)
+{
+ dmnsn_dictionary *thread_profile = ptr;
+
+ dmnsn_lock_mutex(&dmnsn_profile_mutex);
+ dmnsn_dictionary_apply(thread_profile, dmnsn_profile_globalize);
+ dmnsn_unlock_mutex(&dmnsn_profile_mutex);
+
+ dmnsn_delete_dictionary(thread_profile);
+}
+
+/// Initialize the thread-specific pointer.
+static void
+dmnsn_initialize_thread_profile(void)
+{
+ dmnsn_key_create(&dmnsn_thread_profile, dmnsn_delete_thread_profile);
+
+ dmnsn_lock_mutex(&dmnsn_profile_mutex);
+ dmnsn_profile = dmnsn_new_dictionary(sizeof(dmnsn_branch));
+ dmnsn_unlock_mutex(&dmnsn_profile_mutex);
+}
+
+/// Get the thread-specific profile data.
+static dmnsn_dictionary *
+dmnsn_get_thread_profile(void)
+{
+ dmnsn_once(&dmnsn_thread_profile_once, dmnsn_initialize_thread_profile);
+ return pthread_getspecific(dmnsn_thread_profile);
+}
+
+/// Set the thread-specific profile data.
+static void
+dmnsn_set_thread_profile(dmnsn_dictionary *thread_profile)
+{
+ dmnsn_setspecific(dmnsn_thread_profile, thread_profile);
+}
+
+bool
+dmnsn_expect(bool result, bool expected, const char *func, const char *file,
+ unsigned int line)
+{
+ int size = snprintf(NULL, 0, "%s:%s:%u", file, func, line) + 1;
+ if (size < 1) {
+ dmnsn_error("sprintf() failed.");
+ }
+
+ char key[size];
+ if (snprintf(key, size, "%s:%s:%u", file, func, line) < 0) {
+ dmnsn_error("sprintf() failed.");
+ }
+
+ dmnsn_dictionary *thread_profile = dmnsn_get_thread_profile();
+ if (!thread_profile) {
+ thread_profile = dmnsn_new_dictionary(sizeof(dmnsn_branch));
+ dmnsn_set_thread_profile(thread_profile);
+ }
+
+ dmnsn_branch *branch = dmnsn_dictionary_at(thread_profile, key);
+ if (branch) {
+ ++branch->branches;
+ if (result == expected) {
+ ++branch->predicted;
+ }
+ } else {
+ dmnsn_branch new_branch = {
+ .location = dmnsn_strdup(key),
+ .predicted = (result == expected) ? 1 : 0,
+ .branches = 1
+ };
+ dmnsn_dictionary_insert(thread_profile, key, &new_branch);
+ }
+
+ return result;
+}
+
+static void
+dmnsn_print_bad_prediction(void *ptr)
+{
+ dmnsn_branch *branch = ptr;
+ double rate = ((double)branch->predicted)/branch->branches;
+ if (rate < 0.75 || branch->branches < 100000) {
+ fprintf(stderr,
+ "Bad branch prediction: %s: %" PRIu64 "/%" PRIu64 " (%g%%)\n",
+ branch->location, branch->predicted, branch->branches, 100.0*rate);
+ }
+
+ dmnsn_free(branch->location);
+}
+
+DMNSN_DESTRUCTOR static void
+dmnsn_print_bad_predictions(void)
+{
+ dmnsn_dictionary *thread_profile = dmnsn_get_thread_profile();
+ if (thread_profile) {
+ dmnsn_delete_thread_profile(thread_profile);
+ dmnsn_set_thread_profile(NULL);
+ }
+
+ dmnsn_lock_mutex(&dmnsn_profile_mutex);
+ dmnsn_dictionary_apply(dmnsn_profile, dmnsn_print_bad_prediction);
+ dmnsn_delete_dictionary(dmnsn_profile);
+ dmnsn_profile = NULL;
+ dmnsn_unlock_mutex(&dmnsn_profile_mutex);
+}