Commit | Line | Data |
---|---|---|
2a24676e | 1 | /* |
8a90f3aa KB |
2 | * Copyright (c) 1983 The Regents of the University of California. |
3 | * All rights reserved. | |
4 | * | |
6ecf3d85 | 5 | * %sccs.include.redist.c% |
2a24676e | 6 | */ |
99c5be11 | 7 | |
2a24676e | 8 | #ifndef lint |
6ecf3d85 | 9 | static char sccsid[] = "@(#)names.c 5.4 (Berkeley) %G%"; |
8a90f3aa | 10 | #endif /* not lint */ |
99c5be11 ML |
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 | ||
9606e7b9 DS |
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 | |
99c5be11 ML |
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 | ||
9606e7b9 | 54 | #define CHUNKSIZE 1000 |
99c5be11 ML |
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; | |
99c5be11 ML |
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 | * | |
9606e7b9 DS |
71 | * This routine is time critical when starting up the debugger |
72 | * on large programs. | |
99c5be11 ML |
73 | */ |
74 | ||
75 | public Name identname(s, isallocated) | |
76 | String s; | |
77 | Boolean isallocated; | |
78 | { | |
79 | register unsigned h; | |
9606e7b9 DS |
80 | register char *p, *q; |
81 | register Name n, *np; | |
99c5be11 ML |
82 | Namepool newpool; |
83 | ||
84 | h = 0; | |
85 | for (p = s; *p != '\0'; p++) { | |
86 | h = (h << 1) ^ (*p); | |
87 | } | |
9606e7b9 DS |
88 | h &= (HASHTABLESIZE-1); |
89 | np = &nametable[h]; | |
90 | n = *np; | |
99c5be11 ML |
91 | while (n != nil) { |
92 | p = s; | |
93 | q = n->identifier; | |
9606e7b9 DS |
94 | while (*p == *q) { |
95 | if (*p == '\0') { | |
96 | return n; | |
99c5be11 ML |
97 | } |
98 | ++p; | |
99 | ++q; | |
100 | } | |
99c5be11 ML |
101 | n = n->chain; |
102 | } | |
103 | ||
104 | /* | |
9606e7b9 DS |
105 | * Now we know that name hasn't been found, |
106 | * so we allocate a name, store the identifier, and | |
99c5be11 ML |
107 | * enter it in the hash table. |
108 | */ | |
109 | if (nleft <= 0) { | |
110 | newpool = new(Namepool); | |
99c5be11 ML |
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 { | |
9606e7b9 DS |
120 | /* this case doesn't happen very often */ |
121 | n->identifier = newarr(char, strlen(s) + 1); | |
99c5be11 ML |
122 | p = s; |
123 | q = n->identifier; | |
124 | while (*p != '\0') { | |
125 | *q++ = *p++; | |
126 | } | |
127 | *q = '\0'; | |
128 | } | |
9606e7b9 DS |
129 | n->chain = *np; |
130 | *np = n; | |
99c5be11 ML |
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 | } |