summaryrefslogtreecommitdiffstats
path: root/zix/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'zix/hash.c')
-rw-r--r--zix/hash.c287
1 files changed, 141 insertions, 146 deletions
diff --git a/zix/hash.c b/zix/hash.c
index 35eaf24..34464d4 100644
--- a/zix/hash.c
+++ b/zix/hash.c
@@ -25,109 +25,107 @@
from powers of two as possible.
*/
static const unsigned sizes[] = {
- 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
- 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
- 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
-};
+ 53, 97, 193, 389, 769, 1543, 3079,
+ 6151, 12289, 24593, 49157, 98317, 196613, 393241,
+ 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
+ 100663319, 201326611, 402653189, 805306457, 1610612741, 0};
typedef struct ZixHashEntry {
- struct ZixHashEntry* next; ///< Next entry in bucket
- uint32_t hash; ///< Non-modulo hash value
- // Value follows here (access with zix_hash_value)
+ struct ZixHashEntry* next; ///< Next entry in bucket
+ uint32_t hash; ///< Non-modulo hash value
+ // Value follows here (access with zix_hash_value)
} ZixHashEntry;
struct ZixHashImpl {
- ZixHashFunc hash_func;
- ZixEqualFunc equal_func;
- ZixHashEntry** buckets;
- const unsigned* n_buckets;
- size_t value_size;
- unsigned count;
+ ZixHashFunc hash_func;
+ ZixEqualFunc equal_func;
+ ZixHashEntry** buckets;
+ const unsigned* n_buckets;
+ size_t value_size;
+ unsigned count;
};
static inline void*
zix_hash_value(ZixHashEntry* entry)
{
- return entry + 1;
+ return entry + 1;
}
ZixHash*
-zix_hash_new(ZixHashFunc hash_func,
- ZixEqualFunc equal_func,
- size_t value_size)
+zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size)
{
- ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
- if (hash) {
- hash->hash_func = hash_func;
- hash->equal_func = equal_func;
- hash->n_buckets = &sizes[0];
- hash->value_size = value_size;
- hash->count = 0;
- if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
- sizeof(ZixHashEntry*)))) {
- free(hash);
- return NULL;
- }
- }
- return hash;
+ ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
+ if (hash) {
+ hash->hash_func = hash_func;
+ hash->equal_func = equal_func;
+ hash->n_buckets = &sizes[0];
+ hash->value_size = value_size;
+ hash->count = 0;
+ if (!(hash->buckets =
+ (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) {
+ free(hash);
+ return NULL;
+ }
+ }
+ return hash;
}
void
zix_hash_free(ZixHash* hash)
{
- if (!hash) {
- return;
- }
-
- for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- ZixHashEntry* bucket = hash->buckets[b];
- for (ZixHashEntry* e = bucket; e;) {
- ZixHashEntry* next = e->next;
- free(e);
- e = next;
- }
- }
-
- free(hash->buckets);
- free(hash);
+ if (!hash) {
+ return;
+ }
+
+ for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ ZixHashEntry* bucket = hash->buckets[b];
+ for (ZixHashEntry* e = bucket; e;) {
+ ZixHashEntry* next = e->next;
+ free(e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ free(hash);
}
size_t
zix_hash_size(const ZixHash* hash)
{
- return hash->count;
+ return hash->count;
}
static inline void
insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
{
- entry->next = *bucket;
- *bucket = entry;
+ entry->next = *bucket;
+ *bucket = entry;
}
static inline ZixStatus
rehash(ZixHash* hash, unsigned new_n_buckets)
{
- ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(
- new_n_buckets, sizeof(ZixHashEntry*));
- if (!new_buckets) {
- return ZIX_STATUS_NO_MEM;
- }
-
- const unsigned old_n_buckets = *hash->n_buckets;
- for (unsigned b = 0; b < old_n_buckets; ++b) {
- for (ZixHashEntry* e = hash->buckets[b]; e;) {
- ZixHashEntry* const next = e->next;
- const unsigned h = e->hash % new_n_buckets;
- insert_entry(&new_buckets[h], e);
- e = next;
- }
- }
-
- free(hash->buckets);
- hash->buckets = new_buckets;
-
- return ZIX_STATUS_SUCCESS;
+ ZixHashEntry** new_buckets =
+ (ZixHashEntry**)calloc(new_n_buckets, sizeof(ZixHashEntry*));
+ if (!new_buckets) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ const unsigned old_n_buckets = *hash->n_buckets;
+ for (unsigned b = 0; b < old_n_buckets; ++b) {
+ for (ZixHashEntry* e = hash->buckets[b]; e;) {
+ ZixHashEntry* const next = e->next;
+ const unsigned h = e->hash % new_n_buckets;
+ insert_entry(&new_buckets[h], e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ hash->buckets = new_buckets;
+
+ return ZIX_STATUS_SUCCESS;
}
static inline ZixHashEntry*
@@ -136,100 +134,97 @@ find_entry(const ZixHash* hash,
const unsigned h,
const unsigned h_nomod)
{
- for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
- if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
- return e;
- }
- }
- return NULL;
+ for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
+ if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
+ return e;
+ }
+ }
+ return NULL;
}
void*
zix_hash_find(const ZixHash* hash, const void* value)
{
- const unsigned h_nomod = hash->hash_func(value);
- const unsigned h = h_nomod % *hash->n_buckets;
- ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod);
- return entry ? zix_hash_value(entry) : 0;
+ const unsigned h_nomod = hash->hash_func(value);
+ const unsigned h = h_nomod % *hash->n_buckets;
+ ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod);
+ return entry ? zix_hash_value(entry) : 0;
}
ZixStatus
zix_hash_insert(ZixHash* hash, const void* value, void** inserted)
{
- unsigned h_nomod = hash->hash_func(value);
- unsigned h = h_nomod % *hash->n_buckets;
-
- ZixHashEntry* elem = find_entry(hash, value, h, h_nomod);
- if (elem) {
- assert(elem->hash == h_nomod);
- if (inserted) {
- *inserted = zix_hash_value(elem);
- }
- return ZIX_STATUS_EXISTS;
- }
-
- elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
- if (!elem) {
- return ZIX_STATUS_NO_MEM;
- }
- elem->next = NULL;
- elem->hash = h_nomod;
- memcpy(elem + 1, value, hash->value_size);
-
- const unsigned next_n_buckets = *(hash->n_buckets + 1);
- if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
- if (!rehash(hash, next_n_buckets)) {
- h = h_nomod % *(++hash->n_buckets);
- }
- }
-
- insert_entry(&hash->buckets[h], elem);
- ++hash->count;
- if (inserted) {
- *inserted = zix_hash_value(elem);
- }
- return ZIX_STATUS_SUCCESS;
+ unsigned h_nomod = hash->hash_func(value);
+ unsigned h = h_nomod % *hash->n_buckets;
+
+ ZixHashEntry* elem = find_entry(hash, value, h, h_nomod);
+ if (elem) {
+ assert(elem->hash == h_nomod);
+ if (inserted) {
+ *inserted = zix_hash_value(elem);
+ }
+ return ZIX_STATUS_EXISTS;
+ }
+
+ elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
+ if (!elem) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ elem->next = NULL;
+ elem->hash = h_nomod;
+ memcpy(elem + 1, value, hash->value_size);
+
+ const unsigned next_n_buckets = *(hash->n_buckets + 1);
+ if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
+ if (!rehash(hash, next_n_buckets)) {
+ h = h_nomod % *(++hash->n_buckets);
+ }
+ }
+
+ insert_entry(&hash->buckets[h], elem);
+ ++hash->count;
+ if (inserted) {
+ *inserted = zix_hash_value(elem);
+ }
+ return ZIX_STATUS_SUCCESS;
}
ZixStatus
zix_hash_remove(ZixHash* hash, const void* value)
{
- const unsigned h_nomod = hash->hash_func(value);
- const unsigned h = h_nomod % *hash->n_buckets;
-
- ZixHashEntry** next_ptr = &hash->buckets[h];
- for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
- if (h_nomod == e->hash &&
- hash->equal_func(zix_hash_value(e), value)) {
- *next_ptr = e->next;
- free(e);
- return ZIX_STATUS_SUCCESS;
- }
- next_ptr = &e->next;
- }
-
- if (hash->n_buckets != sizes) {
- const unsigned prev_n_buckets = *(hash->n_buckets - 1);
- if (hash->count - 1 <= prev_n_buckets) {
- if (!rehash(hash, prev_n_buckets)) {
- --hash->n_buckets;
- }
- }
- }
-
- --hash->count;
- return ZIX_STATUS_NOT_FOUND;
+ const unsigned h_nomod = hash->hash_func(value);
+ const unsigned h = h_nomod % *hash->n_buckets;
+
+ ZixHashEntry** next_ptr = &hash->buckets[h];
+ for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
+ if (h_nomod == e->hash && hash->equal_func(zix_hash_value(e), value)) {
+ *next_ptr = e->next;
+ free(e);
+ return ZIX_STATUS_SUCCESS;
+ }
+ next_ptr = &e->next;
+ }
+
+ if (hash->n_buckets != sizes) {
+ const unsigned prev_n_buckets = *(hash->n_buckets - 1);
+ if (hash->count - 1 <= prev_n_buckets) {
+ if (!rehash(hash, prev_n_buckets)) {
+ --hash->n_buckets;
+ }
+ }
+ }
+
+ --hash->count;
+ return ZIX_STATUS_NOT_FOUND;
}
void
-zix_hash_foreach(ZixHash* hash,
- ZixHashVisitFunc f,
- void* user_data)
+zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data)
{
- for (unsigned b = 0; b < *hash->n_buckets; ++b) {
- ZixHashEntry* bucket = hash->buckets[b];
- for (ZixHashEntry* e = bucket; e; e = e->next) {
- f(zix_hash_value(e), user_data);
- }
- }
+ for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ ZixHashEntry* bucket = hash->buckets[b];
+ for (ZixHashEntry* e = bucket; e; e = e->next) {
+ f(zix_hash_value(e), user_data);
+ }
+ }
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-02-03 12:49:27 +0000