rset/rsmultiandor.c

   1 /* $Id: rsmultiandor.c,v 1.1 2004-09-28 13:06:35 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;
 121     zint hits; /* returned so far */
 122     int eof; /* seen the end of it */
 123 };
 124
 125 /* Heap functions ***********************/
 126
 127 #if 0
 128 static void heap_dump_item( HEAP h, int i, int level) {
 129     double cur,tot;
 130     if (i>h->heapnum)
 131         return;
 132     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 133     logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 134                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 135     heap_dump_item(h, 2*i, level+1);
 136     heap_dump_item(h, 2*i+1, level+1);
 137 }
 138 static void heap_dump( HEAP h,char *msg) {
 139     logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 140     heap_dump_item(h,1,1);
 141 }
 142 #endif
 143
 144 static void heap_swap (HEAP h, int x, int y)
 145 {
 146     struct heap_item *swap;
 147     swap = h->heap[x];
 148     h->heap[x]=h->heap[y];
 149     h->heap[y]=swap;
 150 }
 151
 152 static int heap_cmp(HEAP h, int x, int y)
 153 {
 154     return (*h->kctrl->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 155 }
 156
 157 static int heap_empty(HEAP h)
 158 {
 159     return ( 0==h->heapnum );
 160 }
 161
 162 static void heap_delete (HEAP h)
 163 { /* deletes the first item in the heap, and balances the rest */
 164     int cur = 1, child = 2;
 165     h->heap[1]=0; /* been deleted */
 166     heap_swap (h, 1, h->heapnum--);
 167     while (child <= h->heapnum) {
 168         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 169             child++;
 170         if (heap_cmp(h,cur,child) > 0)
 171         {
 172             heap_swap (h, cur, child);
 173             cur = child;
 174             child = 2*cur;
 175         }
 176         else
 177             break;
 178     }
 179 }
 180
 181 static void heap_balance (HEAP h)
 182 { /* The heap root element has changed value (to bigger) */
 183   /* swap downwards until the heap is ordered again */
 184     int cur = 1, child = 2;
 185     while (child <= h->heapnum) {
 186         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 187             child++;
 188         if (heap_cmp(h,cur,child) > 0)
 189         {
 190             heap_swap (h, cur, child);
 191             cur = child;
 192             child = 2*cur;
 193         }
 194         else
 195             break;
 196     }
 197 }
 198
 199
 200 static void heap_insert (HEAP h, struct heap_item *hi)
 201 {
 202     int cur, parent;
 203
 204     cur = ++(h->heapnum);
 205     assert(cur <= h->heapmax);
 206     h->heap[cur]=hi;
 207     parent = cur/2;
 208     while (parent && (heap_cmp(h,parent,cur) > 0))
 209     {
 210         assert(parent>0);
 211         heap_swap (h, cur, parent);
 212         cur = parent;
 213         parent = cur/2;
 214     }
 215 }
 216
 217
 218 static
 219 HEAP heap_create (NMEM nmem, int size, const struct key_control *kctrl)
 220 {
 221     HEAP h = (HEAP) nmem_malloc (nmem, sizeof(*h));
 222
 223     ++size; /* heap array starts at 1 */
 224     h->heapnum = 0;
 225     h->heapmax = size;
 226     h->kctrl=kctrl;
 227     h->heap = (struct heap_item**) nmem_malloc(nmem,size*sizeof(*h->heap));
 228     h->heap[0]=0; /* not used */
 229     return h;
 230 }
 231
 232 static void heap_clear( HEAP h)
 233 {
 234     assert(h);
 235     h->heapnum=0;
 236 }
 237
 238 static void heap_destroy (HEAP h)
 239 {
 240     /* nothing to delete, all is nmem'd, and will go away in due time */
 241 }
 242
 243
 244 /* Creating and deleting rsets ***********************/
 245
 246 static RSET rsmulti_andor_create( NMEM nmem, const struct key_control *kcontrol,
 247                            int scope, int no_rsets, RSET* rsets,
 248                            const struct rset_control *ctrl)
 249 {
 250     RSET rnew=rset_create_base(ctrl, nmem,kcontrol, scope);
 251     struct rset_multiandor_info *info;
 252     info = (struct rset_multiandor_info *) nmem_malloc(rnew->nmem,sizeof(*info));
 253     info->no_rsets=no_rsets;
 254     info->rsets=(RSET*)nmem_malloc(rnew->nmem, no_rsets*sizeof(*rsets));
 255     memcpy(info->rsets,rsets,no_rsets*sizeof(*rsets));
 256     rnew->priv=info;
 257     return rnew;
 258 }
 259
 260 RSET rsmultior_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 261             int no_rsets, RSET* rsets)
 262 {
 263     return rsmulti_andor_create(nmem, kcontrol, scope,
 264                                 no_rsets, rsets, &control_or);
 265 }
 266
 267 RSET rsmultiand_create( NMEM nmem, const struct key_control *kcontrol, int scope,
 268             int no_rsets, RSET* rsets)
 269 {
 270     return rsmulti_andor_create(nmem, kcontrol, scope,
 271                                 no_rsets, rsets, &control_and);
 272 }
 273
 274 static void r_delete (RSET ct)
 275 {
 276     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 277     int i;
 278     for(i=0;i<info->no_rsets;i++)
 279         rset_delete(info->rsets[i]);
 280 }
 281
 282 /* Opening and closing fd's on them *********************/
 283
 284 static RSFD r_open_andor (RSET ct, int flag, int is_and)
 285 {
 286     RSFD rfd;
 287     struct rset_multiandor_rfd *p;
 288     struct rset_multiandor_info *info = (struct rset_multiandor_info *) ct->priv;
 289     const struct key_control *kctrl = ct->keycontrol;
 290     int i;
 291
 292     if (flag & RSETF_WRITE)
 293     {
 294         logf (LOG_FATAL, "multior set type is read-only");
 295         return NULL;
 296     }
 297     rfd=rfd_create_base(ct);
 298     if (rfd->priv) {
 299         p=(struct rset_multiandor_rfd *)rfd->priv;
 300         heap_clear(p->h);
 301         assert(p->items);
 302         /* all other pointers shouls already be allocated, in right sizes! */
 303     }
 304     else {
 305         p = (struct rset_multiandor_rfd *) nmem_malloc (ct->nmem,sizeof(*p));
 306         rfd->priv=p;
 307         p->h = heap_create( ct->nmem, info->no_rsets, kctrl);
 308         p->items=(struct heap_item *) nmem_malloc(ct->nmem,
 309                               info->no_rsets*sizeof(*p->items));
 310         for (i=0; i<info->no_rsets; i++){
 311             p->items[i].rset=info->rsets[i];
 312             p->items[i].buf=nmem_malloc(ct->nmem,kctrl->key_size);
 313         }
 314     }
 315     p->flag = flag;
 316     p->hits=0;
 317     p->eof=0;
 318     if (is_and)
 319     { /* read the array and sort it */
 320         for (i=0; i<info->no_rsets; i++){
 321             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 322             if ( !rset_read(p->items[i].fd, p->items[i].buf) )
 323                 p->eof=1;
 324         }
 325     } else
 326     { /* fill the heap for ORing */
 327         for (i=0; i<info->no_rsets; i++){
 328             p->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 329             if ( rset_read(p->items[i].fd, p->items[i].buf) )
 330                 heap_insert(p->h, &(p->items[i]));
 331         }
 332     }
 333     return rfd;
 334 }
 335
 336 static RSFD r_open_or (RSET ct, int flag)
 337 {
 338     return r_open_andor(ct, flag, 0);
 339 }
 340
 341 static RSFD r_open_and (RSET ct, int flag)
 342 {
 343     return r_open_andor(ct, flag, 1);
 344 }
 345
 346
 347 static void r_close (RSFD rfd)
 348 {
 349     struct rset_multiandor_info *info=(struct rset_multiandor_info *)(rfd->rset->priv);
 350     struct rset_multiandor_rfd *p=(struct rset_multiandor_rfd *)(rfd->priv);
 351     int i;
 352
 353     heap_destroy (p->h);
 354     for (i = 0; i<info->no_rsets; i++)
 355         if (p->items[i].fd)
 356             rset_close(p->items[i].fd);
 357     rfd_delete_base(rfd);
 358 }
 359
 360
 361
 362 static int r_forward_or(RSFD rfd, void *buf, const void *untilbuf)
 363 {
 364     struct rset_multiandor_rfd *mrfd=rfd->priv;
 365     const struct key_control *kctrl=rfd->rset->keycontrol;
 366     struct heap_item it;
 367     int rdres;
 368     if (heap_empty(mrfd->h))
 369         return 0;
 370     it = *(mrfd->h->heap[1]);
 371     memcpy(buf,it.buf, kctrl->key_size);
 372     /* FIXME - This is not right ! */
 373     /* If called with an untilbuf, we need to compare to that, and */
 374     /* forward until we are somewhere! */
 375     (mrfd->hits)++;
 376     if (untilbuf)
 377         rdres=rset_forward(it.fd, it.buf, untilbuf);
 378     else
 379         rdres=rset_read(it.fd, it.buf);
 380     if ( rdres )
 381         heap_balance(mrfd->h);
 382     else
 383         heap_delete(mrfd->h);
 384     return 1;
 385
 386 }
 387
 388 static int r_read_or (RSFD rfd, void *buf)
 389 {
 390     return r_forward_or(rfd, buf,0);
 391 }
 392
 393 static int r_read_and (RSFD rfd, void *buf)
 394 {
 395     return 0;
 396 }
 397 static int r_forward_and(RSFD rfd, void *buf, const void *untilbuf)
 398 {
 399     return 0;
 400 }
 401
 402 static void r_pos (RSFD rfd, double *current, double *total)
 403 {
 404     struct rset_multiandor_info *info=
 405              (struct rset_multiandor_info *)(rfd->rset->priv);
 406     struct rset_multiandor_rfd *mrfd=(struct rset_multiandor_rfd *)(rfd->priv);
 407     double cur, tot;
 408     double scur=0.0, stot=0.0;
 409     int i;
 410     for (i=0; i<info->no_rsets; i++){
 411         rset_pos(mrfd->items[i].fd, &cur, &tot);
 412         logf(LOG_LOG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 413         scur += cur;
 414         stot += tot;
 415     }
 416     if (stot <1.0) { /* nothing there */
 417         *current=0;
 418         *total=0;
 419         return;
 420     }
 421     *current=mrfd->hits;
 422     *total=*current*stot/scur;
 423 }
 424
 425
 426 static void r_rewind (RSFD rfd)
 427 {
 428     assert(!"rewind not implemented yet");
 429     /* FIXME - rewind all parts, rebalance heap, clear hits */
 430 }
 431
 432 static int r_write (RSFD rfd, const void *buf)
 433 {
 434     logf (LOG_FATAL, "multior set type is read-only");
 435     return -1;
 436 }