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