1 /* $Id: isamb.c,v 1.56 2004-08-23 13:06:46 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
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 Zebra; see the file LICENSE.zebra. If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include <yaz/xmalloc.h>
33 #define ISAMB_MAJOR_VERSION 2
34 #define ISAMB_MINOR_VERSION 0
46 /* maximum size of encoded buffer */
47 #define DST_ITEM_MAX 256
49 #define ISAMB_MAX_LEVEL 10
50 /* approx 2*max page + max size of item */
51 #define DST_BUF_SIZE 16840
53 #define ISAMB_CACHE_ENTRY_SIZE 4096
55 /* CAT_MAX: _must_ be power of 2 */
57 #define CAT_MASK (CAT_MAX-1)
58 /* CAT_NO: <= CAT_MAX */
61 /* ISAMB_PTR_CODEC=1 var, =0 fixed */
62 #define ISAMB_PTR_CODEC 1
64 struct ISAMB_cache_entry {
69 struct ISAMB_cache_entry *next;
75 struct ISAMB_head head;
76 struct ISAMB_cache_entry *cache_entries;
83 struct ISAMB_file *file;
85 int cache; /* 0=no cache, 1=use cache, -1=dummy isam (for testing only) */
86 int log_io; /* log level for bf_read/bf_write calls */
87 int log_freelist; /* log level for freelist handling */
88 zint skipped_numbers; /* on a leaf node */
89 zint returned_numbers;
90 zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1=higher etc */
91 zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
102 zint no_items; /* number of nodes in this + children */
106 void *decodeClientData;
114 int maxlevel; /* total depth */
117 zint skipped_numbers; /* on a leaf node */
118 zint returned_numbers;
119 zint skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1=higher etc */
120 zint accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */
121 struct ISAMB_block **block;
126 static void encode_ptr (char **dst, zint pos)
128 unsigned char *bp = (unsigned char*) *dst;
132 *bp++ = 128 | (pos & 127);
139 static void encode_ptr (char **dst, zint pos)
141 memcpy(*dst, &pos, sizeof(pos));
142 (*dst) += sizeof(pos);
147 static void decode_ptr (const char **src1, zint *pos)
149 const unsigned char **src = (const unsigned char **) src1;
154 while (((c = *(*src)++) & 128))
156 d += ((zint) (c & 127) << r);
159 d += ((zint) c << r);
163 static void decode_ptr (const char **src, zint *pos)
165 memcpy (pos, *src, sizeof(*pos));
166 (*src) += sizeof(*pos);
170 ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M *method,
173 ISAMB isamb = xmalloc (sizeof(*isamb));
177 isamb->method = (ISAMC_M *) xmalloc (sizeof(*method));
178 memcpy (isamb->method, method, sizeof(*method));
179 isamb->no_cat = CAT_NO;
181 isamb->log_freelist = 0;
182 isamb->cache = cache;
183 isamb->skipped_numbers=0;
184 isamb->returned_numbers=0;
185 for (i=0;i<ISAMB_MAX_LEVEL;i++)
186 isamb->skipped_nodes[i]= isamb->accessed_nodes[i]=0;
189 isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat);
190 for (i = 0; i < isamb->no_cat; i++)
192 char fname[DST_BUF_SIZE];
193 char hbuf[DST_BUF_SIZE];
194 isamb->file[i].cache_entries = 0;
195 isamb->file[i].head_dirty = 0;
196 sprintf (fname, "%s%c", name, i+'A');
198 isamb->file[i].bf = bf_open (bfs, fname, ISAMB_CACHE_ENTRY_SIZE,
201 isamb->file[i].bf = bf_open (bfs, fname, b_size, writeflag);
203 /* fill-in default values (for empty isamb) */
204 isamb->file[i].head.first_block = ISAMB_CACHE_ENTRY_SIZE/b_size+1;
205 isamb->file[i].head.last_block = isamb->file[i].head.first_block;
206 isamb->file[i].head.block_size = b_size;
207 if (i == isamb->no_cat-1 || b_size > 128)
208 isamb->file[i].head.block_offset = 8;
210 isamb->file[i].head.block_offset = 4;
211 isamb->file[i].head.block_max =
212 b_size - isamb->file[i].head.block_offset;
213 isamb->file[i].head.free_list = 0;
214 if (bf_read (isamb->file[i].bf, 0, 0, 0, hbuf))
216 /* got header assume "isamb"major minor len can fit in 16 bytes */
218 int major, minor, len, pos = 0;
221 if (memcmp(hbuf, "isamb", 5))
223 logf(LOG_WARN, "bad isamb header for file %s", fname);
226 if (sscanf(hbuf+5, "%d %d %d", &major, &minor, &len) != 3)
228 logf(LOG_WARN, "bad isamb header for file %s", fname);
231 if (major != ISAMB_MAJOR_VERSION)
233 logf(LOG_WARN, "bad major version for file %s %d, must be %d",
234 fname, major, ISAMB_MAJOR_VERSION);
237 for (left = len - b_size; left > 0; left = left - b_size)
240 if (!bf_read (isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size))
242 logf(LOG_WARN, "truncated isamb header for "
243 "file=%s len=%d pos=%d",
249 decode_ptr(&src, &isamb->file[i].head.first_block);
250 decode_ptr(&src, &isamb->file[i].head.last_block);
251 decode_ptr(&src, &zint_tmp);
252 isamb->file[i].head.block_size = zint_tmp;
253 decode_ptr(&src, &zint_tmp);
254 isamb->file[i].head.block_max = zint_tmp;
255 decode_ptr(&src, &isamb->file[i].head.free_list);
257 assert (isamb->file[i].head.block_size >= isamb->file[i].head.block_offset);
258 isamb->file[i].head_dirty = 0;
259 assert(isamb->file[i].head.block_size == b_size);
263 logf(LOG_WARN, "isamb debug enabled. Things will be slower than usual");
268 static void flush_blocks (ISAMB b, int cat)
270 while (b->file[cat].cache_entries)
272 struct ISAMB_cache_entry *ce_this = b->file[cat].cache_entries;
273 b->file[cat].cache_entries = ce_this->next;
277 yaz_log (b->log_io, "bf_write: flush_blocks");
278 bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
280 xfree (ce_this->buf);
285 static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr)
287 int cat = (int) (pos&CAT_MASK);
288 int off = (int) (((pos/CAT_MAX) &
289 (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1))
290 * b->file[cat].head.block_size);
291 zint norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size);
293 struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0;
298 assert (ISAMB_CACHE_ENTRY_SIZE >= b->file[cat].head.block_size);
299 for (ce = &b->file[cat].cache_entries; *ce; ce = &(*ce)->next, no++)
302 if ((*ce)->pos == norm)
305 *ce = (*ce)->next; /* remove from list */
307 ce_this->next = b->file[cat].cache_entries; /* move to front */
308 b->file[cat].cache_entries = ce_this;
312 memcpy (ce_this->buf + off, userbuf,
313 b->file[cat].head.block_size);
317 memcpy (userbuf, ce_this->buf + off,
318 b->file[cat].head.block_size);
325 assert (ce_last && *ce_last);
327 *ce_last = 0; /* remove the last entry from list */
330 yaz_log (b->log_io, "bf_write: get_block");
331 bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf);
333 xfree (ce_this->buf);
336 ce_this = xmalloc (sizeof(*ce_this));
337 ce_this->next = b->file[cat].cache_entries;
338 b->file[cat].cache_entries = ce_this;
339 ce_this->buf = xmalloc (ISAMB_CACHE_ENTRY_SIZE);
341 yaz_log (b->log_io, "bf_read: get_block");
342 if (!bf_read (b->file[cat].bf, norm, 0, 0, ce_this->buf))
343 memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE);
346 memcpy (ce_this->buf + off, userbuf, b->file[cat].head.block_size);
352 memcpy (userbuf, ce_this->buf + off, b->file[cat].head.block_size);
358 void isamb_close (ISAMB isamb)
361 for (i=0;isamb->accessed_nodes[i];i++)
362 logf(LOG_DEBUG,"isamb_close level leaf-%d: "ZINT_FORMAT" read, "
363 ZINT_FORMAT" skipped",
364 i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]);
365 logf(LOG_DEBUG,"isamb_close returned "ZINT_FORMAT" values, "
366 "skipped "ZINT_FORMAT,
367 isamb->skipped_numbers, isamb->returned_numbers);
368 for (i = 0; i<isamb->no_cat; i++)
370 flush_blocks (isamb, i);
371 if (isamb->file[i].head_dirty)
373 char hbuf[DST_BUF_SIZE];
374 int major = ISAMB_MAJOR_VERSION;
375 int minor = ISAMB_MINOR_VERSION;
377 char *dst = hbuf + 16;
379 int b_size = isamb->file[i].head.block_size;
381 encode_ptr(&dst, isamb->file[i].head.first_block);
382 encode_ptr(&dst, isamb->file[i].head.last_block);
383 encode_ptr(&dst, isamb->file[i].head.block_size);
384 encode_ptr(&dst, isamb->file[i].head.block_max);
385 encode_ptr(&dst, isamb->file[i].head.free_list);
386 memset(dst, '\0', 16); /* ensure no random bytes are written */
390 /* print exactly 16 bytes (including trailing 0) */
391 sprintf(hbuf, "isamb%02d %02d %02d\r\n", major, minor, len);
393 bf_write (isamb->file[i].bf, pos, 0, 0, hbuf);
395 for (left = len - b_size; left > 0; left = left - b_size)
398 bf_write (isamb->file[i].bf, pos, 0, 0, hbuf + pos*b_size);
401 bf_close (isamb->file[i].bf);
404 xfree (isamb->method);
408 /* open_block: read one block at pos.
409 Decode leading sys bytes .. consisting of
411 0: leader byte, != 0 leaf, == 0, non-leaf
412 1-2: used size of block
413 3-7*: number of items and all children
415 * Reserve 5 bytes for large block sizes. 1 for small ones .. Number
416 of items. We can thus have at most 2^40 nodes.
418 static struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos)
420 int cat = (int) (pos&CAT_MASK);
422 int offset = b->file[cat].head.block_offset;
423 struct ISAMB_block *p;
426 p = xmalloc (sizeof(*p));
428 p->cat = (int) (pos & CAT_MASK);
429 p->buf = xmalloc (b->file[cat].head.block_size);
432 if (!get_block (b, pos, p->buf, 0))
434 yaz_log (b->log_io, "bf_read: open_block");
435 if (!bf_read (b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf))
437 yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
438 (long) pos, (long) pos/CAT_MAX);
442 p->bytes = p->buf + offset;
444 p->size = (p->buf[1] + 256 * p->buf[2]) - offset;
447 yaz_log (LOG_FATAL, "Bad block size %d in pos=" ZINT_FORMAT "\n",
450 assert (p->size >= 0);
452 decode_ptr(&src, &p->no_items);
457 p->decodeClientData = (*b->method->codec.start)();
461 struct ISAMB_block *new_block (ISAMB b, int leaf, int cat)
463 struct ISAMB_block *p;
465 p = xmalloc (sizeof(*p));
466 p->buf = xmalloc (b->file[cat].head.block_size);
468 if (!b->file[cat].head.free_list)
471 block_no = b->file[cat].head.last_block++;
472 p->pos = block_no * CAT_MAX + cat;
476 p->pos = b->file[cat].head.free_list;
477 assert((p->pos & CAT_MASK) == cat);
478 if (!get_block (b, p->pos, p->buf, 0))
480 yaz_log (b->log_io, "bf_read: new_block");
481 if (!bf_read (b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf))
483 yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld",
484 (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX);
488 yaz_log (b->log_freelist, "got block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT, p->pos,
489 cat, p->pos/CAT_MAX);
490 memcpy (&b->file[cat].head.free_list, p->buf, sizeof(int));
493 b->file[cat].head_dirty = 1;
494 memset (p->buf, 0, b->file[cat].head.block_size);
495 p->bytes = p->buf + b->file[cat].head.block_offset;
502 p->decodeClientData = (*b->method->codec.start)();
506 struct ISAMB_block *new_leaf (ISAMB b, int cat)
508 return new_block (b, 1, cat);
512 struct ISAMB_block *new_int (ISAMB b, int cat)
514 return new_block (b, 0, cat);
517 static void check_block (ISAMB b, struct ISAMB_block *p)
519 assert(b); /* mostly to make the compiler shut up about unused b */
527 char *startp = p->bytes;
528 const char *src = startp;
529 char *endp = p->bytes + p->size;
532 decode_ptr (&src, &pos);
533 assert ((pos&CAT_MASK) == p->cat);
537 decode_ptr (&src, &item_len);
538 assert (item_len > 0 && item_len < 80);
540 decode_ptr (&src, &pos);
541 if ((pos&CAT_MASK) != p->cat)
543 assert ((pos&CAT_MASK) == p->cat);
549 void close_block (ISAMB b, struct ISAMB_block *p)
555 yaz_log (b->log_freelist, "release block " ZINT_FORMAT " from freelist %d:" ZINT_FORMAT,
556 p->pos, p->cat, p->pos/CAT_MAX);
557 memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(int));
558 b->file[p->cat].head.free_list = p->pos;
559 if (!get_block (b, p->pos, p->buf, 1))
561 yaz_log (b->log_io, "bf_write: close_block (deleted)");
562 bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
567 int offset = b->file[p->cat].head.block_offset;
568 int size = p->size + offset;
569 char *dst = p->buf + 3;
570 assert (p->size >= 0);
572 /* memset becuase encode_ptr usually does not write all bytes */
573 memset(p->buf, 0, b->file[p->cat].head.block_offset);
575 p->buf[1] = size & 255;
576 p->buf[2] = size >> 8;
577 encode_ptr(&dst, p->no_items);
579 if (!get_block (b, p->pos, p->buf, 1))
581 yaz_log (b->log_io, "bf_write: close_block");
582 bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf);
585 (*b->method->codec.stop)(p->decodeClientData);
590 int insert_sub (ISAMB b, struct ISAMB_block **p,
591 void *new_item, int *mode,
593 struct ISAMB_block **sp,
594 void *sub_item, int *sub_size,
595 const void *max_item);
597 int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item,
599 ISAMC_I *stream, struct ISAMB_block **sp,
600 void *split_item, int *split_size, const void *last_max_item)
602 char *startp = p->bytes;
603 const char *src = startp;
604 char *endp = p->bytes + p->size;
606 struct ISAMB_block *sub_p1 = 0, *sub_p2 = 0;
607 char sub_item[DST_ITEM_MAX];
614 assert(p->size >= 0);
615 decode_ptr (&src, &pos);
620 const char *src0 = src;
621 decode_ptr (&src, &item_len);
622 d = (*b->method->compare_item)(src, lookahead_item);
625 sub_p1 = open_block (b, pos);
627 diff_terms -= sub_p1->no_items;
628 more = insert_sub (b, &sub_p1, lookahead_item, mode,
630 sub_item, &sub_size, src);
631 diff_terms += sub_p1->no_items;
636 decode_ptr (&src, &pos);
640 sub_p1 = open_block (b, pos);
642 diff_terms -= sub_p1->no_items;
643 more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2,
644 sub_item, &sub_size, last_max_item);
645 diff_terms += sub_p1->no_items;
648 diff_terms += sub_p2->no_items;
652 p->no_items += diff_terms;
656 /* there was a split - must insert pointer in this one */
657 char dst_buf[DST_BUF_SIZE];
660 assert (sub_size < 80 && sub_size > 1);
662 memcpy (dst, startp, src - startp);
666 encode_ptr (&dst, sub_size); /* sub length and item */
667 memcpy (dst, sub_item, sub_size);
670 encode_ptr (&dst, sub_p2->pos); /* pos */
672 if (endp - src) /* remaining data */
674 memcpy (dst, src, endp - src);
677 p->size = dst - dst_buf;
678 assert (p->size >= 0);
681 if (p->size <= b->file[p->cat].head.block_max)
683 memcpy (startp, dst_buf, dst - dst_buf);
687 struct ISAMB_block *sub_p3;
689 zint no_items_first_half = 0;
695 half = src + b->file[p->cat].head.block_size/2;
696 decode_ptr (&src, &pos);
698 /* read sub block so we can get no_items for it */
699 sub_p3 = open_block(b, pos);
700 no_items_first_half += sub_p3->no_items;
701 close_block(b, sub_p3);
705 decode_ptr (&src, &split_size_tmp);
706 *split_size = (int) split_size_tmp;
709 decode_ptr (&src, &pos);
711 /* read sub block so we can get no_items for it */
712 sub_p3 = open_block(b, pos);
713 no_items_first_half += sub_p3->no_items;
714 close_block(b, sub_p3);
716 /* p is first half */
717 p_new_size = src - dst_buf;
718 memcpy (p->bytes, dst_buf, p_new_size);
720 decode_ptr (&src, &split_size_tmp);
721 *split_size = (int) split_size_tmp;
722 memcpy (split_item, src, *split_size);
725 /* *sp is second half */
726 *sp = new_int (b, p->cat);
727 (*sp)->size = endp - src;
728 memcpy ((*sp)->bytes, src, (*sp)->size);
730 p->size = p_new_size;
732 /* adjust no_items in first&second half */
733 (*sp)->no_items = p->no_items - no_items_first_half;
734 p->no_items = no_items_first_half;
737 close_block (b, sub_p2);
739 close_block (b, sub_p1);
743 int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item,
744 int *lookahead_mode, ISAMC_I *stream,
745 struct ISAMB_block **sp2,
746 void *sub_item, int *sub_size,
747 const void *max_item)
749 struct ISAMB_block *p = *sp1;
752 char dst_buf[DST_BUF_SIZE], *dst = dst_buf;
754 void *c1 = (*b->method->codec.start)();
755 void *c2 = (*b->method->codec.start)();
757 int quater = b->file[b->no_cat-1].head.block_max / 4;
758 char *mid_cut = dst_buf + quater * 2;
759 char *tail_cut = dst_buf + quater * 3;
760 char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max;
763 char cut_item_buf[DST_ITEM_MAX];
764 int cut_item_size = 0;
765 int no_items = 0; /* number of items (total) */
766 int no_items_1 = 0; /* number of items (first half) */
770 char file_item_buf[DST_ITEM_MAX];
771 char *file_item = file_item_buf;
774 endp = p->bytes + p->size;
775 (*b->method->codec.decode)(c1, &file_item, &src);
778 const char *dst_item = 0; /* resulting item to be inserted */
779 char *lookahead_next;
783 d = (*b->method->compare_item)(file_item_buf, lookahead_item);
785 /* d now holds comparison between existing file item and
788 d > 0: lookahead before file
789 d < 0: lookahead after file
793 /* lookahead must be inserted */
794 dst_item = lookahead_item;
795 /* if this is not an insertion, it's really bad .. */
796 if (!*lookahead_mode)
798 yaz_log (LOG_WARN, "isamb: Inconsistent register (1)");
799 assert (*lookahead_mode);
803 dst_item = file_item_buf;
806 if (!*lookahead_mode && d == 0)
808 /* it's a deletion and they match so there is nothing to be
809 inserted anyway .. But mark the thing bad (file item
810 was part of input.. The item will not be part of output */
813 else if (!half1 && dst > mid_cut)
815 /* we have reached the splitting point for the first time */
816 const char *dst_item_0 = dst_item;
817 half1 = dst; /* candidate for splitting */
819 /* encode the resulting item */
820 (*b->method->codec.encode)(c2, &dst, &dst_item);
822 cut_item_size = dst_item - dst_item_0;
823 assert(cut_item_size > 0);
824 memcpy (cut_item_buf, dst_item_0, cut_item_size);
827 no_items_1 = no_items;
832 /* encode the resulting item */
833 (*b->method->codec.encode)(c2, &dst, &dst_item);
837 /* now move "pointers" .. result has been encoded .. */
840 /* we must move the lookahead pointer */
843 /* no more room. Mark lookahead as "gone".. */
847 /* move it really.. */
848 lookahead_next = lookahead_item;
849 if (!(*stream->read_item)(stream->clientData,
853 /* end of stream reached: no "more" and no lookahead */
857 if (lookahead_item && max_item &&
858 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
860 /* the lookahead goes beyond what we allow in this
861 leaf. Mark it as "gone" */
870 /* exact match .. move both pointers */
872 lookahead_next = lookahead_item;
873 if (!(*stream->read_item)(stream->clientData,
874 &lookahead_next, lookahead_mode))
880 break; /* end of file stream reached .. */
881 file_item = file_item_buf; /* move file pointer */
882 (*b->method->codec.decode)(c1, &file_item, &src);
886 /* file pointer must be moved */
889 file_item = file_item_buf;
890 (*b->method->codec.decode)(c1, &file_item, &src);
894 maxp = dst_buf + b->file[b->no_cat-1].head.block_max + quater;
895 /* this loop runs when we are "appending" to a leaf page. That is
896 either it's empty (new) or all file items have been read in
898 while (lookahead_item)
901 const char *src = lookahead_item;
904 /* compare lookahead with max item */
906 (*b->method->compare_item)(max_item, lookahead_item) <= 0)
908 /* stop if we have reached the value of max item */
911 if (!*lookahead_mode)
913 /* this is append. So a delete is bad */
914 yaz_log (LOG_WARN, "isamb: Inconsistent register (2)");
917 else if (!half1 && dst > tail_cut)
919 const char *src_0 = src;
920 half1 = dst; /* candidate for splitting */
922 (*b->method->codec.encode)(c2, &dst, &src);
924 cut_item_size = src - src_0;
925 assert(cut_item_size > 0);
926 memcpy (cut_item_buf, src_0, cut_item_size);
928 no_items_1 = no_items;
932 (*b->method->codec.encode)(c2, &dst, &src);
942 dst_item = lookahead_item;
943 if (!(*stream->read_item)(stream->clientData, &dst_item,
950 new_size = dst - dst_buf;
951 if (p && p->cat != b->no_cat-1 &&
952 new_size > b->file[p->cat].head.block_max)
954 /* non-btree block will be removed */
957 /* delete it too!! */
958 p = 0; /* make a new one anyway */
961 { /* must create a new one */
963 for (i = 0; i < b->no_cat; i++)
964 if (new_size <= b->file[i].head.block_max)
970 if (new_size > b->file[p->cat].head.block_max)
973 const char *cut_item = cut_item_buf;
978 assert(cut_item_size > 0);
981 p->size = half1 - dst_buf;
982 memcpy (p->bytes, dst_buf, half1 - dst_buf);
983 p->no_items = no_items_1;
986 *sp2 = new_leaf (b, p->cat);
988 (*b->method->codec.reset)(c2);
990 first_dst = (*sp2)->bytes;
992 (*b->method->codec.encode)(c2, &first_dst, &cut_item);
994 memcpy (first_dst, half2, dst - half2);
996 (*sp2)->size = (first_dst - (*sp2)->bytes) + (dst - half2);
997 (*sp2)->no_items = no_items - no_items_1;
1000 memcpy (sub_item, cut_item_buf, cut_item_size);
1001 *sub_size = cut_item_size;
1005 memcpy (p->bytes, dst_buf, dst - dst_buf);
1007 p->no_items = no_items;
1009 (*b->method->codec.stop)(c1);
1010 (*b->method->codec.stop)(c2);
1015 int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item,
1018 struct ISAMB_block **sp,
1019 void *sub_item, int *sub_size,
1020 const void *max_item)
1022 if (!*p || (*p)->leaf)
1023 return insert_leaf (b, p, new_item, mode, stream, sp, sub_item,
1024 sub_size, max_item);
1026 return insert_int (b, *p, new_item, mode, stream, sp, sub_item,
1027 sub_size, max_item);
1030 int isamb_unlink (ISAMB b, ISAMC_P pos)
1032 struct ISAMB_block *p1;
1036 p1 = open_block(b, pos);
1042 const char *src = p1->bytes + p1->offset;
1044 decode_ptr(&src, &sub_p);
1045 isamb_unlink(b, sub_p);
1047 while (src != p1->bytes + p1->size)
1049 decode_ptr(&src, &item_len);
1051 decode_ptr(&src, &sub_p);
1052 isamb_unlink(b, sub_p);
1059 ISAMB_P isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I *stream)
1061 char item_buf[DST_ITEM_MAX];
1065 int must_delete = 0;
1072 item_ptr = item_buf;
1074 (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1078 item_ptr = item_buf;
1079 more = (*stream->read_item)(stream->clientData, &item_ptr, &i_mode);
1082 struct ISAMB_block *p = 0, *sp = 0;
1083 char sub_item[DST_ITEM_MAX];
1087 p = open_block (b, pos);
1088 more = insert_sub (b, &p, item_buf, &i_mode, stream, &sp,
1089 sub_item, &sub_size, 0);
1091 { /* increase level of tree by one */
1092 struct ISAMB_block *p2 = new_int (b, p->cat);
1093 char *dst = p2->bytes + p2->size;
1095 encode_ptr (&dst, p->pos);
1096 assert (sub_size < 40);
1097 encode_ptr (&dst, sub_size);
1098 memcpy (dst, sub_item, sub_size);
1100 encode_ptr (&dst, sp->pos);
1102 p2->size = dst - p2->bytes;
1103 p2->no_items = p->no_items + sp->no_items;
1104 pos = p2->pos; /* return new super page */
1105 close_block (b, sp);
1106 close_block (b, p2);
1110 pos = p->pos; /* return current one (again) */
1112 if (p->no_items == 0)
1120 isamb_unlink(b, pos);
1126 ISAMB_PP isamb_pp_open_x (ISAMB isamb, ISAMB_P pos, int *level)
1128 ISAMB_PP pp = xmalloc (sizeof(*pp));
1132 pp->block = xmalloc (ISAMB_MAX_LEVEL * sizeof(*pp->block));
1139 pp->skipped_numbers=0;
1140 pp->returned_numbers=0;
1141 for (i=0;i<ISAMB_MAX_LEVEL;i++)
1142 pp->skipped_nodes[i] = pp->accessed_nodes[i]=0;
1145 struct ISAMB_block *p = open_block (isamb, pos);
1146 const char *src = p->bytes + p->offset;
1147 pp->block[pp->level] = p;
1149 pp->total_size += p->size;
1155 decode_ptr (&src, &pos);
1156 p->offset = src - p->bytes;
1158 pp->accessed_nodes[pp->level]++;
1160 pp->block[pp->level+1] = 0;
1161 pp->maxlevel=pp->level;
1167 ISAMB_PP isamb_pp_open (ISAMB isamb, ISAMB_P pos)
1169 return isamb_pp_open_x (isamb, pos, 0);
1172 void isamb_pp_close_x (ISAMB_PP pp, int *size, int *blocks)
1177 logf(LOG_DEBUG,"isamb_pp_close lev=%d returned "ZINT_FORMAT" values,"
1178 "skipped "ZINT_FORMAT,
1179 pp->maxlevel, pp->skipped_numbers, pp->returned_numbers);
1180 for (i=pp->maxlevel;i>=0;i--)
1181 if ( pp->skipped_nodes[i] || pp->accessed_nodes[i])
1182 logf(LOG_DEBUG,"isamb_pp_close level leaf-%d: "
1183 ZINT_FORMAT" read, "ZINT_FORMAT" skipped", i,
1184 pp->accessed_nodes[i], pp->skipped_nodes[i]);
1185 pp->isamb->skipped_numbers += pp->skipped_numbers;
1186 pp->isamb->returned_numbers += pp->returned_numbers;
1187 for (i=pp->maxlevel;i>=0;i--)
1189 pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i];
1190 pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i];
1193 *size = pp->total_size;
1195 *blocks = pp->no_blocks;
1196 for (i = 0; i <= pp->level; i++)
1197 close_block (pp->isamb, pp->block[i]);
1202 int isamb_block_info (ISAMB isamb, int cat)
1204 if (cat >= 0 && cat < isamb->no_cat)
1205 return isamb->file[cat].head.block_size;
1209 void isamb_pp_close (ISAMB_PP pp)
1211 isamb_pp_close_x (pp, 0, 0);
1214 /* simple recursive dumper .. */
1215 static void isamb_dump_r (ISAMB b, ISAMB_P pos, void (*pr)(const char *str),
1219 char prefix_str[1024];
1222 struct ISAMB_block *p = open_block (b, pos);
1223 sprintf(prefix_str, "%*s " ZINT_FORMAT " cat=%d size=%d max=%d items="
1224 ZINT_FORMAT, level*2, "",
1225 pos, p->cat, p->size, b->file[p->cat].head.block_max,
1228 sprintf(prefix_str, "%*s " ZINT_FORMAT, level*2, "", pos);
1231 while (p->offset < p->size)
1233 const char *src = p->bytes + p->offset;
1235 (*b->method->codec.decode)(p->decodeClientData, &dst, &src);
1236 (*b->method->log_item)(LOG_DEBUG, buf, prefix_str);
1237 p->offset = src - (char*) p->bytes;
1239 assert(p->offset == p->size);
1243 const char *src = p->bytes + p->offset;
1247 decode_ptr (&src, &sub);
1248 p->offset = src - (char*) p->bytes;
1250 isamb_dump_r(b, sub, pr, level+1);
1252 while (p->offset < p->size)
1254 decode_ptr (&src, &item_len);
1255 (*b->method->log_item)(LOG_DEBUG, src, prefix_str);
1257 decode_ptr (&src, &sub);
1259 p->offset = src - (char*) p->bytes;
1261 isamb_dump_r(b, sub, pr, level+1);
1268 void isamb_dump (ISAMB b, ISAMB_P pos, void (*pr)(const char *str))
1270 isamb_dump_r(b, pos, pr, 0);
1274 /* Old isamb_pp_read that Adam wrote, kept as a reference in case we need to
1275 debug the more complex pp_read that also forwards. May be deleted near end
1276 of 2004, if it has not shown to be useful */
1279 int isamb_pp_read (ISAMB_PP pp, void *buf)
1283 struct ISAMB_block *p = pp->block[pp->level];
1287 while (p->offset == p->size)
1290 while (p->offset == p->size)
1294 close_block (pp->isamb, pp->block[pp->level]);
1295 pp->block[pp->level] = 0;
1297 p = pp->block[pp->level];
1300 src = p->bytes + p->offset;
1302 decode_ptr (&src, &item_len);
1304 decode_ptr (&src, &pos);
1306 p->offset = src - (char*) p->bytes;
1312 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1314 pp->total_size += p->size;
1321 src = p->bytes + p->offset;
1322 decode_ptr (&src, &pos);
1323 p->offset = src - (char*) p->bytes;
1327 assert (p->offset < p->size);
1329 src = p->bytes + p->offset;
1330 (*pp->isamb->method->codec.code_item)(ISAMC_DECODE, p->decodeClientData,
1332 p->offset = src - (char*) p->bytes;
1333 /* key_logdump_txt(LOG_DEBUG,buf, "isamb_pp_read returning 1"); */
1338 int isamb_pp_read (ISAMB_PP pp, void *buf)
1340 return isamb_pp_forward(pp, buf, 0);
1344 #define NEW_FORWARD 1
1346 #if NEW_FORWARD == 1
1348 static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
1349 { /* looks one node higher to see if we should be on this node at all */
1350 /* useful in backing off quickly, and in avoiding tail descends */
1351 /* call with pp->level to begin with */
1352 struct ISAMB_block *p;
1359 logf(LOG_DEBUG,"isamb_pp_on_right returning true for root");
1361 return 1; /* we can never skip the root node */
1365 assert(p->offset <= p->size);
1366 if (p->offset < p->size )
1368 assert(p->offset>0);
1369 src=p->bytes + p->offset;
1370 decode_ptr(&src, &item_len);
1372 (*pp->isamb->method->codec.log_item)(LOG_DEBUG,untilbuf,"on_leaf: until");
1373 (*pp->isamb->method->codec.log_item)(LOG_DEBUG,src,"on_leaf: value");
1375 cmp=(*pp->isamb->method->compare_item)(untilbuf,src);
1378 logf(LOG_DEBUG,"isamb_pp_on_right returning true "
1379 "cmp=%d lev=%d ofs=%d",cmp,level,p->offset);
1385 logf(LOG_DEBUG,"isamb_pp_on_right returning false "
1386 "cmp=%d lev=%d ofs=%d",cmp,level,p->offset);
1393 logf(LOG_DEBUG,"isamb_pp_on_right at tail, looking higher "
1396 return isamb_pp_on_right_node(pp, level, untilbuf);
1398 } /* isamb_pp_on_right_node */
1400 static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
1401 { /* reads the next item on the current leaf, returns 0 if end of leaf*/
1402 struct ISAMB_block *p = pp->block[pp->level];
1407 if (p->offset == p->size) {
1409 logf(LOG_DEBUG,"isamb_pp_read_on_leaf returning 0 on node %d",p->pos);
1411 return 0; /* at end of leaf */
1413 src=p->bytes + p->offset;
1415 (*pp->isamb->method->codec.decode)(p->decodeClientData,&dst, &src);
1416 p->offset = src - (char*) p->bytes;
1419 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, buf, "read_on_leaf returning 1");
1422 pp->returned_numbers++;
1424 } /* read_on_leaf */
1426 static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
1427 { /* forwards on the current leaf, returns 0 if not found */
1431 if (!isamb_pp_read_on_leaf(pp,buf))
1433 /* FIXME - this is an extra function call, inline the read? */
1434 cmp=(*pp->isamb->method->compare_item)(untilbuf,buf);
1435 if (cmp <2){ /* found a good one */
1438 logf(LOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items",skips);
1440 pp->returned_numbers++;
1444 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1445 return 0; /* never mind the rest of this leaf */
1446 pp->skipped_numbers++;
1449 } /* forward_on_leaf */
1451 static int isamb_pp_climb_level(ISAMB_PP pp, ISAMB_P *pos)
1452 { /* climbs higher in the tree, until finds a level with data left */
1453 /* returns the node to (consider to) descend to in *pos) */
1454 struct ISAMB_block *p = pp->block[pp->level];
1458 logf(LOG_DEBUG,"isamb_pp_climb_level starting "
1459 "at level %d node %d ofs=%d sz=%d",
1460 pp->level, p->pos, p->offset, p->size);
1462 assert(pp->level >= 0);
1463 assert(p->offset <= p->size);
1467 logf(LOG_DEBUG,"isamb_pp_climb_level returning 0 at root");
1471 assert(pp->level>0);
1472 close_block(pp->isamb, pp->block[pp->level]);
1473 pp->block[pp->level]=0;
1475 p=pp->block[pp->level];
1477 logf(LOG_DEBUG,"isamb_pp_climb_level climbed to level %d node %d ofs=%d",
1478 pp->level, p->pos, p->offset);
1481 assert(p->offset <= p->size);
1482 if (p->offset == p->size ) {
1483 /* we came from the last pointer, climb on */
1484 if (!isamb_pp_climb_level(pp,pos))
1486 p=pp->block[pp->level];
1490 /* skip the child we just came from */
1492 logf(LOG_DEBUG,"isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
1493 pp->level, p->offset, p->size);
1495 assert (p->offset < p->size );
1496 src=p->bytes + p->offset;
1497 decode_ptr(&src, &item_len);
1499 decode_ptr(&src, pos);
1500 p->offset=src - (char *)p->bytes;
1507 static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
1508 { /* scans a upper node until it finds a child <= untilbuf */
1509 /* pp points to the key value, as always. pos is the child read from */
1511 /* if all values are too small, returns the last child in the node */
1512 /* FIXME - this can be detected, and avoided by looking at the */
1513 /* parent node, but that gets messy. Presumably the cost is */
1514 /* pretty low anyway */
1515 struct ISAMB_block *p = pp->block[pp->level];
1516 const char *src=p->bytes + p->offset;
1522 logf(LOG_DEBUG,"isamb_pp_forward_unode starting "
1523 "at level %d node %d ofs=%di sz=%d",
1524 pp->level, p->pos, p->offset, p->size);
1527 assert(p->offset <= p->size);
1528 if (p->offset == p->size) {
1530 logf(LOG_DEBUG,"isamb_pp_forward_unode returning at end "
1531 "at level %d node %d ofs=%di sz=%d",
1532 pp->level, p->pos, p->offset, p->size);
1534 return pos; /* already at the end of it */
1536 while(p->offset < p->size) {
1537 decode_ptr(&src,&item_len);
1538 cmp=(*pp->isamb->method->compare_item)(untilbuf,src);
1540 decode_ptr(&src,&nxtpos);
1544 logf(LOG_DEBUG,"isamb_pp_forward_unode returning a hit "
1545 "at level %d node %d ofs=%d sz=%d",
1546 pp->level, p->pos, p->offset, p->size);
1551 p->offset=src-(char*)p->bytes;
1552 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1558 logf(LOG_DEBUG,"isamb_pp_forward_unode returning at tail "
1559 "at level %d node %d ofs=%d sz=%d skips=%d",
1560 pp->level, p->pos, p->offset, p->size, skips);
1562 return pos; /* that's the last one in the line */
1564 } /* forward_unode */
1566 static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAMB_P pos, const void *untilbuf)
1567 { /* climbs down the tree, from pos, to the leftmost leaf */
1568 struct ISAMB_block *p = pp->block[pp->level];
1572 logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
1573 "starting at lev %d node %d ofs=%d lf=%d u=%p",
1574 pp->level, p->pos, p->offset, p->leaf, untilbuf);
1577 pos=isamb_pp_forward_unode(pp,pos,untilbuf);
1580 p=open_block(pp->isamb, pos);
1581 pp->block[pp->level]=p;
1582 ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
1585 logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
1586 "got lev %d node %d lf=%d",
1587 pp->level, p->pos, p->leaf);
1591 assert (p->offset==0 );
1592 src=p->bytes + p->offset;
1593 decode_ptr(&src, &pos);
1594 p->offset=src-(char*)p->bytes;
1595 isamb_pp_descend_to_leaf(pp,pos,untilbuf);
1597 logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
1598 "returning at lev %d node %d ofs=%d lf=%d",
1599 pp->level, p->pos, p->offset, p->leaf);
1601 } /* descend_to_leaf */
1603 static int isamb_pp_find_next_leaf(ISAMB_PP pp)
1604 { /* finds the next leaf by climbing up and down */
1606 if (!isamb_pp_climb_level(pp,&pos))
1608 isamb_pp_descend_to_leaf(pp, pos,0);
1612 static int isamb_pp_climb_desc(ISAMB_PP pp, const void *untilbuf)
1613 { /* climbs up and descends to a leaf where values >= *untilbuf are found */
1616 struct ISAMB_block *p = pp->block[pp->level];
1617 logf(LOG_DEBUG,"isamb_pp_climb_desc starting "
1618 "at level %d node %d ofs=%d sz=%d",
1619 pp->level, p->pos, p->offset, p->size);
1621 if (!isamb_pp_climb_level(pp,&pos))
1623 /* see if it would pay to climb one higher */
1624 if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
1625 if (!isamb_pp_climb_level(pp,&pos))
1627 isamb_pp_descend_to_leaf(pp, pos,untilbuf);
1629 p = pp->block[pp->level];
1630 logf(LOG_DEBUG,"isamb_pp_climb_desc done "
1631 "at level %d node %d ofs=%d sz=%d",
1632 pp->level, p->pos, p->offset, p->size);
1637 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1640 struct ISAMB_block *p = pp->block[pp->level];
1642 logf(LOG_DEBUG,"isamb_pp_forward starting "
1643 "at level %d node %d ofs=%d sz=%d u=%p",
1644 pp->level, p->pos, p->offset, p->size,untilbuf);
1647 if (isamb_pp_forward_on_leaf( pp, buf, untilbuf)) {
1649 logf(LOG_DEBUG,"isamb_pp_forward (f) returning (A) "
1650 "at level %d node %d ofs=%d sz=%d",
1651 pp->level, p->pos, p->offset, p->size);
1655 if (! isamb_pp_climb_desc( pp, untilbuf)) {
1657 logf(LOG_DEBUG,"isamb_pp_forward (f) returning notfound (B) "
1658 "at level %d node %d ofs=%d sz=%d",
1659 pp->level, p->pos, p->offset, p->size);
1661 return 0; /* could not find a leaf */
1664 if (isamb_pp_forward_on_leaf( pp, buf, untilbuf)) {
1666 logf(LOG_DEBUG,"isamb_pp_forward (f) returning (C) "
1667 "at level %d node %d ofs=%d sz=%d",
1668 pp->level, p->pos, p->offset, p->size);
1672 }while ( isamb_pp_find_next_leaf(pp));
1673 return 0; /* could not find at all */
1675 else { /* no untilbuf, a straight read */
1676 /* FIXME - this should be moved
1677 * directly into the pp_read */
1678 /* keeping here now, to keep same
1679 * interface as the old fwd */
1680 if (isamb_pp_read_on_leaf( pp, buf)) {
1682 logf(LOG_DEBUG,"isamb_pp_forward (read) returning (D) "
1683 "at level %d node %d ofs=%d sz=%d",
1684 pp->level, p->pos, p->offset, p->size);
1688 if (isamb_pp_find_next_leaf(pp)) {
1690 logf(LOG_DEBUG,"isamb_pp_forward (read) returning (E) "
1691 "at level %d node %d ofs=%d sz=%d",
1692 pp->level, p->pos, p->offset, p->size);
1694 return isamb_pp_read_on_leaf(pp, buf);
1699 } /* isam_pp_forward (new version) */
1701 #elif NEW_FORWARD == 0
1703 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
1707 * while at end of node
1708 * climb higher. If out, return 0
1709 * while not on a leaf (and not at its end)
1718 * The upper nodes consist of a sequence of nodenumbers and keys
1719 * When opening a block, the first node number is read in, and
1720 * offset points to the first key, which is the upper limit of keys
1721 * in the node just read.
1725 struct ISAMB_block *p = pp->block[pp->level];
1730 int descending=0; /* used to prevent a border condition error */
1734 logf(LOG_DEBUG,"isamb_pp_forward starting [%p] p=%d",pp,p->pos);
1736 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, untilbuf, "until");
1737 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, buf, "buf");
1742 while ( (p->offset == p->size) && !descending )
1743 { /* end of this block - climb higher */
1744 assert (p->offset <= p->size);
1746 logf(LOG_DEBUG,"isamb_pp_forward climbing from l=%d",
1752 logf(LOG_DEBUG,"isamb_pp_forward returning 0 at root");
1754 return 0; /* at end of the root, nothing left */
1756 close_block(pp->isamb, pp->block[pp->level]);
1757 pp->block[pp->level]=0;
1759 p=pp->block[pp->level];
1761 logf(LOG_DEBUG,"isamb_pp_forward climbed to node %d off=%d",
1765 assert(p->offset <= p->size);
1766 /* skip the child we have handled */
1767 if (p->offset != p->size)
1769 src = p->bytes + p->offset;
1770 decode_ptr(&src, &item_len);
1772 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, src,
1773 " isamb_pp_forward "
1774 "climb skipping old key");
1777 decode_ptr(&src,&pos);
1778 p->offset = src - (char*) p->bytes;
1779 break; /* even if this puts us at the end of the block, we
1780 need to descend to the last pos. UGLY coding,
1781 clean up some day */
1786 src = p->bytes + p->offset;
1787 if (p->offset == p->size)
1788 cmp=-2 ; /* descend to the last node, as we have
1792 decode_ptr(&src, &item_len);
1794 logf(LOG_DEBUG,"isamb_pp_forward (B) on a high node. "
1795 "ofs=%d sz=%d nxtpos=%d ",
1796 p->offset,p->size,pos);
1797 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, src, "");
1800 cmp=(*pp->isamb->method->compare_item)(untilbuf,src);
1804 decode_ptr(&src,&nxtpos);
1809 logf(LOG_DEBUG,"isambb_pp_forward descending l=%d p=%d ",
1812 descending=1; /* prevent climbing for a while */
1814 p = open_block(pp->isamb,pos);
1815 pp->block[pp->level] = p ;
1816 pp->total_size += p->size;
1817 (pp->accessed_nodes[pp->maxlevel - pp->level])++;
1820 { /* block starts with a pos */
1821 src = p->bytes + p->offset;
1822 decode_ptr(&src,&pos);
1823 p->offset=src-(char*) p->bytes;
1825 logf(LOG_DEBUG,"isamb_pp_forward: block %d starts with %d",
1829 } /* descend to the node */
1831 { /* skip the node */
1832 p->offset = src - (char*) p->bytes;
1834 (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
1837 "isamb_pp_forward: skipping block on level %d, noting "
1839 pp->level, pp->maxlevel - pp->level-1 ,
1840 pp->skipped_nodes[pp->maxlevel - pp->level-1 ]);
1842 /* 0 is always leafs, 1 is one level above leafs etc, no
1843 * matter how high tree */
1845 } /* not on a leaf */
1848 if (p->offset == p->size) {
1853 assert (p->offset < p->size);
1854 src = p->bytes + p->offset;
1856 (*pp->isamb->method->codec.decode)(p->decodeClientData,
1858 p->offset = src - (char*) p->bytes;
1860 cmp=(*pp->isamb->method->compare_item)(untilbuf,buf);
1864 logf(LOG_DEBUG,"isamb_pp_forward on a leaf. cmp=%d",
1866 (*pp->isamb->method->codec.log_item)(LOG_DEBUG, buf, "");
1873 (*pp->isamb->method->codec.log_item)(
1874 LOG_DEBUG, buf, "isamb_pp_forward returning 1");
1878 (*pp->isamb->method->codec.log_item)(
1879 LOG_DEBUG, buf, "isamb_pp_read returning 1 (fwd)");
1882 pp->returned_numbers++;
1886 pp->skipped_numbers++;
1892 #elif NEW_FORWARD == 2
1894 int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilb)
1898 struct ISAMB_block *p = pp->block[pp->level];
1903 while (p->offset == p->size)
1906 while (p->offset == p->size)
1910 close_block (pp->isamb, pp->block[pp->level]);
1911 pp->block[pp->level] = 0;
1913 p = pp->block[pp->level];
1918 src = p->bytes + p->offset;
1920 decode_ptr (&src, &item_len);
1922 decode_ptr (&src, &pos);
1924 p->offset = src - (char*) p->bytes;
1926 src = p->bytes + p->offset;
1930 if (!untilb || p->offset == p->size)
1932 assert(p->offset < p->size);
1933 decode_ptr (&src, &item_len);
1934 if ((*pp->isamb->method->compare_item)(untilb, src) <= 1)
1937 decode_ptr (&src, &pos);
1938 p->offset = src - (char*) p->bytes;
1945 pp->block[pp->level] = p = open_block (pp->isamb, pos);
1947 pp->total_size += p->size;
1955 src = p->bytes + p->offset;
1958 decode_ptr (&src, &pos);
1959 p->offset = src - (char*) p->bytes;
1961 if (!untilb || p->offset == p->size)
1963 assert(p->offset < p->size);
1964 decode_ptr (&src, &item_len);
1965 if ((*pp->isamb->method->compare_item)(untilb, src) <= 1)
1972 assert (p->offset < p->size);
1977 src = p->bytes + p->offset;
1978 (*pp->isamb->method->codec.decode)(p->decodeClientData, &dst, &src);
1979 p->offset = src - (char*) p->bytes;
1980 if (!untilb || (*pp->isamb->method->compare_item)(untilb, dst0) <= 1)
1983 if (p->offset == p->size) goto again;
1985 /* key_logdump_txt(LOG_DEBUG,buf, "isamb_pp_read returning 1"); */
1991 void isamb_pp_pos( ISAMB_PP pp, double *current, double *total )
1992 { /* return an estimate of the current position and of the total number of */
1993 /* occureences in the isam tree, based on the current leaf */
1994 /* FIXME - Isam-B ought to know how many we have, so we could return */
1996 struct ISAMB_block *p = pp->block[pp->level];
2001 *total = pp->block[0]->no_items;
2002 *current = (double) pp->returned_numbers;
2003 /* use the precise number, since we have it! */
2005 logf(LOG_LOG, "isamb_pp_pos returning: cur= %0.1f tot=%0.1f rn="
2006 ZINT_FORMAT, *current, *total, pp->returned_numbers);