rset/rsmultiandor.c

   1 /* $Id: rsmultiandor.c,v 1.5 2004-09-30 09:53:05 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);
  51 static int r_read_or (RSFD rfd, void *buf);
  52 static int r_write (RSFD rfd, const void *buf);
  53 static int r_forward_and(RSFD rfd, void *buf,
  54                      const void *untilbuf);
  55 static int r_forward_or(RSFD rfd, void *buf,
  56                      const void *untilbuf);
  57 static void r_pos (RSFD rfd, double *current, double *total);
  58
  59 static const struct rset_control control_or =
  60 {
  61     "multi-or",
  62     r_delete,
  63     r_open_or,
  64     r_close,
  65     r_forward_or,
  66     r_pos,
  67     r_read_or,
  68     r_write,
  69 };
  70 static const struct rset_control control_and =
  71 {
  72     "multi-and",
  73     r_delete,
  74     r_open_and,
  75     r_close,
  76     r_forward_and,
  77     r_pos,
  78     r_read_and,
  79     r_write,
  80 };
  81
  82 const struct rset_control *rset_kind_multior = &control_or;
  83 const struct rset_control *rset_kind_multiand = &control_and;
  84
  85 /* The heap structure:
  86  * The rset contains a list or rsets we are ORing together
  87  * The rfd contains a heap of heap-items, which contain
  88  * a rfd opened to those rsets, and a buffer for one key.
  89  * They also contain a ptr to the rset list in the rset
  90  * itself, for practical reasons.
  91  */
  92
  93 struct heap_item {
  94     RSFD fd;
  95     void *buf;
  96     RSET rset;
  97 };
  98
  99 struct heap {
 100     int heapnum;
 101     int heapmax;
 102     const struct key_control *kctrl;
 103     struct heap_item **heap; /* ptrs to the rfd */
 104 };
 105 typedef struct heap *HEAP;
 106
 107
 108 struct rset_multiandor_info {
 109     int     no_rsets;
 110     RSET    *rsets;
 111 };
 112
 113
 114 struct rset_multiandor_rfd {
 115     int flag;
 116     struct heap_item *items; /* we alloc and free them here */
 117     HEAP h; /* and move around here */
 118     zint hits; /* returned so far */
 119     int eof; /* seen the end of it */
 120     int tailcount; /* how many items are tailing */
 121     char *tailbits;
 122 };
 123
 124 /* Heap functions ***********************/
 125
 126 #if 0
 127 static void heap_dump_item( HEAP h, int i, int level) {
 128     double cur,tot;
 129     if (i>h->heapnum)
 130         return;
 131     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 132     logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 133                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 134     heap_dump_item(h, 2*i, level+1);
 135     heap_dump_item(h, 2*i+1, level+1);
 136 }
 137 static void heap_dump( HEAP h,char *msg) {
 138     logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 139     heap_dump_item(h,1,1);
 140 }
 141 #endif
 142
 143 static void heap_swap (HEAP h, int x, int y)
 144 {
 145     struct heap_item *swap;
 146     swap = h->heap[x];
 147     h->heap[x]=h->heap[y];
 148     h->heap[y]=swap;
 149 }
 150
 151 static int heap_cmp(HEAP h, int x, int y)
 152 {
 153     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 154 }
 155
 156 static int heap_empty(HEAP h)
 157 {
 158     return ( 0==h->heapnum );
 159 }
 160
 161 static void heap_delete (HEAP h)
 162 { /* deletes the first item in the heap, and balances the rest */
 163     int cur = 1, child = 2;
 164     h->heap[1]=0; /* been deleted */
 165     heap_swap (h, 1, h->heapnum--);
 166     while (child <= h->heapnum) {
 167         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 168             child++;
 169         if (heap_cmp(h,cur,child) > 0)
 170         {
 171             heap_swap (h, cur, child);
 172             cur = child;
 173             child = 2*cur;
 174         }
 175         else
 176             break;
 177     }
 178 }
 179
 180 static void heap_balance (HEAP h)
 181 { /* The heap root element has changed value (to bigger) */
 182   /* swap downwards until the heap is ordered again */
 183     int cur = 1, child = 2;
 184     while (child <= h->heapnum) {
 185         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 186             child++;
 187         if (heap_cmp(h,cur,child) > 0)
 188         {
 189             heap_swap (h, cur, child);
 190             cur = child;
 191             child = 2*cur;
 192         }
 193         else
 194             break;
 195     }
 196 }
 197
 198
 199 static void heap_insert (HEAP h, struct heap_item *hi)
 200 {
 201     int cur, parent;
 202
 203     cur = ++(h->heapnum);
 204     assert(cur <= h->heapmax);
 205     h->heap[cur]=hi;
 206     parent = cur/2;
 207     while (parent && (heap_cmp(h,parent,cur) > 0))
 208     {
 209         assert(parent>0);
 210         heap_swap (h, cur, parent);
 211         cur = parent;
 212         parent = cur/2;
 213     }
 214 }
 215
 216
 217 static
 218 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
 219 {
 220     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
 221
 222     ++size; /* heap array starts at 1 */
 223     h->heapnum = 0;
 224     h->heapmax = size;
 225     h->kctrl=kctrl;
 226     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
 227     h->heap[0]=0; /* not used */
 228     return h;
 229 }
 230
 231 static void heap_clear( HEAP h)
 232 {
 233     assert(h);
 234     h->heapnum=0;
 235 }
 236
 237 static void heap_destroy (HEAP h)
 238 {
 239     /* nothing to delete, all is nmem'd, and will go away in due time */
 240 }
 241
 242 int compare_ands(const void *x, const void *y)
 243 { /* used in qsort to get the multi-and args in optimal order */
 244   /* that is, those with fewest occurrences first */
 245     const struct heap_item *hx=x;
 246     const struct heap_item *hy=y;
 247     double cur, totx, toty;
 248     rset_pos(hx->fd, &cur, &totx);
 249     rset_pos(hy->fd, &cur, &toty);
 250     if ( totx > toty +0.5 ) return 1;
 251     if ( totx < toty -0.5 ) return -1;
 252     return 0;  /* return totx - toty, except for overflows and rounding */
 253 }
 254
 255 /* Creating and deleting rsets ***********************/
 256
 257 static RSET rsmulti_andor_create( NMEM nmem, const struct key_control *kcontrol,
 258                            int scope, int no_rsets, RSET* rsets,
 259                            const struct rset_control *ctrl)
 260 {
 261     RSET rnew=rset_create_base(ctrl, nmem,kcontrol, scope);
 262     struct rset_multiandor_info *info;
 263     info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
 264     info->no_rsets=no_rsets;
 265     info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
 266     memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
 267     rnew->priv=info;
 268     return rnew;
 269 }
 270
 271 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 272             int no_rsets, RSET* rsets)
 273 {
 274     return rsmulti_andor_create(nmem, kcontrol, scope,
 275                                 no_rsets, rsets, &control_or);
 276 }
 277
 278 RSET rsmultiand_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 279             int no_rsets, RSET* rsets)
 280 {
 281     return rsmulti_andor_create(nmem, kcontrol, scope,
 282                                 no_rsets, rsets, &control_and);
 283 }
 284
 285 static void r_delete (RSET ct)
 286 {
 287     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 288     int i;
 289     for(i=0;i<info->no_rsets;i++)
 290         rset_delete(info->rsets[i]);
 291 }
 292
 293
 294 /* Opening and closing fd's on them *********************/
 295
 296 static RSFD r_open_andor (RSET ct, int flag, int is_and)
 297 {
 298     RSFD rfd;
 299     struct rset_multiandor_rfd *p;
 300     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 301     const struct key_control *kctrl = ct->keycontrol;
 302     int i;
 303
 304     if (flag & RSETF_WRITE)
 305     {
 306         logf (LOG_FATAL, "multiandor set type is read-only");
 307         return NULL;
 308     }
 309     rfd=rfd_create_base(ct);
 310     if (rfd->priv) {
 311         p=(struct rset_multiandor_rfd *)rfd->priv;
 312         if (!is_and)
 313             heap_clear(p->h);
 314         assert(p->items);
 315         /* all other pointers shouls already be allocated, in right sizes! */
 316     }
 317     else {
 318         p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
 319         rfd->priv=p;
 320         p->h=0;
 321         p->tailbits=0;
 322         if (is_and)
 323             p->tailbits=nmem_malloc(ct->nmem, info->no_rsets*sizeof(char) );
 324         else
 325             p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
 326         p->items=(struct heap_item *) nmem_malloc(ct->nmem,
 327                               info->no_rsets*sizeof(*p->items));
 328         for (i=0; i<info->no_rsets; i++){
 329             p->items[i].rset=info->rsets[i];
 330             p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
 331         }
 332     }
 333     p->flag = flag;
 334     p->hits=0;
 335     p->eof=0;
 336     p->tailcount=0;
 337     if (is_and)
 338     { /* read the array and sort it */
 339         for (i=0; i<info->no_rsets; i++){
 340             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 341             if ( !rset_read(p->items[i].fd, p->items[i].buf) )
 342                 p->eof=1;
 343             p->tailbits[i]=0;
 344         }
 345         qsort(p->items, info->no_rsets, sizeof(p->items[0]), compare_ands);
 346     } else
 347     { /* fill the heap for ORing */
 348         for (i=0; i<info->no_rsets; i++){
 349             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 350             if ( rset_read(p->items[i].fd, p->items[i].buf) )
 351                 heap_insert(p->h, &(p->items[i]));
 352         }
 353     }
 354     return rfd;
 355 }
 356
 357 static RSFD r_open_or (RSET ct, int flag)
 358 {
 359     return r_open_andor(ct, flag, 0);
 360 }
 361
 362 static RSFD r_open_and (RSET ct, int flag)
 363 {
 364     return r_open_andor(ct, flag, 1);
 365 }
 366
 367
 368 static void r_close (RSFD rfd)
 369 {
 370     struct rset_multiandor_info *info=
 371         (struct rset_multiandor_info *)(rfd->rset->priv);
 372     struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
 373     int i;
 374
 375     if (p->h)
 376         heap_destroy (p->h);
 377     for (i = 0; i<info->no_rsets; i++)
 378         if (p->items[i].fd)
 379             rset_close(p->items[i].fd);
 380     rfd_delete_base(rfd);
 381 }
 382
 383
 384
 385 static int r_forward_or(RSFD rfd, void *buf, const void *untilbuf)
 386 { /* while heap head behind untilbuf, forward it and rebalance heap */
 387     struct rset_multiandor_rfd *p=rfd->priv;
 388     const struct key_control *kctrl=rfd->rset->keycontrol;
 389     if (heap_empty(p->h))
 390         return 0;
 391     while ( (*kctrl->cmp)(p->h->heap[1]->buf,untilbuf) < -rfd->rset->scope )
 392     {
 393         if ( rset_forward(p->h->heap[1]->fd, p->h->heap[1]->buf, untilbuf) )
 394             heap_balance(p->h);
 395         else
 396         {
 397             heap_delete(p->h);
 398             if (heap_empty(p->h))
 399                 return 0;
 400         }
 401
 402     }
 403     return r_read_or(rfd,buf);
 404 }
 405
 406
 407 static int r_read_or (RSFD rfd, void *buf)
 408 {
 409     struct rset_multiandor_rfd *mrfd=rfd->priv;
 410     const struct key_control *kctrl=rfd->rset->keycontrol;
 411     struct heap_item *it;
 412     int rdres;
 413     if (heap_empty(mrfd->h))
 414         return 0;
 415     it = mrfd->h->heap[1];
 416     memcpy(buf,it->buf, kctrl->key_size);
 417     (mrfd->hits)++;
 418     rdres=rset_read(it->fd, it->buf);
 419     if ( rdres )
 420         heap_balance(mrfd->h);
 421     else
 422         heap_delete(mrfd->h);
 423     return 1;
 424
 425 }
 426
 427 static int r_read_and (RSFD rfd, void *buf)
 428 { /* Has to return all hits where each item points to the */
 429   /* same sysno (scope), in order. Keep an extra key (hitkey) */
 430   /* as long as all records do not point to hitkey, forward */
 431   /* them, and update hitkey to be the highest seen so far. */
 432   /* (if any item eof's, mark eof, and return 0 thereafter) */
 433   /* Once a hit has been found, scan all items for the smallest */
 434   /* value. Mark all as being in the tail. Read next from that */
 435   /* item, and if not in the same record, clear its tail bit */
 436     struct rset_multiandor_rfd *p=rfd->priv;
 437     const struct key_control *kctrl=rfd->rset->keycontrol;
 438     struct rset_multiandor_info *info=rfd->rset->priv;
 439     int i, mintail;
 440     int cmp;
 441
 442     while (1) {
 443         if (p->tailcount)
 444         { /* we are tailing, find lowest tail and return it */
 445             mintail=0;
 446             while ((mintail<info->no_rsets) && !p->tailbits[mintail])
 447                 mintail++; /* first tail */
 448             for (i=mintail+1;i<info->no_rsets;i++)
 449             {
 450                 if (p->tailbits[i])
 451                 {
 452                     cmp=(*kctrl->cmp)(p->items[i].buf,p->items[mintail].buf);
 453                     if (cmp<0)
 454                         mintail=i;
 455                 }
 456             }
 457             /* return the lowest tail */
 458             memcpy(buf, p->items[mintail].buf, kctrl->key_size);
 459             if (!rset_read(p->items[mintail].fd, p->items[mintail].buf))
 460             {
 461                 p->eof=1; /* game over, once tails have been returned */
 462                 p->tailbits[mintail]=0;
 463                 (p->tailcount)--;
 464                 return 1;
 465             }
 466             /* still a tail? */
 467             cmp=(*kctrl->cmp)(p->items[mintail].buf,buf);
 468             if (cmp >= rfd->rset->scope){
 469                 p->tailbits[mintail]=0;
 470                 (p->tailcount)--;
 471             }
 472             return 1;
 473         }
 474         /* not tailing, forward until all reocrds match, and set up */
 475         /* as tails. the earlier 'if' will then return the hits */
 476         if (p->eof)
 477             return 0; /* nothing more to see */
 478         i=1; /* assume items[0] is highest up */
 479         while (i<info->no_rsets) {
 480             cmp=(*kctrl->cmp)(p->items[0].buf,p->items[i].buf);
 481             if (cmp<=-rfd->rset->scope) { /* [0] was behind, forward it */
 482                 if (!rset_forward(p->items[0].fd, p->items[0].buf,
 483                                   p->items[i].buf))
 484                 {
 485                     p->eof=1; /* game over */
 486                     return 0;
 487                 }
 488                 i=0; /* start frowarding from scratch */
 489             } else if (cmp>=rfd->rset->scope)
 490             { /* [0] was ahead, forward i */
 491                 if (!rset_forward(p->items[i].fd, p->items[i].buf,
 492                                   p->items[0].buf))
 493                 {
 494                     p->eof=1; /* game over */
 495                     return 0;
 496                 }
 497             } else
 498                 i++;
 499         } /* while i */
 500         /* if we get this far, all rsets are now within +- scope of [0] */
 501         /* ergo, we have a hit. Mark them all as tailing, and let the */
 502         /* upper 'if' return the hits in right order */
 503         for (i=0; i<info->no_rsets;i++)
 504             p->tailbits[i]=1;
 505         p->tailcount=info->no_rsets;
 506     } /* while 1 */
 507 }
 508
 509
 510 static int r_forward_and(RSFD rfd, void *buf, const void *untilbuf)
 511 {
 512     struct rset_multiandor_rfd *p=rfd->priv;
 513     const struct key_control *kctrl=rfd->rset->keycontrol;
 514     struct rset_multiandor_info *info=rfd->rset->priv;
 515     int i;
 516     int cmp;
 517     int killtail=0;
 518
 519     for (i=0; i<info->no_rsets;i++)
 520     {
 521         cmp=(*kctrl->cmp)(p->items[i].buf,untilbuf);
 522         if ( cmp <= -rfd->rset->scope )
 523         {
 524             killtail=1; /* we are moving to a different hit */
 525             if (!rset_forward(p->items[i].fd, p->items[i].buf,
 526                               untilbuf))
 527             {
 528                 p->eof=1; /* game over */
 529                 p->tailcount=0;
 530                 return 0;
 531             }
 532         }
 533     }
 534     if (killtail)
 535     {
 536         for (i=0; i<info->no_rsets;i++)
 537             p->tailbits[i]=0;
 538         p->tailcount=0;
 539     }
 540     return r_read_and(rfd,buf);
 541 }
 542
 543 static void r_pos (RSFD rfd, double *current, double *total)
 544 {
 545     struct rset_multiandor_info *info=
 546              (struct rset_multiandor_info *)(rfd->rset->priv);
 547     struct rset_multiandor_rfd *mrfd=(struct rset_multiandor_rfd *)(rfd->priv);
 548     double cur, tot;
 549     double scur=0.0, stot=0.0;
 550     int i;
 551     for (i=0; i<info->no_rsets; i++){
 552         rset_pos(mrfd->items[i].fd, &cur, &tot);
 553         logf(LOG_DEBUG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 554         scur += cur;
 555         stot += tot;
 556     }
 557     if (stot <1.0) { /* nothing there */
 558         *current=0;
 559         *total=0;
 560         return;
 561     }
 562     *current=mrfd->hits;
 563     *total=*current*stot/scur;
 564 }
 565
 566
 567
 568 static int r_write (RSFD rfd, const void *buf)
 569 {
 570     logf (LOG_FATAL, "multior set type is read-only");
 571     return -1;
 572 }