From 7dfdb1744c99d874f7672250cd90b1b9d8d904f2 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 10 Aug 2022 21:24:37 -0400 Subject: Clean up symap implementation and run unit test --- src/symap.c | 119 +++++++++++++++++++++++++++++++++++------------------------- src/symap.h | 23 +++++------- 2 files changed, 80 insertions(+), 62 deletions(-) (limited to 'src') diff --git a/src/symap.c b/src/symap.c index 0dd4688..b034bd0 100644 --- a/src/symap.c +++ b/src/symap.c @@ -25,47 +25,45 @@ */ struct SymapImpl { - /// Unsorted array of strings, so symbols[i] is the symbol for ID i - 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; + char** symbols; ///< String array where symbols[i] is the symbol for ID i + uint32_t* index; ///< ID array sorted by corresponding string in `symbols` + uint32_t size; ///< Number of symbols (length of both symbols and index) + uint32_t pad; ///< Unused padding }; Symap* symap_new(void) { - Symap* map = (Symap*)malloc(sizeof(Symap)); - map->symbols = NULL; - map->index = NULL; - map->size = 0; + Symap* const map = (Symap*)calloc(1, sizeof(Symap)); + + if (map) { + map->symbols = NULL; + map->index = NULL; + map->size = 0U; + } + return map; } void -symap_free(Symap* map) +symap_free(Symap* const map) { - if (!map) { - return; - } + if (map) { + for (uint32_t i = 0U; 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) +symap_strdup(const char* const str) { const size_t len = strlen(str); - char* copy = (char*)malloc(len + 1); + char* const copy = (char*)malloc(len + 1); memcpy(copy, str, len + 1); return copy; } @@ -75,9 +73,10 @@ symap_strdup(const char* str) or the index where a new entry for `sym` should be inserted. */ static uint32_t -symap_search(const Symap* map, const char* sym, bool* exact) +symap_search(const Symap* const map, const char* const sym, bool* const exact) { *exact = false; + if (map->size == 0) { return 0; // Empty map, insert at 0 } @@ -115,12 +114,11 @@ symap_search(const Symap* map, const char* sym, bool* exact) } uint32_t -symap_try_map(Symap* map, const char* sym) +symap_try_map(const Symap* const map, const char* const 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]; } @@ -128,8 +126,9 @@ symap_try_map(Symap* map, const char* sym) } uint32_t -symap_map(Symap* map, const char* sym) +symap_map(Symap* const map, const char* sym) { + // Search for existing symbol bool exact = false; const uint32_t index = symap_search(map, sym, &exact); if (exact) { @@ -137,15 +136,28 @@ symap_map(Symap* map, const char* sym) return map->index[index]; } - const uint32_t id = ++map->size; - char* const str = symap_strdup(sym); + // Claim a new highest ID + const uint32_t id = map->size + 1; + + // Grow symbol array + char** new_symbols = (char**)realloc(map->symbols, id * sizeof(sym)); + if (!new_symbols) { + return 0; + } + + // Grow index array + uint32_t* new_index = (uint32_t*)realloc(map->index, id * sizeof(index)); + if (!new_index) { + return 0; + } // Append new symbol to symbols array - map->symbols = (char**)realloc(map->symbols, map->size * sizeof(str)); - map->symbols[id - 1] = str; + map->size = id; + map->symbols = new_symbols; + map->symbols[id - 1] = symap_strdup(sym); // Insert new index element into sorted index - map->index = (uint32_t*)realloc(map->index, map->size * sizeof(uint32_t)); + map->index = new_index; if (index < map->size - 1) { memmove(map->index + index + 1, map->index + index, @@ -158,7 +170,7 @@ symap_map(Symap* map, const char* sym) } const char* -symap_unmap(Symap* map, uint32_t id) +symap_unmap(const Symap* const map, const uint32_t id) { if (id == 0) { return NULL; @@ -171,12 +183,12 @@ symap_unmap(Symap* map, uint32_t id) return NULL; } -#ifdef STANDALONE +#ifdef SYMAP_STANDALONE # include static void -symap_dump(Symap* map) +symap_dump(Symap* const map) { fprintf(stderr, "{\n"); for (uint32_t i = 0; i < map->size; ++i) { @@ -186,35 +198,44 @@ symap_dump(Symap* map) fprintf(stderr, "}\n"); } -int -main() +static int +symap_test(Symap* const map) { # define N_SYMS 5 - char* syms[N_SYMS] = {"hello", "bonjour", "goodbye", "aloha", "salut"}; - Symap* map = symap_new(); + static const char* const syms[N_SYMS] = { + "hello", "bonjour", "goodbye", "aloha", "salut"}; + for (int i = 0; i < N_SYMS; ++i) { if (symap_try_map(map, syms[i])) { - fprintf(stderr, "error: Symbol already mapped\n"); - return 1; + return fprintf(stderr, "error: Symbol already mapped\n"); } 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 (!!strcmp(map->symbols[id - 1], syms[i])) { + return fprintf(stderr, "error: Corrupt symbol table\n"); } if (symap_map(map, syms[i]) != id) { - fprintf(stderr, "error: Remapped symbol to a different ID\n"); - return 1; + return fprintf(stderr, "error: Remapped symbol to a different ID\n"); } symap_dump(map); } - symap_free(map); return 0; + +# undef N_SYMS +} + +int +main(void) +{ + Symap* const map = symap_new(); + const int st = symap_test(map); + + symap_free(map); + return st; } -#endif // STANDALONE +#endif // SYMAP_STANDALONE diff --git a/src/symap.h b/src/symap.h index ed74157..74dc59a 100644 --- a/src/symap.h +++ b/src/symap.h @@ -12,11 +12,14 @@ #ifndef SYMAP_H #define SYMAP_H +#include "zix/attributes.h" + #include typedef struct SymapImpl Symap; /// Create a new symbol map +ZIX_MALLOC_FUNC Symap* symap_new(void); @@ -24,24 +27,18 @@ symap_new(void); void symap_free(Symap* map); -/// Map a string to a symbol ID if it is already mapped, otherwise return 0 +/// Map a string to a symbol if it is already mapped, otherwise return 0 +ZIX_PURE_FUNC uint32_t -symap_try_map(Symap* map, const char* sym); - -/** - Map a string to a symbol ID. +symap_try_map(const Symap* map, const char* sym); - Note that 0 is never a valid symbol ID. -*/ +/// Map a string to a symbol uint32_t symap_map(Symap* map, const char* sym); -/** - Unmap a symbol ID back to a symbol, or NULL if no such ID exists. - - Note that 0 is never a valid symbol ID. -*/ +/// Unmap a symbol back to a string if possible, otherwise return NULL +ZIX_PURE_FUNC const char* -symap_unmap(Symap* map, uint32_t id); +symap_unmap(const Symap* map, uint32_t id); #endif // SYMAP_H -- cgit v1.2.1