[hackers] [scc] [cc1] Use circular double list for hash collisions || Roberto E. Vargas Caballero

From: <git_AT_suckless.org>
Date: Mon, 12 Dec 2016 15:53:03 +0100 (CET)

commit 2051da00e5d1a5232fa186eebdd1a662eb770fad
Author: Roberto E. Vargas Caballero <k0ga_AT_shike2.com>
AuthorDate: Mon Dec 12 13:55:58 2016 +0100
Commit: Roberto E. Vargas Caballero <k0ga_AT_shike2.com>
CommitDate: Mon Dec 12 15:34:04 2016 +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.

diff --git a/cc1/cc1.h b/cc1/cc1.h
index 9ded21e..55d7bf8 100644
--- a/cc1/cc1.h
+++ b/cc1/cc1.h
_AT_@ -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 */
_AT_@ -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 {
_AT_@ -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
index a87e23e..c2ba7d3 100644
--- a/cc1/main.c
+++ b/cc1/main.c
_AT_@ -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
index cfb4b06..71d5dcf 100644
--- a/cc1/types.c
+++ b/cc1/types.c
_AT_@ -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)
 {
_AT_@ -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;
_AT_@ -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
_AT_@ -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
Received on Mon Dec 12 2016 - 15:53:03 CET