isamc/isamc.c

   1 /*
   2  * Copyright (c) 1995-1998, Index Data.
   3  * See the file LICENSE for details.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: isamc.c,v $
   7  * Revision 1.17  1999-05-26 07:49:14  adam
   8  * C++ compilation.
   9  *
  10  * Revision 1.16  1998/05/27 14:32:03  adam
  11  * Changed default block category layout.
  12  *
  13  * Revision 1.15  1998/05/20 10:12:25  adam
  14  * Implemented automatic EXPLAIN database maintenance.
  15  * Modified Zebra to work with ASN.1 compiled version of YAZ.
  16  *
  17  * Revision 1.14  1998/03/19 10:04:35  adam
  18  * Minor changes.
  19  *
  20  * Revision 1.13  1998/03/18 09:23:55  adam
  21  * Blocks are stored in chunks on free list - up to factor 2 in speed.
  22  * Fixed bug that could occur in block category rearrangemen.
  23  *
  24  * Revision 1.12  1998/03/16 10:37:24  adam
  25  * Added more statistics.
  26  *
  27  * Revision 1.11  1998/03/13 15:30:50  adam
  28  * New functions isc_block_used and isc_block_size. Fixed 'leak'
  29  * in isc_alloc_block.
  30  *
  31  * Revision 1.10  1998/03/11 11:18:18  adam
  32  * Changed the isc_merge to take into account the mfill (minimum-fill).
  33  *
  34  * Revision 1.9  1998/03/06 13:54:02  adam
  35  * Fixed two nasty bugs in isc_merge.
  36  *
  37  * Revision 1.8  1997/09/17 12:19:20  adam
  38  * Zebra version corresponds to YAZ version 1.4.
  39  * Changed Zebra server so that it doesn't depend on global common_resource.
  40  *
  41  * Revision 1.7  1997/02/12 20:42:43  adam
  42  * Bug fix: during isc_merge operations, some pages weren't marked dirty
  43  * even though they should be. At this point the merge operation marks
  44  * a page dirty if the previous page changed at all. A better approach is
  45  * to mark it dirty if the last key written changed in previous page.
  46  *
  47  * Revision 1.6  1996/11/08 11:15:29  adam
  48  * Number of keys in chain are stored in first block and the function
  49  * to retrieve this information, isc_pp_num is implemented.
  50  *
  51  * Revision 1.5  1996/11/04 14:08:57  adam
  52  * Optimized free block usage.
  53  *
  54  * Revision 1.4  1996/11/01 13:36:46  adam
  55  * New element, max_blocks_mem, that control how many blocks of max size
  56  * to store in memory during isc_merge.
  57  * Function isc_merge now ignores delete/update of identical keys and
  58  * the proper blocks are then non-dirty and not written in flush_blocks.
  59  *
  60  * Revision 1.3  1996/11/01  08:59:14  adam
  61  * First version of isc_merge that supports update/delete.
  62  *
  63  * Revision 1.2  1996/10/29 16:44:56  adam
  64  * Work on isc_merge.
  65  *
  66  * Revision 1.1  1996/10/29  13:40:48  adam
  67  * First work.
  68  *
  69  */
  70
  71 /*
  72  * TODO:
  73  *   Reduction to lower categories in isc_merge
  74  */
  75 #include <stdlib.h>
  76 #include <assert.h>
  77 #include <string.h>
  78 #include <stdio.h>
  79
  80 #include <log.h>
  81 #include "isamc-p.h"
  82
  83 static void flush_block (ISAMC is, int cat);
  84 static void release_fc (ISAMC is, int cat);
  85 static void init_fc (ISAMC is, int cat);
  86
  87 #define ISAMC_FREELIST_CHUNK 1
  88
  89 #define SMALL_TEST 0
  90
  91 ISAMC_M isc_getmethod (void)
  92 {
  93     static struct ISAMC_filecat_s def_cat[] = {
  94 #if SMALL_TEST
  95         {    32,     28,      0,  3 },
  96         {    64,     54,     30,  0 },
  97 #else
  98         {    24,     22,     18,  10 },
  99         {   128,    120,    100,  10 },
 100         {   512,    490,    350,  10 },
 101         {  2048,   1900,   1700,  10 },
 102         {  8192,   8000,   7900,  10 },
 103         { 32768,  32000,  31000,  0 },
 104 #endif
 105     };
 106     ISAMC_M m = (ISAMC_M) xmalloc (sizeof(*m));
 107     m->filecat = def_cat;
 108
 109     m->code_start = NULL;
 110     m->code_item = NULL;
 111     m->code_stop = NULL;
 112
 113     m->compare_item = NULL;
 114
 115     m->debug = 1;
 116
 117     m->max_blocks_mem = 10;
 118
 119     return m;
 120 }
 121
 122
 123 ISAMC isc_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method)
 124 {
 125     ISAMC is;
 126     ISAMC_filecat filecat;
 127     int i = 0;
 128     int max_buf_size = 0;
 129
 130     is = (ISAMC) xmalloc (sizeof(*is));
 131
 132     is->method = (ISAMC_M) xmalloc (sizeof(*is->method));
 133     memcpy (is->method, method, sizeof(*method));
 134     filecat = is->method->filecat;
 135     assert (filecat);
 136
 137     /* determine number of block categories */
 138     if (is->method->debug)
 139         logf (LOG_LOG, "isc: bsize  ifill  mfill mblocks");
 140     do
 141     {
 142         if (is->method->debug)
 143             logf (LOG_LOG, "isc:%6d %6d %6d %6d",
 144                   filecat[i].bsize, filecat[i].ifill,
 145                   filecat[i].mfill, filecat[i].mblocks);
 146         if (max_buf_size < filecat[i].mblocks * filecat[i].bsize)
 147             max_buf_size = filecat[i].mblocks * filecat[i].bsize;
 148     } while (filecat[i++].mblocks);
 149     is->no_files = i;
 150     is->max_cat = --i;
 151     /* max_buf_size is the larget buffer to be used during merge */
 152     max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
 153     if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
 154         max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
 155     if (is->method->debug)
 156         logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
 157
 158     assert (is->no_files > 0);
 159     is->files = (ISAMC_file) xmalloc (sizeof(*is->files)*is->no_files);
 160     if (writeflag)
 161     {
 162         is->merge_buf = (char *) xmalloc (max_buf_size+256);
 163         memset (is->merge_buf, 0, max_buf_size+256);
 164     }
 165     else
 166         is->merge_buf = NULL;
 167     for (i = 0; i<is->no_files; i++)
 168     {
 169         char fname[512];
 170
 171         sprintf (fname, "%s%c", name, i+'A');
 172         is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
 173                                    writeflag);
 174         is->files[i].head_is_dirty = 0;
 175         if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
 176                      &is->files[i].head))
 177         {
 178             is->files[i].head.lastblock = 1;
 179             is->files[i].head.freelist = 0;
 180         }
 181         is->files[i].alloc_entries_num = 0;
 182         is->files[i].alloc_entries_max =
 183             is->method->filecat[i].bsize / sizeof(int) - 1;
 184         is->files[i].alloc_buf = (char *)
 185             xmalloc (is->method->filecat[i].bsize);
 186         is->files[i].no_writes = 0;
 187         is->files[i].no_reads = 0;
 188         is->files[i].no_skip_writes = 0;
 189         is->files[i].no_allocated = 0;
 190         is->files[i].no_released = 0;
 191         is->files[i].no_remap = 0;
 192         is->files[i].no_forward = 0;
 193         is->files[i].no_backward = 0;
 194         is->files[i].sum_forward = 0;
 195         is->files[i].sum_backward = 0;
 196         is->files[i].no_next = 0;
 197         is->files[i].no_prev = 0;
 198
 199         init_fc (is, i);
 200     }
 201     return is;
 202 }
 203
 204 int isc_block_used (ISAMC is, int type)
 205 {
 206     if (type < 0 || type >= is->no_files)
 207         return -1;
 208     return is->files[type].head.lastblock-1;
 209 }
 210
 211 int isc_block_size (ISAMC is, int type)
 212 {
 213     ISAMC_filecat filecat = is->method->filecat;
 214     if (type < 0 || type >= is->no_files)
 215         return -1;
 216     return filecat[type].bsize;
 217 }
 218
 219 int isc_close (ISAMC is)
 220 {
 221     int i;
 222
 223     if (is->method->debug)
 224     {
 225         logf (LOG_LOG, "isc:    next    forw   mid-f    prev   backw   mid-b");
 226         for (i = 0; i<is->no_files; i++)
 227             logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
 228                   is->files[i].no_next,
 229                   is->files[i].no_forward,
 230                   is->files[i].no_forward ?
 231                   (double) is->files[i].sum_forward/is->files[i].no_forward
 232                   : 0.0,
 233                   is->files[i].no_prev,
 234                   is->files[i].no_backward,
 235                   is->files[i].no_backward ?
 236                   (double) is->files[i].sum_backward/is->files[i].no_backward
 237                   : 0.0);
 238     }
 239     if (is->method->debug)
 240         logf (LOG_LOG, "isc:  writes   reads skipped   alloc released  remap");
 241     for (i = 0; i<is->no_files; i++)
 242     {
 243         release_fc (is, i);
 244         assert (is->files[i].bf);
 245         if (is->files[i].head_is_dirty)
 246             bf_write (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
 247                  &is->files[i].head);
 248         if (is->method->debug)
 249             logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
 250                   is->files[i].no_writes,
 251                   is->files[i].no_reads,
 252                   is->files[i].no_skip_writes,
 253                   is->files[i].no_allocated,
 254                   is->files[i].no_released,
 255                   is->files[i].no_remap);
 256         xfree (is->files[i].fc_list);
 257         flush_block (is, i);
 258         bf_close (is->files[i].bf);
 259     }
 260     xfree (is->files);
 261     xfree (is->merge_buf);
 262     xfree (is->method);
 263     xfree (is);
 264     return 0;
 265 }
 266
 267 int isc_read_block (ISAMC is, int cat, int pos, char *dst)
 268 {
 269     ++(is->files[cat].no_reads);
 270     return bf_read (is->files[cat].bf, pos, 0, 0, dst);
 271 }
 272
 273 int isc_write_block (ISAMC is, int cat, int pos, char *src)
 274 {
 275     ++(is->files[cat].no_writes);
 276     if (is->method->debug > 2)
 277         logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
 278     return bf_write (is->files[cat].bf, pos, 0, 0, src);
 279 }
 280
 281 int isc_write_dblock (ISAMC is, int cat, int pos, char *src,
 282                       int nextpos, int offset)
 283 {
 284     ISAMC_BLOCK_SIZE size = offset + ISAMC_BLOCK_OFFSET_N;
 285     if (is->method->debug > 2)
 286         logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
 287               (int) size, nextpos);
 288     src -= ISAMC_BLOCK_OFFSET_N;
 289     memcpy (src, &nextpos, sizeof(int));
 290     memcpy (src + sizeof(int), &size, sizeof(size));
 291     return isc_write_block (is, cat, pos, src);
 292 }
 293
 294 #if ISAMC_FREELIST_CHUNK
 295 static void flush_block (ISAMC is, int cat)
 296 {
 297     char *abuf = is->files[cat].alloc_buf;
 298     int block = is->files[cat].head.freelist;
 299     if (block && is->files[cat].alloc_entries_num)
 300     {
 301         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
 302         bf_write (is->files[cat].bf, block, 0, 0, abuf);
 303         is->files[cat].alloc_entries_num = 0;
 304     }
 305     xfree (abuf);
 306 }
 307
 308 static int alloc_block (ISAMC is, int cat)
 309 {
 310     int block = is->files[cat].head.freelist;
 311     char *abuf = is->files[cat].alloc_buf;
 312
 313     (is->files[cat].no_allocated)++;
 314
 315     if (!block)
 316     {
 317         block = (is->files[cat].head.lastblock)++;   /* no free list */
 318         is->files[cat].head_is_dirty = 1;
 319     }
 320     else
 321     {
 322         if (!is->files[cat].alloc_entries_num) /* read first time */
 323         {
 324             bf_read (is->files[cat].bf, block, 0, 0, abuf);
 325             memcpy (&is->files[cat].alloc_entries_num, abuf,
 326                     sizeof(is->files[cat].alloc_entries_num));
 327             assert (is->files[cat].alloc_entries_num > 0);
 328         }
 329         /* have some free blocks now */
 330         assert (is->files[cat].alloc_entries_num > 0);
 331         is->files[cat].alloc_entries_num--;
 332         if (!is->files[cat].alloc_entries_num)  /* last one in block? */
 333         {
 334             memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
 335                     sizeof(int));
 336             is->files[cat].head_is_dirty = 1;
 337
 338             if (is->files[cat].head.freelist)
 339             {
 340                 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
 341                          0, 0, abuf);
 342                 memcpy (&is->files[cat].alloc_entries_num, abuf,
 343                         sizeof(is->files[cat].alloc_entries_num));
 344                 assert (is->files[cat].alloc_entries_num);
 345             }
 346         }
 347         else
 348             memcpy (&block, abuf + sizeof(int) + sizeof(int) *
 349                     is->files[cat].alloc_entries_num, sizeof(int));
 350     }
 351     return block;
 352 }
 353
 354 static void release_block (ISAMC is, int cat, int pos)
 355 {
 356     char *abuf = is->files[cat].alloc_buf;
 357     int block = is->files[cat].head.freelist;
 358
 359     (is->files[cat].no_released)++;
 360
 361     if (block && !is->files[cat].alloc_entries_num) /* must read block */
 362     {
 363         bf_read (is->files[cat].bf, block, 0, 0, abuf);
 364         memcpy (&is->files[cat].alloc_entries_num, abuf,
 365                 sizeof(is->files[cat].alloc_entries_num));
 366         assert (is->files[cat].alloc_entries_num > 0);
 367     }
 368     assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
 369     if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
 370     {
 371         assert (block);
 372         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
 373         bf_write (is->files[cat].bf, block, 0, 0, abuf);
 374         is->files[cat].alloc_entries_num = 0;
 375     }
 376     if (!is->files[cat].alloc_entries_num) /* make new buffer? */
 377     {
 378         memcpy (abuf + sizeof(int), &block, sizeof(int));
 379         is->files[cat].head.freelist = pos;
 380         is->files[cat].head_is_dirty = 1;
 381     }
 382     else
 383     {
 384         memcpy (abuf + sizeof(int) +
 385                 is->files[cat].alloc_entries_num*sizeof(int),
 386                 &pos, sizeof(int));
 387     }
 388     is->files[cat].alloc_entries_num++;
 389 }
 390 #else
 391 static void flush_block (ISAMC is, int cat)
 392 {
 393     char *abuf = is->files[cat].alloc_buf;
 394     xfree (abuf);
 395 }
 396
 397 static int alloc_block (ISAMC is, int cat)
 398 {
 399     int block;
 400     char buf[sizeof(int)];
 401
 402     is->files[cat].head_is_dirty = 1;
 403     (is->files[cat].no_allocated)++;
 404     if ((block = is->files[cat].head.freelist))
 405     {
 406         bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
 407         memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
 408     }
 409     else
 410         block = (is->files[cat].head.lastblock)++;
 411     return block;
 412 }
 413
 414 static void release_block (ISAMC is, int cat, int pos)
 415 {
 416     char buf[sizeof(int)];
 417
 418     (is->files[cat].no_released)++;
 419     is->files[cat].head_is_dirty = 1;
 420     memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
 421     is->files[cat].head.freelist = pos;
 422     bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
 423 }
 424 #endif
 425
 426 int isc_alloc_block (ISAMC is, int cat)
 427 {
 428     int block = 0;
 429
 430     if (is->files[cat].fc_list)
 431     {
 432         int j, nb;
 433         for (j = 0; j < is->files[cat].fc_max; j++)
 434             if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
 435             {
 436                 is->files[cat].fc_list[j] = 0;
 437                 block = nb;
 438                 break;
 439             }
 440     }
 441     if (!block)
 442         block = alloc_block (is, cat);
 443     if (is->method->debug > 3)
 444         logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
 445     return block;
 446 }
 447
 448 void isc_release_block (ISAMC is, int cat, int pos)
 449 {
 450     if (is->method->debug > 3)
 451         logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
 452     if (is->files[cat].fc_list)
 453     {
 454         int j;
 455         for (j = 0; j<is->files[cat].fc_max; j++)
 456             if (!is->files[cat].fc_list[j])
 457             {
 458                 is->files[cat].fc_list[j] = pos;
 459                 return;
 460             }
 461     }
 462     release_block (is, cat, pos);
 463 }
 464
 465 static void init_fc (ISAMC is, int cat)
 466 {
 467     int j = 100;
 468
 469     is->files[cat].fc_max = j;
 470     is->files[cat].fc_list = (int *)
 471         xmalloc (sizeof(*is->files[0].fc_list) * j);
 472     while (--j >= 0)
 473         is->files[cat].fc_list[j] = 0;
 474 }
 475
 476 static void release_fc (ISAMC is, int cat)
 477 {
 478     int b, j = is->files[cat].fc_max;
 479
 480     while (--j >= 0)
 481         if ((b = is->files[cat].fc_list[j]))
 482         {
 483             release_block (is, cat, b);
 484             is->files[cat].fc_list[j] = 0;
 485         }
 486 }
 487
 488 void isc_pp_close (ISAMC_PP pp)
 489 {
 490     ISAMC is = pp->is;
 491
 492     (*is->method->code_stop)(ISAMC_DECODE, pp->decodeClientData);
 493     xfree (pp->buf);
 494     xfree (pp);
 495 }
 496
 497 ISAMC_PP isc_pp_open (ISAMC is, ISAMC_P ipos)
 498 {
 499     ISAMC_PP pp = (ISAMC_PP) xmalloc (sizeof(*pp));
 500     char *src;
 501
 502     pp->cat = isc_type(ipos);
 503     pp->pos = isc_block(ipos);
 504
 505     src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
 506
 507     pp->next = 0;
 508     pp->size = 0;
 509     pp->offset = 0;
 510     pp->is = is;
 511     pp->decodeClientData = (*is->method->code_start)(ISAMC_DECODE);
 512     pp->deleteFlag = 0;
 513     pp->numKeys = 0;
 514
 515     if (pp->pos)
 516     {
 517         src = pp->buf;
 518         isc_read_block (is, pp->cat, pp->pos, src);
 519         memcpy (&pp->next, src, sizeof(pp->next));
 520         src += sizeof(pp->next);
 521         memcpy (&pp->size, src, sizeof(pp->size));
 522         src += sizeof(pp->size);
 523         memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
 524         src += sizeof(pp->numKeys);
 525         assert (pp->next != pp->pos);
 526         pp->offset = src - pp->buf;
 527         assert (pp->offset == ISAMC_BLOCK_OFFSET_1);
 528         if (is->method->debug > 2)
 529             logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
 530                  pp->size, pp->cat, pp->pos, pp->next);
 531     }
 532     return pp;
 533 }
 534
 535 /* returns non-zero if item could be read; 0 otherwise */
 536 int isc_pp_read (ISAMC_PP pp, void *buf)
 537 {
 538     return isc_read_item (pp, (char **) &buf);
 539 }
 540
 541 /* read one item from file - decode and store it in *dst.
 542    Returns
 543      0 if end-of-file
 544      1 if item could be read ok and NO boundary
 545      2 if item could be read ok and boundary */
 546 int isc_read_item (ISAMC_PP pp, char **dst)
 547 {
 548     ISAMC is = pp->is;
 549     char *src = pp->buf + pp->offset;
 550
 551     if (pp->offset >= pp->size)
 552     {
 553         if (!pp->next)
 554         {
 555             pp->pos = 0;
 556             return 0; /* end of file */
 557         }
 558         if (pp->next > pp->pos)
 559         {
 560             if (pp->next == pp->pos + 1)
 561                 is->files[pp->cat].no_next++;
 562             else
 563             {
 564                 is->files[pp->cat].no_forward++;
 565                 is->files[pp->cat].sum_forward += pp->next - pp->pos;
 566             }
 567         }
 568         else
 569         {
 570             if (pp->next + 1 == pp->pos)
 571                 is->files[pp->cat].no_prev++;
 572             else
 573             {
 574                 is->files[pp->cat].no_backward++;
 575                 is->files[pp->cat].sum_backward += pp->pos - pp->next;
 576             }
 577         }
 578         /* out new block position */
 579         pp->pos = pp->next;
 580         src = pp->buf;
 581         /* read block and save 'next' and 'size' entry */
 582         isc_read_block (is, pp->cat, pp->pos, src);
 583         memcpy (&pp->next, src, sizeof(pp->next));
 584         src += sizeof(pp->next);
 585         memcpy (&pp->size, src, sizeof(pp->size));
 586         src += sizeof(pp->size);
 587         /* assume block is non-empty */
 588         assert (src - pp->buf == ISAMC_BLOCK_OFFSET_N);
 589         assert (pp->next != pp->pos);
 590         if (pp->deleteFlag)
 591             isc_release_block (is, pp->cat, pp->pos);
 592         (*is->method->code_item)(ISAMC_DECODE, pp->decodeClientData, dst, &src);
 593         pp->offset = src - pp->buf;
 594         if (is->method->debug > 2)
 595             logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
 596                  pp->size, pp->cat, pp->pos, pp->next);
 597         return 2;
 598     }
 599     (*is->method->code_item)(ISAMC_DECODE, pp->decodeClientData, dst, &src);
 600     pp->offset = src - pp->buf;
 601     return 1;
 602 }
 603
 604 int isc_pp_num (ISAMC_PP pp)
 605 {
 606     return pp->numKeys;
 607 }
 608