1 /* $Id: isamb.c,v 1.88 2006-12-12 13:46:41 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 0
48 /* if 1, upper nodes items are encoded; 0 if not encoded */
51 /* maximum size of encoded buffer */
52 #define DST_ITEM_MAX 256
54 #define ISAMB_MAX_LEVEL 10
55 /* approx 2*max page + max size of item */
56 #define DST_BUF_SIZE (2*4096+300)
58 /* should be maximum block size of multiple thereof */
59 #define ISAMB_CACHE_ENTRY_SIZE 4096
61 /* CAT_MAX: _must_ be power of 2 */
63 #define CAT_MASK (CAT_MAX-1)
64 /* CAT_NO: <= CAT_MAX */
67 /* Smallest block size */
68 #define ISAMB_MIN_SIZE 32
70 #define ISAMB_FAC_SIZE 4
72 /* ISAMB_PTR_CODEC = 1 var, =0 fixed */
73 #define ISAMB_PTR_CODEC 1
75 struct ISAMB_cache_entry {
80 struct ISAMB_cache_entry *next;
86 struct ISAMB_head head;
87 struct ISAMB_cache_entry *cache_entries;
94 struct ISAMB_file *file;
96 int cache; /* 0 = no cache, 1 = use cache, -1 = dummy isam (for testing only) */
97 int log_io; /* log level for bf_read/bf_write calls */
98 int log_freelist; /* log level for freelist handling */
99 zint skipped_numbers; /* on a leaf node */
100 zint returned_numbers;
101 zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1 = higher etc */
102 zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
103 zint number_of_int_splits;
104 zint number_of_leaf_splits;
105 int enable_int_count; /* whether we count nodes (or not) */
106 int cache_size; /* size of blocks to cache (if cache=1) */
117 zint no_items; /* number of nodes in this + children */
121 void *decodeClientData;
129 int maxlevel; /* total depth */
132 zint skipped_numbers; /* on a leaf node */
133 zint returned_numbers;
134 zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1 = higher etc */
135 zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
136 struct ISAMB_block **block;
137 int scope; /* on what level we forward */
141 #define encode_item_len encode_ptr
143 static void encode_ptr(char **dst, zint pos)
145 unsigned char *bp = (unsigned char*) *dst;
149 *bp++ = (unsigned char) (128 | (pos & 127));
152 *bp++ = (unsigned char) pos;
156 static void encode_ptr(char **dst, zint pos)
158 memcpy(*dst, &pos, sizeof(pos));
159 (*dst) += sizeof(pos);
163 #define decode_item_len decode_ptr
165 static void decode_ptr(const char **src, zint *pos)
171 while (((c = *(const unsigned char *)((*src)++)) & 128))
173 d += ((zint) (c & 127) << r);
176 d += ((zint) c << r);
180 static void decode_ptr(const char **src, zint *pos)
182 memcpy(pos, *src, sizeof(*pos));
183 (*src) += sizeof(*pos);
188 void isamb_set_int_count(ISAMB b, int v)
190 b->enable_int_count = v;
193 void isamb_set_cache_size(ISAMB b, int v)
198 ISAMB isamb_open(BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
201 ISAMB isamb = xmalloc(sizeof(*isamb));
202 int i, b_size = ISAMB_MIN_SIZE;
205 isamb->method = (ISAMC_M *) xmalloc(sizeof(*method));
206 memcpy(isamb->method, method, sizeof(*method));
207 isamb->no_cat = CAT_NO;
209 isamb->log_freelist = 0;
210 isamb->cache = cache;
211 isamb->skipped_numbers = 0;
212 isamb->returned_numbers = 0;
213 isamb->number_of_int_splits = 0;
214 isamb->number_of_leaf_splits = 0;
215 isamb->enable_int_count = 1;
216 isamb->cache_size = 40;
218 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
219 isamb->skipped_nodes[i] = isamb->accessed_nodes[i] = 0;
223 yaz_log(YLOG_WARN, "isamb_open %s. Degraded TEST mode", name);
227 assert(cache == 0 || cache == 1);
229 isamb->file = xmalloc(sizeof(*isamb->file) * isamb->no_cat);
231 for (i = 0; i < isamb->no_cat; i++)
233 isamb->file[i].bf = 0;
234 isamb->file[i].head_dirty = 0;
235 isamb->file[i].cache_entries = 0;
238 for (i = 0; i < isamb->no_cat; i++)
240 char fname[DST_BUF_SIZE];
241 char hbuf[DST_BUF_SIZE];
243 sprintf(fname, "%s%c", name, i+'A');
245 isamb->file[i].bf = bf_open(bfs, fname, ISAMB_CACHE_ENTRY_SIZE,
248 isamb->file[i].bf = bf_open(bfs, fname, b_size, writeflag);
250 if (!isamb->file[i].bf)
256 /* fill-in default values (for empty isamb) */
257 isamb->file[i].head.first_block = ISAMB_CACHE_ENTRY_SIZE/b_size+1;
258 isamb->file[i].head.last_block = isamb->file[i].head.first_block;
259 isamb->file[i].head.block_size = b_size;
260 assert(b_size <= ISAMB_CACHE_ENTRY_SIZE);
262 if (i == isamb->no_cat-1 || b_size > 128)
263 isamb->file[i].head.block_offset = 8;
265 isamb->file[i].head.block_offset = 4;
267 isamb->file[i].head.block_offset = 11;
269 isamb->file[i].head.block_max =
270 b_size - isamb->file[i].head.block_offset;
271 isamb->file[i].head.free_list = 0;
272 if (bf_read(isamb->file[i].bf, 0, 0, 0, hbuf))
274 /* got header assume "isamb"major minor len can fit in 16 bytes */
276 int major, minor, len, pos = 0;
279 if (memcmp(hbuf, "isamb", 5))
281 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
284 if (sscanf(hbuf+5, "%d %d %d", &major, &minor, &len) != 3)
286 yaz_log(YLOG_WARN, "bad isamb header for file %s", fname);
289 if (major != ISAMB_MAJOR_VERSION)
291 yaz_log(YLOG_WARN, "bad major version for file %s %d, must be %d",
292 fname, major, ISAMB_MAJOR_VERSION);
295 for (left = len - b_size; left > 0; left = left - b_size)
298 if (!bf_read(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size))
300 yaz_log(YLOG_WARN, "truncated isamb header for "
301 "file=%s len=%d pos=%d",
307 decode_ptr(&src, &isamb->file[i].head.first_block);
308 decode_ptr(&src, &isamb->file[i].head.last_block);
309 decode_ptr(&src, &zint_tmp);
310 isamb->file[i].head.block_size = (int) zint_tmp;
311 decode_ptr(&src, &zint_tmp);
312 isamb->file[i].head.block_max = (int) zint_tmp;
313 decode_ptr(&src, &isamb->file[i].head.free_list);
315 assert (isamb->file[i].head.block_size >= isamb->file[i].head.block_offset);
316 isamb->file[i].head_dirty = 0;
317 assert(isamb->file[i].head.block_size == b_size);
318 b_size = b_size * ISAMB_FAC_SIZE;
321 yaz_log(YLOG_WARN, "isamb debug enabled. Things will be slower than usual");
326 static void flush_blocks (ISAMB b, int cat)
328 while (b->file[cat].cache_entries)
330 struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
331 b->file[cat].cache_entries = ce_this->next;
335 yaz_log(b->log_io, "bf_write: flush_blocks");
336 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
343 static int cache_block (ISAMB b, ISAM_P pos, unsigned char *userbuf, int wr)
345 int cat = (int) (pos&CAT_MASK);
346 int off = (int) (((pos/CAT_MAX) &
347 (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
348 * b->file[cat].head.block_size);
349 zint norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
351 struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
356 assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
357 for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
360 if ((*ce)->pos == norm)
363 *ce = (*ce)->next; /* remove from list */
365 ce_this->next = b->file[cat].cache_entries; /* move to front */
366 b->file[cat].cache_entries = ce_this;
370 memcpy (ce_this->buf + off, userbuf,
371 b->file[cat].head.block_size);
375 memcpy (userbuf, ce_this->buf + off,
376 b->file[cat].head.block_size);
380 if (no >= b->cache_size)
382 assert (ce_last && *ce_last);
384 *ce_last = 0; /* remove the last entry from list */
387 yaz_log(b->log_io, "bf_write: cache_block");
388 bf_write(b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
393 ce_this = xmalloc(sizeof(*ce_this));
394 ce_this->next = b->file[cat].cache_entries;
395 b->file[cat].cache_entries = ce_this;
396 ce_this->buf = xmalloc(ISAMB_CACHE_ENTRY_SIZE);
398 yaz_log(b->log_io, "bf_read: cache_block");
399 if (!bf_read(b->file[cat].bf, norm, 0, 0, ce_this->buf))
400 memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
403 memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
409 memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
415 void isamb_close (ISAMB isamb)
418 for (i = 0; isamb->accessed_nodes[i]; i++)
419 yaz_log(YLOG_DEBUG, "isamb_close level leaf-%d: "ZINT_FORMAT" read, "
420 ZINT_FORMAT" skipped",
421 i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]);
422 yaz_log(YLOG_DEBUG, "isamb_close returned "ZINT_FORMAT" values, "
423 "skipped "ZINT_FORMAT,
424 isamb->skipped_numbers, isamb->returned_numbers);
425 for (i = 0; i<isamb->no_cat; i++)
427 flush_blocks (isamb, i);
428 if (isamb->file[i].head_dirty)
430 char hbuf[DST_BUF_SIZE];
431 int major = ISAMB_MAJOR_VERSION;
432 int minor = ISAMB_MINOR_VERSION;
434 char *dst = hbuf + 16;
436 int b_size = isamb->file[i].head.block_size;
438 encode_ptr(&dst, isamb->file[i].head.first_block);
439 encode_ptr(&dst, isamb->file[i].head.last_block);
440 encode_ptr(&dst, isamb->file[i].head.block_size);
441 encode_ptr(&dst, isamb->file[i].head.block_max);
442 encode_ptr(&dst, isamb->file[i].head.free_list);
443 memset(dst, '\0', b_size); /* ensure no random bytes are written */
447 /* print exactly 16 bytes (including trailing 0) */
448 sprintf(hbuf, "isamb%02d %02d %02d\r\n", major, minor, len);
450 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf);
452 for (left = len - b_size; left > 0; left = left - b_size)
455 bf_write(isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
458 if (isamb->file[i].bf)
459 bf_close (isamb->file[i].bf);
462 xfree(isamb->method);
466 /* open_block: read one block at pos.
467 Decode leading sys bytes .. consisting of
469 0: leader byte, != 0 leaf, == 0, non-leaf
470 1-2: used size of block
471 3-7*: number of items and all children
473 * Reserve 5 bytes for large block sizes. 1 for small ones .. Number
474 of items. We can thus have at most 2^40 nodes.
476 static struct ISAMB_block *open_block(ISAMB b, ISAM_P pos)
478 int cat = (int) (pos&CAT_MASK);
480 int offset = b->file[cat].head.block_offset;
481 struct ISAMB_block *p;
484 p = xmalloc(sizeof(*p));
486 p->cat = (int) (pos & CAT_MASK);
487 p->buf = xmalloc(b->file[cat].head.block_size);
490 if (!cache_block (b, pos, p->buf, 0))
492 yaz_log(b->log_io, "bf_read: open_block");
493 if (bf_read(b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf) != 1)
495 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
496 (long) pos, (long) pos/CAT_MAX);
497 zebra_exit("isamb:open_block");
500 p->bytes = (char *)p->buf + offset;
502 p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
505 yaz_log(YLOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
508 assert (p->size >= 0);
509 src = (char*) p->buf + 3;
510 decode_ptr(&src, &p->no_items);
515 p->decodeClientData = (*b->method->codec.start)();
519 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
521 struct ISAMB_block *p;
523 p = xmalloc(sizeof(*p));
524 p->buf = xmalloc(b->file[cat].head.block_size);
526 if (!b->file[cat].head.free_list)
529 block_no = b->file[cat].head.last_block++;
530 p->pos = block_no * CAT_MAX + cat;
534 p->pos = b->file[cat].head.free_list;
535 assert((p->pos & CAT_MASK) == cat);
536 if (!cache_block (b, p->pos, p->buf, 0))
538 yaz_log(b->log_io, "bf_read: new_block");
539 if (!bf_read(b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf))
541 yaz_log(YLOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
542 (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX);
543 zebra_exit("isamb:new_block");
546 yaz_log(b->log_freelist, "got block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT, p->pos,
547 cat, p->pos/CAT_MAX);
548 memcpy (&b->file[cat].head.free_list, p->buf, sizeof(zint));
551 b->file[cat].head_dirty = 1;
552 memset (p->buf, 0, b->file[cat].head.block_size);
553 p->bytes = (char*)p->buf + b->file[cat].head.block_offset;
560 p->decodeClientData = (*b->method->codec.start)();
564 struct ISAMB_block *new_leaf (ISAMB b, int cat)
566 return new_block (b, 1, cat);
570 struct ISAMB_block *new_int (ISAMB b, int cat)
572 return new_block (b, 0, cat);
575 static void check_block (ISAMB b, struct ISAMB_block *p)
577 assert(b); /* mostly to make the compiler shut up about unused b */
585 char *startp = p->bytes;
586 const char *src = startp;
587 char *endp = p->bytes + p->size;
589 void *c1 = (*b->method->codec.start)();
591 decode_ptr(&src, &pos);
592 assert ((pos&CAT_MASK) == p->cat);
596 char file_item_buf[DST_ITEM_MAX];
597 char *file_item = file_item_buf;
598 (*b->method->codec.reset)(c1);
599 (*b->method->codec.decode)(c1, &file_item, &src);
602 decode_item_len(&src, &item_len);
603 assert (item_len > 0 && item_len < 80);
606 decode_ptr(&src, &pos);
607 if ((pos&CAT_MASK) != p->cat)
609 assert ((pos&CAT_MASK) == p->cat);
612 (*b->method->codec.stop)(c1);
616 void close_block(ISAMB b, struct ISAMB_block *p)
622 yaz_log(b->log_freelist, "release block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT,
623 p->pos, p->cat, p->pos/CAT_MAX);
624 memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(zint));
625 b->file[p->cat].head.free_list = p->pos;
626 if (!cache_block (b, p->pos, p->buf, 1))
628 yaz_log(b->log_io, "bf_write: close_block (deleted)");
629 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
634 int offset = b->file[p->cat].head.block_offset;
635 int size = p->size + offset;
636 char *dst = (char*)p->buf + 3;
637 assert (p->size >= 0);
639 /* memset becuase encode_ptr usually does not write all bytes */
640 memset(p->buf, 0, b->file[p->cat].head.block_offset);
642 p->buf[1] = size & 255;
643 p->buf[2] = size >> 8;
644 encode_ptr(&dst, p->no_items);
646 if (!cache_block (b, p->pos, p->buf, 1))
648 yaz_log(b->log_io, "bf_write: close_block");
649 bf_write(b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
652 (*b->method->codec.stop)(p->decodeClientData);
657 int insert_sub (ISAMB b, struct ISAMB_block **p,
658 void *new_item, int *mode,
660 struct ISAMB_block **sp,
661 void *sub_item, int *sub_size,
662 const void *max_item);
664 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
666 ISAMC_I *stream, struct ISAMB_block **sp,
667 void *split_item, int *split_size, const void *last_max_item)
669 char *startp = p->bytes;
670 const char *src = startp;
671 char *endp = p->bytes + p->size;
673 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
674 char sub_item[DST_ITEM_MAX];
678 void *c1 = (*b->method->codec.start)();
682 assert(p->size >= 0);
683 decode_ptr(&src, &pos);
687 const char *src0 = src;
689 char file_item_buf[DST_ITEM_MAX];
690 char *file_item = file_item_buf;
691 (*b->method->codec.reset)(c1);
692 (*b->method->codec.decode)(c1, &file_item, &src);
693 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
696 sub_p1 = open_block(b, pos);
698 diff_terms -= sub_p1->no_items;
699 more = insert_sub (b, &sub_p1, lookahead_item, mode,
701 sub_item, &sub_size, file_item_buf);
702 diff_terms += sub_p1->no_items;
708 decode_item_len(&src, &item_len);
709 d = (*b->method->compare_item)(src, lookahead_item);
712 sub_p1 = open_block(b, pos);
714 diff_terms -= sub_p1->no_items;
715 more = insert_sub (b, &sub_p1, lookahead_item, mode,
717 sub_item, &sub_size, src);
718 diff_terms += sub_p1->no_items;
724 decode_ptr(&src, &pos);
728 /* we reached the end. So lookahead > last item */
729 sub_p1 = open_block(b, pos);
731 diff_terms -= sub_p1->no_items;
732 more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
733 sub_item, &sub_size, last_max_item);
734 diff_terms += sub_p1->no_items;
737 diff_terms += sub_p2->no_items;
741 p->no_items += diff_terms;
745 /* there was a split - must insert pointer in this one */
746 char dst_buf[DST_BUF_SIZE];
749 const char *sub_item_ptr = sub_item;
751 assert (sub_size < 80 && sub_size > 1);
753 memcpy (dst, startp, src - startp);
758 (*b->method->codec.reset)(c1);
759 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
761 encode_item_len (&dst, sub_size); /* sub length and item */
762 memcpy (dst, sub_item, sub_size);
766 encode_ptr(&dst, sub_p2->pos); /* pos */
768 if (endp - src) /* remaining data */
770 memcpy (dst, src, endp - src);
773 p->size = dst - dst_buf;
774 assert (p->size >= 0);
776 if (p->size <= b->file[p->cat].head.block_max)
778 /* it fits OK in this block */
779 memcpy (startp, dst_buf, dst - dst_buf);
781 close_block(b, sub_p2);
785 /* must split _this_ block as well .. */
786 struct ISAMB_block *sub_p3;
788 char file_item_buf[DST_ITEM_MAX];
789 char *file_item = file_item_buf;
793 zint no_items_first_half = 0;
799 b->number_of_int_splits++;
802 close_block(b, sub_p2);
804 half = src + b->file[p->cat].head.block_size/2;
805 decode_ptr(&src, &pos);
807 if (b->enable_int_count)
809 /* read sub block so we can get no_items for it */
810 sub_p3 = open_block(b, pos);
811 no_items_first_half += sub_p3->no_items;
812 close_block(b, sub_p3);
818 file_item = file_item_buf;
819 (*b->method->codec.reset)(c1);
820 (*b->method->codec.decode)(c1, &file_item, &src);
822 decode_item_len(&src, &split_size_tmp);
823 *split_size = (int) split_size_tmp;
826 decode_ptr(&src, &pos);
828 if (b->enable_int_count)
830 /* read sub block so we can get no_items for it */
831 sub_p3 = open_block(b, pos);
832 no_items_first_half += sub_p3->no_items;
833 close_block(b, sub_p3);
836 /* p is first half */
837 p_new_size = src - dst_buf;
838 memcpy (p->bytes, dst_buf, p_new_size);
841 file_item = file_item_buf;
842 (*b->method->codec.reset)(c1);
843 (*b->method->codec.decode)(c1, &file_item, &src);
844 *split_size = file_item - file_item_buf;
845 memcpy(split_item, file_item_buf, *split_size);
847 decode_item_len(&src, &split_size_tmp);
848 *split_size = (int) split_size_tmp;
849 memcpy (split_item, src, *split_size);
852 /* *sp is second half */
853 *sp = new_int (b, p->cat);
854 (*sp)->size = endp - src;
855 memcpy ((*sp)->bytes, src, (*sp)->size);
857 p->size = p_new_size;
859 /* adjust no_items in first&second half */
860 (*sp)->no_items = p->no_items - no_items_first_half;
861 p->no_items = no_items_first_half;
865 close_block(b, sub_p1);
866 (*b->method->codec.stop)(c1);
870 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
871 int *lookahead_mode, ISAMC_I *stream,
872 struct ISAMB_block **sp2,
873 void *sub_item, int *sub_size,
874 const void *max_item)
876 struct ISAMB_block *p = *sp1;
879 char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
881 void *c1 = (*b->method->codec.start)();
882 void *c2 = (*b->method->codec.start)();
884 int quater = b->file[b->no_cat-1].head.block_max / 4;
885 char *mid_cut = dst_buf + quater * 2;
886 char *tail_cut = dst_buf + quater * 3;
887 char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
890 char cut_item_buf[DST_ITEM_MAX];
891 int cut_item_size = 0;
892 int no_items = 0; /* number of items (total) */
893 int no_items_1 = 0; /* number of items (first half) */
894 int inserted_dst_bytes = 0;
898 char file_item_buf[DST_ITEM_MAX];
899 char *file_item = file_item_buf;
902 endp = p->bytes + p->size;
903 (*b->method->codec.decode)(c1, &file_item, &src);
906 const char *dst_item = 0; /* resulting item to be inserted */
907 char *lookahead_next;
912 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
914 /* d now holds comparison between existing file item and
917 d > 0: lookahead before file
918 d < 0: lookahead after file
922 /* lookahead must be inserted */
923 dst_item = lookahead_item;
924 /* if this is not an insertion, it's really bad .. */
925 if (!*lookahead_mode)
927 yaz_log(YLOG_WARN, "isamb: Inconsistent register (1)");
928 assert(*lookahead_mode);
932 dst_item = file_item_buf;
934 if (!*lookahead_mode && d == 0)
936 /* it's a deletion and they match so there is nothing to be
937 inserted anyway .. But mark the thing bad (file item
938 was part of input.. The item will not be part of output */
941 else if (!half1 && dst > mid_cut)
943 /* we have reached the splitting point for the first time */
944 const char *dst_item_0 = dst_item;
945 half1 = dst; /* candidate for splitting */
947 /* encode the resulting item */
948 (*b->method->codec.encode)(c2, &dst, &dst_item);
950 cut_item_size = dst_item - dst_item_0;
951 assert(cut_item_size > 0);
952 memcpy (cut_item_buf, dst_item_0, cut_item_size);
955 no_items_1 = no_items;
960 /* encode the resulting item */
961 (*b->method->codec.encode)(c2, &dst, &dst_item);
965 /* now move "pointers" .. result has been encoded .. */
968 /* we must move the lookahead pointer */
970 inserted_dst_bytes += (dst - dst_0);
971 if (inserted_dst_bytes >= quater)
972 /* no more room. Mark lookahead as "gone".. */
976 /* move it really.. */
977 lookahead_next = lookahead_item;
978 if (!(*stream->read_item)(stream->clientData,
982 /* end of stream reached: no "more" and no lookahead */
986 if (lookahead_item && max_item &&
987 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
989 /* the lookahead goes beyond what we allow in this
990 leaf. Mark it as "gone" */
999 /* exact match .. move both pointers */
1001 lookahead_next = lookahead_item;
1002 if (!(*stream->read_item)(stream->clientData,
1003 &lookahead_next, lookahead_mode))
1009 break; /* end of file stream reached .. */
1010 file_item = file_item_buf; /* move file pointer */
1011 (*b->method->codec.decode)(c1, &file_item, &src);
1015 /* file pointer must be moved */
1018 file_item = file_item_buf;
1019 (*b->method->codec.decode)(c1, &file_item, &src);
1024 /* this loop runs when we are "appending" to a leaf page. That is
1025 either it's empty (new) or all file items have been read in
1028 maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
1029 while (lookahead_item)
1032 const char *src = lookahead_item;
1035 /* if we have a lookahead item, we stop if we exceed the value of it */
1037 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
1039 /* stop if we have reached the value of max item */
1042 if (!*lookahead_mode)
1044 /* this is append. So a delete is bad */
1045 yaz_log(YLOG_WARN, "isamb: Inconsistent register (2)");
1046 assert(*lookahead_mode);
1048 else if (!half1 && dst > tail_cut)
1050 const char *src_0 = src;
1051 half1 = dst; /* candidate for splitting */
1053 (*b->method->codec.encode)(c2, &dst, &src);
1055 cut_item_size = src - src_0;
1056 assert(cut_item_size > 0);
1057 memcpy (cut_item_buf, src_0, cut_item_size);
1059 no_items_1 = no_items;
1063 (*b->method->codec.encode)(c2, &dst, &src);
1073 dst_item = lookahead_item;
1074 if (!(*stream->read_item)(stream->clientData, &dst_item,
1081 new_size = dst - dst_buf;
1082 if (p && p->cat != b->no_cat-1 &&
1083 new_size > b->file[p->cat].head.block_max)
1085 /* non-btree block will be removed */
1088 /* delete it too!! */
1089 p = 0; /* make a new one anyway */
1092 { /* must create a new one */
1094 for (i = 0; i < b->no_cat; i++)
1095 if (new_size <= b->file[i].head.block_max)
1099 p = new_leaf (b, i);
1101 if (new_size > b->file[p->cat].head.block_max)
1104 const char *cut_item = cut_item_buf;
1109 assert(cut_item_size > 0);
1112 p->size = half1 - dst_buf;
1113 assert(p->size <= b->file[p->cat].head.block_max);
1114 memcpy (p->bytes, dst_buf, half1 - dst_buf);
1115 p->no_items = no_items_1;
1118 *sp2 = new_leaf (b, p->cat);
1120 (*b->method->codec.reset)(c2);
1122 b->number_of_leaf_splits++;
1124 first_dst = (*sp2)->bytes;
1126 (*b->method->codec.encode)(c2, &first_dst, &cut_item);
1128 memcpy (first_dst, half2, dst - half2);
1130 (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
1131 assert((*sp2)->size <= b->file[p->cat].head.block_max);
1132 (*sp2)->no_items = no_items - no_items_1;
1135 memcpy (sub_item, cut_item_buf, cut_item_size);
1136 *sub_size = cut_item_size;
1140 memcpy (p->bytes, dst_buf, dst - dst_buf);
1142 p->no_items = no_items;
1144 (*b->method->codec.stop)(c1);
1145 (*b->method->codec.stop)(c2);
1150 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1153 struct ISAMB_block **sp,
1154 void *sub_item, int *sub_size,
1155 const void *max_item)
1157 if (!*p || (*p)->leaf)
1158 return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1159 sub_size, max_item);
1161 return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1162 sub_size, max_item);
1165 int isamb_unlink (ISAMB b, ISAM_P pos)
1167 struct ISAMB_block *p1;
1171 p1 = open_block(b, pos);
1176 const char *src = p1->bytes + p1->offset;
1178 void *c1 = (*b->method->codec.start)();
1180 decode_ptr(&src, &sub_p);
1181 isamb_unlink(b, sub_p);
1183 while (src != p1->bytes + p1->size)
1186 char file_item_buf[DST_ITEM_MAX];
1187 char *file_item = file_item_buf;
1188 (*b->method->codec.reset)(c1);
1189 (*b->method->codec.decode)(c1, &file_item, &src);
1192 decode_item_len(&src, &item_len);
1195 decode_ptr(&src, &sub_p);
1196 isamb_unlink(b, sub_p);
1199 (*b->method->codec.stop)(c1);
1206 void isamb_merge(ISAMB b, ISAM_P *pos, ISAMC_I *stream)
1208 char item_buf[DST_ITEM_MAX];
1212 int must_delete = 0;
1219 item_ptr = item_buf;
1221 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1226 item_ptr = item_buf;
1227 more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1230 struct ISAMB_block *p = 0, *sp = 0;
1231 char sub_item[DST_ITEM_MAX];
1235 p = open_block(b, *pos);
1236 more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1237 sub_item, &sub_size, 0);
1239 { /* increase level of tree by one */
1240 struct ISAMB_block *p2 = new_int (b, p->cat);
1241 char *dst = p2->bytes + p2->size;
1243 void *c1 = (*b->method->codec.start)();
1244 const char *sub_item_ptr = sub_item;
1247 encode_ptr(&dst, p->pos);
1248 assert (sub_size < 80 && sub_size > 1);
1250 (*b->method->codec.reset)(c1);
1251 (*b->method->codec.encode)(c1, &dst, &sub_item_ptr);
1253 encode_item_len (&dst, sub_size);
1254 memcpy (dst, sub_item, sub_size);
1257 encode_ptr(&dst, sp->pos);
1259 p2->size = dst - p2->bytes;
1260 p2->no_items = p->no_items + sp->no_items;
1261 *pos = p2->pos; /* return new super page */
1265 (*b->method->codec.stop)(c1);
1270 *pos = p->pos; /* return current one (again) */
1272 if (p->no_items == 0)
1280 isamb_unlink(b, *pos);
1285 ISAMB_PP isamb_pp_open_x(ISAMB isamb, ISAM_P pos, int *level, int scope)
1287 ISAMB_PP pp = xmalloc(sizeof(*pp));
1293 pp->block = xmalloc(ISAMB_MAX_LEVEL * sizeof(*pp->block));
1300 pp->skipped_numbers = 0;
1301 pp->returned_numbers = 0;
1303 for (i = 0; i<ISAMB_MAX_LEVEL; i++)
1304 pp->skipped_nodes[i] = pp->accessed_nodes[i] = 0;
1307 struct ISAMB_block *p = open_block(isamb, pos);
1308 const char *src = p->bytes + p->offset;
1309 pp->block[pp->level] = p;
1311 pp->total_size += p->size;
1315 decode_ptr(&src, &pos);
1316 p->offset = src - p->bytes;
1318 pp->accessed_nodes[pp->level]++;
1320 pp->block[pp->level+1] = 0;
1321 pp->maxlevel = pp->level;
1327 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAM_P pos, int scope)
1329 return isamb_pp_open_x(isamb, pos, 0, scope);
1332 void isamb_pp_close_x(ISAMB_PP pp, zint *size, zint *blocks)
1337 yaz_log(YLOG_DEBUG, "isamb_pp_close lev=%d returned "ZINT_FORMAT" values, "
1338 "skipped "ZINT_FORMAT,
1339 pp->maxlevel, pp->skipped_numbers, pp->returned_numbers);
1340 for (i = pp->maxlevel; i>=0; i--)
1341 if (pp->skipped_nodes[i] || pp->accessed_nodes[i])
1342 yaz_log(YLOG_DEBUG, "isamb_pp_close level leaf-%d: "
1343 ZINT_FORMAT" read, "ZINT_FORMAT" skipped", i,
1344 pp->accessed_nodes[i], pp->skipped_nodes[i]);
1345 pp->isamb->skipped_numbers += pp->skipped_numbers;
1346 pp->isamb->returned_numbers += pp->returned_numbers;
1347 for (i = pp->maxlevel; i>=0; i--)
1349 pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1350 pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1353 *size = pp->total_size;
1355 *blocks = pp->no_blocks;
1356 for (i = 0; i <= pp->level; i++)
1357 close_block(pp->isamb, pp->block[i]);
1362 int isamb_block_info (ISAMB isamb, int cat)
1364 if (cat >= 0 && cat < isamb->no_cat)
1365 return isamb->file[cat].head.block_size;
1369 void isamb_pp_close (ISAMB_PP pp)
1371 isamb_pp_close_x(pp, 0, 0);
1374 /* simple recursive dumper .. */
1375 static void isamb_dump_r (ISAMB b, ISAM_P pos, void (*pr)(const char *str),
1379 char prefix_str[1024];
1382 struct ISAMB_block *p = open_block(b, pos);
1383 sprintf(prefix_str, "%*s " ZINT_FORMAT " cat=%d size=%d max=%d items="
1384 ZINT_FORMAT, level*2, "",
1385 pos, p->cat, p->size, b->file[p->cat].head.block_max,
1388 sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1391 while (p->offset < p->size)
1393 const char *src = p->bytes + p->offset;
1395 (*b->method->codec.decode)(p->decodeClientData, &dst, &src);
1396 (*b->method->log_item)(YLOG_DEBUG, buf, prefix_str);
1397 p->offset = src - (char*) p->bytes;
1399 assert(p->offset == p->size);
1403 const char *src = p->bytes + p->offset;
1406 decode_ptr(&src, &sub);
1407 p->offset = src - (char*) p->bytes;
1409 isamb_dump_r(b, sub, pr, level+1);
1411 while (p->offset < p->size)
1414 char file_item_buf[DST_ITEM_MAX];
1415 char *file_item = file_item_buf;
1416 void *c1 = (*b->method->codec.start)();
1417 (*b->method->codec.decode)(c1, &file_item, &src);
1418 (*b->method->codec.stop)(c1);
1419 (*b->method->log_item)(YLOG_DEBUG, file_item_buf, prefix_str);
1422 decode_item_len(&src, &item_len);
1423 (*b->method->log_item)(YLOG_DEBUG, src, prefix_str);
1426 decode_ptr(&src, &sub);
1428 p->offset = src - (char*) p->bytes;
1430 isamb_dump_r(b, sub, pr, level+1);
1437 void isamb_dump(ISAMB b, ISAM_P pos, void (*pr)(const char *str))
1439 isamb_dump_r(b, pos, pr, 0);
1442 int isamb_pp_read(ISAMB_PP pp, void *buf)
1444 return isamb_pp_forward(pp, buf, 0);
1448 static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
1449 { /* looks one node higher to see if we should be on this node at all */
1450 /* useful in backing off quickly, and in avoiding tail descends */
1451 /* call with pp->level to begin with */
1452 struct ISAMB_block *p;
1455 ISAMB b = pp->isamb;
1461 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true for root");
1463 return 1; /* we can never skip the root node */
1466 p = pp->block[level];
1467 assert(p->offset <= p->size);
1468 if (p->offset < p->size)
1471 char file_item_buf[DST_ITEM_MAX];
1472 char *file_item = file_item_buf;
1473 void *c1 = (*b->method->codec.start)();
1474 assert(p->offset > 0);
1475 src = p->bytes + p->offset;
1476 (*b->method->codec.decode)(c1, &file_item, &src);
1477 (*b->method->codec.stop)(c1);
1478 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1481 assert(p->offset > 0);
1482 src = p->bytes + p->offset;
1483 decode_item_len(&src, &item_len);
1485 (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until");
1486 (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value");
1488 cmp = (*b->method->compare_item)(untilbuf, src);
1490 if (cmp < pp->scope)
1493 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true "
1494 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1501 yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false "
1502 "cmp=%d lev=%d ofs=%d", cmp, level, p->offset);
1509 yaz_log(YLOG_DEBUG, "isamb_pp_on_right at tail, looking higher "
1512 return isamb_pp_on_right_node(pp, level, untilbuf);
1514 } /* isamb_pp_on_right_node */
1516 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1518 /* reads the next item on the current leaf, returns 0 if end of leaf*/
1519 struct ISAMB_block *p = pp->block[pp->level];
1524 if (p->offset == p->size)
1527 yaz_log(YLOG_DEBUG, "isamb_pp_read_on_leaf returning 0 on "
1530 return 0; /* at end of leaf */
1532 src = p->bytes + p->offset;
1534 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1535 p->offset = src - (char*) p->bytes;
1537 (*pp->isamb->method->codec.log_item)(YLOG_DEBUG, buf,
1538 "read_on_leaf returning 1");
1540 pp->returned_numbers++;
1542 } /* read_on_leaf */
1544 static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
1545 { /* forwards on the current leaf, returns 0 if not found */
1550 if (!isamb_pp_read_on_leaf(pp, buf))
1552 /* FIXME - this is an extra function call, inline the read? */
1553 cmp=(*pp->isamb->method->compare_item)(untilbuf, buf);
1555 { /* cmp<2 found a good one */
1558 yaz_log(YLOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items", skips);
1560 pp->returned_numbers++;
1564 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1565 return 0; /* never mind the rest of this leaf */
1566 pp->skipped_numbers++;
1569 } /* forward_on_leaf */
1571 static int isamb_pp_climb_level(ISAMB_PP pp, ISAM_P *pos)
1572 { /* climbs higher in the tree, until finds a level with data left */
1573 /* returns the node to (consider to) descend to in *pos) */
1574 struct ISAMB_block *p = pp->block[pp->level];
1577 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level starting "
1578 "at level %d node %d ofs=%d sz=%d",
1579 pp->level, p->pos, p->offset, p->size);
1581 assert(pp->level >= 0);
1582 assert(p->offset <= p->size);
1586 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level returning 0 at root");
1590 assert(pp->level>0);
1591 close_block(pp->isamb, pp->block[pp->level]);
1592 pp->block[pp->level] = 0;
1594 p = pp->block[pp->level];
1596 yaz_log(YLOG_DEBUG, "isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1597 pp->level, p->pos, p->offset);
1600 assert(p->offset <= p->size);
1601 if (p->offset == p->size)
1603 /* we came from the last pointer, climb on */
1604 if (!isamb_pp_climb_level(pp, pos))
1606 p = pp->block[pp->level];
1611 char file_item_buf[DST_ITEM_MAX];
1612 char *file_item = file_item_buf;
1613 ISAMB b = pp->isamb;
1614 void *c1 = (*b->method->codec.start)();
1618 /* skip the child we just came from */
1620 yaz_log(YLOG_DEBUG, "isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1621 pp->level, p->offset, p->size);
1623 assert (p->offset < p->size);
1624 src = p->bytes + p->offset;
1626 (*b->method->codec.decode)(c1, &file_item, &src);
1627 (*b->method->codec.stop)(c1);
1629 decode_item_len(&src, &item_len);
1632 decode_ptr(&src, pos);
1633 p->offset = src - (char *)p->bytes;
1640 static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
1641 { /* scans a upper node until it finds a child <= untilbuf */
1642 /* pp points to the key value, as always. pos is the child read from */
1644 /* if all values are too small, returns the last child in the node */
1645 /* FIXME - this can be detected, and avoided by looking at the */
1646 /* parent node, but that gets messy. Presumably the cost is */
1647 /* pretty low anyway */
1648 ISAMB b = pp->isamb;
1649 struct ISAMB_block *p = pp->block[pp->level];
1650 const char *src = p->bytes + p->offset;
1655 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode starting "
1656 "at level %d node %d ofs=%di sz=%d",
1657 pp->level, p->pos, p->offset, p->size);
1660 assert(p->offset <= p->size);
1661 if (p->offset == p->size)
1664 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at end "
1665 "at level %d node %d ofs=%di sz=%d",
1666 pp->level, p->pos, p->offset, p->size);
1668 return pos; /* already at the end of it */
1670 while(p->offset < p->size)
1673 char file_item_buf[DST_ITEM_MAX];
1674 char *file_item = file_item_buf;
1675 void *c1 = (*b->method->codec.start)();
1676 (*b->method->codec.decode)(c1, &file_item, &src);
1677 (*b->method->codec.stop)(c1);
1678 cmp = (*b->method->compare_item)(untilbuf, file_item_buf);
1681 decode_item_len(&src, &item_len);
1682 cmp = (*b->method->compare_item)(untilbuf, src);
1685 decode_ptr(&src, &nxtpos);
1686 if (cmp<pp->scope) /* cmp<2 */
1689 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning a hit "
1690 "at level %d node %d ofs=%d sz=%d",
1691 pp->level, p->pos, p->offset, p->size);
1696 p->offset = src-(char*)p->bytes;
1697 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1703 yaz_log(YLOG_DEBUG, "isamb_pp_forward_unode returning at tail "
1704 "at level %d node %d ofs=%d sz=%d skips=%d",
1705 pp->level, p->pos, p->offset, p->size, skips);
1707 return pos; /* that's the last one in the line */
1709 } /* forward_unode */
1711 static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAM_P pos,
1712 const void *untilbuf)
1713 { /* climbs down the tree, from pos, to the leftmost leaf */
1714 struct ISAMB_block *p = pp->block[pp->level];
1718 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1719 "starting at lev %d node %d ofs=%d lf=%d u=%p",
1720 pp->level, p->pos, p->offset, p->leaf, untilbuf);
1723 pos = isamb_pp_forward_unode(pp, pos, untilbuf);
1726 p = open_block(pp->isamb, pos);
1727 pp->block[pp->level] = p;
1728 ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
1731 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1732 "got lev %d node %d lf=%d",
1733 pp->level, p->pos, p->leaf);
1737 assert (p->offset==0);
1738 src = p->bytes + p->offset;
1739 decode_ptr(&src, &pos);
1740 p->offset = src-(char*)p->bytes;
1741 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1743 yaz_log(YLOG_DEBUG, "isamb_pp_descend_to_leaf "
1744 "returning at lev %d node %d ofs=%d lf=%d",
1745 pp->level, p->pos, p->offset, p->leaf);
1747 } /* descend_to_leaf */
1749 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1750 { /* finds the next leaf by climbing up and down */
1752 if (!isamb_pp_climb_level(pp, &pos))
1754 isamb_pp_descend_to_leaf(pp, pos, 0);
1758 static int isamb_pp_climb_desc(ISAMB_PP pp, const void *untilbuf)
1759 { /* climbs up and descends to a leaf where values >= *untilbuf are found */
1762 struct ISAMB_block *p = pp->block[pp->level];
1763 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc starting "
1764 "at level %d node %d ofs=%d sz=%d",
1765 pp->level, p->pos, p->offset, p->size);
1767 if (!isamb_pp_climb_level(pp, &pos))
1769 /* see if it would pay to climb one higher */
1770 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1771 if (!isamb_pp_climb_level(pp, &pos))
1773 isamb_pp_descend_to_leaf(pp, pos, untilbuf);
1775 p = pp->block[pp->level];
1776 yaz_log(YLOG_DEBUG, "isamb_pp_climb_desc done "
1777 "at level %d node %d ofs=%d sz=%d",
1778 pp->level, p->pos, p->offset, p->size);
1783 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1786 struct ISAMB_block *p = pp->block[pp->level];
1788 yaz_log(YLOG_DEBUG, "isamb_pp_forward starting "
1789 "at level %d node %d ofs=%d sz=%d u=%p sc=%d",
1790 pp->level, p->pos, p->offset, p->size, untilbuf, scope);
1794 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1797 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (A) "
1798 "at level %d node %d ofs=%d sz=%d",
1799 pp->level, p->pos, p->offset, p->size);
1803 if (! isamb_pp_climb_desc(pp, untilbuf))
1806 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning notfound (B) "
1807 "at level %d node %d ofs=%d sz=%d",
1808 pp->level, p->pos, p->offset, p->size);
1810 return 0; /* could not find a leaf */
1813 if (isamb_pp_forward_on_leaf(pp, buf, untilbuf))
1816 yaz_log(YLOG_DEBUG, "isamb_pp_forward (f) returning (c) "
1817 "at level %d node %d ofs=%d sz=%d",
1818 pp->level, p->pos, p->offset, p->size);
1822 } while (isamb_pp_find_next_leaf(pp));
1823 return 0; /* could not find at all */
1825 else { /* no untilbuf, a straight read */
1826 /* FIXME - this should be moved
1827 * directly into the pp_read */
1828 /* keeping here now, to keep same
1829 * interface as the old fwd */
1830 if (isamb_pp_read_on_leaf(pp, buf))
1833 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (D) "
1834 "at level %d node %d ofs=%d sz=%d",
1835 pp->level, p->pos, p->offset, p->size);
1839 if (isamb_pp_find_next_leaf(pp))
1842 yaz_log(YLOG_DEBUG, "isamb_pp_forward (read) returning (E) "
1843 "at level %d node %d ofs=%d sz=%d",
1844 pp->level, p->pos, p->offset, p->size);
1846 return isamb_pp_read_on_leaf(pp, buf);
1851 } /* isam_pp_forward (new version) */
1853 void isamb_pp_pos(ISAMB_PP pp, double *current, double *total)
1854 { /* return an estimate of the current position and of the total number of */
1855 /* occureences in the isam tree, based on the current leaf */
1859 /* if end-of-stream PP may not be leaf */
1861 *total = (double) (pp->block[0]->no_items);
1862 *current = (double) pp->returned_numbers;
1864 yaz_log(YLOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
1865 ZINT_FORMAT, *current, *total, pp->returned_numbers);
1869 int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb)
1873 struct ISAMB_block *p = pp->block[pp->level];
1874 ISAMB b = pp->isamb;
1878 while (p->offset == p->size)
1884 char file_item_buf[DST_ITEM_MAX];
1885 char *file_item = file_item_buf;
1889 while (p->offset == p->size)
1893 close_block (pp->isamb, pp->block[pp->level]);
1894 pp->block[pp->level] = 0;
1896 p = pp->block[pp->level];
1901 src = p->bytes + p->offset;
1904 c1 = (*b->method->codec.start)();
1905 (*b->method->codec.decode)(c1, &file_item, &src);
1907 decode_ptr (&src, &item_len);
1910 decode_ptr (&src, &pos);
1911 p->offset = src - (char*) p->bytes;
1913 src = p->bytes + p->offset;
1917 if (!untilb || p->offset == p->size)
1919 assert(p->offset < p->size);
1922 file_item = file_item_buf;
1923 (*b->method->codec.reset)(c1);
1924 (*b->method->codec.decode)(c1, &file_item, &src);
1925 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
1931 decode_item_len(&src, &item_len);
1932 if ((*b->method->compare_item)(untilb, src) <= 1)
1936 decode_ptr (&src, &pos);
1937 p->offset = src - (char*) p->bytes;
1944 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1946 pp->total_size += p->size;
1954 src = p->bytes + p->offset;
1957 decode_ptr (&src, &pos);
1958 p->offset = src - (char*) p->bytes;
1960 if (!untilb || p->offset == p->size)
1962 assert(p->offset < p->size);
1965 file_item = file_item_buf;
1966 (*b->method->codec.reset)(c1);
1967 (*b->method->codec.decode)(c1, &file_item, &src);
1968 if ((*b->method->compare_item)(untilb, file_item_buf) <= 1)
1974 decode_ptr (&src, &item_len);
1975 if ((*b->method->compare_item)(untilb, src) <= 1)
1983 (*b->method->codec.stop)(c1);
1986 assert (p->offset < p->size);
1991 src = p->bytes + p->offset;
1992 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1993 p->offset = src - (char*) p->bytes;
1994 if (!untilb || (*pp->isamb->method->compare_item)(untilb, dst0) <= 1)
1997 if (p->offset == p->size) goto again;
2002 zint isamb_get_int_splits(ISAMB b)
2004 return b->number_of_int_splits;
2007 zint isamb_get_leaf_splits(ISAMB b)
2009 return b->number_of_leaf_splits;
2015 * indent-tabs-mode: nil
2017 * vim: shiftwidth=4 tabstop=8 expandtab