shithub: scc

Info  •  Files  •  Log  •  Branches

[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.

--- a/cc1/cc1.h

+++ b/cc1/cc1.h

@@ -284,7 +284,6 @@

 	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 @@

 		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 *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);

--- a/cc1/main.c

+++ b/cc1/main.c

@@ -58,6 +58,7 @@

 	int i;

 	atexit(clean);

+	itypes();

 	icpp();

 	ilex();

--- a/cc1/types.c

+++ b/cc1/types.c

@@ -72,6 +72,19 @@

 	}

 };

+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 @@

 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 @@

 	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 @@

 	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