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, ul_hashtab_sizestep_global)
  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     ul_hashtab_sizestep_global=ul_hashtab_sizestep_null;
 141   }
 142
 143   cust3_resize_table(table, 1<<tablepow);
 144
 145   ser1=ul_randser_generate(count);
 146   if(ser1==NULL)
 147     return 1;
 148
 149   ser2=ul_randser_generate(count);
 150   if(ser2==NULL)
 151     return 1;
 152
 153   item_arr=malloc(sizeof(*item_arr)*count);
 154   if(!item_arr)
 155     return 1;
 156
 157   for(i=0; i<count; i++) {
 158     item=malloc(sizeof(*item));
 159     item->my_val=ser1[i];
 160     item_arr[i]=item;
 161   }
 162
 163   gettimeofday(&time_start,NULL);
 164   for(i=0; i<count; i++) {
 165     res=cust3_insert(table, item_arr[i]);
 166     if(res<=0) {
 167       printf("cust3_insert %d returned %d\n", i, res);
 168     }
 169   }
 170   gettimeofday(&time_stop,NULL);
 171   timing_test_print(&time_start,&time_stop,"HASHTAB random insert");
 172
 173   gettimeofday(&time_start,NULL);
 174   for(j=0; j<10; j++) {
 175     for(i=0; i<count; i++) {
 176       k=ser2[i];
 177       item=cust3_find(table, &k);
 178       if(item==NULL) {
 179         printf("cust3_find %d failed to found item\n", k);
 180       }
 181     }
 182   }
 183   gettimeofday(&time_stop,NULL);
 184   timing_test_print(&time_start,&time_stop,"HASHTAB random find 10x");
 185
 186  #if 0
 187   for(k=10; (k<count) && (k<20); k++) {
 188     item=cust3_find(table, &k);
 189     if(item==NULL) {
 190       printf("cust3_find %d failed to found item in loop 2\n", k);
 191       continue;
 192     }
 193     if(cust3_delete(table, item)<0)
 194       printf("cust3_delete failed to found item %d\n", item->my_val);
 195     else
 196       free(item);
 197   }
 198
 199   for(k=20; k<count; k++) {
 200     item=cust3_delete_key(table, &k);
 201     if(item==NULL)
 202       printf("cust3_delete_key failed to found key %d\n", k);
 203     else
 204       free(item);
 205   }
 206  #endif
 207
 208   gettimeofday(&time_start,NULL);
 209   for(j=0; j<10; j++) {
 210     i=0;
 211     ul_for_each_it(cust3, table, it){
 212       item=cust3_it2item(&it);
 213       if(item) {
 214         i++;
 215       } else {
 216         printf("ul_for_each_it error\n");
 217       }
 218     }
 219     if(i!=table->my_table.count)
 220       printf("ul_for_each_it skipped some items\n");
 221   }
 222   gettimeofday(&time_stop,NULL);
 223   timing_test_print(&time_start,&time_stop,"HASHTAB for each by iterator 10x");
 224
 225   gettimeofday(&time_start,NULL);
 226   for(cust3_first_it(table,&it); !cust3_is_end_it(&it); ) {
 227     item=cust3_it2item(&it);
 228     cust3_delete_it(&it);
 229     free(item);
 230   }
 231   gettimeofday(&time_stop,NULL);
 232   timing_test_print(&time_start,&time_stop,"HASHTAB delete rest by iterator");
 233
 234   cust3_delete_all(table);
 235
 236   free(ser1);
 237   free(ser2);
 238   free(item_arr);
 239
 240   return 0;
 241 }