1 /* 2 * Copyright (c) 1983 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)names.c 5.4 (Berkeley) 06/01/90"; 10 #endif /* not lint */ 11 12 /* 13 * Name are the internal representation for identifiers. 14 * 15 * A hash table is used to map identifiers to names. 16 */ 17 18 #include "defs.h" 19 #include "names.h" 20 21 #ifndef public 22 typedef struct Name *Name; 23 24 /* 25 * Inline (for speed) function to return the identifier (string) 26 * associated with a name. Because C cannot support both inlines 27 * and data hiding at the same time, the Name structure must be 28 * publicly visible. It is not used explicitly, however, outside of this file. 29 */ 30 31 struct Name { 32 char *identifier; 33 Name chain; 34 }; 35 36 #define ident(n) ((n == nil) ? "(noname)" : n->identifier) 37 #endif 38 39 /* 40 * The hash table is a power of two, in order to make hashing faster. 41 * Using a non-prime is ok since we use chaining instead of re-hashing. 42 */ 43 44 #define HASHTABLESIZE 8192 45 46 private Name nametable[HASHTABLESIZE]; 47 48 /* 49 * Names are allocated in large chunks to avoid calls to malloc 50 * and to cluster names in memory so that tracing hash chains 51 * doesn't cause many a page fault. 52 */ 53 54 #define CHUNKSIZE 1000 55 56 typedef struct Namepool { 57 struct Name name[CHUNKSIZE]; 58 struct Namepool *prevpool; 59 } *Namepool; 60 61 private Namepool namepool = nil; 62 private Integer nleft = 0; 63 64 /* 65 * Given an identifier, convert it to a name. 66 * If it's not in the hash table, then put it there. 67 * 68 * The second argument specifies whether the string should be copied 69 * into newly allocated space if not found. 70 * 71 * This routine is time critical when starting up the debugger 72 * on large programs. 73 */ 74 75 public Name identname(s, isallocated) 76 String s; 77 Boolean isallocated; 78 { 79 register unsigned h; 80 register char *p, *q; 81 register Name n, *np; 82 Namepool newpool; 83 84 h = 0; 85 for (p = s; *p != '\0'; p++) { 86 h = (h << 1) ^ (*p); 87 } 88 h &= (HASHTABLESIZE-1); 89 np = &nametable[h]; 90 n = *np; 91 while (n != nil) { 92 p = s; 93 q = n->identifier; 94 while (*p == *q) { 95 if (*p == '\0') { 96 return n; 97 } 98 ++p; 99 ++q; 100 } 101 n = n->chain; 102 } 103 104 /* 105 * Now we know that name hasn't been found, 106 * so we allocate a name, store the identifier, and 107 * enter it in the hash table. 108 */ 109 if (nleft <= 0) { 110 newpool = new(Namepool); 111 newpool->prevpool = namepool; 112 namepool = newpool; 113 nleft = CHUNKSIZE; 114 } 115 --nleft; 116 n = &(namepool->name[nleft]); 117 if (isallocated) { 118 n->identifier = s; 119 } else { 120 /* this case doesn't happen very often */ 121 n->identifier = newarr(char, strlen(s) + 1); 122 p = s; 123 q = n->identifier; 124 while (*p != '\0') { 125 *q++ = *p++; 126 } 127 *q = '\0'; 128 } 129 n->chain = *np; 130 *np = n; 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