From f350e37d8873c9c39285a319c95e7c856beaf142 Mon Sep 17 00:00:00 2001 From: Bert Wesarg Date: Fri, 8 Feb 2008 15:19:49 +0100 Subject: [PATCH] convert GlobalSymList to hash table B.W. Patch: +Symbol-embed-name.patch Patch: +GlobalSymTable.patch --- GlobalSymTable.patch | 323 ++++++++++++++++++++++++++++++++++++++++++++++++ Symbol-embed-name.patch | 115 +++++++++++++++++ series | 2 + 3 files changed, 440 insertions(+) create mode 100644 GlobalSymTable.patch create mode 100644 Symbol-embed-name.patch diff --git a/GlobalSymTable.patch b/GlobalSymTable.patch new file mode 100644 index 0000000..51b1451 --- /dev/null +++ b/GlobalSymTable.patch @@ -0,0 +1,323 @@ +--- + + source/interpret.c | 136 ++++++++++++++++++++++++++++++++++++++--------------- + source/interpret.h | 1 + 2 files changed, 100 insertions(+), 37 deletions(-) + +diff --quilt old/source/interpret.c new/source/interpret.c +--- old/source/interpret.c ++++ new/source/interpret.c +@@ -145,11 +145,17 @@ static int namedArg1(void); + static int namedArgN(void); + static int namedArg1orN(Boolean isFirst); + static int swapTop2(void); + static int arrayIndex(void); + static int makeArrayKeyFromArgs(int nArgs, char **keyString, int leaveParams); +-static void freeSymbolTable(Symbol *symTab); ++static void freeSymbolList(Symbol *symList); ++static void addToSymTab(Symbol **symTab, unsigned int symTabSize, ++ Symbol *sym); ++static Symbol *lookUpInSymTab(Symbol **symTab, unsigned int symTabSize, ++ const char *name); ++static unsigned int hashNameWith(unsigned int hash, const char *name); ++static unsigned int hashName(const char *name); + static int errCheck(const char *s); + static int execError(const char *s1, const char *s2); + static rbTreeNode *arrayEmptyAllocator(void); + static rbTreeNode *arrayAllocateNode(rbTreeNode *src); + static int arrayEntryCopyToNode(rbTreeNode *dst, rbTreeNode *src); +@@ -191,12 +197,13 @@ static void stackdumpInternal(int n, int + #else /* #ifndef DEBUG_STACK */ + #define STACKDUMP(n, x) + #define DISASM_RT(i, n) + #endif /* #ifndef DEBUG_STACK */ + +-/* Global symbols and function definitions */ +-static Symbol *GlobalSymList = NULL; ++/* Global symbols and function definitions, is null initialized */ ++#define GLOBAL_SYMTAB_SIZE 256u ++static Symbol *GlobalSymTab[GLOBAL_SYMTAB_SIZE]; + + /* List of all memory allocated for strings */ + static char *AllocatedStrings = NULL; + + typedef struct SparseArrayEntryWrapperTag { +@@ -395,11 +402,11 @@ Program *FinishCreatingProgram(const cha + return newProg; + } + + void FreeProgram(Program *prog) + { +- freeSymbolTable(prog->localSymList); ++ freeSymbolList(prog->localSymList); + XtFree((char *)prog->code); + if (prog->name) { + XtFree((char *)prog->name); + } + XtFree((char *)prog); +@@ -789,18 +796,18 @@ void SetMacroFocusWindow(WindowInfo *win + + /* + ** install an array iteration symbol + ** it is tagged as an integer but holds an array node pointer + */ +-#define ARRAY_ITER_SYM_PREFIX "aryiter " ++#define ARRAY_ITER_SYM_PREFIX "aryiter #" + Symbol *InstallIteratorSymbol(void) + { + char symbolName[sizeof(ARRAY_ITER_SYM_PREFIX) + TYPE_INT_STR_SIZE(int)]; + DataValue value; +- static int interatorNameIndex = 0; ++ static int interatorNameIndex; + +- sprintf(symbolName, ARRAY_ITER_SYM_PREFIX "#%d", interatorNameIndex); ++ sprintf(symbolName, ARRAY_ITER_SYM_PREFIX "%d", interatorNameIndex); + ++interatorNameIndex; + value.tag = INT_TAG; + value.val.arrayPtr = NULL; + return(InstallSymbol(symbolName, LOCAL_SYM, value)); + } +@@ -809,36 +816,42 @@ Symbol *InstallIteratorSymbol(void) + ** Lookup a constant string by its value. This allows reuse of string + ** constants and fixing a leak in the interpreter. + */ + Symbol *LookupStringConstSymbol(const char *value) + { ++ unsigned int idx; + Symbol *s; + +- for (s = GlobalSymList; s != NULL; s = s->next) { +- if (s->type == CONST_SYM && +- s->value.tag == STRING_TAG && +- !strcmp(s->value.val.str.rep, value)) { +- return(s); ++ for (idx = 0; idx < GLOBAL_SYMTAB_SIZE; idx++) { ++ for (s = GlobalSymTab[idx]; s != NULL; s = s->next) { ++ if (s->type == CONST_SYM ++ && s->value.tag == STRING_TAG ++ && !strcmp(s->value.val.str.rep, value)) { ++ return(s); ++ } + } + } ++ + return(NULL); + } + + /* + ** install string str in the global symbol table with a string name + */ ++#define STRING_CONST_SYM_PREFIX "string #" + Symbol *InstallStringConstSymbol(const char *str) + { +- static int stringConstIndex = 0; +- char stringName[35]; ++ static int stringConstIndex; ++ char stringName[sizeof(STRING_CONST_SYM_PREFIX) + TYPE_INT_STR_SIZE(int)]; + DataValue value; ++ + Symbol *sym = LookupStringConstSymbol(str); + if (sym) { + return sym; + } + +- sprintf(stringName, "string #%d", stringConstIndex++); ++ sprintf(stringName, STRING_CONST_SYM_PREFIX "%d", stringConstIndex++); + value.tag = STRING_TAG; + AllocNStringCpy(&value.val.str, str); + return(InstallSymbol(stringName, CONST_SYM, value)); + } + +@@ -850,14 +863,12 @@ Symbol *LookupSymbol(const char *name) + Symbol *s; + + for (s = LocalSymList; s != NULL; s = s->next) + if (strcmp(s->name, name) == 0) + return s; +- for (s = GlobalSymList; s != NULL; s = s->next) +- if (strcmp(s->name, name) == 0) +- return s; +- return NULL; ++ ++ return lookUpInSymTab(GlobalSymTab, GLOBAL_SYMTAB_SIZE, name); + } + + /* + ** install symbol name in symbol table + */ +@@ -873,12 +884,11 @@ Symbol *InstallSymbol(const char *name, + s->added = 0; + if (type == LOCAL_SYM) { + s->next = LocalSymList; + LocalSymList = s; + } else { +- s->next = GlobalSymList; +- GlobalSymList = s; ++ addToSymTab(GlobalSymTab, GLOBAL_SYMTAB_SIZE, s); + } + return s; + } + + /* +@@ -907,12 +917,11 @@ Symbol *PromoteToGlobal(Symbol *sym) + s = LookupSymbol(sym->name); + if (s != NULL) + return s; + + sym->type = GLOBAL_SYM; +- sym->next = GlobalSymList; +- GlobalSymList = sym; ++ addToSymTab(GlobalSymTab, GLOBAL_SYMTAB_SIZE, sym); + + return sym; + } + + /* +@@ -1131,10 +1140,11 @@ static void MarkArrayContentsAsUsed(Spar + void GarbageCollectStrings(void) + { + SparseArrayEntryWrapper *nextAP, *thisAP; + char *p, *next; + Symbol *s; ++ unsigned int idx; + + /* mark all strings as unreferenced */ + for (p = AllocatedStrings; p != NULL; p = *((char **)p)) { + *(p + sizeof(char *)) = 0; + } +@@ -1144,19 +1154,21 @@ void GarbageCollectStrings(void) + thisAP->inUse = 0; + } + + /* Sweep the global symbol list, marking which strings are still + referenced */ +- for (s = GlobalSymList; s != NULL; s = s->next) { +- if (s->value.tag == STRING_TAG) { +- /* test first because it may be read-only static string */ +- if (!(*(s->value.val.str.rep - 1))) { +- *(s->value.val.str.rep - 1) = 1; ++ for (idx = 0; idx < GLOBAL_SYMTAB_SIZE; idx++) { ++ for (s = GlobalSymTab[idx]; s != NULL; s = s->next) { ++ if (s->value.tag == STRING_TAG) { ++ /* test first because it may be read-only static string */ ++ if (!(*(s->value.val.str.rep - 1))) { ++ *(s->value.val.str.rep - 1) = 1; ++ } ++ } ++ else if (s->value.tag == ARRAY_TAG) { ++ MarkArrayContentsAsUsed(s->value.val.arrayPtr); + } +- } +- else if (s->value.tag == ARRAY_TAG) { +- MarkArrayContentsAsUsed(s->value.val.arrayPtr); + } + } + + /* Collect all of the strings which remain unreferenced */ + next = AllocatedStrings; +@@ -1219,21 +1231,71 @@ static void restoreContext(RestartData * + PC = context->pc; + InitiatingWindow = context->runWindow; + FocusWindow = context->focusWindow; + } + +-static void freeSymbolTable(Symbol *symTab) ++static void freeSymbolList(Symbol *symList) + { + Symbol *s; + +- while(symTab != NULL) { +- s = symTab; +- symTab = s->next; ++ while (symList != NULL) { ++ s = symList; ++ symList = s->next; + free(s); + } + } + ++static unsigned int hashNameWith(unsigned int hash, const char *name) ++{ ++ while (*name) { ++ unsigned char c = *name++; ++ hash = (hash * 16777619u) + c; ++ } ++ ++ return hash; ++} ++ ++static unsigned int hashName(const char *name) ++{ ++ return hashNameWith(2166136261u, name); ++} ++ ++static void addToSymTab(Symbol **symTab, unsigned int symTabSize, ++ Symbol *sym) ++{ ++ unsigned int idx; ++ ++ sym->hash = hashName(sym->name); ++ ++ idx = sym->hash % symTabSize; ++ ++ sym->next = symTab[idx]; ++ symTab[idx] = sym; ++} ++ ++static Symbol *lookUpInSymTab(Symbol **symTab, unsigned int symTabSize, ++ const char *name) ++{ ++ unsigned int hash; ++ unsigned int idx; ++ Symbol *sym; ++ ++ hash = hashName(name); ++ ++ idx = hash % symTabSize; ++ ++ sym = symTab[idx]; ++ while (sym) { ++ if (sym->hash == hash && !strcmp(name, sym->name)) { ++ break; ++ } ++ sym = sym->next; ++ } ++ ++ return sym; ++} ++ + #define POP(dataVal) \ + do { \ + POP_CHECK(1); \ + dataVal = *--StackP; \ + } while (0) +@@ -4417,12 +4479,12 @@ static void disasmInternal(Inst *inst, i + if (inst[i].func == OpFns[j]) { + printd(" %*s", (int)opLen, opNames[j]); + if (j == OP_PUSH_SYM || j == OP_ASSIGN) { + Symbol *sym = inst[i+1].sym; + printd(" %s", sym->name); +- if (sym->value.tag == STRING_TAG && +- strncmp(sym->name, "string #", 8) == 0) { ++ if (sym->type == CONST_SYM ++ && sym->value.tag == STRING_TAG) { + printd(" "); + dumpVal(sym->value); + } + ++i; + } +diff --quilt old/source/interpret.h new/source/interpret.h +--- old/source/interpret.h ++++ new/source/interpret.h +@@ -109,10 +109,11 @@ typedef struct SparseArrayEntryTag { + /* symbol table entry */ + typedef struct SymbolRec { + enum symTypes type; + DataValue value; + int added; ++ unsigned int hash; + struct SymbolRec *next; /* to link to another */ + char name[1]; + } Symbol; + + typedef struct ProgramTag { diff --git a/Symbol-embed-name.patch b/Symbol-embed-name.patch new file mode 100644 index 0000000..de5620a --- /dev/null +++ b/Symbol-embed-name.patch @@ -0,0 +1,115 @@ +--- + + source/interpret.c | 39 +++++++++++++++++++++++++-------------- + source/interpret.h | 4 ++-- + 2 files changed, 27 insertions(+), 16 deletions(-) + +diff --quilt old/source/interpret.c new/source/interpret.c +--- old/source/interpret.c ++++ new/source/interpret.c +@@ -863,12 +863,12 @@ Symbol *LookupSymbol(const char *name) + */ + Symbol *InstallSymbol(const char *name, enum symTypes type, DataValue value) + { + Symbol *s; + +- s = (Symbol *)malloc(sizeof(Symbol)); +- s->name = (char *)malloc(strlen(name)+1); /* +1 for '\0' */ ++ /* no +1, because of .name[1] */ ++ s = malloc(sizeof(Symbol) + strlen(name)); + strcpy(s->name, name); + s->type = type; + s->value = value; + s->added = 0; + if (type == LOCAL_SYM) { +@@ -1224,15 +1224,14 @@ static void restoreContext(RestartData * + static void freeSymbolTable(Symbol *symTab) + { + Symbol *s; + + while(symTab != NULL) { +- s = symTab; +- free(s->name); +- symTab = s->next; +- free((char *)s); +- } ++ s = symTab; ++ symTab = s->next; ++ free(s); ++ } + } + + #define POP(dataVal) \ + do { \ + POP_CHECK(1); \ +@@ -2529,11 +2528,11 @@ static int callSubroutineFromSymbol(Symb + ** values which are already there. + */ + if (sym->type == MACRO_FUNCTION_SYM) { + PUSH_CHECK(3 + !haveNamedArgs); + +- prog = (Program *)sym->value.val.str.rep; ++ prog = sym->value.val.prog; + + if (!haveNamedArgs) + *(StackP++) = noValue; /* push dummy named arg array */ + + StackP->tag = NO_TAG; /* return PC */ +@@ -2719,18 +2718,30 @@ int OverlayRoutineFromSymbol(Symbol *sym + ** executed in the caller's context from a function in macro.c. + */ + + int OverlayRoutineFromProg(Program *prog, int nArgs, int removeArgs) + { +- Symbol sym; ++ Symbol *sym; ++ int ret; ++ ++ /* no +1, because of .name[1] */ ++ sym = malloc(sizeof(Symbol) + strlen(prog->name)); ++ if (NULL == sym) { ++ return False; ++ } ++ ++ sym->type = MACRO_FUNCTION_SYM; ++ strcpy(sym->name, prog->name); ++ sym->value.val.prog = prog; ++ sym->next = NULL; ++ sym->added = 0; ++ ++ ret = OverlayRoutineFromSymbol(sym, nArgs, removeArgs); + +- sym.type = MACRO_FUNCTION_SYM; +- sym.name = prog->name; +- sym.value.val.str.rep = (char *)prog; +- sym.next = NULL; ++ free(sym); + +- return OverlayRoutineFromSymbol(&sym, nArgs, removeArgs); ++ return ret; + } + + /* + ** For special call style where the $args array in the called function is + ** assigned from an array in the caller (as "calledFunc(=argsArray)"), +diff --quilt old/source/interpret.h new/source/interpret.h +--- old/source/interpret.h ++++ new/source/interpret.h +@@ -106,15 +106,15 @@ typedef struct SparseArrayEntryTag { + DataValue value; + } SparseArrayEntry; + + /* symbol table entry */ + typedef struct SymbolRec { +- char *name; + enum symTypes type; + DataValue value; +- struct SymbolRec *next; /* to link to another */ + int added; ++ struct SymbolRec *next; /* to link to another */ ++ char name[1]; + } Symbol; + + typedef struct ProgramTag { + Symbol *localSymList; + Inst *code; diff --git a/series b/series index 9d21da1..3aaf2d4 100644 --- a/series +++ b/series @@ -97,3 +97,5 @@ sh-bg-newline.diff language_mode_hook.patch sanitize-_TAG.patch SUBR_TAG.patch +Symbol-embed-name.patch +GlobalSymTable.patch -- 2.11.4.GIT