1 /* Copyright (c) 1982 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)names.c 1.5 (Berkeley) 03/01/85"; 4 5 static char rcsid[] = "$Header: names.c,v 1.4 84/12/26 10:40:47 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 * Deallocate the name table. 136 */ 137 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