src/texsourc/libavl/libavl/unitTests/avl_test07.c

   1 /*
   2  *   Libavl is a library to manage AVL structure to store and organize
   3  *   everykind of data. You just need to implement function to compare,
   4  *   to desallocate and to print your structure.
   5  *
   6  *       DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   7  *                   Version 2, December 2004
   8  *
   9  *   Copyright (C) 2013 Adrien Oliva <adrien.oliva@yapbreak.fr>
  10  *
  11  *   Everyone is permitted to copy and distribute verbatim or modified
  12  *   copies of this license document, and changing it is allowed as long
  13  *   as the name is changed.
  14  *
  15  *           DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
  16  *   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
  17  *
  18  *   0. You just DO WHAT THE FUCK YOU WANT TO.
  19  */
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <time.h>
  24
  25 #include "../syslog.h"
  26 #include "../avl.h"
  27
  28 struct _tree_data {
  29     int key;
  30     int value;
  31 };
  32
  33 static int data_cmp(void *a, void *b)
  34 {
  35     struct _tree_data aa = *((struct _tree_data *) a);
  36     struct _tree_data bb = *((struct _tree_data *) b);
  37
  38     return aa.key - bb.key;
  39 }
  40
  41 static void data_print(void *d)
  42 {
  43     printf("%p|%d-%d", d,
  44             ((struct _tree_data *) d)->key, ((struct _tree_data *) d)->value);
  45 }
  46
  47 static void data_delete(void *d)
  48 {
  49     free(d);
  50 }
  51
  52 #define MAX_ELEMENT 10000
  53
  54 char *get_data_tests()
  55 {
  56     tree *first = NULL;
  57     struct _tree_data data[MAX_ELEMENT];
  58     struct _tree_data tmp_elmnt;
  59     struct _tree_data current_min;
  60     unsigned int result;
  61     unsigned int element_in_tree = 0;
  62     int i = 0;
  63     int j = 0;
  64
  65     unsigned long rand_seed = (unsigned long) time(NULL);
  66     ILOG("Random seed: %lu", rand_seed);
  67     srand(rand_seed);
  68
  69     for (i = 0; i < MAX_ELEMENT; i++) {
  70         data[i].key = rand();
  71         data[i].value = rand();
  72     }
  73
  74
  75     verif_tree(first);
  76
  77     // Try to allocate a new tree.
  78     first = init_dictionnary(data_cmp, data_print, data_delete, NULL);
  79     if (first == NULL) {
  80         ELOG("Init dictionnary error");
  81         return "Init dictionnary error";
  82     }
  83
  84     // Add data
  85     verif_tree(first);
  86     for (i = 0; i < MAX_ELEMENT; i++) {
  87         tmp_elmnt.key = data[i].key;
  88         if (!is_present(first, &(tmp_elmnt))) {
  89             element_in_tree++;
  90         }
  91         result = insert_elmt(first, &(data[i]), sizeof(struct _tree_data));
  92         if (result != element_in_tree) {
  93             ELOG("Wrong result of inserted element");
  94             return "Wrong result of inserted element";
  95         }
  96         verif_tree(first);
  97     }
  98
  99     current_min.key     = (int) 0x80000000;
 100     current_min.value   = (int) 0x80000000;
 101
 102     for (i = 0; i < MAX_ELEMENT && element_in_tree != 0; i++) {
 103         tmp_elmnt.key       = (int) 0x7fffffff;
 104         tmp_elmnt.value     = (int) 0x7fffffff;
 105         // Get minimum data
 106         for (j = 0; j < MAX_ELEMENT; j++) {
 107             if (    data[j].key < tmp_elmnt.key
 108                 &&  data[j].key > current_min.key) {
 109                 tmp_elmnt.key   = data[j].key;
 110                 tmp_elmnt.value = data[j].value;
 111             }
 112
 113         }
 114
 115         current_min.key     = tmp_elmnt.key;
 116         current_min.value   = tmp_elmnt.value;
 117
 118         if (!is_present(first, &tmp_elmnt)) {
 119             ELOG("Minimum data not in tree");
 120             return "Minimum data not in tree";
 121         }
 122         delete_node_min(first);
 123         if (is_present(first, &tmp_elmnt)) {
 124             ELOG("Minimum element deleted");
 125             return "Minimum element deleted";
 126         }
 127         element_in_tree--;
 128         verif_tree(first);
 129     }
 130
 131     // Try to delete it
 132     delete_tree(first);
 133
 134
 135
 136     return NULL;
 137 }