Return to names.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ucb / dbx

Annotation of 42BSD/ucb/dbx/names.c, revision 1.1.1.1

1.1       root        1: /* Copyright (c) 1982 Regents of the University of California */
                      2: 
                      3: static char sccsid[] = "@(#)names.c 1.3 2/16/83";
                      4: 
                      5: /*
                      6:  * Name are the internal representation for identifiers.
                      7:  *
                      8:  * A hash table is used to map identifiers to names.
                      9:  */
                     10: 
                     11: #include "defs.h"
                     12: #include "names.h"
                     13: 
                     14: #ifndef public
                     15: typedef struct Name *Name;
                     16: 
                     17: /*
                     18:  * Inline (for speed) function to return the identifier (string)
                     19:  * associated with a name.  Because C cannot support both inlines
                     20:  * and data hiding at the same time, the Name structure must be
                     21:  * publicly visible.  It is not used explicitly, however, outside of this file.
                     22:  */
                     23: 
                     24: struct Name {
                     25:     char *identifier;
                     26:     Name chain;
                     27: };
                     28: 
                     29: #define ident(n) ((n == nil) ? "(noname)" : n->identifier)
                     30: #endif
                     31: 
                     32: #define HASHTABLESIZE 2997
                     33: 
                     34: private Name nametable[HASHTABLESIZE];
                     35: 
                     36: /*
                     37:  * Names are allocated in large chunks to avoid calls to malloc
                     38:  * and to cluster names in memory so that tracing hash chains
                     39:  * doesn't cause many a page fault.
                     40:  */
                     41: 
                     42: #define CHUNKSIZE 200
                     43: 
                     44: typedef struct Namepool {
                     45:     struct Name name[CHUNKSIZE];
                     46:     struct Namepool *prevpool;
                     47: } *Namepool;
                     48: 
                     49: private Namepool namepool = nil;
                     50: private Integer nleft = 0;
                     51: 
                     52: /*
                     53:  * Given an identifier, convert it to a name.
                     54:  * If it's not in the hash table, then put it there.
                     55:  *
                     56:  * The second argument specifies whether the string should be copied
                     57:  * into newly allocated space if not found.
                     58:  *
                     59:  * Pardon my use of goto's, but it seemed more efficient and less convoluted
                     60:  * than adding a collection of boolean variables.  This routine is time
                     61:  * critical when starting up the debugger on large programs.
                     62:  */
                     63: 
                     64: public Name identname(s, isallocated)
                     65: String s;
                     66: Boolean isallocated;
                     67: {
                     68:     register unsigned h;
                     69:     register Char *p, *q;
                     70:     register Name n;
                     71:     register Integer len;
                     72:     Namepool newpool;
                     73: 
                     74:     h = 0;
                     75:     for (p = s; *p != '\0'; p++) {
                     76:        h = (h << 1) ^ (*p);
                     77:     }
                     78:     h = h mod HASHTABLESIZE;
                     79:     len = p - s;
                     80:     n = nametable[h];
                     81:     while (n != nil) {
                     82:        p = s;
                     83:        q = n->identifier;
                     84:        for (;;) {
                     85:            if (*p != *q) {
                     86:                goto nomatch;
                     87:            } else if (*p == '\0') {
                     88:                goto match;
                     89:            }
                     90:            ++p;
                     91:            ++q;
                     92:        }
                     93:     nomatch:
                     94:        n = n->chain;
                     95:     }
                     96: 
                     97:     /*
                     98:      * Now we know that name hasn't been found (otherwise we'd have jumped
                     99:      * down to match), so we allocate a name, store the identifier, and
                    100:      * enter it in the hash table.
                    101:      */
                    102:     if (nleft <= 0) {
                    103:        newpool = new(Namepool);
                    104:        bzero(newpool, sizeof(newpool));
                    105:        newpool->prevpool = namepool;
                    106:        namepool = newpool;
                    107:        nleft = CHUNKSIZE;
                    108:     }
                    109:     --nleft;
                    110:     n = &(namepool->name[nleft]);
                    111:     if (isallocated) {
                    112:        n->identifier = s;
                    113:     } else {
                    114:        n->identifier = newarr(char, len + 1);
                    115:        p = s;
                    116:        q = n->identifier;
                    117:        while (*p != '\0') {
                    118:            *q++ = *p++;
                    119:        }
                    120:        *q = '\0';
                    121:     }
                    122:     n->chain = nametable[h];
                    123:     nametable[h] = n;
                    124: 
                    125:     /*
                    126:      * The two possibilities (name known versus unknown) rejoin.
                    127:      */
                    128: match:
                    129:     return n;
                    130: }
                    131: 
                    132: /*
                    133:  * Return the identifier associated with a name.
                    134:  *
                    135:  * Currently compiled inline.
                    136:  *
                    137:  *
                    138:  * public String ident(n)
                    139: Name n;
                    140: {
                    141:     return (n == nil) ? "(noname)" : n->identifier;
                    142: }
                    143:  *
                    144:  */
                    145: 
                    146: /*
                    147:  * Deallocate the name table.
                    148:  */
                    149: 
                    150: public names_free()
                    151: {
                    152:     register int i;
                    153:     register Name n, next;
                    154: 
                    155:     for (i = 0; i < HASHTABLESIZE; i++) {
                    156:        n = nametable[i];
                    157:        while (n != nil) {
                    158:            next = n->chain;
                    159:            dispose(n);
                    160:            n = next;
                    161:        }
                    162:        nametable[i] = nil;
                    163:     }
                    164:     namepool = nil;
                    165:     nleft = 0;
                    166: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.