ref: 29629245a4f764aae6f6f7559c72f943d688e4f5
parent: 666b9f8f7b0c17696139b3a42c51ad39f1bfa5d8
author: ISSOtm <[email protected]>
date: Tue Mar 24 08:50:14 EDT 2020
Use new hashmap implementation for symbols
--- a/include/asm/asm.h
+++ b/include/asm/asm.h
@@ -34,7 +34,6 @@
extern uint32_t unionSize[MAXUNIONS];
extern char tzCurrentFileName[_MAX_PATH + 1];
extern struct Section *pCurrentSection;
-extern struct sSymbol *tHashedSymbols[HASHSIZE];
extern struct sSymbol *pPCSymbol;
extern bool oDontExpandStrings;
--- a/include/asm/symbol.h
+++ b/include/asm/symbol.h
@@ -34,9 +34,7 @@
enum SymbolType type;
bool isExported; /* Whether the symbol is to be exported */
bool isBuiltin; /* Whether the symbol is a built-in */
- bool isReferenced; /* Whether the symbol is referenced in a RPN expr */
struct sSymbol *pScope;
- struct sSymbol *pNext;
struct Section *pSection;
int32_t nValue;
uint32_t ulMacroSize;
@@ -44,6 +42,9 @@
int32_t (*Callback)(struct sSymbol const *self);
char tzFileName[_MAX_PATH + 1]; /* File where the symbol was defined. */
uint32_t nFileLine; /* Line where the symbol was defined. */
+
+ uint32_t ID; /* ID of the symbol in the object file (-1 if none) */
+ struct sSymbol *next; /* Next object to output in the object file */
};
static inline bool sym_IsDefined(struct sSymbol const *sym)
@@ -87,8 +88,9 @@
return sym->pMacro;
}
+void sym_ForEach(void (*func)(struct sSymbol *, void *), void *arg);
+
int32_t sym_GetValue(struct sSymbol const *sym);
-uint32_t sym_CalcHash(const char *s);
void sym_SetExportAll(bool set);
struct sSymbol *sym_AddLocalReloc(char const *tzSym);
struct sSymbol *sym_AddReloc(char const *tzSym);
--- a/src/asm/output.c
+++ b/src/asm/output.c
@@ -40,13 +40,6 @@
struct Patch *pNext;
};
-struct PatchSymbol {- uint32_t ID;
- struct sSymbol const *pSymbol;
- struct PatchSymbol *pNext;
- struct PatchSymbol *pBucketNext; /* next symbol in hash table bucket */
-};
-
struct Assertion {struct Patch *patch;
struct Section *section;
@@ -54,29 +47,17 @@
struct Assertion *next;
};
-struct PatchSymbol *tHashedPatchSymbols[HASHSIZE];
-struct Section *pSectionList, *pCurrentSection;
-struct PatchSymbol *pPatchSymbols;
-struct PatchSymbol **ppPatchSymbolsTail = &pPatchSymbols;
-struct Assertion *assertions = NULL;
char *tzObjectname;
-/*
- * Count the number of symbols used in this object
- */
-static uint32_t countsymbols(void)
-{- struct PatchSymbol *pSym;
- uint32_t count = 0;
+/* TODO: shouldn't `pCurrentSection` be somewhere else? */
+struct Section *pSectionList, *pCurrentSection;
- pSym = pPatchSymbols;
- while (pSym) {- count++;
- pSym = pSym->pNext;
- }
+/* Linked list of symbols to put in the object file */
+static struct sSymbol *objectSymbols = NULL;
+static struct sSymbol **objectSymbolsTail = &objectSymbols;
+static uint32_t nbSymbols = 0; /* Length of the above list */
- return count;
-}
+static struct Assertion *assertions = NULL;
/*
* Count the number of sections used in this object
@@ -236,10 +217,8 @@
break;
case SYMTYPE_EXPORT:
offset = pSym->nValue;
- if (pSym->type != SYM_LABEL)
- sectid = -1;
- else
- sectid = getsectid(pSym->pSection);
+ sectid = pSym->type == SYM_LABEL ? getsectid(pSym->pSection)
+ : -1;
break;
}
@@ -256,60 +235,20 @@
}
/*
- * Add a symbol to the object
+ * Returns a symbol's ID within the object file
+ * If the symbol does not have one, one is assigned by registering the symbol
*/
-static uint32_t nextID;
-
-static uint32_t addsymbol(struct sSymbol const *pSym)
+static uint32_t getSymbolID(struct sSymbol *sym)
{- struct PatchSymbol *pPSym, **ppPSym;
- uint32_t hash;
+ if (sym->ID == -1) {+ sym->ID = nbSymbols++;
- hash = sym_CalcHash(pSym->tzName);
- ppPSym = &(tHashedPatchSymbols[hash]);
-
- while ((*ppPSym) != NULL) {- if (pSym == (*ppPSym)->pSymbol)
- return (*ppPSym)->ID;
- ppPSym = &((*ppPSym)->pBucketNext);
+ *objectSymbolsTail = sym;
+ objectSymbolsTail = &sym->next;
}
-
- pPSym = malloc(sizeof(struct PatchSymbol));
- *ppPSym = pPSym;
-
- if (pPSym == NULL)
- fatalerror("No memory for patchsymbol");-
- pPSym->pNext = NULL;
- pPSym->pBucketNext = NULL;
- pPSym->pSymbol = pSym;
- pPSym->ID = nextID++;
-
- *ppPatchSymbolsTail = pPSym;
- ppPatchSymbolsTail = &(pPSym->pNext);
-
- return pPSym->ID;
+ return sym->ID;
}
-/*
- * Add all exported symbols to the object
- */
-static void addexports(void)
-{- int32_t i;
-
- for (i = 0; i < HASHSIZE; i++) {- struct sSymbol *pSym;
-
- pSym = tHashedSymbols[i];
- while (pSym) {- if (pSym->isExported)
- addsymbol(pSym);
- pSym = pSym->pNext;
- }
- }
-}
-
static void writerpn(uint8_t *rpnexpr, uint32_t *rpnptr, uint8_t *rpn,
uint32_t rpnlen)
{@@ -330,63 +269,46 @@
break;
case RPN_SYM:
{- uint32_t symptr = 0;
-
- while ((tzSym[symptr++] = popbyte()) != 0)
+ for (unsigned int i = -1; (tzSym[++i] = popbyte()); )
;
+ struct sSymbol *sym = sym_FindSymbol(tzSym);
+ uint32_t value;
- struct sSymbol const *sym = sym_FindSymbol(tzSym);
-
- if (!sym) {- break; // TODO: wtf?
- } else if (sym_IsConstant(sym)) {- uint32_t value;
-
- value = sym_GetConstantValue(tzSym);
+ if (sym_IsConstant(sym)) {writebyte(RPN_CONST);
- writebyte(value & 0xFF);
- writebyte(value >> 8);
- writebyte(value >> 16);
- writebyte(value >> 24);
+ value = sym_GetConstantValue(tzSym);
} else {- symptr = addsymbol(sym);
writebyte(RPN_SYM);
- writebyte(symptr & 0xFF);
- writebyte(symptr >> 8);
- writebyte(symptr >> 16);
- writebyte(symptr >> 24);
+ value = getSymbolID(sym);
}
+ writebyte(value & 0xFF);
+ writebyte(value >> 8);
+ writebyte(value >> 16);
+ writebyte(value >> 24);
break;
}
case RPN_BANK_SYM:
{- struct sSymbol *sym;
- uint32_t symptr = 0;
-
- while ((tzSym[symptr++] = popbyte()) != 0)
+ for (unsigned int i = -1; (tzSym[++i] = popbyte()); )
;
+ struct sSymbol *sym = sym_FindSymbol(tzSym);
+ uint32_t value = getSymbolID(sym);
- sym = sym_FindSymbol(tzSym);
- if (sym == NULL)
- break;
-
- symptr = addsymbol(sym);
writebyte(RPN_BANK_SYM);
- writebyte(symptr & 0xFF);
- writebyte(symptr >> 8);
- writebyte(symptr >> 16);
- writebyte(symptr >> 24);
+ writebyte(value & 0xFF);
+ writebyte(value >> 8);
+ writebyte(value >> 16);
+ writebyte(value >> 24);
break;
}
case RPN_BANK_SECT:
{- uint16_t b;
+ uint8_t b;
writebyte(RPN_BANK_SECT);
-
do {b = popbyte();
- writebyte(b & 0xFF);
+ writebyte(b);
} while (b != 0);
break;
}
@@ -471,6 +393,16 @@
fputstring(assert->message, f);
}
+static void registerExportedSymbol(struct sSymbol *symbol, void *arg)
+{+ (void)arg;
+ if (symbol->isExported && symbol->ID == -1) {+ *objectSymbolsTail = symbol;
+ objectSymbolsTail = &symbol->next;
+ nbSymbols++;
+ }
+}
+
/*
* Write an objectfile
*/
@@ -477,26 +409,24 @@
void out_WriteObject(void)
{FILE *f;
- struct PatchSymbol *pSym;
struct Section *pSect;
struct Assertion *assert = assertions;
- addexports();
-
f = fopen(tzObjectname, "wb");
if (!f)
err(1, "Couldn't write file '%s'", tzObjectname);
+ /* Also write exported symbols that weren't written above */
+ sym_ForEach(registerExportedSymbol, NULL);
+
fprintf(f, RGBDS_OBJECT_VERSION_STRING, RGBDS_OBJECT_VERSION_NUMBER);
fputlong(RGBDS_OBJECT_REV, f);
- fputlong(countsymbols(), f);
+ fputlong(nbSymbols, f);
fputlong(countsections(), f);
- pSym = pPatchSymbols;
- while (pSym) {- writesymbol(pSym->pSymbol, f);
- pSym = pSym->pNext;
+ for (struct sSymbol const *sym = objectSymbols; sym; sym = sym->next) {+ writesymbol(sym, f);
}
pSect = pSectionList;
--- a/src/asm/symbol.c
+++ b/src/asm/symbol.c
@@ -11,6 +11,7 @@
*/
#include <assert.h>
+#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
@@ -28,10 +29,12 @@
#include "extern/err.h"
+#include "hashmap.h"
#include "helpers.h"
#include "version.h"
-struct sSymbol *tHashedSymbols[HASHSIZE];
+HashMap symbols;
+
static struct sSymbol *pScope; /* Current section symbol scope */
struct sSymbol *pPCSymbol;
static struct sSymbol *p_NARGSymbol;
@@ -48,6 +51,26 @@
static char SavedSECOND[3];
static bool exportall;
+struct ForEachArgs {+ void (*func)(struct sSymbol *, void *);
+ void *arg;
+};
+
+static void forEachWrapper(void *_symbol, void *_argWrapper)
+{+ struct ForEachArgs *argWrapper = _argWrapper;
+ struct sSymbol *symbol = _symbol;
+
+ argWrapper->func(symbol, argWrapper->arg);
+}
+
+void sym_ForEach(void (*func)(struct sSymbol *, void *), void *arg)
+{+ struct ForEachArgs argWrapper = { .func = func, .arg = arg };+
+ hash_ForEach(symbols, forEachWrapper, &argWrapper);
+}
+
static int32_t Callback_NARG(struct sSymbol const *self)
{(void)self;
@@ -80,14 +103,6 @@
}
/*
- * Calculate the hash value for a symbol name
- */
-uint32_t sym_CalcHash(const char *s)
-{- return calchash(s) % HASHSIZE;
-}
-
-/*
* Update a symbol's definition filename and line
*/
static void updateSymbolFilename(struct sSymbol *nsym)
@@ -105,36 +120,28 @@
*/
static struct sSymbol *createsymbol(char const *s)
{- struct sSymbol **ppsym;
- uint32_t hash;
+ struct sSymbol *symbol = malloc(sizeof(*symbol));
- hash = sym_CalcHash(s);
- ppsym = &(tHashedSymbols[hash]);
+ if (!symbol)
+ fatalerror("Failed to create symbol: %s", strerror(errno));- while ((*ppsym) != NULL)
- ppsym = &((*ppsym)->pNext);
+ if (snprintf(symbol->tzName, MAXSYMLEN + 1, "%s", s) > MAXSYMLEN)
+ warning(WARNING_LONG_STR, "Symbol name is too long: '%s'", s);
- (*ppsym) = malloc(sizeof(struct sSymbol));
+ hash_AddElement(symbols, symbol->tzName, symbol);
- if ((*ppsym) == NULL) {- fatalerror("No memory for symbol");- return NULL;
- }
+ symbol->isExported = false;
+ symbol->isBuiltin = false;
+ symbol->pScope = NULL;
+ symbol->pSection = NULL;
+ symbol->nValue = 0; /* TODO: is this necessary? */
+ symbol->pMacro = NULL;
+ symbol->Callback = NULL;
- if (snprintf((*ppsym)->tzName, MAXSYMLEN + 1, "%s", s) > MAXSYMLEN)
- warning(WARNING_LONG_STR, "Symbol name is too long: '%s'", s);
-
- (*ppsym)->isExported = false;
- (*ppsym)->isBuiltin = false;
- (*ppsym)->isReferenced = false;
- (*ppsym)->pScope = NULL;
- (*ppsym)->pNext = NULL;
- (*ppsym)->pSection = NULL;
- (*ppsym)->nValue = 0;
- (*ppsym)->pMacro = NULL;
- (*ppsym)->Callback = NULL;
- updateSymbolFilename(*ppsym);
- return *ppsym;
+ symbol->ID = -1;
+ symbol->next = NULL;
+ updateSymbolFilename(symbol);
+ return symbol;
}
/*
@@ -153,12 +160,10 @@
}
/*
- * Find the pointer to a symbol by name and scope
+ * Find a symbol by name and scope
*/
-static struct sSymbol **findpsymbol(char const *s, struct sSymbol const *scope)
+static struct sSymbol *findsymbol(char const *s, struct sSymbol const *scope)
{- struct sSymbol **ppsym;
- int32_t hash;
char fullname[MAXSYMLEN + 1];
if (s[0] == '.' && scope) {@@ -168,35 +173,14 @@
char const *separator = strchr(s, '.');
- if (separator) {- if (strchr(separator + 1, '.'))
- fatalerror("'%s' is a nonsensical reference to a nested local symbol",- s);
- }
+ if (separator && strchr(separator + 1, '.'))
+ fatalerror("'%s' is a nonsensical reference to a nested local symbol",+ s);
- hash = sym_CalcHash(s);
- ppsym = &(tHashedSymbols[hash]);
-
- while ((*ppsym) != NULL) {- if ((strcmp(s, (*ppsym)->tzName) == 0))
- return ppsym;
-
- ppsym = &((*ppsym)->pNext);
- }
- return NULL;
+ return hash_GetElement(symbols, s);
}
/*
- * Find a symbol by name and scope
- */
-static struct sSymbol *findsymbol(char const *s, struct sSymbol const *scope)
-{- struct sSymbol **ppsym = findpsymbol(s, scope);
-
- return ppsym ? *ppsym : NULL;
-}
-
-/*
* Find a symbol by name, with automatically determined scope
*/
struct sSymbol *sym_FindSymbol(char const *tzName)
@@ -213,7 +197,7 @@
static inline bool isReferenced(struct sSymbol const *sym)
{- return sym->isReferenced;
+ return sym->ID != -1;
}
/*
@@ -221,33 +205,20 @@
*/
void sym_Purge(char const *tzName)
{- struct sSymbol **ppSym;
- struct sSymbol *pscope;
+ struct sSymbol *scope = tzName[0] == '.' ? pScope : NULL;
+ struct sSymbol *symbol = findsymbol(tzName, scope);
- if (*tzName == '.')
- pscope = pScope;
- else
- pscope = NULL;
-
- ppSym = findpsymbol(tzName, pscope);
-
- if (!ppSym) {+ if (!symbol) { yyerror("'%s' not defined", tzName);- } else if ((*ppSym)->isBuiltin) {+ } else if (symbol->isBuiltin) { yyerror("Built-in symbol '%s' cannot be purged", tzName);- } else if (isReferenced(*ppSym)) {+ } else if (isReferenced(symbol)) { yyerror("Symbol \"%s\" is referenced and thus cannot be purged",tzName);
} else {- struct sSymbol *pSym;
-
- pSym = *ppSym;
- *ppSym = pSym->pNext;
-
- if (pSym->pMacro)
- free(pSym->pMacro);
-
- free(pSym);
+ hash_RemoveElement(symbols, tzName);
+ free(symbol->pMacro);
+ free(symbol);
}
}
@@ -503,10 +474,8 @@
struct sSymbol *nsym = sym_FindSymbol(tzSym);
/* If the symbol doesn't exist, create a ref that can be purged */
- if (!nsym) {+ if (!nsym)
nsym = sym_Ref(tzSym);
- nsym->isReferenced = false;
- }
nsym->isExported = true;
}
@@ -554,7 +523,6 @@
nsym = createsymbol(tzSym);
nsym->type = SYM_REF;
}
- nsym->isReferenced = true;
return nsym;
}
@@ -583,9 +551,6 @@
*/
void sym_Init(void)
{- for (int32_t i = 0; i < HASHSIZE; i++)
- tHashedSymbols[i] = NULL;
-
pPCSymbol = sym_AddReloc("@");pPCSymbol->Callback = CallbackPC;
pPCSymbol->isBuiltin = true;