rset/rsmultiandor.c

   1 /* $Id: rsmultiandor.c,v 1.13 2005-01-15 20:47:16 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 <zebrautl.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 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 {
 137     double cur,tot;
 138     if (i>h->heapnum)
 139         return;
 140     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 141     yaz_log(log_level," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 142                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 143     heap_dump_item(h, 2*i, level+1);
 144     heap_dump_item(h, 2*i+1, level+1);
 145 }
 146 static void heap_dump( HEAP h,char *msg) {
 147     yaz_log(log_level, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 148     heap_dump_item(h,1,1);
 149 }
 150 #endif
 151
 152 static void heap_swap (HEAP h, int x, int y)
 153 {
 154     struct heap_item *swap;
 155     swap = h->heap[x];
 156     h->heap[x] = h->heap[y];
 157     h->heap[y] = swap;
 158 }
 159
 160 static int heap_cmp(HEAP h, int x, int y)
 161 {
 162     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 163 }
 164
 165 static int heap_empty(HEAP h)
 166 {
 167     return ( 0==h->heapnum );
 168 }
 169
 170 static void heap_delete (HEAP h)
 171 { /* deletes the first item in the heap, and balances the rest */
 172     int cur = 1, child = 2;
 173     h->heap[1] = 0; /* been deleted */
 174     heap_swap (h, 1, h->heapnum--);
 175     while (child <= h->heapnum) {
 176         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 177             child++;
 178         if (heap_cmp(h,cur,child) > 0)
 179         {
 180             heap_swap (h, cur, child);
 181             cur = child;
 182             child = 2*cur;
 183         }
 184         else
 185             break;
 186     }
 187 }
 188
 189 static void heap_balance (HEAP h)
 190 { /* The heap root element has changed value (to bigger) */
 191   /* swap downwards until the heap is ordered again */
 192     int cur = 1, child = 2;
 193     while (child <= h->heapnum) {
 194         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 195             child++;
 196         if (heap_cmp(h,cur,child) > 0)
 197         {
 198             heap_swap (h, cur, child);
 199             cur = child;
 200             child = 2*cur;
 201         }
 202         else
 203             break;
 204     }
 205 }
 206
 207
 208 static void heap_insert (HEAP h, struct heap_item *hi)
 209 {
 210     int cur, parent;
 211
 212     cur = ++(h->heapnum);
 213     assert(cur <= h->heapmax);
 214     h->heap[cur] = hi;
 215     parent = cur/2;
 216     while (parent && (heap_cmp(h,parent,cur) > 0))
 217     {
 218         assert(parent>0);
 219         heap_swap (h, cur, parent);
 220         cur = parent;
 221         parent = cur/2;
 222     }
 223 }
 224
 225
 226 static
 227 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
 228 {
 229     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
 230
 231     ++size; /* heap array starts at 1 */
 232     h->heapnum = 0;
 233     h->heapmax = size;
 234     h->kctrl = kctrl;
 235     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
 236     h->heap[0]=0; /* not used */
 237     return h;
 238 }
 239
 240 static void heap_clear( HEAP h)
 241 {
 242     assert(h);
 243     h->heapnum = 0;
 244 }
 245
 246 static void heap_destroy (HEAP h)
 247 {
 248     /* nothing to delete, all is nmem'd, and will go away in due time */
 249 }
 250
 251 int compare_ands(const void *x, const void *y)
 252 { /* used in qsort to get the multi-and args in optimal order */
 253   /* that is, those with fewest occurrences first */
 254     const struct heap_item *hx = x;
 255     const struct heap_item *hy = y;
 256     double cur, totx, toty;
 257     rset_pos(hx->fd, &cur, &totx);
 258     rset_pos(hy->fd, &cur, &toty);
 259     if ( totx > toty +0.5 )
 260         return 1;
 261     if ( totx < toty -0.5 )
 262         return -1;
 263     return 0;  /* return totx - toty, except for overflows and rounding */
 264 }
 265
 266 /* Creating and deleting rsets ***********************/
 267
 268 static RSET rsmulti_andor_create( NMEM nmem, const struct key_control *kcontrol,
 269                            int scope, int no_rsets, RSET* rsets,
 270                            const struct rset_control *ctrl)
 271 {
 272     RSET rnew = rset_create_base(ctrl, nmem,kcontrol, scope,0);
 273     struct rset_multiandor_info *info;
 274     if (!log_level_initialized)
 275     {
 276         log_level = yaz_log_module_level("rsmultiandor");
 277         log_level_initialized = 1;
 278     }
 279     info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
 280     info->no_rsets = no_rsets;
 281     info->rsets = (RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
 282     memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
 283     rnew->priv = info;
 284     return rnew;
 285 }
 286
 287 RSET rsmulti_or_create(NMEM nmem, const struct key_control *kcontrol,
 288                        int scope, int no_rsets, RSET* rsets)
 289 {
 290     return rsmulti_andor_create(nmem, kcontrol, scope,
 291                                 no_rsets, rsets, &control_or);
 292 }
 293
 294 RSET rsmulti_and_create(NMEM nmem, const struct key_control *kcontrol,
 295                         int scope, int no_rsets, RSET* rsets)
 296 {
 297     return rsmulti_andor_create(nmem, kcontrol, scope,
 298                                 no_rsets, rsets, &control_and);
 299 }
 300
 301 static void r_delete (RSET ct)
 302 {
 303     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 304     int i;
 305     for(i = 0; i<info->no_rsets; i++)
 306         rset_delete(info->rsets[i]);
 307 }
 308
 309
 310 /* Opening and closing fd's on them *********************/
 311
 312 static RSFD r_open_andor (RSET ct, int flag, int is_and)
 313 {
 314     RSFD rfd;
 315     struct rset_multiandor_rfd *p;
 316     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 317     const struct key_control *kctrl = ct->keycontrol;
 318     int i;
 319
 320     if (flag & RSETF_WRITE)
 321     {
 322         yaz_log (YLOG_FATAL, "multiandor set type is read-only");
 323         return NULL;
 324     }
 325     rfd = rfd_create_base(ct);
 326     if (rfd->priv) {
 327         p = (struct rset_multiandor_rfd *)rfd->priv;
 328         if (!is_and)
 329             heap_clear(p->h);
 330         assert(p->items);
 331         /* all other pointers shouls already be allocated, in right sizes! */
 332     }
 333     else {
 334         p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
 335         rfd->priv = p;
 336         p->h = 0;
 337         p->tailbits = 0;
 338         if (is_and)
 339             p->tailbits = nmem_malloc(ct->nmem, info->no_rsets*sizeof(char) );
 340         else
 341             p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
 342         p->items=(struct heap_item *) nmem_malloc(ct->nmem,
 343                               info->no_rsets*sizeof(*p->items));
 344         for (i = 0; i<info->no_rsets; i++){
 345             p->items[i].rset = info->rsets[i];
 346             p->items[i].buf = nmem_malloc(ct->nmem,kctrl->key_size);
 347         }
 348     }
 349     p->flag = flag;
 350     p->hits = 0;
 351     p->eof = 0;
 352     p->tailcount = 0;
 353     if (is_and)
 354     { /* read the array and sort it */
 355         for (i = 0; i<info->no_rsets; i++){
 356             p->items[i].fd = rset_open(info->rsets[i],RSETF_READ);
 357             if (!rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 358                 p->eof = 1;
 359             p->tailbits[i] = 0;
 360         }
 361         qsort(p->items, info->no_rsets, sizeof(p->items[0]), compare_ands);
 362     } else
 363     { /* fill the heap for ORing */
 364         for (i = 0; i<info->no_rsets; i++){
 365             p->items[i].fd = rset_open(info->rsets[i],RSETF_READ);
 366             if ( rset_read(p->items[i].fd, p->items[i].buf, &p->items[i].term))
 367                 heap_insert(p->h, &(p->items[i]));
 368         }
 369     }
 370     return rfd;
 371 }
 372
 373 static RSFD r_open_or (RSET ct, int flag)
 374 {
 375     return r_open_andor(ct, flag, 0);
 376 }
 377
 378 static RSFD r_open_and (RSET ct, int flag)
 379 {
 380     return r_open_andor(ct, flag, 1);
 381 }
 382
 383
 384 static void r_close (RSFD rfd)
 385 {
 386     struct rset_multiandor_info *info=
 387         (struct rset_multiandor_info *)(rfd->rset->priv);
 388     struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
 389     int i;
 390
 391     if (p->h)
 392         heap_destroy (p->h);
 393     for (i = 0; i<info->no_rsets; i++)
 394         if (p->items[i].fd)
 395             rset_close(p->items[i].fd);
 396     rfd_delete_base(rfd);
 397 }
 398
 399
 400
 401 static int r_forward_or(RSFD rfd, void *buf,
 402                         TERMID *term,const void *untilbuf)
 403 { /* while heap head behind untilbuf, forward it and rebalance heap */
 404     struct rset_multiandor_rfd *p = rfd->priv;
 405     const struct key_control *kctrl = rfd->rset->keycontrol;
 406     if (heap_empty(p->h))
 407         return 0;
 408     while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
 409     {
 410         if (rset_forward(p->h->heap[1]->fd,p->h->heap[1]->buf,
 411                          &p->h->heap[1]->term, untilbuf))
 412             heap_balance(p->h);
 413         else
 414         {
 415             heap_delete(p->h);
 416             if (heap_empty(p->h))
 417                 return 0;
 418         }
 419
 420     }
 421     return r_read_or(rfd,buf,term);
 422 }
 423
 424
 425 static int r_read_or (RSFD rfd, void *buf, TERMID *term)
 426 {
 427     struct rset_multiandor_rfd *mrfd = rfd->priv;
 428     const struct key_control *kctrl = rfd->rset->keycontrol;
 429     struct heap_item *it;
 430     int rdres;
 431     if (heap_empty(mrfd->h))
 432         return 0;
 433     it = mrfd->h->heap[1];
 434     memcpy(buf,it->buf, kctrl->key_size);
 435     if (term)
 436         *term = it->term;
 437     (mrfd->hits)++;
 438     rdres = rset_read(it->fd, it->buf, &it->term);
 439     if ( rdres )
 440         heap_balance(mrfd->h);
 441     else
 442         heap_delete(mrfd->h);
 443     return 1;
 444
 445 }
 446
 447 static int r_read_and (RSFD rfd, void *buf, TERMID *term)
 448 { /* Has to return all hits where each item points to the */
 449   /* same sysno (scope), in order. Keep an extra key (hitkey) */
 450   /* as long as all records do not point to hitkey, forward */
 451   /* them, and update hitkey to be the highest seen so far. */
 452   /* (if any item eof's, mark eof, and return 0 thereafter) */
 453   /* Once a hit has been found, scan all items for the smallest */
 454   /* value. Mark all as being in the tail. Read next from that */
 455   /* item, and if not in the same record, clear its tail bit */
 456     struct rset_multiandor_rfd *p = rfd->priv;
 457     const struct key_control *kctrl = rfd->rset->keycontrol;
 458     struct rset_multiandor_info *info = rfd->rset->priv;
 459     int i, mintail;
 460     int cmp;
 461
 462     while (1) {
 463         if (p->tailcount)
 464         { /* we are tailing, find lowest tail and return it */
 465             mintail = 0;
 466             while ((mintail<info->no_rsets) && !p->tailbits[mintail])
 467                 mintail++; /* first tail */
 468             for (i = mintail+1; i<info->no_rsets; i++)
 469             {
 470                 if (p->tailbits[i])
 471                 {
 472                     cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf);
 473                     if (cmp<0)
 474                         mintail = i;
 475                 }
 476             }
 477             /* return the lowest tail */
 478             memcpy(buf, p->items[mintail].buf, kctrl->key_size);
 479             if (term)
 480                 *term = p->items[mintail].term;
 481             if (!rset_read(p->items[mintail].fd, p->items[mintail].buf,
 482                            &p->items[mintail].term))
 483             {
 484                 p->eof = 1; /* game over, once tails have been returned */
 485                 p->tailbits[mintail]=0;
 486                 (p->tailcount)--;
 487                 return 1;
 488             }
 489             /* still a tail? */
 490             cmp=(*kctrl->cmp)(p->items[mintail].buf,buf);
 491             if (cmp >= rfd->rset->scope){
 492                 p->tailbits[mintail]=0;
 493                 (p->tailcount)--;
 494             }
 495             return 1;
 496         }
 497         /* not tailing, forward until all reocrds match, and set up */
 498         /* as tails. the earlier 'if' will then return the hits */
 499         if (p->eof)
 500             return 0; /* nothing more to see */
 501         i = 1; /* assume items[0] is highest up */
 502         while (i<info->no_rsets) {
 503             cmp=(*kctrl->cmp)(p->items[0].buf,p->items[i].buf);
 504             if (cmp<=-rfd->rset->scope) { /* [0] was behind, forward it */
 505                 if (!rset_forward(p->items[0].fd, p->items[0].buf,
 506                                   &p->items[0].term, p->items[i].buf))
 507                 {
 508                     p->eof = 1; /* game over */
 509                     return 0;
 510                 }
 511                 i = 0; /* start frowarding from scratch */
 512             } else if (cmp>=rfd->rset->scope)
 513             { /* [0] was ahead, forward i */
 514                 if (!rset_forward(p->items[i].fd, p->items[i].buf,
 515                                   &p->items[i].term, p->items[0].buf))
 516                 {
 517                     p->eof = 1; /* game over */
 518                     return 0;
 519                 }
 520             } else
 521                 i++;
 522         } /* while i */
 523         /* if we get this far, all rsets are now within +- scope of [0] */
 524         /* ergo, we have a hit. Mark them all as tailing, and let the */
 525         /* upper 'if' return the hits in right order */
 526         for (i = 0; i<info->no_rsets; i++)
 527             p->tailbits[i] = 1;
 528         p->tailcount = info->no_rsets;
 529     } /* while 1 */
 530 }
 531
 532
 533 static int r_forward_and(RSFD rfd, void *buf, TERMID *term,
 534                          const void *untilbuf)
 535 {
 536     struct rset_multiandor_rfd *p = rfd->priv;
 537     const struct key_control *kctrl = rfd->rset->keycontrol;
 538     struct rset_multiandor_info *info = rfd->rset->priv;
 539     int i;
 540     int cmp;
 541     int killtail = 0;
 542
 543     for (i = 0; i<info->no_rsets; i++)
 544     {
 545         cmp = (*kctrl->cmp)(p->items[i].buf,untilbuf);
 546         if (cmp <= -rfd->rset->scope)
 547         {
 548             killtail = 1; /* we are moving to a different hit */
 549             if (!rset_forward(p->items[i].fd, p->items[i].buf,
 550                               &p->items[i].term, untilbuf))
 551             {
 552                 p->eof = 1; /* game over */
 553                 p->tailcount = 0;
 554                 return 0;
 555             }
 556         }
 557     }
 558     if (killtail)
 559     {
 560         for (i = 0; i<info->no_rsets; i++)
 561             p->tailbits[i] = 0;
 562         p->tailcount = 0;
 563     }
 564     return r_read_and(rfd,buf,term);
 565 }
 566
 567 static void r_pos (RSFD rfd, double *current, double *total)
 568 {
 569     struct rset_multiandor_info *info =
 570         (struct rset_multiandor_info *)(rfd->rset->priv);
 571     struct rset_multiandor_rfd *mrfd =
 572         (struct rset_multiandor_rfd *)(rfd->priv);
 573     double cur, tot;
 574     double scur = 0.0, stot = 0.0;
 575     int i;
 576     for (i = 0; i<info->no_rsets; i++){
 577         rset_pos(mrfd->items[i].fd, &cur, &tot);
 578         yaz_log(log_level, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 579         scur += cur;
 580         stot += tot;
 581     }
 582     if (stot < 1.0) { /* nothing there */
 583         *current = 0;
 584         *total = 0;
 585         yaz_log(log_level, "r_pos: NULL  %0.1f %0.1f",  *current, *total);
 586     }
 587     else
 588     {
 589         *current = mrfd->hits;
 590         *total = *current*stot/scur;
 591         yaz_log(log_level, "r_pos: =  %0.1f %0.1f",  *current, *total);
 592     }
 593 }
 594
 595 static int r_write (RSFD rfd, const void *buf)
 596 {
 597     yaz_log (YLOG_FATAL, "multior set type is read-only");
 598     return -1;
 599 }
 600
 601 static void r_get_terms(RSET ct, TERMID *terms, int maxterms, int *curterm)
 602     /* Special case: Some multi-ors have all terms pointing to the same */
 603     /* term. We do not want to duplicate those. Other multiors (and ands) */
 604     /* have different terms under them. Those we want. */
 605 {
 606     struct rset_multiandor_info *info =
 607         (struct rset_multiandor_info *) ct->priv;
 608     int firstterm= *curterm;
 609     int i;
 610     for (i = 0; i<info->no_rsets; i++)
 611     {
 612         rset_getterms(info->rsets[i], terms, maxterms, curterm);
 613         if ( ( *curterm > firstterm+1 ) &&
 614              ( *curterm <= maxterms ) &&
 615              ( terms[(*curterm)-1] == terms[firstterm] )
 616             )
 617             (*curterm)--; /* forget the term, seen that before */
 618     }
 619 }
 620
 621