scc

commit 2051da00e5d1a5232fa186eebdd1a662eb770fad
parent e6d33b692fd3237ec7197c2214ae74b476849dd8
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Mon, 12 Dec 2016 13:55:58 +0100

[cc1] Use circular double list for hash collisions

This new data structure will allow us to remove random
types from any point of the list without problems.

Diffstat:
M
cc1/cc1.h
 | 
3
++-
M
cc1/main.c
 | 
1
+
M
cc1/types.c
 | 
29
++++++++++++++++++++++++-----

3 files changed, 27 insertions(+), 6 deletions(-)
diff --git a/cc1/cc1.h b/cc1/cc1.h
@@ -284,7 +284,6 @@ struct type {
 	unsigned char align;        /* align of the type */
 	Type *type;                 /* base type */
 	Symbol *tag;                /* symbol of the strug tag */
-	Type *next;                 /* next element in the hash */
 	union {
 		Type **pars;            /* Function type parameters */
 		Symbol **fields;        /* fields of aggregate type */
@@ -293,6 +292,7 @@ struct type {
 		unsigned char rank;     /* convertion rank */
 		TINT elem;              /* number of type parameters */
 	} n;
+	Type *h_prev, *h_next;       /* hash pointers */
 };
 
 struct symbol {
@@ -356,6 +356,7 @@ extern Type *mktype(Type *tp, int op, TINT nelem, Type *data[]);
 extern Type *duptype(Type *base);
 extern struct limits *getlimits(Type *tp);
 extern void typesize(Type *tp);
+extern void itypes(void);
 
 /* symbol.c */
 extern void dumpstab(char *msg);
diff --git a/cc1/main.c b/cc1/main.c
@@ -58,6 +58,7 @@ main(int argc, char *argv[])
 	int i;
 
 	atexit(clean);
+	itypes();
 	icpp();
 	ilex();
 
diff --git a/cc1/types.c b/cc1/types.c
@@ -72,6 +72,19 @@ static struct limits limits[][4] = {
 	}
 };
 
+static Type typetab[NR_TYPE_HASH];
+
+void
+itypes()
+{
+	Type *tp;
+
+	for (tp = typetab; tp < &typetab[NR_TYPE_HASH]; ++tp) {
+		tp->h_next = tp;
+		tp->h_prev = tp;
+	}
+}
+
 struct limits *
 getlimits(Type *tp)
 {
@@ -242,8 +255,7 @@ typesize(Type *tp)
 Type *
 mktype(Type *tp, int op, TINT nelem, Type *pars[])
 {
-	static Type *typetab[NR_TYPE_HASH];
-	Type **tbl, type;
+	Type *tbl, *h_next, type;
 	unsigned t;
 	Type *bp;
 	int c, k_r = 0;
@@ -296,7 +308,7 @@ mktype(Type *tp, int op, TINT nelem, Type *pars[])
 
 	t = (op ^ (uintptr_t) tp>>3) & NR_TYPE_HASH-1;
 	tbl = &typetab[t];
-	for (bp = *tbl; bp; bp = bp->next) {
+	for (bp = tbl; bp->h_next != tbl; bp = bp->h_next) {
 		if (eqtype(bp, &type, 0) && op != STRUCT && op != UNION) {
 			/*
 			 * pars was allocated by the caller
@@ -313,8 +325,15 @@ mktype(Type *tp, int op, TINT nelem, Type *pars[])
 	bp = xmalloc(sizeof(*bp));
 	*bp = type;
 	bp->id = newid();
-	bp->next = *tbl;
-	return *tbl = bp;
+
+	/* insert the new type in the circular double list */
+	h_next = tbl->h_next;
+	bp->h_next = h_next;
+	bp->h_prev = h_next->h_prev;
+	h_next->h_prev = bp;
+	tbl->h_next = bp;
+
+	return bp;
 }
 
 int