c_cpp/lib/klib/test/khash_test.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <time.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "khash.h"
   8 KHASH_SET_INIT_STR(str)
   9 KHASH_MAP_INIT_INT(int, unsigned char)
  10
  11 typedef struct {
  12         unsigned key;
  13         unsigned char val;
  14 } int_unpack_t;
  15
  16 typedef struct {
  17         unsigned key;
  18         unsigned char val;
  19 } __attribute__ ((__packed__)) int_packed_t;
  20
  21 #define hash_eq(a, b) ((a).key == (b).key)
  22 #define hash_func(a) ((a).key)
  23
  24 KHASH_INIT(iun, int_unpack_t, char, 0, hash_func, hash_eq)
  25 KHASH_INIT(ipk, int_packed_t, char, 0, hash_func, hash_eq)
  26
  27 static int data_size = 5000000;
  28 static unsigned *int_data;
  29 static char **str_data;
  30
  31 void ht_init_data()
  32 {
  33         int i;
  34         char buf[256];
  35         khint32_t x = 11;
  36         printf("--- generating data... ");
  37         int_data = (unsigned*)calloc(data_size, sizeof(unsigned));
  38         str_data = (char**)calloc(data_size, sizeof(char*));
  39         for (i = 0; i < data_size; ++i) {
  40                 int_data[i] = (unsigned)(data_size * ((double)x / UINT_MAX) / 4) * 271828183u;
  41                 sprintf(buf, "%x", int_data[i]);
  42                 str_data[i] = strdup(buf);
  43                 x = 1664525L * x + 1013904223L;
  44         }
  45         printf("done!\n");
  46 }
  47
  48 void ht_destroy_data()
  49 {
  50         int i;
  51         for (i = 0; i < data_size; ++i) free(str_data[i]);
  52         free(str_data); free(int_data);
  53 }
  54
  55 void ht_khash_int()
  56 {
  57         int i, ret;
  58         unsigned *data = int_data;
  59         khash_t(int) *h;
  60         unsigned k;
  61
  62         h = kh_init(int);
  63         for (i = 0; i < data_size; ++i) {
  64                 k = kh_put(int, h, data[i], &ret);
  65                 kh_val(h, k) = i&0xff;
  66                 if (!ret) kh_del(int, h, k);
  67         }
  68         printf("[ht_khash_int] size: %u\n", kh_size(h));
  69         kh_destroy(int, h);
  70 }
  71
  72 void ht_khash_str()
  73 {
  74         int i, ret;
  75         char **data = str_data;
  76         khash_t(str) *h;
  77         unsigned k;
  78
  79         h = kh_init(str);
  80         for (i = 0; i < data_size; ++i) {
  81                 k = kh_put(str, h, data[i], &ret);
  82                 if (!ret) kh_del(str, h, k);
  83         }
  84         printf("[ht_khash_int] size: %u\n", kh_size(h));
  85         kh_destroy(str, h);
  86 }
  87
  88 void ht_khash_unpack()
  89 {
  90         int i, ret;
  91         unsigned *data = int_data;
  92         khash_t(iun) *h;
  93         unsigned k;
  94
  95         h = kh_init(iun);
  96         for (i = 0; i < data_size; ++i) {
  97                 int_unpack_t x;
  98                 x.key = data[i]; x.val = i&0xff;
  99                 k = kh_put(iun, h, x, &ret);
 100                 if (!ret) kh_del(iun, h, k);
 101         }
 102         printf("[ht_khash_unpack] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_unpack_t));
 103         kh_destroy(iun, h);
 104 }
 105
 106 void ht_khash_packed()
 107 {
 108         int i, ret;
 109         unsigned *data = int_data;
 110         khash_t(ipk) *h;
 111         unsigned k;
 112
 113         h = kh_init(ipk);
 114         for (i = 0; i < data_size; ++i) {
 115                 int_packed_t x;
 116                 x.key = data[i]; x.val = i&0xff;
 117                 k = kh_put(ipk, h, x, &ret);
 118                 if (!ret) kh_del(ipk, h, k);
 119         }
 120         printf("[ht_khash_packed] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_packed_t));
 121         kh_destroy(ipk, h);
 122 }
 123
 124 void ht_timing(void (*f)(void))
 125 {
 126         clock_t t = clock();
 127         (*f)();
 128         printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC);
 129 }
 130
 131 int main(int argc, char *argv[])
 132 {
 133         if (argc > 1) data_size = atoi(argv[1]);
 134         ht_init_data();
 135         ht_timing(ht_khash_int);
 136         ht_timing(ht_khash_str);
 137         ht_timing(ht_khash_unpack);
 138         ht_timing(ht_khash_packed);
 139         ht_destroy_data();
 140         return 0;
 141 }