isamb/isamb.c

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