c_cpp/lib/klib/test/kbtree_test.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <time.h>
   4 #include <stdlib.h>
   5 #include <stdint.h>
   6 #include <string.h>
   7
   8 typedef const char *str_t;
   9
  10 #include "kbtree.h"
  11 KBTREE_INIT(int, uint32_t, kb_generic_cmp)
  12 KBTREE_INIT(str, str_t, kb_str_cmp)
  13
  14 static int data_size = 5000000;
  15 static unsigned *int_data;
  16 static char **str_data;
  17
  18 void ht_init_data()
  19 {
  20         int i;
  21         char buf[256];
  22         printf("--- generating data... ");
  23         srand48(11);
  24         int_data = (unsigned*)calloc(data_size, sizeof(unsigned));
  25         str_data = (char**)calloc(data_size, sizeof(char*));
  26         for (i = 0; i < data_size; ++i) {
  27                 int_data[i] = (unsigned)(data_size * drand48() / 4) * 271828183u;
  28                 sprintf(buf, "%x", int_data[i]);
  29                 str_data[i] = strdup(buf);
  30         }
  31         printf("done!\n");
  32 }
  33 void ht_destroy_data()
  34 {
  35         int i;
  36         for (i = 0; i < data_size; ++i) free(str_data[i]);
  37         free(str_data); free(int_data);
  38 }
  39
  40 void ht_khash_int()
  41 {
  42         int i;
  43         unsigned *data = int_data;
  44         uint32_t *l, *u;
  45         kbtree_t(int) *h;
  46
  47         h = kb_init(int, KB_DEFAULT_SIZE);
  48         for (i = 0; i < data_size; ++i) {
  49                 if (kb_get(int, h, data[i]) == 0) kb_put(int, h, data[i]);
  50                 else kb_del(int, h, data[i]);
  51         }
  52         printf("[ht_khash_int] size: %d\n", kb_size(h));
  53         if (1) {
  54                 int cnt = 0;
  55                 uint32_t x, y;
  56                 kb_interval(int, h, 2174625464u, &l, &u);
  57                 printf("interval for 2174625464: (%u, %u)\n", l? *l : 0, u? *u : 0);
  58 #define traverse_f(p) { if (cnt == 0) y = *p; ++cnt; }
  59                 __kb_traverse(uint32_t, h, traverse_f);
  60                 __kb_get_first(uint32_t, h, x);
  61                 printf("# of elements from traversal: %d\n", cnt);
  62                 printf("first element: %d == %d\n", x, y);
  63         }
  64         __kb_destroy(h);
  65 }
  66 void ht_khash_str()
  67 {
  68         int i;
  69         char **data = str_data;
  70         kbtree_t(str) *h;
  71
  72         h = kb_init(str, KB_DEFAULT_SIZE);
  73         for (i = 0; i < data_size; ++i) {
  74                 if (kb_get(str, h, data[i]) == 0) kb_put(str, h, data[i]);
  75                 else kb_del(str, h, data[i]);
  76         }
  77         printf("[ht_khash_int] size: %d\n", kb_size(h));
  78         __kb_destroy(h);
  79 }
  80 void ht_timing(void (*f)(void))
  81 {
  82         clock_t t = clock();
  83         (*f)();
  84         printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC);
  85 }
  86 int main(int argc, char *argv[])
  87 {
  88         if (argc > 1) data_size = atoi(argv[1]);
  89         ht_init_data();
  90         ht_timing(ht_khash_int);
  91         ht_timing(ht_khash_str);
  92         ht_destroy_data();
  93         return 0;
  94 }