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