aboutsummaryrefslogtreecommitdiffstats
path: root/src/symap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/symap.c')
-rw-r--r--src/symap.c343
1 files changed, 178 insertions, 165 deletions
diff --git a/src/symap.c b/src/symap.c
index afcdadb..07002f2 100644
--- a/src/symap.c
+++ b/src/symap.c
@@ -1,18 +1,5 @@
-/*
- Copyright 2011-2014 David Robillard <http://drobilla.net>
-
- Permission to use, copy, modify, and/or distribute this software for any
- purpose with or without fee is hereby granted, provided that the above
- copyright notice and this permission notice appear in all copies.
-
- THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
+// Copyright 2011-2022 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
#include "symap.h"
@@ -38,56 +25,47 @@
*/
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;
+ 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;
- return map;
+ 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;
- }
-
- for (uint32_t i = 0; i < map->size; ++i) {
- free(map->symbols[i]);
- }
-
- free(map->symbols);
- free(map->index);
- free(map);
+ if (map) {
+ for (uint32_t i = 0U; i < map->size; ++i) {
+ free(map->symbols[i]);
+ }
+
+ 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);
- memcpy(copy, str, len + 1);
- return copy;
+ const size_t len = strlen(str);
+ char* const copy = (char*)malloc(len + 1);
+ memcpy(copy, str, len + 1);
+ return copy;
}
/**
@@ -95,141 +73,176 @@ 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
- } else 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;
-
- while (upper >= lower) {
- i = lower + ((upper - lower) / 2);
- cmp = strcmp(map->symbols[map->index[i] - 1], sym);
-
- if (cmp == 0) {
- *exact = true;
- return i;
- } else 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)
+symap_try_map(const Symap* const map, const char* const sym)
{
- bool exact;
- 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) {
+ return map->index[index];
+ }
+
+ return 0;
}
uint32_t
-symap_map(Symap* map, const char* sym)
+symap_map(Symap* const map, const char* sym)
{
- bool exact;
- 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;
+ // Search for existing symbol
+ 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];
+ }
+
+ // 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;
+ }
+
+ map->symbols = new_symbols;
+
+ // Grow index array
+ uint32_t* new_index = (uint32_t*)realloc(map->index, id * sizeof(index));
+ if (!new_index) {
+ return 0;
+ }
+
+ map->index = new_index;
+
+ // Append new symbol to symbols array
+ map->size = id;
+ map->symbols[id - 1] = symap_strdup(sym);
+
+ // Insert new index element into sorted index
+ map->index = new_index;
+ 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)
+symap_unmap(const Symap* const map, const uint32_t id)
{
- if (id == 0) {
- return NULL;
- } else if (id <= map->size) {
- return map->symbols[id - 1];
- }
- return NULL;
+ if (id == 0) {
+ return NULL;
+ }
+
+ if (id <= map->size) {
+ return map->symbols[id - 1];
+ }
+
+ return NULL;
}
-#ifdef STANDALONE
+#ifdef SYMAP_STANDALONE
-#include <stdio.h>
+# include <stdio.h>
static void
-symap_dump(Symap* map)
+symap_dump(Symap* const 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");
+}
+
+static int
+symap_test(Symap* const 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");
+# define N_SYMS 5
+
+ 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])) {
+ return fprintf(stderr, "error: Symbol already mapped\n");
+ }
+
+ const uint32_t id = symap_map(map, syms[i]);
+ if (!id) {
+ return fprintf(stderr, "error: Failed to insert ID\n");
+ }
+
+ if (!!strcmp(map->symbols[id - 1], syms[i])) {
+ return fprintf(stderr, "error: Corrupt symbol table\n");
+ }
+
+ if (symap_map(map, syms[i]) != id) {
+ return fprintf(stderr, "error: Remapped symbol to a different ID\n");
+ }
+
+ symap_dump(map);
+ }
+
+ return 0;
+
+# undef N_SYMS
}
int
-main()
+main(void)
{
- #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;
+ Symap* const map = symap_new();
+ const int st = symap_test(map);
+
+ symap_free(map);
+ return st;
}
-#endif /* STANDALONE */
+#endif // SYMAP_STANDALONE
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-11 15:50:18 +0000