summaryrefslogtreecommitdiff
path: root/lib/sqfs
diff options
context:
space:
mode:
Diffstat (limited to 'lib/sqfs')
-rw-r--r--lib/sqfs/Makemodule.am1
-rw-r--r--lib/sqfs/str_table.c174
-rw-r--r--lib/sqfs/str_table.h51
-rw-r--r--lib/sqfs/xattr_writer.c2
4 files changed, 227 insertions, 1 deletions
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 <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 <goliath@infraroot.at>
+ */
+#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 <stdlib.h>
#include <string.h>
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-01 21:41:58 +0000