-/* $Id: rsmultiandor.c,v 1.27 2007-01-15 15:10:19 adam Exp $
- Copyright (C) 1995-2007
- Index Data ApS
-
-This file is part of the Zebra server.
+/* This file is part of the Zebra server.
+ Copyright (C) 1994-2011 Index Data
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
*/
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <idzebra/isamc.h>
#include <rset.h>
-static RSFD r_open_and (RSET ct, int flag);
-static RSFD r_open_or (RSET ct, int flag);
-static void r_close (RSFD rfd);
-static void r_delete (RSET ct);
-static int r_read_and (RSFD rfd, void *buf, TERMID *term);
-static int r_read_or (RSFD rfd, void *buf, TERMID *term);
-static int r_write (RSFD rfd, const void *buf);
+static RSFD r_open_and(RSET ct, int flag);
+static RSFD r_open_or(RSET ct, int flag);
+static void r_close(RSFD rfd);
+static void r_delete(RSET ct);
+static int r_read_and(RSFD rfd, void *buf, TERMID *term);
+static int r_read_or(RSFD rfd, void *buf, TERMID *term);
+static int r_write(RSFD rfd, const void *buf);
static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
const void *untilbuf);
static int r_forward_or(RSFD rfd, void *buf, TERMID *term,
const void *untilbuf);
-static void r_pos (RSFD rfd, double *current, double *total);
+static void r_pos_and(RSFD rfd, double *current, double *total);
+static void r_pos_or(RSFD rfd, double *current, double *total);
static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm);
-static const struct rset_control control_or =
+static const struct rset_control control_or =
{
"multi-or",
r_delete,
r_open_or,
r_close,
r_forward_or,
- r_pos,
+ r_pos_or,
r_read_or,
r_write,
};
-static const struct rset_control control_and =
+static const struct rset_control control_and =
{
"multi-and",
r_delete,
r_open_and,
r_close,
r_forward_and,
- r_pos,
+ r_pos_and,
r_read_and,
r_write,
};
-/* The heap structure:
- * The rset contains a list or rsets we are ORing together
+/* The heap structure:
+ * The rset contains a list or rsets we are ORing together
* The rfd contains a heap of heap-items, which contain
* a rfd opened to those rsets, and a buffer for one key.
- * They also contain a ptr to the rset list in the rset
- * itself, for practical reasons.
+ * They also contain a ptr to the rset list in the rset
+ * itself, for practical reasons.
*/
struct heap_item {
int dummy;
};
-
struct rfd_private {
int flag;
struct heap_item *items; /* we alloc and free them here */
static int log_level = 0;
static int log_level_initialized = 0;
-
/* Heap functions ***********************/
-#if 0
-static void heap_dump_item( HEAP h, int i, int level)
-{
- double cur,tot;
- if (i>h->heapnum)
- return;
- (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
- yaz_log(log_level," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
- &(h->heap[i]), h->heap[i]->buf, cur,tot );
- heap_dump_item(h, 2*i, level+1);
- heap_dump_item(h, 2*i+1, level+1);
-}
-static void heap_dump( HEAP h,char *msg) {
- yaz_log(log_level, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
- heap_dump_item(h,1,1);
-}
-#endif
-
-static void heap_swap (HEAP h, int x, int y)
+static void heap_swap(HEAP h, int x, int y)
{
struct heap_item *swap;
swap = h->heap[x];
static int heap_cmp(HEAP h, int x, int y)
{
- return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
+ return (*h->kctrl->cmp)(h->heap[x]->buf, h->heap[y]->buf);
}
static int heap_empty(HEAP h)
{
- return ( 0==h->heapnum );
+ return 0 == h->heapnum;
}
-/** \brief deletes the first item in the heap, and balances the rest
+/** \brief deletes the first item in the heap, and balances the rest
*/
-static void heap_delete (HEAP h)
+static void heap_delete(HEAP h)
{
int cur = 1, child = 2;
h->heap[1] = 0; /* been deleted */
- heap_swap (h, 1, h->heapnum--);
- while (child <= h->heapnum) {
- if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
+ heap_swap(h, 1, h->heapnum--);
+ while (child <= h->heapnum)
+ {
+ if (child < h->heapnum && heap_cmp(h, child, 1 + child) > 0)
child++;
if (heap_cmp(h,cur,child) > 0)
{
- heap_swap (h, cur, child);
+ heap_swap(h, cur, child);
cur = child;
child = 2*cur;
}
}
/** \brief puts item into heap.
- The heap root element has changed value (to bigger)
- Swap downwards until the heap is ordered again
+ The heap root element has changed value (to bigger)
+ Swap downwards until the heap is ordered again
*/
-static void heap_balance (HEAP h)
+static void heap_balance(HEAP h)
{
int cur = 1, child = 2;
- while (child <= h->heapnum) {
- if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
+ while (child <= h->heapnum)
+ {
+ if (child < h->heapnum && heap_cmp(h, child, 1 + child) > 0)
child++;
if (heap_cmp(h,cur,child) > 0)
{
- heap_swap (h, cur, child);
+ heap_swap(h, cur, child);
cur = child;
child = 2*cur;
}
}
}
-
-static void heap_insert (HEAP h, struct heap_item *hi)
+static void heap_insert(HEAP h, struct heap_item *hi)
{
int cur, parent;
while (parent && (heap_cmp(h,parent,cur) > 0))
{
assert(parent>0);
- heap_swap (h, cur, parent);
+ heap_swap(h, cur, parent);
cur = parent;
parent = cur/2;
}
}
-
static
-HEAP heap_create (NMEM nmem, int size, const struct rset_key_control *kctrl)
+HEAP heap_create(NMEM nmem, int size, const struct rset_key_control *kctrl)
{
- HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
+ HEAP h = (HEAP) nmem_malloc(nmem, sizeof(*h));
++size; /* heap array starts at 1 */
h->heapnum = 0;
h->heapmax = size;
h->kctrl = kctrl;
- h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
- h->heap[0]=0; /* not used */
+ h->heap = (struct heap_item**) nmem_malloc(nmem, size * sizeof(*h->heap));
+ h->heap[0] = 0; /* not used */
return h;
}
h->heapnum = 0;
}
-static void heap_destroy (HEAP h)
+static void heap_destroy(HEAP h)
{
/* nothing to delete, all is nmem'd, and will go away in due time */
}
double cur, totx, toty;
rset_pos(hx->fd, &cur, &totx);
rset_pos(hy->fd, &cur, &toty);
- if ( totx > toty +0.5 )
+ if (totx > toty + 0.5)
return 1;
- if ( totx < toty -0.5 )
+ if (totx < toty - 0.5)
return -1;
return 0; /* return totx - toty, except for overflows and rounding */
}
static RSET rsmulti_andor_create(NMEM nmem,
- struct rset_key_control *kcontrol,
+ struct rset_key_control *kcontrol,
int scope, TERMID termid,
- int no_rsets, RSET* rsets,
+ int no_rsets, RSET* rsets,
const struct rset_control *ctrl)
{
RSET rnew = rset_create_base(ctrl, nmem, kcontrol, scope, termid,
no_rsets, rsets, &control_and);
}
-static void r_delete (RSET ct)
+static void r_delete(RSET ct)
{
}
-static RSFD r_open_andor (RSET ct, int flag, int is_and)
+static RSFD r_open_andor(RSET ct, int flag, int is_and)
{
RSFD rfd;
struct rfd_private *p;
if (flag & RSETF_WRITE)
{
- yaz_log (YLOG_FATAL, "multiandor set type is read-only");
+ yaz_log(YLOG_FATAL, "multiandor set type is read-only");
return NULL;
}
rfd = rfd_create_base(ct);
- if (rfd->priv) {
+ if (rfd->priv)
+ {
p = (struct rfd_private *)rfd->priv;
if (!is_and)
heap_clear(p->h);
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));
+ p = (struct rfd_private *) nmem_malloc(ct->nmem,sizeof(*p));
rfd->priv = p;
p->h = 0;
p->tailbits = 0;
if (is_and)
p->tailbits = nmem_malloc(ct->nmem, ct->no_children*sizeof(char) );
- else
- p->h = heap_create( ct->nmem, ct->no_children, kctrl);
- p->items = (struct heap_item *)
+ else
+ p->h = heap_create(ct->nmem, ct->no_children, kctrl);
+ p->items = (struct heap_item *)
nmem_malloc(ct->nmem, ct->no_children*sizeof(*p->items));
- for (i = 0; i<ct->no_children; i++)
+ for (i = 0; i < ct->no_children; i++)
{
p->items[i].rset = ct->children[i];
p->items[i].buf = nmem_malloc(ct->nmem, kctrl->key_size);
p->tailcount = 0;
if (is_and)
{ /* read the array and sort it */
- for (i = 0; i<ct->no_children; i++){
+ for (i = 0; i < ct->no_children; i++)
+ {
p->items[i].fd = rset_open(ct->children[i], RSETF_READ);
if (!rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
p->eof = 1;
p->tailbits[i] = 0;
}
qsort(p->items, ct->no_children, sizeof(p->items[0]), compare_ands);
- }
+ }
else
{ /* fill the heap for ORing */
- for (i = 0; i<ct->no_children; i++){
+ for (i = 0; i < ct->no_children; i++)
+ {
p->items[i].fd = rset_open(ct->children[i],RSETF_READ);
if ( rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
heap_insert(p->h, &(p->items[i]));
return rfd;
}
-static RSFD r_open_or (RSET ct, int flag)
+static RSFD r_open_or(RSET ct, int flag)
{
return r_open_andor(ct, flag, 0);
}
-static RSFD r_open_and (RSET ct, int flag)
+static RSFD r_open_and(RSET ct, int flag)
{
return r_open_andor(ct, flag, 1);
}
-
-static void r_close (RSFD rfd)
+static void r_close(RSFD rfd)
{
struct rfd_private *p=(struct rfd_private *)(rfd->priv);
int i;
if (p->h)
- heap_destroy (p->h);
- for (i = 0; i<rfd->rset->no_children; i++)
+ heap_destroy(p->h);
+ for (i = 0; i < rfd->rset->no_children; i++)
if (p->items[i].fd)
rset_close(p->items[i].fd);
}
-static int r_forward_or(RSFD rfd, void *buf,
+static int r_forward_or(RSFD rfd, void *buf,
TERMID *term, const void *untilbuf)
{ /* while heap head behind untilbuf, forward it and rebalance heap */
struct rfd_private *p = rfd->priv;
const struct rset_key_control *kctrl = rfd->rset->keycontrol;
if (heap_empty(p->h))
return 0;
- while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
+ while ((*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
{
- if (rset_forward(p->h->heap[1]->fd,p->h->heap[1]->buf,
+ if (rset_forward(p->h->heap[1]->fd, p->h->heap[1]->buf,
&p->h->heap[1]->term, untilbuf))
heap_balance(p->h);
- else
+ else
{
heap_delete(p->h);
if (heap_empty(p->h))
return r_read_or(rfd, buf, term);
}
-
/** \brief reads one item key from an 'or' set
\param rfd set handle
\param buf resulting item buffer
\retval 0 EOF
\retval 1 item could be read
*/
-static int r_read_or (RSFD rfd, void *buf, TERMID *term)
+static int r_read_or(RSFD rfd, void *buf, TERMID *term)
{
RSET rset = rfd->rset;
struct rfd_private *mrfd = rfd->priv;
}
(mrfd->hits)++;
rdres = rset_read(it->fd, it->buf, &it->term);
- if ( rdres )
+ if (rdres)
heap_balance(mrfd->h);
else
heap_delete(mrfd->h);
return 1;
-
}
/** \brief reads one item key from an 'and' set
\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
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)
-{ struct rfd_private *p = rfd->priv;
+static int r_read_and(RSFD rfd, void *buf, TERMID *term)
+{
+ struct rfd_private *p = rfd->priv;
RSET ct = rfd->rset;
const struct rset_key_control *kctrl = ct->keycontrol;
int i;
- while (1) {
- if (p->tailcount)
+ while (1)
+ {
+ if (p->tailcount)
{ /* we are tailing, find lowest tail and return it */
int mintail = -1;
int cmp;
-
- for (i = 0; i<ct->no_children; i++)
+
+ for (i = 0; i < ct->no_children; i++)
{
if (p->tailbits[i])
{
/* 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 */
- memcpy(buf, p->items[mintail].buf, kctrl->key_size);
+ memcpy(buf, p->items[mintail].buf, kctrl->key_size);
if (term)
*term = p->items[mintail].term;
if (!rset_read(p->items[mintail].fd, p->items[mintail].buf,
&p->items[mintail].term))
{
p->eof = 1; /* game over, once tails have been returned */
- p->tailbits[mintail] = 0;
+ p->tailbits[mintail] = 0;
(p->tailcount)--;
}
else
}
if (p->skip)
continue; /* skip again.. eventually tailcount will be 0 */
- (p->hits)++;
+ if (p->tailcount == 0)
+ (p->hits)++;
return 1;
- }
+ }
/* 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 (i < ct->no_children)
+ 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,
+ if (!rset_forward(p->items[0].fd, p->items[0].buf,
&p->items[0].term, p->items[i].buf))
{
p->eof = 1; /* game over */
return 0;
}
i = 0; /* start forwarding from scratch */
- }
- else if (cmp>=rfd->rset->scope)
+ }
+ else if (cmp >= rfd->rset->scope)
{ /* [0] was ahead, forward i */
- if (!rset_forward(p->items[i].fd, p->items[i].buf,
+ if (!rset_forward(p->items[i].fd, p->items[i].buf,
&p->items[i].term, p->items[0].buf))
{
p->eof = 1; /* game over */
return 0;
}
- }
+ }
else
i++;
} /* while i */
}
-static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
+static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
const void *untilbuf)
-{
+{
struct rfd_private *p = rfd->priv;
RSET ct = rfd->rset;
const struct rset_key_control *kctrl = ct->keycontrol;
int cmp;
int killtail = 0;
- for (i = 0; i<ct->no_children; i++)
+ for (i = 0; i < ct->no_children; i++)
{
cmp = (*kctrl->cmp)(p->items[i].buf,untilbuf);
if (cmp <= -rfd->rset->scope)
{
killtail = 1; /* we are moving to a different hit */
- if (!rset_forward(p->items[i].fd, p->items[i].buf,
+ if (!rset_forward(p->items[i].fd, p->items[i].buf,
&p->items[i].term, untilbuf))
{
p->eof = 1; /* game over */
}
}
}
- if (killtail)
+ if (killtail)
{
- for (i = 0; i<ct->no_children; i++)
+ for (i = 0; i < ct->no_children; i++)
p->tailbits[i] = 0;
p->tailcount = 0;
}
return r_read_and(rfd,buf,term);
}
-static void r_pos (RSFD rfd, double *current, double *total)
+static void r_pos_x(RSFD rfd, double *current, double *total, int and_op)
{
RSET ct = rfd->rset;
- struct rfd_private *mrfd =
- (struct rfd_private *)(rfd->priv);
- double cur, tot;
- double scur = 0.0, stot = 0.0;
+ struct rfd_private *mrfd = (struct rfd_private *)(rfd->priv);
+ double ratio = and_op ? 0.0 : 1.0;
int i;
- for (i = 0; i<ct->no_children; i++){
+ double sum_cur = 0.0;
+ double sum_tot = 0.0;
+ for (i = 0; i < ct->no_children; i++)
+ {
+ double cur, tot;
rset_pos(mrfd->items[i].fd, &cur, &tot);
- yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot);
- scur += cur;
- stot += tot;
+ if (i < 100)
+ yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot);
+ if (and_op)
+ {
+ if (tot > 0.0)
+ {
+ double nratio = cur / tot;
+ if (nratio > ratio)
+ ratio = nratio;
+ }
+ }
+ else
+ {
+ if (cur > 0)
+ sum_cur += (cur - 1);
+ sum_tot += tot;
+ }
}
- if (stot < 1.0) { /* nothing there */
+ if (!and_op && sum_tot > 0.0)
+ {
+ yaz_log(YLOG_LOG, "or op sum_cur=%0.1f sum_tot=%0.1f hits=%f", sum_cur, sum_tot, (double) mrfd->hits);
+ ratio = sum_cur / sum_tot;
+ }
+ if (ratio == 0.0 || ratio == 1.0)
+ { /* nothing there */
*current = 0;
*total = 0;
yaz_log(log_level, "r_pos: NULL %0.1f %0.1f", *current, *total);
else
{
*current = (double) (mrfd->hits);
- *total = *current*stot/scur;
+ *total = *current / ratio;
yaz_log(log_level, "r_pos: = %0.1f %0.1f", *current, *total);
}
}
-static int r_write (RSFD rfd, const void *buf)
+static void r_pos_and(RSFD rfd, double *current, double *total)
{
- yaz_log (YLOG_FATAL, "multior set type is read-only");
+ r_pos_x(rfd, current, total, 1);
+}
+
+static void r_pos_or(RSFD rfd, double *current, double *total)
+{
+ r_pos_x(rfd, current, total, 0);
+}
+
+static int r_write(RSFD rfd, const void *buf)
+{
+ yaz_log(YLOG_FATAL, "multior set type is read-only");
return -1;
}
rset_get_one_term(ct, terms, maxterms, curterm);
else
{
- /* Special case: Some multi-ors have all terms pointing to the same
+ /* Special case: Some multi-ors have all terms pointing to the same
term. We do not want to duplicate those. Other multiors (and ands)
- have different terms under them. Those we want.
+ have different terms under them. Those we want.
*/
- int firstterm= *curterm;
+ int firstterm = *curterm;
int i;
-
- for (i = 0; i<ct->no_children; i++)
+ for (i = 0; i < ct->no_children; i++)
{
rset_getterms(ct->children[i], terms, maxterms, curterm);
- if ( ( *curterm > firstterm+1 ) &&
- ( *curterm <= maxterms ) &&
- ( terms[(*curterm)-1] == terms[firstterm] )
- )
+ if (*curterm > firstterm + 1 && *curterm <= maxterms &&
+ terms[(*curterm) - 1] == terms[firstterm])
(*curterm)--; /* forget the term, seen that before */
}
}
/*
* Local variables:
* c-basic-offset: 4
+ * c-file-style: "Stroustrup"
* indent-tabs-mode: nil
* End:
* vim: shiftwidth=4 tabstop=8 expandtab
projects / idzebra-moved-to-github.git / blobdiff