4.3BSD - /usr/src/new/mkmf/src/hash.c

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

Defined functions