-static int isamb_pp_on_right_node(ISAMB_PP pp, int level, const void *untilbuf)
-{ /* looks one node higher to see if we should be on this node at all */
- /* useful in backing off quickly, and in avoiding tail descends */
- /* call with pp->level to begin with */
- struct ISAMB_block *p;
- int cmp;
- const char *src;
- zint item_len;
- assert(level>=0);
- if ( level == 0) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_on_right returning true for root");
-#endif
- return 1; /* we can never skip the root node */
- }
- level--;
- p=pp->block[level];
- assert(p->offset <= p->size);
- if (p->offset < p->size )
- {
- assert(p->offset>0);
- src=p->bytes + p->offset;
- decode_ptr(&src, &item_len);
-#if ISAMB_DEBUG
- (*pp->isamb->method->codec.log_item)(LOG_DEBUG,untilbuf,"on_leaf: until");
- (*pp->isamb->method->codec.log_item)(LOG_DEBUG,src,"on_leaf: value");
-#endif
- cmp=(*pp->isamb->method->compare_item)(untilbuf,src);
- if (cmp<2) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_on_right returning true "
- "cmp=%d lev=%d ofs=%d",cmp,level,p->offset);
-#endif
- return 1;
- }
- else {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_on_right returning false "
- "cmp=%d lev=%d ofs=%d",cmp,level,p->offset);
-#endif
- return 0;
- }
- }
- else {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_on_right at tail, looking higher "
- "lev=%d",level);
-#endif
- return isamb_pp_on_right_node(pp, level, untilbuf);
- }
-} /* isamb_pp_on_right_node */
-
-static int isamb_pp_read_on_leaf(ISAMB_PP pp, void *buf)
-{ /* reads the next item on the current leaf, returns 0 if end of leaf*/
- struct ISAMB_block *p = pp->block[pp->level];
- char *dst;
- const char *src;
- assert(pp);
- assert(buf);
- if (p->offset == p->size) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_read_on_leaf returning 0 on node %d",p->pos);
-#endif
- return 0; /* at end of leaf */
- }
- src=p->bytes + p->offset;
- dst=buf;
- (*pp->isamb->method->codec.decode)(p->decodeClientData,&dst, &src);
- p->offset = src - (char*) p->bytes;
- /*
-#if ISAMB_DEBUG
- (*pp->isamb->method->codec.log_item)(LOG_DEBUG, buf, "read_on_leaf returning 1");
-#endif
-*/
- pp->returned_numbers++;
- return 1;
-} /* read_on_leaf */
-
-static int isamb_pp_forward_on_leaf(ISAMB_PP pp, void *buf, const void *untilbuf)
-{ /* forwards on the current leaf, returns 0 if not found */
- int cmp;
- int skips=0;
- while (1){
- if (!isamb_pp_read_on_leaf(pp,buf))
- return 0;
- /* FIXME - this is an extra function call, inline the read? */
- cmp=(*pp->isamb->method->compare_item)(untilbuf,buf);
- if (cmp <2){ /* found a good one */
-#if ISAMB_DEBUG
- if (skips)
- logf(LOG_DEBUG, "isam_pp_fwd_on_leaf skipped %d items",skips);
-#endif
- pp->returned_numbers++;
- return 1;
- }
- if (!skips)
- if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
- return 0; /* never mind the rest of this leaf */
- pp->skipped_numbers++;
- skips++;
- }
-} /* forward_on_leaf */
-
-static int isamb_pp_climb_level(ISAMB_PP pp, ISAMB_P *pos)
-{ /* climbs higher in the tree, until finds a level with data left */
- /* returns the node to (consider to) descend to in *pos) */
- struct ISAMB_block *p = pp->block[pp->level];
- const char *src;
- zint item_len;
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_climb_level starting "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- assert(pp->level >= 0);
- assert(p->offset <= p->size);
- if (pp->level==0)
- {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_climb_level returning 0 at root");
-#endif
- return 0;
- }
- assert(pp->level>0);
- 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_climb_level climbed to level %d node %d ofs=%d",
- pp->level, p->pos, p->offset);
-#endif
- assert(!p->leaf);
- assert(p->offset <= p->size);
- if (p->offset == p->size ) {
- /* we came from the last pointer, climb on */
- if (!isamb_pp_climb_level(pp,pos))
- return 0;
- p=pp->block[pp->level];
- }
- else
- {
- /* skip the child we just came from */
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isam_pp_climb_level: skipping lev=%d ofs=%d sz=%d",
- pp->level, p->offset, p->size);
-#endif
- assert (p->offset < p->size );
- src=p->bytes + p->offset;
- decode_ptr(&src, &item_len);
- src += item_len;
- decode_ptr(&src, pos);
- p->offset=src - (char *)p->bytes;
-
- }
- return 1;
-} /* climb_level */
-
-
-static zint isamb_pp_forward_unode(ISAMB_PP pp, zint pos, const void *untilbuf)
-{ /* scans a upper node until it finds a child <= untilbuf */
- /* pp points to the key value, as always. pos is the child read from */
- /* the buffer */
- /* if all values are too small, returns the last child in the node */
- /* FIXME - this can be detected, and avoided by looking at the */
- /* parent node, but that gets messy. Presumably the cost is */
- /* pretty low anyway */
- struct ISAMB_block *p = pp->block[pp->level];
- const char *src=p->bytes + p->offset;
- zint item_len;
- int cmp;
- zint nxtpos;
-#if ISAMB_DEBUG
- int skips=0;
- logf(LOG_DEBUG,"isamb_pp_forward_unode starting "
- "at level %d node %d ofs=%di sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- assert(!p->leaf);
- assert(p->offset <= p->size);
- if (p->offset == p->size) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward_unode returning at end "
- "at level %d node %d ofs=%di sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return pos; /* already at the end of it */
- }
- while(p->offset < p->size) {
- decode_ptr(&src,&item_len);
- cmp=(*pp->isamb->method->compare_item)(untilbuf,src);
- src+=item_len;
- decode_ptr(&src,&nxtpos);
- if (cmp<2)
- {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward_unode returning a hit "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return pos;
- } /* found one */
- pos=nxtpos;
- p->offset=src-(char*)p->bytes;
- (pp->skipped_nodes[pp->maxlevel - pp->level -1])++;
-#if ISAMB_DEBUG
- skips++;
-#endif
- }
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward_unode returning at tail "
- "at level %d node %d ofs=%d sz=%d skips=%d",
- pp->level, p->pos, p->offset, p->size, skips);
-#endif
- return pos; /* that's the last one in the line */
-
-} /* forward_unode */
-
-static void isamb_pp_descend_to_leaf(ISAMB_PP pp, ISAMB_P pos, const void *untilbuf)
-{ /* climbs down the tree, from pos, to the leftmost leaf */
- struct ISAMB_block *p = pp->block[pp->level];
- const char *src;
- assert(!p->leaf);
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
- "starting at lev %d node %d ofs=%d lf=%d u=%p",
- pp->level, p->pos, p->offset, p->leaf, untilbuf);
-#endif
- if (untilbuf)
- pos=isamb_pp_forward_unode(pp,pos,untilbuf);
- ++(pp->level);
- assert(pos);
- p=open_block(pp->isamb, pos);
- pp->block[pp->level]=p;
- ++(pp->accessed_nodes[pp->maxlevel-pp->level]);
- ++(pp->no_blocks);
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
- "got lev %d node %d lf=%d",
- pp->level, p->pos, p->leaf);
-#endif
- if (p->leaf)
- return;
- assert (p->offset==0 );
- src=p->bytes + p->offset;
- decode_ptr(&src, &pos);
- p->offset=src-(char*)p->bytes;
- isamb_pp_descend_to_leaf(pp,pos,untilbuf);
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_descend_to_leaf "
- "returning at lev %d node %d ofs=%d lf=%d",
- pp->level, p->pos, p->offset, p->leaf);
-#endif
-} /* descend_to_leaf */
-
-static int isamb_pp_find_next_leaf(ISAMB_PP pp)
-{ /* finds the next leaf by climbing up and down */
- ISAMB_P pos;
- if (!isamb_pp_climb_level(pp,&pos))
- return 0;
- isamb_pp_descend_to_leaf(pp, pos,0);
- return 1;
-}
-
-static int isamb_pp_climb_desc(ISAMB_PP pp, const void *untilbuf)
-{ /* climbs up and descends to a leaf where values >= *untilbuf are found */
- ISAMB_P pos;
-#if ISAMB_DEBUG
- struct ISAMB_block *p = pp->block[pp->level];
- logf(LOG_DEBUG,"isamb_pp_climb_desc starting "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- if (!isamb_pp_climb_level(pp,&pos))
- return 0;
- /* see if it would pay to climb one higher */
- if (!isamb_pp_on_right_node(pp, pp->level, untilbuf))
- if (!isamb_pp_climb_level(pp,&pos))
- return 0;
- isamb_pp_descend_to_leaf(pp, pos,untilbuf);
-#if ISAMB_DEBUG
- p = pp->block[pp->level];
- logf(LOG_DEBUG,"isamb_pp_climb_desc done "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return 1;
-} /* climb_desc */
-
-int isamb_pp_forward (ISAMB_PP pp, void *buf, const void *untilbuf)
-{
-#if ISAMB_DEBUG
- struct ISAMB_block *p = pp->block[pp->level];
- assert(p->leaf);
- logf(LOG_DEBUG,"isamb_pp_forward starting "
- "at level %d node %d ofs=%d sz=%d u=%p",
- pp->level, p->pos, p->offset, p->size,untilbuf);
-#endif
- if (untilbuf) {
- if (isamb_pp_forward_on_leaf( pp, buf, untilbuf)) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward (f) returning (A) "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return 1;
- }
- if (! isamb_pp_climb_desc( pp, untilbuf)) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward (f) returning notfound (B) "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return 0; /* could not find a leaf */
- }
- do{
- if (isamb_pp_forward_on_leaf( pp, buf, untilbuf)) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward (f) returning (C) "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return 1;
- }
- }while ( isamb_pp_find_next_leaf(pp));
- return 0; /* could not find at all */
- }
- else { /* no untilbuf, a straight read */
- /* FIXME - this should be moved
- * directly into the pp_read */
- /* keeping here now, to keep same
- * interface as the old fwd */
- if (isamb_pp_read_on_leaf( pp, buf)) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward (read) returning (D) "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return 1;
- }
- if (isamb_pp_find_next_leaf(pp)) {
-#if ISAMB_DEBUG
- logf(LOG_DEBUG,"isamb_pp_forward (read) returning (E) "
- "at level %d node %d ofs=%d sz=%d",
- pp->level, p->pos, p->offset, p->size);
-#endif
- return isamb_pp_read_on_leaf(pp, buf);
- }
- else
- return 0;
- }
-} /* isam_pp_forward (new version) */
-
-#elif NEW_FORWARD == 0
-
-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;
- const 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);