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