diff options
| -rw-r--r-- | array.c | 28 | ||||
| -rw-r--r-- | array.h | 6 | ||||
| -rw-r--r-- | hash.c | 10 | ||||
| -rw-r--r-- | hash.h | 10 | ||||
| -rw-r--r-- | makefile | 2 | ||||
| -rw-r--r-- | map.c | 147 | ||||
| -rw-r--r-- | map.h | 43 | ||||
| -rw-r--r-- | set.c | 139 | ||||
| -rw-r--r-- | set.h | 40 | ||||
| -rw-r--r-- | str.c | 88 | ||||
| -rw-r--r-- | str.h | 27 |
11 files changed, 269 insertions, 271 deletions
@@ -4,27 +4,24 @@ #include <stdlib.h> #define CRASH_IF_OOB(array, len) {\ - if (len > array.length)\ - crash("Array access out of bounds: %ld > %ld\n", len, array.length);\ + if (len > array->length)\ + crash(\ + "Array does not have expected length: %ld > %ld\n",\ + len,\ + array->length);\ } -void* array_at(const array_t array, size_t idx) { - CRASH_IF_OOB(array, idx); - return (char*)array.__data + idx*array.elemsz; +void* array_at(const array_t* array, size_t idx) { + CRASH_IF_OOB(array, idx + 1); + return (char*)array->__data + idx*array->elemsz; } -array_t array_slice(const array_t array, size_t start, size_t length) { +array_t array_slice(const array_t* array, size_t start, size_t length) { CRASH_IF_OOB(array, start + length); - array_t slice = { + return (array_t) { .length = length, - .__data = (char*)array.__data + start * array.elemsz + .__data = (char*)array->__data + start * array->elemsz }; - return slice; -} - -array_t array_init(void* data, size_t length, size_t elemsz) { - array_t array = {.length = length, .elemsz = elemsz, .__data = data}; - return array; } array_t array_heap_alloc(size_t length, size_t elemsz) { @@ -35,12 +32,11 @@ array_t array_heap_alloc(size_t length, size_t elemsz) { length, elemsz); - array_t container = { + return (array_t) { .length = length, .elemsz = elemsz, .__data = data_ptr, }; - return container; } void array_heap_destroy(array_t array) { @@ -8,10 +8,8 @@ typedef struct { void* __data; } array_t; -void* array_at(const array_t array, size_t idx); -array_t array_slice(const array_t array, size_t start, size_t length); - -array_t array_init(void* data, size_t length, size_t elemsz); +void* array_at(const array_t* array, size_t idx); +array_t array_slice(const array_t* array, size_t start, size_t length); array_t array_heap_alloc(size_t length, size_t elemsz); void array_heap_destroy(array_t array); @@ -0,0 +1,10 @@ +#include "hash.h" + +size_t hash_bytes(const void* start, size_t size) { + size_t hash = 0; + const char* raw_data = start; + for (size_t i = 0; i < size; i++) { + hash = (hash << 5) - hash + raw_data[i]; + } + return hash; +} @@ -0,0 +1,10 @@ +#ifndef __SAFEC_HASH_H +#define __SAFEC_HASH_H +#include "types.h" + +typedef size_t (*hash_func_t)(const void* key); +typedef bool (*eq_func_t)(const void* key1, const void* key2); + +size_t hash_bytes(const void* start, size_t size); + +#endif @@ -17,7 +17,7 @@ $(BUILD_DIR): $(TARGET): $(OBJS) ar rcs $@ $^ -$(BUILD_DIR)/%.o: %.c +$(BUILD_DIR)/%.o: %.c *.h $(CC) $(CFLAGS) $< -o $@ clean: @@ -3,18 +3,6 @@ #include <stdlib.h> #define DEFAULT_CAPACITY 16 -#define TOMBSTONE_VAL ((void*)-1) - -size_t hash_bytes(const void* start, size_t size) { - size_t hash = 0; - const char* raw_data = start; - for (size_t i = 0; i < size; i++) { - hash = (hash << 5) - hash + raw_data[i]; - } - return hash; -} - -/* MAPS */ void map_init( map_t* map, @@ -195,138 +183,3 @@ void map_foreach_readwrite( free(keys); free(vals); } - -/* SETS */ - -void set_init( - set_t* set, - hash_func_t hash_func, - eq_func_t eq_func, - double load_limit -) { - set_init_capacity(set, hash_func, eq_func, load_limit, DEFAULT_CAPACITY); -} - -void set_init_capacity( - set_t* set, - hash_func_t hash_func, - eq_func_t eq_func, - double load_limit, - size_t capacity -) { - set->hash_func = hash_func; - set->eq_func = eq_func; - set->load_limit = load_limit; - set->size = 0; - set->__num_buckets = capacity / load_limit + 1; - set->__buckets = calloc(set->__num_buckets, sizeof(void*)); - - if (set->__buckets == NULL) - crash("Out of memory allocating %ld hash buckets\n", set->__num_buckets); -} - -void set_destroy(set_t* set) { - free(set->__buckets); -} - -static size_t fetch_set_idx( - const set_t* set, - const void* key, - bool fetch_tombstones -) { - if (key == NULL || key == TOMBSTONE_VAL) - crash("safec sets do not support non-address keys: %p.\n", key); - size_t base = set->hash_func(key) % set->__num_buckets; - size_t idx = base, i = 0, offset = 0; - - for (;;) { - void* cur = set->__buckets[idx]; - if (cur == NULL || (fetch_tombstones && cur == TOMBSTONE_VAL) - || (cur != TOMBSTONE_VAL && set->eq_func(key, cur))) - return idx; - if (offset >= set->__num_buckets) return set->__num_buckets; - i++; - offset = i * i; - idx = (base + offset) % set->__num_buckets; - } -} - -bool set_contains(const set_t* set, const void* key) { - size_t idx = fetch_set_idx(set, key, false); - return idx < set->__num_buckets && set->__buckets[idx] != NULL; -} - -void* set_get(const set_t* set, const void* key) { - return set_get_or_default(set, key, NULL); -} - -void* set_get_or_default(const set_t* set, const void* key, void* default_key) { - size_t idx = fetch_set_idx(set, key, false); - if (idx >= set->__num_buckets) return default_key; - void* found = set->__buckets[idx]; - return found == NULL ? default_key : found; -} - -static void rehash_set(set_t* set) { - size_t old_num_buckets = set->__num_buckets; - void** old_buckets = set->__buckets; - set->__num_buckets <<= 1; - set->__buckets = calloc(set->__num_buckets, sizeof(void*)); - if (set->__buckets == NULL) - crash( - "Out of memory allocating %ld hash buckets\n", set->__num_buckets); - - for (size_t i = 0; i < old_num_buckets; i++) { - void* key = old_buckets[i]; - if (key == NULL) continue; - size_t idx = fetch_set_idx(set, key, true); - if (idx >= set->__num_buckets) - crash( - "Set failed rehashing, likely due to bad hash function.\n"); - set->__buckets[idx] = key; - } - free(old_buckets); -} - -static size_t fetch_set_idx_rehashing(set_t* set, void* key) { - size_t idx = fetch_set_idx(set, key, true); - if ((double) ++set->size / set->__num_buckets > set->load_limit - || idx >= set->__num_buckets) { - rehash_set(set); - idx = fetch_set_idx(set, key, true); - if (idx >= set->__num_buckets) - crash( - "Set still full after rehashing, " - "likely due to bad hash function.\n"); - } - return idx; -} - -void* set_add(set_t* set, void* key) { - size_t idx = fetch_set_idx_rehashing(set, key); - void* old_key = set->__buckets[idx]; - if (old_key != NULL) return old_key; - set->__buckets[idx] = key; - return key; -} - -void set_put(set_t* set, void* key) { - size_t idx = fetch_set_idx_rehashing(set, key); - set->__buckets[idx] = key; -} - -void* set_remove(set_t* set, const void* key) { - size_t idx = fetch_set_idx(set, key, false); - void* old_key = set->__buckets[idx]; - if (old_key != NULL) set->size--; - set->__buckets[idx] = TOMBSTONE_VAL; - return old_key; -} - -void set_foreach(set_t* set, set_foreach_func_t foreach_func, void* data) { - for (size_t i = 0; i < set->__num_buckets; i++) { - void* key = set->__buckets[i]; - if (key == NULL || key == TOMBSTONE_VAL) continue; - foreach_func(key, data); - } -} @@ -1,12 +1,7 @@ #ifndef __SAFEC_MAP_H +#define __SAFEC_MAP_H #include "types.h" - -size_t hash_bytes(const void* start, size_t size); - -typedef size_t (*hash_func_t)(const void* key); -typedef bool (*eq_func_t)(const void* key1, const void* key2); -typedef void (*map_foreach_func_t)(void* key, void* val, void* data); -typedef void (*set_foreach_func_t)(void* key, void* data); +#include "hash.h" struct __map_entry { void* key; @@ -44,6 +39,8 @@ void* map_get_or_default(const map_t* map, const void* key, void* default_val); void* map_compute_if_absent(map_t* map, void* key, void* default_val); void map_put(map_t* map, void* key, void* val); void* map_remove(map_t* map, const void* key); + +typedef void (*map_foreach_func_t)(void* key, void* val, void* data); void map_foreach_readonly( map_t* map, map_foreach_func_t foreach_func, @@ -53,36 +50,4 @@ void map_foreach_readwrite( map_foreach_func_t foreach_func, void* data); -typedef struct { - hash_func_t hash_func; - eq_func_t eq_func; - double load_limit; - - size_t size; - - size_t __num_buckets; - void** __buckets; -} set_t; - -void set_init( - set_t* set, - hash_func_t hash_func, - eq_func_t eq_func, - double load_limit); -void set_init_capacity( - set_t* set, - hash_func_t hash_func, - eq_func_t eq_func, - double load_limit, - size_t capacity); -void set_destroy(set_t* set); - -bool set_contains(const set_t* set, const void* key); -void* set_get(const set_t* set, const void* key); -void* set_get_or_default(const set_t* set, const void* key, void* default_key); -void* set_add(set_t* set, void* key); -void set_put(set_t* set, void* key); -void* set_remove(set_t* set, const void* key); -void set_foreach(set_t* set, set_foreach_func_t foreach_func, void* data); - #endif @@ -0,0 +1,139 @@ +#include "set.h" +#include "crash.h" +#include <stdlib.h> + +#define DEFAULT_CAPACITY 16 +#define TOMBSTONE_VAL ((void*)-1) + +void set_init( + set_t* set, + hash_func_t hash_func, + eq_func_t eq_func, + double load_limit +) { + set_init_capacity(set, hash_func, eq_func, load_limit, DEFAULT_CAPACITY); +} + +void set_init_capacity( + set_t* set, + hash_func_t hash_func, + eq_func_t eq_func, + double load_limit, + size_t capacity +) { + set->hash_func = hash_func; + set->eq_func = eq_func; + set->load_limit = load_limit; + set->size = 0; + set->__num_buckets = capacity / load_limit + 1; + set->__buckets = calloc(set->__num_buckets, sizeof(void*)); + + if (set->__buckets == NULL) + crash("Out of memory allocating %ld hash buckets\n", set->__num_buckets); +} + +void set_destroy(set_t* set) { + free(set->__buckets); +} + +static size_t fetch_set_idx( + const set_t* set, + const void* key, + bool fetch_tombstones +) { + if (key == NULL || key == TOMBSTONE_VAL) + crash("safec sets do not support non-address keys: %p.\n", key); + size_t base = set->hash_func(key) % set->__num_buckets; + size_t idx = base, i = 0, offset = 0; + + for (;;) { + void* cur = set->__buckets[idx]; + if (cur == NULL || (fetch_tombstones && cur == TOMBSTONE_VAL) + || (cur != TOMBSTONE_VAL && set->eq_func(key, cur))) + return idx; + if (offset >= set->__num_buckets) return set->__num_buckets; + i++; + offset = i * i; + idx = (base + offset) % set->__num_buckets; + } +} + +bool set_contains(const set_t* set, const void* key) { + size_t idx = fetch_set_idx(set, key, false); + return idx < set->__num_buckets && set->__buckets[idx] != NULL; +} + +void* set_get(const set_t* set, const void* key) { + return set_get_or_default(set, key, NULL); +} + +void* set_get_or_default(const set_t* set, const void* key, void* default_key) { + size_t idx = fetch_set_idx(set, key, false); + if (idx >= set->__num_buckets) return default_key; + void* found = set->__buckets[idx]; + return found == NULL ? default_key : found; +} + +static void rehash_set(set_t* set) { + size_t old_num_buckets = set->__num_buckets; + void** old_buckets = set->__buckets; + set->__num_buckets <<= 1; + set->__buckets = calloc(set->__num_buckets, sizeof(void*)); + if (set->__buckets == NULL) + crash( + "Out of memory allocating %ld hash buckets\n", set->__num_buckets); + + for (size_t i = 0; i < old_num_buckets; i++) { + void* key = old_buckets[i]; + if (key == NULL) continue; + size_t idx = fetch_set_idx(set, key, true); + if (idx >= set->__num_buckets) + crash( + "Set failed rehashing, likely due to bad hash function.\n"); + set->__buckets[idx] = key; + } + free(old_buckets); +} + +static size_t fetch_set_idx_rehashing(set_t* set, void* key) { + size_t idx = fetch_set_idx(set, key, true); + if ((double) ++set->size / set->__num_buckets > set->load_limit + || idx >= set->__num_buckets) { + rehash_set(set); + idx = fetch_set_idx(set, key, true); + if (idx >= set->__num_buckets) + crash( + "Set still full after rehashing, " + "likely due to bad hash function.\n"); + } + return idx; +} + +void* set_add(set_t* set, void* key) { + size_t idx = fetch_set_idx_rehashing(set, key); + void* old_key = set->__buckets[idx]; + if (old_key != NULL) return old_key; + set->__buckets[idx] = key; + return key; +} + +void set_put(set_t* set, void* key) { + size_t idx = fetch_set_idx_rehashing(set, key); + set->__buckets[idx] = key; +} + +void* set_remove(set_t* set, const void* key) { + size_t idx = fetch_set_idx(set, key, false); + void* old_key = set->__buckets[idx]; + if (old_key != NULL) set->size--; + set->__buckets[idx] = TOMBSTONE_VAL; + return old_key; +} + +void set_foreach(set_t* set, set_foreach_func_t foreach_func, void* data) { + for (size_t i = 0; i < set->__num_buckets; i++) { + void* key = set->__buckets[i]; + if (key == NULL || key == TOMBSTONE_VAL) continue; + foreach_func(key, data); + } +} @@ -0,0 +1,40 @@ +#ifndef __SAFEC_SET_H +#define __SAFEC_SET_H +#include "types.h" +#include "hash.h" + +typedef struct { + hash_func_t hash_func; + eq_func_t eq_func; + double load_limit; + + size_t size; + + size_t __num_buckets; + void** __buckets; +} set_t; + +void set_init( + set_t* set, + hash_func_t hash_func, + eq_func_t eq_func, + double load_limit); +void set_init_capacity( + set_t* set, + hash_func_t hash_func, + eq_func_t eq_func, + double load_limit, + size_t capacity); +void set_destroy(set_t* set); + +bool set_contains(const set_t* set, const void* key); +void* set_get(const set_t* set, const void* key); +void* set_get_or_default(const set_t* set, const void* key, void* default_key); +void* set_add(set_t* set, void* key); +void set_put(set_t* set, void* key); +void* set_remove(set_t* set, const void* key); + +typedef void (*set_foreach_func_t)(void* key, void* data); +void set_foreach(set_t* set, set_foreach_func_t foreach_func, void* data); + +#endif @@ -4,8 +4,11 @@ #include <string.h> #define CRASH_IF_OOB(str, len) {\ - if (len > str.length)\ - crash("String access out of bounds: %ld > %ld\n", len, str.length);\ + if (len > str->length)\ + crash(\ + "String does not have expected length: %ld > %ld\n",\ + len,\ + str->length);\ } static inline char* alloc_data_ptr(size_t length) { @@ -24,56 +27,56 @@ static inline char* alloc_c_str(size_t length) { return c_str; } -char* str_at(const str_t str, size_t idx) { +char* str_at(const str_t* str, size_t idx) { CRASH_IF_OOB(str, idx + 1); - return str.__data + idx; + return str->__data + idx; } -str_t str_slice(const str_t str, size_t start, size_t length) { +str_t str_slice(const str_t* str, size_t start, size_t length) { CRASH_IF_OOB(str, start + length); - str_t slice = {.length = length, .__data = str.__data + start}; - return slice; + return (str_t) {.length = length, .__data = str->__data + start}; } -int str_cmp(const str_t s1, const str_t s2) { - if (s1.length == s2.length) - return memcmp(s1.__data, s2.__data, s1.length); - else if (s1.length > s2.length) { - int cmp = memcmp(s1.__data, s2.__data, s2.length); +int str_cmp(const str_t* s1, const str_t* s2) { + if (s1->length == s2->length) + return memcmp(s1->__data, s2->__data, s1->length); + else if (s1->length > s2->length) { + int cmp = memcmp(s1->__data, s2->__data, s2->length); if (cmp != 0) return cmp; return 1; } else { - int cmp = memcmp(s1.__data, s2.__data, s1.length); + int cmp = memcmp(s1->__data, s2->__data, s1->length); if (cmp != 0) return cmp; return -1; } } -ssize_t str_indexof(const str_t str, char c) { - for (ssize_t i = 0; i < str.length; i++) { - if (str.__data[i] == c) return i; +ssize_t str_indexof(const str_t* str, char c) { + for (ssize_t i = 0; i < str->length; i++) { + if (str->__data[i] == c) return i; } return -1; } -ssize_t str_rindexof(const str_t str, char c) { - for (ssize_t i = (ssize_t)str.length - 1; i >= 0; i--) { - if (str.__data[i] == c) return i; +ssize_t str_rindexof(const str_t* str, char c) { + for (ssize_t i = (ssize_t)str->length - 1; i >= 0; i--) { + if (str->__data[i] == c) return i; } return -1; } -str_t str_heap_dup(const str_t str) { - char* data_ptr = alloc_data_ptr(str.length); - str_t dup_str = {.length = str.length, .__data = data_ptr}; - return dup_str; +str_t str_heap_dup(const str_t* str) { + char* data_ptr = alloc_data_ptr(str->length); + memcpy(data_ptr, str->__data, str->length); + return (str_t) {.length = str->length, .__data = data_ptr}; } -str_t str_heap_cat(const str_t s1, const str_t s2) { - size_t new_len = s1.length + s2.length; +str_t str_heap_cat(const str_t* s1, const str_t* s2) { + size_t new_len = s1->length + s2->length; char* data_ptr = alloc_data_ptr(new_len); - str_t cat_str = {.length = new_len, .__data = data_ptr}; - return cat_str; + memcpy(data_ptr, s1->__data, s1->length); + memcpy(data_ptr + s1->length, s2->__data, s2->length); + return (str_t) {.length = new_len, .__data = data_ptr}; } void str_to_c_str(char* dst, size_t dst_size, const str_t* src) { @@ -87,38 +90,27 @@ void str_to_c_str(char* dst, size_t dst_size, const str_t* src) { dst[src->length] = 0; } -char* str_to_heap_c_str(const str_t src) { - char* dst = alloc_c_str(src.length); - memcpy(dst, src.__data, src.length); +char* str_to_heap_c_str(const str_t* src) { + char* dst = alloc_c_str(src->length); + memcpy(dst, src->__data, src->length); return dst; } -str_t str_init(char* data, size_t length) { - str_t str = {.length = length, .__data = data}; - return str; -} - str_t str_heap_alloc(size_t length) { char* data_ptr = alloc_data_ptr(length); - str_t str = {.length = length, .__data = data_ptr}; - return str; + return (str_t) {.length = length, .__data = data_ptr}; } -str_t str_heap_alloc_iv(const char* c_str) { - size_t length = strlen(c_str); - char* data_ptr = alloc_data_ptr(length); - memcpy(data_ptr, c_str, length); - str_t str = {.length = length, .__data = data_ptr}; - return str; +str_t str_heap_init(const char* c_str, size_t length) { + return str_heap_init_slice(c_str, 0, length); } -str_t str_heap_alloc_iv_slice(const char* c_str, size_t start, size_t length) { +str_t str_heap_init_slice(const char* c_str, size_t start, size_t length) { char* data_ptr = alloc_data_ptr(length); memcpy(data_ptr, c_str + start, length); - str_t str = {.length = length, .__data = data_ptr}; - return str; + return (str_t) {.length = length, .__data = data_ptr}; } -void str_heap_destroy(str_t str) { - free(str.__data); +void str_heap_destroy(str_t* str) { + free(str->__data); } @@ -7,31 +7,26 @@ typedef struct { char* __data; } str_t; -// TODO: heap-allocing the pointer is stupid just return a value -// should just heap-alloc __data - -char* str_at(const str_t str, size_t idx); -str_t str_slice(const str_t str, size_t start, size_t length); -int str_cmp(const str_t s1, const str_t s2); +char* str_at(const str_t* str, size_t idx); +str_t str_slice(const str_t* str, size_t start, size_t length); +int str_cmp(const str_t* s1, const str_t* s2); /* not found = -1 */ -ssize_t str_indexof(const str_t str, char c); -ssize_t str_rindexof(const str_t str, char c); +ssize_t str_indexof(const str_t* str, char c); +ssize_t str_rindexof(const str_t* str, char c); -str_t str_heap_dup(const str_t str); -str_t str_heap_cat(const str_t s1, const str_t s2); +str_t str_heap_dup(const str_t* str); +str_t str_heap_cat(const str_t* s1, const str_t* s2); /* TODO: implement string.h functions for this new string construct */ /* `dst` will be overwritten with the contents of `src` */ void str_to_c_str(char* dst, size_t dst_size, const str_t* src); -char* str_to_heap_c_str(const str_t str); - -str_t str_init(char* data, size_t length); +char* str_to_heap_c_str(const str_t* str); str_t str_heap_alloc(size_t length); -str_t str_heap_alloc_iv(const char* c_str); -str_t str_heap_alloc_iv_slice(const char* c_str, size_t start, size_t length); -void str_heap_destroy(str_t str); +str_t str_heap_init(const char* c_str, size_t length); +str_t str_heap_init_slice(const char* c_str, size_t start, size_t length); +void str_heap_destroy(str_t* str); #endif |