hash.h (3012B)
1 /* $Id$ */ 2 #ifndef HASH_H 3 #define HASH_H 4 5 /* hash table */ 6 7 #define defhash(keytype,type,sym) \ 8 typedef struct HashItem_##sym { \ 9 keytype key; \ 10 type value; \ 11 struct HashItem_##sym *next; \ 12 } HashItem_##sym; \ 13 typedef struct Hash_##sym { \ 14 int size; \ 15 struct HashItem_##sym **tab; \ 16 } Hash_##sym; \ 17 extern Hash_##sym *newHash_##sym(int size); \ 18 extern void putHash_##sym(Hash_##sym *t, keytype key, type value); \ 19 extern type getHash_##sym(Hash_##sym *t, keytype key, type failval); 20 21 defhash(char *, int, si) 22 defhash(char *, char *, ss) 23 defhash(char *, void *, sv) 24 defhash(int, void *, iv) 25 #define defhashfunc(keytype,type,sym) \ 26 Hash_##sym * \ 27 newHash_##sym(int size)\ 28 {\ 29 struct Hash_##sym *hash;\ 30 int i;\ 31 \ 32 hash = (Hash_##sym*)GC_malloc(sizeof(Hash_##sym));\ 33 hash->size = size;\ 34 hash->tab = (HashItem_##sym**)GC_malloc(size*sizeof(HashItem_##sym*));\ 35 for (i = 0; i < size; i++)\ 36 hash->tab[i] = NULL;\ 37 return hash;\ 38 }\ 39 \ 40 static HashItem_##sym* \ 41 lookupHash_##sym(Hash_##sym *t, keytype key, int *hashval_return)\ 42 {\ 43 HashItem_##sym *hi;\ 44 \ 45 *hashval_return = hashfunc(key)%t->size;\ 46 for (hi = t->tab[*hashval_return]; hi != NULL; hi = hi->next) {\ 47 if (keycomp(hi->key,key))\ 48 return hi;\ 49 }\ 50 return NULL;\ 51 }\ 52 \ 53 void \ 54 putHash_##sym(Hash_##sym *t, keytype key, type value)\ 55 {\ 56 int h;\ 57 HashItem_##sym *hi;\ 58 \ 59 hi = lookupHash_##sym(t,key,&h);\ 60 if (hi) {\ 61 hi->value = value;\ 62 return;\ 63 }\ 64 \ 65 hi = (HashItem_##sym*)GC_malloc(sizeof(HashItem_##sym));\ 66 hi->key = key;\ 67 hi->value = value;\ 68 hi->next = t->tab[h];\ 69 t->tab[h] = hi;\ 70 }\ 71 \ 72 type \ 73 getHash_##sym(Hash_##sym *t, keytype key, type failval)\ 74 {\ 75 int h;\ 76 HashItem_##sym *hi;\ 77 \ 78 hi = lookupHash_##sym(t,key,&h);\ 79 if (hi == NULL)\ 80 return failval;\ 81 return hi->value;\ 82 } 83 #define defhashfunc_i(keytype,type,sym) \ 84 Hash_##sym * \ 85 newHash_##sym(int size)\ 86 {\ 87 struct Hash_##sym *hash;\ 88 int i;\ 89 \ 90 hash = (Hash_##sym*)GC_malloc(sizeof(Hash_##sym));\ 91 hash->size = size;\ 92 hash->tab = (HashItem_##sym**)GC_malloc(size*sizeof(HashItem_##sym*));\ 93 for (i = 0; i < size; i++)\ 94 hash->tab[i] = NULL;\ 95 return hash;\ 96 }\ 97 \ 98 static HashItem_##sym* \ 99 lookupHash_##sym(Hash_##sym *t, keytype key, int *hashval_return)\ 100 {\ 101 HashItem_##sym *hi;\ 102 \ 103 *hashval_return = key%t->size;\ 104 for (hi = t->tab[*hashval_return]; hi != NULL; hi = hi->next) {\ 105 if (hi->key == key)\ 106 return hi;\ 107 }\ 108 return NULL;\ 109 }\ 110 \ 111 void \ 112 putHash_##sym(Hash_##sym *t, keytype key, type value)\ 113 {\ 114 int h;\ 115 HashItem_##sym *hi;\ 116 \ 117 hi = lookupHash_##sym(t,key,&h);\ 118 if (hi) {\ 119 hi->value = value;\ 120 return;\ 121 }\ 122 \ 123 hi = (HashItem_##sym*)GC_malloc(sizeof(HashItem_##sym));\ 124 hi->key = key;\ 125 hi->value = value;\ 126 hi->next = t->tab[h];\ 127 t->tab[h] = hi;\ 128 }\ 129 \ 130 type \ 131 getHash_##sym(Hash_##sym *t, keytype key, type failval)\ 132 {\ 133 int h;\ 134 HashItem_##sym *hi;\ 135 \ 136 hi = lookupHash_##sym(t,key,&h);\ 137 if (hi == NULL)\ 138 return failval;\ 139 return hi->value;\ 140 } 141 #endif /* not HASH_H */