rset/rsmultiandor.c

   1 /* $Id: rsmultiandor.c,v 1.19 2005-05-24 11:35:43 adam Exp $
   2    Copyright (C) 1995-2005
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24 /*
  25  * This module implements the rsmulti_or and rsmulti_and result sets
  26  *
  27  * rsmultior is based on a heap, from which we find the next hit.
  28  *
  29  * rsmultiand is based on a simple array of rsets, and a linear
  30  * search to find the record that exists in all of those rsets.
  31  * To speed things up, the array is sorted so that the smallest
  32  * rsets come first, they are most likely to have the hits furthest
  33  * away, and thus forwarding to them makes the most sense.
  34  */
  35
  36
  37 #include <assert.h>
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include <idzebra/util.h>
  43 #include <idzebra/isamc.h>
  44 #include <rset.h>
  45
  46 static RSFD r_open_and (RSET ct, int flag);
  47 static RSFD r_open_or (RSET ct, int flag);
  48 static void r_close (RSFD rfd);
  49 static void r_delete (RSET ct);
  50 static int r_read_and (RSFD rfd, void *buf, TERMID *term);
  51 static int r_read_or (RSFD rfd, void *buf, TERMID *term);
  52 static int r_write (RSFD rfd, const void *buf);
  53 static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
  54                      const void *untilbuf);
  55 static int r_forward_or(RSFD rfd, void *buf, TERMID *term,
  56                      const void *untilbuf);
  57 static void r_pos (RSFD rfd, double *current, double *total);
  58 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm);
  59
  60 static const struct rset_control control_or =
  61 {
  62     "multi-or",
  63     r_delete,
  64     r_get_terms,
  65     r_open_or,
  66     r_close,
  67     r_forward_or,
  68     r_pos,
  69     r_read_or,
  70     r_write,
  71 };
  72
  73 static const struct rset_control control_and =
  74 {
  75     "multi-and",
  76     r_delete,
  77     r_get_terms,
  78     r_open_and,
  79     r_close,
  80     r_forward_and,
  81     r_pos,
  82     r_read_and,
  83     r_write,
  84 };
  85
  86 /* The heap structure:
  87  * The rset contains a list or rsets we are ORing together
  88  * The rfd contains a heap of heap-items, which contain
  89  * a rfd opened to those rsets, and a buffer for one key.
  90  * They also contain a ptr to the rset list in the rset
  91  * itself, for practical reasons.
  92  */
  93
  94 struct heap_item {
  95     RSFD fd;
  96     void *buf;
  97     RSET rset;
  98     TERMID term;
  99 };
 100
 101 struct heap {
 102     int heapnum;
 103     int heapmax;
 104     const struct rset_key_control *kctrl;
 105     struct heap_item **heap; /* ptrs to the rfd */
 106 };
 107 typedef struct heap *HEAP;
 108
 109
 110 struct rset_private {
 111     int dummy;
 112 };
 113
 114
 115 struct rfd_private {
 116     int flag;
 117     struct heap_item *items; /* we alloc and free them here */
 118     HEAP h; /* and move around here */
 119     zint hits; /* returned so far */
 120     int eof; /* seen the end of it */
 121     int tailcount; /* how many items are tailing */
 122     char *tailbits;
 123 };
 124
 125 static int log_level = 0;
 126 static int log_level_initialized = 0;
 127
 128
 129 /* Heap functions ***********************/
 130
 131 #if 0
 132 static void heap_dump_item( HEAP h, int i, int level)
 133 {
 134     double cur,tot;
 135     if (i>h->heapnum)
 136         return;
 137     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 138     yaz_log(log_level," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 139                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 140     heap_dump_item(h, 2*i, level+1);
 141     heap_dump_item(h, 2*i+1, level+1);
 142 }
 143 static void heap_dump( HEAP h,char *msg) {
 144     yaz_log(log_level, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 145     heap_dump_item(h,1,1);
 146 }
 147 #endif
 148
 149 static void heap_swap (HEAP h, int x, int y)
 150 {
 151     struct heap_item *swap;
 152     swap = h->heap[x];
 153     h->heap[x] = h->heap[y];
 154     h->heap[y] = swap;
 155 }
 156
 157 static int heap_cmp(HEAP h, int x, int y)
 158 {
 159     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 160 }
 161
 162 static int heap_empty(HEAP h)
 163 {
 164     return ( 0==h->heapnum );
 165 }
 166
 167 static void heap_delete (HEAP h)
 168 { /* deletes the first item in the heap, and balances the rest */
 169     int cur = 1, child = 2;
 170     h->heap[1] = 0; /* been deleted */
 171     heap_swap (h, 1, h->heapnum--);
 172     while (child <= h->heapnum) {
 173         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 174             child++;
 175         if (heap_cmp(h,cur,child) > 0)
 176         {
 177             heap_swap (h, cur, child);
 178             cur = child;
 179             child = 2*cur;
 180         }
 181         else
 182             break;
 183     }
 184 }
 185
 186 static void heap_balance (HEAP h)
 187 { /* The heap root element has changed value (to bigger) */
 188   /* swap downwards until the heap is ordered again */
 189     int cur = 1, child = 2;
 190     while (child <= h->heapnum) {
 191         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 192             child++;
 193         if (heap_cmp(h,cur,child) > 0)
 194         {
 195             heap_swap (h, cur, child);
 196             cur = child;
 197             child = 2*cur;
 198         }
 199         else
 200             break;
 201     }
 202 }
 203
 204
 205 static void heap_insert (HEAP h, struct heap_item *hi)
 206 {
 207     int cur, parent;
 208
 209     cur = ++(h->heapnum);
 210     assert(cur <= h->heapmax);
 211     h->heap[cur] = hi;
 212     parent = cur/2;
 213     while (parent && (heap_cmp(h,parent,cur) > 0))
 214     {
 215         assert(parent>0);
 216         heap_swap (h, cur, parent);
 217         cur = parent;
 218         parent = cur/2;
 219     }
 220 }
 221
 222
 223 static
 224 HEAP heap_create (NMEM nmem, int size, const struct rset_key_control *kctrl)
 225 {
 226     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
 227
 228     ++size; /* heap array starts at 1 */
 229     h->heapnum = 0;
 230     h->heapmax = size;
 231     h->kctrl = kctrl;
 232     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
 233     h->heap[0]=0; /* not used */
 234     return h;
 235 }
 236
 237 static void heap_clear( HEAP h)
 238 {
 239     assert(h);
 240     h->heapnum = 0;
 241 }
 242
 243 static void heap_destroy (HEAP h)
 244 {
 245     /* nothing to delete, all is nmem'd, and will go away in due time */
 246 }
 247
 248 int compare_ands(const void *x, const void *y)
 249 { /* used in qsort to get the multi-and args in optimal order */
 250   /* that is, those with fewest occurrences first */
 251     const struct heap_item *hx = x;
 252     const struct heap_item *hy = y;
 253     double cur, totx, toty;
 254     rset_pos(hx->fd, &cur, &totx);
 255     rset_pos(hy->fd, &cur, &toty);
 256     if ( totx > toty +0.5 )
 257         return 1;
 258     if ( totx < toty -0.5 )
 259         return -1;
 260     return 0;  /* return totx - toty, except for overflows and rounding */
 261 }
 262
 263 /* Creating and deleting rsets ***********************/
 264
 265 static RSET rsmulti_andor_create(NMEM nmem,
 266                                  struct rset_key_control *kcontrol,
 267                                  int scope, TERMID termid,
 268                                  int no_rsets, RSET* rsets,
 269                                  const struct rset_control *ctrl)
 270 {
 271     RSET rnew = rset_create_base(ctrl, nmem, kcontrol, scope, termid,
 272                                  no_rsets, rsets);
 273     struct rset_private *info;
 274     if (!log_level_initialized)
 275     {
 276         log_level = yaz_log_module_level("rsmultiandor");
 277         log_level_initialized = 1;
 278     }
 279     yaz_log(log_level, "rsmultiand_andor_create scope=%d", scope);
 280     info = (struct rset_private *) nmem_malloc(rnew->nmem, sizeof(*info));
 281     rnew->priv = info;
 282     return rnew;
 283 }
 284
 285 RSET rsmulti_or_create(NMEM nmem, struct rset_key_control *kcontrol,
 286                        int scope, TERMID termid, int no_rsets, RSET* rsets)
 287 {
 288     return rsmulti_andor_create(nmem, kcontrol, scope, termid,
 289                                 no_rsets, rsets, &control_or);
 290 }
 291
 292 RSET rsmulti_and_create(NMEM nmem, struct rset_key_control *kcontrol,
 293                         int scope, int no_rsets, RSET* rsets)
 294 {
 295     return rsmulti_andor_create(nmem, kcontrol, scope, 0,
 296                                 no_rsets, rsets, &control_and);
 297 }
 298
 299 static void r_delete (RSET ct)
 300 {
 301 }
 302
 303 /* Opening and closing fd's on them *********************/
 304
 305 static RSFD r_open_andor (RSET ct, int flag, int is_and)
 306 {
 307     RSFD rfd;
 308     struct rfd_private *p;
 309     const struct rset_key_control *kctrl = ct->keycontrol;
 310     int i;
 311
 312     if (flag & RSETF_WRITE)
 313     {
 314         yaz_log (YLOG_FATAL, "multiandor set type is read-only");
 315         return NULL;
 316     }
 317     rfd = rfd_create_base(ct);
 318     if (rfd->priv) {
 319         p = (struct rfd_private *)rfd->priv;
 320         if (!is_and)
 321             heap_clear(p->h);
 322         assert(p->items);
 323         /* all other pointers shouls already be allocated, in right sizes! */
 324     }
 325     else {
 326         p = (struct rfd_private *) nmem_malloc (ct->nmem,sizeof(*p));
 327         rfd->priv = p;
 328         p->h = 0;
 329         p->tailbits = 0;
 330         if (is_and)
 331             p->tailbits = nmem_malloc(ct->nmem, ct->no_children*sizeof(char) );
 332         else
 333             p->h = heap_create( ct->nmem, ct->no_children, kctrl);
 334         p->items = (struct heap_item *)
 335             nmem_malloc(ct->nmem, ct->no_children*sizeof(*p->items));
 336         for (i = 0; i<ct->no_children; i++)
 337         {
 338             p->items[i].rset = ct->children[i];
 339             p->items[i].buf = nmem_malloc(ct->nmem, kctrl->key_size);
 340         }
 341     }
 342     p->flag = flag;
 343     p->hits = 0;
 344     p->eof = 0;
 345     p->tailcount = 0;
 346     if (is_and)
 347     { /* read the array and sort it */
 348         for (i = 0; i<ct->no_children; i++){
 349             p->items[i].fd = rset_open(ct->children[i], RSETF_READ);
 350             if (!rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 351                 p->eof = 1;
 352             p->tailbits[i] = 0;
 353         }
 354         qsort(p->items, ct->no_children, sizeof(p->items[0]), compare_ands);
 355     } else
 356     { /* fill the heap for ORing */
 357         for (i = 0; i<ct->no_children; i++){
 358             p->items[i].fd = rset_open(ct->children[i],RSETF_READ);
 359             if ( rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 360                 heap_insert(p->h, &(p->items[i]));
 361         }
 362     }
 363     return rfd;
 364 }
 365
 366 static RSFD r_open_or (RSET ct, int flag)
 367 {
 368     return r_open_andor(ct, flag, 0);
 369 }
 370
 371 static RSFD r_open_and (RSET ct, int flag)
 372 {
 373     return r_open_andor(ct, flag, 1);
 374 }
 375
 376
 377 static void r_close (RSFD rfd)
 378 {
 379     struct rfd_private *p=(struct rfd_private *)(rfd->priv);
 380     int i;
 381
 382     if (p->h)
 383         heap_destroy (p->h);
 384     for (i = 0; i<rfd->rset->no_children; i++)
 385         if (p->items[i].fd)
 386             rset_close(p->items[i].fd);
 387 }
 388
 389
 390
 391 static int r_forward_or(RSFD rfd, void *buf,
 392                         TERMID *term, const void *untilbuf)
 393 { /* while heap head behind untilbuf, forward it and rebalance heap */
 394     struct rfd_private *p = rfd->priv;
 395     const struct rset_key_control *kctrl = rfd->rset->keycontrol;
 396     if (heap_empty(p->h))
 397         return 0;
 398     while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
 399     {
 400         if (rset_forward(p->h->heap[1]->fd,p->h->heap[1]->buf,
 401                          &p->h->heap[1]->term, untilbuf))
 402             heap_balance(p->h);
 403         else
 404         {
 405             heap_delete(p->h);
 406             if (heap_empty(p->h))
 407                 return 0;
 408         }
 409
 410     }
 411     return r_read_or(rfd, buf, term);
 412 }
 413
 414
 415 static int r_read_or (RSFD rfd, void *buf, TERMID *term)
 416 {
 417     RSET rset = rfd->rset;
 418     struct rfd_private *mrfd = rfd->priv;
 419     const struct rset_key_control *kctrl = rset->keycontrol;
 420     struct heap_item *it;
 421     int rdres;
 422     if (heap_empty(mrfd->h))
 423         return 0;
 424     it = mrfd->h->heap[1];
 425     memcpy(buf, it->buf, kctrl->key_size);
 426     if (term)
 427     {
 428         if (rset->term)
 429             *term = rset->term;
 430         else
 431             *term = it->term;
 432         assert(*term);
 433     }
 434     (mrfd->hits)++;
 435     rdres = rset_read(it->fd, it->buf, &it->term);
 436     if ( rdres )
 437         heap_balance(mrfd->h);
 438     else
 439         heap_delete(mrfd->h);
 440     return 1;
 441
 442 }
 443
 444 static int r_read_and (RSFD rfd, void *buf, TERMID *term)
 445 { /* Has to return all hits where each item points to the */
 446   /* same sysno (scope), in order. Keep an extra key (hitkey) */
 447   /* as long as all records do not point to hitkey, forward */
 448   /* them, and update hitkey to be the highest seen so far. */
 449   /* (if any item eof's, mark eof, and return 0 thereafter) */
 450   /* Once a hit has been found, scan all items for the smallest */
 451   /* value. Mark all as being in the tail. Read next from that */
 452   /* item, and if not in the same record, clear its tail bit */
 453     struct rfd_private *p = rfd->priv;
 454     RSET ct = rfd->rset;
 455     const struct rset_key_control *kctrl = ct->keycontrol;
 456     int i, mintail;
 457     int cmp;
 458
 459     while (1) {
 460         if (p->tailcount)
 461         { /* we are tailing, find lowest tail and return it */
 462             mintail = 0;
 463             while ((mintail<ct->no_children) && !p->tailbits[mintail])
 464                 mintail++; /* first tail */
 465             for (i = mintail+1; i<ct->no_children; i++)
 466             {
 467                 if (p->tailbits[i])
 468                 {
 469                     cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf);
 470                     if (cmp<0)
 471                         mintail = i;
 472                 }
 473             }
 474             /* return the lowest tail */
 475             memcpy(buf, p->items[mintail].buf, kctrl->key_size);
 476             if (term)
 477                 *term = p->items[mintail].term;
 478             if (!rset_read(p->items[mintail].fd, p->items[mintail].buf,
 479                            &p->items[mintail].term))
 480             {
 481                 p->eof = 1; /* game over, once tails have been returned */
 482                 p->tailbits[mintail] = 0;
 483                 (p->tailcount)--;
 484                 (p->hits)++;
 485                 return 1;
 486             }
 487             /* still a tail? */
 488             cmp = (*kctrl->cmp)(p->items[mintail].buf,buf);
 489             if (cmp >= rfd->rset->scope){
 490                 p->tailbits[mintail] = 0;
 491                 (p->tailcount)--;
 492             }
 493             (p->hits)++;
 494             return 1;
 495         }
 496         /* not tailing, forward until all reocrds match, and set up */
 497         /* as tails. the earlier 'if' will then return the hits */
 498         if (p->eof)
 499             return 0; /* nothing more to see */
 500         i = 1; /* assume items[0] is highest up */
 501         while (i<ct->no_children) {
 502             cmp = (*kctrl->cmp)(p->items[0].buf, p->items[i].buf);
 503             if (cmp <= -rfd->rset->scope) { /* [0] was behind, forward it */
 504                 if (!rset_forward(p->items[0].fd, p->items[0].buf,
 505                                   &p->items[0].term, p->items[i].buf))
 506                 {
 507                     p->eof = 1; /* game over */
 508                     return 0;
 509                 }
 510                 i = 0; /* start frowarding from scratch */
 511             } else if (cmp>=rfd->rset->scope)
 512             { /* [0] was ahead, forward i */
 513                 if (!rset_forward(p->items[i].fd, p->items[i].buf,
 514                                   &p->items[i].term, p->items[0].buf))
 515                 {
 516                     p->eof = 1; /* game over */
 517                     return 0;
 518                 }
 519             } else
 520                 i++;
 521         } /* while i */
 522         /* if we get this far, all rsets are now within +- scope of [0] */
 523         /* ergo, we have a hit. Mark them all as tailing, and let the */
 524         /* upper 'if' return the hits in right order */
 525         for (i = 0; i<ct->no_children; i++)
 526             p->tailbits[i] = 1;
 527         p->tailcount = ct->no_children;
 528     } /* while 1 */
 529 }
 530
 531
 532 static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
 533                          const void *untilbuf)
 534 {
 535     struct rfd_private *p = rfd->priv;
 536     RSET ct = rfd->rset;
 537     const struct rset_key_control *kctrl = ct->keycontrol;
 538     int i;
 539     int cmp;
 540     int killtail = 0;
 541
 542     for (i = 0; i<ct->no_children; i++)
 543     {
 544         cmp = (*kctrl->cmp)(p->items[i].buf,untilbuf);
 545         if (cmp <= -rfd->rset->scope)
 546         {
 547             killtail = 1; /* we are moving to a different hit */
 548             if (!rset_forward(p->items[i].fd, p->items[i].buf,
 549                               &p->items[i].term, untilbuf))
 550             {
 551                 p->eof = 1; /* game over */
 552                 p->tailcount = 0;
 553                 return 0;
 554             }
 555         }
 556     }
 557     if (killtail)
 558     {
 559         for (i = 0; i<ct->no_children; i++)
 560             p->tailbits[i] = 0;
 561         p->tailcount = 0;
 562     }
 563     return r_read_and(rfd,buf,term);
 564 }
 565
 566 static void r_pos (RSFD rfd, double *current, double *total)
 567 {
 568     RSET ct = rfd->rset;
 569     struct rfd_private *mrfd =
 570         (struct rfd_private *)(rfd->priv);
 571     double cur, tot;
 572     double scur = 0.0, stot = 0.0;
 573     int i;
 574     for (i = 0; i<ct->no_children; i++){
 575         rset_pos(mrfd->items[i].fd, &cur, &tot);
 576         yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 577         scur += cur;
 578         stot += tot;
 579     }
 580     if (stot < 1.0) { /* nothing there */
 581         *current = 0;
 582         *total = 0;
 583         yaz_log(log_level, "r_pos: NULL  %0.1f %0.1f",  *current, *total);
 584     }
 585     else
 586     {
 587         *current = (double) (mrfd->hits);
 588         *total = *current*stot/scur;
 589         yaz_log(log_level, "r_pos: =  %0.1f %0.1f",  *current, *total);
 590     }
 591 }
 592
 593 static int r_write (RSFD rfd, const void *buf)
 594 {
 595     yaz_log (YLOG_FATAL, "multior set type is read-only");
 596     return -1;
 597 }
 598
 599 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm)
 600 {
 601     if (ct->term)
 602         rset_get_one_term(ct, terms, maxterms, curterm);
 603     else
 604     {
 605         /* Special case: Some multi-ors have all terms pointing to the same
 606            term. We do not want to duplicate those. Other multiors (and ands)
 607            have different terms under them. Those we want.
 608         */
 609         int firstterm= *curterm;
 610         int i;
 611
 612         for (i = 0; i<ct->no_children; i++)
 613         {
 614             rset_getterms(ct->children[i], terms, maxterms, curterm);
 615             if ( ( *curterm > firstterm+1 ) &&
 616                  ( *curterm <= maxterms ) &&
 617                  ( terms[(*curterm)-1] == terms[firstterm] )
 618                 )
 619                 (*curterm)--; /* forget the term, seen that before */
 620         }
 621     }
 622 }
 623
 624