isamb/isamb.c

   1 /*
   2  *  Copyright (c) 1995-1998, Index Data.
   3  *  See the file LICENSE for details.
   4  *
   5  *  $Id: isamb.c,v 1.5 2002-04-17 08:48:54 adam Exp $
   6  */
   7 #include <yaz/xmalloc.h>
   8 #include <yaz/log.h>
   9 #include <isamb.h>
  10 #include <assert.h>
  11
  12 struct ISAMB_head {
  13     int first_block;
  14     int last_block;
  15     int block_size;
  16 };
  17
  18 #define ISAMB_DATA_OFFSET 3
  19
  20 #define DST_BUF_SIZE 4500
  21 #define DST_ITEM_MAX 256
  22
  23 struct ISAMB_file {
  24     BFile bf;
  25     int head_dirty;
  26     struct ISAMB_head head;
  27 };
  28
  29 struct ISAMB_s {
  30     BFiles bfs;
  31     ISAMC_M method;
  32
  33     struct ISAMB_file *file;
  34     int no_cat;
  35 };
  36
  37 struct ISAMB_block {
  38     int pos;
  39     int cat;
  40     int size;
  41     int leaf;
  42     int dirty;
  43     int offset;
  44     unsigned char *bytes;
  45     void *decodeClientData;
  46 };
  47
  48 struct ISAMB_PP_s {
  49     ISAMB isamb;
  50     int level;
  51     struct ISAMB_block **block;
  52 };
  53
  54 void encode_ptr (char **dst, int pos)
  55 {
  56     memcpy (*dst, &pos, sizeof(pos));
  57     (*dst) += sizeof(pos);
  58 }
  59
  60 void decode_ptr (char **src, int *pos)
  61 {
  62     memcpy (pos, *src, sizeof(*pos));
  63     (*src) += sizeof(*pos);
  64 }
  65
  66 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method)
  67 {
  68     ISAMB isamb = xmalloc (sizeof(*isamb));
  69     int i, b_size = 64;
  70
  71     isamb->bfs = bfs;
  72     isamb->method = (ISAMC_M) xmalloc (sizeof(*method));
  73     memcpy (isamb->method, method, sizeof(*method));
  74     isamb->no_cat = 4;
  75
  76     isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat);
  77     for (i = 0; i<isamb->no_cat; i++)
  78     {
  79         char fname[DST_BUF_SIZE];
  80         isamb->file[i].head.first_block = 1;
  81         isamb->file[i].head.last_block = 1;
  82         isamb->file[i].head.block_size = b_size;
  83         b_size = b_size * 4;
  84         isamb->file[i].head_dirty = 0;
  85         sprintf (fname, "%s-%d", name, i);
  86         isamb->file[i].bf =
  87             bf_open (bfs, fname, isamb->file[i].head.block_size, writeflag);
  88
  89         bf_read (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head),
  90                  &isamb->file[i].head);
  91     }
  92     return isamb;
  93 }
  94
  95 void isamb_close (ISAMB isamb)
  96 {
  97     int i;
  98     for (i = 0; i<isamb->no_cat; i++)
  99     {
 100         if (isamb->file[i].head_dirty)
 101             bf_write (isamb->file[i].bf, 0, 0,
 102                       sizeof(struct ISAMB_head), &isamb->file[i].head);
 103     }
 104     xfree (isamb->file);
 105     xfree (isamb->method);
 106     xfree (isamb);
 107 }
 108
 109 struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
 110 {
 111     int cat = pos&3;
 112     struct ISAMB_block *p;
 113     if (!pos)
 114         return 0;
 115     p = xmalloc (sizeof(*p));
 116     p->pos = pos;
 117     p->cat = pos & 3;
 118     p->bytes = xmalloc (b->file[cat].head.block_size);
 119     bf_read (b->file[cat].bf, pos/4, 0, 0, p->bytes);
 120     p->leaf = p->bytes[0];
 121     p->size = p->bytes[1] + 256 * p->bytes[2];
 122     p->offset = ISAMB_DATA_OFFSET;
 123     p->dirty = 0;
 124     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
 125     return p;
 126 }
 127
 128 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
 129 {
 130     struct ISAMB_block *p;
 131     int block_no;
 132
 133     p = xmalloc (sizeof(*p));
 134     block_no = b->file[cat].head.last_block++;
 135     p->cat = cat;
 136     p->pos = block_no * 4 + cat;
 137     p->cat = cat;
 138     b->file[cat].head_dirty = 1;
 139     p->bytes = xmalloc (b->file[cat].head.block_size);
 140     memset (p->bytes, 0, b->file[cat].head.block_size);
 141     p->leaf = leaf;
 142     p->size = ISAMB_DATA_OFFSET;
 143     p->dirty = 1;
 144     p->offset = ISAMB_DATA_OFFSET;
 145     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
 146     return p;
 147 }
 148
 149 void close_block (ISAMB b, struct ISAMB_block *p)
 150 {
 151     if (!p)
 152         return;
 153     if (p->dirty)
 154     {
 155         p->bytes[0] = p->leaf;
 156         p->bytes[1] = p->size & 255;
 157         p->bytes[2] = p->size >> 8;
 158         bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->bytes);
 159     }
 160     (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData);
 161     xfree (p->bytes);
 162     xfree (p);
 163 }
 164
 165 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
 166                  struct ISAMB_block **sp,
 167                  void *sub_item, int *sub_size);
 168
 169 void insert_leaf (ISAMB b, struct ISAMB_block *p, const void *new_item,
 170                   struct ISAMB_block **sp,
 171                   void *sub_item, int *sub_size)
 172 {
 173     char dst_buf[DST_BUF_SIZE];
 174     char *dst = dst_buf;
 175     char *src = p->bytes + ISAMB_DATA_OFFSET;
 176     char *endp = p->bytes + p->size;
 177     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
 178     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
 179     char *half1 = 0;
 180     char *half2 = 0;
 181     char *cut = dst_buf + p->size / 2;
 182     char cut_item_buf[DST_ITEM_MAX];
 183     int cut_item_size = 0;
 184
 185     while (src != endp)
 186     {
 187         char file_item_buf[DST_ITEM_MAX];
 188         char *file_item = file_item_buf;
 189
 190         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 191         if (new_item)
 192         {
 193             int d = (*b->method->compare_item)(file_item_buf, new_item);
 194             if (d > 0)
 195             {
 196                 char *item_ptr = (char*) new_item;
 197                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 198                 new_item = 0;
 199                 p->dirty = 1;
 200             }
 201             else if (d == 0)
 202             {
 203                 new_item = 0;
 204             }
 205         }
 206
 207         if (!half1 && dst > cut)
 208         {
 209             half1 = dst; /* candidate for splitting */
 210
 211             file_item = file_item_buf;
 212             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
 213
 214             cut_item_size = file_item - file_item_buf;
 215             memcpy (cut_item_buf, file_item_buf, cut_item_size);
 216
 217             half2 = dst;
 218         }
 219         else
 220         {
 221             file_item = file_item_buf;
 222             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
 223         }
 224     }
 225     if (new_item)
 226     {
 227         char *item_ptr = (char*) new_item;
 228         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 229         new_item = 0;
 230         p->dirty = 1;
 231     }
 232     p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
 233     if (p->size > b->file[p->cat].head.block_size)
 234     {
 235         char *first_dst;
 236         char *cut_item = cut_item_buf;
 237
 238        /* first half */
 239         p->size = half1 - dst_buf + ISAMB_DATA_OFFSET;
 240         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, half1 - dst_buf);
 241
 242         /* second half */
 243         *sp = new_block (b, 1, p->cat);
 244
 245         (*b->method->code_reset)(c2);
 246
 247         first_dst = (*sp)->bytes + ISAMB_DATA_OFFSET;
 248
 249         (*b->method->code_item)(ISAMC_ENCODE, c2, &first_dst, &cut_item);
 250
 251         memcpy (first_dst, half2, dst - half2);
 252
 253         (*sp)->size = (first_dst - (char*) (*sp)->bytes) + (dst - half2);
 254         (*sp)->dirty = 1;
 255         p->dirty = 1;
 256         memcpy (sub_item, cut_item_buf, cut_item_size);
 257         *sub_size = cut_item_size;
 258
 259         yaz_log (LOG_LOG, "l split %d / %d", p->size, (*sp)->size);
 260
 261     }
 262     else
 263     {
 264         assert (p->size > ISAMB_DATA_OFFSET);
 265         assert (p->size <= b->file[p->cat].head.block_size);
 266         memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
 267         *sp = 0;
 268     }
 269     (*b->method->code_stop)(ISAMC_DECODE, c1);
 270     (*b->method->code_stop)(ISAMC_ENCODE, c2);
 271 }
 272
 273 void insert_int (ISAMB b, struct ISAMB_block *p, const void *new_item,
 274                  struct ISAMB_block **sp,
 275                  void *split_item, int *split_size)
 276 {
 277     char *startp = p->bytes + ISAMB_DATA_OFFSET;
 278     char *src = startp;
 279     char *endp = p->bytes + p->size;
 280     int pos;
 281     struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
 282     char sub_item[DST_ITEM_MAX];
 283     int sub_size;
 284
 285     *sp = 0;
 286
 287     decode_ptr (&src, &pos);
 288     while (src != endp)
 289     {
 290         int item_len;
 291         int d;
 292         decode_ptr (&src, &item_len);
 293         d = (*b->method->compare_item)(src, new_item);
 294         if (d > 0)
 295         {
 296             sub_p1 = open_block (b, pos);
 297             assert (sub_p1);
 298             insert_sub (b, sub_p1, new_item, &sub_p2,
 299                         sub_item, &sub_size);
 300             break;
 301         }
 302         src += item_len;
 303         decode_ptr (&src, &pos);
 304     }
 305     if (!sub_p1)
 306     {
 307         sub_p1 = open_block (b, pos);
 308         assert (sub_p1);
 309         insert_sub (b, sub_p1, new_item, &sub_p2,
 310                     sub_item, &sub_size);
 311     }
 312     if (sub_p2)
 313     {
 314         char dst_buf[DST_BUF_SIZE];
 315         char *dst = dst_buf;
 316
 317         assert (sub_size < 20);
 318
 319         memcpy (dst, startp, src - startp);
 320
 321         dst += src - startp;
 322
 323         encode_ptr (&dst, sub_size);      /* sub length and item */
 324         memcpy (dst, sub_item, sub_size);
 325         dst += sub_size;
 326
 327         encode_ptr (&dst, sub_p2->pos);   /* pos */
 328
 329         if (endp - src)                   /* remaining data */
 330         {
 331             memcpy (dst, src, endp - src);
 332             dst += endp - src;
 333         }
 334         p->size = dst - dst_buf + ISAMB_DATA_OFFSET;
 335         if (p->size <= b->file[p->cat].head.block_size)
 336         {
 337             memcpy (startp, dst_buf, dst - dst_buf);
 338         }
 339         else
 340         {
 341             int p_new_size;
 342             char *half;
 343             src = dst_buf;
 344             endp = dst;
 345
 346             half = src + b->file[p->cat].head.block_size/2;
 347             decode_ptr (&src, &pos);
 348             while (src <= half)
 349             {
 350                 decode_ptr (&src, split_size);
 351                 src += *split_size;
 352                 decode_ptr (&src, &pos);
 353             }
 354             p_new_size = src - dst_buf;
 355             memcpy (p->bytes + ISAMB_DATA_OFFSET, dst_buf, p_new_size);
 356             p_new_size += ISAMB_DATA_OFFSET;
 357
 358             decode_ptr (&src, split_size);
 359             memcpy (split_item, src, *split_size);
 360             src += *split_size;
 361
 362             *sp = new_block (b, 0, p->cat);
 363             (*sp)->size = endp - src;
 364             memcpy ((*sp)->bytes+ISAMB_DATA_OFFSET, src, (*sp)->size);
 365             (*sp)->size += ISAMB_DATA_OFFSET;
 366
 367             yaz_log (LOG_LOG, "i split %d -> %d %d",
 368                      p->size, p_new_size, (*sp)->size);
 369             p->size = p_new_size;
 370         }
 371         p->dirty = 1;
 372         close_block (b, sub_p2);
 373     }
 374     close_block (b, sub_p1);
 375 }
 376
 377 void insert_sub (ISAMB b, struct ISAMB_block *p, const void *new_item,
 378                 struct ISAMB_block **sp,
 379                 void *sub_item, int *sub_size)
 380 {
 381     if (p->leaf)
 382         insert_leaf (b, p, new_item, sp, sub_item, sub_size);
 383     else
 384         insert_int (b, p, new_item, sp, sub_item, sub_size);
 385 }
 386
 387 int insert_flat (ISAMB b, const void *new_item, ISAMC_P *posp)
 388 {
 389     struct ISAMB_block *p = 0;
 390     char *src = 0, *endp = 0;
 391     char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
 392     int new_size;
 393     ISAMB_P pos = *posp;
 394     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
 395     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
 396
 397     if (pos)
 398     {
 399         p = open_block (b, pos);
 400         if (!p)
 401             return -1;
 402         src = p->bytes + ISAMB_DATA_OFFSET;
 403         endp = p->bytes + p->size;
 404
 405     }
 406     while (p && src != endp)
 407     {
 408         char file_item_buf[DST_ITEM_MAX];
 409         char *file_item = file_item_buf;
 410
 411         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 412         if (new_item)
 413         {
 414             int d = (*b->method->compare_item)(file_item_buf, new_item);
 415             if (d > 0)
 416             {
 417                 char *item_ptr = (char*) new_item;
 418                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 419                 new_item = 0;
 420                 p->dirty = 1;
 421             }
 422             else if (d == 0)
 423             {
 424                 new_item = 0;
 425             }
 426         }
 427         file_item = file_item_buf;
 428         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &file_item);
 429     }
 430     if (new_item)
 431     {
 432         char *item_ptr = (char*) new_item;
 433         (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &item_ptr);
 434         new_item = 0;
 435         if (p)
 436             p->dirty = 1;
 437     }
 438     new_size = dst - dst_buf + ISAMB_DATA_OFFSET;
 439     if (p && new_size > b->file[p->cat].head.block_size)
 440     {
 441         yaz_log (LOG_LOG, "resize %d -> %d", p->size, new_size);
 442         close_block (b, p);
 443         /* delete it too!! */
 444         p = 0; /* make a new one anyway */
 445     }
 446     if (!p)
 447     {   /* must create a new one */
 448         int i;
 449         for (i = 0; i < b->no_cat; i++)
 450             if (new_size <= b->file[i].head.block_size)
 451                 break;
 452         p = new_block (b, 1, i);
 453     }
 454     memcpy (p->bytes+ISAMB_DATA_OFFSET, dst_buf, dst - dst_buf);
 455     p->size = new_size;
 456     *posp = p->pos;
 457     (*b->method->code_stop)(ISAMC_DECODE, c1);
 458     (*b->method->code_stop)(ISAMC_ENCODE, c2);
 459     close_block (b, p);
 460     return 0;
 461 }
 462
 463 int isamb_insert_one (ISAMB b, const void *item, ISAMC_P pos)
 464 {
 465
 466     if ((pos & 3) != b->no_cat-1)
 467     {
 468         /* note if pos == 0 we go here too! */
 469         /* flat insert */
 470         insert_flat (b, item, &pos);
 471     }
 472     else
 473     {
 474         /* b-tree insert */
 475         struct ISAMB_block *p, *sp = 0;
 476         char sub_item[DST_ITEM_MAX];
 477         int sub_size;
 478
 479         insert_sub (b, p, item, &sp, sub_item, &sub_size);
 480         if (sp)
 481         {    /* increase level of tree by one */
 482             struct ISAMB_block *p2 = new_block (b, 0, p->cat);
 483             char *dst = p2->bytes + p2->size;
 484
 485             encode_ptr (&dst, p->pos);
 486             assert (sub_size < 20);
 487             encode_ptr (&dst, sub_size);
 488             memcpy (dst, sub_item, sub_size);
 489             dst += sub_size;
 490             encode_ptr (&dst, sp->pos);
 491
 492             p2->size = dst - (char*) p2->bytes;
 493             pos = p2->pos;  /* return new super page */
 494             close_block (b, sp);
 495             close_block (b, p2);
 496         }
 497         else
 498             pos = p->pos;   /* return current one (again) */
 499         close_block (b, p);
 500     }
 501     return pos;
 502 }
 503
 504 ISAMB_P isamb_merge (ISAMB b, ISAMB_P pos, ISAMC_I data)
 505 {
 506     int i_mode;
 507     char item_buf[DST_ITEM_MAX];
 508     char *item_ptr = item_buf;
 509     while ((*data->read_item)(data->clientData, &item_ptr, &i_mode))
 510     {
 511         item_ptr = item_buf;
 512         pos = isamb_insert_one (b, item_buf, pos);
 513     }
 514     return pos;
 515 }
 516
 517 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
 518 {
 519     ISAMB_PP pp = xmalloc (sizeof(*pp));
 520
 521     pp->isamb = isamb;
 522     pp->block = xmalloc (10 * sizeof(*pp->block));
 523
 524     pp->level = 0;
 525     while (1)
 526     {
 527         struct ISAMB_block *p = open_block (isamb, pos);
 528         char *src = p->bytes + p->offset;
 529         pp->block[pp->level] = p;
 530
 531         if (p->bytes[0]) /* leaf */
 532             break;
 533
 534         decode_ptr (&src, &pos);
 535         p->offset = src - (char*) p->bytes;
 536         pp->level++;
 537     }
 538     pp->block[pp->level+1] = 0;
 539     return pp;
 540 }
 541
 542 void isamb_pp_close (ISAMB_PP pp)
 543 {
 544     int i;
 545     if (!pp)
 546         return;
 547     for (i = 0; i <= pp->level; i++)
 548         close_block (pp->isamb, pp->block[i]);
 549     xfree (pp->block);
 550     xfree (pp);
 551 }
 552
 553 int isamb_pp_read (ISAMB_PP pp, void *buf)
 554 {
 555     char *dst = buf;
 556     char *src;
 557     struct ISAMB_block *p = pp->block[pp->level];
 558     if (!p)
 559         return 0;
 560
 561     while (p->offset == p->size)
 562     {
 563         int pos, item_len;
 564         while (p->offset == p->size)
 565         {
 566             if (pp->level == 0)
 567                 return 0;
 568             close_block (pp->isamb, pp->block[pp->level]);
 569             pp->block[pp->level] = 0;
 570             (pp->level)--;
 571             p = pp->block[pp->level];
 572             assert (p->bytes[0] == 0);  /* must be int */
 573         }
 574         src = p->bytes + p->offset;
 575
 576         decode_ptr (&src, &item_len);
 577         src += item_len;
 578         decode_ptr (&src, &pos);
 579
 580         p->offset = src - (char*) p->bytes;
 581
 582         ++(pp->level);
 583
 584         while (1)
 585         {
 586             pp->block[pp->level] = p = open_block (pp->isamb, pos);
 587
 588             if (p->bytes[0]) /* leaf */
 589             {
 590                 break;
 591             }
 592             src = p->bytes + p->offset;
 593             decode_ptr (&src, &pos);
 594             p->offset = src - (char*) p->bytes;
 595             pp->level++;
 596         }
 597     }
 598     assert (p->offset < p->size);
 599     assert (p->bytes[0]);
 600     src = p->bytes + p->offset;
 601     (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData,
 602                                     &dst, &src);
 603     p->offset = src - (char*) p->bytes;
 604     return 1;
 605 }
 606
 607 int isamb_pp_num (ISAMB_PP pp)
 608 {
 609     return 1;
 610 }