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