From 98b660135e142371431759c2a52a6ecb5457bb0d Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Tue, 19 May 2020 16:17:29 +0200 Subject: Cleanup: move hash table header to include directory Signed-off-by: David Oberhollenzer --- COPYING.md | 6 ++-- include/hash_table.h | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++ lib/sqfs/Makemodule.am | 2 +- lib/sqfs/frag_table.c | 2 +- lib/util/Makemodule.am | 4 +-- lib/util/hash_table.h | 86 -------------------------------------------------- 6 files changed, 93 insertions(+), 93 deletions(-) create mode 100644 include/hash_table.h delete mode 100644 lib/util/hash_table.h diff --git a/COPYING.md b/COPYING.md index 0d2aa0c..d27ddaa 100644 --- a/COPYING.md +++ b/COPYING.md @@ -14,9 +14,9 @@ with the following exceptions: - `lib/sqfs/comp/zlib` contains files that have been extracted from the the zlib compression library and modified. See `lib/sqfs/comp/zlib/README` for details and `licenses/zlib.txt` for details. - - `lib/util/hash_table.*` and `lib/util/fast_urem_by_const.h` contain a hash - table implementation (MIT license). See `licenses/hash_table.txt` for - details. + - `lib/util/hash_table.c`, `include/hash_table.h` and + `lib/util/fast_urem_by_const.h` contain a hash table implementation (MIT + license). See `licenses/hash_table.txt` for details. The rest of squashfs-tools-ng is released under the terms and conditions of the **GNU General Public License version 3 or later**. diff --git a/include/hash_table.h b/include/hash_table.h new file mode 100644 index 0000000..ccbd9c0 --- /dev/null +++ b/include/hash_table.h @@ -0,0 +1,86 @@ +/* + * 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 + +struct hash_entry { + uint32_t hash; + const void *key; + void *data; +}; + +struct hash_table { + struct hash_entry *table; + uint32_t (*key_hash_function)(const void *key); + bool (*key_equals_function)(const void *a, const void *b); + const void *deleted_key; + uint32_t size; + uint32_t rehash; + uint64_t size_magic; + uint64_t rehash_magic; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +struct hash_table * +hash_table_create(uint32_t (*key_hash_function)(const void *key), + bool (*key_equals_function)(const void *a, + const void *b)); + +struct hash_table * +hash_table_clone(struct hash_table *src); +void hash_table_destroy(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)); + +struct hash_entry * +hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, + const void *key, void *data); +struct hash_entry * +hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, + const void *key); + +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/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am index 32b4c25..fffa502 100644 --- a/lib/sqfs/Makemodule.am +++ b/lib/sqfs/Makemodule.am @@ -36,7 +36,7 @@ libsquashfs_la_LIBADD += $(ZSTD_LIBS) $(PTHREAD_LIBS) # directly "import" stuff from libutil libsquashfs_la_SOURCES += lib/util/str_table.c lib/util/alloc.c libsquashfs_la_SOURCES += lib/util/xxhash.c -libsquashfs_la_SOURCES += lib/util/hash_table.c lib/util/hash_table.h +libsquashfs_la_SOURCES += lib/util/hash_table.c include/hash_table.h if WINDOWS libsquashfs_la_SOURCES += lib/sqfs/win32/io_file.c diff --git a/lib/sqfs/frag_table.c b/lib/sqfs/frag_table.c index 59811bb..366cb85 100644 --- a/lib/sqfs/frag_table.c +++ b/lib/sqfs/frag_table.c @@ -14,7 +14,7 @@ #include "sqfs/block.h" #include "compat.h" -#include "lib/util/hash_table.h" +#include "hash_table.h" #include #include diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index 70a11c1..68f5e8d 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -1,8 +1,8 @@ -libutil_a_SOURCES = include/util.h include/str_table.h +libutil_a_SOURCES = include/util.h include/str_table.h include/hash_table.h libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c libutil_a_SOURCES += lib/util/rbtree.c include/rbtree.h libutil_a_SOURCES += lib/util/xxhash.c lib/util/hash_table.c -libutil_a_SOURCES += lib/util/hash_table.h lib/util/fast_urem_by_const.h +libutil_a_SOURCES += lib/util/fast_urem_by_const.h libutil_a_CFLAGS = $(AM_CFLAGS) libutil_a_CPPFLAGS = $(AM_CPPFLAGS) diff --git a/lib/util/hash_table.h b/lib/util/hash_table.h deleted file mode 100644 index ccbd9c0..0000000 --- a/lib/util/hash_table.h +++ /dev/null @@ -1,86 +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 - -struct hash_entry { - uint32_t hash; - const void *key; - void *data; -}; - -struct hash_table { - struct hash_entry *table; - uint32_t (*key_hash_function)(const void *key); - bool (*key_equals_function)(const void *a, const void *b); - const void *deleted_key; - uint32_t size; - uint32_t rehash; - uint64_t size_magic; - uint64_t rehash_magic; - uint32_t max_entries; - uint32_t size_index; - uint32_t entries; - uint32_t deleted_entries; -}; - -struct hash_table * -hash_table_create(uint32_t (*key_hash_function)(const void *key), - bool (*key_equals_function)(const void *a, - const void *b)); - -struct hash_table * -hash_table_clone(struct hash_table *src); -void hash_table_destroy(struct hash_table *ht, - void (*delete_function)(struct hash_entry *entry)); - -struct hash_entry * -hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, - const void *key, void *data); -struct hash_entry * -hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, - const void *key); - -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 */ -- cgit v1.2.3