aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authordec05eba <dec05eba@protonmail.com>2020-01-22 01:47:59 +0100
committerdec05eba <dec05eba@protonmail.com>2020-01-22 01:47:59 +0100
commit88244bd3070399ba62d79bae6dfdf8b09ff8406d (patch)
tree6e9f7c5a27fe9c2dc2231b9bc32ea01c3a11d2ac /src
parentdea77dd862e71cffb2ebab5079df20e0ebaeddf5 (diff)
Add get_or_create method for hash map, more efficient than checking and then creating
Diffstat (limited to 'src')
-rw-r--r--src/std/hash_map.c50
1 files changed, 47 insertions, 3 deletions
diff --git a/src/std/hash_map.c b/src/std/hash_map.c
index 80fd059..44d36db 100644
--- a/src/std/hash_map.c
+++ b/src/std/hash_map.c
@@ -45,9 +45,16 @@ void tsl_hash_map_deinit(TslHashMap *self) {
free(self->buckets_data);
}
-static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash, const TslStringView *key, size_t size, const void *data) {
+/* TODO: Remove if (data) and if (output) */
+static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash, const TslStringView *key, size_t size, const void *data, void **output) {
TslHashMapNode *next_node;
+ /*
+ TODO: Instead of allocating space for the data, allow the user to pass a pointer in the insert
+ method and use that directly.
+ */
uint8_t *node_data = malloc(sizeof(hash) + sizeof(key->size) + key->size + sizeof(size) + size);
+ if(output)
+ *output = node_data;
if(!node_data) {
fprintf(stderr, "Error: hash map append failed. Reason: out of memory\n");
return 0;
@@ -56,6 +63,8 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
next_node = malloc(sizeof(TslHashMapNode));
if(!next_node) {
free(node_data);
+ if(output)
+ *output = NULL;
fprintf(stderr, "Error: hash map append failed. Reason: out of memory\n");
return 0;
}
@@ -64,7 +73,8 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
memcpy(node_data + sizeof(hash), &key->size, sizeof(key->size));
memcpy(node_data + sizeof(hash) + sizeof(key->size), key->data, key->size);
memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size, &size, sizeof(size));
- memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size + sizeof(size), data, size);
+ if(data)
+ memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size + sizeof(size), data, size);
next_node->data = node_data;
if(*head_node) {
@@ -78,6 +88,7 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
}
static size_t tsl_hash_map_get_index(TslHashMap *self, uint64_t hash) {
+ assert((self->buckets_capacity >> 3) > 0);
/* >>3 = 8 = sizeof(TslHashMapNode*) */
return hash & ((self->buckets_capacity >> 3) - 1);
}
@@ -176,7 +187,7 @@ int tsl_hash_map_insert(TslHashMap *self, const TslStringView *key, const void *
index = tsl_hash_map_get_index(self, hash);
bucket = (TslHashMapNode**)self->buckets_data + index;
- return tsl_hash_map_append_bucket(bucket, hash, key, size, data);
+ return tsl_hash_map_append_bucket(bucket, hash, key, size, data, NULL);
}
void* tsl_hash_map_get(TslHashMap *self, const TslStringView *key, TslHashFunc hash_func) {
@@ -202,3 +213,36 @@ void* tsl_hash_map_get(TslHashMap *self, const TslStringView *key, TslHashFunc h
return NULL;
}
+
+int tsl_hash_map_get_or_create(TslHashMap *self, const TslStringView *key, size_t size, TslHashFunc hash_func, void **output) {
+ uint64_t hash;
+ size_t index;
+ TslHashMapNode **bucket;
+ TslHashMapNode *node;
+ assert(size > 0);
+ if(self->buckets_capacity == 0) {
+ if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self)) {
+ *output = NULL;
+ return 0;
+ }
+ }
+
+ hash = hash_func(key->data, key->size);
+ index = tsl_hash_map_get_index(self, hash);
+ bucket = (TslHashMapNode**)self->buckets_data + index;
+ node = *bucket;
+ while(node) {
+ uint64_t node_hash;
+ TslStringView node_key;
+ size_t node_size;
+ uint8_t *node_data;
+ hash_map_node_get(node, &node_hash, &node_key, &node_size, &node_data);
+ if(hash == node_hash && key->size == node_key.size && memcmp(key->data, node_key.data, node_key.size) == 0) {
+ *output = node_data;
+ return 1;
+ }
+ node = node->next;
+ }
+
+ return tsl_hash_map_append_bucket(bucket, hash, key, size, NULL, output);
+}