rset/rsprox.c

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