1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)names.c 1.3 2/16/83"; 4 5 static char rcsid[] = "$Header: names.c,v 1.3 84/03/27 10:22:19 linton Exp $"; 6 7 /* 8 * Name are the internal representation for identifiers. 9 * 10 * A hash table is used to map identifiers to names. 11 */ 12 13 #include "defs.h" 14 #include "names.h" 15 16 #ifndef public 17 typedef struct Name *Name; 18 19 /* 20 * Inline (for speed) function to return the identifier (string) 21 * associated with a name. Because C cannot support both inlines 22 * and data hiding at the same time, the Name structure must be 23 * publicly visible. It is not used explicitly, however, outside of this file. 24 */ 25 26 struct Name { 27 char *identifier; 28 Name chain; 29 }; 30 31 #define ident(n) ((n == nil) ? "(noname)" : n->identifier) 32 #endif 33 34 #define HASHTABLESIZE 2997 35 36 private Name nametable[HASHTABLESIZE]; 37 38 /* 39 * Names are allocated in large chunks to avoid calls to malloc 40 * and to cluster names in memory so that tracing hash chains 41 * doesn't cause many a page fault. 42 */ 43 44 #define CHUNKSIZE 200 45 46 typedef struct Namepool { 47 struct Name name[CHUNKSIZE]; 48 struct Namepool *prevpool; 49 } *Namepool; 50 51 private Namepool namepool = nil; 52 private Integer nleft = 0; 53 54 /* 55 * Given an identifier, convert it to a name. 56 * If it's not in the hash table, then put it there. 57 * 58 * The second argument specifies whether the string should be copied 59 * into newly allocated space if not found. 60 * 61 * Pardon my use of goto's, but it seemed more efficient and less convoluted 62 * than adding a collection of boolean variables. This routine is time 63 * critical when starting up the debugger on large programs. 64 */ 65 66 public Name identname(s, isallocated) 67 String s; 68 Boolean isallocated; 69 { 70 register unsigned h; 71 register Char *p, *q; 72 register Name n; 73 register Integer len; 74 Namepool newpool; 75 76 h = 0; 77 for (p = s; *p != '\0'; p++) { 78 h = (h << 1) ^ (*p); 79 } 80 h = h mod HASHTABLESIZE; 81 len = p - s; 82 n = nametable[h]; 83 while (n != nil) { 84 p = s; 85 q = n->identifier; 86 for (;;) { 87 if (*p != *q) { 88 goto nomatch; 89 } else if (*p == '\0') { 90 goto match; 91 } 92 ++p; 93 ++q; 94 } 95 nomatch: 96 n = n->chain; 97 } 98 99 /* 100 * Now we know that name hasn't been found (otherwise we'd have jumped 101 * down to match), so we allocate a name, store the identifier, and 102 * enter it in the hash table. 103 */ 104 if (nleft <= 0) { 105 newpool = new(Namepool); 106 bzero(newpool, sizeof(newpool)); 107 newpool->prevpool = namepool; 108 namepool = newpool; 109 nleft = CHUNKSIZE; 110 } 111 --nleft; 112 n = &(namepool->name[nleft]); 113 if (isallocated) { 114 n->identifier = s; 115 } else { 116 n->identifier = newarr(char, len + 1); 117 p = s; 118 q = n->identifier; 119 while (*p != '\0') { 120 *q++ = *p++; 121 } 122 *q = '\0'; 123 } 124 n->chain = nametable[h]; 125 nametable[h] = n; 126 127 /* 128 * The two possibilities (name known versus unknown) rejoin. 129 */ 130 match: 131 return n; 132 } 133 134 /* 135 * Return the identifier associated with a name. 136 * 137 * Currently compiled inline. 138 * 139 * 140 * public String ident(n) 141 Name n; 142 { 143 return (n == nil) ? "(noname)" : n->identifier; 144 } 145 * 146 */ 147 148 /* 149 * Deallocate the name table. 150 */ 151 152 public names_free() 153 { 154 register int i; 155 register Name n, next; 156 157 for (i = 0; i < HASHTABLESIZE; i++) { 158 n = nametable[i]; 159 while (n != nil) { 160 next = n->chain; 161 dispose(n); 162 n = next; 163 } 164 nametable[i] = nil; 165 } 166 namepool = nil; 167 nleft = 0; 168 } 169