rset/rsmultior.c

   1 /* $Id: rsmultior.c,v 1.3 2004-08-19 14:11:54 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
  26 #include <assert.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #include <zebrautl.h>
  32 #include <isamc.h>
  33 #include <rsmultior.h>
  34
  35 static void *r_create(RSET ct, const struct rset_control *sel, void *parms);
  36 static RSFD r_open (RSET ct, int flag);
  37 static void r_close (RSFD rfd);
  38 static void r_delete (RSET ct);
  39 static void r_rewind (RSFD rfd);
  40 static int r_read (RSFD rfd, void *buf, int *term_index);
  41 static int r_write (RSFD rfd, const void *buf);
  42 static int r_forward(RSET ct, RSFD rfd, void *buf,  int *term_index,
  43                      int (*cmpfunc)(const void *p1, const void *p2),
  44                      const void *untilbuf);
  45 static void r_pos (RSFD rfd, double *current, double *total);
  46
  47 static const struct rset_control control =
  48 {
  49     "multi-or",
  50     r_create,
  51     r_open,
  52     r_close,
  53     r_delete,
  54     r_rewind,
  55     r_forward,
  56     r_pos,
  57     r_read,
  58     r_write,
  59 };
  60
  61 const struct rset_control *rset_kind_multior = &control;
  62
  63 /* The heap structure:
  64  * The rset contains a list or rsets we are ORing together
  65  * The rfd contains a heap of heap-items, which contain
  66  * a rfd opened to those rsets, and a buffer for one key.
  67  * They also contain a ptr to the rset list in the rset
  68  * itself, for practical reasons.
  69  */
  70
  71 struct heap_item {
  72     RSFD fd;
  73     void *buf;
  74     RSET rset;
  75 };
  76
  77 struct heap {
  78     int heapnum;
  79     int heapmax;
  80     int keysize;
  81     int     (*cmp)(const void *p1, const void *p2);
  82     struct heap_item **heap; /* ptrs to the rfd */
  83 };
  84 typedef struct heap *HEAP;
  85
  86
  87 struct rset_multior_info {
  88     int     key_size;
  89     int     no_rec;
  90     int     (*cmp)(const void *p1, const void *p2);
  91     int     no_rsets;
  92     RSET    *rsets;
  93     int     term_index;
  94     struct rset_multior_rfd *rfd_list;
  95 };
  96
  97
  98 struct rset_multior_rfd {
  99     int flag;
 100     struct heap_item *items; /* we alloc and free them here */
 101     HEAP h;
 102     struct rset_multior_rfd *next;
 103     struct rset_multior_info *info;
 104     zint *countp; /* inc at every new record we see */
 105     zint hits; /* returned so far */
 106     char *prevvalue; /* to see if we are in another record */
 107 };
 108
 109 #if 0
 110 static void heap_dump_item( HEAP h, int i, int level) {
 111     double cur,tot;
 112     if (i>h->heapnum)
 113         return;
 114     (void)rset_pos(h->heap[i]->rset,h->heap[i]->fd, &cur, &tot);
 115     logf(LOG_LOG," %d %*s i=%p buf=%p %0.1f/%0.1f",i, level, "",
 116                     &(h->heap[i]), h->heap[i]->buf, cur,tot );
 117     heap_dump_item(h, 2*i, level+1);
 118     heap_dump_item(h, 2*i+1, level+1);
 119 }
 120 static void heap_dump( HEAP h,char *msg) {
 121     logf(LOG_LOG, "heap dump: %s num=%d max=%d",msg, h->heapnum, h->heapmax);
 122     heap_dump_item(h,1,1);
 123 }
 124 #endif
 125
 126 static void heap_swap (HEAP h, int x, int y)
 127 {
 128     struct heap_item *swap;
 129     swap = h->heap[x];
 130     h->heap[x]=h->heap[y];
 131     h->heap[y]=swap;
 132 }
 133
 134 static int heap_cmp(HEAP h, int x, int y)
 135 {
 136     return (*h->cmp)(h->heap[x]->buf,h->heap[y]->buf);
 137 }
 138
 139 static int heap_empty(HEAP h)
 140 {
 141     return ( 0==h->heapnum );
 142 }
 143
 144 static void heap_delete (HEAP h)
 145 { /* deletes the first item in the heap, and balances the rest */
 146     int cur = 1, child = 2;
 147     h->heap[1]=0; /* been deleted */
 148     heap_swap (h, 1, h->heapnum--);
 149     while (child <= h->heapnum) {
 150         if (child < h->heapnum && heap_cmp(h,child,1+child)>0 )
 151             child++;
 152         if (heap_cmp(h,cur,child) > 0)
 153         {
 154             heap_swap (h, cur, child);
 155             cur = child;
 156             child = 2*cur;
 157         }
 158         else
 159             break;
 160     }
 161 }
 162
 163 static void heap_balance (HEAP h)
 164 { /* The heap root element has changed value (to bigger) */
 165   /* swap downwards until the heap is ordered again */
 166     int cur = 1, child = 2;
 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
 182 static void heap_insert (HEAP h, struct heap_item *hi)
 183 {
 184     int cur, parent;
 185
 186     cur = ++(h->heapnum);
 187     assert(cur <= h->heapmax);
 188     h->heap[cur]=hi;
 189     parent = cur/2;
 190     while (parent && (heap_cmp(h,parent,cur) > 0))
 191     {
 192         assert(parent>0);
 193         heap_swap (h, cur, parent);
 194         cur = parent;
 195         parent = cur/2;
 196     }
 197 }
 198
 199
 200 static
 201 HEAP heap_create (int size, int key_size,
 202       int (*cmp)(const void *p1, const void *p2))
 203 {
 204     HEAP h = (HEAP) xmalloc (sizeof(*h));
 205
 206     ++size; /* heap array starts at 1 */
 207     h->heapnum = 0;
 208     h->heapmax = size;
 209     h->keysize = key_size;
 210     h->cmp = cmp;
 211     h->heap = (struct heap_item**) xmalloc((size)*sizeof(*h->heap));
 212     h->heap[0]=0; /* not used */
 213     return h;
 214 }
 215
 216 static void heap_destroy (HEAP h)
 217 {
 218     xfree (h->heap); /* safe, they all point to the rfd */
 219     xfree (h);
 220 }
 221
 222
 223 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
 224 {
 225     rset_multior_parms *r_parms = (rset_multior_parms *) parms;
 226     struct rset_multior_info *info;
 227
 228     ct->flags |= RSET_FLAG_VOLATILE;
 229         /* FIXME - Remove the whole flags thing, from all rsets */
 230     info = (struct rset_multior_info *) xmalloc (sizeof(*info));
 231     info->key_size = r_parms->key_size;
 232     assert (info->key_size > 1);
 233     info->cmp = r_parms->cmp;
 234     info->no_rsets= r_parms->no_rsets;
 235     info->rsets=r_parms->rsets; /* now we own it! */
 236     info->rfd_list=0;
 237     info->term_index=0 ; /* r_parms->rset_term; */ /*??*/ /*FIXME */
 238     ct->no_rset_terms = 1;
 239     ct->rset_terms = (RSET_TERM *) xmalloc (sizeof(*ct->rset_terms));
 240     ct->rset_terms[0] = r_parms->rset_term;
 241     return info;
 242 }
 243
 244 static RSFD r_open (RSET ct, int flag)
 245 {
 246     struct rset_multior_rfd *rfd;
 247     struct rset_multior_info *info = (struct rset_multior_info *) ct->buf;
 248     int i;
 249     int dummy_termindex;
 250
 251     if (flag & RSETF_WRITE)
 252     {
 253         logf (LOG_FATAL, "multior set type is read-only");
 254         return NULL;
 255     }
 256     rfd = (struct rset_multior_rfd *) xmalloc (sizeof(*rfd));
 257     rfd->flag = flag;
 258     rfd->next = info->rfd_list;
 259     rfd->info = info;
 260     info->rfd_list = rfd;
 261     if (ct->no_rset_terms==1)
 262         rfd->countp=&ct->rset_terms[0]->count;
 263     else
 264         rfd->countp=0;
 265     rfd->h = heap_create( info->no_rsets, info->key_size, info->cmp);
 266     rfd->prevvalue=0;
 267     rfd->hits=0;
 268     rfd->items=(struct heap_item *) xmalloc(info->no_rsets*sizeof(*rfd->items));
 269     for (i=0; i<info->no_rsets; i++){
 270        rfd->items[i].rset=info->rsets[i];
 271        rfd->items[i].buf=xmalloc(info->key_size);
 272        rfd->items[i].fd=rset_open(info->rsets[i],RSETF_READ);
 273 /*       if (item_readbuf(&(rfd->items[i]))) */
 274        if ( rset_read(rfd->items[i].rset, rfd->items[i].fd,
 275                       rfd->items[i].buf, &dummy_termindex) )
 276            heap_insert(rfd->h, &(rfd->items[i]));
 277     }
 278     return rfd;
 279 }
 280
 281 static void r_close (RSFD rfd)
 282 {
 283     struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
 284     struct rset_multior_info *info = mrfd->info;
 285     struct rset_multior_rfd **rfdp;
 286     int i;
 287
 288     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 289         if (*rfdp == rfd)
 290         {
 291             *rfdp = (*rfdp)->next;
 292
 293             heap_destroy (mrfd->h);
 294             for (i = 0; i<info->no_rsets; i++) {
 295                 if (mrfd->items[i].fd)
 296                     rset_close(info->rsets[i],mrfd->items[i].fd);
 297                 xfree(mrfd->items[i].buf);
 298             }
 299             xfree(mrfd->items);
 300             if (mrfd->prevvalue)
 301                 xfree(mrfd->prevvalue);
 302             xfree(mrfd);
 303             return;
 304         }
 305     logf (LOG_FATAL, "r_close but no rfd match!");
 306     assert (0);
 307 }
 308
 309 static void r_delete (RSET ct)
 310 {
 311     struct rset_multior_info *info = (struct rset_multior_info *) ct->buf;
 312     int i;
 313
 314     assert (info->rfd_list == NULL);
 315     for(i=0;i<info->no_rsets;i++)
 316         rset_delete(info->rsets[i]);
 317     xfree(info->rsets);
 318     xfree(info);
 319
 320     for (i = 0; i<ct->no_rset_terms; i++) /* usually only 1 */
 321         rset_term_destroy (ct->rset_terms[i]);
 322     xfree (ct->rset_terms);
 323 }
 324
 325 static void r_rewind (RSFD rfd)
 326 {
 327     assert(!"rewind not implemented yet");
 328 }
 329
 330
 331 static int r_forward(RSET ct, RSFD rfd, void *buf,  int *term_index,
 332                      int (*cmpfunc)(const void *p1, const void *p2),
 333                      const void *untilbuf)
 334 {
 335     struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
 336     struct rset_multior_info *info = mrfd->info;
 337     struct heap_item it;
 338     int rdres;
 339     int dummycount=0;
 340     if (heap_empty(mrfd->h))
 341         return 0;
 342     if (cmpfunc)
 343         assert(cmpfunc==mrfd->info->cmp);
 344     *term_index=0;
 345     it = *(mrfd->h->heap[1]);
 346     memcpy(buf,it.buf, info->key_size);
 347     (mrfd->hits)++;
 348     if (mrfd->countp) {
 349         if (mrfd->prevvalue) {  /* in another record */
 350             if ( (*mrfd->info->cmp)(mrfd->prevvalue,it.buf) < -1)
 351                 (*mrfd->countp)++;
 352         } else {
 353             mrfd->prevvalue=xmalloc(info->key_size);
 354             (*mrfd->countp)++;
 355         }
 356         memcpy(mrfd->prevvalue,it.buf, info->key_size);
 357     }
 358     if (untilbuf)
 359         rdres=rset_forward(it.rset, it.fd, it.buf, &dummycount,
 360                            cmpfunc,untilbuf);
 361     else
 362         rdres=rset_read(it.rset, it.fd, it.buf, &dummycount);
 363     if ( rdres )
 364         heap_balance(mrfd->h);
 365     else
 366         heap_delete(mrfd->h);
 367     return 1;
 368
 369 }
 370
 371 static int r_read (RSFD rfd, void *buf, int *term_index)
 372 {
 373     return r_forward(0,rfd, buf, term_index,0,0);
 374 }
 375
 376 static void r_pos (RSFD rfd, double *current, double *total)
 377 {
 378     struct rset_multior_rfd *mrfd = (struct rset_multior_rfd *) rfd;
 379     struct rset_multior_info *info = mrfd->info;
 380     double cur, tot;
 381     double scur=0.0, stot=0.0;
 382     int i;
 383     for (i=0; i<info->no_rsets; i++){
 384         rset_pos(mrfd->items[i].rset, mrfd->items[i].fd, &cur, &tot);
 385         logf(LOG_LOG, "r_pos: %d %0.1f %0.1f", i, cur,tot);
 386         scur += cur;
 387         stot += tot;
 388     }
 389     if (stot <1.0) { /* nothing there */
 390         *current=0;
 391         *total=0;
 392         return;
 393     }
 394     *current=mrfd->hits;
 395     *total=*current*stot/scur;
 396 }
 397
 398 static int r_write (RSFD rfd, const void *buf)
 399 {
 400     logf (LOG_FATAL, "multior set type is read-only");
 401     return -1;
 402 }