selfhosted lexer

1 files changed, 54 insertions, 0 deletions

diff --git a/src/util.cff b/src/util.cff
index c3a08cb..d1c9dc5 100644
--- a/src/util.cff
+++ b/src/util.cff
@@ -1,3 +1,4 @@
+import "vec.hff";
 import "all.hff";
 
 extern fn xmalloc(n usize) *void {
@@ -6,12 +7,23 @@ extern fn xmalloc(n usize) *void {
    return p;
 }
 
+extern fn xcalloc(n usize, m usize) *void {
+   let p = calloc(n, n);
+   assert(p != #null, "calloc");
+   return p;
+}
+
 extern fn xrealloc(p *void, n usize) *void {
    let p = realloc(p, n);
    assert(p != #null, "realloc");
    return p;
 }
 
+extern fn xstrdup(str *const u8) *u8 {
+   let p = xmalloc(strlen(str) + 1);
+   strcpy(p, str);
+   return p;
+}
 
 extern fn fnv1a(h u32, d [#]const u8) u32 {
    foreach(i, x, d,
@@ -65,3 +77,45 @@ extern fn fatal(P *Parser, loc Loc, fmt *const u8, ...) void {
    ap->end();
    exit(1);
 }
+
+extern fn internstr(s *const u8) *const u8 {
+   static buf Vec<*const u8> = {};
+   static set **const u8 = {};
+   static N int = {};
+   static count int = {};
+
+   if set == #null {
+      set = xcalloc(N = 16, sizeof int);
+   }
+
+   if count == N / 2 {
+      free(set);
+      set = xcalloc(N *= 2, sizeof int);
+      vec_each(s, i, buf,
+         let i = fnv1a_s(FNV1A_INI, s) & (N - 1);
+         for ;; {
+            if set[i] == #null {
+               set[i] = s;
+               break;
+            }
+            i = (i + 1) & (N - 1);
+         }
+      )
+   }
+
+   let i0 = fnv1a_s(FNV1A_INI, s) & (N - 1);
+   let i int = i0;
+   do {
+      if set[i] == #null {
+         ++count;
+         buf->push(xstrdup(s));
+         set[i] = buf.dat[buf.len - 1];
+         return set[i];
+      } else if streq(set[i], s) {
+         return set[i];
+      }
+      i = (i + 1) & (N - 1);
+   } while i != i0;
+   assert(#f, "unreachable");
+
+}