isamb/tstisamb.c

   1 /* $Id: tstisamb.c,v 1.26 2006-12-07 21:13:56 adam Exp $
   2    Copyright (C) 1995-2006
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23 #if HAVE_SYS_TIMES_H
  24 #include <sys/times.h>
  25 #endif
  26 #if HAVE_SYS_TIME_H
  27 #include <sys/time.h>
  28 #endif
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <yaz/log.h>
  33 #include <yaz/xmalloc.h>
  34 #include <idzebra/isamb.h>
  35 #include <assert.h>
  36
  37 static void log_item(int level, const void *b, const char *txt)
  38 {
  39     int x;
  40     memcpy(&x, b, sizeof(int));
  41     yaz_log(YLOG_DEBUG, "%s %d", txt, x);
  42 }
  43
  44 static void log_pr(const char *txt)
  45 {
  46     yaz_log(YLOG_DEBUG, "%s", txt);
  47 }
  48
  49 int compare_item(const void *a, const void *b)
  50 {
  51     int ia, ib;
  52
  53     memcpy(&ia, a, sizeof(int));
  54     memcpy(&ib, b, sizeof(int));
  55     if (ia > ib)
  56         return 1;
  57     if (ia < ib)
  58         return -1;
  59    return 0;
  60 }
  61
  62 void *code_start(void)
  63 {
  64     return 0;
  65 }
  66
  67 void code_item(void *p, char **dst, const char **src)
  68 {
  69     memcpy (*dst, *src, sizeof(int));
  70     (*dst) += sizeof(int);
  71     (*src) += sizeof(int);
  72 }
  73
  74 void code_reset(void *p)
  75 {
  76 }
  77 void code_stop(void *p)
  78 {
  79 }
  80
  81 struct read_info {
  82     int val;
  83     int step;
  84
  85     int no;
  86     int max;
  87     int insertMode;
  88 };
  89
  90 int code_read(void *vp, char **dst, int *insertMode)
  91 {
  92     struct read_info *ri = (struct read_info *)vp;
  93     int x;
  94
  95     if (ri->no >= ri->max)
  96         return 0;
  97     ri->no++;
  98
  99     x = ri->val;
 100     memcpy (*dst, &x, sizeof(int));
 101     (*dst)+=sizeof(int);
 102
 103     ri->val = ri->val + ri->step;
 104     *insertMode = ri->insertMode;
 105
 106 #if 0
 107     yaz_log(YLOG_LOG, "%d %5d", ri->insertMode, x);
 108 #endif
 109     return 1;
 110 }
 111
 112 void bench_insert(ISAMB isb, int number_of_trees,
 113                 int number_of_rounds, int number_of_elements)
 114 {
 115     ISAMC_I isamc_i;
 116     ISAM_P *isamc_p = xmalloc(sizeof(ISAM_P) * number_of_trees);
 117     struct read_info ri;
 118     int round, i;
 119
 120     for (i = 0; i<number_of_trees; i++)
 121         isamc_p[i] = 0; /* initially, is empty */
 122
 123     ri.val = 0;
 124     ri.step = 1;
 125     ri.insertMode = 1;
 126
 127     for (round = 0; round < number_of_rounds; round++)
 128     {
 129 #if HAVE_SYS_TIMES_H
 130 #if HAVE_SYS_TIME_H
 131         struct tms tms1, tms2;
 132         struct timeval start_time, end_time;
 133         double usec;
 134         times(&tms1);
 135         gettimeofday(&start_time, 0);
 136 #endif
 137 #endif
 138         for (i = 0; i<number_of_trees; i++)
 139         {
 140
 141             /* insert a number of entries */
 142             ri.no = 0;
 143
 144             ri.val = (rand());
 145             ri.max = number_of_elements;
 146
 147             isamc_i.clientData = &ri;
 148             isamc_i.read_item = code_read;
 149
 150
 151             isamb_merge (isb, &isamc_p[i] , &isamc_i);
 152         }
 153 #if HAVE_SYS_TIMES_H
 154 #if HAVE_SYS_TIME_H
 155         gettimeofday(&end_time, 0);
 156         times(&tms2);
 157
 158         usec = (end_time.tv_sec - start_time.tv_sec) * 1000000.0 +
 159             end_time.tv_usec - start_time.tv_usec;
 160
 161         yaz_log (YLOG_LOG, "round=%d times: %5.4f %5.2f %5.2f",
 162                  round,
 163                  usec / 1000000,
 164                  (double) (tms2.tms_utime - tms1.tms_utime)/100,
 165                  (double) (tms2.tms_stime - tms1.tms_stime)/100);
 166 #endif
 167 #endif
 168     }
 169 }
 170
 171 void tst_insert(ISAMB isb, int n)
 172 {
 173     ISAMC_I isamc_i;
 174     ISAM_P isamc_p;
 175     struct read_info ri;
 176     ISAMB_PP pp;
 177     char key_buf[20];
 178     int nerrs = 0;
 179
 180     /* insert a number of entries */
 181     ri.no = 0;
 182     ri.max = n;
 183
 184     ri.val = 0;
 185     ri.step = 1;
 186     ri.insertMode = 1;
 187
 188     isamc_i.clientData = &ri;
 189     isamc_i.read_item = code_read;
 190
 191     isamc_p = 0; /* new list */
 192     isamb_merge (isb, &isamc_p , &isamc_i);
 193
 194     /* read the entries */
 195     pp = isamb_pp_open (isb, isamc_p, 1);
 196
 197     ri.val = 0;
 198     while(isamb_pp_read (pp, key_buf))
 199     {
 200         int x;
 201         memcpy (&x, key_buf, sizeof(int));
 202         if (x != ri.val)
 203         {
 204             yaz_log(YLOG_WARN, "isamb_pp_read. n=%d Got %d (expected %d)",
 205                     n, x, ri.val);
 206             nerrs++;
 207         }
 208         else if (nerrs)
 209             yaz_log(YLOG_LOG, "isamb_pp_read. n=%d Got %d",
 210                     n, x);
 211
 212         ri.val++;
 213     }
 214     if (ri.val != ri.max)
 215     {
 216         yaz_log(YLOG_WARN, "ri.max != ri.max (%d != %d)", ri.val, ri.max);
 217         nerrs++;
 218     }
 219     isamb_dump(isb, isamc_p, log_pr);
 220     isamb_pp_close(pp);
 221
 222     if (nerrs)
 223         exit(3);
 224     /* delete a number of entries (even ones) */
 225     ri.no = 0;
 226     ri.max = n - n/2;
 227
 228     ri.val = 0;
 229     ri.step = 2;
 230     ri.insertMode = 0;
 231
 232     isamc_i.clientData = &ri;
 233     isamc_i.read_item = code_read;
 234
 235     isamb_merge (isb, &isamc_p , &isamc_i);
 236
 237     /* delete a number of entries (odd ones) */
 238     ri.no = 0;
 239     ri.max = n/2;
 240
 241     ri.val = 1;
 242     ri.step = 2;
 243     ri.insertMode = 0;
 244
 245     isamc_i.clientData = &ri;
 246     isamc_i.read_item = code_read;
 247
 248     isamb_merge (isb, &isamc_p, &isamc_i);
 249
 250     if (isamc_p)
 251     {
 252         yaz_log(YLOG_WARN, "isamb_merge did not return empty list n=%d",
 253                 n);
 254         exit(3);
 255     }
 256 }
 257
 258 void tst_forward(ISAMB isb, int n)
 259 {
 260     ISAMC_I isamc_i;
 261     ISAM_P isamc_p;
 262     struct read_info ri;
 263     int i;
 264     ISAMB_PP pp;
 265
 266     /* insert a number of entries */
 267     ri.val = 0;
 268     ri.max = n;
 269
 270     ri.no = 0;
 271     ri.step = 1;
 272     ri.insertMode = 1;
 273
 274     isamc_i.clientData = &ri;
 275     isamc_i.read_item = code_read;
 276
 277     isamc_p = 0;
 278     isamb_merge (isb, &isamc_p, &isamc_i);
 279
 280     /* read the entries */
 281     pp = isamb_pp_open (isb, isamc_p, 1);
 282
 283     for (i = 0; i<ri.max; i +=2 )
 284     {
 285         int x = -1;
 286         int xu = i;
 287         isamb_pp_forward(pp, &x, &xu);
 288         if (x != xu && xu != x+1)
 289         {
 290             yaz_log(YLOG_WARN, "isamb_pp_forward (1). Got %d (expected %d)",
 291                     x, xu);
 292             exit(4);
 293         }
 294         ri.no++;
 295     }
 296     isamb_pp_close(pp);
 297
 298     pp = isamb_pp_open (isb, isamc_p, 1);
 299     for (i = 0; i<ri.max; i += 100)
 300     {
 301         int x = -1;
 302         int xu = i;
 303         isamb_pp_forward(pp, &x, &xu);
 304         if (x != xu && xu != x+1)
 305         {
 306             yaz_log(YLOG_WARN, "isamb_pp_forward (2). Got %d (expected %d)",
 307                     x, xu);
 308             exit(4);
 309         }
 310         ri.no++;
 311     }
 312     isamb_pp_close(pp);
 313
 314     isamb_unlink(isb, isamc_p);
 315 }
 316
 317 void tst_x(ISAMB isb)
 318 {
 319     ISAMC_I isamc_i;
 320     ISAM_P isamb_p = 0;
 321     struct read_info ri;
 322
 323     isamc_i.clientData = &ri;
 324     isamc_i.read_item = code_read;
 325     ri.no = 0;
 326     ri.max = 500;
 327
 328     ri.val = 1000;
 329     ri.step = 1;
 330     ri.insertMode = 1;
 331
 332     isamb_merge (isb, &isamb_p , &isamc_i);
 333
 334     ri.no = 0;
 335     ri.max = 500;
 336
 337     ri.val = 1;
 338     ri.step = 1;
 339     ri.insertMode = 1;
 340
 341     isamb_merge (isb, &isamb_p , &isamc_i);
 342 }
 343
 344 void tst_append(ISAMB isb, int n)
 345 {
 346     ISAMC_I isamc_i;
 347     ISAM_P isamb_p = 0;
 348     struct read_info ri;
 349     int i;
 350     int chunk = 10;
 351
 352     for (i = 0; i < n; i += chunk)
 353     {
 354         /* insert a number of entries */
 355         ri.no = 0;
 356         ri.max = i + chunk;
 357
 358         ri.val = 0;
 359         ri.step = 1;
 360         ri.insertMode = 1;
 361
 362         isamc_i.clientData = &ri;
 363         isamc_i.read_item = code_read;
 364
 365         isamb_merge (isb, &isamb_p , &isamc_i);
 366     }
 367 }
 368
 369
 370 struct random_read_info {
 371     int max;
 372     int idx;
 373     int level;
 374     int *delta;
 375 };
 376
 377 int tst_random_read(void *vp, char **dst, int *insertMode)
 378 {
 379     struct random_read_info *ri = (struct random_read_info *)vp;
 380     int x;
 381
 382     while(ri->idx < ri->max && ri->delta[ri->idx] == ri->level)
 383     {
 384         ri->idx++;
 385         ri->level = 0;
 386     }
 387     if (ri->idx >= ri->max)
 388         return 0;
 389
 390     if (ri->delta[ri->idx] > 0)
 391     {
 392         ri->level++;
 393         *insertMode = 1;
 394     }
 395     else
 396     {
 397         ri->level--;
 398         *insertMode = 0;
 399     }
 400     x = ri->idx;
 401     memcpy (*dst, &x, sizeof(int));
 402     (*dst)+=sizeof(int);
 403
 404     yaz_log(YLOG_DEBUG, "%d %5d", *insertMode, x);
 405     return 1;
 406 }
 407
 408 void tst_random(ISAMB isb, int n, int rounds, int max_dups)
 409 {
 410     ISAM_P isamb_p = 0;
 411
 412     int *freq = malloc(sizeof(int) * n);
 413     int *delta = malloc(sizeof(int) * n);
 414     int i, j;
 415     for (i = 0; i<n; i++)
 416         freq[i] = 0;
 417
 418     for (j = 0; j<rounds; j++)
 419     {
 420         yaz_log(YLOG_DEBUG, "round %d", j);
 421         for (i = 0; i<n; i++)
 422         {
 423             if (rand() & 1)
 424                 delta[i] = (rand() % (1+max_dups)) - freq[i];
 425             else
 426                 delta[i] = 0;
 427         }
 428         if (n)
 429         {
 430             ISAMC_I isamc_i;
 431             struct random_read_info ri;
 432
 433             ri.delta = delta;
 434             ri.idx = 0;
 435             ri.max = n;
 436             ri.level = 0;
 437
 438             isamc_i.clientData = &ri;
 439             isamc_i.read_item = tst_random_read;
 440
 441             isamb_merge (isb, &isamb_p , &isamc_i);
 442         }
 443
 444         yaz_log(YLOG_DEBUG, "dump %d", j);
 445         isamb_dump(isb, isamb_p, log_pr);
 446
 447         yaz_log(YLOG_DEBUG, "----------------------------");
 448         for (i = 0; i<n; i++)
 449             freq[i] += delta[i];
 450
 451         if (!isamb_p)
 452         {
 453             for (i = 0; i<n; i++)
 454                 if (freq[i])
 455                 {
 456                     yaz_log(YLOG_WARN, "isamb_merge returned 0, but "
 457                             "freq is non-empty");
 458                     exit(1);
 459                 }
 460         }
 461         else
 462         {
 463             int level = 0;
 464             int idx = 0;
 465             char key_buf[20];
 466             ISAMB_PP pp = isamb_pp_open (isb, isamb_p, 1);
 467
 468             yaz_log(YLOG_DEBUG, "test %d", j);
 469
 470             while(isamb_pp_read (pp, key_buf))
 471             {
 472                 int x;
 473                 memcpy (&x, key_buf, sizeof(int));
 474                 yaz_log(YLOG_DEBUG, "Got %d", x);
 475                 while (idx < n && freq[idx] == level)
 476                 {
 477                     idx++;
 478                     level = 0;
 479                 }
 480                 if (idx == n)
 481                 {
 482                     yaz_log(YLOG_WARN, "tst_random: Extra item: %d", x);
 483                     exit(1);
 484                 }
 485                 if (idx != x)
 486                 {
 487                     yaz_log(YLOG_WARN, "tst_random: Mismatch %d != %d",
 488                             x, idx);
 489                     exit(1);
 490                 }
 491                 level++;
 492             }
 493             while (idx < n && freq[idx] == level)
 494             {
 495                 idx++;
 496                 level = 0;
 497             }
 498             if (idx != n)
 499             {
 500                 yaz_log(YLOG_WARN, "tst_random: Missing item: %d", idx);
 501                 exit(1);
 502             }
 503             isamb_pp_close(pp);
 504         }
 505     }
 506     free(freq);
 507     free(delta);
 508 }
 509
 510 /* \fn void tst_minsert(ISAMB isb, int n)
 511    \brief insert inserts n identical keys, removes n/2, then n-n/2 ..
 512    \param isb ISAMB handle
 513    \param n number of keys
 514 */
 515 void tst_minsert(ISAMB isb, int n)
 516 {
 517     ISAMC_I isamc_i;
 518     ISAM_P isamb_p = 0;
 519     struct read_info ri;
 520
 521     isamc_i.clientData = &ri;
 522
 523     /* all have same value = 1 */
 524     ri.val = 1;
 525     ri.step = 0;
 526
 527     isamc_i.read_item = code_read;
 528
 529     ri.no = 0;
 530     ri.max = n;
 531
 532     ri.insertMode = 1;
 533
 534     isamb_merge (isb, &isamb_p , &isamc_i);
 535
 536     isamb_dump(isb, isamb_p, log_pr);
 537
 538     ri.no = 0;
 539     ri.max = n - n/2;
 540
 541     ri.insertMode = 0;
 542
 543     isamb_merge (isb, &isamb_p , &isamc_i);
 544
 545     ri.no = 0;
 546     ri.max = n/2;
 547
 548     ri.insertMode = 0;
 549
 550     isamb_merge (isb, &isamb_p , &isamc_i);
 551     if (isamb_p)
 552     {
 553         yaz_log(YLOG_WARN, "tst_minsert: isamb_merge should be empty n=%d",
 554                 n);
 555         exit(1);
 556     }
 557 }
 558
 559 /* tests for identical keys.. ISAMB does not handle that, so some of the
 560    tests below fails
 561 */
 562 static void identical_keys_tests(ISAMB isb)
 563 {
 564 #if 1
 565     tst_minsert(isb, 10);
 566 #endif
 567 #if 0
 568     tst_minsert(isb, 600);  /* still fails */
 569 #endif
 570 #if 1
 571     tst_random(isb, 20, 200, 1);
 572 #endif
 573 #if 1
 574     tst_random(isb, 5, 200, 2);
 575 #endif
 576
 577 #if 1
 578     tst_random(isb, 250, 10, 4);
 579 #endif
 580 #if 1
 581     /* fails if both are executed */
 582     tst_random(isb, 20000, 10, 4);
 583     tst_random(isb, 20000, 10, 10);
 584 #endif
 585 #if 1
 586     tst_random(isb, 250, 100, 10);
 587 #endif
 588 }
 589
 590 int main(int argc, char **argv)
 591 {
 592     BFiles bfs;
 593     ISAMB isb;
 594     ISAMC_M method;
 595
 596     if (argc == 2)
 597         yaz_log_init_level(YLOG_ALL);
 598
 599     /* setup method (attributes) */
 600     method.compare_item = compare_item;
 601     method.log_item = log_item;
 602     method.codec.start = code_start;
 603     method.codec.encode = code_item;
 604     method.codec.decode = code_item;
 605     method.codec.reset = code_reset;
 606     method.codec.stop = code_stop;
 607
 608     /* create block system */
 609     bfs = bfs_create(0, 0);
 610     if (!bfs)
 611     {
 612         yaz_log(YLOG_WARN, "bfs_create failed");
 613         exit(1);
 614     }
 615
 616     bf_reset(bfs);
 617
 618     /* create isam handle */
 619     isb = isamb_open (bfs, "isamb", 1, &method, 0);
 620     if (!isb)
 621     {
 622         yaz_log(YLOG_WARN, "isamb_open failed");
 623         exit(2);
 624     }
 625 #if 0
 626     bench_insert(isb, 1000, 100, 10000);
 627 #else
 628     tst_insert(isb, 1);
 629     tst_insert(isb, 2);
 630     tst_insert(isb, 20);
 631     tst_insert(isb, 100);
 632     tst_insert(isb, 500);
 633     tst_insert(isb, 10000);
 634
 635     tst_forward(isb, 10000);
 636
 637     tst_x(isb);
 638
 639     tst_append(isb, 1000);
 640 #endif
 641
 642     if (0)
 643         identical_keys_tests(isb);
 644
 645     isamb_close(isb);
 646
 647     /* exit block system */
 648     bfs_destroy(bfs);
 649     exit(0);
 650     return 0;
 651 }
 652 /*
 653  * Local variables:
 654  * c-basic-offset: 4
 655  * indent-tabs-mode: nil
 656  * End:
 657  * vim: shiftwidth=4 tabstop=8 expandtab
 658  */
 659