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