From 99f3260a98a6b727bfa64ff66c19ca051acef450 Mon Sep 17 00:00:00 2001
From: Mistivia <i@mistivia.com>
Date: Thu, 26 Jun 2025 02:32:34 +0800
Subject: use hash table in top level symbol lookup

---
 src/interp.c | 62 +++++++++++++++++++++++++++++++++++++-----------------------
 src/interp.h |  9 ++-------
 src/sexp.h   |  2 +-
 3 files changed, 41 insertions(+), 32 deletions(-)

diff --git a/src/interp.c b/src/interp.c
index 116636e..9749b6d 100644
--- a/src/interp.c
+++ b/src/interp.c
@@ -14,8 +14,30 @@
 
 #define BUFSIZE 1024
 
-void TopBinding_show(TopBinding self, FILE *fp) { }
-VECTOR_IMPL(TopBinding);
+bool SExpRef_eq(SExpRef a, SExpRef b) {
+    return a.idx == b.idx;
+}
+
+uint64_t SExpRef_hash(SExpRef s) {
+    // FNV-1a 64-bit hash
+    uint32_t idx = s.idx;
+    uint8_t byte0 = idx & 0xff;
+    uint8_t byte1 = (idx >> 8) & 0xff;
+    uint8_t byte2 = (idx >> 16) & 0xff;
+    uint8_t byte3 = (idx >> 24) & 0xff;
+    uint64_t hash = 14695981039346656037ULL;    
+    hash = hash ^ byte0;
+    hash = hash * 1099511628211ULL;
+    hash = hash ^ byte1;
+    hash = hash * 1099511628211ULL;
+    hash = hash ^ byte2;
+    hash = hash * 1099511628211ULL;
+    hash = hash ^ byte3;
+    hash = hash * 1099511628211ULL;
+    return hash;
+}
+
+HASH_TABLE_IMPL(SExpRef, SExpRef);
 
 #define UNBOUND ((SExpRef){-1})
 
@@ -28,7 +50,7 @@ void Interp_init(Interp *self) {
     self->errmsg_buf = malloc(BUFSIZE);
     SExpVector_init(&self->objs);
     IntVector_init(&self->empty_space);
-    TopBindingVector_init(&self->topbindings);
+    SExpRef2SExpRefHashTable_init(&self->topbindings);
     String2IntHashTable_init(&self->symbols);
     int i = 0;
     SExp sexp;
@@ -271,7 +293,7 @@ void Interp_free(Interp *self) {
     String2IntHashTable_free(&self->symbols);
     SExpVector_free(&self->objs);
     IntVector_free(&self->empty_space);
-    TopBindingVector_free(&self->topbindings);
+    SExpRef2SExpRefHashTable_free(&self->topbindings);
     free(self->errmsg_buf);
     Parser_free(self->parser);
     free(self->parser);
@@ -526,7 +548,7 @@ void lisp_defun(Interp *interp, SExpRef name, SExpRef val) {
     REF(newbinding)->binding.value = UNBOUND;
     REF(newbinding)->binding.next = binding;
     REF(interp->top_level)->env.bindings = newbinding;
-    TopBindingVector_push_back(&interp->topbindings, (TopBinding){name, newbinding});
+    SExpRef2SExpRefHashTable_insert(&interp->topbindings, name, newbinding);
 }
 
 void lisp_defvar(Interp *interp, SExpRef name, SExpRef val) {
@@ -544,7 +566,7 @@ void lisp_defvar(Interp *interp, SExpRef name, SExpRef val) {
     REF(newbinding)->binding.value = val;
     REF(newbinding)->binding.next = binding;
     REF(interp->top_level)->env.bindings = newbinding;
-    TopBindingVector_push_back(&interp->topbindings, (TopBinding){name, newbinding});
+    SExpRef2SExpRefHashTable_insert(&interp->topbindings, name, newbinding);
 }
 
 SExpRef lisp_setq(Interp *interp, SExpRef name, SExpRef val) {
@@ -593,29 +615,21 @@ void lisp_print(Interp *interp, SExpRef obj, FILE *fp) {
 }
 
 SExpRef lisp_lookup_topvar(Interp *interp, SExpRef name) {
-    int topbindings_len = TopBindingVector_len(&interp->topbindings);
-    for (int i = 0; i < topbindings_len; i++) {
-        TopBinding topbinding = interp->topbindings.buffer[i];
-        if (topbinding.name.idx == name.idx) {
-            SExpRef ret = REF(topbinding.binding)->binding.value;
-            if (ret.idx < 0) goto notfound;
-            return ret;
-        }
-    }
+    SExpRef *pbinding = SExpRef2SExpRefHashTable_get(&interp->topbindings, name);
+    if (pbinding == NULL) goto notfound;
+    SExpRef ret = REF(*pbinding)->binding.value;
+    if (ret.idx < 0) goto notfound;
+    return ret;
 notfound:
     return new_error(interp, "Unbound variable: %s.\n", REF(name)->str);
 }
 
 SExpRef lisp_lookup_func(Interp *interp, SExpRef name) {
-    int topbindings_len = TopBindingVector_len(&interp->topbindings);
-    for (int i = 0; i < topbindings_len; i++) {
-        TopBinding topbinding = interp->topbindings.buffer[i];
-        if (topbinding.name.idx == name.idx) {
-            SExpRef ret = REF(topbinding.binding)->binding.func;
-            if (ret.idx < 0) goto notfound;
-            return ret;
-        }
-    }
+    SExpRef *pbinding = SExpRef2SExpRefHashTable_get(&interp->topbindings, name);
+    if (pbinding == NULL) goto notfound;
+    SExpRef ret = REF(*pbinding)->binding.func;
+    if (ret.idx < 0) goto notfound;
+    return ret;
 notfound:
     return new_error(interp, "Unbound function: %s.\n", REF(name)->str);
 }
diff --git a/src/interp.h b/src/interp.h
index 3feecfa..0a489cb 100644
--- a/src/interp.h
+++ b/src/interp.h
@@ -14,16 +14,11 @@ typedef struct parser Parser;
 struct interp;
 typedef struct interp Interp;
 
-typedef struct {
-    SExpRef name;
-    SExpRef binding;
-} TopBinding;
-
-VECTOR_DEF(TopBinding);
+HASH_TABLE_DEF(SExpRef, SExpRef);
 
 struct interp {
     SExpVector objs;
-    TopBindingVector topbindings;
+    SExpRef2SExpRefHashTable topbindings;
     IntVector empty_space;
     String2IntHashTable symbols;
     SExpRef stack;
diff --git a/src/sexp.h b/src/sexp.h
index 2923088..d606acf 100644
--- a/src/sexp.h
+++ b/src/sexp.h
@@ -10,7 +10,7 @@ struct sexp;
 typedef struct sexp SExp;
 
 typedef struct {
-    int idx;
+    int32_t idx;
 } SExpRef;
 
 typedef struct {
-- 
cgit v1.0