aboutsummaryrefslogtreecommitdiff
path: root/analyzer/utils/structures
diff options
context:
space:
mode:
Diffstat (limited to 'analyzer/utils/structures')
-rw-r--r--analyzer/utils/structures/hashmap.c108
-rw-r--r--analyzer/utils/structures/hashmap.h77
-rw-r--r--analyzer/utils/structures/heap.c109
-rw-r--r--analyzer/utils/structures/heap.h58
4 files changed, 0 insertions, 352 deletions
diff --git a/analyzer/utils/structures/hashmap.c b/analyzer/utils/structures/hashmap.c
deleted file mode 100644
index 5c7fdf9..0000000
--- a/analyzer/utils/structures/hashmap.c
+++ /dev/null
@@ -1,108 +0,0 @@
-#include "hashmap.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-HashMap *hashmap_new(
- size_t key_size, size_t value_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key),
- void (*value_cleanup)(void *key)
-) {
- HashMap *map = malloc(sizeof(HashMap));
- // initialize NULLs
- memset(map->table, 0, sizeof(HashMapNode *) * HASHMAP_TABLE_SIZE);
- map->key_size = key_size;
- map->value_size = value_size;
- map->hash = hash;
- map->compare = compare;
- map->key_cleanup = key_cleanup;
- map->value_cleanup = value_cleanup;
- return map;
-}
-
-void hashmap_put(HashMap *map, void *key, void *value) {
- size_t key_hash = map->hash(key);
- HashMapNode *node = map->table[key_hash];
-
- // check if it exists
- while (node) {
- // if it exists - update node
- if (map->compare(key, node->key)) {
- // ensure no hanging memory allocation
- if (map->value_cleanup) {
- map->value_cleanup(node);
- }
- memcpy(node->value, value, map->value_size);
- return;
- }
- node = node->next;
- }
-
- // if it doesn't exist - create new node
- HashMapNode *new_node = malloc(sizeof(HashMapNode));
- new_node->key = malloc(map->key_size);
- new_node->value = malloc(map->value_size);
- memcpy(new_node->key, key, map->key_size);
- memcpy(new_node->value, value, map->value_size);
-
- // put in front of the linked list
- new_node->next = map->table[key_hash];
- map->table[key_hash] = new_node;
-}
-
-void *hashmap_get(HashMap *map, void *key) {
- size_t key_hash = map->hash(key);
- HashMapNode *node = map->table[key_hash];
-
- // check if it exists
- while (node) {
- // if it exists - return the value pointer
- if (map->compare(key, node->key)) {
- return node->value;
- }
- node = node->next;
- }
-
- // if it doesn't exist - return NULL
- return NULL;
-}
-
-void free_node_without_next(HashMap *map, HashMapNode *node) {
- if (map->key_cleanup) {
- map->key_cleanup(node);
- }
- if (map->value_cleanup) {
- map->value_cleanup(node);
- }
- free(node->key);
- free(node->value);
- free(node);
-}
-
-void hashmap_delete(HashMap *map, void *key) {
- size_t key_hash = map->hash(key);
- HashMapNode **p_node = &map->table[key_hash];
-
- // check if it exists
- while (*p_node) {
- // if it exists - delete it
- if (map->compare(key, (*p_node)->key)) {
- HashMapNode *next = (*p_node)->next;
- free_node_without_next(map, *p_node);
- *p_node = next;
- return;
- }
- p_node = &(*p_node)->next;
- }
-}
-
-void hashmap_free(HashMap *map) {
- for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) {
- HashMapNode *curr = map->table[i];
- while (curr) {
- HashMapNode *next = curr->next;
- free_node_without_next(map, curr);
- curr = next;
- }
- }
- free(map);
-}
diff --git a/analyzer/utils/structures/hashmap.h b/analyzer/utils/structures/hashmap.h
deleted file mode 100644
index 4f8e24a..0000000
--- a/analyzer/utils/structures/hashmap.h
+++ /dev/null
@@ -1,77 +0,0 @@
-// utils/structures/hashmap.h
-// a simple implementation of hashmap using linked list
-
-#include <stddef.h>
-
-#define HASHMAP_TABLE_SIZE 128
-
-typedef struct HashMapNode {
- void *key;
- void *value;
- struct HashMapNode *next;
-} HashMapNode;
-
-typedef struct {
- HashMapNode *table[HASHMAP_TABLE_SIZE];
- size_t key_size;
- size_t value_size;
- size_t (*hash)(void *key);
- int (*compare)(void *key1, void *key2);
- void (*key_cleanup)(void *key);
- void (*value_cleanup)(void *value);
-} HashMap;
-
-// create a new hash map
-// params:
-// - key_size - size of the key type
-// - value_size - size of the value type
-// - hash - function for hashing keys
-// params:
-// - key - pointer to the key to hash
-// returns:
-// hash of the key (size_t in [0; HASHMAP_TABLE_SIZE))
-// - compare - function for comparing keys
-// params:
-// - key1 - pointer to the first of the keys to compare
-// - key2 - pointer to the second of the keys to compare
-// returns:
-// truthy if the keys are identical, falsy if they are different
-// - key_cleanup - function for cleaning up any internal allocations inside node->key (not the key itself)
-// 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
-// params:
-// - value - 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 (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key),
- void (*value_cleanup)(void *value)
-);
-
-// 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);
-
-// get the value of given key from a hash map
-// params:
-// - map - hash map to get from
-// - key - pointer to the key of the value to get
-// returns:
-// pointer to the value of specified key or NULL if it doesn't exist
-extern void *hashmap_get(HashMap *map, void *key);
-
-// delete an entry from a hash map
-// params:
-// - map - hash map to delete from
-// - key - pointer to the key of the entry to delete
-extern void hashmap_delete(HashMap *map, void *key);
-
-// free the hash map
-// - map - hash map to free
-extern void hashmap_free(HashMap *map);
diff --git a/analyzer/utils/structures/heap.c b/analyzer/utils/structures/heap.c
deleted file mode 100644
index 5310299..0000000
--- a/analyzer/utils/structures/heap.c
+++ /dev/null
@@ -1,109 +0,0 @@
-#include "heap.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-Heap *heap_new(size_t element_size, int (*compare)(void *element1, void *element2), void (*element_cleanup)(void *element)) {
- Heap *heap = malloc(sizeof(Heap));
- heap->data = malloc(INIT_HEAP_CAPACITY * sizeof(void *));
- heap->n_elements = 0;
- heap->element_size = element_size;
- heap->capacity = INIT_HEAP_CAPACITY;
- heap->compare = compare;
- heap->element_cleanup = element_cleanup;
- return heap;
-}
-
-// return index of parent in heap
-size_t parent(size_t i) {
- return (i - 1) / 2;
-}
-
-// return index of left child in heap
-size_t left(size_t i) {
- return 2 * i + 1;
-}
-
-// return index of right child in heap
-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;
-}
-
-// 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 = realloc(heap->data, heap->capacity * sizeof(void *));
-}
-
-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);
-
- // insert into the last position
- size_t i = heap->n_elements;
- heap->data[i] = malloc(heap->element_size);
- memcpy(heap->data[i], element, heap->element_size);
- heap->n_elements++;
-
- // heapify up
- while (i > 0 && heap->compare(heap->data[i], heap->data[parent(i)])) {
- swap(&heap->data[i], &heap->data[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]);
-}
-
-void heap_top_remove(Heap *heap) {
- if (heap->n_elements <= 0)
- return;
-
- free_heap_element(heap, 0);
-
- // move last element to root
- heap->data[0] = heap->data[--heap->n_elements];
-
- // heapify down
- size_t i = 0;
- int changed;
- do {
- size_t l = left(i);
- size_t r = right(i);
- size_t to_be_parent = 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 ((changed = to_be_parent != i)) {
- swap(&heap->data[to_be_parent], &heap->data[i]);
- i = to_be_parent;
- }
- } while (changed);
-}
-
-void heap_free(Heap *heap) {
- for (size_t i = 0; i < heap->n_elements; i++) {
- free_heap_element(heap, i);
- }
- free(heap->data);
- free(heap);
-}
diff --git a/analyzer/utils/structures/heap.h b/analyzer/utils/structures/heap.h
deleted file mode 100644
index eb3430b..0000000
--- a/analyzer/utils/structures/heap.h
+++ /dev/null
@@ -1,58 +0,0 @@
-// utils/structures/heap.h
-// a simple implementation of heap
-
-#include <stddef.h>
-
-#define INIT_HEAP_DEPTH 7
-#define INIT_HEAP_CAPACITY (1 << INIT_HEAP_DEPTH) - 1
-
-#ifndef HEAP_DEFINED
-#define HEAP_DEFINED
-typedef struct {
- void **data;
- size_t n_elements;
- size_t element_size;
- size_t capacity;
- int (*compare)(void *element1, void *element2);
- void (*element_cleanup)(void *element);
-} Heap;
-#endif
-
-// create a new heap
-// params:
-// - element_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
-// 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
-// params:
-// - element - 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));
-
-// 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);
-
-// get the top element from the heap
-// params:
-// - heap - heap to get the top element from
-// returns:
-// pointer to the top element in the heap or NULL if heap is empty
-extern void *heap_top_get(Heap *heap);
-
-// remove the top element from the heap
-// params:
-// - heap - heap to remove the top element from
-extern void heap_top_remove(Heap *heap);
-
-// free the heap
-// - heap - heap to free
-extern void heap_free(Heap *heap);
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-25 01:04:15 +0000