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