Use multiple small hash tables to implement symbol tables

The scanner no longer modifies the symbol table when finding identifiers.

3 files changed, 116 insertions, 80 deletions

diff --git a/src/lexer.l b/src/lexer.l
index 168412b..a947fc1 100644
--- a/src/lexer.l
+++ b/src/lexer.l
@@ -6,10 +6,8 @@
 # include "config.h"
 #endif
 
-#include "ast.h"
 #include "common.h"
 #include "state.h"
-#include "symbol-table.h"
 
 #include "libparser_a-parser.h"
 
@@ -79,15 +77,6 @@ ERROR           .
                     for (i = 0; i < SIZEOF_ARRAY(reserved); i++)
                         if (strcmp(yytext, reserved[i]) == 0)
                             return reserved_token[i];
-                    if (i == SIZEOF_ARRAY(reserved)) {
-                        CcmmcSymbol *ptr = ccmmc_symbol_table_lookup(yytext);
-                        CcmmcState *state = yyextra;
-                        if (ptr == NULL)
-                            ccmmc_symbol_table_insert_id(
-                                yytext, state->line_number);
-                        else
-                            ptr->counter++;
-                    }
                     yylval->lexeme = strdup(yytext);
                     ERR_FATAL_CHECK(yylval->lexeme, strdup);
                     return ID;
diff --git a/src/symbol-table.c b/src/symbol-table.c
index 008172f..bd00d23 100644
--- a/src/symbol-table.c
+++ b/src/symbol-table.c
@@ -2,89 +2,84 @@
 # include "config.h"
 #endif
 
+#include "common.h"
 #include "symbol-table.h"
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <ctype.h>
-#include <math.h>
 
