isamc/isamc.c

   1 /*
   2  * Copyright (c) 1995-1996, Index Data.
   3  * See the file LICENSE for details.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: isamc.c,v $
   7  * Revision 1.2  1996-10-29 16:44:56  adam
   8  * Work on isc_merge.
   9  *
  10  * Revision 1.1  1996/10/29  13:40:48  adam
  11  * First work.
  12  *
  13  */
  14
  15 #include <stdlib.h>
  16 #include <assert.h>
  17 #include <string.h>
  18 #include <stdio.h>
  19
  20 #include <log.h>
  21 #include "isamc-p.h"
  22
  23 ISAMC_M isc_getmethod (void)
  24 {
  25     static struct ISAMC_filecat_s def_cat[] = {
  26         {   32,    28,     0,    20 },
  27         {  512,   490,   100,    20 },
  28         { 4096,  3950,  1000,    20 },
  29         {32768, 32000, 10000,     0 },
  30         {    0,     0,     0,     0 }
  31     };
  32     ISAMC_M m = xmalloc (sizeof(*m));
  33     m->filecat = def_cat;
  34
  35     m->code_start = NULL;
  36     m->code_item = NULL;
  37     m->code_stop = NULL;
  38
  39     m->compare_item = NULL;
  40
  41     m->debug = 0;
  42
  43     return m;
  44 }
  45
  46
  47 ISAMC isc_open (const char *name, int writeflag, ISAMC_M method)
  48 {
  49     ISAMC is;
  50     ISAMC_filecat filecat;
  51     int i;
  52     int max_buf_size = 0;
  53
  54     is = xmalloc (sizeof(*is));
  55
  56     is->method = xmalloc (sizeof(*is->method));
  57     memcpy (is->method, method, sizeof(*method));
  58     filecat = is->method->filecat;
  59     assert (filecat);
  60
  61     /* determine number of block categories */
  62     if (is->method->debug)
  63         logf (LOG_LOG, "isc: bsize  ifill  mfill mblocks");
  64     for (i = 0; filecat[i].bsize; i++)
  65     {
  66         if (is->method->debug)
  67             logf (LOG_LOG, "isc:%6d %6d %6d %6d",
  68                   filecat[i].bsize, filecat[i].ifill,
  69                   filecat[i].mfill, filecat[i].mblocks);
  70         if (max_buf_size < filecat[i].mblocks * filecat[i].bsize)
  71             max_buf_size = filecat[i].mblocks * filecat[i].bsize;
  72     }
  73     is->no_files = i;
  74     is->max_cat = --i;
  75     /* max_buf_size is the larget buffer to be used during merge */
  76     max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
  77     if (is->method->debug)
  78         logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
  79
  80     assert (is->no_files > 0);
  81     is->files = xmalloc (sizeof(*is->files)*i);
  82     is->r_buf = xmalloc (max_buf_size+128);
  83     for (i = 0; i<is->no_files; i++)
  84     {
  85         char fname[512];
  86
  87         sprintf (fname, "%s%c", name, i+'A');
  88         is->files[i].bf = bf_open (fname, is->method->filecat[i].bsize,
  89                                    writeflag);
  90         is->files[i].head_is_dirty = 0;
  91         if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
  92                      &is->files[i].head))
  93         {
  94             is->files[i].head.lastblock = 1;
  95             is->files[i].head.freelist = 0;
  96         }
  97     }
  98     return is;
  99 }
 100
 101 int isc_close (ISAMC is)
 102 {
 103     int i;
 104
 105     for (i = 0; i<is->no_files; i++)
 106         if (is->files[i].bf)
 107         {
 108             if (is->files[i].head_is_dirty)
 109                 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
 110                      &is->files[i].head);
 111             bf_close (is->files[i].bf);
 112         }
 113     xfree (is->files);
 114     xfree (is->r_buf);
 115     xfree (is);
 116     return 0;
 117 }
 118
 119 int isc_read_block (ISAMC is, int cat, int pos, char *dst)
 120 {
 121     if (is->method->debug > 1)
 122         logf (LOG_LOG, "isc: read_block %d %d", cat, pos);
 123     return bf_read (is->files[cat].bf, pos, 0, 0, dst);
 124 }
 125
 126 int isc_write_block (ISAMC is, int cat, int pos, char *src)
 127 {
 128     if (is->method->debug > 1)
 129         logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
 130     return bf_write (is->files[cat].bf, pos, 0, 0, src);
 131 }
 132
 133 int isc_write_dblock (ISAMC is, int cat, int pos, char *src,
 134                       int nextpos, int offset)
 135 {
 136     int xoffset = offset + 2*sizeof(int);
 137     if (is->method->debug > 2)
 138         logf (LOG_LOG, "isc: write_dblock. offset=%d nextpos=%d",
 139               offset, nextpos);
 140     memcpy (src - sizeof(int)*2, &nextpos, sizeof(int));
 141     memcpy (src - sizeof(int), &xoffset, sizeof(int));
 142     return isc_write_block (is, cat, pos, src - sizeof(int)*2);
 143 }
 144
 145 int isc_alloc_block (ISAMC is, int cat)
 146 {
 147     int block;
 148     char buf[sizeof(int)];
 149
 150     is->files[cat].head_is_dirty = 1;
 151     if ((block = is->files[cat].head.freelist))
 152     {
 153         bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
 154         memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
 155     }
 156     else
 157         block = (is->files[cat].head.lastblock)++;
 158     if (is->method->debug > 2)
 159         logf (LOG_LOG, "isc: alloc_block in cat %d -> %d", cat, block);
 160     return block;
 161 }
 162
 163 void isc_release_block (ISAMC is, int cat, int pos)
 164 {
 165     char buf[sizeof(int)];
 166
 167     is->files[cat].head_is_dirty = 1;
 168     memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
 169     is->files[cat].head.freelist = pos;
 170     bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
 171 }
 172
 173 static void isc_flush_blocks (ISAMC is, int *r_ptr, int r_ptri, char *r_buf,
 174                               int *nextpos, int *firstpos, int cat, int last)
 175 {
 176     int i;
 177
 178     for (i = 1; i<r_ptri; i++)
 179     {
 180         int pos;
 181         if (*nextpos)
 182             pos = *nextpos;
 183         else
 184             pos = isc_alloc_block (is, cat);
 185         if (!*firstpos)
 186             *firstpos = pos;
 187         if (last && i == r_ptri-1)
 188             *nextpos = 0;
 189         else
 190             *nextpos = isc_alloc_block (is, cat);
 191         isc_write_dblock (is, cat, pos, r_buf + r_ptr[i-1], *nextpos,
 192                           r_ptr[i] - r_ptr[i-1]);
 193     }
 194 }
 195
 196
 197 ISAMC_P isc_merge_first (ISAMC is, ISAMC_I data)
 198 {
 199     char i_item[128], *i_item_ptr;
 200     int i_more, i_mode, i;
 201
 202     int firstpos = 0;
 203     int nextpos = 0;
 204     int cat = 0;
 205     char r_item_buf[128];
 206     int r_offset = 0;
 207     int r_ptr[100];
 208     int r_ptri = 0;
 209     void *r_clientData = (*is->method->code_start)(ISAMC_ENCODE);
 210     char *r_buf = is->r_buf + ISAMC_BLOCK_OFFSET;
 211
 212     /* read first item from i */
 213     i_item_ptr = i_item;
 214     i_more = (*data->read_item)(data->clientData, &i_item_ptr, &i_mode);
 215     if (i_more)
 216         r_ptr[r_ptri++] = 0;
 217     while (i_more)
 218     {
 219         char *r_item = r_item_buf;
 220
 221         memcpy (r_item, i_item, i_item_ptr - i_item);
 222
 223         if (r_item)  /* insert resulting item? */
 224         {
 225             char *r_out_ptr = r_buf + r_offset;
 226             int new_offset;
 227             int border = r_ptr[r_ptri-1] + is->method->filecat[cat].ifill
 228                          -ISAMC_BLOCK_OFFSET;
 229
 230             (*is->method->code_item)(ISAMC_ENCODE, r_clientData,
 231                                      &r_out_ptr, &r_item);
 232             new_offset = r_out_ptr - r_buf;
 233
 234             if (border >= r_offset && border < new_offset)
 235             {
 236                 /* Initial fill of current block category reached...
 237                    Save offset in r_ptr
 238                  */
 239                 r_ptr[r_ptri++] = r_offset;
 240                 if (cat == is->max_cat)
 241                 {
 242                     /* We are dealing with block of max size. Block(s)
 243                        will be flushed. Note: the block(s) are surely not
 244                        the last one(s).
 245                      */
 246                     if (is->method->debug > 1)
 247                         logf (LOG_LOG, "isc: flush %d sections", r_ptri-1);
 248                     isc_flush_blocks (is, r_ptr, r_ptri, r_buf,
 249                                       &nextpos, &firstpos, cat, 0);
 250                     r_ptri = 0;
 251                     r_ptr[r_ptri++] = 0;
 252                     memcpy (r_buf, r_buf + r_offset, new_offset - r_offset);
 253                     new_offset = (new_offset - r_offset);
 254                 }
 255             }
 256             r_offset = new_offset;
 257             if (cat < is->max_cat &&
 258                 r_ptri>is->method->filecat[cat].mblocks)
 259             {
 260                 /* Max number blocks in current category reached ->
 261                    must switch to next category (with larger block size)
 262                 */
 263                 int j = 1;
 264                 cat++;
 265                 /* r_ptr[0] = r_ptr[0] = 0 true anyway.. */
 266                 for (i = 2; i < r_ptri; i++)
 267                 {
 268                     border = is->method->filecat[cat].ifill -
 269                              ISAMC_BLOCK_OFFSET + r_ptr[j-1];
 270                     if (r_ptr[i] > border && r_ptr[i-1] <= border)
 271                         r_ptr[j++] = r_ptr[i-1];
 272                 }
 273                 r_ptri = j;
 274             }
 275         }
 276         i_item_ptr = i_item;
 277         i_more = (*data->read_item)(data->clientData, &i_item_ptr, &i_mode);
 278     }
 279     r_ptr[r_ptri++] = r_offset;
 280     /* flush rest of block(s) in r_buf */
 281     if (is->method->debug > 1)
 282         logf (LOG_LOG, "isc: flush rest, %d sections", r_ptri-1);
 283     isc_flush_blocks (is, r_ptr, r_ptri, r_buf, &nextpos, &firstpos, cat, 1);
 284     (*is->method->code_stop)(ISAMC_ENCODE, r_clientData);
 285     return cat + firstpos * 8;
 286 }
 287
 288 ISAMC_P isc_merge (ISAMC is, ISAMC_P ipos, ISAMC_I data)
 289 {
 290     char i_item[128], *i_item_ptr;
 291     int i_more, i_mode, i;
 292
 293     ISAMC_PP pp;
 294     char f_item[128], *f_item_ptr;
 295     int f_more;
 296     int block_ptr[100];   /* block pointer (0 if none) */
 297     int dirty_ptr[100];   /* dirty flag pointer (1 if dirty) */
 298
 299     int firstpos = 0;
 300     int nextpos = 0;
 301     int cat = 0;
 302     char r_item_buf[128]; /* temporary result output */
 303     char *r_buf;          /* block with resulting data */
 304     int r_offset = 0;     /* current offset in r_buf */
 305     int r_ptr[100];       /* offset pointer */
 306     int r_ptri = 0;       /* pointer */
 307     void *r_clientData;   /* encode client data */
 308
 309     if (ipos == 0)
 310         return isc_merge_first (is, data);
 311
 312     r_clientData = (*is->method->code_start)(ISAMC_ENCODE);
 313     r_buf = is->r_buf + ISAMC_BLOCK_OFFSET;
 314
 315     pp = isc_pp_open (is, ipos);
 316     f_item_ptr = f_item;
 317     f_more = isc_read_item (pp, &f_item_ptr);
 318     cat = pp->cat;
 319
 320     /* read first item from i */
 321     i_item_ptr = i_item;
 322     i_more = (*data->read_item)(data->clientData, &i_item_ptr, &i_mode);
 323     block_ptr[r_ptri] = pp->pos;
 324     dirty_ptr[r_ptri] = 0;
 325     r_ptr[r_ptri++] = 0;
 326
 327     while (i_more || f_more)
 328     {
 329         char *r_item = r_item_buf;
 330         int cmp;
 331
 332         if (!f_more)
 333             cmp = -1;
 334         else if (!i_more)
 335             cmp = 1;
 336         else
 337             cmp = (*is->method->compare_item)(i_item, f_item);
 338         if (cmp == 0)                   /* insert i=f */
 339         {
 340             if (!i_mode)
 341             {
 342                 r_item = NULL;
 343                 dirty_ptr[r_ptri-1] = 1;
 344             }
 345             else
 346                 memcpy (r_item, f_item, f_item_ptr - f_item);
 347
 348             /* move i */
 349             i_item_ptr = i_item;
 350             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 351                                         &i_mode);
 352             /* move f */
 353             f_item_ptr = f_item;
 354             f_more = isc_read_item (pp, &f_item_ptr);
 355         }
 356         else if (cmp > 0)               /* insert f */
 357         {
 358             memcpy (r_item, f_item, f_item_ptr - f_item);
 359             /* move f */
 360             f_item_ptr = f_item;
 361             f_more = isc_read_item (pp, &f_item_ptr);
 362         }
 363         else                            /* insert i */
 364         {
 365             if (!i_mode)                /* delete item which isn't there? */
 366             {
 367                 logf (LOG_FATAL, "Inconsistent register");
 368                 abort ();
 369             }
 370             memcpy (r_item, i_item, i_item_ptr - i_item);
 371             dirty_ptr[r_ptri-1] = 1;
 372             /* move i */
 373             i_item_ptr = i_item;
 374             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 375                                         &i_mode);
 376         }
 377         if (r_item)  /* insert resulting item? */
 378         {
 379             char *r_out_ptr = r_buf + r_offset;
 380             int new_offset;
 381             int border;
 382
 383             /* border set to initial fill or block size depending on
 384                whether we are creating a new one or updating and old
 385              */
 386             if (block_ptr[r_ptri-1])
 387                 border = r_ptr[r_ptri-1] + is->method->filecat[cat].bsize
 388                          -ISAMC_BLOCK_OFFSET;
 389             else
 390                 border = r_ptr[r_ptri-1] + is->method->filecat[cat].ifill
 391                          -ISAMC_BLOCK_OFFSET;
 392
 393             (*is->method->code_item)(ISAMC_ENCODE, r_clientData,
 394                                      &r_out_ptr, &r_item);
 395             new_offset = r_out_ptr - r_buf;
 396
 397             if (border >= r_offset && border < new_offset)
 398             {
 399                 /* Initial fill of current block category reached...
 400                    Save offset in r_ptr
 401                  */
 402                 r_ptr[r_ptri++] = r_offset;
 403                 if (cat == is->max_cat)
 404                 {
 405                     /* We are dealing with block of max size. Block(s)
 406                        will be flushed. Note: the block(s) are surely not
 407                        the last one(s).
 408                      */
 409                     if (is->method->debug > 1)
 410                         logf (LOG_LOG, "isc: flush %d sections", r_ptri-1);
 411                     isc_flush_blocks (is, r_ptr, r_ptri, r_buf,
 412                                       &nextpos, &firstpos, cat, 0);
 413                     r_ptri = 0;
 414                     r_ptr[r_ptri++] = 0;
 415                     memcpy (r_buf, r_buf + r_offset, new_offset - r_offset);
 416                     new_offset = (new_offset - r_offset);
 417                 }
 418             }
 419             r_offset = new_offset;
 420             if (cat < is->max_cat &&
 421                 r_ptri>is->method->filecat[cat].mblocks)
 422             {
 423                 /* Max number blocks in current category reached ->
 424                    must switch to next category (with larger block size)
 425                 */
 426                 int j = 1;
 427                 cat++;
 428                 /* r_ptr[0] = r_ptr[0] = 0 true anyway.. */
 429                 /* AD: Any old blocks should be deleted */
 430                 for (i = 2; i < r_ptri; i++)
 431                 {
 432                     border = is->method->filecat[cat].ifill -
 433                              ISAMC_BLOCK_OFFSET + r_ptr[j-1];
 434                     if (r_ptr[i] > border && r_ptr[i-1] <= border)
 435                         r_ptr[j++] = r_ptr[i-1];
 436                 }
 437                 r_ptri = j;
 438             }
 439         }
 440     }
 441     r_ptr[r_ptri++] = r_offset;
 442     /* flush rest of block(s) in r_buf */
 443     if (is->method->debug > 1)
 444         logf (LOG_LOG, "isc: flush rest, %d sections", r_ptri-1);
 445     isc_flush_blocks (is, r_ptr, r_ptri, r_buf, &nextpos, &firstpos, cat, 1);
 446     (*is->method->code_stop)(ISAMC_ENCODE, r_clientData);
 447     return cat + firstpos * 8;
 448 }
 449
 450
 451 #if 0
 452 ISAMC_P isc_merge (ISAMC is, ISAMC_P ipos, ISAMC_I data)
 453 {
 454     ISAMC_PP pp;
 455     char f_item[128], *f_item_ptr;
 456     int f_more;
 457     int cat = 0;
 458     int nextpos;
 459
 460     char i_item[128], *i_item_ptr;
 461     int i_more, insertMode;
 462
 463     char r_item_buf[128];
 464     int r_offset = ISAMC_BLOCK_OFFSET;
 465     int r_dirty = 0;
 466     char *r_ptr[100];
 467     int r_ptri = 0;
 468     int r_start = 0;
 469     void *r_clientData = (*is->method->code_start)();
 470
 471     /* rewind and read first item from file */
 472     pp = isc_position (is, ipos);
 473     f_item_ptr = f_item;
 474     f_more = isc_read_item (pp, &f_item_ptr);
 475     cat = pp->cat;
 476
 477     /* read first item from i */
 478     i_item_ptr = i_item;
 479     i_more = (*data->read_item)(data->clientData, &i_item_ptr, &insertMode);
 480
 481     while (f_more || i_more)
 482     {
 483         int cmp;
 484         char *r_item = r_item_buf;
 485
 486         if (!f_more)
 487             cmp = -1;
 488         else if (!i_more)
 489             cmp = 1;
 490         else
 491             cmp = (*is->method->compare_item)(i_item, f_item);
 492         if (cmp == 0)                   /* insert i=f */
 493         {
 494             if (!insertMode)
 495             {
 496                 r_item = NULL;
 497                 r_dirty = 1;
 498             }
 499             else
 500                 memcpy (r_item, f_item, f_item_ptr - f_item);
 501
 502             /* move i */
 503             i_item_ptr = i_item;
 504             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 505                                         &insertMode);
 506             /* move f */
 507             f_item_ptr = f_item;
 508             f_more = isc_read_item (pp, &f_item_ptr);
 509         }
 510         else if (cmp > 0)               /* insert f */
 511         {
 512             memcpy (r_item, f_item, f_item_ptr - f_item);
 513             /* move f */
 514             f_item_ptr = f_item;
 515             f_more = isc_read_item (pp, &f_item_ptr);
 516         }
 517         else                            /* insert i */
 518         {
 519             if (!insertMode)            /* delete item which isn't there? */
 520             {
 521                 logf (LOG_FATAL, "Inconsistent register");
 522                 abort ();
 523             }
 524             memcpy (r_item, i_item, i_item_ptr - i_item);
 525             r_dirty = 1;
 526             /* move i */
 527             i_item_ptr = i_item;
 528             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 529                                         &insertMode);
 530         }
 531         /* check for end of input block condition */
 532
 533         if (r_item)  /* insert resulting item? */
 534         {
 535             char *r_out_ptr = is->r_buf + r_offset;
 536             int new_offset;
 537             int border = is->method->filecat[cat].initsize - r_start;
 538
 539             (*is->method->code_item)(r_clientData, &r_out_ptr, &r_item);
 540             new_offset = r_out_ptr - is->r_buf;
 541
 542             if (border >= r_offset && border < r_newoffset)
 543             {
 544                 r_ptr[r_ptri++] = r_offset;
 545                 if (!is->method->filecat[cat].mblocks)
 546                 {
 547                     assert (r_ptri == 1);
 548                     /* dump block from 0 -> r_offset in max cat */
 549                     r_ptri = 0;
 550                     r_offset = ISAMC_BLOCK_OFFSET;
 551                 }
 552             }
 553             r_offset = new_offset;
 554         }
 555         if (r_ptri && r_ptri == is->method->filecat[cat].mblocks)
 556         {
 557             int i, j = 0;
 558
 559             /* dump previous blocks in chain */
 560
 561             /* recalc r_ptr's */
 562             cat++;
 563             for (i = 1; i<r_ptr; i++)
 564             {
 565                 if (r_ptr[i] > is->method->filecat[cat].ifill &&
 566                     r_ptr[i-1] <= is->method->filecat[cat].ifill)
 567                     r_ptr[j++] = r_ptr[i-1];
 568             }
 569             r_ptri = j;
 570         }
 571     }
 572     (*is->method->code_stop)(r_clientData);
 573     return ipos;
 574 }
 575 #endif
 576
 577 void isc_pp_close (ISAMC_PP pp)
 578 {
 579     ISAMC is = pp->is;
 580
 581     (*is->method->code_stop)(ISAMC_DECODE, pp->decodeClientData);
 582     xfree (pp->buf);
 583     xfree (pp);
 584 }
 585
 586 ISAMC_PP isc_pp_open (ISAMC is, ISAMC_P ipos)
 587 {
 588     ISAMC_PP pp = xmalloc (sizeof(*pp));
 589     char *src;
 590
 591     pp->cat = isc_type(ipos);
 592     pp->next = isc_block(ipos);
 593
 594     src = pp->buf = xmalloc (is->method->filecat[pp->cat].bsize);
 595
 596     pp->pos = 0;
 597     pp->size = 0;
 598     pp->offset = 0;
 599     pp->is = is;
 600     pp->decodeClientData = (*is->method->code_start)(ISAMC_DECODE);
 601     return pp;
 602 }
 603
 604 /* returns 1 if item could be read; 0 otherwise */
 605 int isc_read_key (ISAMC_PP pp, void *buf)
 606 {
 607     return isc_read_item (pp, (char **) &buf);
 608 }
 609
 610 /* returns 1 if item could be read; 0 otherwise */
 611 int isc_read_item (ISAMC_PP pp, char **dst)
 612 {
 613     ISAMC is = pp->is;
 614     char *src = pp->buf + pp->offset;
 615
 616     if (pp->offset >= pp->size)
 617     {
 618         pp->pos = pp->next;
 619         if (!pp->pos)
 620             return 0;
 621         src = pp->buf;
 622         isc_read_block (is, pp->cat, pp->pos, src);
 623
 624         memcpy (&pp->next, src, sizeof(pp->next));
 625         src += sizeof(pp->next);
 626         memcpy (&pp->size, src, sizeof(pp->size));
 627         src += sizeof(pp->size);
 628         /* assume block is non-empty */
 629         assert (pp->next != pp->pos);
 630     }
 631     (*is->method->code_item)(ISAMC_DECODE, pp->decodeClientData, dst, &src);
 632     pp->offset = src - pp->buf;
 633     return 1;
 634 }
 635
 636 int isc_read_islast (ISAMC_PP pp)
 637 {
 638     return pp->offset >= pp->size;
 639 }
 640
 641 int isc_numkeys (ISAMC_PP pp)
 642 {
 643     return 1;
 644 }
 645