From a3a1451c5fabb5c94f7fbeb13fdc6b1e2c23181f Mon Sep 17 00:00:00 2001
From: Quentin Carbonneaux <quentin@c9x.me>
Date: Wed, 17 May 2017 09:40:07 -0400
Subject: intern symbol names

Symbols in the source file are still limited in
length because the rest of the code assumes that
strings always fit in NString bytes.

Regardless, there is already a benefit because
comparing/copying symbol names does not require
using strcmp()/strcpy() anymore.
---
 util.c | 151 ++++++++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 103 insertions(+), 48 deletions(-)

(limited to 'util.c')

diff --git a/util.c b/util.c
index cb6e75c..8527931 100644
--- a/util.c
+++ b/util.c
@@ -3,6 +3,7 @@
 
 typedef struct Bitset Bitset;
 typedef struct Vec Vec;
+typedef struct Bucket Bucket;
 
 struct Vec {
 	ulong mag;
@@ -16,10 +17,17 @@ struct Vec {
 	} align[];
 };
 
+struct Bucket {
+	uint nstr;
+	char **str;
+};
+
 enum {
 	VMin = 2,
 	VMag = 0xcabba9e,
 	NPtr = 256,
+	IBits = 12,
+	IMask = (1<<IBits) - 1,
 };
 
 Typ *typ;
@@ -29,6 +37,18 @@ static void *ptr[NPtr];
 static void **pool = ptr;
 static int nptr = 1;
 
+static Bucket itbl[IMask+1]; /* string interning table */
+
+uint32_t
+hash(char *s)
+{
+	uint32_t h;
+
+	for (h=0; *s; ++s)
+		h = *s + 17*h;
+	return h;
+}
+
 void
 die_(char *file, char *s, ...)
 {
@@ -87,6 +107,88 @@ freeall()
 	nptr = 1;
 }
 
+void *
+vnew(ulong len, size_t esz, Pool pool)
+{
+	void *(*f)(size_t);
+	ulong cap;
+	Vec *v;
+
+	for (cap=VMin; cap<len; cap*=2)
+		;
+	f = pool == Pheap ? emalloc : alloc;
+	v = f(cap * esz + sizeof(Vec));
+	v->mag = VMag;
+	v->cap = cap;
+	v->esz = esz;
+	v->pool = pool;
+	return v + 1;
+}
+
+void
+vfree(void *p)
+{
+	Vec *v;
+
+	v = (Vec *)p - 1;
+	assert(v->mag == VMag);
+	if (v->pool == Pheap) {
+		v->mag = 0;
+		free(v);
+	}
+}
+
+void
+vgrow(void *vp, ulong len)
+{
+	Vec *v;
+	void *v1;
+
+	v = *(Vec **)vp - 1;
+	assert(v+1 && v->mag == VMag);
+	if (v->cap >= len)
+		return;
+	v1 = vnew(len, v->esz, v->pool);
+	memcpy(v1, v+1, v->cap * v->esz);
+	vfree(v+1);
+	*(Vec **)vp = v1;
+}
+
+uint32_t
+intern(char *s)
+{
+	Bucket *b;
+	uint32_t h;
+	uint i, n;
+
+	h = hash(s) & IMask;
+	b = &itbl[h];
+	n = b->nstr;
+
+	for (i=0; i<n; i++)
+		if (strcmp(s, b->str[i]) == 0)
+			return h + (i<<IBits);
+
+	if (n == 1<<(32-IBits))
+		die("interning table overflow");
+	if (n == 0)
+		b->str = vnew(1, sizeof b->str[0], Pheap);
+	else if ((n & (n-1)) == 0)
+		vgrow(&b->str, n+n);
+
+	b->str[n] = emalloc(strlen(s)+1);
+	b->nstr = n + 1;
+	strcpy(b->str[n], s);
+	return h + (n<<IBits);
+}
+
+char *
+str(uint32_t id)
+{
+	assert(id>>IBits < itbl[id&IMask].nstr);
+	return itbl[id&IMask].str[id>>IBits];
+}
+
 int
 iscmp(int op, int *pk, int *pc)
 {
@@ -148,53 +250,6 @@ icpy(Ins *d, Ins *s, ulong n)
 	return d + n;
 }
 
-void *
-vnew(ulong len, size_t esz, Pool pool)
-{
-	void *(*f)(size_t);
-	ulong cap;
-	Vec *v;
-
-	for (cap=VMin; cap<len; cap*=2)
-		;
-	f = pool == Pheap ? emalloc : alloc;
-	v = f(cap * esz + sizeof(Vec));
-	v->mag = VMag;
-	v->cap = cap;
-	v->esz = esz;
-	v->pool = pool;
-	return v + 1;
-}
-
-void
-vfree(void *p)
-{
-	Vec *v;
-
-	v = (Vec *)p - 1;
-	assert(v->mag == VMag);
-	if (v->pool == Pheap) {
-		v->mag = 0;
-		free(v);
-	}
-}
-
-void
-vgrow(void *vp, ulong len)
-{
-	Vec *v;
-	void *v1;
-
-	v = *(Vec **)vp - 1;
-	assert(v+1 && v->mag == VMag);
-	if (v->cap >= len)
-		return;
-	v1 = vnew(len, v->esz, v->pool);
-	memcpy(v1, v+1, v->cap * v->esz);
-	vfree(v+1);
-	*(Vec **)vp = v1;
-}
-
 static int cmptab[][2] ={
 	             /* negation    swap */
 	[Ciule]      = {Ciugt,      Ciuge},
@@ -308,7 +363,7 @@ addcon(Con *c0, Con *c1)
 		if (c1->type == CAddr) {
 			assert(c0->type != CAddr && "adding two addresses");
 			c0->type = CAddr;
-			strcpy(c0->label, c1->label);
+			c0->label = c1->label;
 		}
 		c0->bits.i += c1->bits.i;
 	}
-- 
cgit 1.4.1