rset/rsmultiandor.c

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