![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / contrib / mkmf / src|
Return to hash.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / mkmf / src |
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.