diff options
Diffstat (limited to 'libs/anr/anr_data.h')
| -rw-r--r-- | libs/anr/anr_data.h | 1117 |
1 files changed, 1117 insertions, 0 deletions
diff --git a/libs/anr/anr_data.h b/libs/anr/anr_data.h new file mode 100644 index 0000000..17ac367 --- /dev/null +++ b/libs/anr/anr_data.h @@ -0,0 +1,1117 @@ +/* +anr_data.h - v0.4 - public domain data structures library + +This is a single-header-file library that provides basic data structures + +Do this: + #ifdef ANR_DATA_IMPLEMENTATION +before you include this file in *one* C file to create the implementation. + +The data structures are completely interchangeable if you use the macros. See examples/test_data.c + +DOCUMENTATION + + ANR_DS_ADD + array, linked list: append to end of ds. + hashmap: insert at any open slot. + + ANR_DS_PRINT + print entries. define ANR_DATA_DEBUG to see diff with previous print. + + ANR_DS_FIND_AT + Returns data at index. + + ANR_DS_FIND_BY + Returns index of first match of data. + + ANR_DS_REMOVE_BY + Remove entry given the data ptr. Data ptr is assumed to exist in ds. + + ANR_DS_REMOVE_AT + Remove data at index. + + ANR_DS_INSERT + array, linked list: Insert at index and move up existing data. Index needs to be <= ds.length + hashmap: Insert data at index, replaces existing data. Index needs to be >= 0 and < UINT32_MAX + + ANR_DS_LENGTH + Return number of entries in ds. + + ANR_ITERATE + Iterate over ds, given anr_iter .index and .data entries are filled. + + ANR_DS_FREE + Free memory, dont use ds after this. + +LICENSE + See end of file for license information. + +*/ +#ifndef INCLUDE_ANR_DATA_H +#define INCLUDE_ANR_DATA_H + +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include <stddef.h> + +#ifndef ANRDATADEF +#define ANRDATADEF extern +#endif + +#include <inttypes.h> + +#ifndef ANRDATA_ASSERT +#include <assert.h> +#define ANRDATA_ASSERT(x) assert(x) +#endif + +typedef enum +{ + ANR_DS_LINKEDLIST = 0, + ANR_DS_DYNAMIC_ARRAY = 1, + ANR_DS_HASHMAP = 2, +} anr_ds_type; + +typedef struct +{ + void* prev; + void* next; + void* data; +} anr_linked_list_node; + +typedef struct +{ + anr_ds_type ds_type; + anr_linked_list_node* first; + anr_linked_list_node* last; + uint32_t length; + uint32_t data_size; + + struct // Cache last accessed node. + { + anr_linked_list_node* node; + uint32_t index; + } last_access; + +} anr_linked_list; + +typedef struct +{ + anr_ds_type ds_type; + void* data; + int32_t data_size; + int32_t reserve_size; + int32_t reserved; + int32_t length; +} anr_array; + +typedef struct +{ + uint32_t bucket_start; + uint32_t length; + void* data; +} anr_hashmap_bucket; + +typedef struct +{ + anr_ds_type ds_type; + uint32_t bucket_size; + anr_array buckets; + uint32_t data_size; + uint32_t length; + int32_t last_emptied; // Index known to be empty. -1 if none. + int32_t next_empty; // Next empty index to append. -1 of none. +} anr_hashmap; + +typedef struct +{ + int32_t index; + void* data; + union + { + struct + { + anr_linked_list_node* node; + } ll; + }; +} anr_iter; + +typedef union +{ + anr_linked_list ds_ll; +} anr_ds; + +typedef struct +{ + int32_t (*add)(void* ds, void* ptr); // returns index on success, -1 on fail + void (*free)(void* ds); + void (*print)(void* ds); + void* (*find_at)(void*,uint32_t); // returns data + uint32_t (*find_by)(void* ds, char* ptr); // returns index, or -1 if not found + uint8_t (*remove_at)(void* ds, uint32_t index); // returns 1 on success, 0 on fail + uint8_t (*remove_by)(void* ds, void* ptr); // returns 1 on success, 0 on fail + uint8_t (*insert)(void* ds, uint32_t index, void* ptr); // returns 1 on success, 0 on fail + uint32_t (*length)(void* ds); + anr_iter (*iter_start)(void* ds); + uint8_t (*iter_next)(void* ds, anr_iter* iter); // returns 1 on success, 0 if no more items to iterate +} anr_ds_table; + +typedef struct +{ + int type; + anr_ds_table* ds; +} anr_ds_pair; + +// === linked list === +ANRDATADEF anr_linked_list anr_linked_list_create(uint32_t data_size); +ANRDATADEF int32_t anr_linked_list_add(void* ds, void* ptr); +ANRDATADEF void anr_linked_list_free(void* ds); +ANRDATADEF void anr_linked_list_print(void* ds); +ANRDATADEF void* anr_linked_list_find_at(void* ds, uint32_t index); +ANRDATADEF uint32_t anr_linked_list_find_by(void* ds, char* ptr); +ANRDATADEF uint8_t anr_linked_list_remove_at(void* ds, uint32_t index); +ANRDATADEF uint8_t anr_linked_list_remove_by(void* ds, void* ptr); +ANRDATADEF uint8_t anr_linked_list_insert(void* ds, uint32_t index, void* ptr); +ANRDATADEF uint32_t anr_linked_list_length(void* ds); +ANRDATADEF anr_iter anr_linked_list_iter_start(void* ds); +ANRDATADEF uint8_t anr_linked_list_iter_next(void* ds, anr_iter* iter); + +// === dynamic array === +ANRDATADEF anr_array anr_array_create(uint32_t data_size, uint32_t reserve_count); +ANRDATADEF int32_t anr_array_add(void* ds, void* ptr); +ANRDATADEF void anr_array_free(void* ds); +ANRDATADEF void anr_array_print(void* ds); +ANRDATADEF void* anr_array_find_at(void* ds, uint32_t index); +ANRDATADEF uint32_t anr_array_find_by(void* ds, char* ptr); +ANRDATADEF uint8_t anr_array_remove_at(void* ds, uint32_t index); +ANRDATADEF uint8_t anr_array_remove_by(void* ds, void* ptr); +ANRDATADEF uint8_t anr_array_insert(void* ds, uint32_t index, void* ptr); +ANRDATADEF uint32_t anr_array_length(void* ds); +ANRDATADEF anr_iter anr_array_iter_start(void* ds); +ANRDATADEF uint8_t anr_array_iter_next(void* ds, anr_iter* iter); + +// === hashmap === +ANRDATADEF anr_hashmap anr_hashmap_create(uint32_t data_size, uint32_t bucket_size); +ANRDATADEF int32_t anr_hashmap_add(void* ds, void* ptr); +ANRDATADEF void anr_hashmap_free(void* ds); +ANRDATADEF void anr_hashmap_print(void* ds); +ANRDATADEF void* anr_hashmap_find_at(void* ds, uint32_t index); +ANRDATADEF uint32_t anr_hashmap_find_by(void* ds, char* ptr); +ANRDATADEF uint8_t anr_hashmap_remove_at(void* ds, uint32_t index); +ANRDATADEF uint8_t anr_hashmap_remove_by(void* ds, void* ptr); +ANRDATADEF uint8_t anr_hashmap_insert(void* ds, uint32_t index, void* ptr); +ANRDATADEF uint32_t anr_hashmap_length(void* ds); +ANRDATADEF anr_iter anr_hashmap_iter_start(void* ds); +ANRDATADEF uint8_t anr_hashmap_iter_next(void* ds, anr_iter* iter); + +anr_ds_table _ds_ll = +{ + anr_linked_list_add, + anr_linked_list_free, + anr_linked_list_print, + anr_linked_list_find_at, + anr_linked_list_find_by, + anr_linked_list_remove_at, + anr_linked_list_remove_by, + anr_linked_list_insert, + anr_linked_list_length, + anr_linked_list_iter_start, + anr_linked_list_iter_next, +}; + +anr_ds_table _ds_array = +{ + anr_array_add, + anr_array_free, + anr_array_print, + anr_array_find_at, + anr_array_find_by, + anr_array_remove_at, + anr_array_remove_by, + anr_array_insert, + anr_array_length, + anr_array_iter_start, + anr_array_iter_next, +}; + +anr_ds_table _ds_hashmap = +{ + anr_hashmap_add, + anr_hashmap_free, + anr_hashmap_print, + anr_hashmap_find_at, + anr_hashmap_find_by, + anr_hashmap_remove_at, + anr_hashmap_remove_by, + anr_hashmap_insert, + anr_hashmap_length, + anr_hashmap_iter_start, + anr_hashmap_iter_next, +}; + +anr_ds_pair _ds_arr[] = +{ + {ANR_DS_LINKEDLIST, &_ds_ll}, + {ANR_DS_DYNAMIC_ARRAY, &_ds_array}, + {ANR_DS_HASHMAP, &_ds_hashmap}, +}; + +#define ANR_DS_ARRAY(_data_size, _reserve_count) anr_array_create(_data_size, _reserve_count) +#define ANR_DS_LINKED_LIST(_data_size) anr_linked_list_create(_data_size) +#define ANR_DS_HASHMAP(_data_size, _bucket_size) anr_hashmap_create(_data_size, _bucket_size) + +#define ANR_DS_ADD(__ds, __ptr) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->add((void*)__ds, (void*)__ptr) +#define ANR_DS_FREE(__ds) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->free((void*)__ds) +#define ANR_DS_PRINT(__ds) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->print((void*)__ds) +#define ANR_DS_FIND_AT(__ds, __index) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->find_at((void*)__ds, __index) +#define ANR_DS_FIND_BY(__ds, __ptr) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->find_by((void*)__ds, (void*)__ptr) +#define ANR_DS_REMOVE_BY(__ds, __ptr) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->remove_by((void*)__ds, (void*)__ptr) +#define ANR_DS_REMOVE_AT(__ds, __index) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->remove_at((void*)__ds, __index) +#define ANR_DS_INSERT(__ds, __index, __ptr) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->insert((void*)__ds, __index, (void*)__ptr) +#define ANR_DS_LENGTH(__ds) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->length((void*)__ds) +#define ANR_DS_ITER_START(__ds) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->iter_start((void*)__ds) +#define ANR_DS_ITER_NEXT(__ds, __iter) (_ds_arr[(int)(((anr_ds*)__ds)->ds_ll.ds_type)]).ds->iter_next((void*)__ds, __iter) + +#define ANR_ITERATE(__iter, __ds) \ + anr_iter __iter = ANR_DS_ITER_START((void*)__ds); \ + while (ANR_DS_ITER_NEXT((void*)__ds, &__iter)) + +#endif // INCLUDE_ANR_DATA_H + +#ifdef ANR_DATA_IMPLEMENTATION + +#ifdef ANR_DATA_DEBUG +anr_linked_list curr_print = (anr_linked_list){ANR_DS_LINKEDLIST, 0, 0, 0, 200}; +anr_linked_list prev_print = (anr_linked_list){ANR_DS_LINKEDLIST, 0, 0, 0, 200}; + +static void anr__print_diff() +{ + #define max(a,b) (((a) > (b)) ? (a) : (b)) + #define gotox(x) printf("\033[%dC", (x)) + #define moveup(y) printf("\033[%dA", y); + + int max_lines = max(prev_print.length, curr_print.length); + for (int i = 0; i < max_lines; i++) + { + char* curr_line = (i < curr_print.length) ? ANR_DS_FIND_AT(&curr_print, i) : 0; + if (curr_line) + { + printf("%s", curr_line); + if (i < prev_print.length) moveup(1); + } + + char* prev_line = (i < prev_print.length) ? ANR_DS_FIND_AT(&prev_print, i) : 0; + if (prev_line) + { + gotox(85); + int strl = strlen(prev_line); + for (int x = 0; x < strl; x++) { + char ch = prev_line[x]; + char is_same = (curr_line == NULL) ? 1 : ((x < strlen(curr_line) ? (ch == curr_line[x]) : 0)); + if (!is_same) printf("\033[0;31m%c\033[0m", ch); + else printf("%c", ch); + } + } + } + printf("\n"); + + // Next iteration. + ANR_DS_FREE(&prev_print); + prev_print = curr_print; + curr_print = (anr_linked_list){ANR_DS_LINKEDLIST, 0, 0, 0, 200}; +} + + +void anr_linked_list_print(void* ds) +{ + + anr_linked_list* list = ds; + anr_linked_list_node* iter = list->first; + uint32_t count = 0; + + char* buffer = malloc(200); + snprintf(buffer, 200, "List %p has %d nodes, first: %p last: %p\n", list, list->length, list->first, list->last); + ANR_DS_ADD(&curr_print, buffer); + while (iter) + { + char* buffer = malloc(200); + snprintf(buffer, 200, "#%d %p prev: %p next: %p\n", count, iter, iter->prev, iter->next); + ANR_DS_ADD(&curr_print, buffer); + iter = iter->next; + count++; + } + anr__print_diff(); +} +#else +void anr_linked_list_print(void* ds) +{ + (void)ds; +} +#endif + +uint32_t anr_linked_list_length(void* ds) +{ + anr_linked_list* list = ds; + return list->length; +} + +anr_iter anr_linked_list_iter_start(void* ds) +{ + (void)ds; + anr_iter iter; + iter.ll.node = NULL; + iter.index = -1; + iter.data = NULL; + return iter; +} + +uint8_t anr_linked_list_iter_next(void* ds, anr_iter* iter) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(iter); + anr_linked_list* list = ds; + if (iter->ll.node == NULL) iter->ll.node = list->first; + else iter->ll.node = iter->ll.node->next; + iter->index++; + iter->data = iter->ll.node != NULL ? ((uint8_t*)iter->ll.node)+offsetof(anr_linked_list_node, data) : 0; + return iter->ll.node != NULL; +} + +void anr_linked_list_free(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_linked_list* list = ds; + anr_linked_list_node* iter = list->last; + anr_linked_list_node* last = iter; + while (iter) + { + last = iter; + free(iter->next); + iter = iter->prev; + } + free(last); +} + +uint8_t anr_linked_list_insert(void* ds, uint32_t index, void* ptr) +{ + ANRDATA_ASSERT(ds); + anr_linked_list* list = ds; + + anr_linked_list_node* iter = list->first; + uint32_t count = 0; + + anr_linked_list_node* prev = NULL; + anr_linked_list_node* next = NULL; + list->last_access.index = 0; + list->last_access.node = 0; + + if (index == list->length) { + count = index; + prev = list->last; + next = NULL; + } + else { + while (iter) + { + if (count == index) { + break; + } + iter = iter->next; + count++; + } + + if (!iter) return 0; // out of bounds. + + prev = iter->prev; + next = iter; + } + + anr_linked_list_node* node = malloc(sizeof(anr_linked_list_node) + list->data_size - sizeof(void*)); + if (!node) return 0; + memcpy(((uint8_t*)node)+offsetof(anr_linked_list_node, data), ptr, list->data_size); + node->prev = prev; + node->next = next; + + list->last_access.index = index; + list->last_access.node = node; + + if (count == 0) { + list->first = node; + } + if (count == list->length) { + list->last = node; + } + + if (node->prev) { + ((anr_linked_list_node*)(node->prev))->next = node; + } + if (node->next) { + ((anr_linked_list_node*)(node->next))->prev = node; + } + list->length++; + + return 1; +} + +uint8_t anr_linked_list_remove_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + void* ptr = anr_linked_list_find_at(ds, index); + if (!ptr) return 0; + + anr_linked_list* list = ds; + anr_linked_list_node* iter = ptr - (offsetof(anr_linked_list_node, data)); + iter = iter->prev; + + uint8_t result = anr_linked_list_remove_by(ds, ptr); + list->last_access.index = index-1; + list->last_access.node = iter; + return result; +} + +uint8_t anr_linked_list_remove_by(void* ds, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + + anr_linked_list* list = ds; + anr_linked_list_node* iter = ptr - (offsetof(anr_linked_list_node, data)); + list->last_access.index = 0; + list->last_access.node = 0; + + if (iter == list->first) { + list->first = iter->next; + } + if (iter == list->last) { + list->last = iter->prev; + } + + if (iter->prev) { + ((anr_linked_list_node*)(iter->prev))->next = iter->next; + } + if (iter->next) { + ((anr_linked_list_node*)(iter->next))->prev = iter->prev; + } + + free(iter); + list->length--; + return 1; +} + +uint32_t anr_linked_list_find_by(void* ds, char* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_linked_list* list = ds; + anr_linked_list_node* iter = list->first; + uint32_t count = 0; + while (iter) + { + void* data = ((uint8_t*)iter)+offsetof(anr_linked_list_node, data); + if (memcmp(data, ptr, list->data_size) == 0) { + return count; + } + count++; + iter = iter->next; + } + return -1; +} + +void* anr_linked_list_find_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + anr_linked_list* list = ds; + + typedef struct + { + anr_linked_list_node* node; + uint32_t index; + } possible_start; + + possible_start waypoints[3] = { + (possible_start){list->first, 0}, + (possible_start){list->last_access.node, list->last_access.index}, + (possible_start){list->last, list->length-1} + }; + + uint32_t closest_waypoint = 0; + uint32_t closest_dist = UINT32_MAX; + uint32_t closest_index = 0; + for (int i = 0; i < 3; i++) { + if (waypoints[i].node) { + if (abs(waypoints[i].index - index) < closest_dist) { + closest_index = waypoints[i].index; + closest_waypoint = i; + closest_dist = abs(waypoints[i].index - index); + } + } + } + + uint8_t search_backwards = closest_index > index; + anr_linked_list_node* iter = waypoints[closest_waypoint].node; + uint32_t count = closest_index; + + while (iter) + { + if (count == index) return ((uint8_t*)iter)+offsetof(anr_linked_list_node, data); + iter = search_backwards ? iter->prev : iter->next; + search_backwards ? count-- : count++; + } + return 0; +} + +anr_linked_list anr_linked_list_create(uint32_t data_size) +{ + return (anr_linked_list){ANR_DS_LINKEDLIST, 0, 0, 0, data_size, {0}}; +} + +int32_t anr_linked_list_add(void* ds, void* ptr) +{ + // We dont need to iterate here.. + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_linked_list* list = ds; + anr_linked_list_node* iter = list->first; + do + { + if (iter == NULL || iter->next == NULL) { + anr_linked_list_node* node = malloc(sizeof(anr_linked_list_node) + list->data_size - sizeof(void*)); + if (!node) return -1; + memcpy(((uint8_t*)node)+offsetof(anr_linked_list_node, data), ptr, list->data_size); + node->prev = iter; + node->next = NULL; + iter == NULL ? (list->first = node) : (iter->next = node); + list->last = node; + list->length++; + return list->length-1; + } + + iter = iter->next; + } while (iter); + + ANRDATA_ASSERT(0); + return -1; +} + +anr_array anr_array_create(uint32_t data_size, uint32_t reserve_count) +{ + ANRDATA_ASSERT(data_size > 0); + ANRDATA_ASSERT(reserve_count > 0); + + anr_array arr = (anr_array){ANR_DS_DYNAMIC_ARRAY, .data = 0, .data_size = data_size, .length = 0, .reserve_size = reserve_count, .reserved = 0}; + arr.reserved = reserve_count; + arr.data = malloc(arr.reserved*data_size); + if (!arr.data) { + arr.reserve_size = 1; + arr.data = malloc(arr.reserved*data_size); // Try again with smallest possible size. + ANRDATA_ASSERT(arr.data); + } + + return arr; +} + +int32_t anr_array_add(void* ds, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + + anr_array* arr = (anr_array*)ds; + + arr->length++; + if (arr->reserved < arr->length) + { + arr->reserved += arr->reserve_size; + void* b = realloc(arr->data, arr->reserved*arr->data_size); + if (b) arr->data = b; + else return -1; + } + + memcpy(arr->data + ((arr->length-1) * arr->data_size), ptr, arr->data_size); + + return arr->length-1; +} + +void anr_array_free(void* ds) +{ + ANRDATA_ASSERT(ds); + + anr_array* arr = (anr_array*)ds; + free(arr->data); +} + +#ifdef ANR_DATA_DEBUG +void anr_array_print(void* ds) +{ + ANRDATA_ASSERT(ds); + + anr_array* arr = ds; + char* buffer = malloc(200); + snprintf(buffer, 200, "array %p has %d items, %d reserved\n", arr, arr->length, arr->reserved); + ANR_DS_ADD(&curr_print, buffer); + for (int i = 0; i < arr->length; i++) + { + char* buffer = malloc(200); + snprintf(buffer, 200, "#%d ", i); + char* data = anr_array_find_at(ds, i); + for (int x = 0; x < arr->data_size; x++) { + snprintf(buffer+strlen(buffer), 200, "%x", *(char*)(data + x)); + } + snprintf(buffer+strlen(buffer), 200, "\n"); + ANR_DS_ADD(&curr_print, buffer); + } + #ifdef ANR_DATA_DEBUG + anr__print_diff(); + #else + ANR_DS_FREE(&curr_print); + curr_print = (anr_linked_list){ANR_DS_LINKEDLIST, 0, 0, 0}; + #endif +} +#else +void anr_array_print(void* ds) +{ + (void)ds; +} +#endif + +void* anr_array_find_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + anr_array* arr = ds; + if(index >= arr->length) return 0; + + return arr->data + (index * arr->data_size); +} + +uint32_t anr_array_find_by(void* ds, char* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_array* arr = (anr_array*)ds; + + for (int i = 0; i < arr->length; i++) + { + void* data = anr_array_find_at(ds, i); + if (memcmp(data, ptr, arr->data_size) == 0) { + return i; + } + } + + return -1; +} + +uint8_t anr_array_remove_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + anr_array* arr = (anr_array*)ds; + if (index >= arr->length) return 0; + if (index < 0) return 0; + uint32_t mem_to_move = (arr->length - index - 1) * arr->data_size; + uint32_t mem_to_overwrite = index * arr->data_size; + uint32_t mem_to_copy = (index+1) * arr->data_size; + memmove(arr->data + mem_to_overwrite, arr->data + mem_to_copy, mem_to_move); + arr->length--; + + if (arr->length < arr->reserved / 2) { + arr->reserved /= 2; + void* b = realloc(arr->data, arr->reserved*arr->data_size); + if (b) arr->data = b; + } + return 1; +} + +uint8_t anr_array_remove_by(void* ds, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + + anr_array* arr = (anr_array*)ds; + uint32_t index = (ptr - arr->data) / arr->data_size; + + if (index == arr->length-1) { + arr->length--; + return 1; + } + + return anr_array_remove_at(ds, index); +} + +uint8_t anr_array_insert(void* ds, uint32_t index, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_array* arr = (anr_array*)ds; + if (index > arr->length) return 0; + if (index < 0) return 0; + + if (arr->length >= arr->reserved) + { + arr->reserved += arr->reserve_size; + void* b = realloc(arr->data, arr->reserved*arr->data_size); + if (b) arr->data = b; + else return 0; + } + + if (index == arr->length) return anr_array_add(ds, ptr); + + uint32_t mem_to_move = (arr->length - index) * arr->data_size; + uint32_t mem_to_overwrite = (index+1) * arr->data_size; + uint32_t mem_to_copy = (index) * arr->data_size; + memmove(arr->data + mem_to_overwrite, arr->data + mem_to_copy, mem_to_move); + memcpy(arr->data + index*arr->data_size, ptr, arr->data_size); + arr->length++; + return 1; +} + +uint32_t anr_array_length(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_array* arr = (anr_array*)ds; + return arr->length; +} + +anr_iter anr_array_iter_start(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_iter iter; + iter.index = -1; + iter.data = NULL; + return iter; +} + +uint8_t anr_array_iter_next(void* ds, anr_iter* iter) +{ + ANRDATA_ASSERT(ds); + iter->index++; + iter->data = anr_array_find_at(ds, iter->index); + return iter->data != NULL; +} + +anr_hashmap anr_hashmap_create(uint32_t data_size, uint32_t bucket_size) +{ + ANRDATA_ASSERT(data_size > 0); + ANRDATA_ASSERT(bucket_size > 0); + anr_hashmap hashmap = (anr_hashmap){.ds_type = ANR_DS_HASHMAP, .bucket_size = bucket_size, .data_size = data_size}; + hashmap.buckets = anr_array_create(sizeof(anr_hashmap_bucket), 1); + hashmap.last_emptied = -1; + hashmap.next_empty = -1; + return hashmap; +} + +int32_t anr_hashmap_add(void* ds, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_hashmap* hashmap = (anr_hashmap*)ds; + uint32_t item_size = hashmap->data_size + 1; + + if (hashmap->last_emptied != -1) { + int32_t index = hashmap->last_emptied; + anr_hashmap_insert(ds, index, ptr); + return index; + } + if (hashmap->next_empty != -1) { + int32_t index = hashmap->next_empty; + anr_hashmap_insert(ds, index, ptr); + return index; + } + + uint32_t highest_bucket_start = 0; + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + if (bb->bucket_start > highest_bucket_start) highest_bucket_start = bb->bucket_start; + for (int i = 0; i < hashmap->bucket_size; i++) + { + char* data = bb->data + (i * item_size); + if (data[0] == 1) continue; + memcpy(data+1, ptr, hashmap->data_size); + data[0] = 1; + hashmap->length++; + bb->length++; + + // Check if next slot is empty. + int32_t next_index = i+1; + if (next_index < hashmap->bucket_size) { + char* data = bb->data + (next_index * item_size); + if (data[0] == 0) hashmap->next_empty = next_index; + } + + return bb->bucket_start + i; + } + } + + // All buckets are full, create new one. + anr_hashmap_bucket new_bucket; + new_bucket.bucket_start = highest_bucket_start; + new_bucket.length = 0; + uint32_t alloc_size = (hashmap->bucket_size * hashmap->data_size) + hashmap->bucket_size; + new_bucket.data = malloc(alloc_size); + if (!new_bucket.data) return -1; + memset(new_bucket.data, 0, alloc_size); + uint32_t bucket_index = anr_array_add(&hashmap->buckets, &new_bucket); + if (bucket_index == -1) return -1; + anr_hashmap_bucket* bucket = anr_array_find_at(&hashmap->buckets, bucket_index); + hashmap->next_empty = new_bucket.bucket_start+1; // Bucket was just created so were sure its empty. + hashmap->length++; + char* data = bucket->data + (0 * item_size); + memcpy(data+1, ptr, hashmap->data_size); + data[0] = 1; + return new_bucket.bucket_start; +} + +void anr_hashmap_free(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_hashmap* hashmap = (anr_hashmap*)ds; + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + free(bb->data); + } + ANR_DS_FREE(&hashmap->buckets); +} + +void anr_hashmap_print(void* ds) +{ + ANRDATA_ASSERT(ds); + /* + anr_hashmap* hashmap = (anr_hashmap*)ds; + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + free(bb->data); + } + ANR_DS_FREE(&hashmap->buckets); + */ +} + +void* anr_hashmap_find_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + + anr_hashmap* hashmap = (anr_hashmap*)ds; + + int bucket_start = (index / hashmap->bucket_size) * hashmap->bucket_size; + int inner_index = index % hashmap->bucket_size; + uint32_t item_size = hashmap->data_size + 1; + + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + if (bb->bucket_start == bucket_start) { + char* data = bb->data + (inner_index * item_size); + if (data[0] == 1) return data+1; + + } + } + return 0; +} + +uint32_t anr_hashmap_find_by(void* ds, char* ptr) +{ + ANRDATA_ASSERT(ds); + if (ptr == NULL) return -1; + anr_hashmap* hashmap = (anr_hashmap*)ds; + uint32_t item_size = hashmap->data_size + 1; + + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + for (int i = 0; i < hashmap->bucket_size; i++) + { + char* data = bb->data + (i * item_size); + if (data[0] == 1) { + if (memcmp(data+1, ptr, hashmap->data_size) == 0) return bb->bucket_start + i; + } + } + } + + return -1; +} + +uint8_t anr_hashmap_remove_at(void* ds, uint32_t index) +{ + ANRDATA_ASSERT(ds); + anr_hashmap* hashmap = (anr_hashmap*)ds; + + int bucket_start = (index / hashmap->bucket_size) * hashmap->bucket_size; + int inner_index = index % hashmap->bucket_size; + + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + if (bb->bucket_start == bucket_start) { + uint32_t item_size = hashmap->data_size + 1; + char* data = bb->data + (inner_index * item_size); + if (data[0] == 1) { + data[0] = 0; + hashmap->length--; + bb->length--; + hashmap->last_emptied = index; + + if (bb->length == 0) { + ANR_DS_REMOVE_AT(&hashmap->buckets, iter.index); + } + return 1; + } + } + } + return 0; +} + +uint8_t anr_hashmap_remove_by(void* ds, void* ptr) +{ + ANRDATA_ASSERT(ds); + if (!ptr) return 0; + anr_hashmap* hashmap = (anr_hashmap*)ds; + uint32_t item_size = hashmap->data_size + 1; + + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + void* bucket_start = bb->data; + void* bucket_end = bb->data + (hashmap->bucket_size*item_size); + + if (ptr >= bucket_start && ptr <= bucket_end) + { + return anr_hashmap_remove_at(ds, bb->bucket_start + ((ptr - bucket_start) / item_size)); + } + } + + return 0; +} + +uint8_t anr_hashmap_insert(void* ds, uint32_t index, void* ptr) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(ptr); + anr_hashmap* hashmap = (anr_hashmap*)ds; + + int bucket_start = (index / hashmap->bucket_size) * hashmap->bucket_size; + int inner_index = index % hashmap->bucket_size; + + if (hashmap->last_emptied == index) { + hashmap->last_emptied = -1; + } + if (hashmap->next_empty == index) { + hashmap->next_empty = -1; + } + + anr_hashmap_bucket* bucket = NULL; + ANR_ITERATE(iter, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter.data; + if (bb->bucket_start == bucket_start) { + bucket = bb; + break; + } + } + + if (!bucket) { + // Bucket does not exist yet. create one. + anr_hashmap_bucket new_bucket; + new_bucket.bucket_start = bucket_start; + new_bucket.length = 0; + uint32_t alloc_size = (hashmap->bucket_size * hashmap->data_size) + hashmap->bucket_size; + new_bucket.data = malloc(alloc_size); + if (!new_bucket.data) return 0; + memset(new_bucket.data, 0, alloc_size); + int32_t bucket_index = anr_array_add(&hashmap->buckets, &new_bucket); + if (bucket_index == -1) return 0; + bucket = anr_array_find_at(&hashmap->buckets, bucket_index); + } + + uint32_t item_size = hashmap->data_size + 1; + hashmap->length++; + bucket->length++; + char* data = bucket->data + (inner_index * item_size); + data[0] = 1; + memcpy(data+1, ptr, hashmap->data_size); + return 1; +} + +uint32_t anr_hashmap_length(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_hashmap* hashmap = (anr_hashmap*)ds; + return hashmap->length; +} + +anr_iter anr_hashmap_iter_start(void* ds) +{ + ANRDATA_ASSERT(ds); + anr_iter iter; + iter.data = NULL; + iter.index = -1; + return iter; +} + +uint8_t anr_hashmap_iter_next(void* ds, anr_iter* iter) +{ + ANRDATA_ASSERT(ds); + ANRDATA_ASSERT(iter); + anr_hashmap* hashmap = (anr_hashmap*)ds; + uint32_t item_size = hashmap->data_size + 1; + + ANR_ITERATE(iter2, &hashmap->buckets) + { + anr_hashmap_bucket* bb = (anr_hashmap_bucket*)iter2.data; + for (int i = 0; i < hashmap->bucket_size; i++) + { + int32_t abs_index = bb->bucket_start + i; + char* data = bb->data + (i * item_size); + if (data[0] == 0) continue; + if (abs_index <= iter->index) continue; + + iter->index = i; + iter->data = data+1; + return 1; + } + } + return 0; +} + +#endif // ANR_DATA_IMPLEMENTATION + +/* +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2024 Aldrik Ramaekers +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +------------------------------------------------------------------------------ +*/
\ No newline at end of file |