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 */