Commit | Line | Data |
---|---|---|
99c5be11 ML |
1 | /* Copyright (c) 1982 Regents of the University of California */ |
2 | ||
ecdd5e38 | 3 | static char sccsid[] = "@(#)names.c 1.3 %G%"; |
99c5be11 ML |
4 | |
5 | /* | |
6 | * Name are the internal representation for identifiers. | |
7 | * | |
8 | * A hash table is used to map identifiers to names. | |
9 | */ | |
10 | ||
11 | #include "defs.h" | |
12 | #include "names.h" | |
13 | ||
14 | #ifndef public | |
15 | typedef struct Name *Name; | |
16 | ||
17 | /* | |
18 | * Inline (for speed) function to return the identifier (string) | |
19 | * associated with a name. Because C cannot support both inlines | |
20 | * and data hiding at the same time, the Name structure must be | |
21 | * publicly visible. It is not used explicitly, however, outside of this file. | |
22 | */ | |
23 | ||
24 | struct Name { | |
25 | char *identifier; | |
26 | Name chain; | |
27 | }; | |
28 | ||
29 | #define ident(n) ((n == nil) ? "(noname)" : n->identifier) | |
30 | #endif | |
31 | ||
32 | #define HASHTABLESIZE 2997 | |
33 | ||
34 | private Name nametable[HASHTABLESIZE]; | |
35 | ||
36 | /* | |
37 | * Names are allocated in large chunks to avoid calls to malloc | |
38 | * and to cluster names in memory so that tracing hash chains | |
39 | * doesn't cause many a page fault. | |
40 | */ | |
41 | ||
ecdd5e38 | 42 | #define CHUNKSIZE 200 |
99c5be11 ML |
43 | |
44 | typedef struct Namepool { | |
45 | struct Name name[CHUNKSIZE]; | |
46 | struct Namepool *prevpool; | |
47 | } *Namepool; | |
48 | ||
49 | private Namepool namepool = nil; | |
50 | private Integer nleft = 0; | |
99c5be11 ML |
51 | |
52 | /* | |
53 | * Given an identifier, convert it to a name. | |
54 | * If it's not in the hash table, then put it there. | |
55 | * | |
56 | * The second argument specifies whether the string should be copied | |
57 | * into newly allocated space if not found. | |
58 | * | |
59 | * Pardon my use of goto's, but it seemed more efficient and less convoluted | |
60 | * than adding a collection of boolean variables. This routine is time | |
61 | * critical when starting up the debugger on large programs. | |
62 | */ | |
63 | ||
64 | public Name identname(s, isallocated) | |
65 | String s; | |
66 | Boolean isallocated; | |
67 | { | |
68 | register unsigned h; | |
69 | register Char *p, *q; | |
70 | register Name n; | |
71 | register Integer len; | |
72 | Namepool newpool; | |
73 | ||
74 | h = 0; | |
75 | for (p = s; *p != '\0'; p++) { | |
76 | h = (h << 1) ^ (*p); | |
77 | } | |
78 | h = h mod HASHTABLESIZE; | |
79 | len = p - s; | |
80 | n = nametable[h]; | |
81 | while (n != nil) { | |
82 | p = s; | |
83 | q = n->identifier; | |
84 | for (;;) { | |
85 | if (*p != *q) { | |
86 | goto nomatch; | |
87 | } else if (*p == '\0') { | |
88 | goto match; | |
89 | } | |
90 | ++p; | |
91 | ++q; | |
92 | } | |
93 | nomatch: | |
94 | n = n->chain; | |
95 | } | |
96 | ||
97 | /* | |
98 | * Now we know that name hasn't been found (otherwise we'd have jumped | |
99 | * down to match), so we allocate a name, store the identifier, and | |
100 | * enter it in the hash table. | |
101 | */ | |
102 | if (nleft <= 0) { | |
103 | newpool = new(Namepool); | |
ecdd5e38 | 104 | bzero(newpool, sizeof(newpool)); |
99c5be11 ML |
105 | newpool->prevpool = namepool; |
106 | namepool = newpool; | |
107 | nleft = CHUNKSIZE; | |
108 | } | |
109 | --nleft; | |
110 | n = &(namepool->name[nleft]); | |
111 | if (isallocated) { | |
112 | n->identifier = s; | |
113 | } else { | |
114 | n->identifier = newarr(char, len + 1); | |
115 | p = s; | |
116 | q = n->identifier; | |
117 | while (*p != '\0') { | |
118 | *q++ = *p++; | |
119 | } | |
120 | *q = '\0'; | |
121 | } | |
122 | n->chain = nametable[h]; | |
123 | nametable[h] = n; | |
124 | ||
125 | /* | |
126 | * The two possibilities (name known versus unknown) rejoin. | |
127 | */ | |
128 | match: | |
129 | return n; | |
130 | } | |
131 | ||
132 | /* | |
133 | * Return the identifier associated with a name. | |
134 | * | |
135 | * Currently compiled inline. | |
136 | * | |
137 | * | |
138 | * public String ident(n) | |
139 | Name n; | |
140 | { | |
141 | return (n == nil) ? "(noname)" : n->identifier; | |
142 | } | |
143 | * | |
144 | */ | |
145 | ||
146 | /* | |
147 | * Deallocate the name table. | |
148 | */ | |
149 | ||
150 | public names_free() | |
151 | { | |
152 | register int i; | |
153 | register Name n, next; | |
154 | ||
155 | for (i = 0; i < HASHTABLESIZE; i++) { | |
156 | n = nametable[i]; | |
157 | while (n != nil) { | |
158 | next = n->chain; | |
159 | dispose(n); | |
160 | n = next; | |
161 | } | |
162 | nametable[i] = nil; | |
163 | } | |
164 | namepool = nil; | |
165 | nleft = 0; | |
166 | } |