klisp

commit d59b74abdb62573d6f040fc79c5eb52baf6afab4
parent 4334d29f126a24d21444006f0de2739708b5e63d
Author: Andres Navarro <canavarro82@gmail.com>
Date:   Tue, 19 Apr 2011 19:31:50 -0300

Added a symbol/immutable string table (from lua). STILL NOT IMPLEMENTED.

Diffstat:
M
src/kobject.h
 | 
3
+++
M
src/kstate.h
 | 
10
+++++++++-
M
src/kstring.c
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
src/kstring.h
 | 
5
+++++

4 files changed, 60 insertions(+), 1 deletion(-)
diff --git a/src/kobject.h b/src/kobject.h
@@ -330,6 +330,9 @@ typedef struct __attribute__ ((__packed__)) {
     CommonHeader;
     TValue mark; /* for cycle/sharing aware algorithms */
     TValue str; /* could use String * here, but for now... */
+    uint32_t hash; /* this is different from the str hash to
+		      avoid having both the string and the symbol
+		      from always falling in the same bucket */
 } Symbol;
 
 typedef struct __attribute__ ((__packed__)) {
diff --git a/src/kstate.h b/src/kstate.h
@@ -34,12 +34,20 @@ typedef struct {
     int32_t saved_col;
 } ksource_info_t;
 
+/* in klisp this has both the immutable strings & the symbols */
+typedef struct stringtable {
+  GCObject **hash;
+  uint32_t nuse;  /* number of elements */
+  int32_t size;
+} stringtable;
+
 #define GC_PROTECT_SIZE 32
 
 /* NOTE: when adding TValues here, remember to add them to
    markroot in kgc.c!! */
 struct klisp_State {
-    TValue symbol_table;
+    TValue symbol_table; /* TO BE DELETED */
+    stringtable strt;  /* hash table for immutable strings & symbols */
     TValue curr_cont;
 
     /*
diff --git a/src/kstring.c b/src/kstring.c
@@ -4,6 +4,8 @@
 ** See Copyright Notice in klisp.h
 */
 
+/* SOURCE NOTE: the string table & hashing code is from lua */
+
 #include <string.h>
 #include <stdbool.h>
 
@@ -13,6 +15,47 @@
 #include "kmem.h"
 #include "kgc.h"
 
+/* for immutable string/symbols table */
+void klispS_resize (klisp_State *K, int32_t newsize)
+{
+    GCObject **newhash;
+    stringtable *tb;
+    int32_t i;
+    if (K->gcstate == GCSsweepstring)
+	return;  /* cannot resize during GC traverse */
+    newhash = klispM_newvector(K, newsize, GCObject *);
+    tb = &K->strt;
+    for (i = 0; i < newsize; i++) newhash[i] = NULL;
+    /* rehash */
+    for (i = 0; i < tb->size; i++) {
+	GCObject *p = tb->hash[i];
+	while (p) {  /* for each node in the list */
+	    /* imm string & symbols aren't chained with all other
+	       objs, but with each other in strt */
+	    GCObject *next = p->gch.next;  /* save next */
+	    
+	    uint32_t h = 0;
+
+	    if (p->gch.tt == K_TSYMBOL) {
+		h = ((Symbol *) p)->hash;
+	    } else if (p->gch.tt == K_TSTRING) {
+		h = ((String *) p)->hash;
+	    } else {
+		klisp_assert(0);
+	    }
+
+	    int32_t h1 = lmod(h, newsize);  /* new position */
+	    klisp_assert((int32_t) (h%newsize) == lmod(h, newsize));
+	    p->gch.next = newhash[h1];  /* chain it */
+	    newhash[h1] = p;
+	    p = next;
+	}
+    }
+    klispM_freearray(K, tb->hash, tb->size, GCObject *);
+    tb->size = newsize;
+    tb->hash = newhash;
+}
+
 /* TEMP: this is for initializing the above value */
 TValue kstring_new_empty(klisp_State *K)
 {
diff --git a/src/kstring.h b/src/kstring.h
@@ -4,6 +4,8 @@
 ** See Copyright Notice in klisp.h
 */
 
+/* SOURCE NOTE: the string table & hashing code is from lua */
+
 #ifndef kstring_h
 #define kstring_h
 
@@ -12,6 +14,9 @@
 #include "kobject.h"
 #include "kstate.h"
 
+/* for immutable string table */
+void klispS_resize (klisp_State *K, int32_t newsize);
+
 /* used for initialization */
 TValue kstring_new_empty(klisp_State *K);
 /* general string constructor, buf remains uninit