isamb/isamb.c

   1 /* $Id: isamb.c,v 1.90 2006-12-19 00:25:41 adam Exp $
   2    Copyright (C) 1995-2006
   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 this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <yaz/log.h>
  26 #include <yaz/xmalloc.h>
  27 #include <idzebra/isamb.h>
  28 #include <assert.h>
  29
  30 #ifndef ISAMB_DEBUG
  31 #define ISAMB_DEBUG 0
  32 #endif
  33
  34
  35 #define ISAMB_MAJOR_VERSION 3
  36 #define ISAMB_MINOR_VERSION_NO_ROOT 0
  37 #define ISAMB_MINOR_VERSION_WITH_ROOT 1
  38
  39 struct ISAMB_head {
  40     zint first_block;
  41     zint last_block;
  42     zint free_list;
  43     zint no_items;
  44     int block_size;
  45     int block_max;
  46     int block_offset;
  47 };
  48
  49 /* if 1, upper nodes items are encoded; 0 if not encoded */
  50 #define INT_ENCODE 1
  51
  52 /* maximum size of encoded buffer */
  53 #define DST_ITEM_MAX 256
  54
  55 #define ISAMB_MAX_LEVEL 10
  56 /* approx 2*max page + max size of item */
  57 #define DST_BUF_SIZE (2*4096+300)
  58
  59 /* should be maximum block size of multiple thereof */
  60 #define ISAMB_CACHE_ENTRY_SIZE 4096
  61
  62 /* CAT_MAX: _must_ be power of 2 */
  63 #define CAT_MAX 4
  64 #define CAT_MASK (CAT_MAX-1)
  65 /* CAT_NO: <= CAT_MAX */
  66 #define CAT_NO 4
  67
  68 /* Smallest block size */
  69 #define ISAMB_MIN_SIZE 32
  70 /* Size factor */
  71 #define ISAMB_FAC_SIZE 4
  72
  73 /* ISAMB_PTR_CODEC = 1 var, =0 fixed */
  74 #define ISAMB_PTR_CODEC 1
  75
  76 struct ISAMB_cache_entry {
  77     ISAM_P pos;
  78     unsigned char *buf;
  79     int dirty;
  80     int hits;
  81     struct ISAMB_cache_entry *next;
  82 };
  83
  84 struct ISAMB_file {
  85     BFile bf;
  86     int head_dirty;
  87     struct ISAMB_head head;
  88     struct ISAMB_cache_entry *cache_entries;
  89 };
  90
  91 struct ISAMB_s {
  92     BFiles bfs;
  93     ISAMC_M *method;
  94
  95     struct ISAMB_file *file;
  96     int no_cat;
  97     int cache; /* 0 = no cache, 1 = use cache, -1 = dummy isam (for testing only) */
  98     int log_io;        /* log level for bf_read/bf_write calls */
  99     int log_freelist;  /* log level for freelist handling */
 100     zint skipped_numbers; /* on a leaf node */
 101     zint returned_numbers;
 102     zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1 = higher etc */
 103     zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
 104     zint number_of_int_splits;
 105     zint number_of_leaf_splits;
 106     int enable_int_count; /* whether we count nodes (or not) */
 107     int cache_size; /* size of blocks to cache (if cache=1) */
 108     int minor_version;
 109     zint root_ptr;
 110 };
 111
 112 struct ISAMB_block {
 113     ISAM_P pos;
 114     int cat;
 115     int size;
 116     int leaf;
 117     int dirty;
 118     int deleted;
 119     int offset;
 120     zint no_items;  /* number of nodes in this + children */
 121     char *bytes;
 122     char *cbuf;
 123     unsigned char *buf;
 124     void *decodeClientData;
 125     int log_rw;
 126 };
 127
 128 struct ISAMB_PP_s {
 129     ISAMB isamb;
 130     ISAM_P pos;
 131     int level;
 132     int maxlevel; /* total depth */
 133     zint total_size;
 134     zint no_blocks;
 135     zint skipped_numbers; /* on a leaf node */
 136     zint returned_numbers;
 137     zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1 = higher etc */
 138     zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
 139     struct ISAMB_block **block;
 140     int scope;  /* on what level we forward */
 141 };
 142
 143
 144 #define encode_item_len encode_ptr
 145 #if ISAMB_PTR_CODEC
 146 static void encode_ptr(char **dst, zint pos)
 147 {
 148     unsigned char *bp = (unsigned char*) *dst;
 149
 150     while (pos > 127)
 151     {
 152          *bp++ = (unsigned char) (128 | (pos & 127));
 153          pos = pos >> 7;
 154     }
 155     *bp++ = (unsigned char) pos;
 156     *dst = (char *) bp;
 157 }
 158 #else
 159 static void encode_ptr(char **dst, zint pos)
 160 {
 161     memcpy(*dst, &pos, sizeof(pos));
 162     (*dst) += sizeof(pos);
 163 }
 164 #endif
 165
 166 #define decode_item_len decode_ptr
 167 #if ISAMB_PTR_CODEC
 168 static void decode_ptr(const char **src, zint *pos)
 169 {
 170     zint d = 0;
 171     unsigned char c;
 172     unsigned r = 0;
 173
 174     while (((c = *(const unsigned char *)((*src)++)) & 128))
 175     {
 176         d += ((zint) (c & 127) << r);
 177         r += 7;
 178     }
 179     d += ((zint) c << r);
 180     *pos = d;
 181 }
 182 #else
 183 static void decode_ptr(const char **src, zint *pos)
 184 {
 185      memcpy(pos, *src, sizeof(*pos));
 186      (*src) += sizeof(*pos);
 187 }
 188 #endif
 189
 190
 191 void isamb_set_int_count(ISAMB b, int v)
 192 {
 193     b->enable_int_count = v;
 194 }
 195
 196 void isamb_set_cache_size(ISAMB b, int v)
 197 {
 198     b->cache_size = v;
 199 }
 200
 201 ISAMB isamb_open2(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
 202                   int cache, int no_cat, int *sizes, int use_root_ptr)
 203 {
 204     ISAMB isamb = xmalloc(sizeof(*isamb));
 205     int i;
 206
 207     assert(no_cat <= CAT_MAX);
 208
 209     isamb->bfs = bfs;
 210     isamb->method = (ISAMC_M *) xmalloc(sizeof(*method));
 211     memcpy(isamb->method, method, sizeof(*method));
 212     isamb->no_cat = no_cat;
 213     isamb->log_io = 0;
 214     isamb->log_freelist = 0;
 215     isamb->cache = cache;
 216     isamb->skipped_numbers = 0;
 217     isamb->returned_numbers = 0;
 218     isamb->number_of_int_splits = 0;
 219     isamb->number_of_leaf_splits = 0;
 220     isamb->enable_int_count = 1;
 221     isamb->cache_size = 40;
 222
 223     if (use_root_ptr)
 224         isamb->minor_version = ISAMB_MINOR_VERSION_WITH_ROOT;
 225     else
 226         isamb->minor_version = ISAMB_MINOR_VERSION_NO_ROOT;
 227
 228     isamb->root_ptr = 0;
 229
 230     for (i = 0; i<ISAMB_MAX_LEVEL; i++)
 231         isamb->skipped_nodes[i] = isamb->accessed_nodes[i] = 0;
 232
 233     if (cache == -1)
 234     {
 235         yaz_log(YLOG_WARN, "isamb_open %s. Degraded TEST mode", name);
 236     }
 237     else
 238     {
 239         assert(cache == 0 || cache == 1);
 240     }
 241     isamb->file = xmalloc(sizeof(*isamb->file) * isamb->no_cat);
 242
 243     for (i = 0; i < isamb->no_cat; i++)
 244     {
 245         isamb->file[i].bf = 0;
 246         isamb->file[i].head_dirty = 0;
 247         isamb->file[i].cache_entries = 0;
 248     }
 249
 250     for (i = 0; i < isamb->no_cat; i++)
 251     {
 252         char fname[DST_BUF_SIZE];
 253         char hbuf[DST_BUF_SIZE];
 254
 255         sprintf(fname, "%s%c", name, i+'A');
 256         if (cache)
 257             isamb->file[i].bf = bf_open(bfs, fname, ISAMB_CACHE_ENTRY_SIZE,
 258                                          writeflag);
 259         else
 260             isamb->file[i].bf = bf_open(bfs, fname, sizes[i], writeflag);
 261
 262         if (!isamb->file[i].bf)
 263         {
 264             isamb_close(isamb);
 265             return 0;
 266         }
 267
 268         /* fill-in default values (for empty isamb) */
 269         isamb->file[i].head.first_block = ISAMB_CACHE_ENTRY_SIZE/sizes[i]+1;
 270         isamb->file[i].head.last_block = isamb->file[i].head.first_block;
 271         isamb->file[i].head.block_size = sizes[i];
 272         assert(sizes[i] <= ISAMB_CACHE_ENTRY_SIZE);
 273 #if ISAMB_PTR_CODEC
 274         if (i == isamb->no_cat-1 || sizes[i] > 128)
 275             isamb->file[i].head.block_offset = 8;
 276         else
 277             isamb->file[i].head.block_offset = 4;
 278 #else
 279         isamb->file[i].head.block_offset = 11;
 280 #endif
 281         isamb->file[i].head.block_max =
 282             sizes[i] - isamb->file[i].head.block_offset;
 283         isamb->file[i].head.free_list = 0;
 284         if (bf_read(isamb->file[i].bf, 0, 0, 0, hbuf))
 285         {
 286             /* got header assume "isamb"major minor len can fit in 16 bytes */
 287             zint zint_tmp;
 288             int major, minor, len, pos = 0;
 289             int left;
 290             const char *src = 0;
 291             if (memcmp(hbuf, "isamb", 5))
 292             {
 293                 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
 294                 return 0;
 295             }
 296             if (sscanf(hbuf+5, "%d %d %d", &major, &minor, &len) != 3)
 297             {
 298                 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
 299                 return 0;
 300             }
 301             if (major != ISAMB_MAJOR_VERSION)
 302             {
 303                 yaz_log(YLOG_WARN, "bad major version for file %s %d, must be %d",
 304                      fname, major, ISAMB_MAJOR_VERSION);
 305                 return 0;
 306             }
 307             for (left = len - sizes[i]; left > 0; left = left - sizes[i])
 308             {
 309                 pos++;
 310                 if (!bf_read(isamb->file[i].bf, pos, 0, 0, hbuf + pos*sizes[i]))
 311                 {
 312                     yaz_log(YLOG_WARN, "truncated isamb header for "
 313                          "file=%s len=%d pos=%d",
 314                          fname, len, pos);
 315                     return 0;
 316                 }
 317             }
 318             src = hbuf + 16;
 319             decode_ptr(&src, &isamb->file[i].head.first_block);
 320             decode_ptr(&src, &isamb->file[i].head.last_block);
 321             decode_ptr(&src, &zint_tmp);
 322             isamb->file[i].head.block_size = (int) zint_tmp;
 323             decode_ptr(&src, &zint_tmp);
 324             isamb->file[i].head.block_max = (int) zint_tmp;
 325             decode_ptr(&src, &isamb->file[i].head.free_list);
 326             if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
 327                 decode_ptr(&src, &isamb->root_ptr);
 328         }
 329         assert (isamb->file[i].head.block_size >= isamb->file[i].head.block_offset);
 330         isamb->file[i].head_dirty = 0;
 331         assert(isamb->file[i].head.block_size == sizes[i]);
 332     }
 333 #if ISAMB_DEBUG
 334     yaz_log(YLOG_WARN, "isamb debug enabled. Things will be slower than usual");
 335 #endif
 336     return isamb;
 337 }
 338
 339 ISAMB isamb_open(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
 340                  int cache)
 341 {
 342     int sizes[CAT_NO];
 343     int i, b_size = ISAMB_MIN_SIZE;
 344
 345     for (i = 0; i<CAT_NO; i++)
 346     {
 347         sizes[i] = b_size;
 348         b_size = b_size * ISAMB_FAC_SIZE;
 349     }
 350     return isamb_open2(bfs, name, writeflag, method, cache,
 351                        CAT_NO, sizes, 0);
 352 }
 353
 354 static void flush_blocks (ISAMB b, int cat)
 355 {
 356     while (b->file[cat].cache_entries)
 357     {
 358         struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
 359         b->file[cat].cache_entries = ce_this->next;
 360
 361         if (ce_this->dirty)
 362         {
 363             yaz_log(b->log_io, "bf_write: flush_blocks");
 364             bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
 365         }
 366         xfree(ce_this->buf);
 367         xfree(ce_this);
 368     }
 369 }
 370
 371 static int cache_block (ISAMB b, ISAM_P pos, unsigned char *userbuf, int wr)
 372 {
 373     int cat = (int) (pos&CAT_MASK);
 374     int off = (int) (((pos/CAT_MAX) &
 375                (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
 376         * b->file[cat].head.block_size);
 377     zint norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
 378     int no = 0;
 379     struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
 380
 381     if (!b->cache)
 382         return 0;
 383
 384     assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
 385     for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
 386     {
 387         ce_last = ce;
 388         if ((*ce)->pos == norm)
 389         {
 390             ce_this = *ce;
 391             *ce = (*ce)->next;   /* remove from list */
 392
 393             ce_this->next = b->file[cat].cache_entries;  /* move to front */
 394             b->file[cat].cache_entries = ce_this;
 395
 396             if (wr)
 397             {
 398                 memcpy (ce_this->buf + off, userbuf,
 399                         b->file[cat].head.block_size);
 400                 ce_this->dirty = 1;
 401             }
 402             else
 403                 memcpy (userbuf, ce_this->buf + off,
 404                         b->file[cat].head.block_size);
 405             return 1;
 406         }
 407     }
 408     if (no >= b->cache_size)
 409     {
 410         assert (ce_last && *ce_last);
 411         ce_this = *ce_last;
 412         *ce_last = 0;  /* remove the last entry from list */
 413         if (ce_this->dirty)
 414         {
 415             yaz_log(b->log_io, "bf_write: cache_block");
 416             bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
 417         }
 418         xfree(ce_this->buf);
 419         xfree(ce_this);
 420     }
 421     ce_this = xmalloc(sizeof(*ce_this));
 422     ce_this->next = b->file[cat].cache_entries;
 423     b->file[cat].cache_entries = ce_this;
 424     ce_this->buf = xmalloc(ISAMB_CACHE_ENTRY_SIZE);
 425     ce_this->pos = norm;
 426     yaz_log(b->log_io, "bf_read: cache_block");
 427     if (!bf_read(b->file[cat].bf, norm, 0, 0, ce_this->buf))
 428         memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
 429     if (wr)
 430     {
 431         memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
 432         ce_this->dirty = 1;
 433     }
 434     else
 435     {
 436         ce_this->dirty = 0;
 437         memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
 438     }
 439     return 1;
 440 }
 441
 442
 443 void isamb_close (ISAMB isamb)
 444 {
 445     int i;
 446     for (i = 0; isamb->accessed_nodes[i]; i++)
 447         yaz_log(YLOG_DEBUG, "isamb_close  level leaf-%d: "ZINT_FORMAT" read, "
 448                         ZINT_FORMAT" skipped",
 449              i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]);
 450     yaz_log(YLOG_DEBUG, "isamb_close returned "ZINT_FORMAT" values, "
 451                    "skipped "ZINT_FORMAT,
 452          isamb->skipped_numbers, isamb->returned_numbers);
 453     for (i = 0; i<isamb->no_cat; i++)
 454     {
 455         flush_blocks (isamb, i);
 456         if (isamb->file[i].head_dirty)
 457         {
 458             char hbuf[DST_BUF_SIZE];
 459             int major = ISAMB_MAJOR_VERSION;
 460             int len = 16;
 461             char *dst = hbuf + 16;
 462             int pos = 0, left;
 463             int b_size = isamb->file[i].head.block_size;
 464
 465             encode_ptr(&dst, isamb->file[i].head.first_block);
 466             encode_ptr(&dst, isamb->file[i].head.last_block);
 467             encode_ptr(&dst, isamb->file[i].head.block_size);
 468             encode_ptr(&dst, isamb->file[i].head.block_max);
 469             encode_ptr(&dst, isamb->file[i].head.free_list);
 470
 471             if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
 472                 encode_ptr(&dst, isamb->root_ptr);
 473
 474             memset(dst, '\0', b_size); /* ensure no random bytes are written */
 475
 476             len = dst - hbuf;
 477
 478             /* print exactly 16 bytes (including trailing 0) */
 479             sprintf(hbuf, "isamb%02d %02d %02d\r\n", major,
 480                     isamb->minor_version, len);
 481
 482             bf_write(isamb->file[i].bf, pos, 0, 0, hbuf);
 483
 484             for (left = len - b_size; left > 0; left = left - b_size)
 485             {
 486                 pos++;
 487                 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
 488             }
 489         }
 490         if (isamb->file[i].bf)
 491             bf_close (isamb->file[i].bf);
 492     }
 493     xfree(isamb->file);
 494     xfree(isamb->method);
 495     xfree(isamb);
 496 }
 497
 498 /* open_block: read one block at pos.
 499    Decode leading sys bytes .. consisting of
 500    Offset:Meaning
 501    0: leader byte, != 0 leaf, == 0, non-leaf
 502    1-2: used size of block
 503    3-7*: number of items and all children
 504
 505    * Reserve 5 bytes for large block sizes. 1 for small ones .. Number
 506    of items. We can thus have at most 2^40 nodes.
 507 */
 508 static struct ISAMB_block *open_block(ISAMB b, ISAM_P pos)
 509 {
 510     int cat = (int) (pos&CAT_MASK);
 511     const char *src;
 512     int offset = b->file[cat].head.block_offset;
 513     struct ISAMB_block *p;
 514     if (!pos)
 515         return 0;
 516     p = xmalloc(sizeof(*p));
 517     p->pos = pos;
 518     p->cat = (int) (pos & CAT_MASK);
 519     p->buf = xmalloc(b->file[cat].head.block_size);
 520     p->cbuf = 0;
 521
 522     if (!cache_block (b, pos, p->buf, 0))
 523     {
 524         yaz_log(b->log_io, "bf_read: open_block");
 525         if (bf_read(b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf) != 1)
 526         {
 527             yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
 528                      (long) pos, (long) pos/CAT_MAX);
 529             zebra_exit("isamb:open_block");
 530         }
 531     }
 532     p->bytes = (char *)p->buf + offset;
 533     p->leaf = p->buf[0];
 534     p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
 535     if (p->size < 0)
 536     {
 537         yaz_log(YLOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
 538                  p->size, pos);
 539     }
 540     assert (p->size >= 0);
 541     src = (char*) p->buf + 3;
 542     decode_ptr(&src, &p->no_items);
 543
 544     p->offset = 0;
 545     p->dirty = 0;
 546     p->deleted = 0;
 547     p->decodeClientData = (*b->method->codec.start)();
 548     return p;
 549 }
 550
 551 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
 552 {
 553     struct ISAMB_block *p;
 554
 555     p = xmalloc(sizeof(*p));
 556     p->buf = xmalloc(b->file[cat].head.block_size);
 557
 558     if (!b->file[cat].head.free_list)
 559     {
 560         zint block_no;
 561         block_no = b->file[cat].head.last_block++;
 562         p->pos = block_no * CAT_MAX + cat;
 563     }
 564     else
 565     {
 566         p->pos = b->file[cat].head.free_list;
 567         assert((p->pos & CAT_MASK) == cat);
 568         if (!cache_block (b, p->pos, p->buf, 0))
 569         {
 570             yaz_log(b->log_io, "bf_read: new_block");
 571             if (!bf_read(b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf))
 572             {
 573                 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
 574                          (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX);
 575                 zebra_exit("isamb:new_block");
 576             }
 577         }
 578         yaz_log(b->log_freelist, "got block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT, p->pos,
 579                  cat, p->pos/CAT_MAX);
 580         memcpy (&b->file[cat].head.free_list, p->buf, sizeof(zint));
 581     }
 582     p->cat = cat;
 583     b->file[cat].head_dirty = 1;
 584     memset (p->buf, 0, b->file[cat].head.block_size);
 585     p->bytes = (char*)p->buf + b->file[cat].head.block_offset;
 586     p->leaf = leaf;
 587     p->size = 0;
 588     p->dirty = 1;
 589     p->deleted = 0;
 590     p->offset = 0;
 591     p->no_items = 0;
 592     p->decodeClientData = (*b->method->codec.start)();
 593     return p;
 594 }
 595
 596 struct ISAMB_block *new_leaf (ISAMB b, int cat)
 597 {
 598     return new_block (b, 1, cat);
 599 }
 600
 601
 602 struct ISAMB_block *new_int (ISAMB b, int cat)
 603 {
 604     return new_block (b, 0, cat);
 605 }
 606
 607 static void check_block (ISAMB b, struct ISAMB_block *p)
 608 {
 609     assert(b); /* mostly to make the compiler shut up about unused b */
 610     if (p->leaf)
 611     {
 612         ;
 613     }
 614     else
 615     {
 616         /* sanity check */
 617         char *startp = p->bytes;
 618         const char *src = startp;
 619         char *endp = p->bytes + p->size;
 620         ISAM_P pos;
 621         void *c1 = (*b->method->codec.start)();
 622
 623         decode_ptr(&src, &pos);
 624         assert ((pos&CAT_MASK) == p->cat);
 625         while (src != endp)
 626         {
 627 #if INT_ENCODE
 628             char file_item_buf[DST_ITEM_MAX];
 629             char *file_item = file_item_buf;
 630             (*b->method->codec.reset)(c1);
 631             (*b->method->codec.decode)(c1, &file_item, &src);
 632 #else
 633             zint item_len;
 634             decode_item_len(&src, &item_len);
 635             assert (item_len > 0 && item_len < 128);
 636             src += item_len;
 637 #endif
 638             decode_ptr(&src, &pos);
 639             if ((pos&CAT_MASK) != p->cat)
 640             {
 641                 assert ((pos&CAT_MASK) == p->cat);
 642             }
 643         }
 644         (*b->method->codec.stop)(c1);
 645     }
 646 }
 647
 648 void close_block(ISAMB b, struct ISAMB_block *p)
 649 {
 650     if (!p)
 651         return;
 652     if (p->deleted)
 653     {
 654         yaz_log(b->log_freelist, "release block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT,
 655                  p->pos, p->cat, p->pos/CAT_MAX);
 656         memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(zint));
 657         b->file[p->cat].head.free_list = p->pos;
 658         if (!cache_block (b, p->pos, p->buf, 1))
 659         {
 660             yaz_log(b->log_io, "bf_write: close_block (deleted)");
 661             bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
 662         }
 663     }
 664     else if (p->dirty)
 665     {
 666         int offset = b->file[p->cat].head.block_offset;
 667         int size = p->size + offset;
 668         char *dst =  (char*)p->buf + 3;
 669         assert (p->size >= 0);
 670
 671         /* memset becuase encode_ptr usually does not write all bytes */
 672         memset(p->buf, 0, b->file[p->cat].head.block_offset);
 673         p->buf[0] = p->leaf;
 674         p->buf[1] = size & 255;
 675         p->buf[2] = size >> 8;
 676         encode_ptr(&dst, p->no_items);
 677         check_block(b, p);
 678         if (!cache_block (b, p->pos, p->buf, 1))
 679         {
 680             yaz_log(b->log_io, "bf_write: close_block");
 681             bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
 682         }
 683     }
 684     (*b->method->codec.stop)(p->decodeClientData);
 685     xfree(p->buf);
 686     xfree(p);
 687 }
 688
 689 int insert_sub (ISAMB b, struct ISAMB_block **p,
 690                 void *new_item, int *mode,
 691                 ISAMC_I *stream,
 692                 struct ISAMB_block **sp,
 693                 void *sub_item, int *sub_size,
 694                 const void *max_item);
 695
 696 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
 697                 int *mode,
 698                 ISAMC_I *stream, struct ISAMB_block **sp,
 699                 void *split_item, int *split_size, const void *last_max_item)
 700 {
 701     char *startp = p->bytes;
 702     const char *src = startp;
 703     char *endp = p->bytes + p->size;
 704     ISAM_P pos;
 705     struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
 706     char sub_item[DST_ITEM_MAX];
 707     int sub_size;
 708     int more = 0;
 709     zint diff_terms = 0;
 710     void *c1 = (*b->method->codec.start)();
 711
 712     *sp = 0;
 713
 714     assert(p->size >= 0);
 715     decode_ptr(&src, &pos);
 716     while (src != endp)
 717     {
 718         int d;
 719         const char *src0 = src;
 720 #if INT_ENCODE
 721         char file_item_buf[DST_ITEM_MAX];
 722         char *file_item = file_item_buf;
 723         (*b->method->codec.reset)(c1);
 724         (*b->method->codec.decode)(c1, &file_item, &src);
 725         d = (*b->method->compare_item)(file_item_buf, lookahead_item);
 726         if (d > 0)
 727         {
 728             sub_p1 = open_block(b, pos);
 729             assert (sub_p1);
 730             diff_terms -= sub_p1->no_items;
 731             more = insert_sub (b, &sub_p1, lookahead_item, mode,
 732                                stream, &sub_p2,
 733                                sub_item, &sub_size, file_item_buf);
 734             diff_terms += sub_p1->no_items;
 735             src = src0;
 736             break;
 737         }
 738 #else
 739         zint item_len;
 740         decode_item_len(&src, &item_len);
 741         d = (*b->method->compare_item)(src, lookahead_item);
 742         if (d > 0)
 743         {
 744             sub_p1 = open_block(b, pos);
 745             assert (sub_p1);
 746             diff_terms -= sub_p1->no_items;
 747             more = insert_sub (b, &sub_p1, lookahead_item, mode,
 748                                stream, &sub_p2,
 749                                sub_item, &sub_size, src);
 750             diff_terms += sub_p1->no_items;
 751             src = src0;
 752             break;
 753         }
 754         src += item_len;
 755 #endif
 756         decode_ptr(&src, &pos);
 757     }
 758     if (!sub_p1)
 759     {
 760         /* we reached the end. So lookahead > last item */
 761         sub_p1 = open_block(b, pos);
 762         assert (sub_p1);
 763         diff_terms -= sub_p1->no_items;
 764         more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
 765                            sub_item, &sub_size, last_max_item);
 766         diff_terms += sub_p1->no_items;
 767     }
 768     if (sub_p2)
 769         diff_terms += sub_p2->no_items;
 770     if (diff_terms)
 771     {
 772         p->dirty = 1;
 773         p->no_items += diff_terms;
 774     }
 775     if (sub_p2)
 776     {
 777         /* there was a split - must insert pointer in this one */
 778         char dst_buf[DST_BUF_SIZE];
 779         char *dst = dst_buf;
 780 #if INT_ENCODE
 781         const char *sub_item_ptr = sub_item;
 782 #endif
 783         assert (sub_size < 128 && sub_size > 1);
 784
 785         memcpy (dst, startp, src - startp);
 786
 787         dst += src - startp;
 788
 789 #if INT_ENCODE
 790         (*b->method->codec.reset)(c1);
 791         (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
 792 #else
 793         encode_item_len (&dst, sub_size);      /* sub length and item */
 794         memcpy (dst, sub_item, sub_size);
 795         dst += sub_size;
 796 #endif
 797
 798         encode_ptr(&dst, sub_p2->pos);   /* pos */
 799
 800         if (endp - src)                   /* remaining data */
 801         {
 802             memcpy (dst, src, endp - src);
 803             dst += endp - src;
 804         }
 805         p->size = dst - dst_buf;
 806         assert (p->size >= 0);
 807
 808         if (p->size <= b->file[p->cat].head.block_max)
 809         {
 810             /* it fits OK in this block */
 811             memcpy (startp, dst_buf, dst - dst_buf);
 812
 813             close_block(b, sub_p2);
 814         }
 815         else
 816         {
 817             /* must split _this_ block as well .. */
 818             struct ISAMB_block *sub_p3;
 819 #if INT_ENCODE
 820             char file_item_buf[DST_ITEM_MAX];
 821             char *file_item = file_item_buf;
 822 #else
 823             zint split_size_tmp;
 824 #endif
 825             zint no_items_first_half = 0;
 826             int p_new_size;
 827             const char *half;
 828             src = dst_buf;
 829             endp = dst;
 830
 831             b->number_of_int_splits++;
 832
 833             p->dirty = 1;
 834             close_block(b, sub_p2);
 835
 836             half = src + b->file[p->cat].head.block_size/2;
 837             decode_ptr(&src, &pos);
 838
 839             if (b->enable_int_count)
 840             {
 841                 /* read sub block so we can get no_items for it */
 842                 sub_p3 = open_block(b, pos);
 843                 no_items_first_half += sub_p3->no_items;
 844                 close_block(b, sub_p3);
 845             }
 846
 847             while (src <= half)
 848             {
 849 #if INT_ENCODE
 850                 file_item = file_item_buf;
 851                 (*b->method->codec.reset)(c1);
 852                 (*b->method->codec.decode)(c1, &file_item, &src);
 853 #else
 854                 decode_item_len(&src, &split_size_tmp);
 855                 *split_size = (int) split_size_tmp;
 856                 src += *split_size;
 857 #endif
 858                 decode_ptr(&src, &pos);
 859
 860                 if (b->enable_int_count)
 861                 {
 862                     /* read sub block so we can get no_items for it */
 863                     sub_p3 = open_block(b, pos);
 864                     no_items_first_half += sub_p3->no_items;
 865                     close_block(b, sub_p3);
 866                 }
 867             }
 868             /*  p is first half */
 869             p_new_size = src - dst_buf;
 870             memcpy (p->bytes, dst_buf, p_new_size);
 871
 872 #if INT_ENCODE
 873             file_item = file_item_buf;
 874             (*b->method->codec.reset)(c1);
 875             (*b->method->codec.decode)(c1, &file_item, &src);
 876             *split_size = file_item - file_item_buf;
 877             memcpy(split_item, file_item_buf, *split_size);
 878 #else
 879             decode_item_len(&src, &split_size_tmp);
 880             *split_size = (int) split_size_tmp;
 881             memcpy (split_item, src, *split_size);
 882             src += *split_size;
 883 #endif
 884             /*  *sp is second half */
 885             *sp = new_int (b, p->cat);
 886             (*sp)->size = endp - src;
 887             memcpy ((*sp)->bytes, src, (*sp)->size);
 888
 889             p->size = p_new_size;
 890
 891             /*  adjust no_items in first&second half */
 892             (*sp)->no_items = p->no_items - no_items_first_half;
 893             p->no_items = no_items_first_half;
 894         }
 895         p->dirty = 1;
 896     }
 897     close_block(b, sub_p1);
 898     (*b->method->codec.stop)(c1);
 899     return more;
 900 }
 901
 902 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
 903                  int *lookahead_mode, ISAMC_I *stream,
 904                  struct ISAMB_block **sp2,
 905                  void *sub_item, int *sub_size,
 906                  const void *max_item)
 907 {
 908     struct ISAMB_block *p = *sp1;
 909     char *endp = 0;
 910     const char *src = 0;
 911     char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
 912     int new_size;
 913     void *c1 = (*b->method->codec.start)();
 914     void *c2 = (*b->method->codec.start)();
 915     int more = 1;
 916     int quater = b->file[b->no_cat-1].head.block_max / 4;
 917     char *mid_cut = dst_buf + quater * 2;
 918     char *tail_cut = dst_buf + quater * 3;
 919     char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
 920     char *half1 = 0;
 921     char *half2 = 0;
 922     char cut_item_buf[DST_ITEM_MAX];
 923     int cut_item_size = 0;
 924     int no_items = 0;    /* number of items (total) */
 925     int no_items_1 = 0;  /* number of items (first half) */
 926     int inserted_dst_bytes = 0;
 927
 928     if (p && p->size)
 929     {
 930         char file_item_buf[DST_ITEM_MAX];
 931         char *file_item = file_item_buf;
 932
 933         src = p->bytes;
 934         endp = p->bytes + p->size;
 935         (*b->method->codec.decode)(c1, &file_item, &src);
 936         while (1)
 937         {
 938             const char *dst_item = 0; /* resulting item to be inserted */
 939             char *lookahead_next;
 940             char *dst_0 = dst;
 941             int d = -1;
 942
 943             if (lookahead_item)
 944                 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
 945
 946             /* d now holds comparison between existing file item and
 947                lookahead item
 948                d = 0: equal
 949                d > 0: lookahead before file
 950                d < 0: lookahead after file
 951             */
 952             if (d > 0)
 953             {
 954                 /* lookahead must be inserted */
 955                 dst_item = lookahead_item;
 956                 /* if this is not an insertion, it's really bad .. */
 957                 if (!*lookahead_mode)
 958                 {
 959                     yaz_log(YLOG_WARN, "isamb: Inconsistent register (1)");
 960                     assert(*lookahead_mode);
 961                 }
 962             }
 963             else
 964                 dst_item = file_item_buf;
 965
 966             if (!*lookahead_mode && d == 0)
 967             {
 968                 /* it's a deletion and they match so there is nothing to be
 969                    inserted anyway .. But mark the thing bad (file item
 970                    was part of input.. The item will not be part of output */
 971                 p->dirty = 1;
 972             }
 973             else if (!half1 && dst > mid_cut)
 974             {
 975                 /* we have reached the splitting point for the first time */
 976                 const char *dst_item_0 = dst_item;
 977                 half1 = dst; /* candidate for splitting */
 978
 979                 /* encode the resulting item */
 980                 (*b->method->codec.encode)(c2, &dst, &dst_item);
 981
 982                 cut_item_size = dst_item - dst_item_0;
 983                 assert(cut_item_size > 0);
 984                 memcpy (cut_item_buf, dst_item_0, cut_item_size);
 985
 986                 half2 = dst;
 987                 no_items_1 = no_items;
 988                 no_items++;
 989             }
 990             else
 991             {
 992                 /* encode the resulting item */
 993                 (*b->method->codec.encode)(c2, &dst, &dst_item);
 994                 no_items++;
 995             }
 996
 997             /* now move "pointers" .. result has been encoded .. */
 998             if (d > 0)
 999             {
1000                 /* we must move the lookahead pointer */
1001
1002                 inserted_dst_bytes += (dst - dst_0);
1003                 if (inserted_dst_bytes >=  quater)
1004                     /* no more room. Mark lookahead as "gone".. */
1005                     lookahead_item = 0;
1006                 else
1007                 {
1008                     /* move it really.. */
1009                     lookahead_next = lookahead_item;
1010                     if (!(*stream->read_item)(stream->clientData,
1011                                               &lookahead_next,
1012                                               lookahead_mode))
1013                     {
1014                         /* end of stream reached: no "more" and no lookahead */
1015                         lookahead_item = 0;
1016                         more = 0;
1017                     }
1018                     if (lookahead_item && max_item &&
1019                         (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1020                     {
1021                         /* the lookahead goes beyond what we allow in this
1022                            leaf. Mark it as "gone" */
1023                         lookahead_item = 0;
1024                     }
1025
1026                     p->dirty = 1;
1027                 }
1028             }
1029             else if (d == 0)
1030             {
1031                 /* exact match .. move both pointers */
1032
1033                 lookahead_next = lookahead_item;
1034                 if (!(*stream->read_item)(stream->clientData,
1035                                           &lookahead_next, lookahead_mode))
1036                 {
1037                     lookahead_item = 0;
1038                     more = 0;
1039                 }
1040                 if (src == endp)
1041                     break;  /* end of file stream reached .. */
1042                 file_item = file_item_buf; /* move file pointer */
1043                 (*b->method->codec.decode)(c1, &file_item, &src);
1044             }
1045             else
1046             {
1047                 /* file pointer must be moved */
1048                 if (src == endp)
1049                     break;
1050                 file_item = file_item_buf;
1051                 (*b->method->codec.decode)(c1, &file_item, &src);
1052             }
1053         }
1054     }
1055
1056     /* this loop runs when we are "appending" to a leaf page. That is
1057        either it's empty (new) or all file items have been read in
1058        previous loop */
1059
1060     maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
1061     while (lookahead_item)
1062     {
1063         char *dst_item;
1064         const char *src = lookahead_item;
1065         char *dst_0 = dst;
1066
1067         /* if we have a lookahead item, we stop if we exceed the value of it */
1068         if (max_item &&
1069             (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1070         {
1071             /* stop if we have reached the value of max item */
1072             break;
1073         }
1074         if (!*lookahead_mode)
1075         {
1076             /* this is append. So a delete is bad */
1077             yaz_log(YLOG_WARN, "isamb: Inconsistent register (2)");
1078             assert(*lookahead_mode);
1079         }
1080         else if (!half1 && dst > tail_cut)
1081         {
1082             const char *src_0 = src;
1083             half1 = dst; /* candidate for splitting */
1084
1085             (*b->method->codec.encode)(c2, &dst, &src);
1086
1087             cut_item_size = src - src_0;
1088             assert(cut_item_size > 0);
1089             memcpy (cut_item_buf, src_0, cut_item_size);
1090
1091             no_items_1 = no_items;
1092             half2 = dst;
1093         }
1094         else
1095             (*b->method->codec.encode)(c2, &dst, &src);
1096
1097         if (dst > maxp)
1098         {
1099             dst = dst_0;
1100             break;
1101         }
1102         no_items++;
1103         if (p)
1104             p->dirty = 1;
1105         dst_item = lookahead_item;
1106         if (!(*stream->read_item)(stream->clientData, &dst_item,
1107                                   lookahead_mode))
1108         {
1109             lookahead_item = 0;
1110             more = 0;
1111         }
1112     }
1113     new_size = dst - dst_buf;
1114     if (p && p->cat != b->no_cat-1 &&
1115         new_size > b->file[p->cat].head.block_max)
1116     {
1117         /* non-btree block will be removed */
1118         p->deleted = 1;
1119         close_block(b, p);
1120         /* delete it too!! */
1121         p = 0; /* make a new one anyway */
1122     }
1123     if (!p)
1124     {   /* must create a new one */
1125         int i;
1126         for (i = 0; i < b->no_cat; i++)
1127             if (new_size <= b->file[i].head.block_max)
1128                 break;
1129         if (i == b->no_cat)
1130             i = b->no_cat - 1;
1131         p = new_leaf (b, i);
1132     }
1133     if (new_size > b->file[p->cat].head.block_max)
1134     {
1135         char *first_dst;
1136         const char *cut_item = cut_item_buf;
1137
1138         assert (half1);
1139         assert (half2);
1140
1141         assert(cut_item_size > 0);
1142
1143         /* first half */
1144         p->size = half1 - dst_buf;
1145         assert(p->size <=  b->file[p->cat].head.block_max);
1146         memcpy (p->bytes, dst_buf, half1 - dst_buf);
1147         p->no_items = no_items_1;
1148
1149         /* second half */
1150         *sp2 = new_leaf (b, p->cat);
1151
1152         (*b->method->codec.reset)(c2);
1153
1154         b->number_of_leaf_splits++;
1155
1156         first_dst = (*sp2)->bytes;
1157
1158         (*b->method->codec.encode)(c2, &first_dst, &cut_item);
1159
1160         memcpy (first_dst, half2, dst - half2);
1161
1162         (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
1163         assert((*sp2)->size <=  b->file[p->cat].head.block_max);
1164         (*sp2)->no_items = no_items - no_items_1;
1165         (*sp2)->dirty = 1;
1166         p->dirty = 1;
1167         memcpy (sub_item, cut_item_buf, cut_item_size);
1168         *sub_size = cut_item_size;
1169     }
1170     else
1171     {
1172         memcpy (p->bytes, dst_buf, dst - dst_buf);
1173         p->size = new_size;
1174         p->no_items = no_items;
1175     }
1176     (*b->method->codec.stop)(c1);
1177     (*b->method->codec.stop)(c2);
1178     *sp1 = p;
1179     return more;
1180 }
1181
1182 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1183                 int *mode,
1184                 ISAMC_I *stream,
1185                 struct ISAMB_block **sp,
1186                 void *sub_item, int *sub_size,
1187                 const void *max_item)
1188 {
1189     if (!*p || (*p)->leaf)
1190         return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1191                             sub_size, max_item);
1192     else
1193         return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1194                            sub_size, max_item);
1195 }
1196
1197 int isamb_unlink (ISAMB b, ISAM_P pos)
1198 {
1199     struct ISAMB_block *p1;
1200
1201     if (!pos)
1202         return 0;
1203     p1 = open_block(b, pos);
1204     p1->deleted = 1;
1205     if (!p1->leaf)
1206     {
1207         zint sub_p;
1208         const char *src = p1->bytes + p1->offset;
1209 #if INT_ENCODE
1210         void *c1 = (*b->method->codec.start)();
1211 #endif
1212         decode_ptr(&src, &sub_p);
1213         isamb_unlink(b, sub_p);
1214
1215         while (src != p1->bytes + p1->size)
1216         {
1217 #if INT_ENCODE
1218             char file_item_buf[DST_ITEM_MAX];
1219             char *file_item = file_item_buf;
1220             (*b->method->codec.reset)(c1);
1221             (*b->method->codec.decode)(c1, &file_item, &src);
1222 #else
1223             zint item_len;
1224             decode_item_len(&src, &item_len);
1225             src += item_len;
1226 #endif
1227             decode_ptr(&src, &sub_p);
1228             isamb_unlink(b, sub_p);
1229         }
1230 #if INT_ENCODE
1231         (*b->method->codec.stop)(c1);
1232 #endif
1233     }
1234     close_block(b, p1);
1235     return 0;
1236 }
1237
1238 void isamb_merge(ISAMB b, ISAM_P *pos, ISAMC_I *stream)
1239 {
1240     char item_buf[DST_ITEM_MAX];
1241     char *item_ptr;
1242     int i_mode;
1243     int more;
1244     int must_delete = 0;
1245
1246     if (b->cache < 0)
1247     {
1248         int more = 1;
1249         while (more)
1250         {
1251             item_ptr = item_buf;
1252             more =
1253                 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1254         }
1255         *pos = 1;
1256         return;
1257     }
1258     item_ptr = item_buf;
1259     more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1260     while (more)
1261     {
1262         struct ISAMB_block *p = 0, *sp = 0;
1263         char sub_item[DST_ITEM_MAX];
1264         int sub_size;
1265
1266         if (*pos)
1267             p = open_block(b, *pos);
1268         more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1269                            sub_item, &sub_size, 0);
1270         if (sp)
1271         {    /* increase level of tree by one */
1272             struct ISAMB_block *p2 = new_int (b, p->cat);
1273             char *dst = p2->bytes + p2->size;
1274 #if INT_ENCODE
1275             void *c1 = (*b->method->codec.start)();
1276             const char *sub_item_ptr = sub_item;
1277 #endif
1278
1279             encode_ptr(&dst, p->pos);
1280             assert (sub_size < 128 && sub_size > 1);
1281 #if INT_ENCODE
1282             (*b->method->codec.reset)(c1);
1283             (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
1284 #else
1285             encode_item_len (&dst, sub_size);
1286             memcpy (dst, sub_item, sub_size);
1287             dst += sub_size;
1288 #endif
1289             encode_ptr(&dst, sp->pos);
1290
1291             p2->size = dst - p2->bytes;
1292             p2->no_items = p->no_items + sp->no_items;
1293             *pos = p2->pos;  /* return new super page */
1294             close_block(b, sp);
1295             close_block(b, p2);
1296 #if INT_ENCODE
1297             (*b->method->codec.stop)(c1);
1298 #endif
1299         }
1300         else
1301         {
1302             *pos = p->pos;   /* return current one (again) */
1303         }
1304         if (p->no_items == 0)
1305             must_delete = 1;
1306         else
1307             must_delete = 0;
1308         close_block(b, p);
1309     }
1310     if (must_delete)
1311     {
1312         isamb_unlink(b, *pos);
1313         *pos = 0;
1314     }
1315 }
1316
1317 ISAMB_PP isamb_pp_open_x(ISAMB isamb, ISAM_P pos, int *level, int scope)
1318 {
1319     ISAMB_PP pp = xmalloc(sizeof(*pp));
1320     int i;
1321
1322     assert(pos);
1323
1324     pp->isamb = isamb;
1325     pp->block = xmalloc(ISAMB_MAX_LEVEL * sizeof(*pp->block));
1326
1327     pp->pos = pos;
1328     pp->level = 0;
1329     pp->maxlevel = 0;
1330     pp->total_size = 0;
1331     pp->no_blocks = 0;
1332     pp->skipped_numbers = 0;
1333     pp->returned_numbers = 0;
1334     pp->scope = scope;
1335     for (i = 0; i<ISAMB_MAX_LEVEL; i++)
1336         pp->skipped_nodes[i] = pp->accessed_nodes[i] = 0;
1337     while (1)
1338     {
1339         struct ISAMB_block *p = open_block(isamb, pos);
1340         const char *src = p->bytes + p->offset;
1341         pp->block[pp->level] = p;
1342
1343         pp->total_size += p->size;
1344         pp->no_blocks++;
1345         if (p->leaf)
1346             break;
1347         decode_ptr(&src, &pos);
1348         p->offset = src - p->bytes;
1349         pp->level++;
1350         pp->accessed_nodes[pp->level]++;
1351     }
1352     pp->block[pp->level+1] = 0;
1353     pp->maxlevel = pp->level;
1354     if (level)
1355         *level = pp->level;
1356     return pp;
1357 }
1358
1359 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAM_P pos, int scope)
1360 {
1361     return isamb_pp_open_x(isamb, pos, 0, scope);
1362 }
1363
1364 void isamb_pp_close_x(ISAMB_PP pp, zint *size, zint *blocks)
1365 {
1366     int i;
1367     if (!pp)
1368         return;
1369     yaz_log(YLOG_DEBUG, "isamb_pp_close lev=%d returned "ZINT_FORMAT" values, "
1370                     "skipped "ZINT_FORMAT,
1371         pp->maxlevel, pp->skipped_numbers, pp->returned_numbers);
1372     for (i = pp->maxlevel; i>=0; i--)
1373         if (pp->skipped_nodes[i] || pp->accessed_nodes[i])
1374             yaz_log(YLOG_DEBUG, "isamb_pp_close  level leaf-%d: "
1375                             ZINT_FORMAT" read, "ZINT_FORMAT" skipped", i,
1376                  pp->accessed_nodes[i], pp->skipped_nodes[i]);
1377     pp->isamb->skipped_numbers += pp->skipped_numbers;
1378     pp->isamb->returned_numbers += pp->returned_numbers;
1379     for (i = pp->maxlevel; i>=0; i--)
1380     {
1381         pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1382         pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1383     }
1384     if (size)
1385         *size = pp->total_size;
1386     if (blocks)
1387         *blocks = pp->no_blocks;
1388     for (i = 0; i <= pp->level; i++)
1389         close_block(pp->isamb, pp->block[i]);
1390     xfree(pp->block);
1391     xfree(pp);
1392 }
1393
1394 int isamb_block_info (ISAMB isamb, int cat)
1395 {
1396     if (cat >= 0 && cat < isamb->no_cat)
1397         return isamb->file[cat].head.block_size;
1398     return -1;
1399 }
1400
1401 void isamb_pp_close (ISAMB_PP pp)
1402 {
1403     isamb_pp_close_x(pp, 0, 0);
1404 }
1405
1406 /* simple recursive dumper .. */
1407 static void isamb_dump_r (ISAMB b, ISAM_P pos, void (*pr)(const char *str),
1408                           int level)
1409 {
1410     char buf[1024];
1411     char prefix_str[1024];
1412     if (pos)
1413     {
1414         struct ISAMB_block *p = open_block(b, pos);
1415         sprintf(prefix_str, "%*s " ZINT_FORMAT " cat=%d size=%d max=%d items="
1416                 ZINT_FORMAT, level*2, "",
1417                 pos, p->cat, p->size, b->file[p->cat].head.block_max,
1418                 p->no_items);
1419         (*pr)(prefix_str);
1420         sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1421         if (p->leaf)
1422         {
1423             while (p->offset < p->size)
1424             {
1425                 const char *src = p->bytes + p->offset;
1426                 char *dst = buf;
1427                 (*b->method->codec.decode)(p->decodeClientData, &dst, &src);
1428                 (*b->method->log_item)(YLOG_DEBUG, buf, prefix_str);
1429                 p->offset = src - (char*) p->bytes;
1430             }
1431             assert(p->offset == p->size);
1432         }
1433         else
1434         {
1435             const char *src = p->bytes + p->offset;
1436             ISAM_P sub;
1437
1438             decode_ptr(&src, &sub);
1439             p->offset = src - (char*) p->bytes;
1440
1441             isamb_dump_r(b, sub, pr, level+1);
1442
1443             while (p->offset < p->size)
1444             {
1445 #if INT_ENCODE
1446                 char file_item_buf[DST_ITEM_MAX];
1447                 char *file_item = file_item_buf;
1448                 void *c1 = (*b->method->codec.start)();
1449                 (*b->method->codec.decode)(c1, &file_item, &src);
1450                 (*b->method->codec.stop)(c1);
1451                 (*b->method->log_item)(YLOG_DEBUG, file_item_buf, prefix_str);
1452 #else
1453                 zint item_len;
1454                 decode_item_len(&src, &item_len);
1455                 (*b->method->log_item)(YLOG_DEBUG, src, prefix_str);
1456                 src += item_len;
1457 #endif
1458                 decode_ptr(&src, &sub);
1459
1460                 p->offset = src - (char*) p->bytes;
1461
1462                 isamb_dump_r(b, sub, pr, level+1);
1463             }
1464         }
1465         close_block(b, p);
1466     }
1467 }
1468
1469 void isamb_dump(ISAMB b, ISAM_P pos, void (*pr)(const char *str))
1470 {
1471     isamb_dump_r(b, pos, pr, 0);
1472 }
1473
1474 int isamb_pp_read(ISAMB_PP pp, void *buf)
1475 {
1476     return isamb_pp_forward(pp, buf, 0);
1477 }
1478
1479
1480 static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
1481 { /* looks one node higher to see if we should be on this node at all */
1482   /* useful in backing off quickly, and in avoiding tail descends */
1483   /* call with pp->level to begin with */
1484     struct ISAMB_block *p;
1485     int cmp;
1486     const char *src;
1487     ISAMB b = pp->isamb;
1488
1489     assert(level >= 0);
1490     if (level == 0)
1491     {
1492 #if ISAMB_DEBUG
1493             yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true for root");
1494 #endif
1495         return 1; /* we can never skip the root node */
1496     }
1497     level--;
1498     p = pp->block[level];
1499     assert(p->offset <= p->size);
1500     if (p->offset < p->size)
1501     {
1502 #if INT_ENCODE
1503         char file_item_buf[DST_ITEM_MAX];
1504         char *file_item = file_item_buf;
1505         void *c1 = (*b->method->codec.start)();
1506         assert(p->offset > 0);
1507         src = p->bytes + p->offset;
1508         (*b->method->codec.decode)(c1, &file_item, &src);
1509         (*b->method->codec.stop)(c1);
1510         cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1511 #else
1512         zint item_len;
1513         assert(p->offset > 0);
1514         src = p->bytes + p->offset;
1515         decode_item_len(&src, &item_len);
1516 #if ISAMB_DEBUG
1517         (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until");
1518         (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value");
1519 #endif
1520         cmp = (*b->method->compare_item)(untilbuf, src);
1521 #endif
1522         if (cmp < pp->scope)
1523         {  /* cmp<2 */
1524 #if ISAMB_DEBUG
1525             yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true "
1526                             "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1527 #endif
1528             return 1;
1529         }
1530         else
1531         {
1532 #if ISAMB_DEBUG
1533             yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false "
1534                             "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1535 #endif
1536             return 0;
1537         }
1538     }
1539     else {
1540 #if ISAMB_DEBUG
1541         yaz_log(YLOG_DEBUG, "isamb_pp_on_right at tail, looking higher "
1542                         "lev=%d", level);
1543 #endif
1544         return isamb_pp_on_right_node(pp, level, untilbuf);
1545     }
1546 } /* isamb_pp_on_right_node */
1547
1548 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1549 {
1550     /* reads the next item on the current leaf, returns 0 if end of leaf*/
1551     struct ISAMB_block *p = pp->block[pp->level];
1552     char *dst;
1553     const char *src;
1554     assert(pp);
1555     assert(buf);
1556     if (p->offset == p->size)
1557     {
1558 #if ISAMB_DEBUG
1559         yaz_log(YLOG_DEBUG, "isamb_pp_read_on_leaf returning 0 on "
1560                 "node %d", p->pos);
1561 #endif
1562         return 0; /* at end of leaf */
1563     }
1564     src = p->bytes + p->offset;
1565     dst = buf;
1566     (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1567     p->offset = src - (char*) p->bytes;
1568 #if ISAMB_DEBUG
1569     (*pp->isamb->method->codec.log_item)(YLOG_DEBUG, buf,
1570                                          "read_on_leaf returning 1");
1571 #endif
1572     pp->returned_numbers++;
1573     return 1;
1574 } /* read_on_leaf */
1575
1576 static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
1577 { /* forwards on the current leaf, returns 0 if not found */
1578     int cmp;
1579     int skips = 0;
1580     while (1)
1581     {
1582         if (!isamb_pp_read_on_leaf(pp, buf))
1583             return 0;
1584         /* FIXME - this is an extra function call, inline the read? */
1585         cmp=(*pp->isamb->method->compare_item)(untilbuf, buf);
1586         if (cmp <pp->scope)
1587         {  /* cmp<2  found a good one */
1588 #if ISAMB_DEBUG
1589             if (skips)
1590                 yaz_log(YLOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items", skips);
1591 #endif
1592             pp->returned_numbers++;
1593             return 1;
1594         }
1595         if (!skips)
1596             if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1597                 return 0; /* never mind the rest of this leaf */
1598         pp->skipped_numbers++;
1599         skips++;
1600     }
1601 } /* forward_on_leaf */
1602
1603 static int isamb_pp_climb_level(ISAMB_PP pp, ISAM_P *pos)
1604 { /* climbs higher in the tree, until finds a level with data left */
1605   /* returns the node to (consider to) descend to in *pos) */
1606     struct ISAMB_block *p = pp->block[pp->level];
1607     const char *src;
1608 #if ISAMB_DEBUG
1609     yaz_log(YLOG_DEBUG, "isamb_pp_climb_level starting "
1610                    "at level %d node %d ofs=%d sz=%d",
1611                     pp->level, p->pos, p->offset, p->size);
1612 #endif
1613     assert(pp->level >= 0);
1614     assert(p->offset <= p->size);
1615     if (pp->level==0)
1616     {
1617 #if ISAMB_DEBUG
1618         yaz_log(YLOG_DEBUG, "isamb_pp_climb_level returning 0 at root");
1619 #endif
1620         return 0;
1621     }
1622     assert(pp->level>0);
1623     close_block(pp->isamb, pp->block[pp->level]);
1624     pp->block[pp->level] = 0;
1625     (pp->level)--;
1626     p = pp->block[pp->level];
1627 #if ISAMB_DEBUG
1628     yaz_log(YLOG_DEBUG, "isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1629                     pp->level, p->pos, p->offset);
1630 #endif
1631     assert(!p->leaf);
1632     assert(p->offset <= p->size);
1633     if (p->offset == p->size)
1634     {
1635         /* we came from the last pointer, climb on */
1636         if (!isamb_pp_climb_level(pp, pos))
1637             return 0;
1638         p = pp->block[pp->level];
1639     }
1640     else
1641     {
1642 #if INT_ENCODE
1643         char file_item_buf[DST_ITEM_MAX];
1644         char *file_item = file_item_buf;
1645         ISAMB b = pp->isamb;
1646         void *c1 = (*b->method->codec.start)();
1647 #else
1648         zint item_len;
1649 #endif
1650         /* skip the child we just came from */
1651 #if ISAMB_DEBUG
1652         yaz_log(YLOG_DEBUG, "isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1653                         pp->level, p->offset, p->size);
1654 #endif
1655         assert (p->offset < p->size);
1656         src = p->bytes + p->offset;
1657 #if INT_ENCODE
1658         (*b->method->codec.decode)(c1, &file_item, &src);
1659         (*b->method->codec.stop)(c1);
1660 #else
1661         decode_item_len(&src, &item_len);
1662         src += item_len;
1663 #endif
1664         decode_ptr(&src, pos);
1665         p->offset = src - (char *)p->bytes;
1666
1667     }
1668     return 1;
1669 } /* climb_level */
1670
1671
1672 static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
1673 { /* scans a upper node until it finds a child <= untilbuf */
1674   /* pp points to the key value, as always. pos is the child read from */
1675   /* the buffer */
1676   /* if all values are too small, returns the last child in the node */
1677   /* FIXME - this can be detected, and avoided by looking at the */
1678   /* parent node, but that gets messy. Presumably the cost is */
1679   /* pretty low anyway */
1680     ISAMB b = pp->isamb;
1681     struct ISAMB_block *p = pp->block[pp->level];
1682     const char *src = p->bytes + p->offset;
1683     int cmp;
1684     zint nxtpos;
1685 #if ISAMB_DEBUG
1686     int skips = 0;
1687     yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode starting "
1688                    "at level %d node %d ofs=%di sz=%d",
1689                     pp->level, p->pos, p->offset, p->size);
1690 #endif
1691     assert(!p->leaf);
1692     assert(p->offset <= p->size);
1693     if (p->offset == p->size)
1694     {
1695 #if ISAMB_DEBUG
1696             yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at end "
1697                    "at level %d node %d ofs=%di sz=%d",
1698                     pp->level, p->pos, p->offset, p->size);
1699 #endif
1700         return pos; /* already at the end of it */
1701     }
1702     while(p->offset < p->size)
1703     {
1704 #if INT_ENCODE
1705         char file_item_buf[DST_ITEM_MAX];
1706         char *file_item = file_item_buf;
1707         void *c1 = (*b->method->codec.start)();
1708         (*b->method->codec.decode)(c1, &file_item, &src);
1709         (*b->method->codec.stop)(c1);
1710         cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1711 #else
1712         zint item_len;
1713         decode_item_len(&src, &item_len);
1714         cmp = (*b->method->compare_item)(untilbuf, src);
1715         src += item_len;
1716 #endif
1717         decode_ptr(&src, &nxtpos);
1718         if (cmp<pp->scope) /* cmp<2 */
1719         {
1720 #if ISAMB_DEBUG
1721             yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning a hit "
1722                    "at level %d node %d ofs=%d sz=%d",
1723                     pp->level, p->pos, p->offset, p->size);
1724 #endif
1725             return pos;
1726         } /* found one */
1727         pos = nxtpos;
1728         p->offset = src-(char*)p->bytes;
1729         (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1730 #if ISAMB_DEBUG
1731         skips++;
1732 #endif
1733     }
1734 #if ISAMB_DEBUG
1735             yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at tail "
1736                    "at level %d node %d ofs=%d sz=%d skips=%d",
1737                     pp->level, p->pos, p->offset, p->size, skips);
1738 #endif
1739     return pos; /* that's the last one in the line */
1740
1741 } /* forward_unode */
1742
1743 static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAM_P pos,
1744                                      const void *untilbuf)
1745 { /* climbs down the tree, from pos, to the leftmost leaf */
1746     struct ISAMB_block *p = pp->block[pp->level];
1747     const char *src;
1748     assert(!p->leaf);
1749 #if ISAMB_DEBUG
1750     yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1751                    "starting at lev %d node %d ofs=%d lf=%d u=%p",
1752                    pp->level, p->pos, p->offset, p->leaf, untilbuf);
1753 #endif
1754     if (untilbuf)
1755         pos = isamb_pp_forward_unode(pp, pos, untilbuf);
1756     ++(pp->level);
1757     assert(pos);
1758     p = open_block(pp->isamb, pos);
1759     pp->block[pp->level] = p;
1760     ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
1761     ++(pp->no_blocks);
1762 #if ISAMB_DEBUG
1763     yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1764                    "got lev %d node %d lf=%d",
1765                    pp->level, p->pos, p->leaf);
1766 #endif
1767     if (p->leaf)
1768         return;
1769     assert (p->offset==0);
1770     src = p->bytes + p->offset;
1771     decode_ptr(&src, &pos);
1772     p->offset = src-(char*)p->bytes;
1773     isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1774 #if ISAMB_DEBUG
1775     yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1776                    "returning at lev %d node %d ofs=%d lf=%d",
1777                    pp->level, p->pos, p->offset, p->leaf);
1778 #endif
1779 } /* descend_to_leaf */
1780
1781 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1782 { /* finds the next leaf by climbing up and down */
1783     ISAM_P pos;
1784     if (!isamb_pp_climb_level(pp, &pos))
1785         return 0;
1786     isamb_pp_descend_to_leaf(pp, pos, 0);
1787     return 1;
1788 }
1789
1790 static int isamb_pp_climb_desc(ISAMB_PP pp,  const void *untilbuf)
1791 { /* climbs up and descends to a leaf where values >= *untilbuf are found */
1792     ISAM_P pos;
1793 #if ISAMB_DEBUG
1794     struct ISAMB_block *p = pp->block[pp->level];
1795     yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc starting "
1796                    "at level %d node %d ofs=%d sz=%d",
1797                     pp->level, p->pos, p->offset, p->size);
1798 #endif
1799     if (!isamb_pp_climb_level(pp, &pos))
1800         return 0;
1801     /* see if it would pay to climb one higher */
1802     if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1803         if (!isamb_pp_climb_level(pp, &pos))
1804             return 0;
1805     isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1806 #if ISAMB_DEBUG
1807     p = pp->block[pp->level];
1808     yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc done "
1809                    "at level %d node %d ofs=%d sz=%d",
1810                     pp->level, p->pos, p->offset, p->size);
1811 #endif
1812     return 1;
1813 } /* climb_desc */
1814
1815 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1816 {
1817 #if ISAMB_DEBUG
1818     struct ISAMB_block *p = pp->block[pp->level];
1819     assert(p->leaf);
1820     yaz_log(YLOG_DEBUG, "isamb_pp_forward starting "
1821                    "at level %d node %d ofs=%d sz=%d u=%p sc=%d",
1822                     pp->level, p->pos, p->offset, p->size, untilbuf, scope);
1823 #endif
1824     if (untilbuf)
1825     {
1826         if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1827         {
1828 #if ISAMB_DEBUG
1829             yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (A) "
1830                    "at level %d node %d ofs=%d sz=%d",
1831                     pp->level, p->pos, p->offset, p->size);
1832 #endif
1833             return 1;
1834         }
1835         if (! isamb_pp_climb_desc(pp, untilbuf))
1836         {
1837 #if ISAMB_DEBUG
1838             yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning notfound (B) "
1839                    "at level %d node %d ofs=%d sz=%d",
1840                     pp->level, p->pos, p->offset, p->size);
1841 #endif
1842             return 0; /* could not find a leaf */
1843         }
1844         do {
1845             if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1846             {
1847 #if ISAMB_DEBUG
1848                 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (c) "
1849                         "at level %d node %d ofs=%d sz=%d",
1850                         pp->level, p->pos, p->offset, p->size);
1851 #endif
1852                 return 1;
1853             }
1854         } while (isamb_pp_find_next_leaf(pp));
1855         return 0; /* could not find at all */
1856     }
1857     else { /* no untilbuf, a straight read */
1858         /* FIXME - this should be moved
1859          * directly into the pp_read */
1860         /* keeping here now, to keep same
1861          * interface as the old fwd */
1862         if (isamb_pp_read_on_leaf(pp, buf))
1863         {
1864 #if ISAMB_DEBUG
1865             yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (D) "
1866                    "at level %d node %d ofs=%d sz=%d",
1867                     pp->level, p->pos, p->offset, p->size);
1868 #endif
1869             return 1;
1870         }
1871         if (isamb_pp_find_next_leaf(pp))
1872         {
1873 #if ISAMB_DEBUG
1874             yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (E) "
1875                    "at level %d node %d ofs=%d sz=%d",
1876                     pp->level, p->pos, p->offset, p->size);
1877 #endif
1878             return isamb_pp_read_on_leaf(pp, buf);
1879         }
1880         else
1881             return 0;
1882     }
1883 } /* isam_pp_forward (new version) */
1884
1885 void isamb_pp_pos(ISAMB_PP pp, double *current, double *total)
1886 { /* return an estimate of the current position and of the total number of */
1887   /* occureences in the isam tree, based on the current leaf */
1888     assert(total);
1889     assert(current);
1890
1891     /* if end-of-stream PP may not be leaf */
1892
1893     *total = (double) (pp->block[0]->no_items);
1894     *current = (double) pp->returned_numbers;
1895 #if ISAMB_DEBUG
1896     yaz_log(YLOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
1897          ZINT_FORMAT, *current, *total, pp->returned_numbers);
1898 #endif
1899 }
1900
1901 int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb)
1902 {
1903     char *dst = buf;
1904     const char *src;
1905     struct ISAMB_block *p = pp->block[pp->level];
1906     ISAMB b = pp->isamb;
1907     if (!p)
1908         return 0;
1909 again:
1910     while (p->offset == p->size)
1911     {
1912         ISAM_P pos;
1913 #if INT_ENCODE
1914         const char *src_0;
1915         void *c1;
1916         char file_item_buf[DST_ITEM_MAX];
1917         char *file_item = file_item_buf;
1918 #else
1919         zint item_len;
1920 #endif
1921         while (p->offset == p->size)
1922         {
1923             if (pp->level == 0)
1924                 return 0;
1925             close_block (pp->isamb, pp->block[pp->level]);
1926             pp->block[pp->level] = 0;
1927             (pp->level)--;
1928             p = pp->block[pp->level];
1929             assert (!p->leaf);
1930         }
1931
1932         assert(!p->leaf);
1933         src = p->bytes + p->offset;
1934
1935 #if INT_ENCODE
1936         c1 = (*b->method->codec.start)();
1937         (*b->method->codec.decode)(c1, &file_item, &src);
1938 #else
1939         decode_ptr (&src, &item_len);
1940         src += item_len;
1941 #endif
1942         decode_ptr (&src, &pos);
1943         p->offset = src - (char*) p->bytes;
1944
1945         src = p->bytes + p->offset;
1946
1947         while(1)
1948         {
1949             if (!untilb || p->offset == p->size)
1950                 break;
1951             assert(p->offset < p->size);
1952 #if INT_ENCODE
1953             src_0 = src;
1954             file_item = file_item_buf;
1955             (*b->method->codec.reset)(c1);
1956             (*b->method->codec.decode)(c1, &file_item, &src);
1957             if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
1958             {
1959                 src = src_0;
1960                 break;
1961             }
1962 #else
1963             decode_item_len(&src, &item_len);
1964             if ((*b->method->compare_item)(untilb, src) <= 1)
1965                 break;
1966             src += item_len;
1967 #endif
1968             decode_ptr (&src, &pos);
1969             p->offset = src - (char*) p->bytes;
1970         }
1971
1972         pp->level++;
1973
1974         while (1)
1975         {
1976             pp->block[pp->level] = p = open_block (pp->isamb, pos);
1977
1978             pp->total_size += p->size;
1979             pp->no_blocks++;
1980
1981             if (p->leaf)
1982             {
1983                 break;
1984             }
1985
1986             src = p->bytes + p->offset;
1987             while(1)
1988             {
1989                 decode_ptr (&src, &pos);
1990                 p->offset = src - (char*) p->bytes;
1991
1992                 if (!untilb || p->offset == p->size)
1993                     break;
1994                 assert(p->offset < p->size);
1995 #if INT_ENCODE
1996                 src_0 = src;
1997                 file_item = file_item_buf;
1998                 (*b->method->codec.reset)(c1);
1999                 (*b->method->codec.decode)(c1, &file_item, &src);
2000                 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
2001                 {
2002                     src = src_0;
2003                     break;
2004                 }
2005 #else
2006                 decode_ptr (&src, &item_len);
2007                 if ((*b->method->compare_item)(untilb, src) <= 1)
2008                     break;
2009                 src += item_len;
2010 #endif
2011             }
2012             pp->level++;
2013         }
2014 #if INT_ENCODE
2015         (*b->method->codec.stop)(c1);
2016 #endif
2017     }
2018     assert (p->offset < p->size);
2019     assert (p->leaf);
2020     while(1)
2021     {
2022         char *dst0 = dst;
2023         src = p->bytes + p->offset;
2024         (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
2025         p->offset = src - (char*) p->bytes;
2026         if (!untilb || (*pp->isamb->method->compare_item)(untilb, dst0) <= 1)
2027             break;
2028         dst = dst0;
2029         if (p->offset == p->size) goto again;
2030     }
2031     return 1;
2032 }
2033
2034 zint isamb_get_int_splits(ISAMB b)
2035 {
2036     return b->number_of_int_splits;
2037 }
2038
2039 zint isamb_get_leaf_splits(ISAMB b)
2040 {
2041     return b->number_of_leaf_splits;
2042 }
2043
2044 zint isamb_get_root_ptr(ISAMB b)
2045 {
2046     return b->root_ptr;
2047 }
2048
2049 void isamb_set_root_ptr(ISAMB b, zint root_ptr)
2050 {
2051     b->root_ptr = root_ptr;
2052 }
2053
2054
2055 /*
2056  * Local variables:
2057  * c-basic-offset: 4
2058  * indent-tabs-mode: nil
2059  * End:
2060  * vim: shiftwidth=4 tabstop=8 expandtab
2061  */
2062