1 /* $Id: isamb.c,v 1.93 2007-04-03 16:54:46 adam Exp $
2 Copyright (C) 1995-2007
5 This file is part of the Zebra server.
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
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
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
26 #include <yaz/xmalloc.h>
27 #include <idzebra/isamb.h>
35 #define ISAMB_MAJOR_VERSION 3
36 #define ISAMB_MINOR_VERSION_NO_ROOT 0
37 #define ISAMB_MINOR_VERSION_WITH_ROOT 1
49 /* if 1, upper nodes items are encoded; 0 if not encoded */
52 /* maximum size of encoded buffer */
53 #define DST_ITEM_MAX 256
55 #define ISAMB_MAX_LEVEL 10
56 /* approx 2*max page + max size of item */
57 #define DST_BUF_SIZE (2*4096+300)
59 /* should be maximum block size of multiple thereof */
60 #define ISAMB_CACHE_ENTRY_SIZE 4096
62 /* CAT_MAX: _must_ be power of 2 */
64 #define CAT_MASK (CAT_MAX-1)
65 /* CAT_NO: <= CAT_MAX */
68 /* Smallest block size */
69 #define ISAMB_MIN_SIZE 32
71 #define ISAMB_FAC_SIZE 4
73 /* ISAMB_PTR_CODEC = 1 var, =0 fixed */
74 #define ISAMB_PTR_CODEC 1
76 struct ISAMB_cache_entry {
81 struct ISAMB_cache_entry *next;
87 struct ISAMB_head head;
88 struct ISAMB_cache_entry *cache_entries;
95 struct ISAMB_file *file;
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) */
120 zint no_items; /* number of nodes in this + children */
124 void *decodeClientData;
132 int maxlevel; /* total depth */
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 */
144 #define encode_item_len encode_ptr
146 static void encode_ptr(char **dst, zint pos)
148 unsigned char *bp = (unsigned char*) *dst;
152 *bp++ = (unsigned char) (128 | (pos & 127));
155 *bp++ = (unsigned char) pos;
159 static void encode_ptr(char **dst, zint pos)
161 memcpy(*dst, &pos, sizeof(pos));
162 (*dst) += sizeof(pos);
166 #define decode_item_len decode_ptr
168 static void decode_ptr(const char **src, zint *pos)
174 while (((c = *(const unsigned char *)((*src)++)) & 128))
176 d += ((zint) (c & 127) << r);
179 d += ((zint) c << r);
183 static void decode_ptr(const char **src, zint *pos)
185 memcpy(pos, *src, sizeof(*pos));
186 (*src) += sizeof(*pos);
191 void isamb_set_int_count(ISAMB b, int v)
193 b->enable_int_count = v;
196 void isamb_set_cache_size(ISAMB b, int v)
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)
204 ISAMB isamb = xmalloc(sizeof(*isamb));
207 assert(no_cat <= CAT_MAX);
210 isamb->method = (ISAMC_M *) xmalloc(sizeof(*method));
211 memcpy(isamb->method, method, sizeof(*method));
212 isamb->no_cat = no_cat;
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;
224 isamb->minor_version = ISAMB_MINOR_VERSION_WITH_ROOT;
226 isamb->minor_version = ISAMB_MINOR_VERSION_NO_ROOT;
230 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
231 isamb->skipped_nodes[i] = isamb->accessed_nodes[i] = 0;
235 yaz_log(YLOG_WARN, "isamb_open %s. Degraded TEST mode", name);
239 assert(cache == 0 || cache == 1);
241 isamb->file = xmalloc(sizeof(*isamb->file) * isamb->no_cat);
243 for (i = 0; i < isamb->no_cat; i++)
245 isamb->file[i].bf = 0;
246 isamb->file[i].head_dirty = 0;
247 isamb->file[i].cache_entries = 0;
250 for (i = 0; i < isamb->no_cat; i++)
252 char fname[DST_BUF_SIZE];
253 char hbuf[DST_BUF_SIZE];
255 sprintf(fname, "%s%c", name, i+'A');
257 isamb->file[i].bf = bf_open(bfs, fname, ISAMB_CACHE_ENTRY_SIZE,
260 isamb->file[i].bf = bf_open(bfs, fname, sizes[i], writeflag);
262 if (!isamb->file[i].bf)
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);
274 if (i == isamb->no_cat-1 || sizes[i] > 128)
275 isamb->file[i].head.block_offset = 8;
277 isamb->file[i].head.block_offset = 4;
279 isamb->file[i].head.block_offset = 11;
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))
286 /* got header assume "isamb"major minor len can fit in 16 bytes */
288 int major, minor, len, pos = 0;
291 if (memcmp(hbuf, "isamb", 5))
293 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
297 if (sscanf(hbuf+5, "%d %d %d", &major, &minor, &len) != 3)
299 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
303 if (major != ISAMB_MAJOR_VERSION)
305 yaz_log(YLOG_WARN, "bad major version for file %s %d, must be %d",
306 fname, major, ISAMB_MAJOR_VERSION);
310 for (left = len - sizes[i]; left > 0; left = left - sizes[i])
313 if (!bf_read(isamb->file[i].bf, pos, 0, 0, hbuf + pos*sizes[i]))
315 yaz_log(YLOG_WARN, "truncated isamb header for "
316 "file=%s len=%d pos=%d",
323 decode_ptr(&src, &isamb->file[i].head.first_block);
324 decode_ptr(&src, &isamb->file[i].head.last_block);
325 decode_ptr(&src, &zint_tmp);
326 isamb->file[i].head.block_size = (int) zint_tmp;
327 decode_ptr(&src, &zint_tmp);
328 isamb->file[i].head.block_max = (int) zint_tmp;
329 decode_ptr(&src, &isamb->file[i].head.free_list);
330 if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
331 decode_ptr(&src, &isamb->root_ptr);
333 assert (isamb->file[i].head.block_size >= isamb->file[i].head.block_offset);
334 /* must rewrite the header if root ptr is in use (bug #1017) */
335 if (use_root_ptr && writeflag)
336 isamb->file[i].head_dirty = 1;
338 isamb->file[i].head_dirty = 0;
339 assert(isamb->file[i].head.block_size == sizes[i]);
342 yaz_log(YLOG_WARN, "isamb debug enabled. Things will be slower than usual");
347 ISAMB isamb_open(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
351 int i, b_size = ISAMB_MIN_SIZE;
353 for (i = 0; i<CAT_NO; i++)
356 b_size = b_size * ISAMB_FAC_SIZE;
358 return isamb_open2(bfs, name, writeflag, method, cache,
362 static void flush_blocks (ISAMB b, int cat)
364 while (b->file[cat].cache_entries)
366 struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
367 b->file[cat].cache_entries = ce_this->next;
371 yaz_log(b->log_io, "bf_write: flush_blocks");
372 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
379 static int cache_block (ISAMB b, ISAM_P pos, unsigned char *userbuf, int wr)
381 int cat = (int) (pos&CAT_MASK);
382 int off = (int) (((pos/CAT_MAX) &
383 (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
384 * b->file[cat].head.block_size);
385 zint norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
387 struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
392 assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
393 for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
396 if ((*ce)->pos == norm)
399 *ce = (*ce)->next; /* remove from list */
401 ce_this->next = b->file[cat].cache_entries; /* move to front */
402 b->file[cat].cache_entries = ce_this;
406 memcpy (ce_this->buf + off, userbuf,
407 b->file[cat].head.block_size);
411 memcpy (userbuf, ce_this->buf + off,
412 b->file[cat].head.block_size);
416 if (no >= b->cache_size)
418 assert (ce_last && *ce_last);
420 *ce_last = 0; /* remove the last entry from list */
423 yaz_log(b->log_io, "bf_write: cache_block");
424 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
429 ce_this = xmalloc(sizeof(*ce_this));
430 ce_this->next = b->file[cat].cache_entries;
431 b->file[cat].cache_entries = ce_this;
432 ce_this->buf = xmalloc(ISAMB_CACHE_ENTRY_SIZE);
434 yaz_log(b->log_io, "bf_read: cache_block");
435 if (!bf_read(b->file[cat].bf, norm, 0, 0, ce_this->buf))
436 memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
439 memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
445 memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
451 void isamb_close (ISAMB isamb)
454 for (i = 0; isamb->accessed_nodes[i]; i++)
455 yaz_log(YLOG_DEBUG, "isamb_close level leaf-%d: "ZINT_FORMAT" read, "
456 ZINT_FORMAT" skipped",
457 i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]);
458 yaz_log(YLOG_DEBUG, "isamb_close returned "ZINT_FORMAT" values, "
459 "skipped "ZINT_FORMAT,
460 isamb->skipped_numbers, isamb->returned_numbers);
462 for (i = 0; i<isamb->no_cat; i++)
464 flush_blocks (isamb, i);
465 if (isamb->file[i].head_dirty)
467 char hbuf[DST_BUF_SIZE];
468 int major = ISAMB_MAJOR_VERSION;
470 char *dst = hbuf + 16;
472 int b_size = isamb->file[i].head.block_size;
474 encode_ptr(&dst, isamb->file[i].head.first_block);
475 encode_ptr(&dst, isamb->file[i].head.last_block);
476 encode_ptr(&dst, isamb->file[i].head.block_size);
477 encode_ptr(&dst, isamb->file[i].head.block_max);
478 encode_ptr(&dst, isamb->file[i].head.free_list);
480 if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
481 encode_ptr(&dst, isamb->root_ptr);
483 memset(dst, '\0', b_size); /* ensure no random bytes are written */
487 /* print exactly 16 bytes (including trailing 0) */
488 sprintf(hbuf, "isamb%02d %02d %02d\r\n", major,
489 isamb->minor_version, len);
491 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf);
493 for (left = len - b_size; left > 0; left = left - b_size)
496 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
499 if (isamb->file[i].bf)
500 bf_close (isamb->file[i].bf);
503 xfree(isamb->method);
507 /* open_block: read one block at pos.
508 Decode leading sys bytes .. consisting of
510 0: leader byte, != 0 leaf, == 0, non-leaf
511 1-2: used size of block
512 3-7*: number of items and all children
514 * Reserve 5 bytes for large block sizes. 1 for small ones .. Number
515 of items. We can thus have at most 2^40 nodes.
517 static struct ISAMB_block *open_block(ISAMB b, ISAM_P pos)
519 int cat = (int) (pos&CAT_MASK);
521 int offset = b->file[cat].head.block_offset;
522 struct ISAMB_block *p;
525 p = xmalloc(sizeof(*p));
527 p->cat = (int) (pos & CAT_MASK);
528 p->buf = xmalloc(b->file[cat].head.block_size);
531 if (!cache_block (b, pos, p->buf, 0))
533 yaz_log(b->log_io, "bf_read: open_block");
534 if (bf_read(b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf) != 1)
536 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
537 (long) pos, (long) pos/CAT_MAX);
538 zebra_exit("isamb:open_block");
541 p->bytes = (char *)p->buf + offset;
543 p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
546 yaz_log(YLOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
549 assert (p->size >= 0);
550 src = (char*) p->buf + 3;
551 decode_ptr(&src, &p->no_items);
556 p->decodeClientData = (*b->method->codec.start)();
560 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
562 struct ISAMB_block *p;
564 p = xmalloc(sizeof(*p));
565 p->buf = xmalloc(b->file[cat].head.block_size);
567 if (!b->file[cat].head.free_list)
570 block_no = b->file[cat].head.last_block++;
571 p->pos = block_no * CAT_MAX + cat;
575 p->pos = b->file[cat].head.free_list;
576 assert((p->pos & CAT_MASK) == cat);
577 if (!cache_block (b, p->pos, p->buf, 0))
579 yaz_log(b->log_io, "bf_read: new_block");
580 if (!bf_read(b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf))
582 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
583 (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX);
584 zebra_exit("isamb:new_block");
587 yaz_log(b->log_freelist, "got block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT, p->pos,
588 cat, p->pos/CAT_MAX);
589 memcpy (&b->file[cat].head.free_list, p->buf, sizeof(zint));
592 b->file[cat].head_dirty = 1;
593 memset (p->buf, 0, b->file[cat].head.block_size);
594 p->bytes = (char*)p->buf + b->file[cat].head.block_offset;
601 p->decodeClientData = (*b->method->codec.start)();
605 struct ISAMB_block *new_leaf (ISAMB b, int cat)
607 return new_block (b, 1, cat);
611 struct ISAMB_block *new_int (ISAMB b, int cat)
613 return new_block (b, 0, cat);
616 static void check_block (ISAMB b, struct ISAMB_block *p)
618 assert(b); /* mostly to make the compiler shut up about unused b */
626 char *startp = p->bytes;
627 const char *src = startp;
628 char *endp = p->bytes + p->size;
630 void *c1 = (*b->method->codec.start)();
632 decode_ptr(&src, &pos);
633 assert ((pos&CAT_MASK) == p->cat);
637 char file_item_buf[DST_ITEM_MAX];
638 char *file_item = file_item_buf;
639 (*b->method->codec.reset)(c1);
640 (*b->method->codec.decode)(c1, &file_item, &src);
643 decode_item_len(&src, &item_len);
644 assert (item_len > 0 && item_len < 128);
647 decode_ptr(&src, &pos);
648 if ((pos&CAT_MASK) != p->cat)
650 assert ((pos&CAT_MASK) == p->cat);
653 (*b->method->codec.stop)(c1);
657 void close_block(ISAMB b, struct ISAMB_block *p)
663 yaz_log(b->log_freelist, "release block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT,
664 p->pos, p->cat, p->pos/CAT_MAX);
665 memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(zint));
666 b->file[p->cat].head.free_list = p->pos;
667 if (!cache_block (b, p->pos, p->buf, 1))
669 yaz_log(b->log_io, "bf_write: close_block (deleted)");
670 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
675 int offset = b->file[p->cat].head.block_offset;
676 int size = p->size + offset;
677 char *dst = (char*)p->buf + 3;
678 assert (p->size >= 0);
680 /* memset becuase encode_ptr usually does not write all bytes */
681 memset(p->buf, 0, b->file[p->cat].head.block_offset);
683 p->buf[1] = size & 255;
684 p->buf[2] = size >> 8;
685 encode_ptr(&dst, p->no_items);
687 if (!cache_block (b, p->pos, p->buf, 1))
689 yaz_log(b->log_io, "bf_write: close_block");
690 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
693 (*b->method->codec.stop)(p->decodeClientData);
698 int insert_sub (ISAMB b, struct ISAMB_block **p,
699 void *new_item, int *mode,
701 struct ISAMB_block **sp,
702 void *sub_item, int *sub_size,
703 const void *max_item);
705 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
707 ISAMC_I *stream, struct ISAMB_block **sp,
708 void *split_item, int *split_size, const void *last_max_item)
710 char *startp = p->bytes;
711 const char *src = startp;
712 char *endp = p->bytes + p->size;
714 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
715 char sub_item[DST_ITEM_MAX];
719 void *c1 = (*b->method->codec.start)();
723 assert(p->size >= 0);
724 decode_ptr(&src, &pos);
728 const char *src0 = src;
730 char file_item_buf[DST_ITEM_MAX];
731 char *file_item = file_item_buf;
732 (*b->method->codec.reset)(c1);
733 (*b->method->codec.decode)(c1, &file_item, &src);
734 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
737 sub_p1 = open_block(b, pos);
739 diff_terms -= sub_p1->no_items;
740 more = insert_sub (b, &sub_p1, lookahead_item, mode,
742 sub_item, &sub_size, file_item_buf);
743 diff_terms += sub_p1->no_items;
749 decode_item_len(&src, &item_len);
750 d = (*b->method->compare_item)(src, lookahead_item);
753 sub_p1 = open_block(b, pos);
755 diff_terms -= sub_p1->no_items;
756 more = insert_sub (b, &sub_p1, lookahead_item, mode,
758 sub_item, &sub_size, src);
759 diff_terms += sub_p1->no_items;
765 decode_ptr(&src, &pos);
769 /* we reached the end. So lookahead > last item */
770 sub_p1 = open_block(b, pos);
772 diff_terms -= sub_p1->no_items;
773 more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
774 sub_item, &sub_size, last_max_item);
775 diff_terms += sub_p1->no_items;
778 diff_terms += sub_p2->no_items;
782 p->no_items += diff_terms;
786 /* there was a split - must insert pointer in this one */
787 char dst_buf[DST_BUF_SIZE];
790 const char *sub_item_ptr = sub_item;
792 assert (sub_size < 128 && sub_size > 1);
794 memcpy (dst, startp, src - startp);
799 (*b->method->codec.reset)(c1);
800 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
802 encode_item_len (&dst, sub_size); /* sub length and item */
803 memcpy (dst, sub_item, sub_size);
807 encode_ptr(&dst, sub_p2->pos); /* pos */
809 if (endp - src) /* remaining data */
811 memcpy (dst, src, endp - src);
814 p->size = dst - dst_buf;
815 assert (p->size >= 0);
817 if (p->size <= b->file[p->cat].head.block_max)
819 /* it fits OK in this block */
820 memcpy (startp, dst_buf, dst - dst_buf);
822 close_block(b, sub_p2);
826 /* must split _this_ block as well .. */
827 struct ISAMB_block *sub_p3;
829 char file_item_buf[DST_ITEM_MAX];
830 char *file_item = file_item_buf;
834 zint no_items_first_half = 0;
840 b->number_of_int_splits++;
843 close_block(b, sub_p2);
845 half = src + b->file[p->cat].head.block_size/2;
846 decode_ptr(&src, &pos);
848 if (b->enable_int_count)
850 /* read sub block so we can get no_items for it */
851 sub_p3 = open_block(b, pos);
852 no_items_first_half += sub_p3->no_items;
853 close_block(b, sub_p3);
859 file_item = file_item_buf;
860 (*b->method->codec.reset)(c1);
861 (*b->method->codec.decode)(c1, &file_item, &src);
863 decode_item_len(&src, &split_size_tmp);
864 *split_size = (int) split_size_tmp;
867 decode_ptr(&src, &pos);
869 if (b->enable_int_count)
871 /* read sub block so we can get no_items for it */
872 sub_p3 = open_block(b, pos);
873 no_items_first_half += sub_p3->no_items;
874 close_block(b, sub_p3);
877 /* p is first half */
878 p_new_size = src - dst_buf;
879 memcpy (p->bytes, dst_buf, p_new_size);
882 file_item = file_item_buf;
883 (*b->method->codec.reset)(c1);
884 (*b->method->codec.decode)(c1, &file_item, &src);
885 *split_size = file_item - file_item_buf;
886 memcpy(split_item, file_item_buf, *split_size);
888 decode_item_len(&src, &split_size_tmp);
889 *split_size = (int) split_size_tmp;
890 memcpy (split_item, src, *split_size);
893 /* *sp is second half */
894 *sp = new_int (b, p->cat);
895 (*sp)->size = endp - src;
896 memcpy ((*sp)->bytes, src, (*sp)->size);
898 p->size = p_new_size;
900 /* adjust no_items in first&second half */
901 (*sp)->no_items = p->no_items - no_items_first_half;
902 p->no_items = no_items_first_half;
906 close_block(b, sub_p1);
907 (*b->method->codec.stop)(c1);
911 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
912 int *lookahead_mode, ISAMC_I *stream,
913 struct ISAMB_block **sp2,
914 void *sub_item, int *sub_size,
915 const void *max_item)
917 struct ISAMB_block *p = *sp1;
920 char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
922 void *c1 = (*b->method->codec.start)();
923 void *c2 = (*b->method->codec.start)();
925 int quater = b->file[b->no_cat-1].head.block_max / 4;
926 char *mid_cut = dst_buf + quater * 2;
927 char *tail_cut = dst_buf + quater * 3;
928 char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
931 char cut_item_buf[DST_ITEM_MAX];
932 int cut_item_size = 0;
933 int no_items = 0; /* number of items (total) */
934 int no_items_1 = 0; /* number of items (first half) */
935 int inserted_dst_bytes = 0;
939 char file_item_buf[DST_ITEM_MAX];
940 char *file_item = file_item_buf;
943 endp = p->bytes + p->size;
944 (*b->method->codec.decode)(c1, &file_item, &src);
947 const char *dst_item = 0; /* resulting item to be inserted */
948 char *lookahead_next;
953 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
955 /* d now holds comparison between existing file item and
958 d > 0: lookahead before file
959 d < 0: lookahead after file
963 /* lookahead must be inserted */
964 dst_item = lookahead_item;
965 /* if this is not an insertion, it's really bad .. */
966 if (!*lookahead_mode)
968 yaz_log(YLOG_WARN, "isamb: Inconsistent register (1)");
969 assert(*lookahead_mode);
973 dst_item = file_item_buf;
975 if (!*lookahead_mode && d == 0)
977 /* it's a deletion and they match so there is nothing to be
978 inserted anyway .. But mark the thing bad (file item
979 was part of input.. The item will not be part of output */
982 else if (!half1 && dst > mid_cut)
984 /* we have reached the splitting point for the first time */
985 const char *dst_item_0 = dst_item;
986 half1 = dst; /* candidate for splitting */
988 /* encode the resulting item */
989 (*b->method->codec.encode)(c2, &dst, &dst_item);
991 cut_item_size = dst_item - dst_item_0;
992 assert(cut_item_size > 0);
993 memcpy (cut_item_buf, dst_item_0, cut_item_size);
996 no_items_1 = no_items;
1001 /* encode the resulting item */
1002 (*b->method->codec.encode)(c2, &dst, &dst_item);
1006 /* now move "pointers" .. result has been encoded .. */
1009 /* we must move the lookahead pointer */
1011 inserted_dst_bytes += (dst - dst_0);
1012 if (inserted_dst_bytes >= quater)
1013 /* no more room. Mark lookahead as "gone".. */
1017 /* move it really.. */
1018 lookahead_next = lookahead_item;
1019 if (!(*stream->read_item)(stream->clientData,
1023 /* end of stream reached: no "more" and no lookahead */
1027 if (lookahead_item && max_item &&
1028 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1030 /* the lookahead goes beyond what we allow in this
1031 leaf. Mark it as "gone" */
1040 /* exact match .. move both pointers */
1042 lookahead_next = lookahead_item;
1043 if (!(*stream->read_item)(stream->clientData,
1044 &lookahead_next, lookahead_mode))
1050 break; /* end of file stream reached .. */
1051 file_item = file_item_buf; /* move file pointer */
1052 (*b->method->codec.decode)(c1, &file_item, &src);
1056 /* file pointer must be moved */
1059 file_item = file_item_buf;
1060 (*b->method->codec.decode)(c1, &file_item, &src);
1065 /* this loop runs when we are "appending" to a leaf page. That is
1066 either it's empty (new) or all file items have been read in
1069 maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
1070 while (lookahead_item)
1073 const char *src = lookahead_item;
1076 /* if we have a lookahead item, we stop if we exceed the value of it */
1078 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1080 /* stop if we have reached the value of max item */
1083 if (!*lookahead_mode)
1085 /* this is append. So a delete is bad */
1086 yaz_log(YLOG_WARN, "isamb: Inconsistent register (2)");
1087 assert(*lookahead_mode);
1089 else if (!half1 && dst > tail_cut)
1091 const char *src_0 = src;
1092 half1 = dst; /* candidate for splitting */
1094 (*b->method->codec.encode)(c2, &dst, &src);
1096 cut_item_size = src - src_0;
1097 assert(cut_item_size > 0);
1098 memcpy (cut_item_buf, src_0, cut_item_size);
1100 no_items_1 = no_items;
1104 (*b->method->codec.encode)(c2, &dst, &src);
1114 dst_item = lookahead_item;
1115 if (!(*stream->read_item)(stream->clientData, &dst_item,
1122 new_size = dst - dst_buf;
1123 if (p && p->cat != b->no_cat-1 &&
1124 new_size > b->file[p->cat].head.block_max)
1126 /* non-btree block will be removed */
1129 /* delete it too!! */
1130 p = 0; /* make a new one anyway */
1133 { /* must create a new one */
1135 for (i = 0; i < b->no_cat; i++)
1136 if (new_size <= b->file[i].head.block_max)
1140 p = new_leaf (b, i);
1142 if (new_size > b->file[p->cat].head.block_max)
1145 const char *cut_item = cut_item_buf;
1150 assert(cut_item_size > 0);
1153 p->size = half1 - dst_buf;
1154 assert(p->size <= b->file[p->cat].head.block_max);
1155 memcpy (p->bytes, dst_buf, half1 - dst_buf);
1156 p->no_items = no_items_1;
1159 *sp2 = new_leaf (b, p->cat);
1161 (*b->method->codec.reset)(c2);
1163 b->number_of_leaf_splits++;
1165 first_dst = (*sp2)->bytes;
1167 (*b->method->codec.encode)(c2, &first_dst, &cut_item);
1169 memcpy (first_dst, half2, dst - half2);
1171 (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
1172 assert((*sp2)->size <= b->file[p->cat].head.block_max);
1173 (*sp2)->no_items = no_items - no_items_1;
1176 memcpy (sub_item, cut_item_buf, cut_item_size);
1177 *sub_size = cut_item_size;
1181 memcpy (p->bytes, dst_buf, dst - dst_buf);
1183 p->no_items = no_items;
1185 (*b->method->codec.stop)(c1);
1186 (*b->method->codec.stop)(c2);
1191 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1194 struct ISAMB_block **sp,
1195 void *sub_item, int *sub_size,
1196 const void *max_item)
1198 if (!*p || (*p)->leaf)
1199 return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1200 sub_size, max_item);
1202 return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1203 sub_size, max_item);
1206 int isamb_unlink (ISAMB b, ISAM_P pos)
1208 struct ISAMB_block *p1;
1212 p1 = open_block(b, pos);
1217 const char *src = p1->bytes + p1->offset;
1219 void *c1 = (*b->method->codec.start)();
1221 decode_ptr(&src, &sub_p);
1222 isamb_unlink(b, sub_p);
1224 while (src != p1->bytes + p1->size)
1227 char file_item_buf[DST_ITEM_MAX];
1228 char *file_item = file_item_buf;
1229 (*b->method->codec.reset)(c1);
1230 (*b->method->codec.decode)(c1, &file_item, &src);
1233 decode_item_len(&src, &item_len);
1236 decode_ptr(&src, &sub_p);
1237 isamb_unlink(b, sub_p);
1240 (*b->method->codec.stop)(c1);
1247 void isamb_merge(ISAMB b, ISAM_P *pos, ISAMC_I *stream)
1249 char item_buf[DST_ITEM_MAX];
1253 int must_delete = 0;
1260 item_ptr = item_buf;
1262 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1267 item_ptr = item_buf;
1268 more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1271 struct ISAMB_block *p = 0, *sp = 0;
1272 char sub_item[DST_ITEM_MAX];
1276 p = open_block(b, *pos);
1277 more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1278 sub_item, &sub_size, 0);
1280 { /* increase level of tree by one */
1281 struct ISAMB_block *p2 = new_int (b, p->cat);
1282 char *dst = p2->bytes + p2->size;
1284 void *c1 = (*b->method->codec.start)();
1285 const char *sub_item_ptr = sub_item;
1288 encode_ptr(&dst, p->pos);
1289 assert (sub_size < 128 && sub_size > 1);
1291 (*b->method->codec.reset)(c1);
1292 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
1294 encode_item_len (&dst, sub_size);
1295 memcpy (dst, sub_item, sub_size);
1298 encode_ptr(&dst, sp->pos);
1300 p2->size = dst - p2->bytes;
1301 p2->no_items = p->no_items + sp->no_items;
1302 *pos = p2->pos; /* return new super page */
1306 (*b->method->codec.stop)(c1);
1311 *pos = p->pos; /* return current one (again) */
1313 if (p->no_items == 0)
1321 isamb_unlink(b, *pos);
1326 ISAMB_PP isamb_pp_open_x(ISAMB isamb, ISAM_P pos, int *level, int scope)
1328 ISAMB_PP pp = xmalloc(sizeof(*pp));
1334 pp->block = xmalloc(ISAMB_MAX_LEVEL * sizeof(*pp->block));
1341 pp->skipped_numbers = 0;
1342 pp->returned_numbers = 0;
1344 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
1345 pp->skipped_nodes[i] = pp->accessed_nodes[i] = 0;
1348 struct ISAMB_block *p = open_block(isamb, pos);
1349 const char *src = p->bytes + p->offset;
1350 pp->block[pp->level] = p;
1352 pp->total_size += p->size;
1356 decode_ptr(&src, &pos);
1357 p->offset = src - p->bytes;
1359 pp->accessed_nodes[pp->level]++;
1361 pp->block[pp->level+1] = 0;
1362 pp->maxlevel = pp->level;
1368 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAM_P pos, int scope)
1370 return isamb_pp_open_x(isamb, pos, 0, scope);
1373 void isamb_pp_close_x(ISAMB_PP pp, zint *size, zint *blocks)
1378 yaz_log(YLOG_DEBUG, "isamb_pp_close lev=%d returned "ZINT_FORMAT" values, "
1379 "skipped "ZINT_FORMAT,
1380 pp->maxlevel, pp->skipped_numbers, pp->returned_numbers);
1381 for (i = pp->maxlevel; i>=0; i--)
1382 if (pp->skipped_nodes[i] || pp->accessed_nodes[i])
1383 yaz_log(YLOG_DEBUG, "isamb_pp_close level leaf-%d: "
1384 ZINT_FORMAT" read, "ZINT_FORMAT" skipped", i,
1385 pp->accessed_nodes[i], pp->skipped_nodes[i]);
1386 pp->isamb->skipped_numbers += pp->skipped_numbers;
1387 pp->isamb->returned_numbers += pp->returned_numbers;
1388 for (i = pp->maxlevel; i>=0; i--)
1390 pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1391 pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1394 *size = pp->total_size;
1396 *blocks = pp->no_blocks;
1397 for (i = 0; i <= pp->level; i++)
1398 close_block(pp->isamb, pp->block[i]);
1403 int isamb_block_info (ISAMB isamb, int cat)
1405 if (cat >= 0 && cat < isamb->no_cat)
1406 return isamb->file[cat].head.block_size;
1410 void isamb_pp_close (ISAMB_PP pp)
1412 isamb_pp_close_x(pp, 0, 0);
1415 /* simple recursive dumper .. */
1416 static void isamb_dump_r (ISAMB b, ISAM_P pos, void (*pr)(const char *str),
1420 char prefix_str[1024];
1423 struct ISAMB_block *p = open_block(b, pos);
1424 sprintf(prefix_str, "%*s " ZINT_FORMAT " cat=%d size=%d max=%d items="
1425 ZINT_FORMAT, level*2, "",
1426 pos, p->cat, p->size, b->file[p->cat].head.block_max,
1429 sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1432 while (p->offset < p->size)
1434 const char *src = p->bytes + p->offset;
1436 (*b->method->codec.decode)(p->decodeClientData, &dst, &src);
1437 (*b->method->log_item)(YLOG_DEBUG, buf, prefix_str);
1438 p->offset = src - (char*) p->bytes;
1440 assert(p->offset == p->size);
1444 const char *src = p->bytes + p->offset;
1447 decode_ptr(&src, &sub);
1448 p->offset = src - (char*) p->bytes;
1450 isamb_dump_r(b, sub, pr, level+1);
1452 while (p->offset < p->size)
1455 char file_item_buf[DST_ITEM_MAX];
1456 char *file_item = file_item_buf;
1457 void *c1 = (*b->method->codec.start)();
1458 (*b->method->codec.decode)(c1, &file_item, &src);
1459 (*b->method->codec.stop)(c1);
1460 (*b->method->log_item)(YLOG_DEBUG, file_item_buf, prefix_str);
1463 decode_item_len(&src, &item_len);
1464 (*b->method->log_item)(YLOG_DEBUG, src, prefix_str);
1467 decode_ptr(&src, &sub);
1469 p->offset = src - (char*) p->bytes;
1471 isamb_dump_r(b, sub, pr, level+1);
1478 void isamb_dump(ISAMB b, ISAM_P pos, void (*pr)(const char *str))
1480 isamb_dump_r(b, pos, pr, 0);
1483 int isamb_pp_read(ISAMB_PP pp, void *buf)
1485 return isamb_pp_forward(pp, buf, 0);
1489 static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
1490 { /* looks one node higher to see if we should be on this node at all */
1491 /* useful in backing off quickly, and in avoiding tail descends */
1492 /* call with pp->level to begin with */
1493 struct ISAMB_block *p;
1496 ISAMB b = pp->isamb;
1502 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true for root");
1504 return 1; /* we can never skip the root node */
1507 p = pp->block[level];
1508 assert(p->offset <= p->size);
1509 if (p->offset < p->size)
1512 char file_item_buf[DST_ITEM_MAX];
1513 char *file_item = file_item_buf;
1514 void *c1 = (*b->method->codec.start)();
1515 assert(p->offset > 0);
1516 src = p->bytes + p->offset;
1517 (*b->method->codec.decode)(c1, &file_item, &src);
1518 (*b->method->codec.stop)(c1);
1519 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1522 assert(p->offset > 0);
1523 src = p->bytes + p->offset;
1524 decode_item_len(&src, &item_len);
1526 (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until");
1527 (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value");
1529 cmp = (*b->method->compare_item)(untilbuf, src);
1531 if (cmp < pp->scope)
1534 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true "
1535 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1542 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false "
1543 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1550 yaz_log(YLOG_DEBUG, "isamb_pp_on_right at tail, looking higher "
1553 return isamb_pp_on_right_node(pp, level, untilbuf);
1555 } /* isamb_pp_on_right_node */
1557 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1559 /* reads the next item on the current leaf, returns 0 if end of leaf*/
1560 struct ISAMB_block *p = pp->block[pp->level];
1565 if (p->offset == p->size)
1568 yaz_log(YLOG_DEBUG, "isamb_pp_read_on_leaf returning 0 on "
1571 return 0; /* at end of leaf */
1573 src = p->bytes + p->offset;
1575 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1576 p->offset = src - (char*) p->bytes;
1578 (*pp->isamb->method->codec.log_item)(YLOG_DEBUG, buf,
1579 "read_on_leaf returning 1");
1581 pp->returned_numbers++;
1583 } /* read_on_leaf */
1585 static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
1586 { /* forwards on the current leaf, returns 0 if not found */
1591 if (!isamb_pp_read_on_leaf(pp, buf))
1593 /* FIXME - this is an extra function call, inline the read? */
1594 cmp=(*pp->isamb->method->compare_item)(untilbuf, buf);
1596 { /* cmp<2 found a good one */
1599 yaz_log(YLOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items", skips);
1601 pp->returned_numbers++;
1605 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1606 return 0; /* never mind the rest of this leaf */
1607 pp->skipped_numbers++;
1610 } /* forward_on_leaf */
1612 static int isamb_pp_climb_level(ISAMB_PP pp, ISAM_P *pos)
1613 { /* climbs higher in the tree, until finds a level with data left */
1614 /* returns the node to (consider to) descend to in *pos) */
1615 struct ISAMB_block *p = pp->block[pp->level];
1618 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level starting "
1619 "at level %d node %d ofs=%d sz=%d",
1620 pp->level, p->pos, p->offset, p->size);
1622 assert(pp->level >= 0);
1623 assert(p->offset <= p->size);
1627 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level returning 0 at root");
1631 assert(pp->level>0);
1632 close_block(pp->isamb, pp->block[pp->level]);
1633 pp->block[pp->level] = 0;
1635 p = pp->block[pp->level];
1637 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1638 pp->level, p->pos, p->offset);
1641 assert(p->offset <= p->size);
1642 if (p->offset == p->size)
1644 /* we came from the last pointer, climb on */
1645 if (!isamb_pp_climb_level(pp, pos))
1647 p = pp->block[pp->level];
1652 char file_item_buf[DST_ITEM_MAX];
1653 char *file_item = file_item_buf;
1654 ISAMB b = pp->isamb;
1655 void *c1 = (*b->method->codec.start)();
1659 /* skip the child we just came from */
1661 yaz_log(YLOG_DEBUG, "isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1662 pp->level, p->offset, p->size);
1664 assert (p->offset < p->size);
1665 src = p->bytes + p->offset;
1667 (*b->method->codec.decode)(c1, &file_item, &src);
1668 (*b->method->codec.stop)(c1);
1670 decode_item_len(&src, &item_len);
1673 decode_ptr(&src, pos);
1674 p->offset = src - (char *)p->bytes;
1681 static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
1682 { /* scans a upper node until it finds a child <= untilbuf */
1683 /* pp points to the key value, as always. pos is the child read from */
1685 /* if all values are too small, returns the last child in the node */
1686 /* FIXME - this can be detected, and avoided by looking at the */
1687 /* parent node, but that gets messy. Presumably the cost is */
1688 /* pretty low anyway */
1689 ISAMB b = pp->isamb;
1690 struct ISAMB_block *p = pp->block[pp->level];
1691 const char *src = p->bytes + p->offset;
1696 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode starting "
1697 "at level %d node %d ofs=%di sz=%d",
1698 pp->level, p->pos, p->offset, p->size);
1701 assert(p->offset <= p->size);
1702 if (p->offset == p->size)
1705 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at end "
1706 "at level %d node %d ofs=%di sz=%d",
1707 pp->level, p->pos, p->offset, p->size);
1709 return pos; /* already at the end of it */
1711 while(p->offset < p->size)
1714 char file_item_buf[DST_ITEM_MAX];
1715 char *file_item = file_item_buf;
1716 void *c1 = (*b->method->codec.start)();
1717 (*b->method->codec.decode)(c1, &file_item, &src);
1718 (*b->method->codec.stop)(c1);
1719 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1722 decode_item_len(&src, &item_len);
1723 cmp = (*b->method->compare_item)(untilbuf, src);
1726 decode_ptr(&src, &nxtpos);
1727 if (cmp<pp->scope) /* cmp<2 */
1730 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning a hit "
1731 "at level %d node %d ofs=%d sz=%d",
1732 pp->level, p->pos, p->offset, p->size);
1737 p->offset = src-(char*)p->bytes;
1738 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1744 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at tail "
1745 "at level %d node %d ofs=%d sz=%d skips=%d",
1746 pp->level, p->pos, p->offset, p->size, skips);
1748 return pos; /* that's the last one in the line */
1750 } /* forward_unode */
1752 static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAM_P pos,
1753 const void *untilbuf)
1754 { /* climbs down the tree, from pos, to the leftmost leaf */
1755 struct ISAMB_block *p = pp->block[pp->level];
1759 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1760 "starting at lev %d node %d ofs=%d lf=%d u=%p",
1761 pp->level, p->pos, p->offset, p->leaf, untilbuf);
1764 pos = isamb_pp_forward_unode(pp, pos, untilbuf);
1767 p = open_block(pp->isamb, pos);
1768 pp->block[pp->level] = p;
1769 ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
1772 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1773 "got lev %d node %d lf=%d",
1774 pp->level, p->pos, p->leaf);
1778 assert (p->offset==0);
1779 src = p->bytes + p->offset;
1780 decode_ptr(&src, &pos);
1781 p->offset = src-(char*)p->bytes;
1782 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1784 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1785 "returning at lev %d node %d ofs=%d lf=%d",
1786 pp->level, p->pos, p->offset, p->leaf);
1788 } /* descend_to_leaf */
1790 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1791 { /* finds the next leaf by climbing up and down */
1793 if (!isamb_pp_climb_level(pp, &pos))
1795 isamb_pp_descend_to_leaf(pp, pos, 0);
1799 static int isamb_pp_climb_desc(ISAMB_PP pp, const void *untilbuf)
1800 { /* climbs up and descends to a leaf where values >= *untilbuf are found */
1803 struct ISAMB_block *p = pp->block[pp->level];
1804 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc starting "
1805 "at level %d node %d ofs=%d sz=%d",
1806 pp->level, p->pos, p->offset, p->size);
1808 if (!isamb_pp_climb_level(pp, &pos))
1810 /* see if it would pay to climb one higher */
1811 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1812 if (!isamb_pp_climb_level(pp, &pos))
1814 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1816 p = pp->block[pp->level];
1817 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc done "
1818 "at level %d node %d ofs=%d sz=%d",
1819 pp->level, p->pos, p->offset, p->size);
1824 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1827 struct ISAMB_block *p = pp->block[pp->level];
1829 yaz_log(YLOG_DEBUG, "isamb_pp_forward starting "
1830 "at level %d node %d ofs=%d sz=%d u=%p sc=%d",
1831 pp->level, p->pos, p->offset, p->size, untilbuf, scope);
1835 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1838 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (A) "
1839 "at level %d node %d ofs=%d sz=%d",
1840 pp->level, p->pos, p->offset, p->size);
1844 if (! isamb_pp_climb_desc(pp, untilbuf))
1847 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning notfound (B) "
1848 "at level %d node %d ofs=%d sz=%d",
1849 pp->level, p->pos, p->offset, p->size);
1851 return 0; /* could not find a leaf */
1854 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1857 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (c) "
1858 "at level %d node %d ofs=%d sz=%d",
1859 pp->level, p->pos, p->offset, p->size);
1863 } while (isamb_pp_find_next_leaf(pp));
1864 return 0; /* could not find at all */
1866 else { /* no untilbuf, a straight read */
1867 /* FIXME - this should be moved
1868 * directly into the pp_read */
1869 /* keeping here now, to keep same
1870 * interface as the old fwd */
1871 if (isamb_pp_read_on_leaf(pp, buf))
1874 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (D) "
1875 "at level %d node %d ofs=%d sz=%d",
1876 pp->level, p->pos, p->offset, p->size);
1880 if (isamb_pp_find_next_leaf(pp))
1883 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (E) "
1884 "at level %d node %d ofs=%d sz=%d",
1885 pp->level, p->pos, p->offset, p->size);
1887 return isamb_pp_read_on_leaf(pp, buf);
1892 } /* isam_pp_forward (new version) */
1894 void isamb_pp_pos(ISAMB_PP pp, double *current, double *total)
1895 { /* return an estimate of the current position and of the total number of */
1896 /* occureences in the isam tree, based on the current leaf */
1900 /* if end-of-stream PP may not be leaf */
1902 *total = (double) (pp->block[0]->no_items);
1903 *current = (double) pp->returned_numbers;
1905 yaz_log(YLOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
1906 ZINT_FORMAT, *current, *total, pp->returned_numbers);
1910 int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb)
1914 struct ISAMB_block *p = pp->block[pp->level];
1915 ISAMB b = pp->isamb;
1919 while (p->offset == p->size)
1925 char file_item_buf[DST_ITEM_MAX];
1926 char *file_item = file_item_buf;
1930 while (p->offset == p->size)
1934 close_block (pp->isamb, pp->block[pp->level]);
1935 pp->block[pp->level] = 0;
1937 p = pp->block[pp->level];
1942 src = p->bytes + p->offset;
1945 c1 = (*b->method->codec.start)();
1946 (*b->method->codec.decode)(c1, &file_item, &src);
1948 decode_ptr (&src, &item_len);
1951 decode_ptr (&src, &pos);
1952 p->offset = src - (char*) p->bytes;
1954 src = p->bytes + p->offset;
1958 if (!untilb || p->offset == p->size)
1960 assert(p->offset < p->size);
1963 file_item = file_item_buf;
1964 (*b->method->codec.reset)(c1);
1965 (*b->method->codec.decode)(c1, &file_item, &src);
1966 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
1972 decode_item_len(&src, &item_len);
1973 if ((*b->method->compare_item)(untilb, src) <= 1)
1977 decode_ptr (&src, &pos);
1978 p->offset = src - (char*) p->bytes;
1985 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1987 pp->total_size += p->size;
1995 src = p->bytes + p->offset;
1998 decode_ptr (&src, &pos);
1999 p->offset = src - (char*) p->bytes;
2001 if (!untilb || p->offset == p->size)
2003 assert(p->offset < p->size);
2006 file_item = file_item_buf;
2007 (*b->method->codec.reset)(c1);
2008 (*b->method->codec.decode)(c1, &file_item, &src);
2009 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
2015 decode_ptr (&src, &item_len);
2016 if ((*b->method->compare_item)(untilb, src) <= 1)
2024 (*b->method->codec.stop)(c1);
2027 assert (p->offset < p->size);
2032 src = p->bytes + p->offset;
2033 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
2034 p->offset = src - (char*) p->bytes;
2035 if (!untilb || (*pp->isamb->method->compare_item)(untilb, dst0) <= 1)
2038 if (p->offset == p->size) goto again;
2043 zint isamb_get_int_splits(ISAMB b)
2045 return b->number_of_int_splits;
2048 zint isamb_get_leaf_splits(ISAMB b)
2050 return b->number_of_leaf_splits;
2053 zint isamb_get_root_ptr(ISAMB b)
2058 void isamb_set_root_ptr(ISAMB b, zint root_ptr)
2060 b->root_ptr = root_ptr;
2067 * indent-tabs-mode: nil
2069 * vim: shiftwidth=4 tabstop=8 expandtab