xref: /original-bsd/old/dbx/names.c (revision 1808f06c)
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