X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=blobdiff_plain;f=rset%2Frsmultiandor.c;h=6c3145c4243e368fda6aa959e274cd2107a551c4;hp=b810c549c4584c91d2754c44cd0909783f548826;hb=c33ea56e3771c3b80ba66ef8fda3a09cad171ebb;hpb=2cb08a89ee65d8ae2646b91dcf27bc3883759691 diff --git a/rset/rsmultiandor.c b/rset/rsmultiandor.c index b810c54..6c3145c 100644 --- a/rset/rsmultiandor.c +++ b/rset/rsmultiandor.c @@ -1,5 +1,5 @@ -/* $Id: rsmultiandor.c,v 1.19 2005-05-24 11:35:43 adam Exp $ - Copyright (C) 1995-2005 +/* $Id: rsmultiandor.c,v 1.26 2006-09-08 14:40:55 adam Exp $ + Copyright (C) 1995-2006 Index Data ApS This file is part of the Zebra server. @@ -15,14 +15,15 @@ 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. +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ -/* - * This module implements the rsmulti_or and rsmulti_and result sets +/** + * \file rsmultiandor.c + * \brief This module implements the rsmulti_or and rsmulti_and result sets * * rsmultior is based on a heap, from which we find the next hit. * @@ -119,6 +120,8 @@ struct rfd_private { zint hits; /* returned so far */ int eof; /* seen the end of it */ int tailcount; /* how many items are tailing */ + zint segment; + int skip; char *tailbits; }; @@ -164,8 +167,10 @@ static int heap_empty(HEAP h) return ( 0==h->heapnum ); } +/** \brief deletes the first item in the heap, and balances the rest + */ static void heap_delete (HEAP h) -{ /* deletes the first item in the heap, and balances the rest */ +{ int cur = 1, child = 2; h->heap[1] = 0; /* been deleted */ heap_swap (h, 1, h->heapnum--); @@ -183,9 +188,12 @@ static void heap_delete (HEAP h) } } +/** \brief puts item into heap. + The heap root element has changed value (to bigger) + Swap downwards until the heap is ordered again +*/ static void heap_balance (HEAP h) -{ /* The heap root element has changed value (to bigger) */ - /* swap downwards until the heap is ordered again */ +{ int cur = 1, child = 2; while (child <= h->heapnum) { if (child < h->heapnum && heap_cmp(h,child,1+child)>0 ) @@ -245,10 +253,12 @@ static void heap_destroy (HEAP h) /* nothing to delete, all is nmem'd, and will go away in due time */ } +/** \brief compare and items for quicksort + used in qsort to get the multi-and args in optimal order + that is, those with fewest occurrences first +*/ int compare_ands(const void *x, const void *y) -{ /* used in qsort to get the multi-and args in optimal order */ - /* that is, those with fewest occurrences first */ - const struct heap_item *hx = x; +{ const struct heap_item *hx = x; const struct heap_item *hy = y; double cur, totx, toty; rset_pos(hx->fd, &cur, &totx); @@ -260,8 +270,6 @@ int compare_ands(const void *x, const void *y) return 0; /* return totx - toty, except for overflows and rounding */ } -/* Creating and deleting rsets ***********************/ - static RSET rsmulti_andor_create(NMEM nmem, struct rset_key_control *kcontrol, int scope, TERMID termid, @@ -282,15 +290,15 @@ static RSET rsmulti_andor_create(NMEM nmem, return rnew; } -RSET rsmulti_or_create(NMEM nmem, struct rset_key_control *kcontrol, - int scope, TERMID termid, int no_rsets, RSET* rsets) +RSET rset_create_or(NMEM nmem, struct rset_key_control *kcontrol, + int scope, TERMID termid, int no_rsets, RSET* rsets) { return rsmulti_andor_create(nmem, kcontrol, scope, termid, no_rsets, rsets, &control_or); } -RSET rsmulti_and_create(NMEM nmem, struct rset_key_control *kcontrol, - int scope, int no_rsets, RSET* rsets) +RSET rset_create_and(NMEM nmem, struct rset_key_control *kcontrol, + int scope, int no_rsets, RSET* rsets) { return rsmulti_andor_create(nmem, kcontrol, scope, 0, no_rsets, rsets, &control_and); @@ -300,8 +308,6 @@ static void r_delete (RSET ct) { } -/* Opening and closing fd's on them *********************/ - static RSFD r_open_andor (RSET ct, int flag, int is_and) { RSFD rfd; @@ -322,7 +328,8 @@ static RSFD r_open_andor (RSET ct, int flag, int is_and) assert(p->items); /* all other pointers shouls already be allocated, in right sizes! */ } - else { + else + { p = (struct rfd_private *) nmem_malloc (ct->nmem,sizeof(*p)); rfd->priv = p; p->h = 0; @@ -352,7 +359,8 @@ static RSFD r_open_andor (RSET ct, int flag, int is_and) p->tailbits[i] = 0; } qsort(p->items, ct->no_children, sizeof(p->items[0]), compare_ands); - } else + } + else { /* fill the heap for ORing */ for (i = 0; ino_children; i++){ p->items[i].fd = rset_open(ct->children[i],RSETF_READ); @@ -386,8 +394,6 @@ static void r_close (RSFD rfd) rset_close(p->items[i].fd); } - - static int r_forward_or(RSFD rfd, void *buf, TERMID *term, const void *untilbuf) { /* while heap head behind untilbuf, forward it and rebalance heap */ @@ -412,6 +418,13 @@ static int r_forward_or(RSFD rfd, void *buf, } +/** \brief reads one item key from an 'or' set + \param rfd set handle + \param buf resulting item buffer + \param term resulting term + \retval 0 EOF + \retval 1 item could be read +*/ static int r_read_or (RSFD rfd, void *buf, TERMID *term) { RSET rset = rfd->rset; @@ -429,7 +442,6 @@ static int r_read_or (RSFD rfd, void *buf, TERMID *term) *term = rset->term; else *term = it->term; - assert(*term); } (mrfd->hits)++; rdres = rset_read(it->fd, it->buf, &it->term); @@ -441,34 +453,57 @@ static int r_read_or (RSFD rfd, void *buf, TERMID *term) } +/** \brief reads one item key from an 'and' set + \param rfd set handle + \param buf resulting item buffer + \param term resulting term + \retval 0 EOF + \retval 1 item could be read + + Has to return all hits where each item points to the + same sysno (scope), in order. Keep an extra key (hitkey) + as long as all records do not point to hitkey, forward + them, and update hitkey to be the highest seen so far. + (if any item eof's, mark eof, and return 0 thereafter) + Once a hit has been found, scan all items for the smallest + value. Mark all as being in the tail. Read next from that + item, and if not in the same record, clear its tail bit +*/ static int r_read_and (RSFD rfd, void *buf, TERMID *term) -{ /* Has to return all hits where each item points to the */ - /* same sysno (scope), in order. Keep an extra key (hitkey) */ - /* as long as all records do not point to hitkey, forward */ - /* them, and update hitkey to be the highest seen so far. */ - /* (if any item eof's, mark eof, and return 0 thereafter) */ - /* Once a hit has been found, scan all items for the smallest */ - /* value. Mark all as being in the tail. Read next from that */ - /* item, and if not in the same record, clear its tail bit */ - struct rfd_private *p = rfd->priv; +{ struct rfd_private *p = rfd->priv; RSET ct = rfd->rset; const struct rset_key_control *kctrl = ct->keycontrol; - int i, mintail; - int cmp; + int i; while (1) { if (p->tailcount) { /* we are tailing, find lowest tail and return it */ - mintail = 0; - while ((mintailno_children) && !p->tailbits[mintail]) - mintail++; /* first tail */ - for (i = mintail+1; ino_children; i++) + int mintail = -1; + int cmp; + + for (i = 0; ino_children; i++) { if (p->tailbits[i]) { - cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf); - if (cmp<0) + if (mintail >= 0) + cmp = (*kctrl->cmp) + (p->items[i].buf, p->items[mintail].buf); + else + cmp = -1; + if (cmp < 0) mintail = i; + + if (kctrl->get_segment) + { /* segments enabled */ + zint segment = kctrl->get_segment(p->items[i].buf); + /* store segment if not stored already */ + if (!p->segment && segment) + p->segment = segment; + + /* skip rest entirely if segments don't match */ + if (p->segment && segment && p->segment != segment) + p->skip = 1; + } } } /* return the lowest tail */ @@ -481,25 +516,30 @@ static int r_read_and (RSFD rfd, void *buf, TERMID *term) p->eof = 1; /* game over, once tails have been returned */ p->tailbits[mintail] = 0; (p->tailcount)--; - (p->hits)++; - return 1; } - /* still a tail? */ - cmp = (*kctrl->cmp)(p->items[mintail].buf,buf); - if (cmp >= rfd->rset->scope){ - p->tailbits[mintail] = 0; - (p->tailcount)--; + else + { + /* still a tail? */ + cmp = (*kctrl->cmp)(p->items[mintail].buf,buf); + if (cmp >= rfd->rset->scope) + { + p->tailbits[mintail] = 0; + (p->tailcount)--; + } } + if (p->skip) + continue; /* skip again.. eventually tailcount will be 0 */ (p->hits)++; return 1; } - /* not tailing, forward until all reocrds match, and set up */ + /* not tailing, forward until all records match, and set up */ /* as tails. the earlier 'if' will then return the hits */ if (p->eof) return 0; /* nothing more to see */ i = 1; /* assume items[0] is highest up */ - while (ino_children) { - cmp = (*kctrl->cmp)(p->items[0].buf, p->items[i].buf); + while (i < ct->no_children) + { + int cmp = (*kctrl->cmp)(p->items[0].buf, p->items[i].buf); if (cmp <= -rfd->rset->scope) { /* [0] was behind, forward it */ if (!rset_forward(p->items[0].fd, p->items[0].buf, &p->items[0].term, p->items[i].buf)) @@ -507,8 +547,9 @@ static int r_read_and (RSFD rfd, void *buf, TERMID *term) p->eof = 1; /* game over */ return 0; } - i = 0; /* start frowarding from scratch */ - } else if (cmp>=rfd->rset->scope) + i = 0; /* start forwarding from scratch */ + } + else if (cmp>=rfd->rset->scope) { /* [0] was ahead, forward i */ if (!rset_forward(p->items[i].fd, p->items[i].buf, &p->items[i].term, p->items[0].buf)) @@ -516,15 +557,18 @@ static int r_read_and (RSFD rfd, void *buf, TERMID *term) p->eof = 1; /* game over */ return 0; } - } else + } + else i++; } /* while i */ /* if we get this far, all rsets are now within +- scope of [0] */ /* ergo, we have a hit. Mark them all as tailing, and let the */ /* upper 'if' return the hits in right order */ - for (i = 0; ino_children; i++) + for (i = 0; i < ct->no_children; i++) p->tailbits[i] = 1; p->tailcount = ct->no_children; + p->segment = 0; + p->skip = 0; } /* while 1 */ } @@ -622,3 +666,11 @@ static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm) } +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ +