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