1f4ea7fffSdist /*
2be26f981Sbostic * Copyright (c) 1983 The Regents of the University of California.
3be26f981Sbostic * All rights reserved.
4be26f981Sbostic *
5*1808f06cSbostic * %sccs.include.redist.c%
6f4ea7fffSdist */
7814ef51cSlinton
8f4ea7fffSdist #ifndef lint
9*1808f06cSbostic static char sccsid[] = "@(#)names.c 5.4 (Berkeley) 06/01/90";
10be26f981Sbostic #endif /* not lint */
11814ef51cSlinton
12814ef51cSlinton /*
13814ef51cSlinton * Name are the internal representation for identifiers.
14814ef51cSlinton *
15814ef51cSlinton * A hash table is used to map identifiers to names.
16814ef51cSlinton */
17814ef51cSlinton
18814ef51cSlinton #include "defs.h"
19814ef51cSlinton #include "names.h"
20814ef51cSlinton
21814ef51cSlinton #ifndef public
22814ef51cSlinton typedef struct Name *Name;
23814ef51cSlinton
24814ef51cSlinton /*
25814ef51cSlinton * Inline (for speed) function to return the identifier (string)
26814ef51cSlinton * associated with a name. Because C cannot support both inlines
27814ef51cSlinton * and data hiding at the same time, the Name structure must be
28814ef51cSlinton * publicly visible. It is not used explicitly, however, outside of this file.
29814ef51cSlinton */
30814ef51cSlinton
31814ef51cSlinton struct Name {
32814ef51cSlinton char *identifier;
33814ef51cSlinton Name chain;
34814ef51cSlinton };
35814ef51cSlinton
36814ef51cSlinton #define ident(n) ((n == nil) ? "(noname)" : n->identifier)
37814ef51cSlinton #endif
38814ef51cSlinton
3908dd8fdaSdonn /*
4008dd8fdaSdonn * The hash table is a power of two, in order to make hashing faster.
4108dd8fdaSdonn * Using a non-prime is ok since we use chaining instead of re-hashing.
4208dd8fdaSdonn */
4308dd8fdaSdonn
4408dd8fdaSdonn #define HASHTABLESIZE 8192
45814ef51cSlinton
46814ef51cSlinton private Name nametable[HASHTABLESIZE];
47814ef51cSlinton
48814ef51cSlinton /*
49814ef51cSlinton * Names are allocated in large chunks to avoid calls to malloc
50814ef51cSlinton * and to cluster names in memory so that tracing hash chains
51814ef51cSlinton * doesn't cause many a page fault.
52814ef51cSlinton */
53814ef51cSlinton
5408dd8fdaSdonn #define CHUNKSIZE 1000
55814ef51cSlinton
56814ef51cSlinton typedef struct Namepool {
57814ef51cSlinton struct Name name[CHUNKSIZE];
58814ef51cSlinton struct Namepool *prevpool;
59814ef51cSlinton } *Namepool;
60814ef51cSlinton
61814ef51cSlinton private Namepool namepool = nil;
62814ef51cSlinton private Integer nleft = 0;
63814ef51cSlinton
64814ef51cSlinton /*
65814ef51cSlinton * Given an identifier, convert it to a name.
66814ef51cSlinton * If it's not in the hash table, then put it there.
67814ef51cSlinton *
68814ef51cSlinton * The second argument specifies whether the string should be copied
69814ef51cSlinton * into newly allocated space if not found.
70814ef51cSlinton *
7108dd8fdaSdonn * This routine is time critical when starting up the debugger
7208dd8fdaSdonn * on large programs.
73814ef51cSlinton */
74814ef51cSlinton
identname(s,isallocated)75814ef51cSlinton public Name identname(s, isallocated)
76814ef51cSlinton String s;
77814ef51cSlinton Boolean isallocated;
78814ef51cSlinton {
79814ef51cSlinton register unsigned h;
8008dd8fdaSdonn register char *p, *q;
8108dd8fdaSdonn register Name n, *np;
82814ef51cSlinton Namepool newpool;
83814ef51cSlinton
84814ef51cSlinton h = 0;
85814ef51cSlinton for (p = s; *p != '\0'; p++) {
86814ef51cSlinton h = (h << 1) ^ (*p);
87814ef51cSlinton }
8808dd8fdaSdonn h &= (HASHTABLESIZE-1);
8908dd8fdaSdonn np = &nametable[h];
9008dd8fdaSdonn n = *np;
91814ef51cSlinton while (n != nil) {
92814ef51cSlinton p = s;
93814ef51cSlinton q = n->identifier;
9408dd8fdaSdonn while (*p == *q) {
9508dd8fdaSdonn if (*p == '\0') {
9608dd8fdaSdonn return n;
97814ef51cSlinton }
98814ef51cSlinton ++p;
99814ef51cSlinton ++q;
100814ef51cSlinton }
101814ef51cSlinton n = n->chain;
102814ef51cSlinton }
103814ef51cSlinton
104814ef51cSlinton /*
10508dd8fdaSdonn * Now we know that name hasn't been found,
10608dd8fdaSdonn * so we allocate a name, store the identifier, and
107814ef51cSlinton * enter it in the hash table.
108814ef51cSlinton */
109814ef51cSlinton if (nleft <= 0) {
110814ef51cSlinton newpool = new(Namepool);
111814ef51cSlinton newpool->prevpool = namepool;
112814ef51cSlinton namepool = newpool;
113814ef51cSlinton nleft = CHUNKSIZE;
114814ef51cSlinton }
115814ef51cSlinton --nleft;
116814ef51cSlinton n = &(namepool->name[nleft]);
117814ef51cSlinton if (isallocated) {
118814ef51cSlinton n->identifier = s;
119814ef51cSlinton } else {
12008dd8fdaSdonn /* this case doesn't happen very often */
12108dd8fdaSdonn n->identifier = newarr(char, strlen(s) + 1);
122814ef51cSlinton p = s;
123814ef51cSlinton q = n->identifier;
124814ef51cSlinton while (*p != '\0') {
125814ef51cSlinton *q++ = *p++;
126814ef51cSlinton }
127814ef51cSlinton *q = '\0';
128814ef51cSlinton }
12908dd8fdaSdonn n->chain = *np;
13008dd8fdaSdonn *np = n;
131814ef51cSlinton return n;
132814ef51cSlinton }
133814ef51cSlinton
134814ef51cSlinton /*
135814ef51cSlinton * Deallocate the name table.
136814ef51cSlinton */
137814ef51cSlinton
names_free()138814ef51cSlinton public names_free()
139814ef51cSlinton {
140ecc5c44dSlinton Namepool n, m;
141ecc5c44dSlinton register integer i;
142814ef51cSlinton
143ecc5c44dSlinton n = namepool;
144814ef51cSlinton while (n != nil) {
145ecc5c44dSlinton m = n->prevpool;
146814ef51cSlinton dispose(n);
147ecc5c44dSlinton n = m;
148814ef51cSlinton }
149ecc5c44dSlinton for (i = 0; i < HASHTABLESIZE; i++) {
150814ef51cSlinton nametable[i] = nil;
151814ef51cSlinton }
152814ef51cSlinton namepool = nil;
153814ef51cSlinton nleft = 0;
154814ef51cSlinton }
155