1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)names.c 1.3 02/16/83"; 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 200 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 52 /* 53 * Given an identifier, convert it to a name. 54 * If it's not in the hash table, then put it there. 55 * 56 * The second argument specifies whether the string should be copied 57 * into newly allocated space if not found. 58 * 59 * Pardon my use of goto's, but it seemed more efficient and less convoluted 60 * than adding a collection of boolean variables. This routine is time 61 * critical when starting up the debugger on large programs. 62 */ 63 64 public Name identname(s, isallocated) 65 String s; 66 Boolean isallocated; 67 { 68 register unsigned h; 69 register Char *p, *q; 70 register Name n; 71 register Integer len; 72 Namepool newpool; 73 74 h = 0; 75 for (p = s; *p != '\0'; p++) { 76 h = (h << 1) ^ (*p); 77 } 78 h = h mod HASHTABLESIZE; 79 len = p - s; 80 n = nametable[h]; 81 while (n != nil) { 82 p = s; 83 q = n->identifier; 84 for (;;) { 85 if (*p != *q) { 86 goto nomatch; 87 } else if (*p == '\0') { 88 goto match; 89 } 90 ++p; 91 ++q; 92 } 93 nomatch: 94 n = n->chain; 95 } 96 97 /* 98 * Now we know that name hasn't been found (otherwise we'd have jumped 99 * down to match), so we allocate a name, store the identifier, and 100 * enter it in the hash table. 101 */ 102 if (nleft <= 0) { 103 newpool = new(Namepool); 104 bzero(newpool, sizeof(newpool)); 105 newpool->prevpool = namepool; 106 namepool = newpool; 107 nleft = CHUNKSIZE; 108 } 109 --nleft; 110 n = &(namepool->name[nleft]); 111 if (isallocated) { 112 n->identifier = s; 113 } else { 114 n->identifier = newarr(char, len + 1); 115 p = s; 116 q = n->identifier; 117 while (*p != '\0') { 118 *q++ = *p++; 119 } 120 *q = '\0'; 121 } 122 n->chain = nametable[h]; 123 nametable[h] = n; 124 125 /* 126 * The two possibilities (name known versus unknown) rejoin. 127 */ 128 match: 129 return n; 130 } 131 132 /* 133 * Return the identifier associated with a name. 134 * 135 * Currently compiled inline. 136 * 137 * 138 * public String ident(n) 139 Name n; 140 { 141 return (n == nil) ? "(noname)" : n->identifier; 142 } 143 * 144 */ 145 146 /* 147 * Deallocate the name table. 148 */ 149 150 public names_free() 151 { 152 register int i; 153 register Name n, next; 154 155 for (i = 0; i < HASHTABLESIZE; i++) { 156 n = nametable[i]; 157 while (n != nil) { 158 next = n->chain; 159 dispose(n); 160 n = next; 161 } 162 nametable[i] = nil; 163 } 164 namepool = nil; 165 nleft = 0; 166 } 167