test/tests2.4/hash.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <string.h>
   5 #include <math.h>
   6 #include <time.h>
   7 #include "hash.h"
   8
   9 static int isprime(int number);
  10 static int nextprime(int number);
  11
  12 static void hashexpand(hashtable *table);
  13
  14 static unsigned chrhash(void *s, int M);
  15 static int chrcomp(void *s1, void *s2);
  16 static void * chrdupe(void *key);
  17
  18 static unsigned inthash(void *s, int M);
  19 static int intcomp(void *s1, void *s2);
  20 static void * intdupe(void *i);
  21
  22
  23 void
  24 hashcreate(hashtable *table, keytype typ, int size)
  25 {
  26         table->size=nextprime(size);
  27         table->numkeys=0;
  28
  29         if (typ == CHAR) {
  30                 table->hashfunc=chrhash;
  31                 table->compfunc=chrcomp;
  32                 table->dupefunc=chrdupe;
  33         }
  34         else { /* INT */
  35                 table->hashfunc=inthash;
  36                 table->compfunc=intcomp;
  37                 table->dupefunc=intdupe;
  38         }
  39
  40         assert((table->table=(calloc(table->size, sizeof(bucket *)))) != NULL);
  41 }
  42
  43 void
  44 hashinsert(hashtable *table, void *key, void *val)
  45 {
  46         unsigned h=table->hashfunc(key, table->size);
  47         bucket *p;
  48
  49         assert((p=(bucket *)malloc(sizeof(bucket))) != NULL);
  50         assert((p->key=table->dupefunc(key)) != NULL);
  51         p->val=val;
  52
  53         for (; (table->table)[h] != NULL; h=(h+1)%table->size)
  54                 ;
  55
  56         (table->table)[h]=p;
  57
  58         if (table->numkeys++ > table->size/2)
  59                 hashexpand(table);
  60 }
  61
  62 void *
  63 hashfind(hashtable *table, void *key)
  64 {
  65         register unsigned h=table->hashfunc(key, table->size);
  66
  67         for (; (table->table)[h] != NULL; h=(h+1)%table->size)
  68                 if (table->compfunc((table->table)[h]->key, key) == 0)
  69                         return (table->table)[h]->val;
  70
  71         return NULL;
  72 }
  73
  74 void
  75 hashdelete(hashtable *table, void *key)
  76 {
  77         register unsigned h=table->hashfunc(key, table->size);
  78
  79         for (; (table->table)[h] != NULL; h=(h+1)%table->size) {
  80                 if (table->compfunc((table->table)[h]->key, key) == 0) {
  81                         free((table->table)[h]->key);
  82                         free((table->table)[h]->val);
  83                         (table->table)[h]->key=(table->table)[h]->val=NULL;
  84                         free((table->table)[h]);
  85                         (table->table)[h]=NULL;
  86                 }
  87         }
  88 }
  89
  90 void
  91 hashforeach(hashtable *table, void (*func)(void *, void *))
  92 {
  93         int l;
  94
  95         for (l=0; l<table->size; l++)
  96                 if ((table->table)[l] != NULL)
  97                         func((table->table)[l]->key, (table->table)[l]->val);
  98 }
  99
 100 void
 101 hashempty(hashtable *table)
 102 {
 103         int l;
 104
 105         for (l=0; l<table->size; l++) {
 106                 if ((table->table)[l] != NULL) {
 107                         free((table->table)[l]->key);
 108                         free((table->table)[l]->val);
 109                         free((table->table)[l]);
 110                         (table->table)[l]=NULL;
 111                 }
 112         }
 113
 114         table->numkeys=0;
 115 }
 116
 117 static void
 118 hashexpand(hashtable *table)
 119 {
 120         int size, l;
 121         bucket **t;
 122         unsigned h;
 123
 124         size=nextprime(table->size*2);
 125
 126         assert((t=(calloc(size, sizeof(bucket *)))) != NULL);
 127
 128         for (l=0; l<table->size; l++) {
 129                 if ((table->table)[l] != NULL) {
 130                         h=table->hashfunc((table->table)[l]->key, size);
 131
 132                         for (; t[h] != NULL; h=(h+1)%size)
 133                                 ;
 134
 135                         t[h]=(table->table)[l];
 136                 }
 137         }
 138
 139         free(table->table);
 140
 141         table->size=size;
 142         table->table=t;
 143 }
 144
 145 static int
 146 nextprime(int number)
 147 {
 148         for (;!isprime(number);number++)
 149                 ;
 150
 151         return number;
 152 }
 153
 154 static int
 155 isprime(int number)
 156 {
 157         int sqr, l;
 158
 159         sqr=sqrt(number);
 160
 161         for (l=2;l<=sqr;l++)
 162                 if (number%l == 0)
 163                         return 0;
 164
 165         return 1;
 166 }
 167
 168 static unsigned
 169 chrhash(void *p, int M)
 170 {
 171         register unsigned hashval;
 172         register char *s=p;
 173
 174         for (hashval=0; *s!='\0'; s++)
 175                 hashval=*s+31*hashval;
 176
 177         return hashval%M;
 178 }
 179
 180 static int
 181 chrcomp(void *s1, void *s2)
 182 {
 183         return strcmp((char *)s1, (char *)s2);
 184 }
 185
 186 static void *
 187 chrdupe(void *key)
 188 {
 189         return (void *)strdup((char *)key);
 190 }
 191
 192 static unsigned
 193 inthash(void *i, int M)
 194 {
 195         return *(int *)i%M;
 196 }
 197
 198 static int
 199 intcomp(void *i1, void *i2)
 200 {
 201         return *(int *)i1-*(int *)i2;
 202 }
 203
 204 static void *
 205 intdupe(void *i)
 206 {
 207         int *p;
 208
 209
 210         assert((p=(int *)malloc(sizeof(int))) != NULL);
 211
 212         *p=*(int *)i;
 213
 214         return p;
 215 }
 216
 217
 218
 219
 220
 221
 222