4.3BSD - /usr/src/ucb/dbx/names.c

   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.1 (Berkeley) 5/31/85";
   9: #endif not lint
  10: 
  11: static char rcsid[] = "$Header: names.c,v 1.4 84/12/26 10:40:47 linton 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: #define HASHTABLESIZE 2997
  41: 
  42: private Name nametable[HASHTABLESIZE];
  43: 
  44: /*
  45:  * Names are allocated in large chunks to avoid calls to malloc
  46:  * and to cluster names in memory so that tracing hash chains
  47:  * doesn't cause many a page fault.
  48:  */
  49: 
  50: #define CHUNKSIZE 200
  51: 
  52: typedef struct Namepool {
  53:     struct Name name[CHUNKSIZE];
  54:     struct Namepool *prevpool;
  55: } *Namepool;
  56: 
  57: private Namepool namepool = nil;
  58: private Integer nleft = 0;
  59: 
  60: /*
  61:  * Given an identifier, convert it to a name.
  62:  * If it's not in the hash table, then put it there.
  63:  *
  64:  * The second argument specifies whether the string should be copied
  65:  * into newly allocated space if not found.
  66:  *
  67:  * Pardon my use of goto's, but it seemed more efficient and less convoluted
  68:  * than adding a collection of boolean variables.  This routine is time
  69:  * critical when starting up the debugger on large programs.
  70:  */
  71: 
  72: public Name identname(s, isallocated)
  73: String s;
  74: Boolean isallocated;
  75: {
  76:     register unsigned h;
  77:     register Char *p, *q;
  78:     register Name n;
  79:     register Integer len;
  80:     Namepool newpool;
  81: 
  82:     h = 0;
  83:     for (p = s; *p != '\0'; p++) {
  84:     h = (h << 1) ^ (*p);
  85:     }
  86:     h = h mod HASHTABLESIZE;
  87:     len = p - s;
  88:     n = nametable[h];
  89:     while (n != nil) {
  90:     p = s;
  91:     q = n->identifier;
  92:     for (;;) {
  93:         if (*p != *q) {
  94:         goto nomatch;
  95:         } else if (*p == '\0') {
  96:         goto match;
  97:         }
  98:         ++p;
  99:         ++q;
 100:     }
 101:     nomatch:
 102:     n = n->chain;
 103:     }
 104: 
 105:     /*
 106:      * Now we know that name hasn't been found (otherwise we'd have jumped
 107:      * down to match), 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:     bzero(newpool, sizeof(newpool));
 113:     newpool->prevpool = namepool;
 114:     namepool = newpool;
 115:     nleft = CHUNKSIZE;
 116:     }
 117:     --nleft;
 118:     n = &(namepool->name[nleft]);
 119:     if (isallocated) {
 120:     n->identifier = s;
 121:     } else {
 122:     n->identifier = newarr(char, len + 1);
 123:     p = s;
 124:     q = n->identifier;
 125:     while (*p != '\0') {
 126:         *q++ = *p++;
 127:     }
 128:     *q = '\0';
 129:     }
 130:     n->chain = nametable[h];
 131:     nametable[h] = n;
 132: 
 133:     /*
 134:      * The two possibilities (name known versus unknown) rejoin.
 135:      */
 136: match:
 137:     return n;
 138: }
 139: 
 140: /*
 141:  * Deallocate the name table.
 142:  */
 143: 
 144: public names_free()
 145: {
 146:     Namepool n, m;
 147:     register integer i;
 148: 
 149:     n = namepool;
 150:     while (n != nil) {
 151:     m = n->prevpool;
 152:     dispose(n);
 153:     n = m;
 154:     }
 155:     for (i = 0; i < HASHTABLESIZE; i++) {
 156:     nametable[i] = nil;
 157:     }
 158:     namepool = nil;
 159:     nleft = 0;
 160: }

Defined functions

Defined variables

Defined struct's

Defined typedef's

Defined macros