isamb/isamb.c

   1 /* $Id: isamb.c,v 1.22 2003-02-04 12:06:47 pop Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23 #include <string.h>
  24 #include <yaz/xmalloc.h>
  25 #include <yaz/log.h>
  26 #include <isamb.h>
  27 #include <assert.h>
  28
  29 struct ISAMB_head {
  30     int first_block;
  31     int last_block;
  32     int block_size;
  33     int block_max;
  34     int free_list;
  35 };
  36
  37 #define ISAMB_DATA_OFFSET 3
  38
  39 #define DST_ITEM_MAX 256
  40
  41 /* approx 2*4 K + max size of item */
  42 #define DST_BUF_SIZE 8448
  43
  44 #define ISAMB_CACHE_ENTRY_SIZE 4096
  45
  46 struct ISAMB_cache_entry {
  47     ISAMB_P pos;
  48     char *buf;
  49     int dirty;
  50     int hits;
  51     struct ISAMB_cache_entry *next;
  52 };
  53
  54
  55 struct ISAMB_file {
  56     BFile bf;
  57     int head_dirty;
  58     struct ISAMB_head head;
  59     struct ISAMB_cache_entry *cache_entries;
  60 };
  61
  62 struct ISAMB_s {
  63     BFiles bfs;
  64     ISAMC_M method;
  65
  66     struct ISAMB_file *file;
  67     int no_cat;
  68     int cache; /* 0=no cache, 1=use cache, -1=dummy isam (for testing only) */
  69     int log_io;        /* log level for bf_read/bf_write calls */
  70     int log_freelist;  /* log level for freelist handling */
  71 };
  72
  73 struct ISAMB_block {
  74     ISAMB_P pos;
  75     int cat;
  76     int size;
  77     int leaf;
  78     int dirty;
  79     int deleted;
  80     int offset;
  81     char *bytes;
  82     unsigned char *buf;
  83     void *decodeClientData;
  84     int log_rw;
  85 };
  86
  87 struct ISAMB_PP_s {
  88     ISAMB isamb;
  89     ISAMB_P pos;
  90     int level;
  91     int total_size;
  92     int no_blocks;
  93     struct ISAMB_block **block;
  94 };
  95
  96 void encode_ptr (char **dst, int pos)
  97 {
  98     memcpy (*dst, &pos, sizeof(pos));
  99     (*dst) += sizeof(pos);
 100 }
 101
 102 void decode_ptr (char **src, int *pos)
 103 {
 104     memcpy (pos, *src, sizeof(*pos));
 105     (*src) += sizeof(*pos);
 106 }
 107
 108 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method,
 109                   int cache)
 110 {
 111     ISAMB isamb = xmalloc (sizeof(*isamb));
 112     int i, b_size = 32;
 113
 114     isamb->bfs = bfs;
 115     isamb->method = (ISAMC_M) xmalloc (sizeof(*method));
 116     memcpy (isamb->method, method, sizeof(*method));
 117     isamb->no_cat = 4;
 118     isamb->log_io = 0;
 119     isamb->cache = cache;
 120
 121     isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat);
 122     for (i = 0; i<isamb->no_cat; i++)
 123     {
 124         char fname[DST_BUF_SIZE];
 125         isamb->file[i].cache_entries = 0;
 126         isamb->file[i].head_dirty = 0;
 127         sprintf (fname, "%s%c", name, i+'A');
 128         if (cache)
 129             isamb->file[i].bf = bf_open (bfs, fname, ISAMB_CACHE_ENTRY_SIZE,
 130                                          writeflag);
 131         else
 132             isamb->file[i].bf = bf_open (bfs, fname, b_size, writeflag);
 133
 134
 135         if (!bf_read (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head),
 136                       &isamb->file[i].head))
 137         {
 138             isamb->file[i].head.first_block = ISAMB_CACHE_ENTRY_SIZE/b_size+1;
 139             isamb->file[i].head.last_block = isamb->file[i].head.first_block;
 140             isamb->file[i].head.block_size = b_size;
 141             isamb->file[i].head.block_max = b_size - ISAMB_DATA_OFFSET;
 142             isamb->file[i].head.free_list = 0;
 143         }
 144         assert (isamb->file[i].head.block_size >= ISAMB_DATA_OFFSET);
 145         isamb->file[i].head_dirty = 0;
 146         assert(isamb->file[i].head.block_size == b_size);
 147         b_size = b_size * 4;
 148     }
 149     return isamb;
 150 }
 151
 152 static void flush_blocks (ISAMB b, int cat)
 153 {
 154     while (b->file[cat].cache_entries)
 155     {
 156         struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
 157         b->file[cat].cache_entries = ce_this->next;
 158
 159         if (ce_this->dirty)
 160         {
 161             yaz_log (b->log_io, "bf_write: flush_blocks");
 162             bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
 163         }
 164         xfree (ce_this->buf);
 165         xfree (ce_this);
 166     }
 167 }
 168
 169 static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr)
 170 {
 171     int cat = pos&3;
 172     int off = ((pos/4) &
 173                (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
 174         * b->file[cat].head.block_size;
 175     int norm = pos / (4*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
 176     int no = 0;
 177     struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
 178
 179     if (!b->cache)
 180         return 0;
 181
 182     assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
 183     for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
 184     {
 185         ce_last = ce;
 186         if ((*ce)->pos == norm)
 187         {
 188             ce_this = *ce;
 189             *ce = (*ce)->next;   /* remove from list */
 190
 191             ce_this->next = b->file[cat].cache_entries;  /* move to front */
 192             b->file[cat].cache_entries = ce_this;
 193
 194             if (wr)
 195             {
 196                 memcpy (ce_this->buf + off, userbuf,
 197                         b->file[cat].head.block_size);
 198                 ce_this->dirty = 1;
 199             }
 200             else
 201                 memcpy (userbuf, ce_this->buf + off,
 202                         b->file[cat].head.block_size);
 203             return 1;
 204         }
 205     }
 206     if (no >= 40)
 207     {
 208         assert (no == 40);
 209         assert (ce_last && *ce_last);
 210         ce_this = *ce_last;
 211         *ce_last = 0;  /* remove the last entry from list */
 212         if (ce_this->dirty)
 213         {
 214             yaz_log (b->log_io, "bf_write: get_block");
 215             bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
 216         }
 217         xfree (ce_this->buf);
 218         xfree (ce_this);
 219     }
 220     ce_this = xmalloc (sizeof(*ce_this));
 221     ce_this->next = b->file[cat].cache_entries;
 222     b->file[cat].cache_entries = ce_this;
 223     ce_this->buf = xmalloc (ISAMB_CACHE_ENTRY_SIZE);
 224     ce_this->pos = norm;
 225     yaz_log (b->log_io, "bf_read: get_block");
 226     if (!bf_read (b->file[cat].bf, norm, 0, 0, ce_this->buf))
 227         memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
 228     if (wr)
 229     {
 230         memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
 231         ce_this->dirty = 1;
 232     }
 233     else
 234     {
 235         ce_this->dirty = 0;
 236         memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
 237     }
 238     return 1;
 239 }
 240
 241
 242 void isamb_close (ISAMB isamb)
 243 {
 244     int i;
 245     for (i = 0; i<isamb->no_cat; i++)
 246     {
 247         flush_blocks (isamb, i);
 248         if (isamb->file[i].head_dirty)
 249             bf_write (isamb->file[i].bf, 0, 0,
 250                       sizeof(struct ISAMB_head), &isamb->file[i].head);
 251
 252     }
 253     xfree (isamb->file);
 254     xfree (isamb->method);
 255     xfree (isamb);
 256 }
 257
 258
 259 struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
 260 {
 261     int cat = pos&3;
 262     struct ISAMB_block *p;
 263     if (!pos)
 264         return 0;
 265     p = xmalloc (sizeof(*p));
 266     p->pos = pos;
 267     p->cat = pos & 3;
 268     p->buf = xmalloc (b->file[cat].head.block_size);
 269
 270     if (!get_block (b, pos, p->buf, 0))
 271     {
 272         yaz_log (b->log_io, "bf_read: open_block");
 273         if (!bf_read (b->file[cat].bf, pos/4, 0, 0, p->buf))
 274         {
 275             yaz_log (LOG_FATAL, "read failure for pos=%ld block=%ld",
 276                      (long) pos, (long) pos/4);
 277             abort();
 278         }
 279     }
 280     p->bytes = p->buf + ISAMB_DATA_OFFSET;
 281     p->leaf = p->buf[0];
 282     p->size = p->buf[1] + 256 * p->buf[2] - ISAMB_DATA_OFFSET;
 283     p->offset = 0;
 284     p->dirty = 0;
 285     p->deleted = 0;
 286     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
 287     return p;
 288 }
 289
 290 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
 291 {
 292     struct ISAMB_block *p;
 293
 294     p = xmalloc (sizeof(*p));
 295     p->buf = xmalloc (b->file[cat].head.block_size);
 296
 297     if (!b->file[cat].head.free_list)
 298     {
 299         int block_no;
 300         block_no = b->file[cat].head.last_block++;
 301         p->pos = block_no * 4 + cat;
 302     }
 303     else
 304     {
 305         p->pos = b->file[cat].head.free_list;
 306         if (!get_block (b, p->pos, p->buf, 0))
 307         {
 308             yaz_log (b->log_io, "bf_read: new_block");
 309             if (!bf_read (b->file[cat].bf, p->pos/4, 0, 0, p->buf))
 310             {
 311                 yaz_log (LOG_FATAL, "read failure for pos=%ld block=%ld",
 312                          (long) p->pos/4, (long) p->pos/4);
 313                 abort ();
 314             }
 315         }
 316         yaz_log (b->log_freelist, "got block %d from freelist %d:%d", p->pos,
 317                  cat, p->pos/4);
 318         memcpy (&b->file[cat].head.free_list, p->buf, sizeof(int));
 319     }
 320     p->cat = cat;
 321     b->file[cat].head_dirty = 1;
 322     memset (p->buf, 0, b->file[cat].head.block_size);
 323     p->bytes = p->buf + ISAMB_DATA_OFFSET;
 324     p->leaf = leaf;
 325     p->size = 0;
 326     p->dirty = 1;
 327     p->deleted = 0;
 328     p->offset = 0;
 329     p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE);
 330     return p;
 331 }
 332
 333 struct ISAMB_block *new_leaf (ISAMB b, int cat)
 334 {
 335     return new_block (b, 1, cat);
 336 }
 337
 338
 339 struct ISAMB_block *new_int (ISAMB b, int cat)
 340 {
 341     return new_block (b, 0, cat);
 342 }
 343
 344 void close_block (ISAMB b, struct ISAMB_block *p)
 345 {
 346     if (!p)
 347         return;
 348     if (p->deleted)
 349     {
 350         yaz_log (b->log_freelist, "release block %d from freelist %d:%d",
 351                  p->pos, p->cat, p->pos/4);
 352         memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(int));
 353         b->file[p->cat].head.free_list = p->pos;
 354         if (!get_block (b, p->pos, p->buf, 1))
 355         {
 356             yaz_log (b->log_io, "bf_write: close_block");
 357             bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->buf);
 358         }
 359     }
 360     else if (p->dirty)
 361     {
 362         int size = p->size + ISAMB_DATA_OFFSET;
 363         p->buf[0] = p->leaf;
 364         p->buf[1] = size & 255;
 365         p->buf[2] = size >> 8;
 366         if (!get_block (b, p->pos, p->buf, 1))
 367         {
 368             yaz_log (b->log_io, "bf_write: close_block");
 369             bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->buf);
 370         }
 371     }
 372     (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData);
 373     xfree (p->buf);
 374     xfree (p);
 375 }
 376
 377 int insert_sub (ISAMB b, struct ISAMB_block **p,
 378                 void *new_item, int *mode,
 379                 ISAMC_I stream,
 380                 struct ISAMB_block **sp,
 381                 void *sub_item, int *sub_size,
 382                 void *max_item);
 383
 384 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
 385                 int *mode,
 386                 ISAMC_I stream, struct ISAMB_block **sp,
 387                 void *split_item, int *split_size, void *last_max_item)
 388 {
 389     char *startp = p->bytes;
 390     char *src = startp;
 391     char *endp = p->bytes + p->size;
 392     int pos;
 393     struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
 394     char sub_item[DST_ITEM_MAX];
 395     int sub_size;
 396     int more;
 397
 398     *sp = 0;
 399
 400     decode_ptr (&src, &pos);
 401     while (src != endp)
 402     {
 403         int item_len;
 404         int d;
 405         decode_ptr (&src, &item_len);
 406         d = (*b->method->compare_item)(src, lookahead_item);
 407         if (d > 0)
 408         {
 409             sub_p1 = open_block (b, pos);
 410             assert (sub_p1);
 411             more = insert_sub (b, &sub_p1, lookahead_item, mode,
 412                                stream, &sub_p2,
 413                                sub_item, &sub_size, src);
 414             break;
 415         }
 416         src += item_len;
 417         decode_ptr (&src, &pos);
 418     }
 419     if (!sub_p1)
 420     {
 421         sub_p1 = open_block (b, pos);
 422         assert (sub_p1);
 423         more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
 424                            sub_item, &sub_size, last_max_item);
 425     }
 426     if (sub_p2)
 427     {
 428         /* there was a split - must insert pointer in this one */
 429         char dst_buf[DST_BUF_SIZE];
 430         char *dst = dst_buf;
 431
 432         assert (sub_size < 30 && sub_size > 1);
 433
 434         memcpy (dst, startp, src - startp);
 435
 436         dst += src - startp;
 437
 438         encode_ptr (&dst, sub_size);      /* sub length and item */
 439         memcpy (dst, sub_item, sub_size);
 440         dst += sub_size;
 441
 442         encode_ptr (&dst, sub_p2->pos);   /* pos */
 443
 444         if (endp - src)                   /* remaining data */
 445         {
 446             memcpy (dst, src, endp - src);
 447             dst += endp - src;
 448         }
 449         p->size = dst - dst_buf;
 450         if (p->size <= b->file[p->cat].head.block_max)
 451         {
 452             memcpy (startp, dst_buf, dst - dst_buf);
 453         }
 454         else
 455         {
 456             int p_new_size;
 457             char *half;
 458             src = dst_buf;
 459             endp = dst;
 460
 461             half = src + b->file[p->cat].head.block_size/2;
 462             decode_ptr (&src, &pos);
 463             while (src <= half)
 464             {
 465                 decode_ptr (&src, split_size);
 466                 src += *split_size;
 467                 decode_ptr (&src, &pos);
 468             }
 469             p_new_size = src - dst_buf;
 470             memcpy (p->bytes, dst_buf, p_new_size);
 471
 472             decode_ptr (&src, split_size);
 473             memcpy (split_item, src, *split_size);
 474             src += *split_size;
 475
 476             *sp = new_int (b, p->cat);
 477             (*sp)->size = endp - src;
 478             memcpy ((*sp)->bytes, src, (*sp)->size);
 479
 480             p->size = p_new_size;
 481         }
 482         p->dirty = 1;
 483         close_block (b, sub_p2);
 484     }
 485     close_block (b, sub_p1);
 486     return more;
 487 }
 488
 489
 490 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
 491                  int *lookahead_mode, ISAMC_I stream, struct ISAMB_block **sp2,
 492                  void *sub_item, int *sub_size,
 493                  void *max_item)
 494 {
 495     struct ISAMB_block *p = *sp1;
 496     char *src = 0, *endp = 0;
 497     char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
 498     int new_size;
 499     void *c1 = (*b->method->code_start)(ISAMC_DECODE);
 500     void *c2 = (*b->method->code_start)(ISAMC_ENCODE);
 501     int more = 1;
 502     int quater = b->file[b->no_cat-1].head.block_max / 4;
 503     char *cut = dst_buf + quater * 2;
 504     char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
 505     char *half1 = 0;
 506     char *half2 = 0;
 507     char cut_item_buf[DST_ITEM_MAX];
 508     int cut_item_size = 0;
 509
 510     if (p && p->size)
 511     {
 512         char file_item_buf[DST_ITEM_MAX];
 513         char *file_item = file_item_buf;
 514
 515         src = p->bytes;
 516         endp = p->bytes + p->size;
 517         (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 518         while (1)
 519         {
 520             char *dst_item = 0;
 521             char *dst_0 = dst;
 522             char *lookahead_next;
 523             int d = -1;
 524
 525             if (lookahead_item)
 526                 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
 527
 528             if (d > 0)
 529             {
 530                 dst_item = lookahead_item;
 531                 assert (*lookahead_mode);
 532             }
 533             else
 534                 dst_item = file_item_buf;
 535             if (!*lookahead_mode && d == 0)
 536             {
 537                 p->dirty = 1;
 538             }
 539             else if (!half1 && dst > cut)
 540             {
 541                 char *dst_item_0 = dst_item;
 542                 half1 = dst; /* candidate for splitting */
 543
 544                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &dst_item);
 545
 546                 cut_item_size = dst_item - dst_item_0;
 547                 memcpy (cut_item_buf, dst_item_0, cut_item_size);
 548
 549                 half2 = dst;
 550             }
 551             else
 552                 (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &dst_item);
 553             if (d > 0)
 554             {
 555                 if (dst > maxp)
 556                 {
 557                     dst = dst_0;
 558                     lookahead_item = 0;
 559                 }
 560                 else
 561                 {
 562                     lookahead_next = lookahead_item;
 563                     if (!(*stream->read_item)(stream->clientData,
 564                                               &lookahead_next,
 565                                               lookahead_mode))
 566                     {
 567                         lookahead_item = 0;
 568                         more = 0;
 569                     }
 570                     if (lookahead_item && max_item &&
 571                         (*b->method->compare_item)(max_item, lookahead_item) <= 0)
 572                     {
 573                         /* max_item 1 */
 574                         lookahead_item = 0;
 575                     }
 576
 577                     p->dirty = 1;
 578                 }
 579             }
 580             else if (d == 0)
 581             {
 582                 lookahead_next = lookahead_item;
 583                 if (!(*stream->read_item)(stream->clientData,
 584                                           &lookahead_next, lookahead_mode))
 585                 {
 586                     lookahead_item = 0;
 587                     more = 0;
 588                 }
 589                 if (src == endp)
 590                     break;
 591                 file_item = file_item_buf;
 592                 (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 593             }
 594             else
 595             {
 596                 if (src == endp)
 597                     break;
 598                 file_item = file_item_buf;
 599                 (*b->method->code_item)(ISAMC_DECODE, c1, &file_item, &src);
 600             }
 601         }
 602     }
 603     maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
 604     while (lookahead_item)
 605     {
 606         char *dst_item = lookahead_item;
 607         char *dst_0 = dst;
 608
 609         if (max_item &&
 610             (*b->method->compare_item)(max_item, lookahead_item) <= 0)
 611         {
 612             /* max_item 2 */
 613             break;
 614         }
 615         if (!*lookahead_mode)
 616         {
 617             yaz_log (LOG_WARN, "Inconsistent register (2)");
 618             abort();
 619         }
 620         else if (!half1 && dst > cut)
 621         {
 622             char *dst_item_0 = dst_item;
 623             half1 = dst; /* candidate for splitting */
 624
 625             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &dst_item);
 626
 627             cut_item_size = dst_item - dst_item_0;
 628             memcpy (cut_item_buf, dst_item_0, cut_item_size);
 629
 630             half2 = dst;
 631         }
 632         else
 633             (*b->method->code_item)(ISAMC_ENCODE, c2, &dst, &dst_item);
 634
 635         if (dst > maxp)
 636         {
 637             dst = dst_0;
 638             break;
 639         }
 640         if (p)
 641             p->dirty = 1;
 642         dst_item = lookahead_item;
 643         if (!(*stream->read_item)(stream->clientData, &dst_item,
 644                                   lookahead_mode))
 645         {
 646             lookahead_item = 0;
 647             more = 0;
 648         }
 649     }
 650     new_size = dst - dst_buf;
 651     if (p && p->cat != b->no_cat-1 &&
 652         new_size > b->file[p->cat].head.block_max)
 653     {
 654         /* non-btree block will be removed */
 655         p->deleted = 1;
 656         close_block (b, p);
 657         /* delete it too!! */
 658         p = 0; /* make a new one anyway */
 659     }
 660     if (!p)
 661     {   /* must create a new one */
 662         int i;
 663         for (i = 0; i < b->no_cat; i++)
 664             if (new_size <= b->file[i].head.block_max)
 665                 break;
 666         if (i == b->no_cat)
 667             i = b->no_cat - 1;
 668         p = new_leaf (b, i);
 669     }
 670     if (new_size > b->file[p->cat].head.block_max)
 671     {
 672         char *first_dst;
 673         char *cut_item = cut_item_buf;
 674
 675         assert (half1);
 676         assert (half2);
 677
 678        /* first half */
 679         p->size = half1 - dst_buf;
 680         memcpy (p->bytes, dst_buf, half1 - dst_buf);
 681
 682         /* second half */
 683         *sp2 = new_leaf (b, p->cat);
 684
 685         (*b->method->code_reset)(c2);
 686
 687         first_dst = (*sp2)->bytes;
 688
 689         (*b->method->code_item)(ISAMC_ENCODE, c2, &first_dst, &cut_item);
 690
 691         memcpy (first_dst, half2, dst - half2);
 692
 693         (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
 694         (*sp2)->dirty = 1;
 695         p->dirty = 1;
 696         memcpy (sub_item, cut_item_buf, cut_item_size);
 697         *sub_size = cut_item_size;
 698     }
 699     else
 700     {
 701         memcpy (p->bytes, dst_buf, dst - dst_buf);
 702         p->size = new_size;
 703     }
 704     (*b->method->code_stop)(ISAMC_DECODE, c1);
 705     (*b->method->code_stop)(ISAMC_ENCODE, c2);
 706     *sp1 = p;
 707     return more;
 708 }
 709
 710 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
 711                 int *mode,
 712                 ISAMC_I stream,
 713                 struct ISAMB_block **sp,
 714                 void *sub_item, int *sub_size,
 715                 void *max_item)
 716 {
 717     if (!*p || (*p)->leaf)
 718         return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
 719                             sub_size, max_item);
 720     else
 721         return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
 722                            sub_size, max_item);
 723 }
 724
 725 int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I stream)
 726 {
 727     char item_buf[DST_ITEM_MAX];
 728     char *item_ptr;
 729     int i_mode;
 730     int more;
 731
 732     if (b->cache < 0)
 733     {
 734         int more = 1;
 735         while (more)
 736         {
 737             item_ptr = item_buf;
 738             more =
 739                 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
 740         }
 741         return 1;
 742     }
 743     item_ptr = item_buf;
 744     more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
 745     while (more)
 746     {
 747         struct ISAMB_block *p = 0, *sp = 0;
 748         char sub_item[DST_ITEM_MAX];
 749         int sub_size;
 750
 751         if (pos)
 752             p = open_block (b, pos);
 753         more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
 754                             sub_item, &sub_size, 0);
 755         if (sp)
 756         {    /* increase level of tree by one */
 757             struct ISAMB_block *p2 = new_int (b, p->cat);
 758             char *dst = p2->bytes + p2->size;
 759
 760             encode_ptr (&dst, p->pos);
 761             assert (sub_size < 20);
 762             encode_ptr (&dst, sub_size);
 763             memcpy (dst, sub_item, sub_size);
 764             dst += sub_size;
 765             encode_ptr (&dst, sp->pos);
 766
 767             p2->size = dst - p2->bytes;
 768             pos = p2->pos;  /* return new super page */
 769             close_block (b, sp);
 770             close_block (b, p2);
 771         }
 772         else
 773             pos = p->pos;   /* return current one (again) */
 774         close_block (b, p);
 775     }
 776     return pos;
 777 }
 778
 779 ISAMB_PP isamb_pp_open_x (ISAMB isamb, ISAMB_P pos, int *level)
 780 {
 781     ISAMB_PP pp = xmalloc (sizeof(*pp));
 782
 783     pp->isamb = isamb;
 784     pp->block = xmalloc (10 * sizeof(*pp->block));
 785
 786     pp->pos = pos;
 787     pp->level = 0;
 788     pp->total_size = 0;
 789     pp->no_blocks = 0;
 790     while (1)
 791     {
 792         struct ISAMB_block *p = open_block (isamb, pos);
 793         char *src = p->bytes + p->offset;
 794         pp->block[pp->level] = p;
 795
 796         pp->total_size += p->size;
 797         pp->no_blocks++;
 798
 799         if (p->leaf)
 800             break;
 801
 802         decode_ptr (&src, &pos);
 803         p->offset = src - p->bytes;
 804         pp->level++;
 805     }
 806     pp->block[pp->level+1] = 0;
 807     if (level)
 808         *level = pp->level;
 809     return pp;
 810 }
 811
 812 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
 813 {
 814     return isamb_pp_open_x (isamb, pos, 0);
 815 }
 816
 817 void isamb_pp_close_x (ISAMB_PP pp, int *size, int *blocks)
 818 {
 819     int i;
 820     if (!pp)
 821         return;
 822     if (size)
 823         *size = pp->total_size;
 824     if (blocks)
 825         *blocks = pp->no_blocks;
 826     for (i = 0; i <= pp->level; i++)
 827         close_block (pp->isamb, pp->block[i]);
 828     xfree (pp->block);
 829     xfree (pp);
 830 }
 831
 832 int isamb_block_info (ISAMB isamb, int cat)
 833 {
 834     if (cat >= 0 && cat < isamb->no_cat)
 835         return isamb->file[cat].head.block_size;
 836     return -1;
 837 }
 838
 839 void isamb_pp_close (ISAMB_PP pp)
 840 {
 841     isamb_pp_close_x (pp, 0, 0);
 842 }
 843
 844 int isamb_pp_read (ISAMB_PP pp, void *buf)
 845 {
 846     char *dst = buf;
 847     char *src;
 848     struct ISAMB_block *p = pp->block[pp->level];
 849     if (!p)
 850         return 0;
 851
 852     while (p->offset == p->size)
 853     {
 854         int pos, item_len;
 855         while (p->offset == p->size)
 856         {
 857             if (pp->level == 0)
 858                 return 0;
 859             close_block (pp->isamb, pp->block[pp->level]);
 860             pp->block[pp->level] = 0;
 861             (pp->level)--;
 862             p = pp->block[pp->level];
 863             assert (!p->leaf);  /* must be int */
 864         }
 865         src = p->bytes + p->offset;
 866
 867         decode_ptr (&src, &item_len);
 868         src += item_len;
 869         decode_ptr (&src, &pos);
 870
 871         p->offset = src - (char*) p->bytes;
 872
 873         ++(pp->level);
 874
 875         while (1)
 876         {
 877             pp->block[pp->level] = p = open_block (pp->isamb, pos);
 878
 879             pp->total_size += p->size;
 880             pp->no_blocks++;
 881
 882             if (p->leaf) /* leaf */
 883             {
 884                 break;
 885             }
 886             src = p->bytes + p->offset;
 887             decode_ptr (&src, &pos);
 888             p->offset = src - (char*) p->bytes;
 889             pp->level++;
 890         }
 891     }
 892     assert (p->offset < p->size);
 893     assert (p->leaf);
 894     src = p->bytes + p->offset;
 895     (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData,
 896                                     &dst, &src);
 897     p->offset = src - (char*) p->bytes;
 898     return 1;
 899 }
 900
 901 int isamb_pp_num (ISAMB_PP pp)
 902 {
 903     return 1;
 904 }