isamc/merge-d.c

   1 /*
   2  * Copyright (c) 1996-1998, Index Data.
   3  * See the file LICENSE for details.
   4  * Heikki Levanto
   5  *
   6  * $Id: merge-d.c,v 1.17 1999-08-24 13:17:42 heikki Exp $
   7  *
   8  * missing
   9  *
  10  * optimize
  11  *  - Input filter: Eliminate del-ins pairs, tell if only one entry (or none)
  12  *  - single-entry optimizing (keep the one entry in the dict, no block)
  13  *  - study and optimize block sizes (later)
  14  *  - Clean up the different ways diffs are handled in writing and reading
  15  *  - Keep a merge-count in the firstpp, and if the block has already been
  16  *    merged, reduce it to a larger size even if it could fit in a small one!
  17  *  - Keep minimum freespace in the category table, and use that in reduce!
  18  *  - pass a space-needed for separateDiffBlock and reduce to be able to
  19  *    reserve more room for diffs, or to force a separate (larger?) block
  20  *  - Idea: Simplify the structure, so that the first block is always diffs.
  21  *    On small blocks, that is all we have. Once a block has been merged, we
  22  *    allocate the first main block and a (new) firstblock ffor diffs. From
  23  *    that point on the word has two blocks for it.
  24  *  - On allocating more blocks (in append), check the order of blocks, and
  25  *    if needed, swap them.
  26  *  - In merge, merge also with the input data.
  27  *
  28  * bugs
  29  *
  30  * caveat
  31  *  There is a confusion about the block addresses. cat or type is the category,
  32  *  pos or block is the block number. pp structures keep these two separate,
  33  *  and combine when saving the pp. The next pointer in the pp structure is
  34  *  also a combined address, but needs to be combined every time it is needed,
  35  *  and separated when the partss are needed... This is done with the isamd_
  36  *  _block, _type, and _addr macros. The _addr takes block and type as args,
  37  *  in that order. This conflicts with the order these are often mentioned in
  38  *  the debug log calls, and other places, leading to small mistakes here
  39  *  and there.
  40  *
  41  *  Needs cleaning! The way diff blocks are handled in append and reading is
  42  *  quite different, and likely to give maintenance problems.
  43  *
  44  *  log levels (set isamddebug=x in zebra.cfg (or what ever cfg file you use) )
  45  *    0 = no logging. Default
  46  *    1 = no logging here. isamd logs overall statistics
  47  *    2 = Each call to isamd_append with start address and no more
  48  *    3 = Start and type of append, start of merge, and result of append
  49  *    4 = Block allocations
  50  *    5 = Block-level operations (read/write)
  51  *    6 = Details about diff blocks etc.
  52  *    7 = Log each record as it passes the system (once)
  53  *    8 = Log raw and (de)coded data
  54  *    9 = Anything else that may be useful
  55  *   .. = Anything needed to hunt a specific bug
  56  *  (note that all tests in the code are like debug>3, which means 4 or above!)
  57  *
  58  * Design for the new and improved isamd
  59  * Key points:
  60  *  - The first block is only diffs, no straight data
  61  *  - Additional blocks are straight data
  62  *  - When a diff block gets filled up, a data block is created by
  63  *    merging the diffs with the data
  64  *
  65  * Structure
  66  *  - Isamd_pp: buffer for diffs and for data
  67  *              keep both pos, type, and combined address
  68  *              routine to set the address
  69  *  - diffbuf: lengths as short ints, or bytes for small blocks
  70  *  - keys are of key_struct, not just a number of bytes.
  71  *
  72  * Routines
  73  *  - isamd_append
  74  *    - create_new_block if needed
  75  *    - append_diffs
  76  *      - load_diffs
  77  *      - get diffend, start encoding
  78  *      - while input data
  79  *        - encode it
  80  *        - if no room, then realloc block in larger size
  81  *        - if still no room, merge and exit
  82  *        - append in the block
  83  *
  84  * - merge
  85  *   - just as before, except that merges also input data directly
  86  *   - writes into new data blocks
  87  *
  88  *
  89  * - isamd.c: load firstpp, load datablock
  90  *            save firstpp, save datablock
  91  * - Readlength, writelength - handling right size of len fields
  92  * - isamd_read_main_item: take also a merge input structure, and merge it too
  93  * - prefilter: cache two inputs, and check if they cancel.
  94  * - single-item optimization
  95  *
  96  * questions: Should we realloc firstblocks in a different size as the main
  97  * blocks. Makes a sideways seek, which is bound to be slowe. But saves some
  98  * update time. Compromise: alloc the first one in the size of the datablock,
  99  * but increase if necessary. Large blocks get a large diff, ok. Small ones
 100  * may get an extra seek in read, but save merges.
 101  */
 102
 103 #include <stdlib.h>
 104 #include <assert.h>
 105 #include <string.h>
 106 #include <stdio.h>
 107 #include <log.h>
 108 #include "../index/index.h"
 109 #include "isamd-p.h"
 110
 111
 112 struct ISAMD_DIFF_s {
 113   int diffidx;
 114   int maxidx;
 115   struct it_key key;
 116   void *decodeData;
 117   int mode;
 118 };
 119
 120
 121
 122 static char *hexdump(unsigned char *p, int len, char *buff) {
 123   static char localbuff[128];
 124   char bytebuff[8];
 125   if (!buff) buff=localbuff;
 126   *buff='\0';
 127   while (len--) {
 128     sprintf(bytebuff,"%02x",*p);
 129     p++;
 130     strcat(buff,bytebuff);
 131     if (len) strcat(buff,",");
 132   }
 133   return buff;
 134 }
 135
 136
 137 static int separateDiffBlock(ISAMD_PP pp)
 138 {
 139   int limit = sizeof(int) + 8;
 140   if (pp->next)
 141      return 1;  /* multi-block chains always have a separate diff block */
 142   return ( pp->size + limit >= pp->is->method->filecat[pp->cat].bsize);
 143   /* make sure there is at least room for the length and one diff. if not, */
 144   /* it goes to a separate block. Assumes max diff is 8 bytes. Not         */
 145   /* unreaalistic in large data sets, where first sysno may be very large, */
 146   /* and even the first seqno may be quite something. */
 147
 148   /* todo: Make the limit adjustable in the filecat table ! */
 149 }
 150
 151
 152 /**************************************************************
 153  * Reading
 154  **************************************************************/
 155
 156 static void getDiffInfo(ISAMD_PP pp, int diffidx)
 157 { /* builds the diff info structures from a diffblock */
 158    int maxinfos = pp->is->method->filecat[pp->cat].bsize / 5 +1;
 159     /* Each diff takes at least 5 bytes. Probably more, but this is safe */
 160    int i=1;  /* [0] is used for the main data */
 161    int diffsz= maxinfos * sizeof(struct ISAMD_DIFF_s);
 162
 163    pp->diffinfo = xmalloc( diffsz );
 164    memset(pp->diffinfo,'\0',diffsz);
 165    if (pp->is->method->debug > 5)
 166       logf(LOG_LOG,"isamd_getDiffInfo: %d (%d:%d), ix=%d mx=%d",
 167          isamd_addr(pp->pos, pp->cat), pp->cat, pp->pos, diffidx,maxinfos);
 168    assert(pp->diffbuf);
 169
 170    while (i<maxinfos)
 171    {
 172       if ( diffidx+sizeof(int) > pp->is->method->filecat[pp->cat].bsize )
 173       {
 174          if (pp->is->method->debug > 5)
 175            logf(LOG_LOG,"isamd_getDiffInfo:Near end (no room for len) at ix=%d n=%d",
 176                diffidx, i);
 177          return; /* whole block done */
 178       }
 179       memcpy( &pp->diffinfo[i].maxidx, &pp->diffbuf[diffidx], sizeof(int) );
 180
 181       if (pp->is->method->debug > 5)
 182         logf(LOG_LOG,"isamd_getDiffInfo: max=%d ix=%d dbuf=%p",
 183           pp->diffinfo[i].maxidx, diffidx, pp->diffbuf);
 184
 185       if ( (pp->is->method->debug > 0) &&
 186          (pp->diffinfo[i].maxidx > pp->is->method->filecat[pp->cat].bsize) )
 187       { /* bug-hunting, this fails on some long runs that log too much */
 188          logf(LOG_LOG,"Bad MaxIx!!! %s:%d: diffidx=%d",
 189                        __FILE__,__LINE__, diffidx);
 190          logf(LOG_LOG,"i=%d maxix=%d bsz=%d", i, pp->diffinfo[i].maxidx,
 191                        pp->is->method->filecat[pp->cat].bsize);
 192          logf(LOG_LOG,"pp=%d=%d:%d  pp->nx=%d=%d:%d",
 193                        isamd_addr(pp->pos,pp->cat), pp->pos, pp->cat,
 194                        pp->next, isamd_type(pp->next), isamd_block(pp->next) );
 195       }
 196       assert(pp->diffinfo[i].maxidx <= pp->is->method->filecat[pp->cat].bsize+1);
 197
 198       if (0==pp->diffinfo[i].maxidx)
 199       {
 200          if (pp->is->method->debug > 5)  //!!! 4
 201            logf(LOG_LOG,"isamd_getDiffInfo:End mark at ix=%d n=%d",
 202                diffidx, i);
 203          return; /* end marker */
 204       }
 205       diffidx += sizeof(int);
 206       pp->diffinfo[i].decodeData = (*pp->is->method->code_start)(ISAMD_DECODE);
 207       pp->diffinfo[i].diffidx = diffidx;
 208       if (pp->is->method->debug > 5)
 209         logf(LOG_LOG,"isamd_getDiff[%d]:%d-%d %s",
 210           i,diffidx-sizeof(int),pp->diffinfo[i].maxidx,
 211           hexdump((char *)&pp->diffbuf[diffidx-4],8,0) );
 212       diffidx=pp->diffinfo[i].maxidx;
 213       if ( diffidx > pp->is->method->filecat[pp->cat].bsize )
 214         return; /* whole block done */
 215       ++i;
 216    }
 217    assert (!"too many diff sequences in the block");
 218 }
 219
 220 static void loadDiffs(ISAMD_PP pp)
 221 {  /* assumes pp is a firstblock! */
 222    int diffidx;
 223    int diffaddr;
 224    if (0==pp->diffs)
 225      return; /* no diffs to talk about */
 226    if (pp->diffs & 1 )
 227    { /* separate diff block, load it */
 228       pp->diffbuf= xmalloc( pp->is->method->filecat[pp->cat].bsize);
 229       diffaddr=isamd_addr(pp->diffs/2, pp->cat);
 230       isamd_read_block (pp->is, isamd_type(diffaddr),
 231                                 isamd_block(diffaddr), pp->diffbuf );
 232       diffidx= ISAMD_BLOCK_OFFSET_N;
 233       if (pp->is->method->debug > 4)
 234         logf(LOG_LOG,"isamd_LoadDiffs: loaded block %d=%d:%d, d=%d ix=%d",
 235           diffaddr, isamd_type(diffaddr),isamd_block(diffaddr),
 236           pp->diffs,diffidx);
 237    }
 238    else
 239    { /* integrated block, just set the pointers */
 240      pp->diffbuf = pp->buf;
 241      diffidx = pp->size;  /* size is the beginning of diffs, diffidx the end*/
 242       if (pp->is->method->debug > 4)
 243         logf(LOG_LOG,"isamd_LoadDiffs: within %d=%d:%d, d=%d ix=%d ",
 244           isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos, pp->diffs, diffidx);
 245    }
 246    getDiffInfo(pp,diffidx);
 247 } /* loadDiffs */
 248
 249
 250 void isamd_free_diffs(ISAMD_PP pp)
 251 {
 252   int i;
 253   if (pp->is->method->debug > 5)
 254      logf(LOG_LOG,"isamd_free_diffs: pp=%p di=%p", pp, pp->diffinfo);
 255   if (!pp->diffinfo)
 256     return;
 257   for (i=1;pp->diffinfo[i].decodeData;i++)
 258   {
 259       if (pp->is->method->debug > 8)
 260          logf(LOG_LOG,"isamd_free_diffs [%d]=%p",i,
 261                        pp->diffinfo[i].decodeData);
 262       (*pp->is->method->code_stop)(ISAMD_DECODE,pp->diffinfo[i].decodeData);
 263   }
 264   xfree(pp->diffinfo);
 265   if (pp->diffbuf != pp->buf)
 266     xfree (pp->diffbuf);
 267 } /* isamd_free_diffs */
 268
 269
 270 /* Reads one item and corrects for the diffs, if any */
 271 /* return 1 for ok, 0 for eof */
 272 int isamd_read_item (ISAMD_PP pp, char **dst)
 273 {
 274   char *keyptr;
 275   char *codeptr;
 276   char *codestart;
 277   int winner=0; /* which diff holds the day */
 278   int i; /* looping diffs */
 279   int cmp;
 280   int retry=1;
 281   if (pp->diffs==0)  /* no diffs, just read the thing */
 282      return isamd_read_main_item(pp,dst);
 283
 284   if (!pp->diffinfo)
 285     loadDiffs(pp);
 286   while (retry)
 287   {
 288      retry=0;
 289      if (0==pp->diffinfo[0].key.sysno)
 290      { /* 0 is special case, main data. */
 291         keyptr=(char*) &(pp->diffinfo[0].key);
 292         pp->diffinfo[0].mode = ! isamd_read_main_item(pp,&keyptr);
 293         if (pp->is->method->debug > 7)
 294           logf(LOG_LOG,"isamd_read_item: read main %d.%d (%x.%x)",
 295             pp->diffinfo[0].key.sysno, pp->diffinfo[0].key.seqno,
 296             pp->diffinfo[0].key.sysno, pp->diffinfo[0].key.seqno);
 297      } /* get main data */
 298      winner = 0;
 299      for (i=1; (!retry) && (pp->diffinfo[i].decodeData); i++)
 300      {
 301         if (pp->is->method->debug > 8)
 302           logf(LOG_LOG,"isamd_read_item: considering d%d %d.%d ix=%d mx=%d",
 303                i, pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 304                   pp->diffinfo[i].diffidx,   pp->diffinfo[i].maxidx);
 305
 306         if ( (0==pp->diffinfo[i].key.sysno) &&
 307              (pp->diffinfo[i].diffidx < pp->diffinfo[i].maxidx))
 308         {/* read a new one, if possible */
 309            codeptr= codestart = &(pp->diffbuf[pp->diffinfo[i].diffidx]);
 310            keyptr=(char *)&(pp->diffinfo[i].key);
 311            (*pp->is->method->code_item)(ISAMD_DECODE,
 312                  pp->diffinfo[i].decodeData, &keyptr, &codeptr);
 313            pp->diffinfo[i].diffidx += codeptr-codestart;
 314            pp->diffinfo[i].mode = pp->diffinfo[i].key.seqno & 1;
 315            pp->diffinfo[i].key.seqno = pp->diffinfo[i].key.seqno >>1 ;
 316            if (pp->is->method->debug > 7)
 317              logf(LOG_LOG,"isamd_read_item: read diff[%d] %d.%d (%x.%x)",i,
 318                pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 319                pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno);
 320         }
 321         if ( 0!= pp->diffinfo[i].key.sysno)
 322         { /* got a key, compare */
 323           cmp=key_compare(&pp->diffinfo[i].key, &pp->diffinfo[winner].key);
 324           if (0==pp->diffinfo[winner].key.sysno)
 325             cmp=-1; /* end of main sequence, take all diffs */
 326           if (cmp<0)
 327           {
 328              if (pp->is->method->debug > 8)
 329                logf(LOG_LOG,"isamd_read_item: ins %d<%d %d.%d (%x.%x) < %d.%d (%x.%x)",
 330                  i, winner,
 331                  pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 332                  pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 333                  pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno,
 334                  pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno);
 335              if (pp->diffinfo[i].mode)  /* insert diff, should always be */
 336                winner = i;
 337              else
 338                assert(!"delete diff for nonexisting item");
 339                /* is an assert too steep here? Not really.*/
 340           } /* earlier key */
 341           else if (cmp==0)
 342           {
 343              if (!pp->diffinfo[i].mode) /* delete diff. should always be */
 344              {
 345                 if (pp->is->method->debug > 8)
 346                   logf(LOG_LOG,"isamd_read_item: del %d at%d %d.%d (%x.%x)",
 347                     i, winner,
 348                     pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 349                     pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno);
 350                 pp->diffinfo[winner].key.sysno=0; /* delete it */
 351              }
 352              else
 353                 if (pp->is->method->debug > 2)
 354                   logf(LOG_LOG,"isamd_read_item: duplicate ins %d at%d %d.%d (%x.%x)",
 355                     i, winner,
 356                     pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno,
 357                     pp->diffinfo[i].key.sysno, pp->diffinfo[i].key.seqno);
 358                 /* skip the insert, since we already have it in the base */
 359                 /* Should we fail an assertion here??? */
 360              pp->diffinfo[i].key.sysno=0; /* done with the delete */
 361              retry=1; /* start all over again */
 362           } /* matching key */
 363           /* else it is a later key, its turn will come */
 364         } /* got a key */
 365      } /* for each diff */
 366   } /* not retry */
 367
 368   if ( pp->diffinfo[winner].key.sysno)
 369   {
 370     if (pp->is->method->debug > 7)
 371       logf(LOG_LOG,"isamd_read_item: got %d  %d.%d (%x.%x)",
 372         winner,
 373         pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno,
 374         pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno);
 375     memcpy(*dst, &pp->diffinfo[winner].key, sizeof(struct it_key) );
 376     *dst += sizeof(struct it_key);
 377     pp->diffinfo[winner].key.sysno=0; /* used that one up */
 378     cmp= 1;
 379   }
 380   else
 381   {
 382     if (pp->is->method->debug > 7)
 383       logf(LOG_LOG,"isamd_read_item: eof w=%d  %d.%d (%x.%x)",
 384         winner,
 385         pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno,
 386         pp->diffinfo[winner].key.sysno, pp->diffinfo[winner].key.seqno);
 387     assert(winner==0); /* if nothing found, nothing comes from a diff */
 388     cmp= 0; /* eof */
 389   }
 390   return cmp;
 391
 392 } /* isamd_read_item */
 393
 394 /*****************************************************************
 395  * Support routines
 396  *****************************************************************/
 397
 398 static void isamd_reduceblock(ISAMD_PP pp)
 399 /* takes a large block, and reduces its category if possible */
 400 /* Presumably the first block in an isam-list */
 401 {
 402    if (pp->pos)
 403       return; /* existing block, do not touch */
 404    if (pp->is->method->debug > 5)
 405      logf(LOG_LOG,"isamd_reduce: start p=%d c=%d sz=%d",
 406        pp->pos, pp->cat, pp->size);
 407    while ( ( pp->cat > 0 ) && (!pp->next) &&
 408            (pp->offset < pp->is->method->filecat[pp->cat-1].bsize ) )
 409       pp->cat--;
 410    pp->pos = isamd_alloc_block(pp->is, pp->cat);
 411    if (pp->is->method->debug > 5)
 412      logf(LOG_LOG,"isamd_reduce:  got  p=%d c=%d sz=%d",
 413        pp->pos, pp->cat, pp->size);
 414 } /* reduceblock */
 415
 416
 417
 418
 419 static int save_first_pp ( ISAMD_PP firstpp)
 420 {
 421    isamd_reduceblock(firstpp);
 422    isamd_buildfirstblock(firstpp);
 423    isamd_write_block(firstpp->is,firstpp->cat,firstpp->pos,firstpp->buf);
 424    return isamd_addr(firstpp->pos,firstpp->cat);
 425 }
 426
 427 static void save_last_pp (ISAMD_PP pp)
 428 {
 429    pp->next = 0;/* just to be sure */
 430    isamd_buildlaterblock(pp);
 431    isamd_write_block(pp->is,pp->cat,pp->pos,pp->buf);
 432 }
 433
 434
 435 static int save_both_pps (ISAMD_PP firstpp, ISAMD_PP pp)
 436 {
 437    /* order of things: Better to save firstpp first, if there are just two */
 438    /* blocks, but last if there are blocks in between, as these have already */
 439    /* been saved... optimise later (that's why this is in its own func...*/
 440    int retval = save_first_pp(firstpp);
 441    if (firstpp!=pp){
 442       save_last_pp(pp);
 443       isamd_pp_close(pp);
 444    }
 445    isamd_pp_close(firstpp);
 446    return retval;
 447 } /* save_both_pps */
 448
 449 static ISAMD_PP read_diff_block(ISAMD_PP firstpp, int* p_diffidx)
 450 { /* reads the diff block (if separate) and sets diffidx right */
 451    ISAMD_PP pp=firstpp;
 452    int i;
 453    int diffidx;
 454    if (pp->diffs == 0)
 455    { /* no diffs yet, create room for them */
 456       if (separateDiffBlock(firstpp))
 457       { /* create a new block */
 458          pp=isamd_pp_open(pp->is,isamd_addr(0,firstpp->cat));
 459          pp->pos = isamd_alloc_block(pp->is, pp->cat);
 460          firstpp->diffs = pp->pos*2 +1;
 461          diffidx = pp->size = pp->offset = ISAMD_BLOCK_OFFSET_N;
 462          if (pp->is->method->debug >5)
 463              logf(LOG_LOG,"isamd_appd: alloc diff  (d=%d) %d=%d:%d ix=%d",
 464                    firstpp->diffs,
 465                    isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 466                    diffidx);
 467       }
 468       else
 469       { /* prepare to append diffs in head */
 470         diffidx = pp->size;
 471         pp->diffs = diffidx *2 +0;
 472         i=diffidx; /* make an end marker */
 473         while ( ( i < pp->is->method->filecat[pp->cat].bsize) &&
 474                 ( i <= diffidx + sizeof(int)))
 475             pp->buf[i++]='\0';
 476         if (pp->is->method->debug >5)
 477              logf(LOG_LOG,"isamd_appd: set up diffhead  (d=%d) %d=%d:%d ix=%d",
 478                    firstpp->diffs,
 479                    isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 480                    diffidx);
 481       }
 482    } /* new */
 483    else
 484    { /* existing diffs */
 485       if (pp->diffs & 1)
 486       { /* diffs in a separate block, load it */
 487         pp=isamd_pp_open(pp->is, isamd_addr(firstpp->diffs/2,pp->cat));
 488         diffidx = pp->offset= pp->size;
 489         if (pp->is->method->debug >5)
 490            logf(LOG_LOG,"isamd_appd: loaded diff (d=%d) %d=%d:%d ix=%d",
 491                  firstpp->diffs,
 492                  isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 493                  diffidx);
 494       }
 495       else
 496       { /* diffs within the nead */
 497          diffidx= pp->diffs/2;
 498          if (pp->is->method->debug >5)
 499             logf(LOG_LOG,"isamd_appd: diffs in head d=%d %d=%d:%d ix=%d sz=%d",
 500                      pp->diffs,
 501                      isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 502                      diffidx, pp->size);
 503       }
 504    } /* diffs exist already */
 505    *p_diffidx = diffidx;
 506    return pp;
 507 } /* read_diff_block */
 508
 509
 510
 511
 512 /*******************************************************************
 513  * Building main blocks (no diffs)
 514  *******************************************************************/
 515
 516
 517
 518 static ISAMD_PP get_new_main_block( ISAMD_PP firstpp, ISAMD_PP pp)
 519 {  /* allocates a new block for the main data, and links it in */
 520    int newblock;
 521    if (firstpp==pp)
 522    { /* special case: it was the first block. Save much later */
 523       if (0==firstpp->pos)
 524       { /* firstpp not allocated yet, do so now, */
 525         /* to keep blocks in order. Don't save yet, though */
 526          firstpp->pos = isamd_alloc_block(pp->is, firstpp->cat);
 527       }
 528       newblock = isamd_alloc_block(pp->is, firstpp->cat);
 529       firstpp->next = isamd_addr(newblock,firstpp->cat);
 530         /* keep the largest category */
 531       pp=isamd_pp_open(pp->is,isamd_addr(0,firstpp->cat));/*don't load*/
 532       pp->pos=newblock;
 533       pp->size = pp->offset = ISAMD_BLOCK_OFFSET_N;
 534       pp->next=0;
 535       if (pp->is->method->debug >3)
 536          logf(LOG_LOG,"isamd_g_mainblk: Alloc2 f=%d=%d:%d n=%d=%d:%d",
 537             isamd_addr(firstpp->pos,firstpp->cat),
 538             firstpp->cat, firstpp->pos,
 539             isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos );
 540    }
 541    else
 542    { /* it was not the first block */
 543       newblock = isamd_alloc_block(pp->is, firstpp->cat);
 544       pp->next = isamd_addr(newblock,firstpp->cat);
 545       if (pp->is->method->debug >3)
 546          logf(LOG_LOG,"isamd_build: Alloc1 after p=%d=%d:%d->%d=%d:%d",
 547             isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 548             isamd_addr(newblock,pp->cat), pp->cat, newblock );
 549       isamd_buildlaterblock(pp);
 550       isamd_write_block(pp->is,pp->cat,pp->pos,pp->buf);
 551       pp->size = pp->offset = ISAMD_BLOCK_OFFSET_N;
 552       pp->next=0;
 553       pp->cat = firstpp->cat;
 554       pp->pos = newblock;
 555       pp->cat = firstpp->cat; /* is already, never mind */
 556    }
 557   return pp;
 558 } /* get_new_main_block */
 559
 560
 561 static ISAMD_PP  append_main_item(ISAMD_PP firstpp,
 562                                   ISAMD_PP pp,
 563                                   struct it_key *i_key,
 564                                   void *encoder_data)
 565 {  /* appends one item in the main data block, allocates new if needed */
 566    char *i_item= (char *) i_key;  /* same as char */
 567    char *i_ptr=i_item;
 568    char codebuff[128];
 569    char *c_ptr = codebuff;
 570    int codelen;
 571    char hexbuff[64];
 572
 573    int maxsize = pp->is->method->filecat[pp->is->max_cat].bsize;
 574
 575    c_ptr=codebuff;
 576    i_ptr=i_item;
 577    (*pp->is->method->code_item)(ISAMD_ENCODE, encoder_data, &c_ptr, &i_ptr);
 578    codelen = c_ptr - codebuff;
 579    assert ( (codelen<128) && (codelen>0));
 580    if (pp->is->method->debug >7)
 581       logf(LOG_LOG,"isamd:build: coded into %s  (nk=%d)",
 582           hexdump(codebuff, c_ptr-codebuff,hexbuff), firstpp->numKeys+1);
 583
 584    if (pp->offset + codelen > maxsize )
 585    { /* oops, block full - get a new one */
 586       pp =  get_new_main_block( firstpp, pp );
 587       /* reset encoging and code again */
 588       (*pp->is->method->code_reset)(encoder_data);
 589       c_ptr=codebuff;
 590       i_ptr=i_item;
 591       (*pp->is->method->code_item)(ISAMD_ENCODE, encoder_data, &c_ptr, &i_ptr);
 592       codelen = c_ptr - codebuff;
 593       assert ( (codelen<128) && (codelen>0));
 594       if (pp->is->method->debug >7)
 595          logf(LOG_LOG,"isamd:build: recoded into %s  (nk=%d)",
 596              hexdump(codebuff, c_ptr-codebuff,hexbuff), firstpp->numKeys+1);
 597    } /* block full */
 598
 599    /* write the data into pp, now we must have room */
 600    memcpy(&(pp->buf[pp->offset]),codebuff,codelen);
 601    pp->offset += codelen;
 602    pp->size += codelen;
 603    firstpp->numKeys++;
 604    /* clear the next 4 bytes in block, to avoid confusions with diff lens */
 605    /* dirty, it should not be done here, but something slips somewhere, and */
 606    /* I hope this fixes it...  - Heikki */
 607    codelen = pp->offset;
 608    while ( (codelen < maxsize ) && (codelen <= pp->offset+4) )
 609      pp->buf[codelen++] = '\0';
 610    return pp;
 611 } /* append_main_item */
 612
 613
 614 static int isamd_build_first_block(ISAMD is, ISAMD_I data)
 615 {
 616    struct it_key i_key;  /* input key */
 617    char *i_item= (char *) &i_key;  /* same as char */
 618    char *i_ptr=i_item;
 619    int i_more =1;
 620    int i_mode;     /* 0 for delete, 1 for insert */
 621
 622    ISAMD_PP firstpp;
 623    ISAMD_PP pp;
 624    void *encoder_data;
 625
 626    char hexbuff[64];
 627
 628    ++(is->files[0].no_fbuilds);
 629
 630    firstpp=pp=isamd_pp_open(is, isamd_addr(0,is->max_cat));
 631    firstpp->size = firstpp->offset = ISAMD_BLOCK_OFFSET_1;
 632
 633    encoder_data=(*is->method->code_start)(ISAMD_ENCODE);
 634
 635    if (is->method->debug >2)
 636       logf(LOG_LOG,"isamd_bld start: p=%d=%d:%d sz=%d maxsz=%d ",
 637          isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 638          pp->size, pp->is->method->filecat[pp->is->max_cat].bsize);
 639
 640    /* read first input */
 641    i_ptr = i_item;
 642    i_more = (*data->read_item)(data->clientData, &i_ptr, &i_mode);
 643    if (i_more)
 644      assert( i_ptr-i_item == sizeof(i_key) );
 645
 646    if (pp->is->method->debug >7)
 647       logf(LOG_LOG,"isamd: build_fi start: m=%d %s",
 648          i_mode, hexdump(i_item,i_ptr-i_item,hexbuff) );
 649
 650    while (i_more)
 651    {
 652       if (i_mode!=0)
 653       { /* ignore deletes here, should not happen */
 654          pp= append_main_item(firstpp, pp, &i_key, encoder_data);
 655       } /* not delete */
 656
 657       /* (try to) read the next item */
 658       i_ptr = i_item;
 659       i_more = (*data->read_item)(data->clientData, &i_ptr, &i_mode);
 660
 661       if ( (i_more) && (pp->is->method->debug >7) )
 662          logf(LOG_LOG,"isamd: build_fi read: m=%d %s",
 663             i_mode, hexdump(i_item,i_ptr-i_item,hexbuff) );
 664
 665    } /* i_more */
 666    (*is->method->code_stop)(ISAMD_ENCODE, encoder_data);
 667
 668    return save_both_pps( firstpp, pp );
 669
 670 } /* build_first_block */
 671
 672
 673 /***************************************************************
 674  * Merging diffs
 675  ***************************************************************/
 676
 677
 678 static int merge ( ISAMD_PP *p_firstpp,   /* first pp of the chain */
 679                    ISAMD_PP *p_pp,        /* diff block */
 680                    struct it_key *p_key ) /* not used yet */
 681 {
 682   ISAMD_PP readpp = *p_firstpp;
 683   int diffidx;
 684   int killblk=0;
 685   struct it_key r_key;
 686   char * r_ptr;
 687   int r_more = 1;
 688   ISAMD_PP firstpp;  /* the new first, the one we write into */
 689   ISAMD_PP pp;
 690   void *encoder_data;
 691
 692   ++(readpp->is->files[0].no_merges);
 693
 694   /* set up diffs as they should be for reading */
 695   readpp->offset= ISAMD_BLOCK_OFFSET_1;
 696
 697   if ( (*p_firstpp)->diffs & 1 )
 698   { /* separate diff block in *p_pp */
 699      killblk = readpp->diffs/2;
 700      diffidx /*size*/ = readpp->is->method->filecat[readpp->cat].bsize;
 701      readpp->diffbuf= xmalloc( diffidx); /* copy diffs to where read wants*/
 702      memcpy( readpp->diffbuf, &((*p_pp)->buf[0]), diffidx);
 703      diffidx = ISAMD_BLOCK_OFFSET_N;
 704      if (readpp->is->method->debug >2)
 705      {
 706         logf(LOG_LOG,"isamd_merge:separate diffs at ix=%d",
 707                 diffidx);
 708         logf(LOG_LOG,"isamd_merge: dbuf=%p (from %p) pp=%p",
 709                  readpp->diffbuf, &((*p_pp)->buf[0]), (*p_pp) );
 710      }
 711   }
 712   else
 713   { /* integrated diffs */
 714      assert ( *p_pp == *p_firstpp );  /* can only be in the first block */
 715      diffidx=readpp->size;
 716      readpp->diffs = diffidx*2+0;
 717      readpp->diffbuf=readpp->buf;
 718      if (readpp->is->method->debug >2)
 719          logf(LOG_LOG,"isamd_merge:local diffs at %d: %s",
 720            diffidx,hexdump(&(readpp->diffbuf[diffidx]),8,0));
 721   }
 722
 723   getDiffInfo(readpp,diffidx);
 724   if (readpp->is->method->debug >8)
 725          logf(LOG_LOG,"isamd_merge: diffinfo=%p", readpp->diffinfo);
 726
 727
 728   if (killblk)
 729   {  /* we had a separate diff block, release it, we have copied the data */
 730      isamd_release_block(readpp->is, readpp->cat, killblk);
 731      isamd_pp_close (*p_pp);
 732      if (readpp->is->method->debug >3)
 733          logf(LOG_LOG,"isamd_merge: released diff block %d=%d:%d",
 734               isamd_addr(killblk,readpp->cat), readpp->cat, killblk );
 735   }
 736
 737
 738   /* release our data block. Do before reading, when pos is stable ! */
 739   killblk=readpp->pos;
 740   assert(killblk);
 741   isamd_release_block(readpp->is, readpp->cat, killblk);
 742   if (readpp->is->method->debug >3)
 743       logf(LOG_LOG,"isamd_merge: released old firstblock %d (%d:%d)",
 744                isamd_addr(killblk,readpp->cat), readpp->cat, killblk );
 745
 746   r_ptr= (char *) &r_key;
 747   r_more = isamd_read_item( readpp, &r_ptr);
 748   if (!r_more)
 749   { /* oops, all data has been deleted! what to do??? */
 750     /* never mind, we have at least one more delta to add to the block */
 751     /* pray that is not a delete as well... */
 752     r_key.sysno = 0;
 753     r_key.seqno = 0;
 754      if (readpp->is->method->debug >3)
 755          logf(LOG_LOG,"isamd_merge:all data has been deleted (nk=%d) ",
 756             readpp->numKeys);
 757     assert (readpp->numKeys == 0);
 758   }
 759
 760
 761   /* set up the new blocks for simple writing */
 762   firstpp=pp=isamd_pp_open(readpp->is,isamd_addr(0, readpp->is->max_cat));
 763   firstpp->size = firstpp->offset = ISAMD_BLOCK_OFFSET_1;
 764   encoder_data = (*pp->is->method->code_start)(ISAMD_ENCODE);
 765
 766   while (r_more)
 767   {
 768      if (readpp->is->method->debug >6)
 769          logf(LOG_LOG,"isamd_merge: got key %d.%d",
 770            r_key.sysno, r_key.seqno );
 771      pp= append_main_item(firstpp, pp, &r_key, encoder_data);
 772
 773      if ( (readpp->pos != killblk ) && (0!=readpp->pos) )
 774      {  /* pos can get to 0 at end of main seq, if still diffs left...*/
 775         if (readpp->is->method->debug >3)
 776             logf(LOG_LOG,"isamd_merge: released block %d (%d:%d) now %d=%d:%d",
 777                 isamd_addr(killblk,readpp->cat), readpp->cat, killblk,
 778                 isamd_addr(readpp->pos,readpp->cat),readpp->cat, readpp->pos );
 779         isamd_release_block(readpp->is, readpp->cat, readpp->pos);
 780         killblk=readpp->pos;
 781      }
 782
 783      /* (try to) read next item */
 784      r_ptr= (char *) &r_key;
 785      r_more = isamd_read_item( readpp, &r_ptr);
 786
 787   } /* while read */
 788
 789   /* set things up so that append can continue */
 790   isamd_reduceblock(firstpp);
 791   firstpp->diffs=0;
 792
 793   if (firstpp!=pp)
 794   { /* the last data block is of no interest any more */
 795     save_last_pp(pp);
 796     if (readpp->is->method->debug >4)
 797         logf(LOG_LOG,"isamd_merge: saved last block %d=%d:%d",
 798               isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos);
 799     isamd_pp_close(pp);
 800   }
 801
 802   if (readpp->is->method->debug >5)
 803         logf(LOG_LOG,"isamd_merge: closing readpp %d=%d:%d di=%p",
 804               isamd_addr(readpp->pos,readpp->cat), readpp->cat, readpp->pos,
 805               readpp->diffinfo);
 806   isamd_pp_close(readpp); /* pos is 0 by now, at eof. close works anyway */
 807
 808   (*firstpp->is->method->code_stop)(ISAMD_ENCODE, encoder_data);
 809
 810   *p_firstpp = firstpp;
 811
 812   if (readpp->is->method->debug >2)
 813       logf(LOG_LOG,"isamd_merge: merge ret  %d=%d:%d nx=%d=%d:%d d=%d=2*%d+%d",
 814             isamd_addr(pp->pos,pp->cat), pp->cat, pp->pos,
 815             pp->next, isamd_type(pp->next), isamd_block(pp->next),
 816             pp->diffs, pp->diffs/2, pp->diffs &1 );
 817   return 0;
 818
 819 } /* merge */
 820
 821
 822
 823 /***************************************************************
 824  * Appending diffs
 825  ***************************************************************/
 826
 827
 828
 829 static int append_diffs(ISAMD is, ISAMD_P ipos, ISAMD_I data)
 830 {
 831    struct it_key i_key;    /* one input item */
 832    char *i_item = (char *) &i_key;  /* same as chars */
 833    char *i_ptr=i_item;
 834    int i_more =1;
 835    int i_mode;     /* 0 for delete, 1 for insert */
 836
 837    ISAMD_PP firstpp;
 838    ISAMD_PP pp;
 839    void *encoder_data;
 840    char hexbuff[64];
 841    int diffidx=0;
 842    int maxsize=0;
 843    int difflenidx;
 844    char codebuff[128];
 845    char *c_ptr = codebuff;
 846    int codelen;
 847    int merge_rc;
 848    int mergecount=0;
 849
 850    ++(is->files[0].no_appds);
 851
 852    firstpp=isamd_pp_open(is, ipos);
 853    if (is->method->debug >2)
 854       logf(LOG_LOG,"isamd_appd: Start ipos=%d=%d:%d d=%d=%d*2+%d nk=%d",
 855         ipos, isamd_type(ipos), isamd_block(ipos),
 856         firstpp->diffs, firstpp->diffs/2, firstpp->diffs & 1, firstpp->numKeys);
 857    pp=read_diff_block(firstpp, &diffidx);
 858    encoder_data=(*is->method->code_start)(ISAMD_ENCODE);
 859    maxsize = is->method->filecat[pp->cat].bsize;
 860
 861    difflenidx = diffidx;
 862    diffidx+=sizeof(int);  /* difflen will be stored here */
 863
 864    /* read first input */
 865    i_ptr = i_item;
 866    i_more = (*data->read_item)(data->clientData, &i_ptr, &i_mode);
 867
 868    if (is->method->debug >6)
 869       logf(LOG_LOG,"isamd_appd: start with m=%d %s",
 870          i_mode, hexdump(i_item,i_ptr-i_item,hexbuff) );
 871
 872    while (i_more)
 873    {
 874       /* store the mode bit inside key */
 875       assert( ((i_key.seqno<<1)>>1) == i_key.seqno); /* can spare the bit */
 876       i_key.seqno = i_key.seqno * 2 + i_mode;
 877
 878       c_ptr=codebuff;
 879       i_ptr=i_item;
 880       (*is->method->code_item)(ISAMD_ENCODE, encoder_data, &c_ptr, &i_ptr);
 881       codelen = c_ptr - codebuff;
 882       assert ( (codelen<128) && (codelen>0));
 883       if (is->method->debug >7)
 884          logf(LOG_LOG,"isamd_appd: coded into %d: %s (nk=%d) (ix=%d)",
 885              codelen, hexdump(codebuff, codelen,hexbuff),
 886              firstpp->numKeys,diffidx);
 887
 888       if (diffidx + codelen > maxsize )
 889       { /* block full */
 890          if (is->method->debug >3)
 891             logf(LOG_LOG,"isamd_appd: block full (ix=%d mx=%d lix=%d)",
 892                diffidx, maxsize, difflenidx);
 893          if (is->method->debug >8)
 894             logf(LOG_LOG,"isamd_appd: block pp=%p buf=%p [%d]:%s",
 895                pp, pp->buf,
 896                difflenidx, hexdump(&pp->buf[difflenidx],8,0));
 897          if (mergecount++)
 898              ++(is->files[0].no_remerges);
 899          merge_rc = merge (&firstpp, &pp, &i_key);
 900          if (0!=merge_rc)
 901            return merge_rc;  /* merge handled them all ! */
 902
 903          /* set things up so we can continue */
 904          pp = read_diff_block(firstpp, &diffidx);
 905          (*is->method->code_reset)(encoder_data);
 906          maxsize = is->method->filecat[pp->cat].bsize;
 907          difflenidx=diffidx;
 908          diffidx+=sizeof(int);
 909
 910          /* code the current input key again */
 911          c_ptr=codebuff;
 912          i_ptr=i_item;
 913          (*is->method->code_item)(ISAMD_ENCODE, encoder_data, &c_ptr, &i_ptr);
 914          codelen = c_ptr - codebuff;
 915          assert ( (codelen<128) && (codelen>0));
 916          if (is->method->debug >7)
 917             logf(LOG_LOG,"isamd_appd: recoded into %d: %s (nk=%d) (ix=%d)",
 918                 codelen, hexdump(codebuff, codelen,hexbuff),
 919                 firstpp->numKeys,diffidx);
 920
 921       } /* block full */
 922
 923       /* Note: this goes horribly wrong if there is no room for the diff */
 924       /* after the merge! The solution is to increase the limit in */
 925       /* separateDiffBlock, to force a separate diff block earlier, and not */
 926       /* to have absurdly small blocks */
 927       assert ( diffidx+codelen <= maxsize );
 928
 929       /* save the diff */
 930       memcpy(&(pp->buf[diffidx]),codebuff,codelen);
 931       diffidx += codelen;
 932       if (i_mode)
 933         firstpp->numKeys++; /* insert diff */
 934       else
 935         firstpp->numKeys--; /* delete diff */
 936
 937       /* update length of this diff run */
 938       memcpy(&(pp->buf[difflenidx]),&diffidx,sizeof(diffidx));
 939       if (firstpp==pp)
 940         firstpp->diffs =diffidx*2+0;
 941       else
 942         pp->size =diffidx;
 943
 944       /* (try to) read the next input */
 945       i_ptr = i_item;
 946       i_more = (*data->read_item)(data->clientData, &i_ptr, &i_mode);
 947       if ( (i_more) && (is->method->debug >6) )
 948          logf(LOG_LOG,"isamd_appd: got m=%d %s",
 949             i_mode, hexdump(i_item,i_ptr-i_item,hexbuff) );
 950    } /* more loop */
 951
 952    /* clear the next difflen, if room for such */
 953    difflenidx = diffidx;
 954    while ( (difflenidx-diffidx<=sizeof(int)) && (difflenidx<maxsize))
 955      pp->buf[difflenidx++]='\0';
 956
 957
 958   (*firstpp->is->method->code_stop)(ISAMD_ENCODE, encoder_data);
 959    return save_both_pps( firstpp, pp );
 960
 961 } /* append_diffs */
 962
 963
 964
 965 /*************************************************************
 966  * isamd_append itself, Sweet, isn't it
 967  *************************************************************/
 968
 969 ISAMD_P isamd_append (ISAMD is, ISAMD_P ipos, ISAMD_I data)
 970 {
 971    int retval=0;
 972
 973    if (0==ipos)
 974       retval = isamd_build_first_block(is,data);
 975    else
 976       retval = append_diffs(is,ipos,data);
 977
 978    return retval;
 979 } /*  isamd_append */
 980
 981
 982 /*
 983  * $Log: merge-d.c,v $
 984  * Revision 1.17  1999-08-24 13:17:42  heikki
 985  * Block sizes, comments
 986  *
 987  * Revision 1.16  1999/08/24 10:12:02  heikki
 988  * Comments about optimising
 989  *
 990  * Revision 1.15  1999/08/22 08:26:34  heikki
 991  * COmments
 992  *
 993  * Revision 1.14  1999/08/20 12:25:58  heikki
 994  * Statistics in isamd
 995  *
 996  * Revision 1.13  1999/08/18 13:59:19  heikki
 997  * Fixed another unlikely difflen bug
 998  *
 999  * Revision 1.12  1999/08/18 13:28:17  heikki
1000  * Set log levels to decent values
1001  *
1002  * Revision 1.11  1999/08/18 10:37:11  heikki
1003  * Fixed (another) difflen bug
1004  *
1005  * Revision 1.10  1999/08/18 09:13:31  heikki
1006  * Fixed a detail
1007  *
1008  * Revision 1.9  1999/08/17 19:46:53  heikki
1009  * Fixed a memory leak
1010  *
1011  * Revision 1.8  1999/08/07 11:30:59  heikki
1012  * Bug fixing (still a mem leak somewhere)
1013  *
1014  * Revision 1.7  1999/08/04 14:21:18  heikki
1015  * isam-d seems to be working.
1016  *
1017  * Revision 1.6  1999/07/23 15:43:05  heikki
1018  * Hunted a few bugs in isam-d. Still crashes on the long test run
1019  *
1020  * Revision 1.5  1999/07/23 13:58:52  heikki
1021  * merged closer to working, still fails on filling a separate, large block
1022  *
1023  * Revision 1.4  1999/07/21 14:53:55  heikki
1024  * isamd read and write functions work, except when block full
1025  * Merge missing still. Need to split some functions
1026  *
1027  * Revision 1.1  1999/07/14 13:14:47  heikki
1028  * Created empty
1029  *
1030  *
1031  */
1032
1033
1034
1035