ctdb/tests/src/rb_test.c

   1 /*
   2    simple rb test tool
   3
   4    Copyright (C) Ronnie Sahlberg 2007
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "includes.h"
  21 #include "lib/util/dlinklist.h"
  22 #include "system/filesys.h"
  23 #include "popt.h"
  24 #include "cmdline.h"
  25
  26 #include <sys/time.h>
  27 #include <time.h>
  28 #include "common/rb_tree.h"
  29
  30 static struct timeval tp1,tp2;
  31
  32 static void start_timer(void)
  33 {
  34         gettimeofday(&tp1,NULL);
  35 }
  36
  37 static double end_timer(void)
  38 {
  39         gettimeofday(&tp2,NULL);
  40         return (tp2.tv_sec + (tp2.tv_usec*1.0e-6)) -
  41                 (tp1.tv_sec + (tp1.tv_usec*1.0e-6));
  42 }
  43
  44 int num_records=5;
  45
  46 static void *callback(void *p, void *d)
  47 {
  48         uint32_t *data = (uint32_t *)d;
  49
  50         if (d==NULL) {
  51                 data = (uint32_t *)p;
  52         }
  53
  54         (*data)++;
  55
  56         return data;
  57 }
  58
  59 static void *random_add(void *p, void *d)
  60 {
  61         return p;
  62 }
  63
  64 static int traverse(void *p, void *d)
  65 {
  66         uint32_t *data = (uint32_t *)d;
  67
  68         printf("traverse data:%d\n",*data);
  69         return 0;
  70 }
  71
  72 static int random_traverse(void *p, void *d)
  73 {
  74         printf("%s   ",(char *)d);
  75         return 0;
  76 }
  77
  78 static uint32_t calc_checksum = 0;
  79 static int traverse_checksum(void *p, void *d)
  80 {
  81         int i,j,k;
  82
  83         sscanf(d, "%d.%d.%d", &i, &j, &k);
  84         calc_checksum += i*100+j*10+k;
  85         return 0;
  86 }
  87
  88 static int count_traverse(void *p, void *d)
  89 {
  90         int *count = p;
  91         (*count)++;
  92         return 0;
  93 }
  94
  95 static int count_traverse_abort(void *p, void *d)
  96 {
  97         int *count = p;
  98         (*count)++;
  99         return -1;
 100 }
 101
 102 /*
 103   main program
 104 */
 105 int main(int argc, const char *argv[])
 106 {
 107         struct poptOption popt_options[] = {
 108                 POPT_AUTOHELP
 109                 POPT_CTDB_CMDLINE
 110                 { "num-records", 'r', POPT_ARG_INT, &num_records, 0, "num_records", "integer" },
 111                 POPT_TABLEEND
 112         };
 113         int opt, traverse_count;
 114         const char **extra_argv;
 115         int extra_argc = 0;
 116         poptContext pc;
 117         int i,j,k;
 118         trbt_tree_t *tree;
 119         uint32_t *data;
 120         uint32_t key[3];
 121         uint32_t key1[3] = {0,10,20};
 122         uint32_t key2[3] = {0,10,21};
 123         uint32_t key3[3] = {0,11,20};
 124         uint32_t key4[3] = {2,10,20};
 125         TALLOC_CTX *memctx;
 126         uint32_t **u32array;
 127         uint32_t checksum;
 128
 129         pc = poptGetContext(argv[0], argc, argv, popt_options, POPT_CONTEXT_KEEP_FIRST);
 130
 131         while ((opt = poptGetNextOpt(pc)) != -1) {
 132                 switch (opt) {
 133                 default:
 134                         fprintf(stderr, "Invalid option %s: %s\n",
 135                                 poptBadOption(pc, 0), poptStrerror(opt));
 136                         exit(1);
 137                 }
 138         }
 139
 140         /* setup the remaining options for the main program to use */
 141         extra_argv = poptGetArgs(pc);
 142         if (extra_argv) {
 143                 extra_argv++;
 144                 while (extra_argv[extra_argc]) extra_argc++;
 145         }
 146
 147         printf("testing trbt_insert32_callback for %d records\n", num_records);
 148         memctx   = talloc_new(NULL);
 149         u32array = talloc_array(memctx, uint32_t *, num_records);
 150         tree = trbt_create(memctx, 0);
 151         for (i=0; i<num_records; i++) {
 152                 u32array[i]  = talloc(u32array, uint32_t);
 153                 *u32array[i] = 0;
 154                 trbt_insert32_callback(tree, i, callback, u32array[i]);
 155         }
 156         for (i=3; i<num_records; i++) {
 157                 trbt_insert32_callback(tree, i, callback, NULL);
 158         }
 159
 160         printf("first 3 keys should have data==1\n");
 161         printf("the rest of the keys should have data==2\n");
 162         for (i=0; i<num_records; i++) {
 163                 data = trbt_lookup32(tree, i);
 164                 printf("key:%d data:%d\n", i, *data);
 165         }
 166 //      talloc_report_full(tree, stdout);
 167 //      talloc_report_full(memctx, stdout);
 168 //      print_tree(tree);
 169
 170         printf("deleting key 2\n");
 171         talloc_free(u32array[2]);
 172 //      talloc_report_full(tree, stdout);
 173 //      talloc_report_full(memctx, stdout);
 174 //      print_tree(tree);
 175
 176         printf("deleting key 1\n");
 177         talloc_free(u32array[1]);
 178 //      talloc_report_full(tree, stdout);
 179 //      talloc_report_full(memctx, stdout);
 180 //      print_tree(tree);
 181
 182         printf("freeing tree\n");
 183         talloc_report_full(memctx, stdout);
 184         talloc_free(memctx);
 185
 186
 187         printf("testing trbt_insertarray32_callback\n");
 188         memctx   = talloc_new(NULL);
 189         tree = trbt_create(memctx, 0);
 190         u32array = talloc_array(memctx, uint32_t *, 4);
 191         for (i=0;i<4;i++) {
 192                 u32array[i]  = talloc(u32array, uint32_t);
 193                 *u32array[i] = 0;
 194         }
 195         trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
 196         trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
 197         trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
 198         trbt_insertarray32_callback(tree, 3, key3, callback, u32array[2]);
 199         trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
 200         trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
 201
 202         data = trbt_lookuparray32(tree, 3, key1);
 203         printf("key1 dataptr:%p == %d\n",data,data?*data:-1);
 204         data = trbt_lookuparray32(tree, 3, key2);
 205         printf("key2 dataptr:%p == %d\n",data,data?*data:-1);
 206         data = trbt_lookuparray32(tree, 3, key3);
 207         printf("key3 dataptr:%p == %d\n",data,data?*data:-1);
 208         data = trbt_lookuparray32(tree, 3, key4);
 209         printf("key4 dataptr:%p == %d\n",data,data?*data:-1);
 210         trbt_traversearray32(tree, 3, traverse, NULL);
 211
 212         printf("\ndeleting key4\n");
 213         talloc_free(trbt_lookuparray32(tree, 3, key4));
 214         data = trbt_lookuparray32(tree, 3, key1);
 215         printf("key1 dataptr:%p == %d\n",data,data?*data:-1);
 216         data = trbt_lookuparray32(tree, 3, key2);
 217         printf("key2 dataptr:%p == %d\n",data,data?*data:-1);
 218         data = trbt_lookuparray32(tree, 3, key3);
 219         printf("key3 dataptr:%p == %d\n",data,data?*data:-1);
 220         data = trbt_lookuparray32(tree, 3, key4);
 221         printf("key4 dataptr:%p == %d\n",data,data?*data:-1);
 222         trbt_traversearray32(tree, 3, traverse, NULL);
 223
 224         printf("\ndeleting key2\n");
 225         talloc_free(trbt_lookuparray32(tree, 3, key2));
 226         data = trbt_lookuparray32(tree, 3, key1);
 227         printf("key1 dataptr:%p == %d\n",data,data?*data:-1);
 228         data = trbt_lookuparray32(tree, 3, key2);
 229         printf("key2 dataptr:%p == %d\n",data,data?*data:-1);
 230         data = trbt_lookuparray32(tree, 3, key3);
 231         printf("key3 dataptr:%p == %d\n",data,data?*data:-1);
 232         data = trbt_lookuparray32(tree, 3, key4);
 233         printf("key4 dataptr:%p == %d\n",data,data?*data:-1);
 234         trbt_traversearray32(tree, 3, traverse, NULL);
 235
 236         printf("\ndeleting key3\n");
 237         talloc_free(trbt_lookuparray32(tree, 3, key3));
 238         data = trbt_lookuparray32(tree, 3, key1);
 239         printf("key1 dataptr:%p == %d\n",data,data?*data:-1);
 240         data = trbt_lookuparray32(tree, 3, key2);
 241         printf("key2 dataptr:%p == %d\n",data,data?*data:-1);
 242         data = trbt_lookuparray32(tree, 3, key3);
 243         printf("key3 dataptr:%p == %d\n",data,data?*data:-1);
 244         data = trbt_lookuparray32(tree, 3, key4);
 245         printf("key4 dataptr:%p == %d\n",data,data?*data:-1);
 246         trbt_traversearray32(tree, 3, traverse, NULL);
 247
 248         printf("\ndeleting key1\n");
 249         talloc_free(trbt_lookuparray32(tree, 3, key1));
 250         data = trbt_lookuparray32(tree, 3, key1);
 251         printf("key1 dataptr:%p == %d\n",data,data?*data:-1);
 252         data = trbt_lookuparray32(tree, 3, key2);
 253         printf("key2 dataptr:%p == %d\n",data,data?*data:-1);
 254         data = trbt_lookuparray32(tree, 3, key3);
 255         printf("key3 dataptr:%p == %d\n",data,data?*data:-1);
 256         data = trbt_lookuparray32(tree, 3, key4);
 257         printf("key4 dataptr:%p == %d\n",data,data?*data:-1);
 258         trbt_traversearray32(tree, 3, traverse, NULL);
 259
 260         talloc_free(tree);
 261         talloc_free(memctx);
 262
 263
 264         printf("\nrun random insert and delete for 60 seconds\n");
 265         memctx   = talloc_new(NULL);
 266         tree = trbt_create(memctx, 0);
 267         i=0;
 268         start_timer();
 269         checksum = 0;
 270         /* add and delete nodes from a 3 level tree fro 60 seconds.
 271            each time a node is added or deleted, traverse the tree and
 272            compute a checksum over the data stored in the tree and compare this
 273            with a checksum we keep which contains what the checksum should be
 274          */
 275         while(end_timer() < 60.0){
 276                 char *str;
 277
 278                 i++;
 279                 key[0]=random()%10;
 280                 key[1]=random()%10;
 281                 key[2]=random()%10;
 282                 if (random()%2) {
 283                         if (trbt_lookuparray32(tree, 3, key) == NULL) {
 284                                 /* this node does not yet exist, add it to the
 285                                    tree and update the checksum
 286                                  */
 287                                 str=talloc_asprintf(memctx, "%d.%d.%d", key[0],key[1],key[2]);
 288                                 trbt_insertarray32_callback(tree, 3, key, random_add, str);
 289                                 checksum += key[0]*100+key[1]*10+key[2];
 290                         }
 291                 } else {
 292                         if ((str=trbt_lookuparray32(tree, 3, key)) != NULL) {
 293                                 /* this node does exist in  the tree, delete
 294                                    it and update the checksum accordingly
 295                                  */
 296                                 talloc_free(str);
 297                                 checksum -= key[0]*100+key[1]*10+key[2];
 298                         }
 299                 }
 300                 /* traverse all nodes in the tree and calculate the checksum
 301                    it better match the one we keep track of in
 302                    'checksum'
 303                 */
 304                 calc_checksum = 0;
 305                 trbt_traversearray32(tree, 3, traverse_checksum, NULL);
 306                 if(checksum != calc_checksum) {
 307                         printf("Wrong checksum  %d!=%d\n",checksum, calc_checksum);
 308                         exit(10);
 309                 }
 310
 311                 if(i%1000==999)printf(".");fflush(stdout);
 312         }
 313         printf("\niterations passed:%d\n", i);
 314         trbt_traversearray32(tree, 3, random_traverse, NULL);
 315         printf("\n");
 316         printf("first node: %s\n", (char *)trbt_findfirstarray32(tree, 3));
 317
 318         traverse_count = 0;
 319         trbt_traversearray32(tree, 3, count_traverse, &traverse_count);
 320         printf("\n");
 321         printf("number of entries in traverse %d\n", traverse_count);
 322
 323         traverse_count = 0;
 324         trbt_traversearray32(tree, 3, count_traverse_abort, &traverse_count);
 325         printf("\n");
 326         printf("number of entries in aborted traverse %d\n", traverse_count);
 327         if (traverse_count != 1) {
 328                 printf("Failed to abort the traverse. Should have been aborted after 1 element but did iterate over %d elements\n", traverse_count);
 329                 exit(10);
 330         }
 331         printf("\ndeleting all entries\n");
 332         for(i=0;i<10;i++){
 333         for(j=0;j<10;j++){
 334         for(k=0;k<10;k++){
 335                 key[0]=i;
 336                 key[1]=j;
 337                 key[2]=k;
 338                 talloc_free(trbt_lookuparray32(tree, 3, key));
 339         }
 340         }
 341         }
 342         trbt_traversearray32(tree, 3, random_traverse, NULL);
 343         printf("\n");
 344         talloc_report_full(tree, stdout);
 345
 346         return 0;
 347 }