1 /* $Id: isamb.c,v 1.92 2007-02-24 16:46:22 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 isamb->file[i].head_dirty = 0;
335 assert(isamb->file[i].head.block_size == sizes[i]);
338 yaz_log(YLOG_WARN, "isamb debug enabled. Things will be slower than usual");
343 ISAMB isamb_open(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
347 int i, b_size = ISAMB_MIN_SIZE;
349 for (i = 0; i<CAT_NO; i++)
352 b_size = b_size * ISAMB_FAC_SIZE;
354 return isamb_open2(bfs, name, writeflag, method, cache,
358 static void flush_blocks (ISAMB b, int cat)
360 while (b->file[cat].cache_entries)
362 struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
363 b->file[cat].cache_entries = ce_this->next;
367 yaz_log(b->log_io, "bf_write: flush_blocks");
368 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
375 static int cache_block (ISAMB b, ISAM_P pos, unsigned char *userbuf, int wr)
377 int cat = (int) (pos&CAT_MASK);
378 int off = (int) (((pos/CAT_MAX) &
379 (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
380 * b->file[cat].head.block_size);
381 zint norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
383 struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
388 assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
389 for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
392 if ((*ce)->pos == norm)
395 *ce = (*ce)->next; /* remove from list */
397 ce_this->next = b->file[cat].cache_entries; /* move to front */
398 b->file[cat].cache_entries = ce_this;
402 memcpy (ce_this->buf + off, userbuf,
403 b->file[cat].head.block_size);
407 memcpy (userbuf, ce_this->buf + off,
408 b->file[cat].head.block_size);
412 if (no >= b->cache_size)
414 assert (ce_last && *ce_last);
416 *ce_last = 0; /* remove the last entry from list */
419 yaz_log(b->log_io, "bf_write: cache_block");
420 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
425 ce_this = xmalloc(sizeof(*ce_this));
426 ce_this->next = b->file[cat].cache_entries;
427 b->file[cat].cache_entries = ce_this;
428 ce_this->buf = xmalloc(ISAMB_CACHE_ENTRY_SIZE);
430 yaz_log(b->log_io, "bf_read: cache_block");
431 if (!bf_read(b->file[cat].bf, norm, 0, 0, ce_this->buf))
432 memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
435 memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
441 memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
447 void isamb_close (ISAMB isamb)
450 for (i = 0; isamb->accessed_nodes[i]; i++)
451 yaz_log(YLOG_DEBUG, "isamb_close level leaf-%d: "ZINT_FORMAT" read, "
452 ZINT_FORMAT" skipped",
453 i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]);
454 yaz_log(YLOG_DEBUG, "isamb_close returned "ZINT_FORMAT" values, "
455 "skipped "ZINT_FORMAT,
456 isamb->skipped_numbers, isamb->returned_numbers);
457 for (i = 0; i<isamb->no_cat; i++)
459 flush_blocks (isamb, i);
460 if (isamb->file[i].head_dirty)
462 char hbuf[DST_BUF_SIZE];
463 int major = ISAMB_MAJOR_VERSION;
465 char *dst = hbuf + 16;
467 int b_size = isamb->file[i].head.block_size;
469 encode_ptr(&dst, isamb->file[i].head.first_block);
470 encode_ptr(&dst, isamb->file[i].head.last_block);
471 encode_ptr(&dst, isamb->file[i].head.block_size);
472 encode_ptr(&dst, isamb->file[i].head.block_max);
473 encode_ptr(&dst, isamb->file[i].head.free_list);
475 if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
476 encode_ptr(&dst, isamb->root_ptr);
478 memset(dst, '\0', b_size); /* ensure no random bytes are written */
482 /* print exactly 16 bytes (including trailing 0) */
483 sprintf(hbuf, "isamb%02d %02d %02d\r\n", major,
484 isamb->minor_version, len);
486 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf);
488 for (left = len - b_size; left > 0; left = left - b_size)
491 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
494 if (isamb->file[i].bf)
495 bf_close (isamb->file[i].bf);
498 xfree(isamb->method);
502 /* open_block: read one block at pos.
503 Decode leading sys bytes .. consisting of
505 0: leader byte, != 0 leaf, == 0, non-leaf
506 1-2: used size of block
507 3-7*: number of items and all children
509 * Reserve 5 bytes for large block sizes. 1 for small ones .. Number
510 of items. We can thus have at most 2^40 nodes.
512 static struct ISAMB_block *open_block(ISAMB b, ISAM_P pos)
514 int cat = (int) (pos&CAT_MASK);
516 int offset = b->file[cat].head.block_offset;
517 struct ISAMB_block *p;
520 p = xmalloc(sizeof(*p));
522 p->cat = (int) (pos & CAT_MASK);
523 p->buf = xmalloc(b->file[cat].head.block_size);
526 if (!cache_block (b, pos, p->buf, 0))
528 yaz_log(b->log_io, "bf_read: open_block");
529 if (bf_read(b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf) != 1)
531 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
532 (long) pos, (long) pos/CAT_MAX);
533 zebra_exit("isamb:open_block");
536 p->bytes = (char *)p->buf + offset;
538 p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
541 yaz_log(YLOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
544 assert (p->size >= 0);
545 src = (char*) p->buf + 3;
546 decode_ptr(&src, &p->no_items);
551 p->decodeClientData = (*b->method->codec.start)();
555 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
557 struct ISAMB_block *p;
559 p = xmalloc(sizeof(*p));
560 p->buf = xmalloc(b->file[cat].head.block_size);
562 if (!b->file[cat].head.free_list)
565 block_no = b->file[cat].head.last_block++;
566 p->pos = block_no * CAT_MAX + cat;
570 p->pos = b->file[cat].head.free_list;
571 assert((p->pos & CAT_MASK) == cat);
572 if (!cache_block (b, p->pos, p->buf, 0))
574 yaz_log(b->log_io, "bf_read: new_block");
575 if (!bf_read(b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf))
577 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
578 (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX);
579 zebra_exit("isamb:new_block");
582 yaz_log(b->log_freelist, "got block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT, p->pos,
583 cat, p->pos/CAT_MAX);
584 memcpy (&b->file[cat].head.free_list, p->buf, sizeof(zint));
587 b->file[cat].head_dirty = 1;
588 memset (p->buf, 0, b->file[cat].head.block_size);
589 p->bytes = (char*)p->buf + b->file[cat].head.block_offset;
596 p->decodeClientData = (*b->method->codec.start)();
600 struct ISAMB_block *new_leaf (ISAMB b, int cat)
602 return new_block (b, 1, cat);
606 struct ISAMB_block *new_int (ISAMB b, int cat)
608 return new_block (b, 0, cat);
611 static void check_block (ISAMB b, struct ISAMB_block *p)
613 assert(b); /* mostly to make the compiler shut up about unused b */
621 char *startp = p->bytes;
622 const char *src = startp;
623 char *endp = p->bytes + p->size;
625 void *c1 = (*b->method->codec.start)();
627 decode_ptr(&src, &pos);
628 assert ((pos&CAT_MASK) == p->cat);
632 char file_item_buf[DST_ITEM_MAX];
633 char *file_item = file_item_buf;
634 (*b->method->codec.reset)(c1);
635 (*b->method->codec.decode)(c1, &file_item, &src);
638 decode_item_len(&src, &item_len);
639 assert (item_len > 0 && item_len < 128);
642 decode_ptr(&src, &pos);
643 if ((pos&CAT_MASK) != p->cat)
645 assert ((pos&CAT_MASK) == p->cat);
648 (*b->method->codec.stop)(c1);
652 void close_block(ISAMB b, struct ISAMB_block *p)
658 yaz_log(b->log_freelist, "release block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT,
659 p->pos, p->cat, p->pos/CAT_MAX);
660 memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(zint));
661 b->file[p->cat].head.free_list = p->pos;
662 if (!cache_block (b, p->pos, p->buf, 1))
664 yaz_log(b->log_io, "bf_write: close_block (deleted)");
665 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
670 int offset = b->file[p->cat].head.block_offset;
671 int size = p->size + offset;
672 char *dst = (char*)p->buf + 3;
673 assert (p->size >= 0);
675 /* memset becuase encode_ptr usually does not write all bytes */
676 memset(p->buf, 0, b->file[p->cat].head.block_offset);
678 p->buf[1] = size & 255;
679 p->buf[2] = size >> 8;
680 encode_ptr(&dst, p->no_items);
682 if (!cache_block (b, p->pos, p->buf, 1))
684 yaz_log(b->log_io, "bf_write: close_block");
685 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
688 (*b->method->codec.stop)(p->decodeClientData);
693 int insert_sub (ISAMB b, struct ISAMB_block **p,
694 void *new_item, int *mode,
696 struct ISAMB_block **sp,
697 void *sub_item, int *sub_size,
698 const void *max_item);
700 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
702 ISAMC_I *stream, struct ISAMB_block **sp,
703 void *split_item, int *split_size, const void *last_max_item)
705 char *startp = p->bytes;
706 const char *src = startp;
707 char *endp = p->bytes + p->size;
709 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
710 char sub_item[DST_ITEM_MAX];
714 void *c1 = (*b->method->codec.start)();
718 assert(p->size >= 0);
719 decode_ptr(&src, &pos);
723 const char *src0 = src;
725 char file_item_buf[DST_ITEM_MAX];
726 char *file_item = file_item_buf;
727 (*b->method->codec.reset)(c1);
728 (*b->method->codec.decode)(c1, &file_item, &src);
729 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
732 sub_p1 = open_block(b, pos);
734 diff_terms -= sub_p1->no_items;
735 more = insert_sub (b, &sub_p1, lookahead_item, mode,
737 sub_item, &sub_size, file_item_buf);
738 diff_terms += sub_p1->no_items;
744 decode_item_len(&src, &item_len);
745 d = (*b->method->compare_item)(src, lookahead_item);
748 sub_p1 = open_block(b, pos);
750 diff_terms -= sub_p1->no_items;
751 more = insert_sub (b, &sub_p1, lookahead_item, mode,
753 sub_item, &sub_size, src);
754 diff_terms += sub_p1->no_items;
760 decode_ptr(&src, &pos);
764 /* we reached the end. So lookahead > last item */
765 sub_p1 = open_block(b, pos);
767 diff_terms -= sub_p1->no_items;
768 more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
769 sub_item, &sub_size, last_max_item);
770 diff_terms += sub_p1->no_items;
773 diff_terms += sub_p2->no_items;
777 p->no_items += diff_terms;
781 /* there was a split - must insert pointer in this one */
782 char dst_buf[DST_BUF_SIZE];
785 const char *sub_item_ptr = sub_item;
787 assert (sub_size < 128 && sub_size > 1);
789 memcpy (dst, startp, src - startp);
794 (*b->method->codec.reset)(c1);
795 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
797 encode_item_len (&dst, sub_size); /* sub length and item */
798 memcpy (dst, sub_item, sub_size);
802 encode_ptr(&dst, sub_p2->pos); /* pos */
804 if (endp - src) /* remaining data */
806 memcpy (dst, src, endp - src);
809 p->size = dst - dst_buf;
810 assert (p->size >= 0);
812 if (p->size <= b->file[p->cat].head.block_max)
814 /* it fits OK in this block */
815 memcpy (startp, dst_buf, dst - dst_buf);
817 close_block(b, sub_p2);
821 /* must split _this_ block as well .. */
822 struct ISAMB_block *sub_p3;
824 char file_item_buf[DST_ITEM_MAX];
825 char *file_item = file_item_buf;
829 zint no_items_first_half = 0;
835 b->number_of_int_splits++;
838 close_block(b, sub_p2);
840 half = src + b->file[p->cat].head.block_size/2;
841 decode_ptr(&src, &pos);
843 if (b->enable_int_count)
845 /* read sub block so we can get no_items for it */
846 sub_p3 = open_block(b, pos);
847 no_items_first_half += sub_p3->no_items;
848 close_block(b, sub_p3);
854 file_item = file_item_buf;
855 (*b->method->codec.reset)(c1);
856 (*b->method->codec.decode)(c1, &file_item, &src);
858 decode_item_len(&src, &split_size_tmp);
859 *split_size = (int) split_size_tmp;
862 decode_ptr(&src, &pos);
864 if (b->enable_int_count)
866 /* read sub block so we can get no_items for it */
867 sub_p3 = open_block(b, pos);
868 no_items_first_half += sub_p3->no_items;
869 close_block(b, sub_p3);
872 /* p is first half */
873 p_new_size = src - dst_buf;
874 memcpy (p->bytes, dst_buf, p_new_size);
877 file_item = file_item_buf;
878 (*b->method->codec.reset)(c1);
879 (*b->method->codec.decode)(c1, &file_item, &src);
880 *split_size = file_item - file_item_buf;
881 memcpy(split_item, file_item_buf, *split_size);
883 decode_item_len(&src, &split_size_tmp);
884 *split_size = (int) split_size_tmp;
885 memcpy (split_item, src, *split_size);
888 /* *sp is second half */
889 *sp = new_int (b, p->cat);
890 (*sp)->size = endp - src;
891 memcpy ((*sp)->bytes, src, (*sp)->size);
893 p->size = p_new_size;
895 /* adjust no_items in first&second half */
896 (*sp)->no_items = p->no_items - no_items_first_half;
897 p->no_items = no_items_first_half;
901 close_block(b, sub_p1);
902 (*b->method->codec.stop)(c1);
906 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
907 int *lookahead_mode, ISAMC_I *stream,
908 struct ISAMB_block **sp2,
909 void *sub_item, int *sub_size,
910 const void *max_item)
912 struct ISAMB_block *p = *sp1;
915 char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
917 void *c1 = (*b->method->codec.start)();
918 void *c2 = (*b->method->codec.start)();
920 int quater = b->file[b->no_cat-1].head.block_max / 4;
921 char *mid_cut = dst_buf + quater * 2;
922 char *tail_cut = dst_buf + quater * 3;
923 char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
926 char cut_item_buf[DST_ITEM_MAX];
927 int cut_item_size = 0;
928 int no_items = 0; /* number of items (total) */
929 int no_items_1 = 0; /* number of items (first half) */
930 int inserted_dst_bytes = 0;
934 char file_item_buf[DST_ITEM_MAX];
935 char *file_item = file_item_buf;
938 endp = p->bytes + p->size;
939 (*b->method->codec.decode)(c1, &file_item, &src);
942 const char *dst_item = 0; /* resulting item to be inserted */
943 char *lookahead_next;
948 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
950 /* d now holds comparison between existing file item and
953 d > 0: lookahead before file
954 d < 0: lookahead after file
958 /* lookahead must be inserted */
959 dst_item = lookahead_item;
960 /* if this is not an insertion, it's really bad .. */
961 if (!*lookahead_mode)
963 yaz_log(YLOG_WARN, "isamb: Inconsistent register (1)");
964 assert(*lookahead_mode);
968 dst_item = file_item_buf;
970 if (!*lookahead_mode && d == 0)
972 /* it's a deletion and they match so there is nothing to be
973 inserted anyway .. But mark the thing bad (file item
974 was part of input.. The item will not be part of output */
977 else if (!half1 && dst > mid_cut)
979 /* we have reached the splitting point for the first time */
980 const char *dst_item_0 = dst_item;
981 half1 = dst; /* candidate for splitting */
983 /* encode the resulting item */
984 (*b->method->codec.encode)(c2, &dst, &dst_item);
986 cut_item_size = dst_item - dst_item_0;
987 assert(cut_item_size > 0);
988 memcpy (cut_item_buf, dst_item_0, cut_item_size);
991 no_items_1 = no_items;
996 /* encode the resulting item */
997 (*b->method->codec.encode)(c2, &dst, &dst_item);
1001 /* now move "pointers" .. result has been encoded .. */
1004 /* we must move the lookahead pointer */
1006 inserted_dst_bytes += (dst - dst_0);
1007 if (inserted_dst_bytes >= quater)
1008 /* no more room. Mark lookahead as "gone".. */
1012 /* move it really.. */
1013 lookahead_next = lookahead_item;
1014 if (!(*stream->read_item)(stream->clientData,
1018 /* end of stream reached: no "more" and no lookahead */
1022 if (lookahead_item && max_item &&
1023 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1025 /* the lookahead goes beyond what we allow in this
1026 leaf. Mark it as "gone" */
1035 /* exact match .. move both pointers */
1037 lookahead_next = lookahead_item;
1038 if (!(*stream->read_item)(stream->clientData,
1039 &lookahead_next, lookahead_mode))
1045 break; /* end of file stream reached .. */
1046 file_item = file_item_buf; /* move file pointer */
1047 (*b->method->codec.decode)(c1, &file_item, &src);
1051 /* file pointer must be moved */
1054 file_item = file_item_buf;
1055 (*b->method->codec.decode)(c1, &file_item, &src);
1060 /* this loop runs when we are "appending" to a leaf page. That is
1061 either it's empty (new) or all file items have been read in
1064 maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
1065 while (lookahead_item)
1068 const char *src = lookahead_item;
1071 /* if we have a lookahead item, we stop if we exceed the value of it */
1073 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1075 /* stop if we have reached the value of max item */
1078 if (!*lookahead_mode)
1080 /* this is append. So a delete is bad */
1081 yaz_log(YLOG_WARN, "isamb: Inconsistent register (2)");
1082 assert(*lookahead_mode);
1084 else if (!half1 && dst > tail_cut)
1086 const char *src_0 = src;
1087 half1 = dst; /* candidate for splitting */
1089 (*b->method->codec.encode)(c2, &dst, &src);
1091 cut_item_size = src - src_0;
1092 assert(cut_item_size > 0);
1093 memcpy (cut_item_buf, src_0, cut_item_size);
1095 no_items_1 = no_items;
1099 (*b->method->codec.encode)(c2, &dst, &src);
1109 dst_item = lookahead_item;
1110 if (!(*stream->read_item)(stream->clientData, &dst_item,
1117 new_size = dst - dst_buf;
1118 if (p && p->cat != b->no_cat-1 &&
1119 new_size > b->file[p->cat].head.block_max)
1121 /* non-btree block will be removed */
1124 /* delete it too!! */
1125 p = 0; /* make a new one anyway */
1128 { /* must create a new one */
1130 for (i = 0; i < b->no_cat; i++)
1131 if (new_size <= b->file[i].head.block_max)
1135 p = new_leaf (b, i);
1137 if (new_size > b->file[p->cat].head.block_max)
1140 const char *cut_item = cut_item_buf;
1145 assert(cut_item_size > 0);
1148 p->size = half1 - dst_buf;
1149 assert(p->size <= b->file[p->cat].head.block_max);
1150 memcpy (p->bytes, dst_buf, half1 - dst_buf);
1151 p->no_items = no_items_1;
1154 *sp2 = new_leaf (b, p->cat);
1156 (*b->method->codec.reset)(c2);
1158 b->number_of_leaf_splits++;
1160 first_dst = (*sp2)->bytes;
1162 (*b->method->codec.encode)(c2, &first_dst, &cut_item);
1164 memcpy (first_dst, half2, dst - half2);
1166 (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
1167 assert((*sp2)->size <= b->file[p->cat].head.block_max);
1168 (*sp2)->no_items = no_items - no_items_1;
1171 memcpy (sub_item, cut_item_buf, cut_item_size);
1172 *sub_size = cut_item_size;
1176 memcpy (p->bytes, dst_buf, dst - dst_buf);
1178 p->no_items = no_items;
1180 (*b->method->codec.stop)(c1);
1181 (*b->method->codec.stop)(c2);
1186 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1189 struct ISAMB_block **sp,
1190 void *sub_item, int *sub_size,
1191 const void *max_item)
1193 if (!*p || (*p)->leaf)
1194 return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1195 sub_size, max_item);
1197 return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1198 sub_size, max_item);
1201 int isamb_unlink (ISAMB b, ISAM_P pos)
1203 struct ISAMB_block *p1;
1207 p1 = open_block(b, pos);
1212 const char *src = p1->bytes + p1->offset;
1214 void *c1 = (*b->method->codec.start)();
1216 decode_ptr(&src, &sub_p);
1217 isamb_unlink(b, sub_p);
1219 while (src != p1->bytes + p1->size)
1222 char file_item_buf[DST_ITEM_MAX];
1223 char *file_item = file_item_buf;
1224 (*b->method->codec.reset)(c1);
1225 (*b->method->codec.decode)(c1, &file_item, &src);
1228 decode_item_len(&src, &item_len);
1231 decode_ptr(&src, &sub_p);
1232 isamb_unlink(b, sub_p);
1235 (*b->method->codec.stop)(c1);
1242 void isamb_merge(ISAMB b, ISAM_P *pos, ISAMC_I *stream)
1244 char item_buf[DST_ITEM_MAX];
1248 int must_delete = 0;
1255 item_ptr = item_buf;
1257 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1262 item_ptr = item_buf;
1263 more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1266 struct ISAMB_block *p = 0, *sp = 0;
1267 char sub_item[DST_ITEM_MAX];
1271 p = open_block(b, *pos);
1272 more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1273 sub_item, &sub_size, 0);
1275 { /* increase level of tree by one */
1276 struct ISAMB_block *p2 = new_int (b, p->cat);
1277 char *dst = p2->bytes + p2->size;
1279 void *c1 = (*b->method->codec.start)();
1280 const char *sub_item_ptr = sub_item;
1283 encode_ptr(&dst, p->pos);
1284 assert (sub_size < 128 && sub_size > 1);
1286 (*b->method->codec.reset)(c1);
1287 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
1289 encode_item_len (&dst, sub_size);
1290 memcpy (dst, sub_item, sub_size);
1293 encode_ptr(&dst, sp->pos);
1295 p2->size = dst - p2->bytes;
1296 p2->no_items = p->no_items + sp->no_items;
1297 *pos = p2->pos; /* return new super page */
1301 (*b->method->codec.stop)(c1);
1306 *pos = p->pos; /* return current one (again) */
1308 if (p->no_items == 0)
1316 isamb_unlink(b, *pos);
1321 ISAMB_PP isamb_pp_open_x(ISAMB isamb, ISAM_P pos, int *level, int scope)
1323 ISAMB_PP pp = xmalloc(sizeof(*pp));
1329 pp->block = xmalloc(ISAMB_MAX_LEVEL * sizeof(*pp->block));
1336 pp->skipped_numbers = 0;
1337 pp->returned_numbers = 0;
1339 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
1340 pp->skipped_nodes[i] = pp->accessed_nodes[i] = 0;
1343 struct ISAMB_block *p = open_block(isamb, pos);
1344 const char *src = p->bytes + p->offset;
1345 pp->block[pp->level] = p;
1347 pp->total_size += p->size;
1351 decode_ptr(&src, &pos);
1352 p->offset = src - p->bytes;
1354 pp->accessed_nodes[pp->level]++;
1356 pp->block[pp->level+1] = 0;
1357 pp->maxlevel = pp->level;
1363 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAM_P pos, int scope)
1365 return isamb_pp_open_x(isamb, pos, 0, scope);
1368 void isamb_pp_close_x(ISAMB_PP pp, zint *size, zint *blocks)
1373 yaz_log(YLOG_DEBUG, "isamb_pp_close lev=%d returned "ZINT_FORMAT" values, "
1374 "skipped "ZINT_FORMAT,
1375 pp->maxlevel, pp->skipped_numbers, pp->returned_numbers);
1376 for (i = pp->maxlevel; i>=0; i--)
1377 if (pp->skipped_nodes[i] || pp->accessed_nodes[i])
1378 yaz_log(YLOG_DEBUG, "isamb_pp_close level leaf-%d: "
1379 ZINT_FORMAT" read, "ZINT_FORMAT" skipped", i,
1380 pp->accessed_nodes[i], pp->skipped_nodes[i]);
1381 pp->isamb->skipped_numbers += pp->skipped_numbers;
1382 pp->isamb->returned_numbers += pp->returned_numbers;
1383 for (i = pp->maxlevel; i>=0; i--)
1385 pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1386 pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1389 *size = pp->total_size;
1391 *blocks = pp->no_blocks;
1392 for (i = 0; i <= pp->level; i++)
1393 close_block(pp->isamb, pp->block[i]);
1398 int isamb_block_info (ISAMB isamb, int cat)
1400 if (cat >= 0 && cat < isamb->no_cat)
1401 return isamb->file[cat].head.block_size;
1405 void isamb_pp_close (ISAMB_PP pp)
1407 isamb_pp_close_x(pp, 0, 0);
1410 /* simple recursive dumper .. */
1411 static void isamb_dump_r (ISAMB b, ISAM_P pos, void (*pr)(const char *str),
1415 char prefix_str[1024];
1418 struct ISAMB_block *p = open_block(b, pos);
1419 sprintf(prefix_str, "%*s " ZINT_FORMAT " cat=%d size=%d max=%d items="
1420 ZINT_FORMAT, level*2, "",
1421 pos, p->cat, p->size, b->file[p->cat].head.block_max,
1424 sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1427 while (p->offset < p->size)
1429 const char *src = p->bytes + p->offset;
1431 (*b->method->codec.decode)(p->decodeClientData, &dst, &src);
1432 (*b->method->log_item)(YLOG_DEBUG, buf, prefix_str);
1433 p->offset = src - (char*) p->bytes;
1435 assert(p->offset == p->size);
1439 const char *src = p->bytes + p->offset;
1442 decode_ptr(&src, &sub);
1443 p->offset = src - (char*) p->bytes;
1445 isamb_dump_r(b, sub, pr, level+1);
1447 while (p->offset < p->size)
1450 char file_item_buf[DST_ITEM_MAX];
1451 char *file_item = file_item_buf;
1452 void *c1 = (*b->method->codec.start)();
1453 (*b->method->codec.decode)(c1, &file_item, &src);
1454 (*b->method->codec.stop)(c1);
1455 (*b->method->log_item)(YLOG_DEBUG, file_item_buf, prefix_str);
1458 decode_item_len(&src, &item_len);
1459 (*b->method->log_item)(YLOG_DEBUG, src, prefix_str);
1462 decode_ptr(&src, &sub);
1464 p->offset = src - (char*) p->bytes;
1466 isamb_dump_r(b, sub, pr, level+1);
1473 void isamb_dump(ISAMB b, ISAM_P pos, void (*pr)(const char *str))
1475 isamb_dump_r(b, pos, pr, 0);
1478 int isamb_pp_read(ISAMB_PP pp, void *buf)
1480 return isamb_pp_forward(pp, buf, 0);
1484 static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
1485 { /* looks one node higher to see if we should be on this node at all */
1486 /* useful in backing off quickly, and in avoiding tail descends */
1487 /* call with pp->level to begin with */
1488 struct ISAMB_block *p;
1491 ISAMB b = pp->isamb;
1497 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true for root");
1499 return 1; /* we can never skip the root node */
1502 p = pp->block[level];
1503 assert(p->offset <= p->size);
1504 if (p->offset < p->size)
1507 char file_item_buf[DST_ITEM_MAX];
1508 char *file_item = file_item_buf;
1509 void *c1 = (*b->method->codec.start)();
1510 assert(p->offset > 0);
1511 src = p->bytes + p->offset;
1512 (*b->method->codec.decode)(c1, &file_item, &src);
1513 (*b->method->codec.stop)(c1);
1514 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1517 assert(p->offset > 0);
1518 src = p->bytes + p->offset;
1519 decode_item_len(&src, &item_len);
1521 (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until");
1522 (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value");
1524 cmp = (*b->method->compare_item)(untilbuf, src);
1526 if (cmp < pp->scope)
1529 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true "
1530 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1537 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false "
1538 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1545 yaz_log(YLOG_DEBUG, "isamb_pp_on_right at tail, looking higher "
1548 return isamb_pp_on_right_node(pp, level, untilbuf);
1550 } /* isamb_pp_on_right_node */
1552 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1554 /* reads the next item on the current leaf, returns 0 if end of leaf*/
1555 struct ISAMB_block *p = pp->block[pp->level];
1560 if (p->offset == p->size)
1563 yaz_log(YLOG_DEBUG, "isamb_pp_read_on_leaf returning 0 on "
1566 return 0; /* at end of leaf */
1568 src = p->bytes + p->offset;
1570 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1571 p->offset = src - (char*) p->bytes;
1573 (*pp->isamb->method->codec.log_item)(YLOG_DEBUG, buf,
1574 "read_on_leaf returning 1");
1576 pp->returned_numbers++;
1578 } /* read_on_leaf */
1580 static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
1581 { /* forwards on the current leaf, returns 0 if not found */
1586 if (!isamb_pp_read_on_leaf(pp, buf))
1588 /* FIXME - this is an extra function call, inline the read? */
1589 cmp=(*pp->isamb->method->compare_item)(untilbuf, buf);
1591 { /* cmp<2 found a good one */
1594 yaz_log(YLOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items", skips);
1596 pp->returned_numbers++;
1600 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1601 return 0; /* never mind the rest of this leaf */
1602 pp->skipped_numbers++;
1605 } /* forward_on_leaf */
1607 static int isamb_pp_climb_level(ISAMB_PP pp, ISAM_P *pos)
1608 { /* climbs higher in the tree, until finds a level with data left */
1609 /* returns the node to (consider to) descend to in *pos) */
1610 struct ISAMB_block *p = pp->block[pp->level];
1613 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level starting "
1614 "at level %d node %d ofs=%d sz=%d",
1615 pp->level, p->pos, p->offset, p->size);
1617 assert(pp->level >= 0);
1618 assert(p->offset <= p->size);
1622 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level returning 0 at root");
1626 assert(pp->level>0);
1627 close_block(pp->isamb, pp->block[pp->level]);
1628 pp->block[pp->level] = 0;
1630 p = pp->block[pp->level];
1632 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1633 pp->level, p->pos, p->offset);
1636 assert(p->offset <= p->size);
1637 if (p->offset == p->size)
1639 /* we came from the last pointer, climb on */
1640 if (!isamb_pp_climb_level(pp, pos))
1642 p = pp->block[pp->level];
1647 char file_item_buf[DST_ITEM_MAX];
1648 char *file_item = file_item_buf;
1649 ISAMB b = pp->isamb;
1650 void *c1 = (*b->method->codec.start)();
1654 /* skip the child we just came from */
1656 yaz_log(YLOG_DEBUG, "isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1657 pp->level, p->offset, p->size);
1659 assert (p->offset < p->size);
1660 src = p->bytes + p->offset;
1662 (*b->method->codec.decode)(c1, &file_item, &src);
1663 (*b->method->codec.stop)(c1);
1665 decode_item_len(&src, &item_len);
1668 decode_ptr(&src, pos);
1669 p->offset = src - (char *)p->bytes;
1676 static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
1677 { /* scans a upper node until it finds a child <= untilbuf */
1678 /* pp points to the key value, as always. pos is the child read from */
1680 /* if all values are too small, returns the last child in the node */
1681 /* FIXME - this can be detected, and avoided by looking at the */
1682 /* parent node, but that gets messy. Presumably the cost is */
1683 /* pretty low anyway */
1684 ISAMB b = pp->isamb;
1685 struct ISAMB_block *p = pp->block[pp->level];
1686 const char *src = p->bytes + p->offset;
1691 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode starting "
1692 "at level %d node %d ofs=%di sz=%d",
1693 pp->level, p->pos, p->offset, p->size);
1696 assert(p->offset <= p->size);
1697 if (p->offset == p->size)
1700 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at end "
1701 "at level %d node %d ofs=%di sz=%d",
1702 pp->level, p->pos, p->offset, p->size);
1704 return pos; /* already at the end of it */
1706 while(p->offset < p->size)
1709 char file_item_buf[DST_ITEM_MAX];
1710 char *file_item = file_item_buf;
1711 void *c1 = (*b->method->codec.start)();
1712 (*b->method->codec.decode)(c1, &file_item, &src);
1713 (*b->method->codec.stop)(c1);
1714 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1717 decode_item_len(&src, &item_len);
1718 cmp = (*b->method->compare_item)(untilbuf, src);
1721 decode_ptr(&src, &nxtpos);
1722 if (cmp<pp->scope) /* cmp<2 */
1725 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning a hit "
1726 "at level %d node %d ofs=%d sz=%d",
1727 pp->level, p->pos, p->offset, p->size);
1732 p->offset = src-(char*)p->bytes;
1733 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1739 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at tail "
1740 "at level %d node %d ofs=%d sz=%d skips=%d",
1741 pp->level, p->pos, p->offset, p->size, skips);
1743 return pos; /* that's the last one in the line */
1745 } /* forward_unode */
1747 static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAM_P pos,
1748 const void *untilbuf)
1749 { /* climbs down the tree, from pos, to the leftmost leaf */
1750 struct ISAMB_block *p = pp->block[pp->level];
1754 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1755 "starting at lev %d node %d ofs=%d lf=%d u=%p",
1756 pp->level, p->pos, p->offset, p->leaf, untilbuf);
1759 pos = isamb_pp_forward_unode(pp, pos, untilbuf);
1762 p = open_block(pp->isamb, pos);
1763 pp->block[pp->level] = p;
1764 ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
1767 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1768 "got lev %d node %d lf=%d",
1769 pp->level, p->pos, p->leaf);
1773 assert (p->offset==0);
1774 src = p->bytes + p->offset;
1775 decode_ptr(&src, &pos);
1776 p->offset = src-(char*)p->bytes;
1777 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1779 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1780 "returning at lev %d node %d ofs=%d lf=%d",
1781 pp->level, p->pos, p->offset, p->leaf);
1783 } /* descend_to_leaf */
1785 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1786 { /* finds the next leaf by climbing up and down */
1788 if (!isamb_pp_climb_level(pp, &pos))
1790 isamb_pp_descend_to_leaf(pp, pos, 0);
1794 static int isamb_pp_climb_desc(ISAMB_PP pp, const void *untilbuf)
1795 { /* climbs up and descends to a leaf where values >= *untilbuf are found */
1798 struct ISAMB_block *p = pp->block[pp->level];
1799 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc starting "
1800 "at level %d node %d ofs=%d sz=%d",
1801 pp->level, p->pos, p->offset, p->size);
1803 if (!isamb_pp_climb_level(pp, &pos))
1805 /* see if it would pay to climb one higher */
1806 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1807 if (!isamb_pp_climb_level(pp, &pos))
1809 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1811 p = pp->block[pp->level];
1812 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc done "
1813 "at level %d node %d ofs=%d sz=%d",
1814 pp->level, p->pos, p->offset, p->size);
1819 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1822 struct ISAMB_block *p = pp->block[pp->level];
1824 yaz_log(YLOG_DEBUG, "isamb_pp_forward starting "
1825 "at level %d node %d ofs=%d sz=%d u=%p sc=%d",
1826 pp->level, p->pos, p->offset, p->size, untilbuf, scope);
1830 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1833 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (A) "
1834 "at level %d node %d ofs=%d sz=%d",
1835 pp->level, p->pos, p->offset, p->size);
1839 if (! isamb_pp_climb_desc(pp, untilbuf))
1842 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning notfound (B) "
1843 "at level %d node %d ofs=%d sz=%d",
1844 pp->level, p->pos, p->offset, p->size);
1846 return 0; /* could not find a leaf */
1849 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1852 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (c) "
1853 "at level %d node %d ofs=%d sz=%d",
1854 pp->level, p->pos, p->offset, p->size);
1858 } while (isamb_pp_find_next_leaf(pp));
1859 return 0; /* could not find at all */
1861 else { /* no untilbuf, a straight read */
1862 /* FIXME - this should be moved
1863 * directly into the pp_read */
1864 /* keeping here now, to keep same
1865 * interface as the old fwd */
1866 if (isamb_pp_read_on_leaf(pp, buf))
1869 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (D) "
1870 "at level %d node %d ofs=%d sz=%d",
1871 pp->level, p->pos, p->offset, p->size);
1875 if (isamb_pp_find_next_leaf(pp))
1878 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (E) "
1879 "at level %d node %d ofs=%d sz=%d",
1880 pp->level, p->pos, p->offset, p->size);
1882 return isamb_pp_read_on_leaf(pp, buf);
1887 } /* isam_pp_forward (new version) */
1889 void isamb_pp_pos(ISAMB_PP pp, double *current, double *total)
1890 { /* return an estimate of the current position and of the total number of */
1891 /* occureences in the isam tree, based on the current leaf */
1895 /* if end-of-stream PP may not be leaf */
1897 *total = (double) (pp->block[0]->no_items);
1898 *current = (double) pp->returned_numbers;
1900 yaz_log(YLOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
1901 ZINT_FORMAT, *current, *total, pp->returned_numbers);
1905 int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb)
1909 struct ISAMB_block *p = pp->block[pp->level];
1910 ISAMB b = pp->isamb;
1914 while (p->offset == p->size)
1920 char file_item_buf[DST_ITEM_MAX];
1921 char *file_item = file_item_buf;
1925 while (p->offset == p->size)
1929 close_block (pp->isamb, pp->block[pp->level]);
1930 pp->block[pp->level] = 0;
1932 p = pp->block[pp->level];
1937 src = p->bytes + p->offset;
1940 c1 = (*b->method->codec.start)();
1941 (*b->method->codec.decode)(c1, &file_item, &src);
1943 decode_ptr (&src, &item_len);
1946 decode_ptr (&src, &pos);
1947 p->offset = src - (char*) p->bytes;
1949 src = p->bytes + p->offset;
1953 if (!untilb || p->offset == p->size)
1955 assert(p->offset < p->size);
1958 file_item = file_item_buf;
1959 (*b->method->codec.reset)(c1);
1960 (*b->method->codec.decode)(c1, &file_item, &src);
1961 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
1967 decode_item_len(&src, &item_len);
1968 if ((*b->method->compare_item)(untilb, src) <= 1)
1972 decode_ptr (&src, &pos);
1973 p->offset = src - (char*) p->bytes;
1980 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1982 pp->total_size += p->size;
1990 src = p->bytes + p->offset;
1993 decode_ptr (&src, &pos);
1994 p->offset = src - (char*) p->bytes;
1996 if (!untilb || p->offset == p->size)
1998 assert(p->offset < p->size);
2001 file_item = file_item_buf;
2002 (*b->method->codec.reset)(c1);
2003 (*b->method->codec.decode)(c1, &file_item, &src);
2004 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
2010 decode_ptr (&src, &item_len);
2011 if ((*b->method->compare_item)(untilb, src) <= 1)
2019 (*b->method->codec.stop)(c1);
2022 assert (p->offset < p->size);
2027 src = p->bytes + p->offset;
2028 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
2029 p->offset = src - (char*) p->bytes;
2030 if (!untilb || (*pp->isamb->method->compare_item)(untilb, dst0) <= 1)
2033 if (p->offset == p->size) goto again;
2038 zint isamb_get_int_splits(ISAMB b)
2040 return b->number_of_int_splits;
2043 zint isamb_get_leaf_splits(ISAMB b)
2045 return b->number_of_leaf_splits;
2048 zint isamb_get_root_ptr(ISAMB b)
2053 void isamb_set_root_ptr(ISAMB b, zint root_ptr)
2055 b->root_ptr = root_ptr;
2062 * indent-tabs-mode: nil
2064 * vim: shiftwidth=4 tabstop=8 expandtab