rset/rsmultiandor.c

   1 /* $Id: rsmultiandor.c,v 1.10 2004-11-19 10:27:14 heikki Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   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 rsmultior and rsmultiand 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 <zebrautl.h>
  43 #include <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 static const struct rset_control control_and =
  73 {
  74     "multi-and",
  75     r_delete,
  76     r_get_terms,
  77     r_open_and,
  78     r_close,
  79     r_forward_and,
  80     r_pos,
  81     r_read_and,
  82     r_write,
  83 };
  84
  85 const struct rset_control *rset_kind_multior = &control_or;
  86 const struct rset_control *rset_kind_multiand = &control_and;
  87
  88 /* The heap structure:
  89  * The rset contains a list or rsets we are ORing together
  90  * The rfd contains a heap of heap-items, which contain
  91  * a rfd opened to those rsets, and a buffer for one key.
  92  * They also contain a ptr to the rset list in the rset
  93  * itself, for practical reasons.
  94  */
  95
  96 struct heap_item {
  97     RSFD fd;
  98     void *buf;
  99     RSET rset;
 100     TERMID term;
 101 };
 102
 103 struct heap {
 104     int heapnum;
 105     int heapmax;
 106     const struct key_control *kctrl;
 107     struct heap_item **heap; /* ptrs to the rfd */
 108 };
 109 typedef struct heap *HEAP;
 110
 111
 112 struct rset_multiandor_info {
 113     int     no_rsets;
 114     RSET    *rsets;
 115 };
 116
 117
 118 struct rset_multiandor_rfd {
 119     int flag;
 120     struct heap_item *items; /* we alloc and free them here */
 121     HEAP h; /* and move around here */
 122     zint hits; /* returned so far */
 123     int eof; /* seen the end of it */
 124     int tailcount; /* how many items are tailing */
 125     char *tailbits;
 126 };
 127
 128 static int log_level=0;
 129 static int log_level_initialized=0;
 130
 131
 132 /* Heap functions ***********************/
 133
 134 #if 0
 135 static void heap_dump_item( HEAP h, int i, int level) {
 136     double cur,tot;
 137     if (i>h->heapnum)
 138         return;
 139     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 140     yaz_log(log_level," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 141                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 142     heap_dump_item(h, 2*i, level+1);
 143     heap_dump_item(h, 2*i+1, level+1);
 144 }
 145 static void heap_dump( HEAP h,char *msg) {
 146     yaz_log(log_level, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 147     heap_dump_item(h,1,1);
 148 }
 149 #endif
 150
 151 static void heap_swap (HEAP h, int x, int y)
 152 {
 153     struct heap_item *swap;
 154     swap = h->heap[x];
 155     h->heap[x]=h->heap[y];
 156     h->heap[y]=swap;
 157 }
 158
 159 static int heap_cmp(HEAP h, int x, int y)
 160 {
 161     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 162 }
 163
 164 static int heap_empty(HEAP h)
 165 {
 166     return ( 0==h->heapnum );
 167 }
 168
 169 static void heap_delete (HEAP h)
 170 { /* deletes the first item in the heap, and balances the rest */
 171     int cur = 1, child = 2;
 172     h->heap[1]=0; /* been deleted */
 173     heap_swap (h, 1, h->heapnum--);
 174     while (child <= h->heapnum) {
 175         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 176             child++;
 177         if (heap_cmp(h,cur,child) > 0)
 178         {
 179             heap_swap (h, cur, child);
 180             cur = child;
 181             child = 2*cur;
 182         }
 183         else
 184             break;
 185     }
 186 }
 187
 188 static void heap_balance (HEAP h)
 189 { /* The heap root element has changed value (to bigger) */
 190   /* swap downwards until the heap is ordered again */
 191     int cur = 1, child = 2;
 192     while (child <= h->heapnum) {
 193         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 194             child++;
 195         if (heap_cmp(h,cur,child) > 0)
 196         {
 197             heap_swap (h, cur, child);
 198             cur = child;
 199             child = 2*cur;
 200         }
 201         else
 202             break;
 203     }
 204 }
 205
 206
 207 static void heap_insert (HEAP h, struct heap_item *hi)
 208 {
 209     int cur, parent;
 210
 211     cur = ++(h->heapnum);
 212     assert(cur <= h->heapmax);
 213     h->heap[cur]=hi;
 214     parent = cur/2;
 215     while (parent && (heap_cmp(h,parent,cur) > 0))
 216     {
 217         assert(parent>0);
 218         heap_swap (h, cur, parent);
 219         cur = parent;
 220         parent = cur/2;
 221     }
 222 }
 223
 224
 225 static
 226 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
 227 {
 228     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
 229
 230     ++size; /* heap array starts at 1 */
 231     h->heapnum = 0;
 232     h->heapmax = size;
 233     h->kctrl=kctrl;
 234     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
 235     h->heap[0]=0; /* not used */
 236     return h;
 237 }
 238
 239 static void heap_clear( HEAP h)
 240 {
 241     assert(h);
 242     h->heapnum=0;
 243 }
 244
 245 static void heap_destroy (HEAP h)
 246 {
 247     /* nothing to delete, all is nmem'd, and will go away in due time */
 248 }
 249
 250 int compare_ands(const void *x, const void *y)
 251 { /* used in qsort to get the multi-and args in optimal order */
 252   /* that is, those with fewest occurrences first */
 253     const struct heap_item *hx=x;
 254     const struct heap_item *hy=y;
 255     double cur, totx, toty;
 256     rset_pos(hx->fd, &cur, &totx);
 257     rset_pos(hy->fd, &cur, &toty);
 258     if ( totx > toty +0.5 ) return 1;
 259     if ( totx < toty -0.5 ) 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, const struct key_control *kcontrol,
 266                            int scope, int no_rsets, RSET* rsets,
 267                            const struct rset_control *ctrl)
 268 {
 269     RSET rnew=rset_create_base(ctrl, nmem,kcontrol, scope,0);
 270     struct rset_multiandor_info *info;
 271     if (!log_level_initialized)
 272     {
 273         log_level=yaz_log_module_level("rsmultiandor");
 274         log_level_initialized=1;
 275     }
 276     info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
 277     info->no_rsets=no_rsets;
 278     info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
 279     memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
 280     rnew->priv=info;
 281     return rnew;
 282 }
 283
 284 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 285             int no_rsets, RSET* rsets)
 286 {
 287     return rsmulti_andor_create(nmem, kcontrol, scope,
 288                                 no_rsets, rsets, &control_or);
 289 }
 290
 291 RSET rsmultiand_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 292             int no_rsets, RSET* rsets)
 293 {
 294     return rsmulti_andor_create(nmem, kcontrol, scope,
 295                                 no_rsets, rsets, &control_and);
 296 }
 297
 298 static void r_delete (RSET ct)
 299 {
 300     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 301     int i;
 302     for(i=0;i<info->no_rsets;i++)
 303         rset_delete(info->rsets[i]);
 304 }
 305
 306
 307 /* Opening and closing fd's on them *********************/
 308
 309 static RSFD r_open_andor (RSET ct, int flag, int is_and)
 310 {
 311     RSFD rfd;
 312     struct rset_multiandor_rfd *p;
 313     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 314     const struct key_control *kctrl = ct->keycontrol;
 315     int i;
 316
 317     if (flag & RSETF_WRITE)
 318     {
 319         yaz_log (YLOG_FATAL, "multiandor set type is read-only");
 320         return NULL;
 321     }
 322     rfd=rfd_create_base(ct);
 323     if (rfd->priv) {
 324         p=(struct rset_multiandor_rfd *)rfd->priv;
 325         if (!is_and)
 326             heap_clear(p->h);
 327         assert(p->items);
 328         /* all other pointers shouls already be allocated, in right sizes! */
 329     }
 330     else {
 331         p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
 332         rfd->priv=p;
 333         p->h=0;
 334         p->tailbits=0;
 335         if (is_and)
 336             p->tailbits=nmem_malloc(ct->nmem, info->no_rsets*sizeof(char) );
 337         else
 338             p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
 339         p->items=(struct heap_item *) nmem_malloc(ct->nmem,
 340                               info->no_rsets*sizeof(*p->items));
 341         for (i=0; i<info->no_rsets; i++){
 342             p->items[i].rset=info->rsets[i];
 343             p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
 344         }
 345     }
 346     p->flag = flag;
 347     p->hits=0;
 348     p->eof=0;
 349     p->tailcount=0;
 350     if (is_and)
 351     { /* read the array and sort it */
 352         for (i=0; i<info->no_rsets; i++){
 353             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 354             if (!rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 355                 p->eof=1;
 356             p->tailbits[i]=0;
 357         }
 358         qsort(p->items, info->no_rsets, sizeof(p->items[0]), compare_ands);
 359     } else
 360     { /* fill the heap for ORing */
 361         for (i=0; i<info->no_rsets; i++){
 362             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 363             if ( rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 364                 heap_insert(p->h, &(p->items[i]));
 365         }
 366     }
 367     return rfd;
 368 }
 369
 370 static RSFD r_open_or (RSET ct, int flag)
 371 {
 372     return r_open_andor(ct, flag, 0);
 373 }
 374
 375 static RSFD r_open_and (RSET ct, int flag)
 376 {
 377     return r_open_andor(ct, flag, 1);
 378 }
 379
 380
 381 static void r_close (RSFD rfd)
 382 {
 383     struct rset_multiandor_info *info=
 384         (struct rset_multiandor_info *)(rfd->rset->priv);
 385     struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
 386     int i;
 387
 388     if (p->h)
 389         heap_destroy (p->h);
 390     for (i = 0; i<info->no_rsets; i++)
 391         if (p->items[i].fd)
 392             rset_close(p->items[i].fd);
 393     rfd_delete_base(rfd);
 394 }
 395
 396
 397
 398 static int r_forward_or(RSFD rfd, void *buf,
 399                         TERMID *term,const void *untilbuf)
 400 { /* while heap head behind untilbuf, forward it and rebalance heap */
 401     struct rset_multiandor_rfd *p=rfd->priv;
 402     const struct key_control *kctrl=rfd->rset->keycontrol;
 403     if (heap_empty(p->h))
 404         return 0;
 405     while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
 406     {
 407         if (rset_forward(p->h->heap[1]->fd,p->h->heap[1]->buf,
 408                          &p->h->heap[1]->term, untilbuf))
 409             heap_balance(p->h);
 410         else
 411         {
 412             heap_delete(p->h);
 413             if (heap_empty(p->h))
 414                 return 0;
 415         }
 416
 417     }
 418     return r_read_or(rfd,buf,term);
 419 }
 420
 421
 422 static int r_read_or (RSFD rfd, void *buf, TERMID *term)
 423 {
 424     struct rset_multiandor_rfd *mrfd=rfd->priv;
 425     const struct key_control *kctrl=rfd->rset->keycontrol;
 426     struct heap_item *it;
 427     int rdres;
 428     if (heap_empty(mrfd->h))
 429         return 0;
 430     it = mrfd->h->heap[1];
 431     memcpy(buf,it->buf, kctrl->key_size);
 432     if (term)
 433         *term=it->term;
 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 rset_multiandor_rfd *p=rfd->priv;
 454     const struct key_control *kctrl=rfd->rset->keycontrol;
 455     struct rset_multiandor_info *info=rfd->rset->priv;
 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<info->no_rsets) && !p->tailbits[mintail])
 464                 mintail++; /* first tail */
 465             for (i=mintail+1;i<info->no_rsets;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                 return 1;
 485             }
 486             /* still a tail? */
 487             cmp=(*kctrl->cmp)(p->items[mintail].buf,buf);
 488             if (cmp >= rfd->rset->scope){
 489                 p->tailbits[mintail]=0;
 490                 (p->tailcount)--;
 491             }
 492             return 1;
 493         }
 494         /* not tailing, forward until all reocrds match, and set up */
 495         /* as tails. the earlier 'if' will then return the hits */
 496         if (p->eof)
 497             return 0; /* nothing more to see */
 498         i=1; /* assume items[0] is highest up */
 499         while (i<info->no_rsets) {
 500             cmp=(*kctrl->cmp)(p->items[0].buf,p->items[i].buf);
 501             if (cmp<=-rfd->rset->scope) { /* [0] was behind, forward it */
 502                 if (!rset_forward(p->items[0].fd, p->items[0].buf,
 503                                   &p->items[0].term, p->items[i].buf))
 504                 {
 505                     p->eof=1; /* game over */
 506                     return 0;
 507                 }
 508                 i=0; /* start frowarding from scratch */
 509             } else if (cmp>=rfd->rset->scope)
 510             { /* [0] was ahead, forward i */
 511                 if (!rset_forward(p->items[i].fd, p->items[i].buf,
 512                                   &p->items[i].term, p->items[0].buf))
 513                 {
 514                     p->eof=1; /* game over */
 515                     return 0;
 516                 }
 517             } else
 518                 i++;
 519         } /* while i */
 520         /* if we get this far, all rsets are now within +- scope of [0] */
 521         /* ergo, we have a hit. Mark them all as tailing, and let the */
 522         /* upper 'if' return the hits in right order */
 523         for (i=0; i<info->no_rsets;i++)
 524             p->tailbits[i]=1;
 525         p->tailcount=info->no_rsets;
 526     } /* while 1 */
 527 }
 528
 529
 530 static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
 531                          const void *untilbuf)
 532 {
 533     struct rset_multiandor_rfd *p=rfd->priv;
 534     const struct key_control *kctrl=rfd->rset->keycontrol;
 535     struct rset_multiandor_info *info=rfd->rset->priv;
 536     int i;
 537     int cmp;
 538     int killtail=0;
 539
 540     for (i=0; i<info->no_rsets;i++)
 541     {
 542         cmp=(*kctrl->cmp)(p->items[i].buf,untilbuf);
 543         if ( cmp <= -rfd->rset->scope )
 544         {
 545             killtail=1; /* we are moving to a different hit */
 546             if (!rset_forward(p->items[i].fd, p->items[i].buf,
 547                               &p->items[i].term, untilbuf))
 548             {
 549                 p->eof=1; /* game over */
 550                 p->tailcount=0;
 551                 return 0;
 552             }
 553         }
 554     }
 555     if (killtail)
 556     {
 557         for (i=0; i<info->no_rsets;i++)
 558             p->tailbits[i]=0;
 559         p->tailcount=0;
 560     }
 561     return r_read_and(rfd,buf,term);
 562 }
 563
 564 static void r_pos (RSFD rfd, double *current, double *total)
 565 {
 566     struct rset_multiandor_info *info=
 567              (struct rset_multiandor_info *)(rfd->rset->priv);
 568     struct rset_multiandor_rfd *mrfd=(struct rset_multiandor_rfd *)(rfd->priv);
 569     double cur, tot;
 570     double scur=0.0, stot=0.0;
 571     int i;
 572     for (i=0; i<info->no_rsets; i++){
 573         rset_pos(mrfd->items[i].fd, &cur, &tot);
 574         yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 575         scur += cur;
 576         stot += tot;
 577     }
 578     if (stot <1.0) { /* nothing there */
 579         *current=0;
 580         *total=0;
 581         yaz_log(log_level, "r_pos: NULL  %0.1f %0.1f",  *current, *total);
 582         return;
 583     }
 584     *current=mrfd->hits;
 585     *total=*current*stot/scur;
 586     yaz_log(log_level, "r_pos: =  %0.1f %0.1f",  *current, *total);
 587 }
 588
 589
 590
 591 static int r_write (RSFD rfd, const void *buf)
 592 {
 593     yaz_log (YLOG_FATAL, "multior set type is read-only");
 594     return -1;
 595 }
 596
 597 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm)
 598     /* Special case: Some multi-ors have all terms pointing to the same */
 599     /* term. We do not want to duplicate those. Other multiors (and ands) */
 600     /* have different terms under them. Those we want. */
 601 {
 602     struct rset_multiandor_info *info =
 603         (struct rset_multiandor_info *) ct->priv;
 604     int firstterm= *curterm;
 605     int i;
 606     for (i=0;i<info->no_rsets;i++)
 607     {
 608         rset_getterms(info->rsets[i], terms, maxterms, curterm);
 609         if ( ( (*curterm) > firstterm+1 ) &&
 610              ( (*curterm) <= maxterms ) &&
 611              ( terms[(*curterm)-1] == terms[firstterm] ) )
 612             (*curterm)--; /* forget the term, seen that before */
 613     }
 614 }
 615
 616