X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=blobdiff_plain;f=isamb%2Fisamb.c;h=2f439718372435d69d2cda4981fb6373da0afd8d;hp=1e0a7dd514fa7c2c34afc397bbd5583065dfb352;hb=12d4ad07fc9bae26217f7d6bc17181a1b892337a;hpb=ba1ca9cd76ff8e56daff04ee0e6c8fa21c7b04b6 diff --git a/isamb/isamb.c b/isamb/isamb.c index 1e0a7dd..2f43971 100644 --- a/isamb/isamb.c +++ b/isamb/isamb.c @@ -1,39 +1,71 @@ -/* - * Copyright (c) 2000-2002, Index Data. - * See the file LICENSE for details. - * - * $Id: isamb.c,v 1.18 2002-07-15 11:50:45 adam Exp $ - */ +/* $Id: isamb.c,v 1.35 2004-06-02 07:53:31 adam Exp $ + Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004 + Index Data Aps + +This file is part of the Zebra server. + +Zebra is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +Zebra is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with Zebra; see the file LICENSE.zebra. If not, write to the +Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. +*/ + +#include #include #include #include #include +#ifndef ISAMB_DEBUG +#define ISAMB_DEBUG 0 +#endif + struct ISAMB_head { int first_block; int last_block; int block_size; int block_max; + int free_list; }; #define ISAMB_DATA_OFFSET 3 +/* maximum size of encoded buffer */ #define DST_ITEM_MAX 256 -/* approx 2*4 K + max size of item */ -#define DST_BUF_SIZE 8448 +#define ISAMB_MAX_LEVEL 10 +/* approx 2*max page + max size of item */ +#define DST_BUF_SIZE 16840 #define ISAMB_CACHE_ENTRY_SIZE 4096 +/* CAT_MAX: _must_ be power of 2 */ +#define CAT_MAX 4 +#define CAT_MASK (CAT_MAX-1) +/* CAT_NO: <= CAT_MAX */ +#define CAT_NO 4 + +/* ISAMB_PTR_CODEC=1 var, =0 fixed */ +#define ISAMB_PTR_CODEC 1 + struct ISAMB_cache_entry { ISAMB_P pos; - char *buf; + unsigned char *buf; int dirty; int hits; struct ISAMB_cache_entry *next; }; - struct ISAMB_file { BFile bf; int head_dirty; @@ -43,11 +75,17 @@ struct ISAMB_file { struct ISAMB_s { BFiles bfs; - ISAMC_M method; + ISAMC_M *method; struct ISAMB_file *file; int no_cat; int cache; /* 0=no cache, 1=use cache, -1=dummy isam (for testing only) */ + int log_io; /* log level for bf_read/bf_write calls */ + int log_freelist; /* log level for freelist handling */ + int skipped_numbers; /* on a leaf node */ + int returned_numbers; + int skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1=higher etc */ + int accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */ }; struct ISAMB_block { @@ -56,45 +94,92 @@ struct ISAMB_block { int size; int leaf; int dirty; + int deleted; int offset; char *bytes; unsigned char *buf; void *decodeClientData; + int log_rw; }; struct ISAMB_PP_s { ISAMB isamb; ISAMB_P pos; int level; + int maxlevel; /* total depth */ int total_size; int no_blocks; + int skipped_numbers; /* on a leaf node */ + int returned_numbers; + int skipped_nodes[ISAMB_MAX_LEVEL]; /* [0]=skipped leaves, 1=higher etc */ + int accessed_nodes[ISAMB_MAX_LEVEL]; /* nodes we did not skip */ struct ISAMB_block **block; }; -void encode_ptr (char **dst, int pos) +#if ISAMB_PTR_CODEC +static void encode_ptr (char **dst, unsigned pos) +{ + unsigned char *bp = (unsigned char*) *dst; + + while (pos > 127) + { + *bp++ = 128 | (pos & 127); + pos = pos >> 7; + } + *bp++ = pos; + *dst = (char *) bp; +} +#else +static void encode_ptr (char **dst, unsigned pos) { - memcpy (*dst, &pos, sizeof(pos)); + memcpy(*dst, &pos, sizeof(pos)); (*dst) += sizeof(pos); } +#endif -void decode_ptr (char **src, int *pos) +#if ISAMB_PTR_CODEC +static void decode_ptr (char **src1, int *pos) { - memcpy (pos, *src, sizeof(*pos)); - (*src) += sizeof(*pos); + unsigned char **src = (unsigned char **) src1; + unsigned d = 0; + unsigned char c; + unsigned r = 0; + + while (((c = *(*src)++) & 128)) + { + d += ((c & 127) << r); + r += 7; + } + d += (c << r); + *pos = d; } +#else +static void decode_ptr (char **src, int *pos) +{ + memcpy (pos, *src, sizeof(*pos)); + (*src) += sizeof(*pos); +} +#endif -ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method, +ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M *method, int cache) { ISAMB isamb = xmalloc (sizeof(*isamb)); int i, b_size = 32; isamb->bfs = bfs; - isamb->method = (ISAMC_M) xmalloc (sizeof(*method)); + isamb->method = (ISAMC_M *) xmalloc (sizeof(*method)); memcpy (isamb->method, method, sizeof(*method)); - isamb->no_cat = 4; + isamb->no_cat = CAT_NO; + isamb->log_io = 0; + isamb->log_freelist = 0; isamb->cache = cache; + isamb->skipped_numbers=0; + isamb->returned_numbers=0; + for (i=0;iskipped_nodes[i]= isamb->accessed_nodes[i]=0; + assert (cache == 0); isamb->file = xmalloc (sizeof(*isamb->file) * isamb->no_cat); for (i = 0; ino_cat; i++) { @@ -116,12 +201,16 @@ ISAMB isamb_open (BFiles bfs, const char *name, int writeflag, ISAMC_M method, isamb->file[i].head.last_block = isamb->file[i].head.first_block; isamb->file[i].head.block_size = b_size; isamb->file[i].head.block_max = b_size - ISAMB_DATA_OFFSET; + isamb->file[i].head.free_list = 0; } assert (isamb->file[i].head.block_size >= ISAMB_DATA_OFFSET); isamb->file[i].head_dirty = 0; assert(isamb->file[i].head.block_size == b_size); b_size = b_size * 4; } +#if ISAMB_DEBUG + logf(LOG_WARN, "isamb debug enabled. Things will be slower than usual"); +#endif return isamb; } @@ -133,7 +222,10 @@ static void flush_blocks (ISAMB b, int cat) b->file[cat].cache_entries = ce_this->next; if (ce_this->dirty) + { + yaz_log (b->log_io, "bf_write: flush_blocks"); bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf); + } xfree (ce_this->buf); xfree (ce_this); } @@ -141,11 +233,11 @@ static void flush_blocks (ISAMB b, int cat) static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr) { - int cat = pos&3; - int off = ((pos/4) & + int cat = pos&CAT_MASK; + int off = ((pos/CAT_MAX) & (ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size - 1)) * b->file[cat].head.block_size; - int norm = pos / (4*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size); + int norm = pos / (CAT_MASK*ISAMB_CACHE_ENTRY_SIZE / b->file[cat].head.block_size); int no = 0; struct ISAMB_cache_entry **ce, *ce_this = 0, **ce_last = 0; @@ -183,7 +275,10 @@ static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr) ce_this = *ce_last; *ce_last = 0; /* remove the last entry from list */ if (ce_this->dirty) + { + yaz_log (b->log_io, "bf_write: get_block"); bf_write (b->file[cat].bf, ce_this->pos, 0, 0, ce_this->buf); + } xfree (ce_this->buf); xfree (ce_this); } @@ -192,6 +287,7 @@ static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr) b->file[cat].cache_entries = ce_this; ce_this->buf = xmalloc (ISAMB_CACHE_ENTRY_SIZE); ce_this->pos = norm; + yaz_log (b->log_io, "bf_read: get_block"); if (!bf_read (b->file[cat].bf, norm, 0, 0, ce_this->buf)) memset (ce_this->buf, 0, ISAMB_CACHE_ENTRY_SIZE); if (wr) @@ -211,6 +307,11 @@ static int get_block (ISAMB b, ISAMC_P pos, char *userbuf, int wr) void isamb_close (ISAMB isamb) { int i; + for (i=0;isamb->accessed_nodes[i];i++) + logf(LOG_DEBUG,"isamb_close level leaf-%d: %d read, %d skipped", + i, isamb->accessed_nodes[i], isamb->skipped_nodes[i]); + logf(LOG_DEBUG,"isamb_close returned %d values, skipped %d", + isamb->skipped_numbers, isamb->returned_numbers); for (i = 0; ino_cat; i++) { flush_blocks (isamb, i); @@ -218,6 +319,7 @@ void isamb_close (ISAMB isamb) bf_write (isamb->file[i].bf, 0, 0, sizeof(struct ISAMB_head), &isamb->file[i].head); + bf_close (isamb->file[i].bf); } xfree (isamb->file); xfree (isamb->method); @@ -227,50 +329,80 @@ void isamb_close (ISAMB isamb) struct ISAMB_block *open_block (ISAMB b, ISAMC_P pos) { - int cat = pos&3; + int cat = pos&CAT_MASK; struct ISAMB_block *p; if (!pos) return 0; p = xmalloc (sizeof(*p)); p->pos = pos; - p->cat = pos & 3; + p->cat = pos & CAT_MASK; p->buf = xmalloc (b->file[cat].head.block_size); if (!get_block (b, pos, p->buf, 0)) { - if (!bf_read (b->file[cat].bf, pos/4, 0, 0, p->buf)) + yaz_log (b->log_io, "bf_read: open_block"); + if (!bf_read (b->file[cat].bf, pos/CAT_MAX, 0, 0, p->buf)) { - yaz_log (LOG_FATAL, "read failure for pos=%ld block=%ld", - (long) pos, (long) pos/4); + yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld", + (long) pos, (long) pos/CAT_MAX); abort(); } } p->bytes = p->buf + ISAMB_DATA_OFFSET; p->leaf = p->buf[0]; - p->size = p->buf[1] + 256 * p->buf[2] - ISAMB_DATA_OFFSET; + p->size = (p->buf[1] + 256 * p->buf[2]) - ISAMB_DATA_OFFSET; + if (p->size < 0) + { + yaz_log (LOG_FATAL, "Bad block size %d in pos=%d\n", p->size, pos); + } + assert (p->size >= 0); p->offset = 0; p->dirty = 0; + p->deleted = 0; p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE); + yaz_log (LOG_DEBUG, "isamb_open_block: Opened block %d ofs=%d",pos, p->offset); return p; } struct ISAMB_block *new_block (ISAMB b, int leaf, int cat) { struct ISAMB_block *p; - int block_no; - + p = xmalloc (sizeof(*p)); - block_no = b->file[cat].head.last_block++; - p->cat = cat; - p->pos = block_no * 4 + cat; + p->buf = xmalloc (b->file[cat].head.block_size); + + if (!b->file[cat].head.free_list) + { + int block_no; + block_no = b->file[cat].head.last_block++; + p->pos = block_no * CAT_MAX + cat; + } + else + { + p->pos = b->file[cat].head.free_list; + assert((p->pos & CAT_MASK) == cat); + if (!get_block (b, p->pos, p->buf, 0)) + { + yaz_log (b->log_io, "bf_read: new_block"); + if (!bf_read (b->file[cat].bf, p->pos/CAT_MAX, 0, 0, p->buf)) + { + yaz_log (LOG_FATAL, "isamb: read fail for pos=%ld block=%ld", + (long) p->pos/CAT_MAX, (long) p->pos/CAT_MAX); + abort (); + } + } + yaz_log (b->log_freelist, "got block %d from freelist %d:%d", p->pos, + cat, p->pos/CAT_MAX); + memcpy (&b->file[cat].head.free_list, p->buf, sizeof(int)); + } p->cat = cat; b->file[cat].head_dirty = 1; - p->buf = xmalloc (b->file[cat].head.block_size); memset (p->buf, 0, b->file[cat].head.block_size); p->bytes = p->buf + ISAMB_DATA_OFFSET; p->leaf = leaf; p->size = 0; p->dirty = 1; + p->deleted = 0; p->offset = 0; p->decodeClientData = (*b->method->code_start)(ISAMC_DECODE); return p; @@ -287,18 +419,63 @@ struct ISAMB_block *new_int (ISAMB b, int cat) return new_block (b, 0, cat); } +static void check_block (ISAMB b, struct ISAMB_block *p) +{ + if (p->leaf) + { + ; + } + else + { + /* sanity check */ + char *startp = p->bytes; + char *src = startp; + char *endp = p->bytes + p->size; + int pos; + + decode_ptr (&src, &pos); + assert ((pos&CAT_MASK) == p->cat); + while (src != endp) + { + int item_len; + decode_ptr (&src, &item_len); + assert (item_len > 0 && item_len < 30); + src += item_len; + decode_ptr (&src, &pos); + assert ((pos&CAT_MASK) == p->cat); + } + } +} + void close_block (ISAMB b, struct ISAMB_block *p) { if (!p) return; - if (p->dirty) + if (p->deleted) + { + yaz_log (b->log_freelist, "release block %d from freelist %d:%d", + p->pos, p->cat, p->pos/CAT_MAX); + memcpy (p->buf, &b->file[p->cat].head.free_list, sizeof(int)); + b->file[p->cat].head.free_list = p->pos; + if (!get_block (b, p->pos, p->buf, 1)) + { + yaz_log (b->log_io, "bf_write: close_block (deleted)"); + bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf); + } + } + else if (p->dirty) { int size = p->size + ISAMB_DATA_OFFSET; + assert (p->size >= 0); p->buf[0] = p->leaf; p->buf[1] = size & 255; p->buf[2] = size >> 8; + check_block(b, p); if (!get_block (b, p->pos, p->buf, 1)) - bf_write (b->file[p->cat].bf, p->pos/4, 0, 0, p->buf); + { + yaz_log (b->log_io, "bf_write: close_block"); + bf_write (b->file[p->cat].bf, p->pos/CAT_MAX, 0, 0, p->buf); + } } (*b->method->code_stop)(ISAMC_DECODE, p->decodeClientData); xfree (p->buf); @@ -307,14 +484,14 @@ void close_block (ISAMB b, struct ISAMB_block *p) int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, int *mode, - ISAMC_I stream, + ISAMC_I *stream, struct ISAMB_block **sp, void *sub_item, int *sub_size, void *max_item); int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, int *mode, - ISAMC_I stream, struct ISAMB_block **sp, + ISAMC_I *stream, struct ISAMB_block **sp, void *split_item, int *split_size, void *last_max_item) { char *startp = p->bytes; @@ -328,11 +505,13 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, *sp = 0; + assert(p->size >= 0); decode_ptr (&src, &pos); while (src != endp) { int item_len; int d; + char *src0 = src; decode_ptr (&src, &item_len); d = (*b->method->compare_item)(src, lookahead_item); if (d > 0) @@ -342,6 +521,7 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, more = insert_sub (b, &sub_p1, lookahead_item, mode, stream, &sub_p2, sub_item, &sub_size, src); + src = src0; break; } src += item_len; @@ -378,6 +558,7 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, dst += endp - src; } p->size = dst - dst_buf; + assert (p->size >= 0); if (p->size <= b->file[p->cat].head.block_max) { memcpy (startp, dst_buf, dst - dst_buf); @@ -419,7 +600,8 @@ int insert_int (ISAMB b, struct ISAMB_block *p, void *lookahead_item, int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, - int *lookahead_mode, ISAMC_I stream, struct ISAMB_block **sp2, + int *lookahead_mode, ISAMC_I *stream, + struct ISAMB_block **sp2, void *sub_item, int *sub_size, void *max_item) { @@ -430,7 +612,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, void *c1 = (*b->method->code_start)(ISAMC_DECODE); void *c2 = (*b->method->code_start)(ISAMC_ENCODE); int more = 1; - int quater = b->file[b->no_cat-1].head.block_max / 4; + int quater = b->file[b->no_cat-1].head.block_max / CAT_MAX; char *cut = dst_buf + quater * 2; char *maxp = dst_buf + b->file[b->no_cat-1].head.block_max; char *half1 = 0; @@ -459,7 +641,11 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, if (d > 0) { dst_item = lookahead_item; - assert (*lookahead_mode); + if (!*lookahead_mode) + { + yaz_log (LOG_WARN, "isamb: Inconsistent register (1)"); + assert (*lookahead_mode); + } } else dst_item = file_item_buf; @@ -545,7 +731,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, } if (!*lookahead_mode) { - yaz_log (LOG_WARN, "Inconsistent register (2)"); + yaz_log (LOG_WARN, "isamb: Inconsistent register (2)"); abort(); } else if (!half1 && dst > cut) @@ -583,6 +769,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, new_size > b->file[p->cat].head.block_max) { /* non-btree block will be removed */ + p->deleted = 1; close_block (b, p); /* delete it too!! */ p = 0; /* make a new one anyway */ @@ -639,7 +826,7 @@ int insert_leaf (ISAMB b, struct ISAMB_block **sp1, void *lookahead_item, int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, int *mode, - ISAMC_I stream, + ISAMC_I *stream, struct ISAMB_block **sp, void *sub_item, int *sub_size, void *max_item) @@ -652,7 +839,36 @@ int insert_sub (ISAMB b, struct ISAMB_block **p, void *new_item, sub_size, max_item); } -int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I stream) +int isamb_unlink (ISAMB b, ISAMC_P pos) +{ + struct ISAMB_block *p1; + + if (!pos) + return 0; + p1 = open_block(b, pos); + p1->deleted = 1; + if (!p1->leaf) + { + int sub_p; + int item_len; + char *src = p1->bytes + p1->offset; + + decode_ptr(&src, &sub_p); + isamb_unlink(b, sub_p); + + while (src != p1->bytes + p1->size) + { + decode_ptr(&src, &item_len); + src += item_len; + decode_ptr(&src, &sub_p); + isamb_unlink(b, sub_p); + } + } + close_block(b, p1); + return 0; +} + +int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I *stream) { char item_buf[DST_ITEM_MAX]; char *item_ptr; @@ -709,14 +925,20 @@ int isamb_merge (ISAMB b, ISAMC_P pos, ISAMC_I stream) ISAMB_PP isamb_pp_open_x (ISAMB isamb, ISAMB_P pos, int *level) { ISAMB_PP pp = xmalloc (sizeof(*pp)); + int i; pp->isamb = isamb; - pp->block = xmalloc (10 * sizeof(*pp->block)); + pp->block = xmalloc (ISAMB_MAX_LEVEL * sizeof(*pp->block)); pp->pos = pos; pp->level = 0; + pp->maxlevel=0; pp->total_size = 0; pp->no_blocks = 0; + pp->skipped_numbers=0; + pp->returned_numbers=0; + for (i=0;iskipped_nodes[i] = pp->accessed_nodes[i]=0; while (1) { struct ISAMB_block *p = open_block (isamb, pos); @@ -725,15 +947,17 @@ ISAMB_PP isamb_pp_open_x (ISAMB isamb, ISAMB_P pos, int *level) pp->total_size += p->size; pp->no_blocks++; - if (p->leaf) break; + decode_ptr (&src, &pos); p->offset = src - p->bytes; pp->level++; + pp->accessed_nodes[pp->level]++; } pp->block[pp->level+1] = 0; + pp->maxlevel=pp->level; if (level) *level = pp->level; return pp; @@ -749,6 +973,19 @@ void isamb_pp_close_x (ISAMB_PP pp, int *size, int *blocks) int i; if (!pp) return; + logf(LOG_DEBUG,"isamb_pp_close lev=%d returned %d values, skipped %d", + pp->maxlevel, pp->skipped_numbers, pp->returned_numbers); + for (i=pp->maxlevel;i>=0;i--) + if ( pp->skipped_nodes[i] || pp->accessed_nodes[i]) + logf(LOG_DEBUG,"isamb_pp_close level leaf-%d: %d read, %d skipped", i, + pp->accessed_nodes[i], pp->skipped_nodes[i]); + pp->isamb->skipped_numbers += pp->skipped_numbers; + pp->isamb->returned_numbers += pp->returned_numbers; + for (i=pp->maxlevel;i>=0;i--) + { + pp->isamb->accessed_nodes[i] += pp->accessed_nodes[i]; + pp->isamb->skipped_nodes[i] += pp->skipped_nodes[i]; + } if (size) *size = pp->total_size; if (blocks) @@ -768,9 +1005,15 @@ int isamb_block_info (ISAMB isamb, int cat) void isamb_pp_close (ISAMB_PP pp) { - return isamb_pp_close_x (pp, 0, 0); + isamb_pp_close_x (pp, 0, 0); } + +#if 0 +/* Old isamb_pp_read that Adam wrote, kept as a reference in case we need to + debug the more complex pp_read that also forwards. May be deleted near end + of 2004, if it has not shown to be useful */ + int isamb_pp_read (ISAMB_PP pp, void *buf) { char *dst = buf; @@ -790,7 +1033,7 @@ int isamb_pp_read (ISAMB_PP pp, void *buf) pp->block[pp->level] = 0; (pp->level)--; p = pp->block[pp->level]; - assert (!p->leaf); /* must be int */ + assert (!p->leaf); } src = p->bytes + p->offset; @@ -809,7 +1052,7 @@ int isamb_pp_read (ISAMB_PP pp, void *buf) pp->total_size += p->size; pp->no_blocks++; - if (p->leaf) /* leaf */ + if (p->leaf) { break; } @@ -825,9 +1068,207 @@ int isamb_pp_read (ISAMB_PP pp, void *buf) (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData, &dst, &src); p->offset = src - (char*) p->bytes; + /* key_logdump_txt(LOG_DEBUG,buf, "isamb_pp_read returning 1"); */ return 1; } +#else +int isamb_pp_read (ISAMB_PP pp, void *buf) +{ + return isamb_pp_forward(pp,buf,0); +} +#endif + +int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf) +{ + /* pseudocode: + * while 1 + * while at end of node + * climb higher. If out, return 0 + * while not on a leaf (and not at its end) + * decode next + * if cmp + * descend to node + * decode next + * if cmp + * return 1 + */ + /* + * The upper nodes consist of a sequence of nodenumbers and keys + * When opening a block, the first node number is read in, and + * offset points to the first key, which is the upper limit of keys + * in the node just read. + */ + char *dst = buf; + char *src; + struct ISAMB_block *p = pp->block[pp->level]; + int cmp; + int item_len; + int pos; + int nxtpos; + int descending=0; /* used to prevent a border condition error */ + if (!p) + return 0; +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward starting [%p] p=%d",pp,p->pos); + + (*pp->isamb->method->log_item)(LOG_DEBUG, untilbuf, "until"); + (*pp->isamb->method->log_item)(LOG_DEBUG, buf, "buf"); +#endif + + while (1) + { + while ( (p->offset == p->size) && !descending ) + { /* end of this block - climb higher */ + assert (p->offset <= p->size); +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward climbing from l=%d", + pp->level); +#endif + if (pp->level == 0) + { +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward returning 0 at root"); +#endif + return 0; /* at end of the root, nothing left */ + } + close_block(pp->isamb, pp->block[pp->level]); + pp->block[pp->level]=0; + (pp->level)--; + p=pp->block[pp->level]; +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward climbed to node %d off=%d", + p->pos, p->offset); +#endif + assert(!p->leaf); + assert(p->offset <= p->size); + /* skip the child we have handled */ + if (p->offset != p->size) + { + src = p->bytes + p->offset; + decode_ptr(&src, &item_len); +#if ISAMB_DEBUG + (*pp->isamb->method->log_item)(LOG_DEBUG, src, + " isamb_pp_forward " + "climb skipping old key"); +#endif + src += item_len; + decode_ptr(&src,&pos); + p->offset = src - (char*) p->bytes; + break; /* even if this puts us at the end of the block, we + need to descend to the last pos. UGLY coding, + clean up some day */ + } + } + if (!p->leaf) + { + src = p->bytes + p->offset; + if (p->offset == p->size) + cmp=-2 ; /* descend to the last node, as we have + no value to cmp */ + else + { + decode_ptr(&src, &item_len); +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward (B) on a high node. " + "ofs=%d sz=%d nxtpos=%d ", + p->offset,p->size,pos); + (*pp->isamb->method->log_item)(LOG_DEBUG, src, ""); +#endif + if (untilbuf) + cmp=(*pp->isamb->method->compare_item)(untilbuf,src); + else + cmp=-2; + src += item_len; + decode_ptr(&src,&nxtpos); + } + if (cmp<2) + { +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isambb_pp_forward descending l=%d p=%d ", + pp->level, pos); +#endif + descending=1; /* prevent climbing for a while */ + ++(pp->level); + p = open_block(pp->isamb,pos); + pp->block[pp->level] = p ; + pp->total_size += p->size; + (pp->accessed_nodes[pp->maxlevel - pp->level])++; + pp->no_blocks++; + if ( !p->leaf) + { /* block starts with a pos */ + src = p->bytes + p->offset; + decode_ptr(&src,&pos); + p->offset=src-(char*) p->bytes; +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward: block %d starts with %d", + p->pos, pos); +#endif + } + } /* descend to the node */ + else + { /* skip the node */ + p->offset = src - (char*) p->bytes; + pos=nxtpos; + (pp->skipped_nodes[pp->maxlevel - pp->level -1])++; +#if ISAMB_DEBUG + logf(LOG_DEBUG, + "isamb_pp_forward: skipping block on level %d, noting " + "on %d (%d)", + pp->level, pp->maxlevel - pp->level-1 , + pp->skipped_nodes[pp->maxlevel - pp->level-1 ]); +#endif + /* 0 is always leafs, 1 is one level above leafs etc, no + * matter how high tree */ + } + } /* not on a leaf */ + else + { /* on a leaf */ + if (p->offset == p->size) { + descending = 0; + } + else + { + assert (p->offset < p->size); + src = p->bytes + p->offset; + dst=buf; + (*pp->isamb->method->code_item)(ISAMC_DECODE, p->decodeClientData, + &dst, &src); + p->offset = src - (char*) p->bytes; + if (untilbuf) + cmp=(*pp->isamb->method->compare_item)(untilbuf,buf); + else + cmp=-2; +#if ISAMB_DEBUG + logf(LOG_DEBUG,"isamb_pp_forward on a leaf. cmp=%d", + cmp); + (*pp->isamb->method->log_item)(LOG_DEBUG, buf, ""); +#endif + if (cmp <2) + { +#if ISAMB_DEBUG + if (untilbuf) + { + (*pp->isamb->method->log_item)( + LOG_DEBUG, buf, "isamb_pp_forward returning 1"); + } + else + { + (*pp->isamb->method->log_item)( + LOG_DEBUG, buf, "isamb_pp_read returning 1 (fwd)"); + } +#endif + pp->returned_numbers++; + return 1; + } + else + pp->skipped_numbers++; + } + } /* leaf */ + } /* main loop */ +} + + int isamb_pp_num (ISAMB_PP pp) { return 1;