1 /* $Id: isamb.c,v 1.89 2006-12-18 23:40:08 adam Exp $
2 Copyright (C) 1995-2006
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);
296 if (sscanf(hbuf+5, "%d %d %d", &major, &minor, &len) != 3)
298 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
301 if (major != ISAMB_MAJOR_VERSION)
303 yaz_log(YLOG_WARN, "bad major version for file %s %d, must be %d",
304 fname, major, ISAMB_MAJOR_VERSION);
307 for (left = len - sizes[i]; left > 0; left = left - sizes[i])
310 if (!bf_read(isamb->file[i].bf, pos, 0, 0, hbuf + pos*sizes[i]))
312 yaz_log(YLOG_WARN, "truncated isamb header for "
313 "file=%s len=%d pos=%d",
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);
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]);
334 yaz_log(YLOG_WARN, "isamb debug enabled. Things will be slower than usual");
339 ISAMB isamb_open(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
343 int i, b_size = ISAMB_MIN_SIZE;
345 for (i = 0; i<CAT_NO; i++)
348 b_size = b_size * ISAMB_FAC_SIZE;
350 return isamb_open2(bfs, name, writeflag, method, cache,
354 static void flush_blocks (ISAMB b, int cat)
356 while (b->file[cat].cache_entries)
358 struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
359 b->file[cat].cache_entries = ce_this->next;
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);
371 static int cache_block (ISAMB b, ISAM_P pos, unsigned char *userbuf, int wr)
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);
379 struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
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++)
388 if ((*ce)->pos == norm)
391 *ce = (*ce)->next; /* remove from list */
393 ce_this->next = b->file[cat].cache_entries; /* move to front */
394 b->file[cat].cache_entries = ce_this;
398 memcpy (ce_this->buf + off, userbuf,
399 b->file[cat].head.block_size);
403 memcpy (userbuf, ce_this->buf + off,
404 b->file[cat].head.block_size);
408 if (no >= b->cache_size)
410 assert (ce_last && *ce_last);
412 *ce_last = 0; /* remove the last entry from list */
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);
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);
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);
431 memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
437 memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
443 void isamb_close (ISAMB isamb)
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++)
455 flush_blocks (isamb, i);
456 if (isamb->file[i].head_dirty)
458 char hbuf[DST_BUF_SIZE];
459 int major = ISAMB_MAJOR_VERSION;
461 char *dst = hbuf + 16;
463 int b_size = isamb->file[i].head.block_size;
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);
471 if (isamb->minor_version >= ISAMB_MINOR_VERSION_WITH_ROOT)
472 encode_ptr(&dst, isamb->root_ptr);
474 memset(dst, '\0', b_size); /* ensure no random bytes are written */
478 /* print exactly 16 bytes (including trailing 0) */
479 sprintf(hbuf, "isamb%02d %02d %02d\r\n", major,
480 isamb->minor_version, len);
482 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf);
484 for (left = len - b_size; left > 0; left = left - b_size)
487 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
490 if (isamb->file[i].bf)
491 bf_close (isamb->file[i].bf);
494 xfree(isamb->method);
498 /* open_block: read one block at pos.
499 Decode leading sys bytes .. consisting of
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
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.
508 static struct ISAMB_block *open_block(ISAMB b, ISAM_P pos)
510 int cat = (int) (pos&CAT_MASK);
512 int offset = b->file[cat].head.block_offset;
513 struct ISAMB_block *p;
516 p = xmalloc(sizeof(*p));
518 p->cat = (int) (pos & CAT_MASK);
519 p->buf = xmalloc(b->file[cat].head.block_size);
522 if (!cache_block (b, pos, p->buf, 0))
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)
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");
532 p->bytes = (char *)p->buf + offset;
534 p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
537 yaz_log(YLOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
540 assert (p->size >= 0);
541 src = (char*) p->buf + 3;
542 decode_ptr(&src, &p->no_items);
547 p->decodeClientData = (*b->method->codec.start)();
551 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
553 struct ISAMB_block *p;
555 p = xmalloc(sizeof(*p));
556 p->buf = xmalloc(b->file[cat].head.block_size);
558 if (!b->file[cat].head.free_list)
561 block_no = b->file[cat].head.last_block++;
562 p->pos = block_no * CAT_MAX + cat;
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))
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))
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");
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));
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;
592 p->decodeClientData = (*b->method->codec.start)();
596 struct ISAMB_block *new_leaf (ISAMB b, int cat)
598 return new_block (b, 1, cat);
602 struct ISAMB_block *new_int (ISAMB b, int cat)
604 return new_block (b, 0, cat);
607 static void check_block (ISAMB b, struct ISAMB_block *p)
609 assert(b); /* mostly to make the compiler shut up about unused b */
617 char *startp = p->bytes;
618 const char *src = startp;
619 char *endp = p->bytes + p->size;
621 void *c1 = (*b->method->codec.start)();
623 decode_ptr(&src, &pos);
624 assert ((pos&CAT_MASK) == p->cat);
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);
634 decode_item_len(&src, &item_len);
635 assert (item_len > 0 && item_len < 80);
638 decode_ptr(&src, &pos);
639 if ((pos&CAT_MASK) != p->cat)
641 assert ((pos&CAT_MASK) == p->cat);
644 (*b->method->codec.stop)(c1);
648 void close_block(ISAMB b, struct ISAMB_block *p)
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))
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);
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);
671 /* memset becuase encode_ptr usually does not write all bytes */
672 memset(p->buf, 0, b->file[p->cat].head.block_offset);
674 p->buf[1] = size & 255;
675 p->buf[2] = size >> 8;
676 encode_ptr(&dst, p->no_items);
678 if (!cache_block (b, p->pos, p->buf, 1))
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);
684 (*b->method->codec.stop)(p->decodeClientData);
689 int insert_sub (ISAMB b, struct ISAMB_block **p,
690 void *new_item, int *mode,
692 struct ISAMB_block **sp,
693 void *sub_item, int *sub_size,
694 const void *max_item);
696 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
698 ISAMC_I *stream, struct ISAMB_block **sp,
699 void *split_item, int *split_size, const void *last_max_item)
701 char *startp = p->bytes;
702 const char *src = startp;
703 char *endp = p->bytes + p->size;
705 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
706 char sub_item[DST_ITEM_MAX];
710 void *c1 = (*b->method->codec.start)();
714 assert(p->size >= 0);
715 decode_ptr(&src, &pos);
719 const char *src0 = src;
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);
728 sub_p1 = open_block(b, pos);
730 diff_terms -= sub_p1->no_items;
731 more = insert_sub (b, &sub_p1, lookahead_item, mode,
733 sub_item, &sub_size, file_item_buf);
734 diff_terms += sub_p1->no_items;
740 decode_item_len(&src, &item_len);
741 d = (*b->method->compare_item)(src, lookahead_item);
744 sub_p1 = open_block(b, pos);
746 diff_terms -= sub_p1->no_items;
747 more = insert_sub (b, &sub_p1, lookahead_item, mode,
749 sub_item, &sub_size, src);
750 diff_terms += sub_p1->no_items;
756 decode_ptr(&src, &pos);
760 /* we reached the end. So lookahead > last item */
761 sub_p1 = open_block(b, pos);
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;
769 diff_terms += sub_p2->no_items;
773 p->no_items += diff_terms;
777 /* there was a split - must insert pointer in this one */
778 char dst_buf[DST_BUF_SIZE];
781 const char *sub_item_ptr = sub_item;
783 assert (sub_size < 80 && sub_size > 1);
785 memcpy (dst, startp, src - startp);
790 (*b->method->codec.reset)(c1);
791 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
793 encode_item_len (&dst, sub_size); /* sub length and item */
794 memcpy (dst, sub_item, sub_size);
798 encode_ptr(&dst, sub_p2->pos); /* pos */
800 if (endp - src) /* remaining data */
802 memcpy (dst, src, endp - src);
805 p->size = dst - dst_buf;
806 assert (p->size >= 0);
808 if (p->size <= b->file[p->cat].head.block_max)
810 /* it fits OK in this block */
811 memcpy (startp, dst_buf, dst - dst_buf);
813 close_block(b, sub_p2);
817 /* must split _this_ block as well .. */
818 struct ISAMB_block *sub_p3;
820 char file_item_buf[DST_ITEM_MAX];
821 char *file_item = file_item_buf;
825 zint no_items_first_half = 0;
831 b->number_of_int_splits++;
834 close_block(b, sub_p2);
836 half = src + b->file[p->cat].head.block_size/2;
837 decode_ptr(&src, &pos);
839 if (b->enable_int_count)
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);
850 file_item = file_item_buf;
851 (*b->method->codec.reset)(c1);
852 (*b->method->codec.decode)(c1, &file_item, &src);
854 decode_item_len(&src, &split_size_tmp);
855 *split_size = (int) split_size_tmp;
858 decode_ptr(&src, &pos);
860 if (b->enable_int_count)
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);
868 /* p is first half */
869 p_new_size = src - dst_buf;
870 memcpy (p->bytes, dst_buf, p_new_size);
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);
879 decode_item_len(&src, &split_size_tmp);
880 *split_size = (int) split_size_tmp;
881 memcpy (split_item, src, *split_size);
884 /* *sp is second half */
885 *sp = new_int (b, p->cat);
886 (*sp)->size = endp - src;
887 memcpy ((*sp)->bytes, src, (*sp)->size);
889 p->size = p_new_size;
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;
897 close_block(b, sub_p1);
898 (*b->method->codec.stop)(c1);
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)
908 struct ISAMB_block *p = *sp1;
911 char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
913 void *c1 = (*b->method->codec.start)();
914 void *c2 = (*b->method->codec.start)();
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;
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;
930 char file_item_buf[DST_ITEM_MAX];
931 char *file_item = file_item_buf;
934 endp = p->bytes + p->size;
935 (*b->method->codec.decode)(c1, &file_item, &src);
938 const char *dst_item = 0; /* resulting item to be inserted */
939 char *lookahead_next;
944 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
946 /* d now holds comparison between existing file item and
949 d > 0: lookahead before file
950 d < 0: lookahead after file
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)
959 yaz_log(YLOG_WARN, "isamb: Inconsistent register (1)");
960 assert(*lookahead_mode);
964 dst_item = file_item_buf;
966 if (!*lookahead_mode && d == 0)
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 */
973 else if (!half1 && dst > mid_cut)
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 */
979 /* encode the resulting item */
980 (*b->method->codec.encode)(c2, &dst, &dst_item);
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);
987 no_items_1 = no_items;
992 /* encode the resulting item */
993 (*b->method->codec.encode)(c2, &dst, &dst_item);
997 /* now move "pointers" .. result has been encoded .. */
1000 /* we must move the lookahead pointer */
1002 inserted_dst_bytes += (dst - dst_0);
1003 if (inserted_dst_bytes >= quater)
1004 /* no more room. Mark lookahead as "gone".. */
1008 /* move it really.. */
1009 lookahead_next = lookahead_item;
1010 if (!(*stream->read_item)(stream->clientData,
1014 /* end of stream reached: no "more" and no lookahead */
1018 if (lookahead_item && max_item &&
1019 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1021 /* the lookahead goes beyond what we allow in this
1022 leaf. Mark it as "gone" */
1031 /* exact match .. move both pointers */
1033 lookahead_next = lookahead_item;
1034 if (!(*stream->read_item)(stream->clientData,
1035 &lookahead_next, lookahead_mode))
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);
1047 /* file pointer must be moved */
1050 file_item = file_item_buf;
1051 (*b->method->codec.decode)(c1, &file_item, &src);
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
1060 maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
1061 while (lookahead_item)
1064 const char *src = lookahead_item;
1067 /* if we have a lookahead item, we stop if we exceed the value of it */
1069 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1071 /* stop if we have reached the value of max item */
1074 if (!*lookahead_mode)
1076 /* this is append. So a delete is bad */
1077 yaz_log(YLOG_WARN, "isamb: Inconsistent register (2)");
1078 assert(*lookahead_mode);
1080 else if (!half1 && dst > tail_cut)
1082 const char *src_0 = src;
1083 half1 = dst; /* candidate for splitting */
1085 (*b->method->codec.encode)(c2, &dst, &src);
1087 cut_item_size = src - src_0;
1088 assert(cut_item_size > 0);
1089 memcpy (cut_item_buf, src_0, cut_item_size);
1091 no_items_1 = no_items;
1095 (*b->method->codec.encode)(c2, &dst, &src);
1105 dst_item = lookahead_item;
1106 if (!(*stream->read_item)(stream->clientData, &dst_item,
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)
1117 /* non-btree block will be removed */
1120 /* delete it too!! */
1121 p = 0; /* make a new one anyway */
1124 { /* must create a new one */
1126 for (i = 0; i < b->no_cat; i++)
1127 if (new_size <= b->file[i].head.block_max)
1131 p = new_leaf (b, i);
1133 if (new_size > b->file[p->cat].head.block_max)
1136 const char *cut_item = cut_item_buf;
1141 assert(cut_item_size > 0);
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;
1150 *sp2 = new_leaf (b, p->cat);
1152 (*b->method->codec.reset)(c2);
1154 b->number_of_leaf_splits++;
1156 first_dst = (*sp2)->bytes;
1158 (*b->method->codec.encode)(c2, &first_dst, &cut_item);
1160 memcpy (first_dst, half2, dst - half2);
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;
1167 memcpy (sub_item, cut_item_buf, cut_item_size);
1168 *sub_size = cut_item_size;
1172 memcpy (p->bytes, dst_buf, dst - dst_buf);
1174 p->no_items = no_items;
1176 (*b->method->codec.stop)(c1);
1177 (*b->method->codec.stop)(c2);
1182 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1185 struct ISAMB_block **sp,
1186 void *sub_item, int *sub_size,
1187 const void *max_item)
1189 if (!*p || (*p)->leaf)
1190 return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1191 sub_size, max_item);
1193 return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1194 sub_size, max_item);
1197 int isamb_unlink (ISAMB b, ISAM_P pos)
1199 struct ISAMB_block *p1;
1203 p1 = open_block(b, pos);
1208 const char *src = p1->bytes + p1->offset;
1210 void *c1 = (*b->method->codec.start)();
1212 decode_ptr(&src, &sub_p);
1213 isamb_unlink(b, sub_p);
1215 while (src != p1->bytes + p1->size)
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);
1224 decode_item_len(&src, &item_len);
1227 decode_ptr(&src, &sub_p);
1228 isamb_unlink(b, sub_p);
1231 (*b->method->codec.stop)(c1);
1238 void isamb_merge(ISAMB b, ISAM_P *pos, ISAMC_I *stream)
1240 char item_buf[DST_ITEM_MAX];
1244 int must_delete = 0;
1251 item_ptr = item_buf;
1253 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1258 item_ptr = item_buf;
1259 more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1262 struct ISAMB_block *p = 0, *sp = 0;
1263 char sub_item[DST_ITEM_MAX];
1267 p = open_block(b, *pos);
1268 more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1269 sub_item, &sub_size, 0);
1271 { /* increase level of tree by one */
1272 struct ISAMB_block *p2 = new_int (b, p->cat);
1273 char *dst = p2->bytes + p2->size;
1275 void *c1 = (*b->method->codec.start)();
1276 const char *sub_item_ptr = sub_item;
1279 encode_ptr(&dst, p->pos);
1280 assert (sub_size < 80 && sub_size > 1);
1282 (*b->method->codec.reset)(c1);
1283 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
1285 encode_item_len (&dst, sub_size);
1286 memcpy (dst, sub_item, sub_size);
1289 encode_ptr(&dst, sp->pos);
1291 p2->size = dst - p2->bytes;
1292 p2->no_items = p->no_items + sp->no_items;
1293 *pos = p2->pos; /* return new super page */
1297 (*b->method->codec.stop)(c1);
1302 *pos = p->pos; /* return current one (again) */
1304 if (p->no_items == 0)
1312 isamb_unlink(b, *pos);
1317 ISAMB_PP isamb_pp_open_x(ISAMB isamb, ISAM_P pos, int *level, int scope)
1319 ISAMB_PP pp = xmalloc(sizeof(*pp));
1325 pp->block = xmalloc(ISAMB_MAX_LEVEL * sizeof(*pp->block));
1332 pp->skipped_numbers = 0;
1333 pp->returned_numbers = 0;
1335 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
1336 pp->skipped_nodes[i] = pp->accessed_nodes[i] = 0;
1339 struct ISAMB_block *p = open_block(isamb, pos);
1340 const char *src = p->bytes + p->offset;
1341 pp->block[pp->level] = p;
1343 pp->total_size += p->size;
1347 decode_ptr(&src, &pos);
1348 p->offset = src - p->bytes;
1350 pp->accessed_nodes[pp->level]++;
1352 pp->block[pp->level+1] = 0;
1353 pp->maxlevel = pp->level;
1359 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAM_P pos, int scope)
1361 return isamb_pp_open_x(isamb, pos, 0, scope);
1364 void isamb_pp_close_x(ISAMB_PP pp, zint *size, zint *blocks)
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--)
1381 pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1382 pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1385 *size = pp->total_size;
1387 *blocks = pp->no_blocks;
1388 for (i = 0; i <= pp->level; i++)
1389 close_block(pp->isamb, pp->block[i]);
1394 int isamb_block_info (ISAMB isamb, int cat)
1396 if (cat >= 0 && cat < isamb->no_cat)
1397 return isamb->file[cat].head.block_size;
1401 void isamb_pp_close (ISAMB_PP pp)
1403 isamb_pp_close_x(pp, 0, 0);
1406 /* simple recursive dumper .. */
1407 static void isamb_dump_r (ISAMB b, ISAM_P pos, void (*pr)(const char *str),
1411 char prefix_str[1024];
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,
1420 sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1423 while (p->offset < p->size)
1425 const char *src = p->bytes + p->offset;
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;
1431 assert(p->offset == p->size);
1435 const char *src = p->bytes + p->offset;
1438 decode_ptr(&src, &sub);
1439 p->offset = src - (char*) p->bytes;
1441 isamb_dump_r(b, sub, pr, level+1);
1443 while (p->offset < p->size)
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);
1454 decode_item_len(&src, &item_len);
1455 (*b->method->log_item)(YLOG_DEBUG, src, prefix_str);
1458 decode_ptr(&src, &sub);
1460 p->offset = src - (char*) p->bytes;
1462 isamb_dump_r(b, sub, pr, level+1);
1469 void isamb_dump(ISAMB b, ISAM_P pos, void (*pr)(const char *str))
1471 isamb_dump_r(b, pos, pr, 0);
1474 int isamb_pp_read(ISAMB_PP pp, void *buf)
1476 return isamb_pp_forward(pp, buf, 0);
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;
1487 ISAMB b = pp->isamb;
1493 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true for root");
1495 return 1; /* we can never skip the root node */
1498 p = pp->block[level];
1499 assert(p->offset <= p->size);
1500 if (p->offset < p->size)
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);
1513 assert(p->offset > 0);
1514 src = p->bytes + p->offset;
1515 decode_item_len(&src, &item_len);
1517 (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until");
1518 (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value");
1520 cmp = (*b->method->compare_item)(untilbuf, src);
1522 if (cmp < pp->scope)
1525 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true "
1526 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1533 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false "
1534 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1541 yaz_log(YLOG_DEBUG, "isamb_pp_on_right at tail, looking higher "
1544 return isamb_pp_on_right_node(pp, level, untilbuf);
1546 } /* isamb_pp_on_right_node */
1548 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1550 /* reads the next item on the current leaf, returns 0 if end of leaf*/
1551 struct ISAMB_block *p = pp->block[pp->level];
1556 if (p->offset == p->size)
1559 yaz_log(YLOG_DEBUG, "isamb_pp_read_on_leaf returning 0 on "
1562 return 0; /* at end of leaf */
1564 src = p->bytes + p->offset;
1566 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1567 p->offset = src - (char*) p->bytes;
1569 (*pp->isamb->method->codec.log_item)(YLOG_DEBUG, buf,
1570 "read_on_leaf returning 1");
1572 pp->returned_numbers++;
1574 } /* read_on_leaf */
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 */
1582 if (!isamb_pp_read_on_leaf(pp, buf))
1584 /* FIXME - this is an extra function call, inline the read? */
1585 cmp=(*pp->isamb->method->compare_item)(untilbuf, buf);
1587 { /* cmp<2 found a good one */
1590 yaz_log(YLOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items", skips);
1592 pp->returned_numbers++;
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++;
1601 } /* forward_on_leaf */
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];
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);
1613 assert(pp->level >= 0);
1614 assert(p->offset <= p->size);
1618 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level returning 0 at root");
1622 assert(pp->level>0);
1623 close_block(pp->isamb, pp->block[pp->level]);
1624 pp->block[pp->level] = 0;
1626 p = pp->block[pp->level];
1628 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1629 pp->level, p->pos, p->offset);
1632 assert(p->offset <= p->size);
1633 if (p->offset == p->size)
1635 /* we came from the last pointer, climb on */
1636 if (!isamb_pp_climb_level(pp, pos))
1638 p = pp->block[pp->level];
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)();
1650 /* skip the child we just came from */
1652 yaz_log(YLOG_DEBUG, "isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1653 pp->level, p->offset, p->size);
1655 assert (p->offset < p->size);
1656 src = p->bytes + p->offset;
1658 (*b->method->codec.decode)(c1, &file_item, &src);
1659 (*b->method->codec.stop)(c1);
1661 decode_item_len(&src, &item_len);
1664 decode_ptr(&src, pos);
1665 p->offset = src - (char *)p->bytes;
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 */
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;
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);
1692 assert(p->offset <= p->size);
1693 if (p->offset == p->size)
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);
1700 return pos; /* already at the end of it */
1702 while(p->offset < p->size)
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);
1713 decode_item_len(&src, &item_len);
1714 cmp = (*b->method->compare_item)(untilbuf, src);
1717 decode_ptr(&src, &nxtpos);
1718 if (cmp<pp->scope) /* cmp<2 */
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);
1728 p->offset = src-(char*)p->bytes;
1729 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
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);
1739 return pos; /* that's the last one in the line */
1741 } /* forward_unode */
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];
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);
1755 pos = isamb_pp_forward_unode(pp, pos, untilbuf);
1758 p = open_block(pp->isamb, pos);
1759 pp->block[pp->level] = p;
1760 ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
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);
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);
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);
1779 } /* descend_to_leaf */
1781 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1782 { /* finds the next leaf by climbing up and down */
1784 if (!isamb_pp_climb_level(pp, &pos))
1786 isamb_pp_descend_to_leaf(pp, pos, 0);
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 */
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);
1799 if (!isamb_pp_climb_level(pp, &pos))
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))
1805 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
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);
1815 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1818 struct ISAMB_block *p = pp->block[pp->level];
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);
1826 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
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);
1835 if (! isamb_pp_climb_desc(pp, untilbuf))
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);
1842 return 0; /* could not find a leaf */
1845 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
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);
1854 } while (isamb_pp_find_next_leaf(pp));
1855 return 0; /* could not find at all */
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))
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);
1871 if (isamb_pp_find_next_leaf(pp))
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);
1878 return isamb_pp_read_on_leaf(pp, buf);
1883 } /* isam_pp_forward (new version) */
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 */
1891 /* if end-of-stream PP may not be leaf */
1893 *total = (double) (pp->block[0]->no_items);
1894 *current = (double) pp->returned_numbers;
1896 yaz_log(YLOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
1897 ZINT_FORMAT, *current, *total, pp->returned_numbers);
1901 int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb)
1905 struct ISAMB_block *p = pp->block[pp->level];
1906 ISAMB b = pp->isamb;
1910 while (p->offset == p->size)
1916 char file_item_buf[DST_ITEM_MAX];
1917 char *file_item = file_item_buf;
1921 while (p->offset == p->size)
1925 close_block (pp->isamb, pp->block[pp->level]);
1926 pp->block[pp->level] = 0;
1928 p = pp->block[pp->level];
1933 src = p->bytes + p->offset;
1936 c1 = (*b->method->codec.start)();
1937 (*b->method->codec.decode)(c1, &file_item, &src);
1939 decode_ptr (&src, &item_len);
1942 decode_ptr (&src, &pos);
1943 p->offset = src - (char*) p->bytes;
1945 src = p->bytes + p->offset;
1949 if (!untilb || p->offset == p->size)
1951 assert(p->offset < p->size);
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)
1963 decode_item_len(&src, &item_len);
1964 if ((*b->method->compare_item)(untilb, src) <= 1)
1968 decode_ptr (&src, &pos);
1969 p->offset = src - (char*) p->bytes;
1976 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1978 pp->total_size += p->size;
1986 src = p->bytes + p->offset;
1989 decode_ptr (&src, &pos);
1990 p->offset = src - (char*) p->bytes;
1992 if (!untilb || p->offset == p->size)
1994 assert(p->offset < p->size);
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)
2006 decode_ptr (&src, &item_len);
2007 if ((*b->method->compare_item)(untilb, src) <= 1)
2015 (*b->method->codec.stop)(c1);
2018 assert (p->offset < p->size);
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)
2029 if (p->offset == p->size) goto again;
2034 zint isamb_get_int_splits(ISAMB b)
2036 return b->number_of_int_splits;
2039 zint isamb_get_leaf_splits(ISAMB b)
2041 return b->number_of_leaf_splits;
2044 zint isamb_get_root_ptr(ISAMB b)
2049 void isamb_set_root_ptr(ISAMB b, zint root_ptr)
2051 b->root_ptr = root_ptr;
2058 * indent-tabs-mode: nil
2060 * vim: shiftwidth=4 tabstop=8 expandtab