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