Return to names.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / pgrm / dbx

Annotation of 43BSDReno/pgrm/dbx/names.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1983 The Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * Redistribution and use in source and binary forms are permitted
        !             6:  * provided that: (1) source distributions retain this entire copyright
        !             7:  * notice and comment, and (2) distributions including binaries display
        !             8:  * the following acknowledgement:  ``This product includes software
        !             9:  * developed by the University of California, Berkeley and its contributors''
        !            10:  * in the documentation or other materials provided with the distribution
        !            11:  * and in all advertising materials mentioning features or use of this
        !            12:  * software. Neither the name of the University nor the names of its
        !            13:  * contributors may be used to endorse or promote products derived
        !            14:  * from this software without specific prior written permission.
        !            15:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            16:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            17:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            18:  */
        !            19: 
        !            20: #ifndef lint
        !            21: static char sccsid[] = "@(#)names.c    5.4 (Berkeley) 6/1/90";
        !            22: #endif /* not lint */
        !            23: 
        !            24: /*
        !            25:  * Name are the internal representation for identifiers.
        !            26:  *
        !            27:  * A hash table is used to map identifiers to names.
        !            28:  */
        !            29: 
        !            30: #include "defs.h"
        !            31: #include "names.h"
        !            32: 
        !            33: #ifndef public
        !            34: typedef struct Name *Name;
        !            35: 
        !            36: /*
        !            37:  * Inline (for speed) function to return the identifier (string)
        !            38:  * associated with a name.  Because C cannot support both inlines
        !            39:  * and data hiding at the same time, the Name structure must be
        !            40:  * publicly visible.  It is not used explicitly, however, outside of this file.
        !            41:  */
        !            42: 
        !            43: struct Name {
        !            44:     char *identifier;
        !            45:     Name chain;
        !            46: };
        !            47: 
        !            48: #define ident(n) ((n == nil) ? "(noname)" : n->identifier)
        !            49: #endif
        !            50: 
        !            51: /*
        !            52:  * The hash table is a power of two, in order to make hashing faster.
        !            53:  * Using a non-prime is ok since we use chaining instead of re-hashing.
        !            54:  */
        !            55: 
        !            56: #define HASHTABLESIZE 8192
        !            57: 
        !            58: private Name nametable[HASHTABLESIZE];
        !            59: 
        !            60: /*
        !            61:  * Names are allocated in large chunks to avoid calls to malloc
        !            62:  * and to cluster names in memory so that tracing hash chains
        !            63:  * doesn't cause many a page fault.
        !            64:  */
        !            65: 
        !            66: #define CHUNKSIZE 1000
        !            67: 
        !            68: typedef struct Namepool {
        !            69:     struct Name name[CHUNKSIZE];
        !            70:     struct Namepool *prevpool;
        !            71: } *Namepool;
        !            72: 
        !            73: private Namepool namepool = nil;
        !            74: private Integer nleft = 0;
        !            75: 
        !            76: /*
        !            77:  * Given an identifier, convert it to a name.
        !            78:  * If it's not in the hash table, then put it there.
        !            79:  *
        !            80:  * The second argument specifies whether the string should be copied
        !            81:  * into newly allocated space if not found.
        !            82:  *
        !            83:  * This routine is time critical when starting up the debugger
        !            84:  * on large programs.
        !            85:  */
        !            86: 
        !            87: public Name identname(s, isallocated)
        !            88: String s;
        !            89: Boolean isallocated;
        !            90: {
        !            91:     register unsigned h;
        !            92:     register char *p, *q;
        !            93:     register Name n, *np;
        !            94:     Namepool newpool;
        !            95: 
        !            96:     h = 0;
        !            97:     for (p = s; *p != '\0'; p++) {
        !            98:        h = (h << 1) ^ (*p);
        !            99:     }
        !           100:     h &= (HASHTABLESIZE-1);
        !           101:     np = &nametable[h];
        !           102:     n = *np;
        !           103:     while (n != nil) {
        !           104:        p = s;
        !           105:        q = n->identifier;
        !           106:        while (*p == *q) {
        !           107:            if (*p == '\0') {
        !           108:                return n;
        !           109:            }
        !           110:            ++p;
        !           111:            ++q;
        !           112:        }
        !           113:        n = n->chain;
        !           114:     }
        !           115: 
        !           116:     /*
        !           117:      * Now we know that name hasn't been found,
        !           118:      * so we allocate a name, store the identifier, and
        !           119:      * enter it in the hash table.
        !           120:      */
        !           121:     if (nleft <= 0) {
        !           122:        newpool = new(Namepool);
        !           123:        newpool->prevpool = namepool;
        !           124:        namepool = newpool;
        !           125:        nleft = CHUNKSIZE;
        !           126:     }
        !           127:     --nleft;
        !           128:     n = &(namepool->name[nleft]);
        !           129:     if (isallocated) {
        !           130:        n->identifier = s;
        !           131:     } else {
        !           132:        /* this case doesn't happen very often */
        !           133:        n->identifier = newarr(char, strlen(s) + 1);
        !           134:        p = s;
        !           135:        q = n->identifier;
        !           136:        while (*p != '\0') {
        !           137:            *q++ = *p++;
        !           138:        }
        !           139:        *q = '\0';
        !           140:     }
        !           141:     n->chain = *np;
        !           142:     *np = n;
        !           143:     return n;
        !           144: }
        !           145: 
        !           146: /*
        !           147:  * Deallocate the name table.
        !           148:  */
        !           149: 
        !           150: public names_free()
        !           151: {
        !           152:     Namepool n, m;
        !           153:     register integer i;
        !           154: 
        !           155:     n = namepool;
        !           156:     while (n != nil) {
        !           157:        m = n->prevpool;
        !           158:        dispose(n);
        !           159:        n = m;
        !           160:     }
        !           161:     for (i = 0; i < HASHTABLESIZE; i++) {
        !           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.