From 2087cc237cd0fe1ed29ebf891648bacb46f4833b Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sun, 26 Jun 2022 16:45:52 +0200 Subject: Cleanup: move libutil headers to sub directory Move all the libutil stuff from the toplevel include/ to a util/ sub directory and fix up the includes that make use of them. Signed-off-by: David Oberhollenzer --- include/array.h | 79 --------------------------- include/hash_table.h | 92 ------------------------------- include/mempool.h | 31 ----------- include/rbtree.h | 74 ------------------------- include/str_table.h | 63 ---------------------- include/threadpool.h | 125 ------------------------------------------- include/util.h | 38 ------------- include/util/array.h | 79 +++++++++++++++++++++++++++ include/util/hash_table.h | 92 +++++++++++++++++++++++++++++++ include/util/mempool.h | 31 +++++++++++ include/util/rbtree.h | 74 +++++++++++++++++++++++++ include/util/str_table.h | 63 ++++++++++++++++++++++ include/util/threadpool.h | 125 +++++++++++++++++++++++++++++++++++++++++++ include/util/util.h | 38 +++++++++++++ include/util/w32threadwrap.h | 105 ++++++++++++++++++++++++++++++++++++ include/w32threadwrap.h | 105 ------------------------------------ 16 files changed, 607 insertions(+), 607 deletions(-) delete mode 100644 include/array.h delete mode 100644 include/hash_table.h delete mode 100644 include/mempool.h delete mode 100644 include/rbtree.h delete mode 100644 include/str_table.h delete mode 100644 include/threadpool.h delete mode 100644 include/util.h create mode 100644 include/util/array.h create mode 100644 include/util/hash_table.h create mode 100644 include/util/mempool.h create mode 100644 include/util/rbtree.h create mode 100644 include/util/str_table.h create mode 100644 include/util/threadpool.h create mode 100644 include/util/util.h create mode 100644 include/util/w32threadwrap.h delete mode 100644 include/w32threadwrap.h (limited to 'include') diff --git a/include/array.h b/include/array.h deleted file mode 100644 index cbac7c2..0000000 --- a/include/array.h +++ /dev/null @@ -1,79 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * array.h - * - * Copyright (C) 2021 David Oberhollenzer - */ -#ifndef ARRAY_H -#define ARRAY_H - -#include "sqfs/predef.h" -#include "sqfs/error.h" - -#include -#include -#include - -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/hash_table.h b/include/hash_table.h deleted file mode 100644 index 813e059..0000000 --- a/include/hash_table.h +++ /dev/null @@ -1,92 +0,0 @@ -/* - * 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 - * - */ - -#ifndef _HASH_TABLE_H -#define _HASH_TABLE_H - -#include -#include -#include - -#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/mempool.h b/include/mempool.h deleted file mode 100644 index c946c31..0000000 --- a/include/mempool.h +++ /dev/null @@ -1,31 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * mempool.h - * - * Copyright (C) 2021 David Oberhollenzer - */ -#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/rbtree.h b/include/rbtree.h deleted file mode 100644 index aac175b..0000000 --- a/include/rbtree.h +++ /dev/null @@ -1,74 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * rbtree.h - * - * Copyright (C) 2019 David Oberhollenzer - */ -#ifndef SQFS_RBTREE_H -#define SQFS_RBTREE_H - -#include "config.h" -#include "sqfs/predef.h" -#include "mempool.h" -#include "compat.h" - -#include - -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/str_table.h b/include/str_table.h deleted file mode 100644 index 206fa3a..0000000 --- a/include/str_table.h +++ /dev/null @@ -1,63 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * str_table.h - * - * Copyright (C) 2019 David Oberhollenzer - */ -#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/threadpool.h b/include/threadpool.h deleted file mode 100644 index f25c497..0000000 --- a/include/threadpool.h +++ /dev/null @@ -1,125 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * threadpool.h - * - * Copyright (C) 2021 David Oberhollenzer - */ -#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.h b/include/util.h deleted file mode 100644 index 4b05340..0000000 --- a/include/util.h +++ /dev/null @@ -1,38 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * util.h - * - * Copyright (C) 2019 David Oberhollenzer - */ -#ifndef SQFS_UTIL_H -#define SQFS_UTIL_H - -#include "config.h" -#include "sqfs/predef.h" -#include "compat.h" - -#include - -/* - 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/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 + */ +#ifndef ARRAY_H +#define ARRAY_H + +#include "sqfs/predef.h" +#include "sqfs/error.h" + +#include +#include +#include + +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 + * + */ + +#ifndef _HASH_TABLE_H +#define _HASH_TABLE_H + +#include +#include +#include + +#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 + */ +#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 + */ +#ifndef SQFS_RBTREE_H +#define SQFS_RBTREE_H + +#include "config.h" +#include "sqfs/predef.h" +#include "mempool.h" +#include "compat.h" + +#include + +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 + */ +#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 + */ +#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 + */ +#ifndef SQFS_UTIL_H +#define SQFS_UTIL_H + +#include "config.h" +#include "sqfs/predef.h" +#include "compat.h" + +#include + +/* + 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 + */ +#ifndef W32THREADWRAP_H +#define W32THREADWRAP_H + +#include "sqfs/predef.h" + +#define WIN32_LEAN_AND_MEAN +#define VC_EXTRALEAN +#include + +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 */ diff --git a/include/w32threadwrap.h b/include/w32threadwrap.h deleted file mode 100644 index 6b7344c..0000000 --- a/include/w32threadwrap.h +++ /dev/null @@ -1,105 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * w32threadwrap.h - * - * Copyright (C) 2021 David Oberhollenzer - */ -#ifndef W32THREADWRAP_H -#define W32THREADWRAP_H - -#include "sqfs/predef.h" - -#define WIN32_LEAN_AND_MEAN -#define VC_EXTRALEAN -#include - -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 */ -- cgit v1.2.3