c_cpp/lib/klib/test/kavl_test.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <stdint.h>
   4 #include <string.h>
   5 #include "kavl.h"
   6
   7 #define CALLOC(type, num) ((type*)calloc(num, sizeof(type)))
   8
   9 struct my_node {
  10         int key;
  11         KAVL_HEAD(struct my_node) head;
  12 };
  13
  14 #define my_cmp(p, q) (((p)->key > (q)->key) - ((p)->key < (q)->key))
  15 KAVL_INIT(my, struct my_node, head, my_cmp)
  16
  17 int check(struct my_node *p, int *hh)
  18 {
  19         int c = 1, h[2] = {0, 0};
  20         *hh = 0;
  21         if (p) {
  22                 if (p->head.p[0]) c += check(p->head.p[0], &h[0]);
  23                 if (p->head.p[1]) c += check(p->head.p[1], &h[1]);
  24                 *hh = (h[0] > h[1]? h[0] : h[1]) + 1;
  25                 if (h[1] - h[0] != (int)p->head.balance)
  26                         fprintf(stderr, "%d - %d != %d at %c\n", h[1], h[0], p->head.balance, p->key);
  27                 if (c != (int)p->head.size)
  28                         fprintf(stderr, "%d != %d at %c\n", p->head.size, c, p->key);
  29                 return c;
  30         } else return 0;
  31 }
  32 /*
  33 int print_tree(const struct my_node *p)
  34 {
  35         int c = 1;
  36         if (p == 0) return 0;
  37         if (p->head.p[0] || p->head.p[1]) {
  38                 putchar('(');
  39                 if (p->head.p[0]) c += print_tree(p->head.p[0]);
  40                 else putchar('.');
  41                 putchar(',');
  42                 if (p->head.p[1]) c += print_tree(p->head.p[1]);
  43                 else putchar('.');
  44                 putchar(')');
  45         }
  46         putchar(p->key);
  47         return c;
  48 }
  49
  50 void check_and_print(struct my_node *root)
  51 {
  52         int h;
  53         check(root, &h);
  54         print_tree(root);
  55         putchar('\n');
  56 }
  57 */
  58 void shuffle(int n, char a[])
  59 {
  60         int i, j;
  61         for (i = n; i > 1; --i) {
  62                 char tmp;
  63                 j = (int)(drand48() * i);
  64                 tmp = a[j]; a[j] = a[i-1]; a[i-1] = tmp;
  65         }
  66 }
  67
  68 int main(void)
  69 {
  70         char buf[256];
  71         int i, n, h;
  72         struct my_node *root = 0;
  73         struct my_node *p, *q, t;
  74         kavl_itr_t(my) itr;
  75         unsigned cnt;
  76
  77         for (i = 33, n = 0; i <= 126; ++i)
  78                 if (i != '(' && i != ')' && i != '.' && i != ';')
  79                         buf[n++] = i;
  80         shuffle(n, buf);
  81         for (i = 0; i < n; ++i) {
  82                 p = CALLOC(struct my_node, 1);
  83                 p->key = buf[i];
  84                 q = kavl_insert(my, &root, p, &cnt);
  85                 if (p != q) free(p);
  86                 check(root, &h);
  87         }
  88         shuffle(n, buf);
  89         for (i = 0; i < n/2; ++i) {
  90                 t.key = buf[i];
  91                 q = kavl_erase(my, &root, &t, 0);
  92                 if (q) free(q);
  93                 check(root, &h);
  94         }
  95
  96         kavl_itr_first(my, root, &itr);
  97         do {
  98                 const struct my_node *r = kavl_at(&itr);
  99                 putchar(r->key);
 100                 free((void*)r);
 101         } while (kavl_itr_next(my, &itr));
 102         putchar('\n');
 103         return 0;
 104 }