From fb9a5b153f16d8c8fe961b6af0f54a7178e032a6 Mon Sep 17 00:00:00 2001 From: gramanas Date: Sun, 16 Jun 2024 20:27:29 +0300 Subject: Add pds --- src/pds.h | 417 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 417 insertions(+) create mode 100644 src/pds.h (limited to 'src/pds.h') diff --git a/src/pds.h b/src/pds.h new file mode 100644 index 0000000..e0b9df2 --- /dev/null +++ b/src/pds.h @@ -0,0 +1,417 @@ +#ifndef _PDS_H +#define _PDS_H + +/* pointer data structures */ +/* Simple stack with psuh/pop */ +/* Simple hashmap with char * as key */ + +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef PDSDEF +#ifdef PDS_STATIC +#define PDSDEF static +#else +#define PDSDEF extern +#endif +#endif + +#define PSTACK_RESIZE_FACTOR 2 +#define PSTACK_INIT_CAPACITY 16 + + typedef struct pstack + { + uint64_t cap; + uint64_t size; + uint64_t stride; + void* data; + } pstack; + + /* Exported API */ + /* Stack */ + PDSDEF void* _pstack_create(uint64_t length, uint64_t stride); +#ifndef pstack_create +#define pstack_create(type) _pstack_create(PSTACK_INIT_CAPACITY, sizeof(type)); +#endif + +#ifndef pstack_create_ex +#define pstack_create_ex(type, cap) _pstack_create(cap, sizeof(type)); +#endif + + PDSDEF void* _pstack_push(void* list, const void* value_ptr); +#ifndef pstack_push +#define pstack_push(list, val) \ + do { \ + typeof(val) tmp = val; \ + list = _pstack_push(list, &tmp); \ + } while (0); +#endif + + PDSDEF uint64_t pstack_capacity(void* list); + PDSDEF uint64_t pstack_size(void* list); + PDSDEF uint64_t pstack_stride(void* list); + PDSDEF void pstack_length_set(void* list, uint64_t value); + PDSDEF void pstack_destroy(void* list); + PDSDEF void* pstack_resize(void* list); + + /* Hashmap */ + + typedef struct phash + { + uint64_t element_size; + uint32_t element_count; + int8_t is_pointer_type; + void* memory; + } phash; + + /* Exported API */ + + PDSDEF void phash_create(uint64_t element_size, + uint32_t element_count, + void* memory, + int8_t is_pointer_type, + phash* out_phash); + PDSDEF void phash_destroy(phash* table); + PDSDEF int8_t phash_set(phash* table, const char* name, void* value); + PDSDEF int8_t phash_set_ptr(phash* table, const char* name, void** value); + PDSDEF int8_t phash_get(phash* table, const char* name, void* out_value); + PDSDEF int8_t phash_get_ptr(phash* table, const char* name, void** out_value); + +#ifdef __cplusplus +} +#endif + +/* End header file */ +#endif /* _PDS_H */ + +#ifdef PDS_IMPLEMENTATION + +PDSDEF void* +_pstack_create(uint64_t length, uint64_t stride) +{ + uint64_t header_size = sizeof(pstack); + uint64_t list_size = length * stride; + + pstack* list = (pstack*)malloc(header_size + list_size); + list->cap = length; + list->size = 0; + list->stride = stride; + list->data = NULL; + + return (void*)((uint8_t*)list + header_size); +} + +PDSDEF uint64_t +pstack_capacity(void* list) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + return header->cap; +} + +PDSDEF uint64_t +pstack_size(void* list) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + return header->size; +} + +PDSDEF uint64_t +pstack_stride(void* list) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + return header->stride; +} + +PDSDEF void +pstack_length_set(void* list, uint64_t value) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + header->size = value; +} + +PDSDEF void +pstack_destroy(void* list) +{ + if (list) { + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + free(header); + } +} + +PDSDEF void* +pstack_resize(void* list) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + if (header->cap == 0) { + fprintf(stderr, + "pstack_resize called on an list with 0 capacity. This should not " + "be possible.\n"); + return 0; + } + void* temp = + _pstack_create((PSTACK_RESIZE_FACTOR * header->cap), header->stride); + + pstack* new_header = (pstack*)((uint8_t*)temp - header_size); + new_header->size = header->size; + + memcpy(temp, list, header->size * header->stride); + + pstack_destroy(list); + return temp; +} + +PDSDEF void* +_pstack_push(void* list, const void* value_ptr) +{ + uint64_t header_size = sizeof(pstack); + pstack* header = (pstack*)((uint8_t*)list - header_size); + if (header->size >= header->cap) { + list = pstack_resize(list); + } + header = (pstack*)((uint8_t*)list - header_size); + + uint64_t addr = (uint64_t)list; + addr += (header->size * header->stride); + memcpy((void*)addr, value_ptr, header->stride); + pstack_length_set(list, header->size + 1); + return list; +} + +PDSDEF int +pstack_pop(void* list, void* dest) +{ + uint64_t size = pstack_size(list); + uint64_t stride = pstack_stride(list); + if (size < 1) { + // fprintf(stderr, "pstack_pop called on an empty pstack. Nothing to be + // done.\n"); + return 1; + } + uint64_t addr = (uint64_t)list; + addr += ((size - 1) * stride); + memcpy(dest, (void*)addr, stride); + pstack_length_set(list, size - 1); + return 0; +} + +/* int */ +/* main() */ +/* { */ +/* int* lst = pstack_create(int); */ +/* pstack_push(lst, 1); */ +/* pstack_push(lst, 2); */ + +/* int i; */ +/* while (!pstack_pop(lst, &i)) { */ +/* printf("%d\n", i); */ +/* } */ + +/* char** lst2 = pstack_create(char*); */ +/* pstack_push(lst2, &"Hello"); */ +/* pstack_push(lst2, &"you!"); */ + +/* char *s; */ +/* while (!pstack_pop(lst2, &s)) { */ +/* printf("%s\n", s); */ +/* } */ + +/* pstack_destroy(lst); */ +/* pstack_destroy(lst2); */ + +/* return 0; */ +/* } */ + +static uint64_t +hash_name(const char* name, uint32_t element_count) +{ + // A multipler to use when generating a hash. Prime to hopefully avoid + // collisions. + static const uint64_t multiplier = 97; + + unsigned const char* us; + uint64_t hash = 0; + + for (us = (unsigned const char*)name; *us; us++) { + hash = hash * multiplier + *us; + } + + // Mod it against the size of the table. + hash %= element_count; + + return hash; +} + +PDSDEF void +phash_create(uint64_t element_size, + uint32_t element_count, + void* memory, + int8_t is_pointer_type, + phash* out_phash) +{ + if (!memory || !out_phash) { + fprintf( + stderr, + "phash_create failed! Pointer to memory and out_phash are required.\n"); + return; + } + if (!element_count || !element_size) { + fprintf( + stderr, + "element_size and element_count must be a positive non-zero value.\n"); + return; + } + + out_phash->memory = memory; + out_phash->element_count = element_count; + out_phash->element_size = element_size; + out_phash->is_pointer_type = is_pointer_type; + memset(out_phash->memory, 0, element_size * element_count); +} + +PDSDEF void +phash_destroy(phash* table) +{ + if (table) { + memset(table->memory, 0, table->element_size * table->element_count); + } +} + +PDSDEF int8_t +phash_set(phash* table, const char* name, void* value) +{ + if (!table || !name || !value) { + fprintf(stderr, "phash_set requires table, name and value to exist."); + return 0; + } + if (table->is_pointer_type) { + fprintf(stderr, + "phash_set should not be used with tables that have pointer types. " + "Use phash_set_ptr instead.\n"); + return 0; + } + + uint64_t hash = hash_name(name, table->element_count); + memcpy( + table->memory + (table->element_size * hash), value, table->element_size); + return 1; +} + +PDSDEF int8_t +phash_set_ptr(phash* table, const char* name, void** value) +{ + if (!table || !name) { + fprintf(stderr, "phash_set_ptr requires table and name to exist.\n"); + return 0; + } + if (!table->is_pointer_type) { + fprintf(stderr, + "phash_set_ptr should not be used with tables that do not have " + "pointer types. Use phash_set instead.\n"); + return 0; + } + + uint64_t hash = hash_name(name, table->element_count); + ((void**)table->memory)[hash] = value ? *value : 0; + return 1; +} + +PDSDEF int8_t +phash_get(phash* table, const char* name, void* out_value) +{ + if (!table || !name || !out_value) { + fprintf(stderr, "phash_get requires table, name and out_value to exist.\n"); + return 0; + } + if (table->is_pointer_type) { + fprintf(stderr, + "phash_get should not be used with tables that have pointer types. " + "Use phash_set_ptr instead.\n"); + return 0; + } + + uint64_t hash = hash_name(name, table->element_count); + memcpy(out_value, + table->memory + (table->element_size * hash), + table->element_size); + return 1; +} + +PDSDEF int8_t +phash_get_ptr(phash* table, const char* name, void** out_value) +{ + if (!table || !name || !out_value) { + fprintf(stderr, + "phash_get_ptr requires table, name and out_value to exist.\n"); + return 0; + } + if (!table->is_pointer_type) { + fprintf(stderr, + "phash_get_ptr should not be used with tables that do not have " + "pointer types. Use phash_get instead.\n"); + return 0; + } + + uint64_t hash = hash_name(name, table->element_count); + *out_value = ((void**)table->memory)[hash]; + return *out_value != 0; +} + +/* struct test */ +/* { */ +/* int a; */ +/* char b[15]; */ +/* }; */ + +/* int */ +/* main() */ +/* { */ +/* phash tbl; */ +/* int mem[2]; */ +/* phash_create(sizeof(int), 2, &mem, 0, &tbl); */ + +/* int x = 2; */ +/* phash_set(&tbl, "Val", &x); */ +/* x = 3; */ +/* phash_set(&tbl, "Val1", &x); */ +/* x = 4; */ +/* phash_set(&tbl, "Val2", &x); */ + +/* int y; */ +/* phash_get(&tbl, "Val", &y); */ +/* printf("%d\n", y); */ +/* phash_get(&tbl, "Val1", &y); */ +/* printf("%d\n", y); */ +/* phash_get(&tbl, "Val2", &y); */ +/* printf("%d\n", y); */ + +/* phash_destroy(&tbl); */ + +/* phash tbl2; */ +/* struct test mem2[15]; */ +/* phash_create(sizeof(struct test), 15, &mem2, 1, &tbl2); */ + +/* struct test a = { .a = 5, .b = "Yooo" }; */ +/* struct test* aa = &a; */ +/* phash_set_ptr(&tbl2, "aha", (void**)&aa); */ + +/* struct test* get; */ +/* phash_get_ptr(&tbl2, "aha", (void**)&get); */ +/* printf("{ a: %d, b: %s }\n", get->a, get->b); */ + +/* return 0; */ +/* } */ + +#endif /* PDS_IMPLEMENTATION */ -- cgit v1.2.3