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