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