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     ! 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.