summaryrefslogtreecommitdiff
path: root/include/util
diff options
context:
space:
mode:
Diffstat (limited to 'include/util')
-rw-r--r--include/util/array.h79
-rw-r--r--include/util/hash_table.h92
-rw-r--r--include/util/mempool.h31
-rw-r--r--include/util/rbtree.h74
-rw-r--r--include/util/str_table.h63
-rw-r--r--include/util/threadpool.h125
-rw-r--r--include/util/util.h38
-rw-r--r--include/util/w32threadwrap.h105
8 files changed, 607 insertions, 0 deletions
diff --git a/include/util/array.h b/include/util/array.h
new file mode 100644
index 0000000..cbac7c2
--- /dev/null
+++ b/include/util/array.h
@@ -0,0 +1,79 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * array.h
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef ARRAY_H
+#define ARRAY_H
+
+#include "sqfs/predef.h"
+#include "sqfs/error.h"
+
+#include <stddef.h>
+#include <string.h>
+#include <stdlib.h>
+
+typedef struct {
+ /* sizeof a single element */
+ size_t size;
+
+ /* total number of elements available */
+ size_t count;
+
+ /* actually used number of elements available */
+ size_t used;
+
+ void *data;
+} array_t;
+
+static SQFS_INLINE void *array_get(array_t *array, size_t index)
+{
+ if (index >= array->used)
+ return NULL;
+
+ return (char *)array->data + array->size * index;
+}
+
+static SQFS_INLINE int array_set(array_t *array, size_t index, const void *data)
+{
+ if (index >= array->used)
+ return SQFS_ERROR_OUT_OF_BOUNDS;
+
+ memcpy((char *)array->data + array->size * index, data, array->size);
+ return 0;
+}
+
+static SQFS_INLINE void array_sort_range(array_t *array, size_t start,
+ size_t count,
+ int (*compare_fun)(const void *a,
+ const void *b))
+{
+ if (start < array->used) {
+ if (count > (array->used - start))
+ count = array->used - start;
+
+ qsort((char *)array->data + array->size * start, count,
+ array->size, compare_fun);
+ }
+}
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+SQFS_INTERNAL int array_init(array_t *array, size_t size, size_t capacity);
+
+SQFS_INTERNAL int array_init_copy(array_t *array, const array_t *src);
+
+SQFS_INTERNAL void array_cleanup(array_t *array);
+
+SQFS_INTERNAL int array_append(array_t *array, const void *data);
+
+SQFS_INTERNAL int array_set_capacity(array_t *array, size_t capacity);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* ARRAY_H */
diff --git a/include/util/hash_table.h b/include/util/hash_table.h
new file mode 100644
index 0000000..813e059
--- /dev/null
+++ b/include/util/hash_table.h
@@ -0,0 +1,92 @@
+/*
+ * 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 _HASH_TABLE_H
+#define _HASH_TABLE_H
+
+#include <stdlib.h>
+#include <inttypes.h>
+#include <stdbool.h>
+
+#include "sqfs/predef.h"
+
+struct hash_entry {
+ sqfs_u32 hash;
+ const void *key;
+ void *data;
+};
+
+struct hash_table {
+ struct hash_entry *table;
+ sqfs_u32 (*key_hash_function)(void *user, const void *key);
+ bool (*key_equals_function)(void *user, const void *a, const void *b);
+ const void *deleted_key;
+ void *user;
+ sqfs_u32 size;
+ sqfs_u32 rehash;
+ sqfs_u64 size_magic;
+ sqfs_u64 rehash_magic;
+ sqfs_u32 max_entries;
+ sqfs_u32 size_index;
+ sqfs_u32 entries;
+ sqfs_u32 deleted_entries;
+};
+
+SQFS_INTERNAL struct hash_table *
+hash_table_create(sqfs_u32 (*key_hash_function)(void *user, const void *key),
+ bool (*key_equals_function)(void *user, const void *a,
+ const void *b));
+
+SQFS_INTERNAL struct hash_table *
+hash_table_clone(struct hash_table *src);
+
+SQFS_INTERNAL void
+hash_table_destroy(struct hash_table *ht,
+ void (*delete_function)(struct hash_entry *entry));
+
+SQFS_INTERNAL struct hash_entry *
+hash_table_insert_pre_hashed(struct hash_table *ht, sqfs_u32 hash,
+ const void *key, void *data);
+
+SQFS_INTERNAL struct hash_entry *
+hash_table_search_pre_hashed(struct hash_table *ht, sqfs_u32 hash,
+ const void *key);
+
+SQFS_INTERNAL struct hash_entry *hash_table_next_entry(struct hash_table *ht,
+ struct hash_entry *entry);
+
+/**
+ * This foreach function is safe against deletion (which just replaces
+ * an entry's data with the deleted marker), but not against insertion
+ * (which may rehash the table, making entry a dangling pointer).
+ */
+#define hash_table_foreach(ht, entry) \
+ for (struct hash_entry *entry = hash_table_next_entry(ht, NULL); \
+ entry != NULL; \
+ entry = hash_table_next_entry(ht, entry))
+
+#endif /* _HASH_TABLE_H */
diff --git a/include/util/mempool.h b/include/util/mempool.h
new file mode 100644
index 0000000..c946c31
--- /dev/null
+++ b/include/util/mempool.h
@@ -0,0 +1,31 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * mempool.h
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef MEMPOOL_H
+#define MEMPOOL_H
+
+#include "compat.h"
+#include "sqfs/predef.h"
+
+typedef struct mem_pool_t mem_pool_t;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+SQFS_INTERNAL mem_pool_t *mem_pool_create(size_t obj_size);
+
+SQFS_INTERNAL void mem_pool_destroy(mem_pool_t *mem);
+
+SQFS_INTERNAL void *mem_pool_allocate(mem_pool_t *mem);
+
+SQFS_INTERNAL void mem_pool_free(mem_pool_t *mem, void *ptr);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* MEMPOOL_H */
diff --git a/include/util/rbtree.h b/include/util/rbtree.h
new file mode 100644
index 0000000..aac175b
--- /dev/null
+++ b/include/util/rbtree.h
@@ -0,0 +1,74 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * rbtree.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef SQFS_RBTREE_H
+#define SQFS_RBTREE_H
+
+#include "config.h"
+#include "sqfs/predef.h"
+#include "mempool.h"
+#include "compat.h"
+
+#include <stddef.h>
+
+typedef struct rbtree_node_t {
+ struct rbtree_node_t *left;
+ struct rbtree_node_t *right;
+ sqfs_u32 value_offset;
+ sqfs_u32 is_red : 1;
+ sqfs_u32 pad0 : 31;
+
+ sqfs_u8 data[];
+} rbtree_node_t;
+
+typedef struct rbtree_t {
+ rbtree_node_t *root;
+
+#ifndef NO_CUSTOM_ALLOC
+ mem_pool_t *pool;
+#endif
+
+ int (*key_compare)(const void *ctx,
+ const void *lhs, const void *hrs);
+
+ size_t key_size;
+ size_t key_size_padded;
+
+ size_t value_size;
+
+ void *key_context;
+} rbtree_t;
+
+static SQFS_INLINE void *rbtree_node_key(rbtree_node_t *n)
+{
+ return n->data;
+}
+
+static SQFS_INLINE void *rbtree_node_value(rbtree_node_t *n)
+{
+ return n->data + n->value_offset;
+}
+
+SQFS_INTERNAL int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize,
+ int(*key_compare)(const void *, const void *,
+ const void *));
+
+SQFS_INTERNAL void rbtree_cleanup(rbtree_t *tree);
+
+SQFS_INTERNAL int rbtree_copy(const rbtree_t *tree, rbtree_t *out);
+
+SQFS_INTERNAL int rbtree_insert(rbtree_t *tree, const void *key,
+ const void *value);
+
+SQFS_INTERNAL rbtree_node_t *rbtree_lookup(const rbtree_t *tree,
+ const void *key);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* TOOLS_RBTREE_H */
+
diff --git a/include/util/str_table.h b/include/util/str_table.h
new file mode 100644
index 0000000..206fa3a
--- /dev/null
+++ b/include/util/str_table.h
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * str_table.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef STR_TABLE_H
+#define STR_TABLE_H
+
+#include "sqfs/predef.h"
+#include "array.h"
+#include "hash_table.h"
+
+typedef struct {
+ size_t index;
+ size_t refcount;
+ char string[];
+} str_bucket_t;
+
+/* Stores strings in a hash table and assigns an incremental, unique ID to
+ each string. Subsequent additions return the existing ID. The ID can be
+ used for (hopefully) constant time lookup of the original string. */
+typedef struct {
+ /* an array that resolves index to bucket pointer */
+ array_t bucket_ptrs;
+
+ /* hash table with the string buckets attached */
+ struct hash_table *ht;
+
+ /* the next ID we are going to allocate */
+ size_t next_index;
+} str_table_t;
+
+/* the number of strings currently stored in the table */
+static SQFS_INLINE size_t str_table_count(const str_table_t *table)
+{
+ return table->next_index;
+}
+
+/* `size` is the number of hash table buckets to use internally. */
+SQFS_INTERNAL int str_table_init(str_table_t *table);
+
+SQFS_INTERNAL void str_table_cleanup(str_table_t *table);
+
+SQFS_INTERNAL int str_table_copy(str_table_t *dst, const str_table_t *src);
+
+/* Resolve a string to an incremental, unique ID. */
+SQFS_INTERNAL
+int str_table_get_index(str_table_t *table, const char *str, size_t *idx);
+
+/* Resolve a unique ID to the string it represents.
+ Returns NULL if the ID is unknown, i.e. out of bounds. */
+SQFS_INTERNAL
+const char *str_table_get_string(const str_table_t *table, size_t index);
+
+SQFS_INTERNAL void str_table_add_ref(str_table_t *table, size_t index);
+
+SQFS_INTERNAL void str_table_del_ref(str_table_t *table, size_t index);
+
+SQFS_INTERNAL
+size_t str_table_get_ref_count(const str_table_t *table, size_t index);
+
+#endif /* STR_TABLE_H */
diff --git a/include/util/threadpool.h b/include/util/threadpool.h
new file mode 100644
index 0000000..f25c497
--- /dev/null
+++ b/include/util/threadpool.h
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * threadpool.h
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef THREADPOOL_H
+#define THREADPOOL_H
+
+#include "sqfs/predef.h"
+
+typedef int (*thread_pool_worker_t)(void *user, void *work_item);
+
+/**
+ * @struct thread_pool_t
+ *
+ * @brief A thread pool with a ticket number based work item ordering.
+ *
+ * While the order in which items are non-deterministic, the thread pool
+ * implementation internally uses a ticket system to ensure the completed
+ * items are deqeueued in the same order that they were enqueued.
+ */
+typedef struct thread_pool_t {
+ /**
+ * @brief Shutdown and destroy a thread pool.
+ *
+ * @param pool A pointer to a pool returned by thread_pool_create
+ */
+ void (*destroy)(struct thread_pool_t *pool);
+
+ /**
+ * @brief Get the actual number of worker threads available.
+ *
+ * @return A number greater or equal to 1.
+ */
+ size_t (*get_worker_count)(struct thread_pool_t *pool);
+
+ /**
+ * @brief Change the user data pointer for a thread pool worker
+ * by index.
+ *
+ * @param idx A zero-based index into the worker list.
+ * @param ptr A user pointer that this specific worker thread should
+ * pass to the worker callback.
+ */
+ void (*set_worker_ptr)(struct thread_pool_t *pool, size_t idx,
+ void *ptr);
+
+ /**
+ * @brief Submit a work item to a thread pool.
+ *
+ * This function will fail on allocation failure or if the internal
+ * error state is set was set by one of the workers.
+ *
+ * @param ptr A pointer to a work object to enqueue.
+ *
+ * @return Zero on success.
+ */
+ int (*submit)(struct thread_pool_t *pool, void *ptr);
+
+ /**
+ * @brief Wait for a work item to be completed.
+ *
+ * This function dequeues a single completed work item. It may block
+ * until one of the worker threads signals completion of an additional
+ * item.
+ *
+ * This function guarantees to return the items in the same order as
+ * they were submitted, so the function can actually block longer than
+ * necessary, because it has to wait until the next item in sequence
+ * is finished.
+ *
+ * @return A pointer to a new work item or NULL if there are none
+ * in the pipeline.
+ */
+ void *(*dequeue)(struct thread_pool_t *pool);
+
+ /**
+ * @brief Get the internal worker return status value.
+ *
+ * If the worker functions returns a non-zero exit status in one of the
+ * worker threads, the thread pool stors the value internally and shuts
+ * down. This function can be used to retrieve the value.
+ *
+ * @return A non-zero value returned by the worker callback or zero if
+ * everything is A-OK.
+ */
+ int (*get_status)(struct thread_pool_t *pool);
+} thread_pool_t;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @brief Create a thread pool instance.
+ *
+ * @param num_jobs The number of worker threads to launch.
+ * @param worker A function to call from the worker threads to process
+ * the work items.
+ *
+ * @return A pointer to a thread pool on success, NULL on failure.
+ */
+SQFS_INTERNAL thread_pool_t *thread_pool_create(size_t num_jobs,
+ thread_pool_worker_t worker);
+
+/**
+ * @brief Create a serial mockup thread pool implementation.
+ *
+ * This returns a @ref thread_pool_t implementation that, instead of running a
+ * thread pool actually does the work in-situ when dequeueing.
+ *
+ * @param worker A function to call from the worker threads to process
+ * the work items.
+ *
+ * @return A pointer to a thread pool on success, NULL on failure.
+ */
+SQFS_INTERNAL
+thread_pool_t *thread_pool_create_serial(thread_pool_worker_t worker);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* THREADPOOL_H */
diff --git a/include/util/util.h b/include/util/util.h
new file mode 100644
index 0000000..4b05340
--- /dev/null
+++ b/include/util/util.h
@@ -0,0 +1,38 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * util.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef SQFS_UTIL_H
+#define SQFS_UTIL_H
+
+#include "config.h"
+#include "sqfs/predef.h"
+#include "compat.h"
+
+#include <stddef.h>
+
+/*
+ Helper for allocating data structures with flexible array members.
+
+ 'base_size' is the size of the struct itself, 'item_size' the size of a
+ single array element and 'nmemb' the number of elements.
+
+ Iternally checks for arithmetic overflows when allocating the combined thing.
+ */
+SQFS_INTERNAL
+void *alloc_flex(size_t base_size, size_t item_size, size_t nmemb);
+
+/* Basically the same as calloc, but *ALWAYS* does overflow checking */
+SQFS_INTERNAL
+void *alloc_array(size_t item_size, size_t nmemb);
+
+SQFS_INTERNAL sqfs_u32 xxh32(const void *input, const size_t len);
+
+/*
+ Returns true if the given region of memory is filled with zero-bytes only.
+ */
+SQFS_INTERNAL bool is_memory_zero(const void *blob, size_t size);
+
+#endif /* SQFS_UTIL_H */
diff --git a/include/util/w32threadwrap.h b/include/util/w32threadwrap.h
new file mode 100644
index 0000000..6b7344c
--- /dev/null
+++ b/include/util/w32threadwrap.h
@@ -0,0 +1,105 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * w32threadwrap.h
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef W32THREADWRAP_H
+#define W32THREADWRAP_H
+
+#include "sqfs/predef.h"
+
+#define WIN32_LEAN_AND_MEAN
+#define VC_EXTRALEAN
+#include <windows.h>
+
+typedef unsigned int sigset_t;
+typedef HANDLE pthread_t;
+typedef CRITICAL_SECTION pthread_mutex_t;
+typedef CONDITION_VARIABLE pthread_cond_t;
+
+static inline int pthread_create(pthread_t *thread, const void *attr,
+ LPTHREAD_START_ROUTINE proc, LPVOID arg)
+{
+ HANDLE hnd = CreateThread(NULL, 0, proc, arg, 0, 0);
+ (void)attr;
+
+ if (hnd == NULL)
+ return -1;
+
+ *thread = hnd;
+ return 0;
+}
+
+static int pthread_join(pthread_t thread, void **retval)
+{
+ WaitForSingleObject(thread, INFINITE);
+ CloseHandle(thread);
+ if (retval != NULL)
+ *retval = NULL;
+ return 0;
+}
+
+static inline int pthread_mutex_init(pthread_mutex_t *mutex, const void *attr)
+{
+ (void)attr;
+ InitializeCriticalSection(mutex);
+ return 0;
+}
+
+static inline int pthread_mutex_lock(pthread_mutex_t *mutex)
+{
+ EnterCriticalSection(mutex);
+ return 0;
+}
+
+static inline int pthread_mutex_unlock(pthread_mutex_t *mutex)
+{
+ LeaveCriticalSection(mutex);
+ return 0;
+}
+
+static inline void pthread_mutex_destroy(pthread_mutex_t *mutex)
+{
+ DeleteCriticalSection(mutex);
+}
+
+static inline int pthread_cond_init(pthread_cond_t *cond, const void *attr)
+{
+ (void)attr;
+ InitializeConditionVariable(cond);
+ return 0;
+}
+
+static inline int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mtx)
+{
+ return SleepConditionVariableCS(cond, mtx, INFINITE) != 0;
+}
+
+static inline int pthread_cond_broadcast(pthread_cond_t *cond)
+{
+ WakeAllConditionVariable(cond);
+ return 0;
+}
+
+static inline void pthread_cond_destroy(pthread_cond_t *cond)
+{
+ (void)cond;
+}
+
+#define SIG_SETMASK (0)
+
+static inline int sigfillset(sigset_t *set)
+{
+ *set = 0xFFFFFFFF;
+ return 0;
+}
+
+static inline int pthread_sigmask(int how, const sigset_t *set,
+ const sigset_t *old)
+{
+ (void)how; (void)set; (void)old;
+ return 0;
+}
+
+#endif /* W32THREADWRAP_H */
generated by cgit v1.2.3 (git 2.39.1) at 2025-10-31 18:13:14 +0000