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