rset/rsprox.c

   1 /* $Id: rsprox.c,v 1.11 2004-08-24 14:25:16 heikki Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
   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 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <assert.h>
  27
  28 #include <zebrautl.h>
  29 #include <rsprox.h>
  30
  31 #ifndef RSET_DEBUG
  32 #define RSET_DEBUG 0
  33 #endif
  34
  35 static RSFD r_open (RSET ct, int flag);
  36 static void r_close (RSFD rfd);
  37 static void r_delete (RSET ct);
  38 static void r_rewind (RSFD rfd);
  39 static int r_forward(RSET ct, RSFD rfd, void *buf,
  40                      int (*cmpfunc)(const void *p1, const void *p2),
  41                      const void *untilbuf);
  42 static int r_read (RSFD rfd, void *buf);
  43 static int r_write (RSFD rfd, const void *buf);
  44 static void r_pos (RSFD rfd, double *current, double *total);
  45
  46 static const struct rset_control control =
  47 {
  48     "prox",
  49     r_open,
  50     r_close,
  51     r_delete,
  52     r_rewind,
  53     r_forward,
  54     r_pos,
  55     r_read,
  56     r_write,
  57 };
  58
  59 const struct rset_control *rset_kind_prox = &control;
  60
  61 struct rset_prox_info {
  62 /*    struct rset_prox_parms p; */
  63     RSET *rset;
  64     int rset_no;
  65     int ordered;
  66     int exclusion;
  67     int relation;
  68     int distance;
  69     int key_size;
  70     int (*cmp)(const void *p1, const void *p2);
  71     int (*getseq)(const void *p);
  72     struct rset_prox_rfd *rfd_list;
  73 };
  74
  75 struct rset_prox_rfd {
  76     RSFD *rfd;
  77     char **buf;  /* lookahead key buffers */
  78     char *more;  /* more in each lookahead? */
  79     struct rset_prox_rfd *next;
  80     struct rset_prox_info *info;
  81     zint hits;
  82 };
  83
  84
  85 RSET rsprox_create( NMEM nmem, int key_size,
  86             int (*cmp)(const void *p1, const void *p2),
  87             int (*getseq)(const void *p),
  88             int rset_no, RSET *rset,
  89             int ordered, int exclusion,
  90             int relation, int distance)
  91 {
  92     RSET rnew=rset_create_base(&control, nmem);
  93     struct rset_prox_info *info;
  94     info = (struct rset_prox_info *) nmem_malloc(rnew->nmem,sizeof(*info));
  95     info->key_size = key_size;
  96     info->cmp = cmp;
  97     info->getseq=getseq; /* FIXME - what about multi-level stuff ?? */
  98     info->rset = nmem_malloc(rnew->nmem,rset_no * sizeof(*info->rset));
  99     memcpy(info->rset, rset,
 100            rset_no * sizeof(*info->rset));
 101     info->rset_no=rset_no;
 102     info->ordered=ordered;
 103     info->exclusion=exclusion;
 104     info->relation=relation;
 105     info->distance=distance;
 106     info->rfd_list = NULL;
 107     rnew->priv=info;
 108     return rnew;
 109 }
 110
 111
 112 static void r_delete (RSET ct)
 113 {
 114     struct rset_prox_info *info = (struct rset_prox_info *) ct->priv;
 115     int i;
 116
 117     assert (info->rfd_list == NULL);
 118     for (i = 0; i<info->rset_no; i++)
 119         rset_delete (info->rset[i]);
 120 /*  xfree (info->rset); */  /* nmems! */
 121 /*  xfree (info); */
 122 }
 123
 124 #if 0
 125 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
 126 {
 127     rset_prox_parms *prox_parms = (rset_prox_parms *) parms;
 128     struct rset_prox_info *info;
 129
 130     info = (struct rset_prox_info *) xmalloc (sizeof(*info));
 131     memcpy(&info->p, prox_parms, sizeof(struct rset_prox_parms));
 132     assert(info->p.rset_no >= 2);
 133     info->p.rset = xmalloc(info->p.rset_no * sizeof(*info->p.rset));
 134     memcpy(info->p.rset, prox_parms->rset,
 135            info->p.rset_no * sizeof(*info->p.rset));
 136     info->rfd_list = NULL;
 137     return info;
 138 }
 139 #endif
 140
 141 static RSFD r_open (RSET ct, int flag)
 142 {
 143     struct rset_prox_info *info = (struct rset_prox_info *) ct->priv;
 144     struct rset_prox_rfd *rfd;
 145     int i;
 146
 147     if (flag & RSETF_WRITE)
 148     {
 149         logf (LOG_FATAL, "prox set type is read-only");
 150         return NULL;
 151     }
 152     rfd = (struct rset_prox_rfd *) xmalloc (sizeof(*rfd));
 153     logf(LOG_DEBUG,"rsprox (%s) open [%p]", ct->control->desc, rfd);
 154     rfd->next = info->rfd_list;
 155     info->rfd_list = rfd;
 156     rfd->info = info;
 157
 158     rfd->more = xmalloc (sizeof(*rfd->more) * info->rset_no);
 159
 160     rfd->buf = xmalloc(sizeof(*rfd->buf) * info->rset_no);
 161     for (i = 0; i < info->rset_no; i++)
 162         rfd->buf[i] = xmalloc (info->key_size);
 163
 164     rfd->rfd = xmalloc(sizeof(*rfd->rfd) * info->rset_no);
 165     for (i = 0; i < info->rset_no; i++)
 166         rfd->rfd[i] = rset_open (info->rset[i], RSETF_READ);
 167
 168     for (i = 0; i < info->rset_no; i++)
 169         rfd->more[i] = rset_read (info->rset[i], rfd->rfd[i],
 170                                   rfd->buf[i]);
 171     rfd->hits=0;
 172     return rfd;
 173 }
 174
 175 static void r_close (RSFD rfd)
 176 {
 177     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
 178     struct rset_prox_rfd **rfdp;
 179
 180     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 181         if (*rfdp == rfd)
 182         {
 183             int i;
 184             for (i = 0; i<info->rset_no; i++)
 185                 xfree ((*rfdp)->buf[i]);
 186             xfree ((*rfdp)->buf);
 187             xfree ((*rfdp)->more);
 188
 189             for (i = 0; i<info->rset_no; i++)
 190                 rset_close (info->rset[i], (*rfdp)->rfd[i]);
 191             xfree ((*rfdp)->rfd);
 192
 193             *rfdp = (*rfdp)->next;
 194             xfree (rfd);
 195             return;
 196         }
 197     logf (LOG_FATAL, "r_close but no rfd match!");
 198     assert (0);
 199 }
 200
 201 static void r_rewind (RSFD rfd)
 202 {
 203     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
 204     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
 205     int i;
 206
 207     logf (LOG_DEBUG, "rsprox_rewind");
 208
 209     for (i = 0; i < info->rset_no; i++)
 210     {
 211         rset_rewind (info->rset[i], p->rfd[i]);
 212         p->more[i] = rset_read (info->rset[i], p->rfd[i], p->buf[i]);
 213     }
 214     p->hits=0;
 215 }
 216
 217 static int r_forward (RSET ct, RSFD rfd, void *buf,
 218                       int (*cmpfunc)(const void *p1, const void *p2),
 219                       const void *untilbuf)
 220 {
 221     /* Note: CT is not used. We _can_ pass NULL for it */
 222     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
 223     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
 224     int cmp=0;
 225     int i;
 226
 227     if (untilbuf)
 228     {
 229         /* it's enough to forward first one. Other will follow
 230            automatically */
 231         if ( p->more[0] && ((cmpfunc)(untilbuf, p->buf[0]) >= 2) )
 232             p->more[0] = rset_forward(info->rset[0], p->rfd[0],
 233                                       p->buf[0], info->cmp,
 234                                       untilbuf);
 235     }
 236     if (info->ordered && info->relation == 3 && info->exclusion == 0
 237         && info->distance == 1)
 238     {
 239         while (p->more[0])
 240         {
 241             for (i = 1; i < info->rset_no; i++)
 242             {
 243                 if (!p->more[i])
 244                 {
 245                     p->more[0] = 0;    /* saves us a goto out of while loop. */
 246                     break;
 247                 }
 248                 cmp = (*info->cmp) (p->buf[i], p->buf[i-1]);
 249                 if (cmp > 1)
 250                 {
 251                     p->more[i-1] = rset_forward (info->rset[i-1],
 252                                                  p->rfd[i-1],
 253                                                  p->buf[i-1],
 254                                                  info->cmp,
 255                                                  p->buf[i]);
 256                     break;
 257                 }
 258                 else if (cmp == 1)
 259                 {
 260                     if ((*info->getseq)(p->buf[i-1]) +1 !=
 261                         (*info->getseq)(p->buf[i]))
 262                     {
 263                         p->more[i-1] = rset_read ( info->rset[i-1],
 264                                              p->rfd[i-1], p->buf[i-1]);
 265                         break;
 266                     }
 267                 }
 268                 else
 269                 {
 270                     p->more[i] = rset_forward (info->rset[i], p->rfd[i],
 271                                                p->buf[i], info->cmp,
 272                                                p->buf[i-1]);
 273                     break;
 274                 }
 275             }
 276             if (i == p->info->rset_no)
 277             {
 278                 memcpy (buf, p->buf[0], info->key_size);
 279                 p->more[0] = rset_read (info->rset[0], p->rfd[0], p->buf[0]);
 280                 p->hits++;
 281                 return 1;
 282             }
 283         }
 284     }
 285     else if (info->rset_no == 2)
 286     {
 287         while (p->more[0] && p->more[1])
 288         {
 289             int cmp = (*info->cmp)(p->buf[0], p->buf[1]);
 290             if (cmp < -1)
 291                 p->more[0] = rset_forward (info->rset[0], p->rfd[0],
 292                                            p->buf[0], info->cmp, p->buf[0]);
 293             else if (cmp > 1)
 294                 p->more[1] = rset_forward (info->rset[1], p->rfd[1],
 295                                            p->buf[1], info->cmp, p->buf[1]);
 296             else
 297             {
 298                 int seqno[500];
 299                 int n = 0;
 300
 301                 seqno[n++] = (*info->getseq)(p->buf[0]);
 302                 while ((p->more[0] = rset_read (info->rset[0], p->rfd[0],
 303                                                 p->buf[0])) >= -1 &&
 304                        p->more[0] <= -1)
 305                     if (n < 500)
 306                         seqno[n++] = (*info->getseq)(p->buf[0]);
 307
 308                 for (i = 0; i<n; i++)
 309                 {
 310                     int diff = (*info->getseq)(p->buf[1]) - seqno[i];
 311                     int excl = info->exclusion;
 312                     if (!info->ordered && diff < 0)
 313                         diff = -diff;
 314                     switch (info->relation)
 315                     {
 316                     case 1:      /* < */
 317                         if (diff < info->distance && diff >= 0)
 318                             excl = !excl;
 319                         break;
 320                     case 2:      /* <= */
 321                         if (diff <= info->distance && diff >= 0)
 322                             excl = !excl;
 323                         break;
 324                     case 3:      /* == */
 325                         if (diff == info->distance && diff >= 0)
 326                             excl = !excl;
 327                         break;
 328                     case 4:      /* >= */
 329                         if (diff >= info->distance && diff >= 0)
 330                             excl = !excl;
 331                         break;
 332                     case 5:      /* > */
 333                         if (diff > info->distance && diff >= 0)
 334                             excl = !excl;
 335                         break;
 336                     case 6:      /* != */
 337                         if (diff != info->distance && diff >= 0)
 338                             excl = !excl;
 339                         break;
 340                     }
 341                     if (excl)
 342                     {
 343                         memcpy (buf, p->buf[1], info->key_size);
 344
 345                         p->more[1] = rset_read (info->rset[1],
 346                                                 p->rfd[1], p->buf[1]);
 347                         p->hits++;
 348                         return 1;
 349                     }
 350                 }
 351                 p->more[1] = rset_read (info->rset[1], p->rfd[1],
 352                                         p->buf[1]);
 353             }
 354         }
 355     }
 356     return 0;
 357 }
 358
 359
 360 static int r_read (RSFD rfd, void *buf)
 361 {
 362     { double cur,tot; r_pos(rfd,&cur,&tot); } /*!*/
 363     return r_forward(0, rfd, buf, 0, 0);
 364 }
 365
 366 static int r_write (RSFD rfd, const void *buf)
 367 {
 368     logf (LOG_FATAL, "prox set type is read-only");
 369     return -1;
 370 }
 371
 372 static void r_pos (RSFD rfd, double *current, double *total)
 373 {
 374     struct rset_prox_info *info = ((struct rset_prox_rfd*)rfd)->info;
 375     struct rset_prox_rfd *p = (struct rset_prox_rfd *) rfd;
 376     int i;
 377     double cur,tot=-1;
 378     double scur=0,stot=0;
 379     double r;
 380
 381     logf (LOG_DEBUG, "rsprox_pos");
 382
 383     for (i = 0; i < info->rset_no; i++)
 384     {
 385         rset_pos(info->rset[i], p->rfd[i],  &cur, &tot);
 386         if (tot>0) {
 387             scur += cur;
 388             stot += tot;
 389         }
 390     }
 391     if (tot <0) {  /* nothing found */
 392         *current=-1;
 393         *total=-1;
 394     } else if (tot <1) { /* most likely tot==0 */
 395         *current=0;
 396         *total=0;
 397     } else {
 398         r=scur/stot;
 399         *current=p->hits;
 400         *total=*current/r ;
 401     }
 402     logf(LOG_DEBUG,"prox_pos: [%d] %0.1f/%0.1f= %0.4f ",
 403                     i,*current, *total, r);
 404 }