From 73920b6f7f49407da60018dfbba8f7a458c155c6 Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Wed, 2 Apr 2008 21:00:50 +0200 Subject: [PATCH] Use isamb_pp_forward2 as the isamb forward function. The existing isamb_pp_forward has removed by this commit and the isamb_pp_forward takes it place. The _2 version seems to be a lot faster for "long" skips and it's a lot simpler to understand (IMHO). --- include/idzebra/isamb.h | 2 - isamb/isamb.c | 407 +---------------------------------------------- 2 files changed, 1 insertion(+), 408 deletions(-) diff --git a/include/idzebra/isamb.h b/include/idzebra/isamb.h index aa17bd4..c2f48bf 100644 --- a/include/idzebra/isamb.h +++ b/include/idzebra/isamb.h @@ -53,8 +53,6 @@ int isamb_pp_read(ISAMB_PP pp, void *buf); YAZ_EXPORT int isamb_pp_forward(ISAMB_PP pp, void *buf, const void *untilbuf); -YAZ_EXPORT -int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilbuf); YAZ_EXPORT void isamb_pp_pos(ISAMB_PP pp, double *current, double *total); diff --git a/isamb/isamb.c b/isamb/isamb.c index 2b69426..3b72464 100644 --- a/isamb/isamb.c +++ b/isamb/isamb.c @@ -1494,411 +1494,6 @@ int isamb_pp_read(ISAMB_PP pp, void *buf) } -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; - ISAMB b = pp->isamb; - - assert(level >= 0); - if (level == 0) - { -#if ISAMB_DEBUG - yaz_log(YLOG_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) - { -#if INT_ENCODE - char file_item_buf[DST_ITEM_MAX]; - char *file_item = file_item_buf; - void *c1 = (*b->method->codec.start)(); - assert(p->offset > 0); - src = p->bytes + p->offset; - (*b->method->codec.decode)(c1, &file_item, &src); - (*b->method->codec.stop)(c1); - cmp = (*b->method->compare_item)(untilbuf, file_item_buf); -#else - zint item_len; - assert(p->offset > 0); - src = p->bytes + p->offset; - decode_item_len(&src, &item_len); -#if ISAMB_DEBUG - (*b->method->codec.log_item)(YLOG_DEBUG, untilbuf, "on_leaf: until"); - (*b->method->codec.log_item)(YLOG_DEBUG, src, "on_leaf: value"); -#endif - cmp = (*b->method->compare_item)(untilbuf, src); -#endif - if (cmp < pp->scope) - { /* cmp<2 */ -#if ISAMB_DEBUG - yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning true " - "cmp=%d lev=%d ofs=%d", cmp, level, p->offset); -#endif - return 1; - } - else - { -#if ISAMB_DEBUG - yaz_log(YLOG_DEBUG, "isamb_pp_on_right returning false " - "cmp=%d lev=%d ofs=%d", cmp, level, p->offset); -#endif - return 0; - } - } - else { -#if ISAMB_DEBUG - yaz_log(YLOG_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 - yaz_log(YLOG_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)(YLOG_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 scope) - { /* cmp<2 found a good one */ -#if ISAMB_DEBUG - if (skips) - yaz_log(YLOG_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, ISAM_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; -#if ISAMB_DEBUG - yaz_log(YLOG_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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 - { -#if INT_ENCODE - char file_item_buf[DST_ITEM_MAX]; - char *file_item = file_item_buf; - ISAMB b = pp->isamb; - void *c1 = (*b->method->codec.start)(); -#else - zint item_len; -#endif - /* skip the child we just came from */ -#if ISAMB_DEBUG - yaz_log(YLOG_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; -#if INT_ENCODE - (*b->method->codec.decode)(c1, &file_item, &src); - (*b->method->codec.stop)(c1); -#else - decode_item_len(&src, &item_len); - src += item_len; -#endif - 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 */ - ISAMB b = pp->isamb; - struct ISAMB_block *p = pp->block[pp->level]; - const char *src = p->bytes + p->offset; - int cmp; - zint nxtpos; -#if ISAMB_DEBUG - int skips = 0; - yaz_log(YLOG_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 - yaz_log(YLOG_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) - { -#if INT_ENCODE - char file_item_buf[DST_ITEM_MAX]; - char *file_item = file_item_buf; - void *c1 = (*b->method->codec.start)(); - (*b->method->codec.decode)(c1, &file_item, &src); - (*b->method->codec.stop)(c1); - cmp = (*b->method->compare_item)(untilbuf, file_item_buf); -#else - zint item_len; - decode_item_len(&src, &item_len); - cmp = (*b->method->compare_item)(untilbuf, src); - src += item_len; -#endif - decode_ptr(&src, &nxtpos); - if (cmpscope) /* cmp<2 */ - { -#if ISAMB_DEBUG - yaz_log(YLOG_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 - yaz_log(YLOG_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, ISAM_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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 */ - ISAM_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 */ - ISAM_P pos; -#if ISAMB_DEBUG - struct ISAMB_block *p = pp->block[pp->level]; - yaz_log(YLOG_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]; - yaz_log(YLOG_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); - yaz_log(YLOG_DEBUG, "isamb_pp_forward starting " - "at level %d node %d ofs=%d sz=%d u=%p sc=%d", - pp->level, p->pos, p->offset, p->size, untilbuf, scope); -#endif - if (untilbuf) - { - if (isamb_pp_forward_on_leaf(pp, buf, untilbuf)) - { -#if ISAMB_DEBUG - yaz_log(YLOG_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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 - yaz_log(YLOG_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) */ - void isamb_pp_pos(ISAMB_PP pp, double *current, double *total) { /* return an estimate of the current position and of the total number of */ /* occureences in the isam tree, based on the current leaf */ @@ -1915,7 +1510,7 @@ void isamb_pp_pos(ISAMB_PP pp, double *current, double *total) #endif } -int isamb_pp_forward2(ISAMB_PP pp, void *buf, const void *untilb) +int isamb_pp_forward(ISAMB_PP pp, void *buf, const void *untilb) { char *dst = buf; const char *src; -- 1.7.10.4