From 9e874301350a70a1ba40b5508878d559f68f8f4a Mon Sep 17 00:00:00 2001 From: Mosder Date: Tue, 28 Jul 2026 16:38:04 +0200 Subject: refactor: generalized dynamic arrays with structures/array.h --- analyzer/structures/array.c | 110 ++++++++++++++++++++++++++++++++++++++++++ analyzer/structures/array.h | 80 ++++++++++++++++++++++++++++++ analyzer/structures/hashmap.c | 28 +++++------ analyzer/structures/hashmap.h | 22 ++++----- analyzer/structures/heap.c | 73 +++++++++++++--------------- analyzer/structures/heap.h | 30 ++++++------ 6 files changed, 264 insertions(+), 79 deletions(-) create mode 100644 analyzer/structures/array.c create mode 100644 analyzer/structures/array.h (limited to 'analyzer/structures') diff --git a/analyzer/structures/array.c b/analyzer/structures/array.c new file mode 100644 index 0000000..ecdc0df --- /dev/null +++ b/analyzer/structures/array.c @@ -0,0 +1,110 @@ +#include "structures/array.h" + +#include +#include + +#include "utils/memory.h" + +DynArray array_new(size_t el_size, size_t capacity, void (*el_cleanup)(void *el)) { + // clang-format off + DynArray array = { + .data = safe_malloc(capacity * el_size), + .el_size = el_size, + .count = 0, + .capacity = capacity, + .el_cleanup = el_cleanup + }; + // clang-format on + return array; +} + +void *array_get(DynArray array, size_t index) { + if (index >= array.count) + return NULL; + return (char *)array.data + index * array.el_size; +} + +void *array_next(DynArray array, void *prev) { + // if NULL - return first or NULL if count is 0 + if (!prev) + return array.count == 0 ? NULL : array.data; + + ptrdiff_t byte_diff = (char *)prev - (char *)array.data; + + // if outside of range / prev was last - return NULL + if (byte_diff < 0 || (size_t)byte_diff >= (array.count - 1) * array.el_size) + return NULL; + + return (char *)prev + array.el_size; +} + +// expand an array +void array_expand(DynArray *array, size_t to_fit) { + while (array->capacity < to_fit) + array->capacity *= 2; + array->data = safe_realloc(array->data, array->capacity * array->el_size); +} + +void array_put(DynArray *array, size_t index, void *val) { + if (index >= array->capacity) + array_expand(array, index + 1); + + if (index < array->count && array->el_cleanup) + array->el_cleanup(array_get(*array, index)); + + memcpy((char *)array->data + index * array->el_size, val, array->el_size); + + if (index >= array->count) + array->count = index + 1; +} + +void array_append(DynArray *array, void *val) { + if (array->count >= array->capacity) + array_expand(array, array->count + 1); + memcpy((char *)array->data + array->count++ * array->el_size, val, array->el_size); +} + +void array_concat(DynArray *array, void *arr2, size_t len2) { + if (array->count + len2 > array->capacity) + array_expand(array, array->count + len2); + memcpy((char *)array->data + array->count * array->el_size, arr2, len2 * array->el_size); + array->count += len2; +} + +void array_remove_front(DynArray *array, size_t to_remove) { + if (to_remove >= array->count) { + array->count = 0; + return; + } + + if (array->el_cleanup) { + for (size_t i = 0; i < to_remove; i++) + array->el_cleanup(array_get(*array, i)); + } + + array->count -= to_remove; + memmove(array->data, (char *)array->data + to_remove * array->el_size, array->count * array->el_size); +} + +void array_remove_back(DynArray *array, size_t to_remove) { + if (to_remove >= array->count) { + array->count = 0; + return; + } + + if (array->el_cleanup) { + for (size_t i = 0; i < to_remove; i++) + array->el_cleanup(array_get(*array, array->count - i - 1)); + } + + array->count -= to_remove; +} + +void array_destroy(DynArray array) { + if (array.el_cleanup) { + void *el = NULL; + while ((el = array_next(array, el))) + array.el_cleanup(el); + } + free(array.data); +} diff --git a/analyzer/structures/array.h b/analyzer/structures/array.h new file mode 100644 index 0000000..5f65bc3 --- /dev/null +++ b/analyzer/structures/array.h @@ -0,0 +1,80 @@ +// structures/array.h +// implementation of dynamic array + +#include + +#ifndef ARRAY_H +#define ARRAY_H + +typedef struct { + void *data; // array elements + size_t el_size; // element size + size_t count; // element count + size_t capacity; // array capacity + void (*el_cleanup)(void *el); // element cleanup function +} DynArray; + +// create new dynamic array of given el_size and capacity +// params: +// - el_size - size of the element to be in array +// - capacity - initial capacity of the array +// - cleanup - element cleanup function (if there are any internal allocations) +// if no internal allocations - should be NULL +// returns: +// newly created DynArray +extern DynArray array_new(size_t el_size, size_t capacity, void (*el_cleanup)(void *el)); + +// get (the pointer to) an element in the array +// params: +// - array - array to get from +// - index - index of the elment to get +// returns: +// pointer to the element to get or NULL if it doesn't exist +extern void *array_get(DynArray array, size_t index); + +// get the next element in the array +// params: +// - array - array to get next element from +// - prev - previous element of the array, if NULL gets first +// returns: +// pointer to the next element or NULL prev was the last one +extern void *array_next(DynArray array, void *prev); + +// put an element into the array +// params: +// - array - array to put to +// - index - index to put to +// - val - pointer to the value to put +extern void array_put(DynArray *array, size_t index, void *val); + +// append to array, expand if necessary +// params: +// - array - array to append to +// - val - pointer to the value to append to the array +extern void array_append(DynArray *array, void *val); + +// concatenate 2 arrays, expand if necessary +// params: +// - array - first array (destination) +// - arr2 - second array (doesn't have to be dynamic) +// - len2 - length of arr2 +extern void array_concat(DynArray *array, void *arr2, size_t len2); + +// remove given count of elements from the front of the array +// params: +// - array - array to remove from +// - to_remove - count of elements to remove +extern void array_remove_front(DynArray *array, size_t to_remove); + +// remove given count of elements from the back of the array +// params: +// - array - array to remove from +// - to_remove - count of elements to remove +extern void array_remove_back(DynArray *array, size_t to_remove); + +// destroy the array +// params: +// - array - array to destroy +extern void array_destroy(DynArray array); + +#endif diff --git a/analyzer/structures/hashmap.c b/analyzer/structures/hashmap.c index 5eb27ae..53fd5fc 100644 --- a/analyzer/structures/hashmap.c +++ b/analyzer/structures/hashmap.c @@ -7,25 +7,25 @@ HashMap *hashmap_new( size_t key_size, - size_t value_size, + size_t val_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), - void (*value_cleanup)(void *key) + void (*val_cleanup)(void *val) ) { HashMap *map = safe_malloc(sizeof(HashMap)); // initialize NULLs memset(map->table, 0, HASHMAP_TABLE_SIZE * sizeof(HashMapNode *)); map->key_size = key_size; - map->value_size = value_size; + map->val_size = val_size; map->hash = hash; map->compare = compare; map->key_cleanup = key_cleanup; - map->value_cleanup = value_cleanup; + map->val_cleanup = val_cleanup; return map; } -void hashmap_put(HashMap *map, void *key, void *value) { +void hashmap_put(HashMap *map, void *key, void *val) { size_t key_hash = map->hash(key); HashMapNode *node = map->table[key_hash]; @@ -34,10 +34,10 @@ void hashmap_put(HashMap *map, void *key, void *value) { // if it exists - update node if (map->compare(key, node->key)) { // ensure no hanging memory allocation - if (map->value_cleanup) { - map->value_cleanup(node->value); + if (map->val_cleanup) { + map->val_cleanup(node->val); } - memcpy(node->value, value, map->value_size); + memcpy(node->val, val, map->val_size); return; } node = node->next; @@ -46,9 +46,9 @@ void hashmap_put(HashMap *map, void *key, void *value) { // if it doesn't exist - create new node HashMapNode *new_node = safe_malloc(sizeof(HashMapNode)); new_node->key = safe_malloc(map->key_size); - new_node->value = safe_malloc(map->value_size); + new_node->val = safe_malloc(map->val_size); memcpy(new_node->key, key, map->key_size); - memcpy(new_node->value, value, map->value_size); + memcpy(new_node->val, val, map->val_size); // put in front of the linked list new_node->next = map->table[key_hash]; @@ -63,7 +63,7 @@ void *hashmap_get(HashMap *map, void *key) { while (node) { // if it exists - return the value pointer if (map->compare(key, node->key)) { - return node->value; + return node->val; } node = node->next; } @@ -76,11 +76,11 @@ void free_node_without_next(HashMap *map, HashMapNode *node) { if (map->key_cleanup) { map->key_cleanup(node->key); } - if (map->value_cleanup) { - map->value_cleanup(node->value); + if (map->val_cleanup) { + map->val_cleanup(node->val); } free(node->key); - free(node->value); + free(node->val); free(node); } diff --git a/analyzer/structures/hashmap.h b/analyzer/structures/hashmap.h index 528f24a..10637f1 100644 --- a/analyzer/structures/hashmap.h +++ b/analyzer/structures/hashmap.h @@ -7,24 +7,24 @@ typedef struct HashMapNode { void *key; - void *value; + void *val; struct HashMapNode *next; } HashMapNode; typedef struct { HashMapNode *table[HASHMAP_TABLE_SIZE]; size_t key_size; - size_t value_size; + size_t val_size; size_t (*hash)(void *key); int (*compare)(void *key1, void *key2); void (*key_cleanup)(void *key); - void (*value_cleanup)(void *value); + void (*val_cleanup)(void *val); } HashMap; // create a new hash map // params: // - key_size - size of the key type -// - value_size - size of the value type +// - val_size - size of the value type // - hash - function for hashing keys // params: // - key - pointer to the key to hash @@ -40,27 +40,27 @@ typedef struct { // if it has no heap allocations, this should be NULL // params: // - key - pointer to the key to cleanup -// - value_cleanup - function for cleaning up any internal allocations inside node->value (not the value itself) -// if it has no heap allocations, this should be NULL +// - val_cleanup - function for cleaning up any internal allocations inside node->val (not the value itself) +// if it has no heap allocations, this should be NULL // params: -// - value - pointer to the value to cleanup +// - val - pointer to the value to cleanup // returns: // pointer to the new hash map extern HashMap *hashmap_new( size_t key_size, - size_t value_size, + size_t val_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), - void (*value_cleanup)(void *value) + void (*val_cleanup)(void *val) ); // create/update an entry in a hash map // params: // - map - hash map to insert to // - key - pointer to the key -// - value - pointer to the value -extern void hashmap_put(HashMap *map, void *key, void *value); +// - val - pointer to the value +extern void hashmap_put(HashMap *map, void *key, void *val); // get the value of given key from a hash map // params: diff --git a/analyzer/structures/heap.c b/analyzer/structures/heap.c index 1267668..8f34ef2 100644 --- a/analyzer/structures/heap.c +++ b/analyzer/structures/heap.c @@ -5,14 +5,14 @@ #include "utils/memory.h" -Heap *heap_new(size_t element_size, int (*compare)(void *element1, void *element2), void (*element_cleanup)(void *element)) { +Heap *heap_new(size_t el_size, int (*compare)(void *el1, void *el2), void (*el_cleanup)(void *el)) { Heap *heap = safe_malloc(sizeof(Heap)); - heap->data = safe_malloc(INIT_HEAP_CAPACITY * sizeof(void *)); - heap->n_elements = 0; - heap->element_size = element_size; + heap->data = safe_malloc(INIT_HEAP_CAPACITY * el_size); + heap->count = 0; + heap->el_size = el_size; heap->capacity = INIT_HEAP_CAPACITY; heap->compare = compare; - heap->element_cleanup = element_cleanup; + heap->el_cleanup = el_cleanup; return heap; } @@ -31,56 +31,50 @@ size_t right(size_t i) { return 2 * i + 2; } -// swap two elements -void swap(void **p_el1, void **p_el2) { - void *tmp = *p_el1; - *p_el1 = *p_el2; - *p_el2 = tmp; +// swap two elements in heap +void swap(Heap *heap, size_t i1, size_t i2) { + char tmp[heap->el_size]; + memcpy(tmp, heap->data + i1, heap->el_size); + memcpy(heap->data + i1, heap->data + i2, heap->el_size); + memcpy(heap->data + i2, tmp, heap->el_size); } // expand heap exponentially to fit el_count elements void expand_heap(Heap *heap, size_t el_count) { while (heap->capacity < el_count) heap->capacity = (heap->capacity << 1) | 1; - heap->data = safe_realloc(heap->data, heap->capacity * sizeof(void *)); + heap->data = safe_realloc(heap->data, heap->capacity * heap->el_size); } void heap_insert(Heap *heap, void *element) { // expand heap if capacity is too small - if (heap->n_elements >= heap->capacity) - expand_heap(heap, heap->n_elements + 1); + if (heap->count >= heap->capacity) + expand_heap(heap, heap->count + 1); // insert into the last position - size_t i = heap->n_elements; - heap->data[i] = safe_malloc(heap->element_size); - memcpy(heap->data[i], element, heap->element_size); - heap->n_elements++; + size_t i = heap->count++; + memcpy(heap->data + i, element, heap->count); // heapify up - while (i > 0 && heap->compare(heap->data[i], heap->data[parent(i)])) { - swap(&heap->data[i], &heap->data[parent(i)]); + while (i > 0 && heap->compare(heap->data + i, heap->data + parent(i))) { + swap(heap, i, parent(i)); i = parent(i); } } void *heap_top_get(Heap *heap) { - return heap->n_elements <= 0 ? NULL : heap->data[0]; -} - -void free_heap_element(Heap *heap, size_t index) { - if (heap->element_cleanup) - heap->element_cleanup(heap->data[index]); - free(heap->data[index]); + return heap->count <= 0 ? NULL : heap->data; } void heap_top_remove(Heap *heap) { - if (heap->n_elements <= 0) + if (heap->count <= 0) return; - free_heap_element(heap, 0); + if (heap->el_cleanup) + heap->el_cleanup(heap->data); // move last element to root - heap->data[0] = heap->data[--heap->n_elements]; + memcpy(heap->data, heap->data + --heap->count, heap->el_size); // heapify down size_t i = 0; @@ -88,16 +82,16 @@ void heap_top_remove(Heap *heap) { do { size_t l = left(i); size_t r = right(i); - size_t to_be_parent = i; + size_t new_par = i; - if (l < heap->n_elements && heap->compare(heap->data[l], heap->data[to_be_parent])) - to_be_parent = l; - if (r < heap->n_elements && heap->compare(heap->data[r], heap->data[to_be_parent])) - to_be_parent = r; + if (l < heap->count && heap->compare(heap->data + l, heap->data + new_par)) + new_par = l; + if (r < heap->count && heap->compare(heap->data + r, heap->data + new_par)) + new_par = r; - if ((changed = to_be_parent != i)) { - swap(&heap->data[to_be_parent], &heap->data[i]); - i = to_be_parent; + if ((changed = new_par != i)) { + swap(heap, new_par, i); + i = new_par; } } while (changed); } @@ -105,8 +99,9 @@ void heap_top_remove(Heap *heap) { void heap_free(Heap *heap) { if (!heap) return; - for (size_t i = 0; i < heap->n_elements; i++) { - free_heap_element(heap, i); + if (heap->el_cleanup) { + for (size_t i = 0; i < heap->count; i++) + heap->el_cleanup(heap->data + i); } free(heap->data); free(heap); diff --git a/analyzer/structures/heap.h b/analyzer/structures/heap.h index 1ae72c0..a2d7333 100644 --- a/analyzer/structures/heap.h +++ b/analyzer/structures/heap.h @@ -10,36 +10,36 @@ #define INIT_HEAP_CAPACITY (1 << INIT_HEAP_DEPTH) - 1 typedef struct { - void **data; - size_t n_elements; - size_t element_size; + void *data; + size_t count; + size_t el_size; size_t capacity; - int (*compare)(void *element1, void *element2); - void (*element_cleanup)(void *element); + int (*compare)(void *el1, void *el2); + void (*el_cleanup)(void *el); } Heap; // create a new heap // params: -// - element_size - size of the heap element +// - el_size - size of the heap element // - compare - function for comparing elements // params: -// - element1 - pointer to the first of the elements to compare -// - element2 - pointer to the second of the elements to compare +// - el1 - pointer to the first of the elements to compare +// - el2 - pointer to the second of the elements to compare // returns: -// truthy if element1 should be element2's parent (e.g. element1 > element2 for max heap), falsy otherwise -// - element_cleanup - function for cleaning up any internal allocations inside element (not the element itself) -// if it has no heap allocations, this should be NULL +// truthy if el1 should be el2's parent (e.g. el1 > el2 for max heap), falsy otherwise +// - el_cleanup - function for cleaning up any internal allocations inside element (not the element itself) +// if it has no heap allocations, this should be NULL // params: -// - element - pointer to the element to cleanup +// - el - pointer to the element to cleanup // returns: // pointer to the new heap -extern Heap *heap_new(size_t element_size, int (*compare)(void *element1, void *element2), void (*element_cleanup)(void *element)); +extern Heap *heap_new(size_t el_size, int (*compare)(void *el1, void *el2), void (*el_cleanup)(void *el)); // insert new element into the heap // params: // - heap - heap to insert to -// - element - pointer to the element to insert -extern void heap_insert(Heap *heap, void *element); +// - el - pointer to the element to insert +extern void heap_insert(Heap *heap, void *el); // get the top element from the heap // params: -- cgit v1.2.3