aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/hashmap.c343
-rw-r--r--src/queue.c176
2 files changed, 519 insertions, 0 deletions
diff --git a/src/hashmap.c b/src/hashmap.c
new file mode 100644
index 0000000..c9fb315
--- /dev/null
+++ b/src/hashmap.c
@@ -0,0 +1,343 @@
+#include <bh/internal/hashmap.h>
+#include <stdlib.h>
+#include <string.h>
+
+bh_hashmap_t *bh_hashmap_new(bh_equal_cb_t equal,
+ bh_hash_cb_t hash)
+{
+ bh_hashmap_t *result;
+
+ result = malloc(sizeof(*result));
+ if (result)
+ bh_hashmap_init(result, equal, hash);
+
+ return result;
+}
+
+void bh_hashmap_free(bh_hashmap_t *hashmap)
+{
+ bh_hashmap_destroy(hashmap);
+ free(hashmap);
+}
+
+void bh_hashmap_init(bh_hashmap_t *hashmap,
+ bh_equal_cb_t equal,
+ bh_hash_cb_t hash)
+{
+ memset(hashmap, 0, sizeof(*hashmap));
+ hashmap->factor = 0.75f;
+ hashmap->equal = equal;
+ hashmap->hash = hash;
+}
+
+void bh_hashmap_destroy(bh_hashmap_t *hashmap)
+{
+ if (hashmap->capacity)
+ {
+ free(hashmap->data);
+ free(hashmap->psls);
+ }
+}
+
+void bh_hashmap_clear(bh_hashmap_t *hashmap)
+{
+ if (hashmap->capacity)
+ memset(hashmap->psls, 0, hashmap->capacity * sizeof(size_t));
+ hashmap->size = 0;
+}
+
+int bh_hashmap_reserve(bh_hashmap_t *hashmap,
+ size_t size)
+{
+ bh_hashmap_t other;
+ size_t capacity, max_capacity, threshold;
+
+ /* Calculate hashmap max capacity and capacity threshold */
+ capacity = hashmap->capacity;
+ threshold = hashmap->capacity * hashmap->factor;
+ max_capacity = ((size_t)-1) / sizeof(bh_hashmap_node_t);
+
+ /* New capacity can't be smaller then current hashmap size */
+ if (size < hashmap->size)
+ size = hashmap->size;
+
+ /* Find new hashmap capacity */
+ if (!size)
+ {
+ /* No capacity needed */
+ capacity = 0;
+ threshold = 0;
+ }
+ else if (size > threshold)
+ {
+ /* Bigger capacity needed - grow the hashmap */
+ while (size > threshold)
+ {
+ capacity = (capacity) ? (capacity * 2) : (16);
+ threshold = capacity * hashmap->factor;
+
+ /* Capacity can't be bigger than max capacity and overflow */
+ if (capacity > max_capacity || capacity < 16)
+ return -1;
+ }
+ }
+ else
+ {
+ /* Smaller capacity needed - shrink the hashmap */
+ while (size <= threshold / 2 && capacity > 16)
+ {
+ capacity /= 2;
+ threshold = capacity * hashmap->factor;
+ }
+ }
+
+ /* Prevent same size reallocation */
+ if (capacity == hashmap->capacity)
+ return 0;
+
+ /* Initialize new hashmap */
+ bh_hashmap_init(&other, hashmap->equal, hashmap->hash);
+ other.factor = hashmap->factor;
+
+ if (capacity)
+ {
+ void *iter;
+
+ /* Allocate new memory for the hashmap */
+ other.data = malloc(sizeof(*other.data) * capacity);
+
+ other.psls = malloc(sizeof(size_t) * capacity);
+ other.threshold = threshold;
+ other.capacity = capacity;
+
+ /* Check for allocations failure */
+ if (!other.data || !other.psls)
+ {
+ if (other.data)
+ free(other.data);
+ if (other.psls)
+ free(other.psls);
+ return -1;
+ }
+
+ /* Reset probe sequence lengths */
+ memset(other.psls, 0, sizeof(size_t) * other.capacity);
+
+ /* Iterate and insert data into hashmap */
+ iter = bh_hashmap_iter_next(hashmap, NULL);
+ while (iter)
+ {
+ void *key, *value;
+
+ key = bh_hashmap_iter_key(iter);
+ value = bh_hashmap_iter_value(iter);
+ bh_hashmap_insert(&other, key, value);
+
+ iter = bh_hashmap_iter_next(hashmap, iter);
+ }
+ }
+
+ /* Swap hashmaps */
+ bh_hashmap_destroy(hashmap);
+ *hashmap = other;
+ return 0;
+}
+
+int bh_hashmap_insert(bh_hashmap_t *hashmap,
+ void *key,
+ void *value)
+{
+ size_t bucket, psl, tmp_psl;
+ bh_hashmap_node_t item, tmp;
+
+ /* Try to stay below hashmap threshold */
+ if (hashmap->size + 1 > hashmap->threshold)
+ if (bh_hashmap_reserve(hashmap, hashmap->size + 1))
+ if (hashmap->size >= hashmap->capacity)
+ return -1;
+
+ /* Prepare inserted data and set PSL to 1 */
+ item.key = key;
+ item.value = value;
+ psl = 1;
+
+ /* Calculate prefered bucket index */
+ bucket = hashmap->hash(key) & (hashmap->capacity - 1);
+
+ /* Find empty bucket */
+ while (hashmap->psls[bucket])
+ {
+ /* Current bucket is richer then us - swap elements */
+ if (psl > hashmap->psls[bucket])
+ {
+ tmp = hashmap->data[bucket];
+ tmp_psl = hashmap->psls[bucket];
+ hashmap->data[bucket] = item;
+ hashmap->psls[bucket] = psl;
+ item = tmp;
+ psl = tmp_psl;
+ }
+
+ bucket = (bucket + 1) & (hashmap->capacity - 1);
+ psl++;
+ }
+
+ /* Found empty bucket - place item here */
+ hashmap->data[bucket] = item;
+ hashmap->psls[bucket] = psl;
+ hashmap->size++;
+
+ return 0;
+}
+
+void bh_hashmap_remove(bh_hashmap_t *hashmap,
+ void *key)
+{
+ void *iter;
+
+ iter = bh_hashmap_iter_at(hashmap, key);
+ if (iter)
+ bh_hashmap_iter_remove(hashmap, iter);
+}
+
+void *bh_hashmap_at(bh_hashmap_t *hashmap,
+ void *key,
+ int *exists)
+{
+ void *iter;
+
+ iter = bh_hashmap_iter_at(hashmap, key);
+ if (iter)
+ {
+ /* If exists flag passed - set to 1 */
+ if (exists)
+ *exists = 1;
+ return bh_hashmap_iter_value(iter);
+ }
+
+ /* If exists flag passed - set to 0 */
+ if (exists)
+ *exists = 0;
+ return NULL;
+}
+
+int bh_hashmap_empty(bh_hashmap_t *hashmap)
+{
+ return !hashmap->size;
+}
+
+size_t bh_hashmap_size(bh_hashmap_t *hashmap)
+{
+ return hashmap->size;
+}
+
+size_t bh_hashmap_capacity(bh_hashmap_t *hashmap)
+{
+ return hashmap->capacity;
+}
+
+float bh_hashmap_factor(bh_hashmap_t *hashmap)
+{
+ return hashmap->factor;
+}
+
+void bh_hashmap_set_factor(bh_hashmap_t *hashmap,
+ float factor)
+{
+ factor = (factor > 1.0f) ? (1.0f) : (factor);
+ factor = (factor < 0.15f) ? (0.15f) : (factor);
+
+ hashmap->factor = factor;
+ hashmap->threshold = hashmap->capacity * factor;
+}
+
+void *bh_hashmap_iter_at(bh_hashmap_t *hashmap,
+ void *key)
+{
+ size_t bucket, psl;
+
+ /* Nothing can be in empty map */
+ if (!hashmap->size)
+ return NULL;
+
+ /* Calculate prefered bucket index and set PSL to 1 */
+ bucket = hashmap->hash(key) & (hashmap->capacity - 1);
+ psl = 1;
+
+ /* Iterate hashmap until we find element or find richer bucket */
+ while (hashmap->psls[bucket] >= psl && hashmap->equal(hashmap->data[bucket].key, key))
+ {
+ bucket = (bucket + 1) & (hashmap->capacity - 1);
+ psl++;
+ }
+
+ /* If bucket is poorer or equal to us - we found our element */
+ if (hashmap->psls[bucket] >= psl)
+ return hashmap->data + bucket;
+
+ return NULL;
+}
+
+void *bh_hashmap_iter_next(bh_hashmap_t *hashmap,
+ void *iter)
+{
+ bh_hashmap_node_t *item;
+
+ item = (bh_hashmap_node_t *)iter;
+ while (1)
+ {
+ /* Advance or set iterator to the first element */
+ if (item)
+ item++;
+ else
+ item = hashmap->data;
+
+ /* Check iterator for validity */
+ if (item >= hashmap->data + hashmap->capacity)
+ return NULL;
+
+ /* Check iterator's item PSL */
+ if (hashmap->psls[item - hashmap->data])
+ return item;
+ }
+}
+
+void bh_hashmap_iter_remove(bh_hashmap_t *hashmap,
+ void *iter)
+{
+ size_t bucket, next_bucket;
+
+ /* Check if hashmap is empty or we are given NULL iterator */
+ if (!iter || !hashmap->size)
+ return;
+
+ /* Adjust hashmap size, calculate current and next bucket index */
+ hashmap->size--;
+ bucket = (bh_hashmap_node_t *)iter - hashmap->data;
+ next_bucket = (bucket + 1) & (hashmap->capacity - 1);
+
+ /* Shift all elements toward their preffered place */
+ while (hashmap->psls[next_bucket] > 1)
+ {
+ /* Copy item and adjust PSL */
+ hashmap->data[bucket] = hashmap->data[next_bucket];
+ hashmap->psls[bucket] = hashmap->psls[next_bucket] - 1;
+
+ /* Calculate next bucket index */
+ bucket = next_bucket;
+ next_bucket = (bucket + 1) & (hashmap->capacity - 1);
+ }
+
+ /* Reset bucket's PSL (mark empty) */
+ hashmap->psls[bucket] = 0;
+}
+
+void *bh_hashmap_iter_key(void *iter)
+{
+ return ((bh_hashmap_node_t *)iter)->key;
+}
+
+void *bh_hashmap_iter_value(void *iter)
+{
+ return ((bh_hashmap_node_t *)iter)->value;
+}
diff --git a/src/queue.c b/src/queue.c
new file mode 100644
index 0000000..8d48401
--- /dev/null
+++ b/src/queue.c
@@ -0,0 +1,176 @@
+#include <bh/internal/queue.h>
+#include <stdlib.h>
+#include <string.h>
+
+bh_queue_t *bh_queue_new(void)
+{
+ bh_queue_t *result;
+
+ result = malloc(sizeof(*result));
+ if (result)
+ bh_queue_init(result);
+
+ return result;
+}
+
+void bh_queue_free(bh_queue_t *queue)
+{
+ bh_queue_destroy(queue);
+ free(queue);
+}
+
+void bh_queue_init(bh_queue_t *queue)
+{
+ memset(queue, 0, sizeof(*queue));
+}
+
+void bh_queue_destroy(bh_queue_t *queue)
+{
+ if (queue->capacity)
+ free(queue->data);
+}
+
+void bh_queue_clear(bh_queue_t *queue)
+{
+ queue->head = 0;
+ queue->tail = 0;
+ queue->size = 0;
+}
+
+int bh_queue_reserve(bh_queue_t *queue,
+ size_t size)
+{
+ bh_queue_t other;
+
+ /* New capacity should be great or equal to current size */
+ if (size < queue->size)
+ size = queue->size;
+
+ /* New capacity should not exceed maximum capacity */
+ if (size > ((size_t)-1) / sizeof(void *))
+ return -1;
+
+ /* Prevent same size memory reallocation */
+ if (size == queue->capacity)
+ return 0;
+
+ /* Prepare new empty queue */
+ bh_queue_init(&other);
+ if (size)
+ {
+ void *iter;
+
+ /* Allocate new capacity for the queue */
+ other.data = malloc(size * sizeof(void *));
+ other.capacity = size;
+ if (!other.data)
+ return -1;
+
+ /* Iterate over old queue and insert data into new queue */
+ iter = bh_queue_iter_next(queue, NULL);
+ while (iter)
+ {
+ bh_queue_insert(&other, bh_queue_iter_value(iter));
+ iter = bh_queue_iter_next(queue, iter);
+ }
+ }
+
+ /* If old queue had allocated data - free it */
+ if (queue->capacity)
+ free(queue->data);
+
+ /* Copy queue information */
+ *queue = other;
+ return 0;
+}
+
+int bh_queue_insert(bh_queue_t *queue,
+ void *value)
+{
+ /* Check if queue can contain new element */
+ if (queue->size + 1 > queue->capacity)
+ {
+ size_t capacity;
+
+ /* Check potential size overflow and reserve capacity */
+ capacity = (queue->capacity) ? (queue->capacity * 2) : (16);
+ if (capacity < queue->capacity || bh_queue_reserve(queue, capacity))
+ return -1;
+ }
+
+ /* Increase queue size and advance tail index */
+ queue->data[queue->tail] = value;
+ queue->size++;
+ if (++queue->tail >= queue->capacity)
+ queue->tail = 0;
+
+ return 0;
+}
+
+void bh_queue_remove(bh_queue_t *queue)
+{
+ /* Do nothing if queue is empty */
+ if (!queue->size)
+ return;
+
+ /* Decrease queue size and advance head index */
+ queue->size--;
+ if (++queue->head >= queue->capacity)
+ queue->head = 0;
+}
+
+void *bh_queue_front(bh_queue_t *queue)
+{
+ /* Do nothing if queue is empty */
+ if (!queue->size)
+ return NULL;
+
+ /* Return front element */
+ return queue->data[queue->head];
+}
+
+int bh_queue_empty(bh_queue_t *queue)
+{
+ return !queue->size;
+}
+
+size_t bh_queue_size(bh_queue_t *queue)
+{
+ return queue->size;
+}
+
+size_t bh_queue_capacity(bh_queue_t *queue)
+{
+ return queue->capacity;
+}
+
+void *bh_queue_iter_next(bh_queue_t *queue,
+ void *iter)
+{
+ void **element = (void **)iter;
+
+ /* Do nothing if queue is empty */
+ if (!queue->size)
+ return NULL;
+
+ /* Advance or set iterator */
+ if (element)
+ {
+ element++;
+ if (element == queue->data + queue->capacity)
+ element = queue->data;
+
+ /* Check if we reached the end */
+ if (element == queue->data + queue->tail)
+ return NULL;
+ }
+ else
+ element = queue->data + queue->head;
+
+ return element;
+}
+
+void *bh_queue_iter_value(void *iter)
+{
+ return *(void **)iter;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-01 02:19:55 +0000