aboutsummaryrefslogtreecommitdiffstats
path: root/src/symap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/symap.c')
-rw-r--r--src/symap.c284
1 files changed, 141 insertions, 143 deletions
diff --git a/src/symap.c b/src/symap.c
index b699269..196c963 100644
--- a/src/symap.c
+++ b/src/symap.c
@@ -38,56 +38,56 @@
*/
struct SymapImpl {
- /**
- Unsorted array of strings, such that the symbol for ID i is found
- at symbols[i - 1].
- */
- char** symbols;
-
- /**
- Array of IDs, sorted by corresponding string in `symbols`.
- */
- uint32_t* index;
-
- /**
- Number of symbols (number of items in `symbols` and `index`).
- */
- uint32_t size;
+ /**
+ Unsorted array of strings, such that the symbol for ID i is found
+ at symbols[i - 1].
+ */
+ char** symbols;
+
+ /**
+ Array of IDs, sorted by corresponding string in `symbols`.
+ */
+ uint32_t* index;
+
+ /**
+ Number of symbols (number of items in `symbols` and `index`).
+ */
+ uint32_t size;
};
Symap*
symap_new(void)
{
- Symap* map = (Symap*)malloc(sizeof(Symap));
- map->symbols = NULL;
- map->index = NULL;
- map->size = 0;
- return map;
+ Symap* map = (Symap*)malloc(sizeof(Symap));
+ map->symbols = NULL;
+ map->index = NULL;
+ map->size = 0;
+ return map;
}
void
symap_free(Symap* map)
{
- if (!map) {
- return;
- }
+ if (!map) {
+ return;
+ }
- for (uint32_t i = 0; i < map->size; ++i) {
- free(map->symbols[i]);
- }
+ for (uint32_t i = 0; i < map->size; ++i) {
+ free(map->symbols[i]);
+ }
- free(map->symbols);
- free(map->index);
- free(map);
+ free(map->symbols);
+ free(map->index);
+ free(map);
}
static char*
symap_strdup(const char* str)
{
- const size_t len = strlen(str);
- char* copy = (char*)malloc(len + 1);
- memcpy(copy, str, len + 1);
- return copy;
+ const size_t len = strlen(str);
+ char* copy = (char*)malloc(len + 1);
+ memcpy(copy, str, len + 1);
+ return copy;
}
/**
@@ -97,146 +97,144 @@ symap_strdup(const char* str)
static uint32_t
symap_search(const Symap* map, const char* sym, bool* exact)
{
- *exact = false;
- if (map->size == 0) {
- return 0; // Empty map, insert at 0
- }
-
- if (strcmp(map->symbols[map->index[map->size - 1] - 1], sym) < 0) {
- return map->size; // Greater than last element, append
- }
-
- uint32_t lower = 0;
- uint32_t upper = map->size - 1;
- uint32_t i = upper;
- int cmp = 0;
-
- while (upper >= lower) {
- i = lower + ((upper - lower) / 2);
- cmp = strcmp(map->symbols[map->index[i] - 1], sym);
-
- if (cmp == 0) {
- *exact = true;
- return i;
- }
-
- if (cmp > 0) {
- if (i == 0) {
- break; // Avoid underflow
- }
- upper = i - 1;
- } else {
- lower = ++i;
- }
- }
-
- assert(!*exact || strcmp(map->symbols[map->index[i] - 1], sym) > 0);
- return i;
+ *exact = false;
+ if (map->size == 0) {
+ return 0; // Empty map, insert at 0
+ }
+
+ if (strcmp(map->symbols[map->index[map->size - 1] - 1], sym) < 0) {
+ return map->size; // Greater than last element, append
+ }
+
+ uint32_t lower = 0;
+ uint32_t upper = map->size - 1;
+ uint32_t i = upper;
+ int cmp = 0;
+
+ while (upper >= lower) {
+ i = lower + ((upper - lower) / 2);
+ cmp = strcmp(map->symbols[map->index[i] - 1], sym);
+
+ if (cmp == 0) {
+ *exact = true;
+ return i;
+ }
+
+ if (cmp > 0) {
+ if (i == 0) {
+ break; // Avoid underflow
+ }
+ upper = i - 1;
+ } else {
+ lower = ++i;
+ }
+ }
+
+ assert(!*exact || strcmp(map->symbols[map->index[i] - 1], sym) > 0);
+ return i;
}
uint32_t
symap_try_map(Symap* map, const char* sym)
{
- bool exact = false;
- const uint32_t index = symap_search(map, sym, &exact);
- if (exact) {
- assert(!strcmp(map->symbols[map->index[index]], sym));
- return map->index[index];
- }
-
- return 0;
+ bool exact = false;
+ const uint32_t index = symap_search(map, sym, &exact);
+ if (exact) {
+ assert(!strcmp(map->symbols[map->index[index]], sym));
+ return map->index[index];
+ }
+
+ return 0;
}
uint32_t
symap_map(Symap* map, const char* sym)
{
- bool exact = false;
- const uint32_t index = symap_search(map, sym, &exact);
- if (exact) {
- assert(!strcmp(map->symbols[map->index[index] - 1], sym));
- return map->index[index];
- }
-
- const uint32_t id = ++map->size;
- char* const str = symap_strdup(sym);
-
- /* Append new symbol to symbols array */
- map->symbols = (char**)realloc(map->symbols, map->size * sizeof(str));
- map->symbols[id - 1] = str;
-
- /* Insert new index element into sorted index */
- map->index = (uint32_t*)realloc(map->index, map->size * sizeof(uint32_t));
- if (index < map->size - 1) {
- memmove(map->index + index + 1,
- map->index + index,
- (map->size - index - 1) * sizeof(uint32_t));
- }
-
- map->index[index] = id;
-
- return id;
+ bool exact = false;
+ const uint32_t index = symap_search(map, sym, &exact);
+ if (exact) {
+ assert(!strcmp(map->symbols[map->index[index] - 1], sym));
+ return map->index[index];
+ }
+
+ const uint32_t id = ++map->size;
+ char* const str = symap_strdup(sym);
+
+ /* Append new symbol to symbols array */
+ map->symbols = (char**)realloc(map->symbols, map->size * sizeof(str));
+ map->symbols[id - 1] = str;
+
+ /* Insert new index element into sorted index */
+ map->index = (uint32_t*)realloc(map->index, map->size * sizeof(uint32_t));
+ if (index < map->size - 1) {
+ memmove(map->index + index + 1,
+ map->index + index,
+ (map->size - index - 1) * sizeof(uint32_t));
+ }
+
+ map->index[index] = id;
+
+ return id;
}
const char*
symap_unmap(Symap* map, uint32_t id)
{
- if (id == 0) {
- return NULL;
- }
+ if (id == 0) {
+ return NULL;
+ }
- if (id <= map->size) {
- return map->symbols[id - 1];
- }
+ if (id <= map->size) {
+ return map->symbols[id - 1];
+ }
- return NULL;
+ return NULL;
}
#ifdef STANDALONE
-#include <stdio.h>
+# include <stdio.h>
static void
symap_dump(Symap* map)
{
- fprintf(stderr, "{\n");
- for (uint32_t i = 0; i < map->size; ++i) {
- fprintf(stderr, "\t%u = %s\n",
- map->index[i], map->symbols[map->index[i] - 1]);
- }
- fprintf(stderr, "}\n");
+ fprintf(stderr, "{\n");
+ for (uint32_t i = 0; i < map->size; ++i) {
+ fprintf(
+ stderr, "\t%u = %s\n", map->index[i], map->symbols[map->index[i] - 1]);
+ }
+ fprintf(stderr, "}\n");
}
int
main()
{
- #define N_SYMS 5
- char* syms[N_SYMS] = {
- "hello", "bonjour", "goodbye", "aloha", "salut"
- };
-
- Symap* map = symap_new();
- for (int i = 0; i < N_SYMS; ++i) {
- if (symap_try_map(map, syms[i])) {
- fprintf(stderr, "error: Symbol already mapped\n");
- return 1;
- }
-
- const uint32_t id = symap_map(map, syms[i]);
- if (strcmp(map->symbols[id - 1], syms[i])) {
- fprintf(stderr, "error: Corrupt symbol table\n");
- return 1;
- }
-
- if (symap_map(map, syms[i]) != id) {
- fprintf(stderr, "error: Remapped symbol to a different ID\n");
- return 1;
- }
-
- symap_dump(map);
- }
-
- symap_free(map);
- return 0;
+# define N_SYMS 5
+ char* syms[N_SYMS] = {"hello", "bonjour", "goodbye", "aloha", "salut"};
+
+ Symap* map = symap_new();
+ for (int i = 0; i < N_SYMS; ++i) {
+ if (symap_try_map(map, syms[i])) {
+ fprintf(stderr, "error: Symbol already mapped\n");
+ return 1;
+ }
+
+ const uint32_t id = symap_map(map, syms[i]);
+ if (strcmp(map->symbols[id - 1], syms[i])) {
+ fprintf(stderr, "error: Corrupt symbol table\n");
+ return 1;
+ }
+
+ if (symap_map(map, syms[i]) != id) {
+ fprintf(stderr, "error: Remapped symbol to a different ID\n");
+ return 1;
+ }
+
+ symap_dump(map);
+ }
+
+ symap_free(map);
+ return 0;
}
#endif /* STANDALONE */
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-20 00:45:58 +0000