-#define TABLE_SIZE    256
-
-static CcmmcSymbol *hash_table[TABLE_SIZE];
-
-static int hash(char *str) {
+static int hash(const char *str)
+{
     int idx = 0;
-    while (*str) {
+    for (; *str; str++) {
         idx = idx << 1;
         idx += *str;
-        str++;
     }
-    return (idx & (TABLE_SIZE-1));
+    return (idx & (CCMMC_SYMBOL_SCOPE_HASH_TABLE_SIZE - 1));
 }
 
-/* returns the symbol table entry if found else NULL */
-CcmmcSymbol *ccmmc_symbol_table_lookup(char *name) {
-    int hash_key;
-    CcmmcSymbol *symptr;
-    if (!name)
-        return NULL;
-    hash_key = hash(name);
-    symptr = hash_table[hash_key];
-
-    while (symptr) {
-        if (!(strcmp(name, symptr->lexeme)))
-            return symptr;
-        symptr = symptr->front;
-    }
-    return NULL;
+void ccmmc_symbol_table_init(CcmmcSymbolTable *table)
+{
+    table->all = NULL;
+    table->all_last = NULL;
+    table->current = NULL;
 }
 
-
-void ccmmc_symbol_table_insert_id(char *name, int line_number) {
-    int hash_key;
-    CcmmcSymbol *ptr;
-    CcmmcSymbol *symptr = malloc(sizeof(CcmmcSymbol));
-
-    hash_key = hash(name);
-    ptr = hash_table[hash_key];
-
-    if (ptr == NULL) {
-        /* first entry for this hash_key */
-        hash_table[hash_key] = symptr;
-        symptr->front = NULL;
-        symptr->back = symptr;
+// push a scope on the stack
+void ccmmc_symbol_table_open_scope(CcmmcSymbolTable *table)
+{
+    CcmmcSymbolScope *scope = malloc(sizeof(CcmmcSymbolScope));
+    ERR_FATAL_CHECK(scope, malloc);
+    for (int i = 0; i < CCMMC_SYMBOL_SCOPE_HASH_TABLE_SIZE; i++)
+        scope->hash_table[i] = NULL;
+    if (table->all == NULL) {
+        table->all = scope;
+        table->all_last = scope;
     } else {
-        symptr->front = ptr;
-        ptr->back = symptr;
-        symptr->back = symptr;
-        hash_table[hash_key] = symptr;
+        table->all_last->all_next = scope;
+        table->all_last = scope;
     }
+    scope->all_next = NULL;
+    scope->current_next = table->current;
+    table->current = scope;
+}
 
-    strcpy(symptr->lexeme, name);
-    symptr->line = line_number;
-    symptr->counter = 1;
+// pop a scope from the stack
+void ccmmc_symbol_table_close_scope(CcmmcSymbolTable *table)
+{
+    CcmmcSymbolScope *closing = table->current;
+    table->current = closing->current_next;
 }
 
-static void print_symbol(CcmmcSymbol *ptr) {
-    printf(" Name = %s \n", ptr->lexeme);
-    printf(" References = %d \n", ptr->counter);
+void ccmmc_symbol_table_insert(CcmmcSymbolTable *table,
+    const char *name, CcmmcSymbolKind kind, CcmmcSymbolType type)
+{
+    int key = hash(name);
+    CcmmcSymbol *symbol = malloc(sizeof(CcmmcSymbol));
+    ERR_FATAL_CHECK(symbol, malloc);
+    symbol->kind = kind;
+    symbol->type = type;
+    symbol->attr.addr = 0;
+    symbol->name = name;
+    symbol->next = table->current->hash_table[key];
+    table->current->hash_table[key] = symbol;
 }
 
-void ccmmc_symbol_table_print(void) {
-    puts("----- Symbol Table ---------");
-    for (int i = 0; i < TABLE_SIZE; i++)
-    {
-        CcmmcSymbol *symptr;
-        symptr = hash_table[i];
-        while (symptr != NULL)
-        {
-             printf("====>  index = %d\n", i);
-             print_symbol(symptr);
-             symptr = symptr->front;
+CcmmcSymbol *ccmmc_symbol_table_retrive (
+    CcmmcSymbolTable *table, const char *name)
+{
+    if (name == NULL)
+        return NULL;
+
+    int key = hash(name);
+    for (CcmmcSymbolScope *scope = table->current; scope; scope = scope->current_next) {
+        for (CcmmcSymbol *symbol = scope->hash_table[key]; symbol; symbol = symbol->next) {
+            if (strcmp(name, symbol->name) == 0)
+                return symbol;
         }
     }
+    return NULL;
 }
 
 // vim: set sw=4 ts=4 sts=4 et:
diff --git a/src/symbol-table.h b/src/symbol-table.h
index 2afd1b0..1d71e09 100644
--- a/src/symbol-table.h
+++ b/src/symbol-table.h
@@ -1,18 +1,70 @@
 #ifndef CCMMC_HEADER_SYMBOL_TABLE_H
 #define CCMMC_HEADER_SYMBOL_TABLE_H
 
+#include "ast.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#define CCMMC_SYMBOL_SCOPE_HASH_TABLE_SIZE 256
+
+typedef enum CcmmcSymbolKind_enum {
+    CCMMC_SYMBOL_KIND_VARIABLE,
+    CCMMC_SYMBOL_KIND_TYPE,
+    CCMMC_SYMBOL_KIND_FUNCTION
+} CcmmcSymbolKind;
+
+typedef struct CcmmcSymbolType_struct CcmmcSymbolType;
+typedef struct CcmmcSymbolType_struct {
+    CcmmcAstValueType type_base;
+    size_t array_dimension;
+    size_t *array_size;
+    size_t param_count;
+    CcmmcSymbolType *param_list;
+} CcmmcSymbolType;
+
+typedef struct CcmmcSymbolAttr_struct {
+    uint64_t addr;
+} CcmmcSymbolAttr;
+
+typedef struct CcmmcSymbol_struct CcmmcSymbol;
 typedef struct CcmmcSymbol_struct {
-    char lexeme[256];
-    struct CcmmcSymbol_struct *front;
-    struct CcmmcSymbol_struct *back;
-    int line;
-    int counter;
+    CcmmcSymbolKind kind;
+    CcmmcSymbolType type;
+    CcmmcSymbolAttr attr;
+    const char *name;
+    CcmmcSymbol *next;
 } CcmmcSymbol;
 
-CcmmcSymbol     *ccmmc_symbol_table_lookup          (char *name);
-void             ccmmc_symbol_table_insert_id       (char *name,
-                                                     int line_number);
-void             ccmmc_symbol_table_print           (void);
+typedef struct CcmmcSymbolScope_struct CcmmcSymbolScope;
+typedef struct CcmmcSymbolScope_struct {
+    CcmmcSymbol *hash_table[CCMMC_SYMBOL_SCOPE_HASH_TABLE_SIZE];
+    CcmmcSymbolScope *all_next;
+    CcmmcSymbolScope *current_next;
+} CcmmcSymbolScope;
+
+typedef struct CcmmcSymbolTable_struct {
+    CcmmcSymbolScope *all;
+    CcmmcSymbolScope *all_last;
+    CcmmcSymbolScope *current;
+} CcmmcSymbolTable;
+
+static inline bool ccmmc_symbol_is_scalar(CcmmcSymbol *symbol) {
+    return symbol->type.array_dimension == 0;
+}
+static inline bool ccmmc_symbol_is_array(CcmmcSymbol *symbol) {
+    return symbol->type.array_dimension != 0;
+}
+
+void             ccmmc_symbol_table_open_scope      (CcmmcSymbolTable *table);
+void             ccmmc_symbol_table_close_scope     (CcmmcSymbolTable *table);
+void             ccmmc_symbol_table_init            (CcmmcSymbolTable *table);
+void             ccmmc_symbol_table_insert          (CcmmcSymbolTable *table,
+                                                     const char *name,
+                                                     CcmmcSymbolKind kind,
+                                                     CcmmcSymbolType type);
+CcmmcSymbol     *ccmmc_symbol_table_retrive         (CcmmcSymbolTable *table,
+                                                     const char *name);
 
 #endif
 // vim: set sw=4 ts=4 sts=4 et: