hash.h

   1 /* $Id: hash.h,v 1.6 2003/09/24 18:48:59 ukai Exp $ */
   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 */