Return to hash.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / mkmf / src

Annotation of 43BSD/contrib/mkmf/src/hash.c, revision 1.1

1.1     ! root        1: /* $Header: hash.c,v 1.1 85/03/14 15:38:16 nicklin Exp $ */
        !             2: 
        !             3: /*
        !             4:  * Author: Peter J. Nicklin
        !             5:  */
        !             6: #include "null.h"
        !             7: #include "hash.h"
        !             8: #include "macro.h"
        !             9: 
        !            10: /*
        !            11:  * hthash() returns a hash value for string, s.
        !            12:  */
        !            13: hthash(s, hash)
        !            14:        register char *s;               /* string */
        !            15:        HASH *hash;                     /* hash table */
        !            16: {
        !            17:        register int hashval;           /* hash value for string */
        !            18: 
        !            19:        for (hashval = 0; *s != '\0'; s++)
        !            20:                hashval += *s;
        !            21:        return(hashval % hash->hashsiz);
        !            22: }
        !            23: 
        !            24: 
        !            25: 
        !            26: /*
        !            27:  * htinit() returns a pointer to a new hash table, or a null pointer if
        !            28:  * out of memory.
        !            29:  */
        !            30: HASH *
        !            31: htinit(hashsiz)
        !            32:        unsigned int hashsiz;           /* hash table size */
        !            33: {
        !            34:        char *malloc();                 /* allocate memory */
        !            35:        char *calloc();                 /* allocate and zero memory */
        !            36:        HASH *ht;                       /* pointer to hash table struct */
        !            37:        HASHBLK **pt;                   /* pointer to hash pointer table */
        !            38: 
        !            39:        if ((ht = (HASH *) malloc(sizeof(HASH))) == NULL ||
        !            40:            (pt = (HASHBLK **) calloc(hashsiz, sizeof(HASHBLK *))) == NULL)
        !            41:                {
        !            42:                warn("out of memory");
        !            43:                return(NULL);
        !            44:                }
        !            45:        ht->hashtab = pt;
        !            46:        ht->hashsiz = hashsiz;
        !            47:        return(ht);
        !            48: }
        !            49: 
        !            50: 
        !            51: 
        !            52: /*
        !            53:  * htinstall() installs a new entry in a hash table if it doesn't already
        !            54:  * exist. If it does, the old definition and value is superseded. Returns
        !            55:  * a pointer to the entry, or null if out of memory.
        !            56:  */
        !            57: HASHBLK *
        !            58: htinstall(key, def, val, hash)
        !            59:        char *key;                      /* key for hash table entry */
        !            60:        char *def;                      /* definition string */
        !            61:        int val;                        /* integer value */
        !            62:        HASH *hash;                     /* hash table */
        !            63: {
        !            64:        char *malloc();                 /* memory allocator */
        !            65:        char *strsav();                 /* save string somewhere */
        !            66:        HASHBLK *htb;                   /* hash table entry block */
        !            67:        HASHBLK *htlookup();            /* find hash table entry */
        !            68:        int hashval;                    /* hash value for key */
        !            69:        int hthash();                   /* calculate hash value */
        !            70: 
        !            71:        if ((htb = htlookup(key, hash)) == NULL)
        !            72:                {                       /* not found */
        !            73:                if ((htb = (HASHBLK *) malloc(sizeof(HASHBLK))) == NULL)
        !            74:                        return(NULL);
        !            75:                if ((htb->h_key = strsav(key)) == NULL)
        !            76:                        return(NULL);
        !            77:                hashval = hthash(key, hash);
        !            78:                htb->h_next = (hash->hashtab)[hashval];
        !            79:                (hash->hashtab)[hashval] = htb;
        !            80:                htb->h_sub = NULL;
        !            81:                htb->h_tag = NULL;
        !            82:                }
        !            83:        else    {                       /* found */
        !            84:                free(htb->h_def);       /* free previous definition */
        !            85:                }
        !            86:        if ((htb->h_def = strsav(def)) == NULL)
        !            87:                return(NULL);
        !            88:        htb->h_val = val;
        !            89:        return(htb);
        !            90: }
        !            91: 
        !            92: 
        !            93: 
        !            94: /*
        !            95:  * htlookup() returns a pointer to a hash table entry if found, otherwise null.
        !            96:  */
        !            97: HASHBLK *
        !            98: htlookup(key, hash)
        !            99:        char *key;                      /* key for hash table entry */
        !           100:        HASH *hash;                     /* hash table */
        !           101: {
        !           102:        HASHBLK *htb;                   /* hash table entry block */
        !           103:        int hthash();                   /* calculate hash value */
        !           104: 
        !           105:        for (htb = (hash->hashtab)[hthash(key, hash)]; htb != NULL; htb = htb->h_next)
        !           106:                if (EQUAL(htb->h_key, key))
        !           107:                        return(htb);    /* found */
        !           108:        return(NULL);                   /* not found */
        !           109: }
        !           110: 
        !           111: 
        !           112: 
        !           113: /*
        !           114:  * htrm() removes a hash table entry. If key is null, the entire hash
        !           115:  * table is removed.
        !           116:  */
        !           117: void
        !           118: htrm(key, hash)
        !           119:        char *key;                      /* key for hash table entry */
        !           120:        HASH *hash;                     /* hash table */
        !           121: {
        !           122:        HASHBLK *htbrm();               /* remove hash table block */
        !           123:        HASHBLK *htc;                   /* first hash table block in chain */
        !           124:        int hashval;                    /* hash value for key */
        !           125:        int hthash();                   /* compute hash value */
        !           126:        int i;                          /* hash table index */
        !           127: 
        !           128:        if (key == NULL)
        !           129:                {
        !           130:                for (i = 0; i < hash->hashsiz; i++)
        !           131:                        if ((htc = (hash->hashtab)[i]) != NULL)
        !           132:                                htc = htbrm(key, htc);
        !           133:                free((char *) hash);
        !           134:                }
        !           135:        else    {
        !           136:                hashval = hthash(key, hash);
        !           137:                if ((htc = (hash->hashtab)[hashval]) != NULL)
        !           138:                        (hash->hashtab)[hashval] = htbrm(key, htc);
        !           139:                }
        !           140: }
        !           141: 
        !           142: 
        !           143: 
        !           144: /*
        !           145:  * htbrm() removes a hash table block identified by key. If key is null, the
        !           146:  * entire chain is removed. Returns a pointer to the first block in the chain.
        !           147:  */
        !           148: HASHBLK *
        !           149: htbrm(key, htc)
        !           150:        char *key;                      /* key string */
        !           151:        HASHBLK *htc;                   /* hash table block chain */
        !           152: {
        !           153:        HASHBLK *curblk;                /* current list block */
        !           154:        HASHBLK *nxtblk;                /* next list block */
        !           155:        HASHBLK *prvblk;                /* previous list block */
        !           156: 
        !           157:        if (key == NULL)
        !           158:                while (htc != NULL)
        !           159:                        {
        !           160:                        nxtblk = htc->h_next;
        !           161:                        free(htc->h_key);
        !           162:                        free(htc->h_def);
        !           163:                        free((char *) htc);
        !           164:                        htc = nxtblk;
        !           165:                        }
        !           166:        else    {
        !           167:                /* first block is a special case */
        !           168:                if (EQUAL(htc->h_key, key))
        !           169:                        {
        !           170:                        nxtblk = htc->h_next;
        !           171:                        free(htc->h_key);
        !           172:                        free(htc->h_def);
        !           173:                        free((char *) htc);
        !           174:                        htc = nxtblk;
        !           175:                        }
        !           176:                else    {
        !           177:                        /* remainder of list */
        !           178:                        prvblk = htc;
        !           179:                        curblk = htc->h_next;
        !           180:                        while (curblk != NULL)
        !           181:                                if (EQUAL(curblk->h_key, key))
        !           182:                                        {
        !           183:                                        prvblk->h_next = curblk->h_next;
        !           184:                                        free(curblk->h_key);
        !           185:                                        free(curblk->h_def);
        !           186:                                        free((char *) curblk);
        !           187:                                        curblk = prvblk->h_next;
        !           188:                                        break;
        !           189:                                        }
        !           190:                                else    {
        !           191:                                        prvblk = curblk;
        !           192:                                        curblk = curblk->h_next;
        !           193:                                        }
        !           194:                        }
        !           195:                }
        !           196:        return(htc);
        !           197: }

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