diff options
Diffstat (limited to 'src/lib')
| -rw-r--r-- | src/lib/hash.c | 135 | ||||
| -rw-r--r-- | src/lib/hashmap.c | 327 | ||||
| -rw-r--r-- | src/lib/list.c | 32 | ||||
| -rw-r--r-- | src/lib/queue.c | 61 |
4 files changed, 555 insertions, 0 deletions
diff --git a/src/lib/hash.c b/src/lib/hash.c new file mode 100644 index 0000000..392f79d --- /dev/null +++ b/src/lib/hash.c @@ -0,0 +1,135 @@ +//----------------------------------------------------------------------------- +// xxHash Library +// Copyright (c) 2012-2021 Yann Collet +// Copyright (c) 2023 Marvin Borner +// All rights reserved. +// +// BSD 2-Clause License (https://www.opensource.org/licenses/bsd-license.php) +// +// xxHash3 +//----------------------------------------------------------------------------- + +#include <string.h> + +#include <lib/hash.h> + +#define XXH_PRIME_1 11400714785074694791ULL +#define XXH_PRIME_2 14029467366897019727ULL +#define XXH_PRIME_3 1609587929392839161ULL +#define XXH_PRIME_4 9650029242287828579ULL +#define XXH_PRIME_5 2870177450012600261ULL + +static uint64_t XXH_read64(void *memptr) +{ + uint64_t val; + memcpy(&val, memptr, sizeof(val)); + return val; +} + +static uint32_t XXH_read32(void *memptr) +{ + uint32_t val; + memcpy(&val, memptr, sizeof(val)); + return val; +} + +static uint64_t XXH_rotl64(uint64_t x, int r) +{ + return (x << r) | (x >> (64 - r)); +} + +hash_t hash(void *data, size_t len, uint64_t seed) +{ + uint8_t *p = (uint8_t *)data; + uint8_t *end = p + len; + uint64_t h64; + + if (len >= 32) { + uint8_t *limit = end - 32; + uint64_t v1 = seed + XXH_PRIME_1 + XXH_PRIME_2; + uint64_t v2 = seed + XXH_PRIME_2; + uint64_t v3 = seed + 0; + uint64_t v4 = seed - XXH_PRIME_1; + + do { + v1 += XXH_read64(p) * XXH_PRIME_2; + v1 = XXH_rotl64(v1, 31); + v1 *= XXH_PRIME_1; + + v2 += XXH_read64(p + 8) * XXH_PRIME_2; + v2 = XXH_rotl64(v2, 31); + v2 *= XXH_PRIME_1; + + v3 += XXH_read64(p + 16) * XXH_PRIME_2; + v3 = XXH_rotl64(v3, 31); + v3 *= XXH_PRIME_1; + + v4 += XXH_read64(p + 24) * XXH_PRIME_2; + v4 = XXH_rotl64(v4, 31); + v4 *= XXH_PRIME_1; + + p += 32; + } while (p <= limit); + + h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); + + v1 *= XXH_PRIME_2; + v1 = XXH_rotl64(v1, 31); + v1 *= XXH_PRIME_1; + h64 ^= v1; + h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4; + + v2 *= XXH_PRIME_2; + v2 = XXH_rotl64(v2, 31); + v2 *= XXH_PRIME_1; + h64 ^= v2; + h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4; + + v3 *= XXH_PRIME_2; + v3 = XXH_rotl64(v3, 31); + v3 *= XXH_PRIME_1; + h64 ^= v3; + h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4; + + v4 *= XXH_PRIME_2; + v4 = XXH_rotl64(v4, 31); + v4 *= XXH_PRIME_1; + h64 ^= v4; + h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4; + } else { + h64 = seed + XXH_PRIME_5; + } + + h64 += (uint64_t)len; + + while (p + 8 <= end) { + uint64_t k1 = XXH_read64(p); + k1 *= XXH_PRIME_2; + k1 = XXH_rotl64(k1, 31); + k1 *= XXH_PRIME_1; + h64 ^= k1; + h64 = XXH_rotl64(h64, 27) * XXH_PRIME_1 + XXH_PRIME_4; + p += 8; + } + + if (p + 4 <= end) { + h64 ^= (uint64_t)(XXH_read32(p)) * XXH_PRIME_1; + h64 = XXH_rotl64(h64, 23) * XXH_PRIME_2 + XXH_PRIME_3; + p += 4; + } + + while (p < end) { + h64 ^= (*p) * XXH_PRIME_5; + h64 = XXH_rotl64(h64, 11) * XXH_PRIME_1; + p++; + } + + h64 ^= h64 >> 33; + h64 *= XXH_PRIME_2; + h64 ^= h64 >> 29; + h64 *= XXH_PRIME_3; + h64 ^= h64 >> 32; + + return h64; +} diff --git a/src/lib/hashmap.c b/src/lib/hashmap.c new file mode 100644 index 0000000..7de7245 --- /dev/null +++ b/src/lib/hashmap.c @@ -0,0 +1,327 @@ +// Copyright 2020 Joshua J Baker. All rights reserved. +// Copyright 2023 Marvin Borner +// Use of this source code is governed by an MIT-style +// license that can be found in the LICENSE file. + +// This is a fork of tidwall's hashmap. It's heavily reduced and adapted. + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <stddef.h> + +#include <lib/hashmap.h> +#include <lib/hash.h> + +#define GROW_AT 0.60 +#define SHRINK_AT 0.10 + +struct bucket { + uint64_t hash : 48; + uint64_t dib : 16; +}; + +struct hashmap { + size_t elsize; + size_t cap; + void (*elfree)(void *item); + size_t bucketsz; + size_t nbuckets; + size_t count; + size_t mask; + size_t growat; + size_t shrinkat; + uint8_t growpower; + bool oom; + void *buckets; + void *spare; + void *edata; +}; + +void hashmap_set_grow_by_power(struct hashmap *map, size_t power) +{ + map->growpower = power < 1 ? 1 : power > 16 ? 16 : power; +} + +static struct bucket *bucket_at0(void *buckets, size_t bucketsz, size_t i) +{ + return (struct bucket *)(((char *)buckets) + (bucketsz * i)); +} + +static struct bucket *bucket_at(struct hashmap *map, size_t index) +{ + return bucket_at0(map->buckets, map->bucketsz, index); +} + +static void *bucket_item(struct bucket *entry) +{ + return ((char *)entry) + sizeof(struct bucket); +} + +static uint64_t clip_hash(uint64_t hash) +{ + return hash & 0xFFFFFFFFFFFF; +} + +struct hashmap *hashmap_new(size_t elsize, size_t cap, + void (*elfree)(void *item)) +{ + size_t ncap = 16; + if (cap < ncap) { + cap = ncap; + } else { + while (ncap < cap) { + ncap *= 2; + } + cap = ncap; + } + size_t bucketsz = sizeof(struct bucket) + elsize; + while (bucketsz & (sizeof(uintptr_t) - 1)) { + bucketsz++; + } + // hashmap + spare + edata + size_t size = sizeof(struct hashmap) + bucketsz * 2; + struct hashmap *map = malloc(size); + if (!map) { + return NULL; + } + memset(map, 0, sizeof(struct hashmap)); + map->elsize = elsize; + map->bucketsz = bucketsz; + map->elfree = elfree; + map->spare = ((char *)map) + sizeof(struct hashmap); + map->edata = (char *)map->spare + bucketsz; + map->cap = cap; + map->nbuckets = cap; + map->mask = map->nbuckets - 1; + map->buckets = malloc(map->bucketsz * map->nbuckets); + if (!map->buckets) { + free(map); + return NULL; + } + memset(map->buckets, 0, map->bucketsz * map->nbuckets); + map->growpower = 1; + map->growat = map->nbuckets * GROW_AT; + map->shrinkat = map->nbuckets * SHRINK_AT; + return map; +} + +static void free_elements(struct hashmap *map) +{ + if (!map->elfree) + return; + + for (size_t i = 0; i < map->nbuckets; i++) { + struct bucket *bucket = bucket_at(map, i); + if (bucket->dib) + map->elfree(bucket_item(bucket)); + } +} + +void hashmap_clear(struct hashmap *map, bool update_cap) +{ + map->count = 0; + free_elements(map); + if (update_cap) { + map->cap = map->nbuckets; + } else if (map->nbuckets != map->cap) { + void *new_buckets = malloc(map->bucketsz * map->cap); + if (new_buckets) { + free(map->buckets); + map->buckets = new_buckets; + } + map->nbuckets = map->cap; + } + memset(map->buckets, 0, map->bucketsz * map->nbuckets); + map->mask = map->nbuckets - 1; + map->growat = map->nbuckets * 0.75; + map->shrinkat = map->nbuckets * 0.10; +} + +static bool resize0(struct hashmap *map, size_t new_cap) +{ + struct hashmap *map2 = hashmap_new(map->elsize, new_cap, map->elfree); + if (!map2) + return false; + for (size_t i = 0; i < map->nbuckets; i++) { + struct bucket *entry = bucket_at(map, i); + if (!entry->dib) { + continue; + } + entry->dib = 1; + size_t j = entry->hash & map2->mask; + while (1) { + struct bucket *bucket = bucket_at(map2, j); + if (bucket->dib == 0) { + memcpy(bucket, entry, map->bucketsz); + break; + } + if (bucket->dib < entry->dib) { + memcpy(map2->spare, bucket, map->bucketsz); + memcpy(bucket, entry, map->bucketsz); + memcpy(entry, map2->spare, map->bucketsz); + } + j = (j + 1) & map2->mask; + entry->dib += 1; + } + } + free(map->buckets); + map->buckets = map2->buckets; + map->nbuckets = map2->nbuckets; + map->mask = map2->mask; + map->growat = map2->growat; + map->shrinkat = map2->shrinkat; + free(map2); + return true; +} + +static bool resize(struct hashmap *map, size_t new_cap) +{ + return resize0(map, new_cap); +} + +void *hashmap_set(struct hashmap *map, void *item, uint64_t hash) +{ + hash = clip_hash(hash); + map->oom = false; + if (map->count == map->growat) { + if (!resize(map, map->nbuckets * (1 << map->growpower))) { + map->oom = true; + return NULL; + } + } + + struct bucket *entry = map->edata; + entry->hash = hash; + entry->dib = 1; + void *eitem = bucket_item(entry); + memcpy(eitem, item, map->elsize); + + void *bitem; + size_t i = entry->hash & map->mask; + while (1) { + struct bucket *bucket = bucket_at(map, i); + if (bucket->dib == 0) { + memcpy(bucket, entry, map->bucketsz); + map->count++; + return NULL; + } + bitem = bucket_item(bucket); + if (entry->hash == bucket->hash) { + memcpy(map->spare, bitem, map->elsize); + memcpy(bitem, eitem, map->elsize); + return map->spare; + } + if (bucket->dib < entry->dib) { + memcpy(map->spare, bucket, map->bucketsz); + memcpy(bucket, entry, map->bucketsz); + memcpy(entry, map->spare, map->bucketsz); + eitem = bucket_item(entry); + } + i = (i + 1) & map->mask; + entry->dib += 1; + } +} + +void *hashmap_get(struct hashmap *map, uint64_t hash) +{ + hash = clip_hash(hash); + size_t i = hash & map->mask; + while (1) { + struct bucket *bucket = bucket_at(map, i); + if (!bucket->dib) + return NULL; + if (bucket->hash == hash) + return bucket_item(bucket); + i = (i + 1) & map->mask; + } +} + +void *hashmap_probe(struct hashmap *map, uint64_t position) +{ + size_t i = position & map->mask; + struct bucket *bucket = bucket_at(map, i); + if (!bucket->dib) { + return NULL; + } + return bucket_item(bucket); +} + +void *hashmap_delete(struct hashmap *map, uint64_t hash) +{ + hash = clip_hash(hash); + map->oom = false; + size_t i = hash & map->mask; + while (1) { + struct bucket *bucket = bucket_at(map, i); + if (!bucket->dib) + return NULL; + void *bitem = bucket_item(bucket); + if (bucket->hash == hash) { + memcpy(map->spare, bitem, map->elsize); + bucket->dib = 0; + while (1) { + struct bucket *prev = bucket; + i = (i + 1) & map->mask; + bucket = bucket_at(map, i); + if (bucket->dib <= 1) { + prev->dib = 0; + break; + } + memcpy(prev, bucket, map->bucketsz); + prev->dib--; + } + map->count--; + if (map->nbuckets > map->cap && + map->count <= map->shrinkat) { + resize(map, map->nbuckets / 2); + } + return map->spare; + } + i = (i + 1) & map->mask; + } +} + +size_t hashmap_count(struct hashmap *map) +{ + return map->count; +} + +void hashmap_free(struct hashmap *map) +{ + if (!map) + return; + free_elements(map); + free(map->buckets); + free(map); +} + +bool hashmap_oom(struct hashmap *map) +{ + return map->oom; +} + +bool hashmap_scan(struct hashmap *map, bool (*iter)(void *item)) +{ + for (size_t i = 0; i < map->nbuckets; i++) { + struct bucket *bucket = bucket_at(map, i); + if (bucket->dib && !iter(bucket_item(bucket))) { + return false; + } + } + return true; +} + +bool hashmap_iter(struct hashmap *map, size_t *i, void **item) +{ + struct bucket *bucket; + do { + if (*i >= map->nbuckets) + return false; + bucket = bucket_at(map, *i); + (*i)++; + } while (!bucket->dib); + *item = bucket_item(bucket); + return true; +} diff --git a/src/lib/list.c b/src/lib/list.c new file mode 100644 index 0000000..db7c5a6 --- /dev/null +++ b/src/lib/list.c @@ -0,0 +1,32 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdlib.h> + +#include <log.h> +#include <lib/list.h> + +static struct list *list_new(void) +{ + struct list *list = malloc(sizeof(*list)); + if (!list) + fatal("out of memory!\n"); + return list; +} + +struct list *list_add(struct list *list, void *data) +{ + struct list *new = list_new(); + new->data = data; + new->next = list; + return new; +} + +void list_free(struct list *list) +{ + while (list) { + struct list *next = list->next; + free(list); + list = next; + } +} diff --git a/src/lib/queue.c b/src/lib/queue.c new file mode 100644 index 0000000..f039257 --- /dev/null +++ b/src/lib/queue.c @@ -0,0 +1,61 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdlib.h> + +#include <lib/queue.h> +#include <log.h> + +struct queue *queue_new(void) +{ + struct queue *queue = malloc(sizeof(*queue)); + if (!queue) + fatal("out of memory!\n"); + queue->head = 0; + queue->tail = 0; + return queue; +} + +void queue_free(struct queue *queue) +{ + while (queue->head) { + struct queue_node *node = queue->head; + queue->head = node->next; + free(node); + } + free(queue); +} + +void queue_push(struct queue *queue, void *data) +{ + struct queue_node *node = malloc(sizeof(*node)); + if (!node) + fatal("out of memory!\n"); + node->data = data; + node->next = 0; + if (queue->tail) { + queue->tail->next = node; + queue->tail = node; + } else { + queue->head = node; + queue->tail = node; + } +} + +void *queue_pop(struct queue *queue) +{ + if (!queue->head) + return 0; + struct queue_node *node = queue->head; + queue->head = node->next; + if (!queue->head) + queue->tail = 0; + void *data = node->data; + free(node); + return data; +} + +int queue_empty(struct queue *queue) +{ + return !queue->head; +} |