/* SYMBOL TABLE HANDLING */ #include #define IDF_HASHSIZE 307 /* size of hashtable, must be odd */ #define IDF_STARTHASH(hs) (hs = 0) #define IDF_ENHASH(hs,ch) (hs = (hs << 2) + ch) #define IDF_STOPHASH(hs) (hs = hs % IDF_HASHSIZE) static struct idf *IDF_hashtable[IDF_HASHSIZE]; /* All identifiers can in principle be reached through IDF_hashtable; IDF_hashtable[hc] is the start of a chain of idf's whose tags all hash to hc. Any identifier is entered into this list, regardless of the nature of its declaration (variable, selector, structure tag, etc.). */ _PROTOTYPE(static struct idf *IDF_new, (char *, int, int)); void init_idf() { } static struct idf * IDF_new(tg, size, cpy) register char *tg; register int size; { static int nidf; static struct idf *pidf; static struct idf null_idf; register struct idf *id; #define NIDS 50 #define IBUFSIZ 2048 static unsigned int icnt; static char *ip; register char *p; if (! nidf--) { nidf += NIDS; pidf = (struct idf *) Malloc(NIDS * sizeof (struct idf)); } id = pidf; pidf++; *id = null_idf; if (cpy) { if (size > icnt) { icnt = size > IBUFSIZ ? size : IBUFSIZ; p = Malloc(icnt); } else p = ip; icnt -= size; id->id_text = p; while (size--) { *p++ = *tg++; } ip = p; } else id->id_text = tg; return id; } #ifdef IDF_DEBUG void hash_stat() { register int i; int total_count = 0; print("Hash table tally:\n"); for (i = 0; i < IDF_HASHSIZE; i++) { register struct idf *notch = IDF_hashtable[i]; register int cnt = 0; print ("%d ", i); while (notch) { cnt++; print("'%s' ", notch->id_text); notch = notch->id_next; } print("%d\n", cnt); total_count += cnt; } print("total = %d\n", total_count); print("End hash table tally\n"); } void idfappfun(fun, opt) int (*fun)(); int opt; { register int i; for (i = 0; i < IDF_HASHSIZE; i++) { register struct idf *notch = IDF_hashtable[i]; while (notch) { (*fun)(notch, opt); notch = notch->id_next; } } } #endif /* IDF_DEBUG */ struct idf * str2idf(tg, cpy) char tg[]; { /* str2idf() returns an entry in the symbol table for the identifier tg. If necessary, an entry is created. */ register char *cp = tg; struct idf **hook; register struct idf *notch; register unsigned int hash; register int c; int size; IDF_STARTHASH(hash); while (c = *cp++) { IDF_ENHASH(hash, c); } IDF_STOPHASH(hash); size = cp - tg; /* The tag tg with length size and known hash value hash is looked up in the identifier table; if not found, it is entered if cpy >= 0. A pointer to it is returned. Notice that the chains of idf's are sorted alphabetically. */ hook = &IDF_hashtable[hash]; while ((notch = *hook)) { register char *s1 = tg; cp = notch->id_text; while (!(c = (*s1 - *cp++))) { if (*s1++ == '\0') { break; } } if (c == 0) return notch; if (c < 0) break; hook = ¬ch->id_next; } /* a new struct idf must be inserted at the hook */ if (cpy < 0) return 0; notch = IDF_new(tg, size, cpy); notch->id_next = *hook; *hook = notch; /* hooked in */ return notch; }