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