![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to names.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / dbx|
Return to names.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / dbx |
1.1 root 1: /*
2: * Copyright (c) 1983 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted
6: * provided that: (1) source distributions retain this entire copyright
7: * notice and comment, and (2) distributions including binaries display
8: * the following acknowledgement: ``This product includes software
9: * developed by the University of California, Berkeley and its contributors''
10: * in the documentation or other materials provided with the distribution
11: * and in all advertising materials mentioning features or use of this
12: * software. Neither the name of the University nor the names of its
13: * contributors may be used to endorse or promote products derived
14: * from this software without specific prior written permission.
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18: */
19:
20: #ifndef lint
21: static char sccsid[] = "@(#)names.c 5.4 (Berkeley) 6/1/90";
22: #endif /* not lint */
23:
24: /*
25: * Name are the internal representation for identifiers.
26: *
27: * A hash table is used to map identifiers to names.
28: */
29:
30: #include "defs.h"
31: #include "names.h"
32:
33: #ifndef public
34: typedef struct Name *Name;
35:
36: /*
37: * Inline (for speed) function to return the identifier (string)
38: * associated with a name. Because C cannot support both inlines
39: * and data hiding at the same time, the Name structure must be
40: * publicly visible. It is not used explicitly, however, outside of this file.
41: */
42:
43: struct Name {
44: char *identifier;
45: Name chain;
46: };
47:
48: #define ident(n) ((n == nil) ? "(noname)" : n->identifier)
49: #endif
50:
51: /*
52: * The hash table is a power of two, in order to make hashing faster.
53: * Using a non-prime is ok since we use chaining instead of re-hashing.
54: */
55:
56: #define HASHTABLESIZE 8192
57:
58: private Name nametable[HASHTABLESIZE];
59:
60: /*
61: * Names are allocated in large chunks to avoid calls to malloc
62: * and to cluster names in memory so that tracing hash chains
63: * doesn't cause many a page fault.
64: */
65:
66: #define CHUNKSIZE 1000
67:
68: typedef struct Namepool {
69: struct Name name[CHUNKSIZE];
70: struct Namepool *prevpool;
71: } *Namepool;
72:
73: private Namepool namepool = nil;
74: private Integer nleft = 0;
75:
76: /*
77: * Given an identifier, convert it to a name.
78: * If it's not in the hash table, then put it there.
79: *
80: * The second argument specifies whether the string should be copied
81: * into newly allocated space if not found.
82: *
83: * This routine is time critical when starting up the debugger
84: * on large programs.
85: */
86:
87: public Name identname(s, isallocated)
88: String s;
89: Boolean isallocated;
90: {
91: register unsigned h;
92: register char *p, *q;
93: register Name n, *np;
94: Namepool newpool;
95:
96: h = 0;
97: for (p = s; *p != '\0'; p++) {
98: h = (h << 1) ^ (*p);
99: }
100: h &= (HASHTABLESIZE-1);
101: np = &nametable[h];
102: n = *np;
103: while (n != nil) {
104: p = s;
105: q = n->identifier;
106: while (*p == *q) {
107: if (*p == '\0') {
108: return n;
109: }
110: ++p;
111: ++q;
112: }
113: n = n->chain;
114: }
115:
116: /*
117: * Now we know that name hasn't been found,
118: * so we allocate a name, store the identifier, and
119: * enter it in the hash table.
120: */
121: if (nleft <= 0) {
122: newpool = new(Namepool);
123: newpool->prevpool = namepool;
124: namepool = newpool;
125: nleft = CHUNKSIZE;
126: }
127: --nleft;
128: n = &(namepool->name[nleft]);
129: if (isallocated) {
130: n->identifier = s;
131: } else {
132: /* this case doesn't happen very often */
133: n->identifier = newarr(char, strlen(s) + 1);
134: p = s;
135: q = n->identifier;
136: while (*p != '\0') {
137: *q++ = *p++;
138: }
139: *q = '\0';
140: }
141: n->chain = *np;
142: *np = n;
143: return n;
144: }
145:
146: /*
147: * Deallocate the name table.
148: */
149:
150: public names_free()
151: {
152: Namepool n, m;
153: register integer i;
154:
155: n = namepool;
156: while (n != nil) {
157: m = n->prevpool;
158: dispose(n);
159: n = m;
160: }
161: for (i = 0; i < HASHTABLESIZE; i++) {
162: nametable[i] = nil;
163: }
164: namepool = nil;
165: nleft = 0;
166: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.