ulut/ul_hashtabchk.c

   1 #include <string.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <limits.h>
   5 #ifndef SDCC
   6 #include <sys/time.h>
   7 #endif
   8
   9 #include "ul_utmalloc.h"
  10 #include "ul_hashtab.h"
  11 #include "ul_hashtabcust.h"
  12
  13 typedef int ul_randser_int_t;
  14
  15 #define UL_HASHTAB_WITH_HASHVAL
  16
  17 typedef struct cust3_item {
  18   int my_val;
  19  #ifndef UL_HASHTAB_WITH_HASHVAL
  20   ul_hashtab_node_t my_node;
  21  #else /*UL_HASHTAB_WITH_HASHCACHE*/
  22   ul_hashtab_node_hashval_t my_node;
  23  #endif /*UL_HASHTAB_WITH_HASHCACHE*/
  24   int more_data;
  25 } cust3_item_t;
  26
  27 typedef struct cust3_table {
  28   ul_hashtab_cust_table_field_t my_table;
  29   int my_info;
  30   int my_first_val;
  31   int my_last_val;
  32 } cust3_table_t;
  33
  34 typedef int cust3_key_t;
  35
  36 UL_HASTAB_CUST_NODE_INT_DEC(cust3, cust3_table_t, cust3_item_t, cust3_key_t,
  37         my_table, my_node, my_val, cust3_cmp_fnc)
  38
  39 inline int
  40 cust3_cmp_fnc(const cust3_key_t *a, const cust3_key_t *b)
  41 {
  42   if (*a>*b) return 1;
  43   if (*a<*b) return -1;
  44   return 0;
  45 }
  46
  47 inline ul_hashtab_hashval_t
  48 cust3_hash_fnc(const cust3_key_t *a)
  49 {
  50   return *a;
  51 }
  52
  53 inline ul_hashtab_hashval_t
  54 cust3_hash_get_fnc(const cust3_item_t *item)
  55 {
  56  #ifdef UL_HASHTAB_WITH_HASHVAL
  57   return item->my_node.hashval;
  58  #else /*UL_HASHTAB_WITH_HASHCACHE*/
  59   return cust3_hash_fnc(&item->my_val);
  60  #endif /*UL_HASHTAB_WITH_HASHCACHE*/
  61 }
  62
  63 inline void
  64 cust_hash_prep_fnc(cust3_item_t *item)
  65 {
  66  #ifdef UL_HASHTAB_WITH_HASHVAL
  67   item->my_node.hashval=cust3_hash_fnc(&item->my_val);
  68  #endif /*UL_HASHTAB_WITH_HASHCACHE*/
  69 }
  70
  71 UL_HASTAB_CUST_NODE_INT_IMP(cust3, cust3_table_t, cust3_item_t, cust3_key_t,
  72         my_table, my_node, my_val, cust3_cmp_fnc, cust3_hash_fnc,
  73         cust3_hash_get_fnc, cust_hash_prep_fnc, 0, 0)
  74
  75
  76 cust3_table_t cust3_table;
  77
  78 ul_randser_int_t *ul_randser_generate(ul_randser_int_t len)
  79 {
  80   ul_randser_int_t *ser;
  81   ul_randser_int_t i;
  82
  83   ser=malloc(sizeof(*ser)*len);
  84   if(ser==NULL)
  85     return NULL;
  86
  87   for(i=0; i<len; i++) {
  88     ser[i]=i;
  89   }
  90
  91   for(i=len; i--; ) {
  92     ul_randser_int_t t, k;
  93     k=rand();
  94     k=(unsigned long long)k*i/RAND_MAX;
  95     t=ser[k];
  96     ser[k]=ser[i];
  97     ser[i]=t;
  98   }
  99
 100   return ser;
 101 }
 102
 103 void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
 104 {
 105   long sec, usec;
 106   sec=stop->tv_sec-start->tv_sec;
 107   usec=stop->tv_usec-start->tv_usec;
 108   if(usec>=1000000) {
 109     usec-=1000000;
 110     sec++;
 111   }
 112   if(usec<0) {
 113     usec+=1000000;
 114     sec--;
 115   }
 116   printf("%s :\t%4ld.%06ld\n",s,sec,usec);
 117 }
 118
 119 int main(int argc, char *argv[])
 120 {
 121   cust3_table_t *table=&cust3_table;
 122   cust3_item_t *item;
 123   cust3_key_t k;
 124   cust3_it_t it;
 125   int count=100000;
 126   int tablepow=12;
 127   cust3_item_t **item_arr;
 128   struct timeval time_start, time_stop;
 129   int i, j;
 130   int res;
 131   ul_randser_int_t *ser1, *ser2;
 132
 133   cust3_init_table_field(table);
 134
 135   if(argc>=2) {
 136     count=atol(argv[1]);
 137   }
 138   if(argc>=3) {
 139     tablepow=atol(argv[2]);
 140   }
 141
 142   cust3_resize_table(table, 1<<tablepow);
 143
 144   ser1=ul_randser_generate(count);
 145   if(ser1==NULL)
 146     return 1;
 147
 148   ser2=ul_randser_generate(count);
 149   if(ser2==NULL)
 150     return 1;
 151
 152   item_arr=malloc(sizeof(*item_arr)*count);
 153   if(!item_arr)
 154     return 1;
 155
 156   for(i=0; i<count; i++) {
 157     item=malloc(sizeof(*item));
 158     item->my_val=ser1[i];
 159     item_arr[i]=item;
 160   }
 161
 162   gettimeofday(&time_start,NULL);
 163   for(i=0; i<count; i++) {
 164     res=cust3_insert(table, item_arr[i]);
 165     if(res<=0) {
 166       printf("cust3_insert %d returned %d\n", i, res);
 167     }
 168   }
 169   gettimeofday(&time_stop,NULL);
 170   timing_test_print(&time_start,&time_stop,"HASHTAB random insert");
 171
 172   gettimeofday(&time_start,NULL);
 173   for(j=0; j<10; j++) {
 174     for(i=0; i<count; i++) {
 175       k=ser2[i];
 176       item=cust3_find(table, &k);
 177       if(item==NULL) {
 178         printf("cust3_find %d failed to found item\n", k);
 179       }
 180     }
 181   }
 182   gettimeofday(&time_stop,NULL);
 183   timing_test_print(&time_start,&time_stop,"HASHTAB random find 10x");
 184
 185  #if 0
 186   for(k=10; (k<count) && (k<20); k++) {
 187     item=cust3_find(table, &k);
 188     if(item==NULL) {
 189       printf("cust3_find %d failed to found item in loop 2\n", k);
 190       continue;
 191     }
 192     if(cust3_delete(table, item)<0)
 193       printf("cust3_delete failed to found item %d\n", item->my_val);
 194     else
 195       free(item);
 196   }
 197
 198   for(k=20; k<count; k++) {
 199     item=cust3_delete_key(table, &k);
 200     if(item==NULL)
 201       printf("cust3_delete_key failed to found key %d\n", k);
 202     else
 203       free(item);
 204   }
 205  #endif
 206
 207   gettimeofday(&time_start,NULL);
 208   for(j=0; j<10; j++) {
 209     i=0;
 210     ul_for_each_it(cust3, table, it){
 211       item=cust3_it2item(&it);
 212       if(item) {
 213         i++;
 214       } else {
 215         printf("ul_for_each_it error\n");
 216       }
 217     }
 218     if(i!=table->my_table.count)
 219       printf("ul_for_each_it skipped some items\n");
 220   }
 221   gettimeofday(&time_stop,NULL);
 222   timing_test_print(&time_start,&time_stop,"HASHTAB for each by iterator 10x");
 223
 224   gettimeofday(&time_start,NULL);
 225   for(cust3_first_it(table,&it); !cust3_is_end_it(&it); ) {
 226     item=cust3_it2item(&it);
 227     cust3_delete_it(&it);
 228     free(item);
 229   }
 230   gettimeofday(&time_stop,NULL);
 231   timing_test_print(&time_start,&time_stop,"HASHTAB delete rest by iterator");
 232
 233   cust3_delete_all(table);
 234
 235   free(ser1);
 236   free(ser2);
 237   free(item_arr);
 238
 239   return 0;
 240 }