From f1d1feabec428bf9ffc2c786d28ce7cc95725d48 Mon Sep 17 00:00:00 2001 From: Mosder Date: Mon, 6 Jul 2026 09:47:09 +0200 Subject: fix: fixed includes in utils/fs.c. also YAGNI --- analyzer/utils/fs.c | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) (limited to 'analyzer/utils/fs.c') diff --git a/analyzer/utils/fs.c b/analyzer/utils/fs.c index 76fb581..2dd8191 100644 --- a/analyzer/utils/fs.c +++ b/analyzer/utils/fs.c @@ -1,8 +1,9 @@ -#include "utils.h" +#include "fs.h" -#include +#include +#include +#include #include -#include void get_home_dir(char *home_dir) { strcpy(home_dir, getenv("HOME")); @@ -35,9 +36,3 @@ void create_necessary_directories() { mkdir(capture_dir, 0755); mkdir(saves_dir, 0755); } - -void write_file(char *path, void *contents, int contents_len, int flags, mode_t permissions) { - int fd = open(path, flags, permissions); - write(fd, contents, contents_len); - close(fd); -} -- cgit v1.2.3 From 106e1f7a579a66c46cb68356f585917fe7883310 Mon Sep 17 00:00:00 2001 From: Mosder Date: Tue, 14 Jul 2026 11:08:32 +0200 Subject: refactor: generalized Makefile by adding CC and CFLAGS variables. Changed from realtive to absolute paths for includes --- Makefile | 31 ++++----- analyzer/parser/fight_results.c | 2 +- analyzer/parser/fight_results.h | 4 +- analyzer/parser/find_parse_functions.h | 2 +- analyzer/parser/parser.c | 4 +- analyzer/parser/parser.h | 6 +- analyzer/parser/parser_defs.h | 2 +- analyzer/structures/hashmap.c | 112 +++++++++++++++++++++++++++++++++ analyzer/structures/hashmap.h | 81 ++++++++++++++++++++++++ analyzer/structures/heap.c | 109 ++++++++++++++++++++++++++++++++ analyzer/structures/heap.h | 58 +++++++++++++++++ analyzer/utils/fs.c | 2 +- analyzer/utils/structures/hashmap.c | 108 ------------------------------- analyzer/utils/structures/hashmap.h | 77 ----------------------- analyzer/utils/structures/heap.c | 109 -------------------------------- analyzer/utils/structures/heap.h | 58 ----------------- analyzer/utils/tcp.c | 4 +- analyzer/utils/tcp_seq_math.c | 2 +- analyzer/utils/time.c | 2 +- 19 files changed, 392 insertions(+), 381 deletions(-) create mode 100644 analyzer/structures/hashmap.c create mode 100644 analyzer/structures/hashmap.h create mode 100644 analyzer/structures/heap.c create mode 100644 analyzer/structures/heap.h delete mode 100644 analyzer/utils/structures/hashmap.c delete mode 100644 analyzer/utils/structures/hashmap.h delete mode 100644 analyzer/utils/structures/heap.c delete mode 100644 analyzer/utils/structures/heap.h (limited to 'analyzer/utils/fs.c') diff --git a/Makefile b/Makefile index e5a9c54..2455ece 100644 --- a/Makefile +++ b/Makefile @@ -1,31 +1,34 @@ +CC=gcc +CFLAGS=-iquote ./analyzer + global: compile sudo mv branal /usr/bin local: compile mv branal ${HOME}/.local/bin -compile: utils capture analyzer parser - gcc *.o main.c -lpcap -o branal +compile: structures utils capture analyzer parser + $(CC) $(CFLAGS) -lpcap *.o main.c -o branal rm *.o -utils: structures - gcc -c analyzer/utils/fs.c - gcc -c analyzer/utils/time.c - gcc -c analyzer/utils/tcp.c - gcc -c analyzer/utils/tcp_seq_math.c - structures: - gcc -c analyzer/utils/structures/hashmap.c - gcc -c analyzer/utils/structures/heap.c + $(CC) $(CFLAGS) -c analyzer/structures/hashmap.c + $(CC) $(CFLAGS) -c analyzer/structures/heap.c + +utils: + $(CC) $(CFLAGS) -c analyzer/utils/fs.c + $(CC) $(CFLAGS) -c analyzer/utils/time.c + $(CC) $(CFLAGS) -c analyzer/utils/tcp.c + $(CC) $(CFLAGS) -c analyzer/utils/tcp_seq_math.c capture: - gcc -c analyzer/capture.c + $(CC) $(CFLAGS) -c analyzer/capture.c analyzer: - gcc -c analyzer/analyzer.c + $(CC) $(CFLAGS) -c analyzer/analyzer.c parser: - gcc -c analyzer/parser/parser.c - gcc -c analyzer/parser/fight_results.c + $(CC) $(CFLAGS) -c analyzer/parser/parser.c + $(CC) $(CFLAGS) -c analyzer/parser/fight_results.c .PHONY: analyzer diff --git a/analyzer/parser/fight_results.c b/analyzer/parser/fight_results.c index 4fbb0f8..65e72ea 100644 --- a/analyzer/parser/fight_results.c +++ b/analyzer/parser/fight_results.c @@ -1,4 +1,4 @@ -#include "fight_results.h" +#include "parser/fight_results.h" #include #include diff --git a/analyzer/parser/fight_results.h b/analyzer/parser/fight_results.h index 4e1ea60..de7f525 100644 --- a/analyzer/parser/fight_results.h +++ b/analyzer/parser/fight_results.h @@ -1,8 +1,8 @@ // parser/fight_results.h // utilities for parsing the fight results data -#include "../utils/tcp.h" -#include "parser_defs.h" +#include "parser/parser_defs.h" +#include "utils/tcp.h" // Payload structure: // FIGHT_RESULTS_START EntityResults (SEPARATOR_ENTITY EntityResults)* FIGHT_RESULTS_END diff --git a/analyzer/parser/find_parse_functions.h b/analyzer/parser/find_parse_functions.h index 4e53274..dd7579e 100644 --- a/analyzer/parser/find_parse_functions.h +++ b/analyzer/parser/find_parse_functions.h @@ -1,7 +1,7 @@ // parser/find_parse_functions.h // array of find and parse functions for every result type -#include "fight_results.h" +#include "parser/fight_results.h" #define RESULT_TYPE_COUNT 1 diff --git a/analyzer/parser/parser.c b/analyzer/parser/parser.c index 246635c..3ef48b5 100644 --- a/analyzer/parser/parser.c +++ b/analyzer/parser/parser.c @@ -1,8 +1,8 @@ -#include "parser.h" +#include "parser/parser.h" #include -#include "find_parse_functions.h" +#include "parser/find_parse_functions.h" // expand parsed data exponentially to fit el_count elements ParsedData *expand_parsed_data(ParsedData *parsed_data, size_t *capacity, size_t el_count) { diff --git a/analyzer/parser/parser.h b/analyzer/parser/parser.h index e2d5c5d..4b28aa7 100644 --- a/analyzer/parser/parser.h +++ b/analyzer/parser/parser.h @@ -1,9 +1,9 @@ // parser/parser.h // main parser file -#include "../utils/tcp.h" -#include "fight_results.h" -#include "parser_defs.h" +#include "parser/fight_results.h" +#include "parser/parser_defs.h" +#include "utils/tcp.h" #define INIT_PARSED_DATA_CAPACITY 4 diff --git a/analyzer/parser/parser_defs.h b/analyzer/parser/parser_defs.h index b76b7e6..6af6059 100644 --- a/analyzer/parser/parser_defs.h +++ b/analyzer/parser/parser_defs.h @@ -1,7 +1,7 @@ // parser/parser_defs.h // useful definitions for parser files -#include "../utils/tcp.h" +#include "utils/tcp.h" #ifndef TYPE_ENUM_DEFINED #define TYPE_ENUM_DEFINED diff --git a/analyzer/structures/hashmap.c b/analyzer/structures/hashmap.c new file mode 100644 index 0000000..ed2eb4b --- /dev/null +++ b/analyzer/structures/hashmap.c @@ -0,0 +1,112 @@ +#include "structures/hashmap.h" + +#include +#include + +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/structures/hashmap.h b/analyzer/structures/hashmap.h new file mode 100644 index 0000000..528f24a --- /dev/null +++ b/analyzer/structures/hashmap.h @@ -0,0 +1,81 @@ +// structures/hashmap.h +// a simple implementation of hashmap using linked list + +#include + +#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/structures/heap.c b/analyzer/structures/heap.c new file mode 100644 index 0000000..690aac1 --- /dev/null +++ b/analyzer/structures/heap.c @@ -0,0 +1,109 @@ +#include "structures/heap.h" + +#include +#include + +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/structures/heap.h b/analyzer/structures/heap.h new file mode 100644 index 0000000..8a23164 --- /dev/null +++ b/analyzer/structures/heap.h @@ -0,0 +1,58 @@ +// structures/heap.h +// a simple implementation of heap + +#include + +#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); diff --git a/analyzer/utils/fs.c b/analyzer/utils/fs.c index 2dd8191..5e3eb1c 100644 --- a/analyzer/utils/fs.c +++ b/analyzer/utils/fs.c @@ -1,4 +1,4 @@ -#include "fs.h" +#include "utils/fs.h" #include #include 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 -#include - -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 - -#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 -#include - -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 - -#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); diff --git a/analyzer/utils/tcp.c b/analyzer/utils/tcp.c index 56df842..ab5303e 100644 --- a/analyzer/utils/tcp.c +++ b/analyzer/utils/tcp.c @@ -1,4 +1,4 @@ -#include "tcp.h" +#include "utils/tcp.h" #include #include @@ -6,7 +6,7 @@ #include #include -#include "tcp_seq_math.h" +#include "utils/tcp_seq_math.h" // initalize default TCP segment TCPSegment new_segment() { diff --git a/analyzer/utils/tcp_seq_math.c b/analyzer/utils/tcp_seq_math.c index 272cb5a..2cc6e3f 100644 --- a/analyzer/utils/tcp_seq_math.c +++ b/analyzer/utils/tcp_seq_math.c @@ -1,4 +1,4 @@ -#include "tcp_seq_math.h" +#include "utils/tcp_seq_math.h" int seq_after(uint32_t a, uint32_t b) { return (int32_t)(a - b) > 0; diff --git a/analyzer/utils/time.c b/analyzer/utils/time.c index 72c0bc7..d95da65 100644 --- a/analyzer/utils/time.c +++ b/analyzer/utils/time.c @@ -1,4 +1,4 @@ -#include "time.h" +#include "utils/time.h" #include #include -- cgit v1.2.3