isamb/tstisamb.c

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