Return to names.c CVS log

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

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

1.1       root        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: }

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