![[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 [The Machine Emulator] / tme / libtme|
Return to hash.c CVS log | Up to [The Machine Emulator] / tme / libtme |
1.1 root 1: /* $Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $ */
2:
3: /* libtme/hash.c - hash table support: */
4:
5: /*
6: * Copyright (c) 2003 Matt Fredette
7: * All rights reserved.
8: *
9: * Redistribution and use in source and binary forms, with or without
10: * modification, are permitted provided that the following conditions
11: * are met:
12: * 1. Redistributions of source code must retain the above copyright
13: * notice, this list of conditions and the following disclaimer.
14: * 2. Redistributions in binary form must reproduce the above copyright
15: * notice, this list of conditions and the following disclaimer in the
16: * documentation and/or other materials provided with the distribution.
17: * 3. All advertising materials mentioning features or use of this software
18: * must display the following acknowledgement:
19: * This product includes software developed by Matt Fredette.
20: * 4. The name of the author may not be used to endorse or promote products
21: * derived from this software without specific prior written permission.
22: *
23: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
24: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
25: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26: * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
27: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
29: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
31: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32: * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33: * POSSIBILITY OF SUCH DAMAGE.
34: */
35:
36: #include <tme/common.h>
37: _TME_RCSID("$Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $");
38:
39: /* includes: */
40: #include <tme/hash.h>
41:
42: /* our hash table size array: */
43: static unsigned long _tme_hash_sizes[] = {
44: 2,
45: 3,
46: 5,
47: 7,
48: 11,
49: 17,
50: 37,
51: 83,
52: 281,
53: 421,
54: 631,
55: 947,
56: 2131,
57: 7193,
58: 10789,
59: 16183,
60: 81929,
61: 414763,
62: 933217,
63: 10629917,
64: 35875969,
65: 80720929,
66: };
67:
68: /* this allocates and returns a new hash: */
69: tme_hash_t
70: tme_hash_new(tme_hash_func_t hash_func,
71: tme_compare_func_t compare_func,
72: tme_hash_data_t value_null)
73: {
74: tme_hash_t hash;
75:
76: hash = tme_new0(struct _tme_hash, 1);
77: hash->_tme_hash_size = _tme_hash_sizes[0];
78: hash->_tme_hash_table =
79: tme_new0(struct _tme_hash_bucket *,
80: hash->_tme_hash_size);
81: hash->_tme_hash_count = 0;
82: hash->_tme_hash_hash = hash_func;
83: hash->_tme_hash_compare = compare_func;
84: hash->_tme_hash_null = value_null;
85: return (hash);
86: }
87:
88: /* this destroys a hash: */
89: void
90: tme_hash_destroy(tme_hash_t hash)
91: {
92: struct _tme_hash_bucket *bucket, *bucket_next;
93: unsigned long bucket_i;
94:
95: /* free all of the buckets in the hash table: */
96: for (bucket_i = 0;
97: bucket_i < hash->_tme_hash_size;
98: bucket_i++) {
99: for (bucket = hash->_tme_hash_table[bucket_i];
100: bucket != NULL;
101: bucket = bucket_next) {
102: bucket_next = bucket->_tme_hash_bucket_next;
103: tme_free(bucket);
104: }
105: }
106: tme_free(hash->_tme_hash_table);
107: tme_free(hash);
108: }
109:
110: /* this does an internal lookup in a hash table: */
111: static struct _tme_hash_bucket *
112: _tme_hash_lookup_internal(tme_hash_t hash,
113: tme_hash_data_t key,
114: struct _tme_hash_bucket ***__bucket)
115: {
116: unsigned long bucket_i;
117: struct _tme_hash_bucket **_bucket, *bucket;
118:
119: /* hash the key: */
120: bucket_i = (*hash->_tme_hash_hash)(key) % hash->_tme_hash_size;
121:
122: /* walk the chain of buckets: */
123: for (_bucket = hash->_tme_hash_table + bucket_i;
124: (bucket = *_bucket) != NULL;
125: _bucket = &bucket->_tme_hash_bucket_next) {
126:
127: /* compare the key in this bucket with the lookup key.
128: if it succeeds, return the bucket: */
129: if ((*hash->_tme_hash_compare)(key, bucket->_tme_hash_bucket_key)) {
130: if (__bucket != NULL) {
131: *__bucket = _bucket;
132: }
133: return (bucket);
134: }
135: }
136:
137: /* the lookup failed. return where the bucket might be inserted: */
138: if (__bucket != NULL) {
139: *__bucket = _bucket;
140: }
141: return (NULL);
142: }
143:
144: /* this inserts a value into a hash table: */
145: void
146: tme_hash_insert(tme_hash_t hash,
147: tme_hash_data_t key,
148: tme_hash_data_t value)
149: {
150: struct _tme_hash_bucket *bucket, *bucket_next, **_bucket;
151: struct _tme_hash hash_new;
152: int size_i;
153: unsigned long bucket_i;
154:
155: /* if this key is not already present in the hash table: */
156: bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
157: if (bucket == NULL) {
158:
159: /* if we need to resize this hash table: */
160: if ((hash->_tme_hash_count * 2) > hash->_tme_hash_size) {
161:
162: /* make a copy of the top of the hash: */
163: hash_new = *hash;
164:
165: /* set the new size of the hash: */
166: hash_new._tme_hash_size = hash->_tme_hash_count * 2;
167: for (size_i = 0;
168: _tme_hash_sizes[size_i] < hash_new._tme_hash_size;
169: size_i++) {
170: if (size_i + 1 == TME_ARRAY_ELS(_tme_hash_sizes)) {
171: abort();
172: }
173: }
174: hash_new._tme_hash_size = _tme_hash_sizes[size_i];
175:
176: /* allocate the new hash table: */
177: hash_new._tme_hash_table =
178: tme_new0(struct _tme_hash_bucket *,
179: hash_new._tme_hash_size);
180:
181: /* move everything from the old hash table into the new: */
182: for (bucket_i = 0;
183: bucket_i < hash->_tme_hash_size;
184: bucket_i++) {
185: for (bucket = hash->_tme_hash_table[bucket_i];
186: bucket != NULL;
187: bucket = bucket_next) {
188: bucket_next = bucket->_tme_hash_bucket_next;
189: _tme_hash_lookup_internal(&hash_new,
190: bucket->_tme_hash_bucket_key,
191: &_bucket);
192: bucket->_tme_hash_bucket_next = *_bucket;
193: *_bucket = bucket;
194: }
195: }
196:
197: /* free the old hash table: */
198: tme_free(hash->_tme_hash_table);
199:
200: /* set the new top of the hash: */
201: *hash = hash_new;
202:
203: /* do the internal lookup again: */
204: _tme_hash_lookup_internal(hash, key, &_bucket);
205: }
206:
207: /* create the new bucket and link it in: */
208: bucket = tme_new(struct _tme_hash_bucket, 1);
209: bucket->_tme_hash_bucket_next = *_bucket;
210: *_bucket = bucket;
211:
212: /* increment the number of keys in the hash: */
213: hash->_tme_hash_count++;
214: }
215:
216: /* set the key and value in the bucket: */
217: bucket->_tme_hash_bucket_key = key;
218: bucket->_tme_hash_bucket_value = value;
219: }
220:
221: /* this looks up a key in the hash: */
222: tme_hash_data_t
223: tme_hash_lookup(tme_hash_t hash,
224: tme_hash_data_t key)
225: {
226: struct _tme_hash_bucket *bucket;
227:
228: bucket = _tme_hash_lookup_internal(hash, key, NULL);
229: return (bucket != NULL
230: ? bucket->_tme_hash_bucket_value
231: : hash->_tme_hash_null);
232: }
233:
234: /* this removes a key in the hash: */
235: void
236: tme_hash_remove(tme_hash_t hash,
237: tme_hash_data_t key)
238: {
239: struct _tme_hash_bucket *bucket, **_bucket;
240:
241: bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
242: if (bucket != NULL) {
243: *_bucket = bucket->_tme_hash_bucket_next;
244: tme_free(bucket);
245: hash->_tme_hash_count--;
246: }
247: }
248:
249: /* this calls a function for each key and value in the hash: */
250: void
251: tme_hash_foreach(tme_hash_t hash,
252: tme_foreach_func_t func,
253: void *private)
254: {
255: struct _tme_hash_bucket *bucket;
256: unsigned long bucket_i;
257:
258: /* walk all of the buckets in the hash table: */
259: for (bucket_i = 0;
260: bucket_i < hash->_tme_hash_size;
261: bucket_i++) {
262: for (bucket = hash->_tme_hash_table[bucket_i];
263: bucket != NULL;
264: bucket = bucket->_tme_hash_bucket_next) {
265: (*func)(bucket->_tme_hash_bucket_key,
266: bucket->_tme_hash_bucket_value,
267: private);
268: }
269: }
270: }
271:
272: /* this calls a function for each key and value in the hash.
273: if the function returns TRUE the entry is removed: */
274: unsigned long
275: tme_hash_foreach_remove(tme_hash_t hash,
276: tme_foreach_remove_func_t func,
277: void *private)
278: {
279: struct _tme_hash_bucket **_bucket, *bucket;
280: unsigned long bucket_i, count;
281:
282: /* walk all of the buckets in the hash table: */
283: count = 0;
284: for (bucket_i = 0;
285: bucket_i < hash->_tme_hash_size;
286: bucket_i++) {
287: for (_bucket = &hash->_tme_hash_table[bucket_i];
288: (bucket = *_bucket) != NULL; ) {
289: if ((*func)(bucket->_tme_hash_bucket_key,
290: bucket->_tme_hash_bucket_value,
291: private)) {
292: *_bucket = bucket->_tme_hash_bucket_next;
293: tme_free(bucket);
294: hash->_tme_hash_count--;
295: count++;
296: }
297: else {
298: _bucket = &bucket->_tme_hash_bucket_next;
299: }
300: }
301: }
302: return (count);
303: }
304:
305: /* this hashes a direct value: */
306: unsigned long
307: tme_direct_hash(tme_hash_data_t key)
308: {
309: return ((unsigned long) key);
310: }
311:
312: /* this compares two direct values: */
313: int
314: tme_direct_compare(tme_hash_data_t key0,
315: tme_hash_data_t key1)
316: {
317: return (key0 == key1);
318: }
319:
320: /* this hashes a string value: */
321: unsigned long
322: tme_string_hash(tme_hash_data_t key)
323: {
324: /* this is cribbed from the Dragon book: */
325: const char *p;
326: char c;
327: unsigned long h, g;
328:
329: p = (const char *) key;
330: h = 0;
331:
332: for (; (c = *(p++)) != '\0'; ) {
333: h = (h << 4) + c;
334: g = (h & 0xf0000000);
335: if (g) {
336: h = h ^ (g >> 24);
337: h = h ^ g;
338: }
339: }
340:
341: return (h);
342: }
343:
344: /* this compares two string values: */
345: int
346: tme_string_compare(tme_hash_data_t key0,
347: tme_hash_data_t key1)
348: {
349: return (!strcmp((const char *) key0, (const char *) key1));
350: }
351:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.