isamc/isamh.c

   1 /*
   2  * Copyright (c) 1995-1998, Index Data.
   3  * See the file LICENSE for details.
   4  * Heikki Levanto
   5  *
   6  * Isamh - append-only isam
   7  *
   8  * TODO
   9  * All of it
  10  * Define structures
  11  * Get append to work
  12  */
  13
  14
  15
  16
  17 #include <stdlib.h>
  18 #include <assert.h>
  19 #include <string.h>
  20 #include <stdio.h>
  21
  22 #include <log.h>
  23 #include "isamh-p.h"
  24
  25 static void flush_block (ISAMH is, int cat);
  26 static void release_fc (ISAMH is, int cat);
  27 static void init_fc (ISAMH is, int cat);
  28
  29 #define ISAMH_FREELIST_CHUNK 1
  30
  31 #define SMALL_TEST 1
  32
  33 ISAMH_M isamh_getmethod (void)
  34 {
  35     static struct ISAMH_filecat_s def_cat[] = {
  36 #if SMALL_TEST
  37 /*        blocksz,   maxnum */
  38         {    32,   3 },
  39         {    64,   0 },
  40 #else
  41         {    24, 10 },
  42         {   128, 10 },
  43         {   512, 10 },
  44         {  2048, 10 },
  45         {  8192, 10 },
  46         { 32768,  0 },
  47 #endif
  48     };
  49     ISAMH_M m = (ISAMH_M) xmalloc (sizeof(*m));
  50     m->filecat = def_cat;
  51
  52     m->code_start = NULL;
  53     m->code_item = NULL;
  54     m->code_stop = NULL;
  55     m->code_reset = NULL;
  56
  57     m->compare_item = NULL;
  58
  59     m->debug = 1;
  60
  61     m->max_blocks_mem = 10;
  62
  63     return m;
  64 }
  65
  66
  67 ISAMH isamh_open (BFiles bfs, const char *name, int writeflag, ISAMH_M method)
  68 {
  69     ISAMH is;
  70     ISAMH_filecat filecat;
  71     int i = 0;
  72     int max_buf_size = 0;
  73
  74     is = (ISAMH) xmalloc (sizeof(*is));
  75
  76     is->method = (ISAMH_M) xmalloc (sizeof(*is->method));
  77     memcpy (is->method, method, sizeof(*method));
  78     filecat = is->method->filecat;
  79     assert (filecat);
  80
  81     /* determine number of block categories */
  82     if (is->method->debug)
  83         logf (LOG_LOG, "isc: bsize  ifill  mfill mblocks");
  84     do
  85     {
  86         if (is->method->debug)
  87             logf (LOG_LOG, "isc:%6d %6d",
  88                   filecat[i].bsize, filecat[i].mblocks);
  89         if (max_buf_size < filecat[i].bsize)
  90             max_buf_size = filecat[i].bsize;
  91     } while (filecat[i++].mblocks);
  92     is->no_files = i;
  93     is->max_cat = --i;
  94 #ifdef SKIPTHIS
  95     /* max_buf_size is the larget buffer to be used during merge */
  96     max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
  97     if (max_buf_size < (1+is->method->max_blocks_mem) * filecat[i].bsize)
  98         max_buf_size = (1+is->method->max_blocks_mem) * filecat[i].bsize;
  99 #endif
 100
 101     if (is->method->debug)
 102         logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
 103
 104     assert (is->no_files > 0);
 105     is->files = (ISAMH_file) xmalloc (sizeof(*is->files)*is->no_files);
 106     if (writeflag)
 107     {
 108 #ifdef SKIPTHIS
 109         is->merge_buf = (char *) xmalloc (max_buf_size+256);
 110         memset (is->merge_buf, 0, max_buf_size+256);
 111 #else
 112         is->startblock = (char *) xmalloc (max_buf_size+256);
 113         memset (is->startblock, 0, max_buf_size+256);
 114         is->lastblock = (char *) xmalloc (max_buf_size+256);
 115         memset (is->lastblock, 0, max_buf_size+256);
 116         /* The spare 256 bytes should not be needed! */
 117 #endif
 118     }
 119     else
 120         is->startblock = is->lastblock = NULL;
 121
 122     for (i = 0; i<is->no_files; i++)
 123     {
 124         char fname[512];
 125
 126         sprintf (fname, "%s%c", name, i+'A');
 127         is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
 128                                    writeflag);
 129         is->files[i].head_is_dirty = 0;
 130         if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
 131                      &is->files[i].head))
 132         {
 133             is->files[i].head.lastblock = 1;
 134             is->files[i].head.freelist = 0;
 135         }
 136         is->files[i].alloc_entries_num = 0;
 137         is->files[i].alloc_entries_max =
 138             is->method->filecat[i].bsize / sizeof(int) - 1;
 139         is->files[i].alloc_buf = (char *)
 140             xmalloc (is->method->filecat[i].bsize);
 141         is->files[i].no_writes = 0;
 142         is->files[i].no_reads = 0;
 143         is->files[i].no_skip_writes = 0;
 144         is->files[i].no_allocated = 0;
 145         is->files[i].no_released = 0;
 146         is->files[i].no_remap = 0;
 147         is->files[i].no_forward = 0;
 148         is->files[i].no_backward = 0;
 149         is->files[i].sum_forward = 0;
 150         is->files[i].sum_backward = 0;
 151         is->files[i].no_next = 0;
 152         is->files[i].no_prev = 0;
 153
 154         init_fc (is, i);
 155     }
 156     return is;
 157 }
 158
 159 int isamh_block_used (ISAMH is, int type)
 160 {
 161     if (type < 0 || type >= is->no_files)
 162         return -1;
 163     return is->files[type].head.lastblock-1;
 164 }
 165
 166 int isamh_block_size (ISAMH is, int type)
 167 {
 168     ISAMH_filecat filecat = is->method->filecat;
 169     if (type < 0 || type >= is->no_files)
 170         return -1;
 171     return filecat[type].bsize;
 172 }
 173
 174 int isamh_close (ISAMH is)
 175 {
 176     int i;
 177
 178     if (is->method->debug)
 179     {
 180         logf (LOG_LOG, "isc:    next    forw   mid-f    prev   backw   mid-b");
 181         for (i = 0; i<is->no_files; i++)
 182             logf (LOG_LOG, "isc:%8d%8d%8.1f%8d%8d%8.1f",
 183                   is->files[i].no_next,
 184                   is->files[i].no_forward,
 185                   is->files[i].no_forward ?
 186                   (double) is->files[i].sum_forward/is->files[i].no_forward
 187                   : 0.0,
 188                   is->files[i].no_prev,
 189                   is->files[i].no_backward,
 190                   is->files[i].no_backward ?
 191                   (double) is->files[i].sum_backward/is->files[i].no_backward
 192                   : 0.0);
 193     }
 194     if (is->method->debug)
 195         logf (LOG_LOG, "isc:  writes   reads skipped   alloc released  remap");
 196     for (i = 0; i<is->no_files; i++)
 197     {
 198         release_fc (is, i);
 199         assert (is->files[i].bf);
 200         if (is->files[i].head_is_dirty)
 201             bf_write (is->files[i].bf, 0, 0, sizeof(ISAMH_head),
 202                  &is->files[i].head);
 203         if (is->method->debug)
 204             logf (LOG_LOG, "isc:%8d%8d%8d%8d%8d%8d",
 205                   is->files[i].no_writes,
 206                   is->files[i].no_reads,
 207                   is->files[i].no_skip_writes,
 208                   is->files[i].no_allocated,
 209                   is->files[i].no_released,
 210                   is->files[i].no_remap);
 211         xfree (is->files[i].fc_list);
 212         flush_block (is, i);
 213         bf_close (is->files[i].bf);
 214     }
 215     xfree (is->files);
 216     xfree (is->startblock);
 217     xfree (is->lastblock);
 218     xfree (is->method);
 219     xfree (is);
 220     return 0;
 221 }
 222
 223 int isamh_read_block (ISAMH is, int cat, int pos, char *dst)
 224 {
 225     ++(is->files[cat].no_reads);
 226     return bf_read (is->files[cat].bf, pos, 0, 0, dst);
 227 }
 228
 229 int isamh_write_block (ISAMH is, int cat, int pos, char *src)
 230 {
 231     ++(is->files[cat].no_writes);
 232     if (is->method->debug > 2)
 233         logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
 234     return bf_write (is->files[cat].bf, pos, 0, 0, src);
 235 }
 236
 237 int isamh_write_dblock (ISAMH is, int cat, int pos, char *src,
 238                       int nextpos, int offset)
 239 {
 240     ISAMH_BLOCK_SIZE size = offset + ISAMH_BLOCK_OFFSET_N;
 241     if (is->method->debug > 2)
 242         logf (LOG_LOG, "isc: write_dblock. size=%d nextpos=%d",
 243               (int) size, nextpos);
 244     src -= ISAMH_BLOCK_OFFSET_N;
 245     memcpy (src, &nextpos, sizeof(int));
 246     memcpy (src + sizeof(int), &size, sizeof(size));
 247     return isamh_write_block (is, cat, pos, src);
 248 }
 249
 250 #if ISAMH_FREELIST_CHUNK
 251 static void flush_block (ISAMH is, int cat)
 252 {
 253     char *abuf = is->files[cat].alloc_buf;
 254     int block = is->files[cat].head.freelist;
 255     if (block && is->files[cat].alloc_entries_num)
 256     {
 257         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
 258         bf_write (is->files[cat].bf, block, 0, 0, abuf);
 259         is->files[cat].alloc_entries_num = 0;
 260     }
 261     xfree (abuf);
 262 }
 263
 264 static int alloc_block (ISAMH is, int cat)
 265 {
 266     int block = is->files[cat].head.freelist;
 267     char *abuf = is->files[cat].alloc_buf;
 268
 269     (is->files[cat].no_allocated)++;
 270
 271     if (!block)
 272     {
 273         block = (is->files[cat].head.lastblock)++;   /* no free list */
 274         is->files[cat].head_is_dirty = 1;
 275     }
 276     else
 277     {
 278         if (!is->files[cat].alloc_entries_num) /* read first time */
 279         {
 280             bf_read (is->files[cat].bf, block, 0, 0, abuf);
 281             memcpy (&is->files[cat].alloc_entries_num, abuf,
 282                     sizeof(is->files[cat].alloc_entries_num));
 283             assert (is->files[cat].alloc_entries_num > 0);
 284         }
 285         /* have some free blocks now */
 286         assert (is->files[cat].alloc_entries_num > 0);
 287         is->files[cat].alloc_entries_num--;
 288         if (!is->files[cat].alloc_entries_num)  /* last one in block? */
 289         {
 290             memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
 291                     sizeof(int));
 292             is->files[cat].head_is_dirty = 1;
 293
 294             if (is->files[cat].head.freelist)
 295             {
 296                 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
 297                          0, 0, abuf);
 298                 memcpy (&is->files[cat].alloc_entries_num, abuf,
 299                         sizeof(is->files[cat].alloc_entries_num));
 300                 assert (is->files[cat].alloc_entries_num);
 301             }
 302         }
 303         else
 304             memcpy (&block, abuf + sizeof(int) + sizeof(int) *
 305                     is->files[cat].alloc_entries_num, sizeof(int));
 306     }
 307     return block;
 308 }
 309
 310 static void release_block (ISAMH is, int cat, int pos)
 311 {
 312     char *abuf = is->files[cat].alloc_buf;
 313     int block = is->files[cat].head.freelist;
 314
 315     (is->files[cat].no_released)++;
 316
 317     if (block && !is->files[cat].alloc_entries_num) /* must read block */
 318     {
 319         bf_read (is->files[cat].bf, block, 0, 0, abuf);
 320         memcpy (&is->files[cat].alloc_entries_num, abuf,
 321                 sizeof(is->files[cat].alloc_entries_num));
 322         assert (is->files[cat].alloc_entries_num > 0);
 323     }
 324     assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
 325     if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
 326     {
 327         assert (block);
 328         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
 329         bf_write (is->files[cat].bf, block, 0, 0, abuf);
 330         is->files[cat].alloc_entries_num = 0;
 331     }
 332     if (!is->files[cat].alloc_entries_num) /* make new buffer? */
 333     {
 334         memcpy (abuf + sizeof(int), &block, sizeof(int));
 335         is->files[cat].head.freelist = pos;
 336         is->files[cat].head_is_dirty = 1;
 337     }
 338     else
 339     {
 340         memcpy (abuf + sizeof(int) +
 341                 is->files[cat].alloc_entries_num*sizeof(int),
 342                 &pos, sizeof(int));
 343     }
 344     is->files[cat].alloc_entries_num++;
 345 }
 346 #else
 347 static void flush_block (ISAMH is, int cat)
 348 {
 349     char *abuf = is->files[cat].alloc_buf;
 350     xfree (abuf);
 351 }
 352
 353 static int alloc_block (ISAMH is, int cat)
 354 {
 355     int block;
 356     char buf[sizeof(int)];
 357
 358     is->files[cat].head_is_dirty = 1;
 359     (is->files[cat].no_allocated)++;
 360     if ((block = is->files[cat].head.freelist))
 361     {
 362         bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
 363         memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
 364     }
 365     else
 366         block = (is->files[cat].head.lastblock)++;
 367     return block;
 368 }
 369
 370 static void release_block (ISAMH is, int cat, int pos)
 371 {
 372     char buf[sizeof(int)];
 373
 374     (is->files[cat].no_released)++;
 375     is->files[cat].head_is_dirty = 1;
 376     memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
 377     is->files[cat].head.freelist = pos;
 378     bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
 379 }
 380 #endif
 381
 382 int isamh_alloc_block (ISAMH is, int cat)
 383 {
 384     int block = 0;
 385
 386     if (is->files[cat].fc_list)
 387     {
 388         int j, nb;
 389         for (j = 0; j < is->files[cat].fc_max; j++)
 390             if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
 391             {
 392                 is->files[cat].fc_list[j] = 0;
 393                 block = nb;
 394                 break;
 395             }
 396     }
 397     if (!block)
 398         block = alloc_block (is, cat);
 399     if (is->method->debug > 3)
 400         logf (LOG_LOG, "isc: alloc_block in cat %d: %d", cat, block);
 401     return block;
 402 }
 403
 404 void isamh_release_block (ISAMH is, int cat, int pos)
 405 {
 406     if (is->method->debug > 3)
 407         logf (LOG_LOG, "isc: release_block in cat %d: %d", cat, pos);
 408     if (is->files[cat].fc_list)
 409     {
 410         int j;
 411         for (j = 0; j<is->files[cat].fc_max; j++)
 412             if (!is->files[cat].fc_list[j])
 413             {
 414                 is->files[cat].fc_list[j] = pos;
 415                 return;
 416             }
 417     }
 418     release_block (is, cat, pos);
 419 }
 420
 421 static void init_fc (ISAMH is, int cat)
 422 {
 423     int j = 100;
 424
 425     is->files[cat].fc_max = j;
 426     is->files[cat].fc_list = (int *)
 427         xmalloc (sizeof(*is->files[0].fc_list) * j);
 428     while (--j >= 0)
 429         is->files[cat].fc_list[j] = 0;
 430 }
 431
 432 static void release_fc (ISAMH is, int cat)
 433 {
 434     int b, j = is->files[cat].fc_max;
 435
 436     while (--j >= 0)
 437         if ((b = is->files[cat].fc_list[j]))
 438         {
 439             release_block (is, cat, b);
 440             is->files[cat].fc_list[j] = 0;
 441         }
 442 }
 443
 444 void isamh_pp_close (ISAMH_PP pp)
 445 {
 446     ISAMH is = pp->is;
 447
 448     (*is->method->code_stop)(ISAMH_DECODE, pp->decodeClientData);
 449     xfree (pp->buf);
 450     xfree (pp);
 451 }
 452
 453 ISAMH_PP isamh_pp_open (ISAMH is, ISAMH_P ipos)
 454 {
 455     ISAMH_PP pp = (ISAMH_PP) xmalloc (sizeof(*pp));
 456     char *src;
 457
 458     pp->cat = isamh_type(ipos);
 459     pp->pos = isamh_block(ipos);
 460
 461     src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
 462
 463     pp->next = 0;
 464     pp->size = 0;
 465     pp->offset = 0;
 466     pp->is = is;
 467     pp->decodeClientData = (*is->method->code_start)(ISAMH_DECODE);
 468     pp->deleteFlag = 0;
 469     pp->numKeys = 0;
 470     pp->lastblock=0;
 471
 472     if (pp->pos)
 473     {
 474         src = pp->buf;
 475         isamh_read_block (is, pp->cat, pp->pos, src);
 476         memcpy (&pp->next, src, sizeof(pp->next));
 477         src += sizeof(pp->next);
 478         memcpy (&pp->size, src, sizeof(pp->size));
 479         src += sizeof(pp->size);
 480         memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
 481         src += sizeof(pp->numKeys);
 482         memcpy (&pp->lastblock, src, sizeof(pp->lastblock));
 483         src += sizeof(pp->lastblock);
 484         assert (pp->next != pp->pos);
 485         pp->offset = src - pp->buf;
 486         assert (pp->offset == ISAMH_BLOCK_OFFSET_1);
 487         if (is->method->debug > 2)
 488             logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
 489                  pp->size, pp->cat, pp->pos, pp->next);
 490     }
 491     return pp;
 492 }
 493
 494 void isamh_buildfirstblock(ISAMH_PP pp){
 495   char *dst=pp->buf;
 496   assert(pp->buf);
 497   assert(pp->next != pp->pos);
 498   memcpy(dst, &pp->next, sizeof(pp->next) );
 499   dst += sizeof(pp->next);
 500   memcpy(dst, &pp->size,sizeof(pp->size));
 501   dst += sizeof(pp->size);
 502   memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
 503   dst += sizeof(pp->numKeys);
 504   memcpy(dst, &pp->lastblock, sizeof(pp->lastblock));
 505   dst += sizeof(pp->lastblock);
 506   assert (dst - pp->buf  == ISAMH_BLOCK_OFFSET_1);
 507   if (pp->is->method->debug > 2)
 508      logf (LOG_LOG, "isamh: firstblock: sz=%d c=%d p=%d>%d>%d nk=%d",
 509            pp->size, pp->cat, pp->pos, pp->next, pp->lastblock,pp->numKeys);
 510 }
 511
 512 void isamh_buildlaterblock(ISAMH_PP pp){
 513   char *dst=pp->buf;
 514   assert(pp->buf);
 515   assert(pp->next != pp->pos);
 516   memcpy(dst, &pp->next, sizeof(pp->next) );
 517   dst += sizeof(pp->next);
 518   memcpy(dst, &pp->size,sizeof(pp->size));
 519   dst += sizeof(pp->size);
 520   assert (dst - pp->buf  == ISAMH_BLOCK_OFFSET_N);
 521   if (pp->is->method->debug > 2)
 522      logf (LOG_LOG, "isamh: laterblock: sz=%d c=%d p=%d>%d",
 523                  pp->size, pp->cat, pp->pos, pp->next);
 524 }
 525
 526
 527
 528 /* returns non-zero if item could be read; 0 otherwise */
 529 int isamh_pp_read (ISAMH_PP pp, void *buf)
 530 {
 531     return isamh_read_item (pp, (char **) &buf);
 532 }
 533
 534 /* read one item from file - decode and store it in *dst.
 535    Returns
 536      0 if end-of-file
 537      1 if item could be read ok and NO boundary
 538      2 if item could be read ok and boundary */
 539 int isamh_read_item (ISAMH_PP pp, char **dst)
 540 {
 541     ISAMH is = pp->is;
 542     char *src = pp->buf + pp->offset;
 543
 544     if (pp->offset >= pp->size)
 545     {
 546         if (!pp->next)
 547         {
 548             pp->pos = 0;
 549             return 0; /* end of file */
 550         }
 551         if (pp->next > pp->pos)
 552         {
 553             if (pp->next == pp->pos + 1)
 554                 is->files[pp->cat].no_next++;
 555             else
 556             {
 557                 is->files[pp->cat].no_forward++;
 558                 is->files[pp->cat].sum_forward += pp->next - pp->pos;
 559             }
 560         }
 561         else
 562         {
 563             if (pp->next + 1 == pp->pos)
 564                 is->files[pp->cat].no_prev++;
 565             else
 566             {
 567                 is->files[pp->cat].no_backward++;
 568                 is->files[pp->cat].sum_backward += pp->pos - pp->next;
 569             }
 570         }
 571         /* out new block position */
 572         pp->pos = pp->next;
 573         src = pp->buf;
 574         /* read block and save 'next' and 'size' entry */
 575         isamh_read_block (is, pp->cat, pp->pos, src);
 576         memcpy (&pp->next, src, sizeof(pp->next));
 577         src += sizeof(pp->next);
 578         memcpy (&pp->size, src, sizeof(pp->size));
 579         src += sizeof(pp->size);
 580         /* assume block is non-empty */
 581         assert (src - pp->buf == ISAMH_BLOCK_OFFSET_N);
 582         assert (pp->next != pp->pos);
 583         if (pp->deleteFlag)
 584             isamh_release_block (is, pp->cat, pp->pos);
 585         (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
 586         pp->offset = src - pp->buf;
 587         if (is->method->debug > 2)
 588             logf (LOG_LOG, "isc: read_block size=%d %d %d next=%d",
 589                  pp->size, pp->cat, pp->pos, pp->next);
 590         return 2;
 591     }
 592     (*is->method->code_item)(ISAMH_DECODE, pp->decodeClientData, dst, &src);
 593     pp->offset = src - pp->buf;
 594     return 1;
 595 }
 596
 597 int isamh_pp_num (ISAMH_PP pp)
 598 {
 599     return pp->numKeys;
 600 }
 601
 602 /*
 603  * $Log: isamh.c,v $
 604  * Revision 1.2  1999-07-06 09:37:05  heikki
 605  * Working on isamh - not ready yet.
 606  *
 607  * Revision 1.1  1999/06/30 15:04:54  heikki
 608  * Copied from isamc.c, slowly starting to simplify...
 609  *
 610  */