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.1  1996-10-29 13:40:48  adam
   8  * First work.
   9  *
  10  */
  11
  12 #include <stdlib.h>
  13 #include <assert.h>
  14 #include <string.h>
  15 #include <stdio.h>
  16
  17 #include <log.h>
  18 #include "isamc-p.h"
  19
  20 ISAMC_M isc_getmethod (void)
  21 {
  22     static struct ISAMC_filecat_s def_cat[] = {
  23         {   32,    28,     0,    20 },
  24         {  512,   490,   100,    20 },
  25         { 4096,  3950,  1000,    20 },
  26         {32768, 32000, 10000,     0 },
  27         {    0,     0,     0,     0 }
  28     };
  29     ISAMC_M m = xmalloc (sizeof(*m));
  30     m->filecat = def_cat;
  31
  32     m->code_start = NULL;
  33     m->code_item = NULL;
  34     m->code_stop = NULL;
  35
  36     m->compare_item = NULL;
  37
  38     m->debug = 0;
  39
  40     return m;
  41 }
  42
  43
  44 ISAMC isc_open (const char *name, int writeflag, ISAMC_M method)
  45 {
  46     ISAMC is;
  47     ISAMC_filecat filecat;
  48     int i;
  49     int max_buf_size = 0;
  50
  51     is = xmalloc (sizeof(*is));
  52
  53     is->method = xmalloc (sizeof(*is->method));
  54     memcpy (is->method, method, sizeof(*method));
  55     filecat = is->method->filecat;
  56     assert (filecat);
  57
  58     /* determine number of block categories */
  59     if (is->method->debug)
  60         logf (LOG_LOG, "isc: bsize  ifill  mfill mblocks");
  61     for (i = 0; filecat[i].bsize; i++)
  62     {
  63         if (is->method->debug)
  64             logf (LOG_LOG, "isc:%6d %6d %6d %6d",
  65                   filecat[i].bsize, filecat[i].ifill,
  66                   filecat[i].mfill, filecat[i].mblocks);
  67         if (max_buf_size < filecat[i].mblocks * filecat[i].bsize)
  68             max_buf_size = filecat[i].mblocks * filecat[i].bsize;
  69     }
  70     is->no_files = i;
  71     is->max_cat = --i;
  72     /* max_buf_size is the larget buffer to be used during merge */
  73     max_buf_size = (1 + max_buf_size / filecat[i].bsize) * filecat[i].bsize;
  74     if (is->method->debug)
  75         logf (LOG_LOG, "isc: max_buf_size %d", max_buf_size);
  76
  77     assert (is->no_files > 0);
  78     is->files = xmalloc (sizeof(*is->files)*i);
  79     is->r_buf = xmalloc (max_buf_size+128);
  80     for (i = 0; i<is->no_files; i++)
  81     {
  82         char fname[512];
  83
  84         sprintf (fname, "%s%c", name, i+'A');
  85         is->files[i].bf = bf_open (fname, is->method->filecat[i].bsize,
  86                                    writeflag);
  87         is->files[i].head_is_dirty = 0;
  88         if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
  89                      &is->files[i].head))
  90         {
  91             is->files[i].head.lastblock = 1;
  92             is->files[i].head.freelist = 0;
  93         }
  94     }
  95     return is;
  96 }
  97
  98 int isc_close (ISAMC is)
  99 {
 100     int i;
 101
 102     for (i = 0; i<is->no_files; i++)
 103         if (is->files[i].bf)
 104         {
 105             if (is->files[i].head_is_dirty)
 106                 bf_write (is->files[i].bf, 0, 0, sizeof(ISAMC_head),
 107                      &is->files[i].head);
 108             bf_close (is->files[i].bf);
 109         }
 110     xfree (is->files);
 111     xfree (is->r_buf);
 112     xfree (is);
 113     return 0;
 114 }
 115
 116 void isc_catpos (ISAMC_P ipos, int *cat, int *pos)
 117 {
 118     *pos = ipos >> 3;
 119     *cat = ipos & 7;
 120 }
 121
 122 int isc_read_block (ISAMC is, int cat, int pos, char *dst)
 123 {
 124     if (is->method->debug > 1)
 125         logf (LOG_LOG, "isc: read_block %d %d", cat, pos);
 126     return bf_read (is->files[cat].bf, pos, 0, 0, dst);
 127 }
 128
 129 int isc_write_block (ISAMC is, int cat, int pos, char *src)
 130 {
 131     if (is->method->debug > 1)
 132         logf (LOG_LOG, "isc: write_block %d %d", cat, pos);
 133     return bf_write (is->files[cat].bf, pos, 0, 0, src);
 134 }
 135
 136 int isc_write_dblock (ISAMC is, int cat, int pos, char *src,
 137                       int nextpos, int offset)
 138 {
 139     int xoffset = offset + 2*sizeof(int);
 140     if (is->method->debug > 2)
 141         logf (LOG_LOG, "isc: write_dblock. offset=%d nextpos=%d",
 142               offset, nextpos);
 143     memcpy (src - sizeof(int)*2, &nextpos, sizeof(int));
 144     memcpy (src - sizeof(int), &xoffset, sizeof(int));
 145     return isc_write_block (is, cat, pos, src - sizeof(int)*2);
 146 }
 147
 148 int isc_alloc_block (ISAMC is, int cat)
 149 {
 150     int block;
 151     char buf[sizeof(int)];
 152
 153     is->files[cat].head_is_dirty = 1;
 154     if ((block = is->files[cat].head.freelist))
 155     {
 156         bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
 157         memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
 158     }
 159     else
 160         block = (is->files[cat].head.lastblock)++;
 161     if (is->method->debug > 2)
 162         logf (LOG_LOG, "isc: alloc_block in cat %d -> %d", cat, block);
 163     return block;
 164 }
 165
 166 void isc_release_block (ISAMC is, int cat, int pos)
 167 {
 168     char buf[sizeof(int)];
 169
 170     is->files[cat].head_is_dirty = 1;
 171     memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
 172     is->files[cat].head.freelist = pos;
 173     bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
 174 }
 175
 176 static void isc_flush_blocks (ISAMC is, int *r_ptr, int r_ptri, char *r_buf,
 177                               int *nextpos, int *firstpos, int cat, int last)
 178 {
 179     int i;
 180
 181     for (i = 1; i<r_ptri; i++)
 182     {
 183         int pos;
 184         if (*nextpos)
 185             pos = *nextpos;
 186         else
 187             pos = isc_alloc_block (is, cat);
 188         if (!*firstpos)
 189             *firstpos = pos;
 190         if (last && i == r_ptri-1)
 191             *nextpos = 0;
 192         else
 193             *nextpos = isc_alloc_block (is, cat);
 194         isc_write_dblock (is, cat, pos, r_buf + r_ptr[i-1], *nextpos,
 195                           r_ptr[i] - r_ptr[i-1]);
 196     }
 197 }
 198
 199
 200 ISAMC_P isc_merge_first (ISAMC is, ISAMC_I data)
 201 {
 202     char i_item[128], *i_item_ptr;
 203     int i_more, i_mode, i;
 204
 205     int firstpos = 0;
 206     int nextpos = 0;
 207     int cat = 0;
 208     char r_item_buf[128];
 209     int r_offset = 0;
 210     int r_ptr[100];
 211     int r_ptri = 0;
 212     void *r_clientData = (*is->method->code_start)(ISAMC_ENCODE);
 213     char *r_buf = is->r_buf + ISAMC_BLOCK_OFFSET;
 214
 215     /* read first item from i */
 216     i_item_ptr = i_item;
 217     i_more = (*data->read_item)(data->clientData, &i_item_ptr, &i_mode);
 218     if (i_more)
 219         r_ptr[r_ptri++] = 0;
 220     while (i_more)
 221     {
 222         char *r_item = r_item_buf;
 223
 224         memcpy (r_item, i_item, i_item_ptr - i_item);
 225
 226         if (r_item)  /* insert resulting item? */
 227         {
 228             char *r_out_ptr = r_buf + r_offset;
 229             int new_offset;
 230             int border = r_ptr[r_ptri-1] + is->method->filecat[cat].ifill
 231                          -ISAMC_BLOCK_OFFSET;
 232
 233             (*is->method->code_item)(ISAMC_ENCODE, r_clientData,
 234                                      &r_out_ptr, &r_item);
 235             new_offset = r_out_ptr - r_buf;
 236
 237             if (border >= r_offset && border < new_offset)
 238             {
 239                 /* Initial fill of current block category reached...
 240                    Save offset in r_ptr
 241                  */
 242                 r_ptr[r_ptri++] = r_offset;
 243                 if (cat == is->max_cat)
 244                 {
 245                     /* We are dealing with block of max size. Block(s)
 246                        will be flushed. Note: the block(s) are surely not
 247                        the last one(s).
 248                      */
 249                     if (is->method->debug > 1)
 250                         logf (LOG_LOG, "isc: flush %d sections", r_ptri-1);
 251                     isc_flush_blocks (is, r_ptr, r_ptri, r_buf,
 252                                       &nextpos, &firstpos, cat, 0);
 253                     r_ptri = 0;
 254                     r_ptr[r_ptri++] = 0;
 255                     memcpy (r_buf, r_buf + r_offset, new_offset - r_offset);
 256                     new_offset = (new_offset - r_offset);
 257                 }
 258             }
 259             r_offset = new_offset;
 260             if (cat < is->max_cat &&
 261                 r_ptri>is->method->filecat[cat].mblocks)
 262             {
 263                 /* Max number blocks in current category reached ->
 264                    must switch to next category (with larger block size)
 265                 */
 266                 int j = 1;
 267                 cat++;
 268                 /* r_ptr[0] = r_ptr[0] = 0 true anyway.. */
 269                 for (i = 2; i < r_ptri; i++)
 270                 {
 271                     border = is->method->filecat[cat].ifill -
 272                              ISAMC_BLOCK_OFFSET + r_ptr[j-1];
 273                     if (r_ptr[i] > border && r_ptr[i-1] <= border)
 274                         r_ptr[j++] = r_ptr[i-1];
 275                 }
 276                 r_ptri = j;
 277             }
 278         }
 279         i_item_ptr = i_item;
 280         i_more = (*data->read_item)(data->clientData, &i_item_ptr, &i_mode);
 281     }
 282     r_ptr[r_ptri++] = r_offset;
 283     /* flush rest of block(s) in r_buf */
 284     if (is->method->debug > 1)
 285         logf (LOG_LOG, "isc: flush rest, %d sections", r_ptri-1);
 286     isc_flush_blocks (is, r_ptr, r_ptri, r_buf, &nextpos, &firstpos, cat, 1);
 287     (*is->method->code_stop)(ISAMC_ENCODE, r_clientData);
 288     return cat + firstpos * 8;
 289 }
 290
 291 ISAMC_P isc_merge (ISAMC is, ISAMC_P ipos, ISAMC_I data)
 292 {
 293     assert (ipos == 0);
 294     return isc_merge_first (is, data);
 295 }
 296
 297
 298 #if 0
 299 ISAMC_P isc_merge (ISAMC is, ISAMC_P ipos, ISAMC_I data)
 300 {
 301     ISAMC_PP pp;
 302     char f_item[128], *f_item_ptr;
 303     int f_more;
 304     int cat = 0;
 305     int nextpos;
 306
 307     char i_item[128], *i_item_ptr;
 308     int i_more, insertMode;
 309
 310     char r_item_buf[128];
 311     int r_offset = ISAMC_BLOCK_OFFSET;
 312     int r_dirty = 0;
 313     char *r_ptr[100];
 314     int r_ptri = 0;
 315     int r_start = 0;
 316     void *r_clientData = (*is->method->code_start)();
 317
 318     /* rewind and read first item from file */
 319     pp = isc_position (is, ipos);
 320     f_item_ptr = f_item;
 321     f_more = isc_read_item (pp, &f_item_ptr);
 322     cat = pp->cat;
 323
 324     /* read first item from i */
 325     i_item_ptr = i_item;
 326     i_more = (*data->read_item)(data->clientData, &i_item_ptr, &insertMode);
 327
 328     while (f_more || i_more)
 329     {
 330         int cmp;
 331         char *r_item = r_item_buf;
 332
 333         if (!f_more)
 334             cmp = -1;
 335         else if (!i_more)
 336             cmp = 1;
 337         else
 338             cmp = (*is->method->compare_item)(i_item, f_item);
 339         if (cmp == 0)                   /* insert i=f */
 340         {
 341             if (!insertMode)
 342             {
 343                 r_item = NULL;
 344                 r_dirty = 1;
 345             }
 346             else
 347                 memcpy (r_item, f_item, f_item_ptr - f_item);
 348
 349             /* move i */
 350             i_item_ptr = i_item;
 351             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 352                                         &insertMode);
 353             /* move f */
 354             f_item_ptr = f_item;
 355             f_more = isc_read_item (pp, &f_item_ptr);
 356         }
 357         else if (cmp > 0)               /* insert f */
 358         {
 359             memcpy (r_item, f_item, f_item_ptr - f_item);
 360             /* move f */
 361             f_item_ptr = f_item;
 362             f_more = isc_read_item (pp, &f_item_ptr);
 363         }
 364         else                            /* insert i */
 365         {
 366             if (!insertMode)            /* delete item which isn't there? */
 367             {
 368                 logf (LOG_FATAL, "Inconsistent register");
 369                 abort ();
 370             }
 371             memcpy (r_item, i_item, i_item_ptr - i_item);
 372             r_dirty = 1;
 373             /* move i */
 374             i_item_ptr = i_item;
 375             i_more = (*data->read_item)(data->clientData, &i_item_ptr,
 376                                         &insertMode);
 377         }
 378         /* check for end of input block condition */
 379
 380         if (r_item)  /* insert resulting item? */
 381         {
 382             char *r_out_ptr = is->r_buf + r_offset;
 383             int new_offset;
 384             int border = is->method->filecat[cat].initsize - r_start;
 385
 386             (*is->method->code_item)(r_clientData, &r_out_ptr, &r_item);
 387             new_offset = r_out_ptr - is->r_buf;
 388
 389             if (border >= r_offset && border < r_newoffset)
 390             {
 391                 r_ptr[r_ptri++] = r_offset;
 392                 if (!is->method->filecat[cat].mblocks)
 393                 {
 394                     assert (r_ptri == 1);
 395                     /* dump block from 0 -> r_offset in max cat */
 396                     r_ptri = 0;
 397                     r_offset = ISAMC_BLOCK_OFFSET;
 398                 }
 399             }
 400             r_offset = new_offset;
 401         }
 402         if (r_ptri && r_ptri == is->method->filecat[cat].mblocks)
 403         {
 404             int i, j = 0;
 405
 406             /* dump previous blocks in chain */
 407
 408             /* recalc r_ptr's */
 409             cat++;
 410             for (i = 1; i<r_ptr; i++)
 411             {
 412                 if (r_ptr[i] > is->method->filecat[cat].ifill &&
 413                     r_ptr[i-1] <= is->method->filecat[cat].ifill)
 414                     r_ptr[j++] = r_ptr[i-1];
 415             }
 416             r_ptri = j;
 417         }
 418     }
 419     (*is->method->code_stop)(r_clientData);
 420     return ipos;
 421 }
 422 #endif
 423
 424 void isc_pp_close (ISAMC_PP pp)
 425 {
 426     ISAMC is = pp->is;
 427
 428     (*is->method->code_stop)(ISAMC_DECODE, pp->decodeClientData);
 429     xfree (pp->buf);
 430     xfree (pp);
 431 }
 432
 433 ISAMC_PP isc_pp_open (ISAMC is, ISAMC_P ipos)
 434 {
 435     ISAMC_PP pp = xmalloc (sizeof(*pp));
 436     char *src;
 437
 438     isc_catpos (ipos, &pp->cat, &pp->next);
 439
 440     src = pp->buf = xmalloc (is->method->filecat[pp->cat].bsize);
 441
 442     pp->pos = 0;
 443     pp->size = 0;
 444     pp->offset = 0;
 445     pp->is = is;
 446     pp->decodeClientData = (*is->method->code_start)(ISAMC_DECODE);
 447     return pp;
 448 }
 449
 450 /* returns 1 if item could be read; 0 otherwise */
 451 int isc_read_key (ISAMC_PP pp, void *buf)
 452 {
 453     return isc_read_item (pp, (char **) &buf);
 454 }
 455
 456 /* returns 1 if item could be read; 0 otherwise */
 457 int isc_read_item (ISAMC_PP pp, char **dst)
 458 {
 459     ISAMC is = pp->is;
 460     char *src = pp->buf + pp->offset;
 461
 462     if (pp->offset >= pp->size)
 463     {
 464         pp->pos = pp->next;
 465         if (!pp->pos)
 466             return 0;
 467         src = pp->buf;
 468         isc_read_block (is, pp->cat, pp->pos, src);
 469
 470         memcpy (&pp->next, src, sizeof(pp->next));
 471         src += sizeof(pp->next);
 472         memcpy (&pp->size, src, sizeof(pp->size));
 473         src += sizeof(pp->size);
 474         /* assume block is non-empty */
 475         assert (pp->next != pp->pos);
 476     }
 477     (*is->method->code_item)(ISAMC_DECODE, pp->decodeClientData, dst, &src);
 478     pp->offset = src - pp->buf;
 479     return 1;
 480 }
 481
 482 int isc_read_islast (ISAMC_PP pp)
 483 {
 484     return pp->offset >= pp->size;
 485 }
 486
 487 int isc_numkeys (ISAMC_PP pp)
 488 {
 489     return 1;
 490 }
 491