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 +- 4 files changed, 227 insertions(+), 1 deletion(-) create mode 100644 lib/sqfs/str_table.c create mode 100644 lib/sqfs/str_table.h (limited to 'lib/sqfs') 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 -- cgit v1.2.3