From 2d303a7f0a6076bbf5739bae4f0fa443d0da5203 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sun, 24 Nov 2019 17:26:33 +0100 Subject: Cleanup: completely move str_table into libsquashfs internals Signed-off-by: David Oberhollenzer --- lib/sqfs/Makemodule.am | 1 + lib/sqfs/str_table.c | 174 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/sqfs/str_table.h | 51 ++++++++++++++ lib/sqfs/xattr_writer.c | 2 +- lib/util/Makemodule.am | 3 +- lib/util/str_table.c | 174 ------------------------------------------------ 6 files changed, 228 insertions(+), 177 deletions(-) create mode 100644 lib/sqfs/str_table.c create mode 100644 lib/sqfs/str_table.h delete mode 100644 lib/util/str_table.c (limited to 'lib') diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am index c687d1c..be405cf 100644 --- a/lib/sqfs/Makemodule.am +++ b/lib/sqfs/Makemodule.am @@ -23,6 +23,7 @@ libsquashfs_la_SOURCES += lib/sqfs/write_super.c lib/sqfs/data_writer/block.c libsquashfs_la_SOURCES += lib/sqfs/data_writer/internal.h lib/sqfs/data_reader.c libsquashfs_la_SOURCES += lib/sqfs/data_writer/common.c libsquashfs_la_SOURCES += lib/sqfs/data_writer/fileapi.c +libsquashfs_la_SOURCES += lib/sqfs/str_table.c lib/sqfs/str_table.h libsquashfs_la_CPPFLAGS = $(AM_CPPFLAGS) libsquashfs_la_LDFLAGS = $(AM_LDFLAGS) libsquashfs_la_CFLAGS = $(AM_CFLAGS) $(PTHREAD_CFLAGS) $(ZLIB_CFLAGS) diff --git a/lib/sqfs/str_table.c b/lib/sqfs/str_table.c new file mode 100644 index 0000000..1ec0ef7 --- /dev/null +++ b/lib/sqfs/str_table.c @@ -0,0 +1,174 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * str_table.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include +#include +#include + +#include "sqfs/error.h" +#include "util/util.h" +#include "str_table.h" + +/* R5 hash function (borrowed from reiserfs) */ +static sqfs_u32 strhash(const char *s) +{ + const signed char *str = (const signed char *)s; + sqfs_u32 a = 0; + + while (*str != '\0') { + a += *str << 4; + a += *str >> 4; + a *= 11; + str++; + } + + return a; +} + +static int strings_grow(str_table_t *table) +{ + size_t newsz; + void *new; + + if (table->num_strings < table->max_strings) + return 0; + + newsz = table->max_strings ? (table->max_strings * 2) : 16; + new = realloc(table->strings, sizeof(table->strings[0]) * newsz); + + if (new == NULL) + return SQFS_ERROR_ALLOC; + + table->strings = new; + table->max_strings = newsz; + return 0; +} + +int str_table_init(str_table_t *table, size_t size) +{ + memset(table, 0, sizeof(*table)); + + table->buckets = alloc_array(size, sizeof(table->buckets[0])); + table->num_buckets = size; + + if (table->buckets == NULL) + return SQFS_ERROR_ALLOC; + + return 0; +} + +void str_table_cleanup(str_table_t *table) +{ + str_bucket_t *bucket; + size_t i; + + for (i = 0; i < table->num_buckets; ++i) { + while (table->buckets[i] != NULL) { + bucket = table->buckets[i]; + table->buckets[i] = bucket->next; + + free(bucket->str); + free(bucket); + } + } + + free(table->buckets); + free(table->strings); + memset(table, 0, sizeof(*table)); +} + +int str_table_get_index(str_table_t *table, const char *str, size_t *idx) +{ + str_bucket_t *bucket; + sqfs_u32 hash; + size_t index; + int err; + + hash = strhash(str); + index = hash % table->num_buckets; + bucket = table->buckets[index]; + + while (bucket != NULL) { + if (strcmp(bucket->str, str) == 0) { + *idx = bucket->index; + return 0; + } + + bucket = bucket->next; + } + + err = strings_grow(table); + if (err) + return err; + + bucket = calloc(1, sizeof(*bucket)); + if (bucket == NULL) + goto fail_oom; + + bucket->str = strdup(str); + if (bucket->str == NULL) + goto fail_oom; + + bucket->index = table->num_strings; + table->strings[table->num_strings++] = bucket->str; + *idx = bucket->index; + + bucket->next = table->buckets[index]; + table->buckets[index] = bucket; + return 0; +fail_oom: + free(bucket); + return SQFS_ERROR_ALLOC; +} + +const char *str_table_get_string(str_table_t *table, size_t index) +{ + if (index >= table->num_strings) + return NULL; + + return table->strings[index]; +} + +static str_bucket_t *bucket_by_index(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = NULL; + sqfs_u32 hash; + + if (index < table->num_strings) { + hash = strhash(table->strings[index]); + bucket = table->buckets[hash % table->num_buckets]; + + while (bucket != NULL && bucket->index != index) + bucket = bucket->next; + } + + return bucket; +} + +void str_table_add_ref(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + if (bucket != NULL && bucket->refcount < ~((size_t)0)) + bucket->refcount += 1; +} + +void str_table_del_ref(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + if (bucket != NULL && bucket->refcount > 0) + bucket->refcount -= 1; +} + +size_t str_table_get_ref_count(str_table_t *table, size_t index) +{ + str_bucket_t *bucket = bucket_by_index(table, index); + + return bucket != NULL ? bucket->refcount : 0; +} diff --git a/lib/sqfs/str_table.h b/lib/sqfs/str_table.h new file mode 100644 index 0000000..61f8aa5 --- /dev/null +++ b/lib/sqfs/str_table.h @@ -0,0 +1,51 @@ +/* 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" + +typedef struct str_bucket_t { + struct str_bucket_t *next; + char *str; + size_t index; + size_t refcount; +} 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 { + str_bucket_t **buckets; + size_t num_buckets; + + char **strings; + size_t num_strings; + size_t max_strings; +} str_table_t; + +/* `size` is the number of hash table buckets to use internally. */ +SQFS_INTERNAL int str_table_init(str_table_t *table, size_t size); + +SQFS_INTERNAL void str_table_cleanup(str_table_t *table); + +/* 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(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(str_table_t *table, size_t index); + +#endif /* STR_TABLE_H */ diff --git a/lib/sqfs/xattr_writer.c b/lib/sqfs/xattr_writer.c index 81ee26c..2e6a074 100644 --- a/lib/sqfs/xattr_writer.c +++ b/lib/sqfs/xattr_writer.c @@ -15,8 +15,8 @@ #include "sqfs/block.h" #include "sqfs/io.h" -#include "util/str_table.h" #include "util/util.h" +#include "str_table.h" #include #include diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index 07e94e2..426e088 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -1,5 +1,4 @@ -libutil_la_SOURCES = include/util/util.h include/util/str_table.h -libutil_la_SOURCES += lib/util/str_table.c lib/util/alloc.c +libutil_la_SOURCES = include/util/util.h lib/util/alloc.c libutil_la_CFLAGS = $(AM_CFLAGS) libutil_la_CPPFLAGS = $(AM_CPPFLAGS) libutil_la_LDFLAGS = $(AM_LDFLAGS) diff --git a/lib/util/str_table.c b/lib/util/str_table.c deleted file mode 100644 index 513b243..0000000 --- a/lib/util/str_table.c +++ /dev/null @@ -1,174 +0,0 @@ -/* SPDX-License-Identifier: LGPL-3.0-or-later */ -/* - * str_table.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#include "config.h" - -#include -#include -#include - -#include "sqfs/error.h" -#include "util/str_table.h" -#include "util/util.h" - -/* R5 hash function (borrowed from reiserfs) */ -static sqfs_u32 strhash(const char *s) -{ - const signed char *str = (const signed char *)s; - sqfs_u32 a = 0; - - while (*str != '\0') { - a += *str << 4; - a += *str >> 4; - a *= 11; - str++; - } - - return a; -} - -static int strings_grow(str_table_t *table) -{ - size_t newsz; - void *new; - - if (table->num_strings < table->max_strings) - return 0; - - newsz = table->max_strings ? (table->max_strings * 2) : 16; - new = realloc(table->strings, sizeof(table->strings[0]) * newsz); - - if (new == NULL) - return SQFS_ERROR_ALLOC; - - table->strings = new; - table->max_strings = newsz; - return 0; -} - -int str_table_init(str_table_t *table, size_t size) -{ - memset(table, 0, sizeof(*table)); - - table->buckets = alloc_array(size, sizeof(table->buckets[0])); - table->num_buckets = size; - - if (table->buckets == NULL) - return SQFS_ERROR_ALLOC; - - return 0; -} - -void str_table_cleanup(str_table_t *table) -{ - str_bucket_t *bucket; - size_t i; - - for (i = 0; i < table->num_buckets; ++i) { - while (table->buckets[i] != NULL) { - bucket = table->buckets[i]; - table->buckets[i] = bucket->next; - - free(bucket->str); - free(bucket); - } - } - - free(table->buckets); - free(table->strings); - memset(table, 0, sizeof(*table)); -} - -int str_table_get_index(str_table_t *table, const char *str, size_t *idx) -{ - str_bucket_t *bucket; - sqfs_u32 hash; - size_t index; - int err; - - hash = strhash(str); - index = hash % table->num_buckets; - bucket = table->buckets[index]; - - while (bucket != NULL) { - if (strcmp(bucket->str, str) == 0) { - *idx = bucket->index; - return 0; - } - - bucket = bucket->next; - } - - err = strings_grow(table); - if (err) - return err; - - bucket = calloc(1, sizeof(*bucket)); - if (bucket == NULL) - goto fail_oom; - - bucket->str = strdup(str); - if (bucket->str == NULL) - goto fail_oom; - - bucket->index = table->num_strings; - table->strings[table->num_strings++] = bucket->str; - *idx = bucket->index; - - bucket->next = table->buckets[index]; - table->buckets[index] = bucket; - return 0; -fail_oom: - free(bucket); - return SQFS_ERROR_ALLOC; -} - -const char *str_table_get_string(str_table_t *table, size_t index) -{ - if (index >= table->num_strings) - return NULL; - - return table->strings[index]; -} - -static str_bucket_t *bucket_by_index(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = NULL; - sqfs_u32 hash; - - if (index < table->num_strings) { - hash = strhash(table->strings[index]); - bucket = table->buckets[hash % table->num_buckets]; - - while (bucket != NULL && bucket->index != index) - bucket = bucket->next; - } - - return bucket; -} - -void str_table_add_ref(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - if (bucket != NULL && bucket->refcount < ~((size_t)0)) - bucket->refcount += 1; -} - -void str_table_del_ref(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - if (bucket != NULL && bucket->refcount > 0) - bucket->refcount -= 1; -} - -size_t str_table_get_ref_count(str_table_t *table, size_t index) -{ - str_bucket_t *bucket = bucket_by_index(table, index); - - return bucket != NULL ? bucket->refcount : 0; -} -- cgit v1.2.3