rset/rsbool.c

   1 /* $Id: rsbool.c,v 1.40 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 <rset.h>
  30 #include <rsbool.h>
  31
  32 #ifndef RSET_DEBUG
  33 #define RSET_DEBUG 0
  34 #endif
  35
  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_forward(RSET ct, RSFD rfd, void *buf,
  41                      int (*cmpfunc)(const void *p1, const void *p2),
  42                      const void *untilbuf);
  43 static void r_pos (RSFD rfd, double *current, double *total);
  44 static int r_read_and (RSFD rfd, void *buf);
  45 static int r_read_or (RSFD rfd, void *buf);
  46 static int r_read_not (RSFD rfd, void *buf);
  47 static int r_write (RSFD rfd, const void *buf);
  48
  49 static const struct rset_control control_and =
  50 {
  51     "and",
  52     r_open,
  53     r_close,
  54     r_delete,
  55     r_rewind,
  56     r_forward,
  57     r_pos,
  58     r_read_and,
  59     r_write,
  60 };
  61
  62 static const struct rset_control control_or =
  63 {
  64     "or",
  65     r_open,
  66     r_close,
  67     r_delete,
  68     r_rewind,
  69     r_forward,
  70     r_pos,
  71     r_read_or,
  72     r_write,
  73 };
  74
  75 static const struct rset_control control_not =
  76 {
  77     "not",
  78     r_open,
  79     r_close,
  80     r_delete,
  81     r_rewind,
  82     r_forward,
  83     r_pos,
  84     r_read_not,
  85     r_write,
  86 };
  87
  88
  89 const struct rset_control *rset_kind_and = &control_and;
  90 const struct rset_control *rset_kind_or = &control_or;
  91 const struct rset_control *rset_kind_not = &control_not;
  92
  93 struct rset_bool_info {
  94     int key_size;
  95     RSET rset_l;
  96     RSET rset_r;
  97     int (*cmp)(const void *p1, const void *p2);
  98     void (*log_item)(int logmask, const void *p, const char *txt);
  99     struct rset_bool_rfd *rfd_list;
 100 };
 101
 102 struct rset_bool_rfd {
 103     zint hits;
 104     RSFD rfd_l;
 105     RSFD rfd_r;
 106     int  more_l;
 107     int  more_r;
 108     void *buf_l;
 109     void *buf_r;
 110     int tail;
 111     struct rset_bool_rfd *next;
 112     struct rset_bool_info *info;
 113 };
 114
 115 static RSET rsbool_create_base( const struct rset_control *ctrl,
 116             NMEM nmem, int key_size,
 117             int (*cmp)(const void *p1, const void *p2),
 118             RSET rset_l, RSET rset_r,
 119             void (*log_item)(int logmask, const void *p, const char *txt) )
 120 {
 121     RSET rnew=rset_create_base(ctrl, nmem);
 122     struct rset_bool_info *info;
 123     info = (struct rset_bool_info *) nmem_malloc(rnew->nmem,sizeof(*info));
 124     info->key_size = key_size;
 125     info->rset_l = rset_l;
 126     info->rset_r = rset_r;
 127     info->cmp = cmp;
 128     info->log_item = log_item;
 129     info->rfd_list = NULL;
 130
 131     rnew->priv=info;
 132     return rnew;
 133 }
 134
 135
 136 RSET rsbool_create_and( NMEM nmem, int key_size,
 137             int (*cmp)(const void *p1, const void *p2),
 138             RSET rset_l, RSET rset_r,
 139             void (*log_item)(int logmask, const void *p, const char *txt) )
 140 {
 141     return rsbool_create_base(rset_kind_and, nmem, key_size, cmp,
 142                               rset_l, rset_r, log_item);
 143 }
 144
 145 RSET rsbool_create_or( NMEM nmem, int key_size,
 146             int (*cmp)(const void *p1, const void *p2),
 147             RSET rset_l, RSET rset_r,
 148             void (*log_item)(int logmask, const void *p, const char *txt) )
 149 {
 150     return rsbool_create_base(rset_kind_or, nmem, key_size, cmp,
 151                               rset_l, rset_r, log_item);
 152 }
 153
 154 RSET rsbool_create_not( NMEM nmem, int key_size,
 155             int (*cmp)(const void *p1, const void *p2),
 156             RSET rset_l, RSET rset_r,
 157             void (*log_item)(int logmask, const void *p, const char *txt) )
 158 {
 159     return rsbool_create_base(rset_kind_not, nmem, key_size, cmp,
 160                               rset_l, rset_r, log_item);
 161 }
 162
 163 static void r_delete (RSET ct)
 164 {
 165     struct rset_bool_info *info = (struct rset_bool_info *) ct->priv;
 166
 167     assert (info->rfd_list == NULL);
 168     rset_delete (info->rset_l);
 169     rset_delete (info->rset_r);
 170     /* xfree (info); */ /* nmem'd */
 171 }
 172
 173 #if 0
 174 static void *r_create (RSET ct, const struct rset_control *sel, void *parms)
 175 {
 176     rset_bool_parms *bool_parms = (rset_bool_parms *) parms;
 177     struct rset_bool_info *info;
 178
 179     info = (struct rset_bool_info *) xmalloc (sizeof(*info));
 180     info->key_size = bool_parms->key_size;
 181     info->rset_l = bool_parms->rset_l;
 182     info->rset_r = bool_parms->rset_r;
 183     info->cmp = bool_parms->cmp;
 184     info->log_item = bool_parms->log_item;
 185     info->rfd_list = NULL;
 186
 187     return info;
 188 }
 189 #endif
 190
 191 static RSFD r_open (RSET ct, int flag)
 192 {
 193     struct rset_bool_info *info = (struct rset_bool_info *) ct->priv;
 194     struct rset_bool_rfd *rfd;
 195
 196     if (flag & RSETF_WRITE)
 197     {
 198         logf (LOG_FATAL, "bool set type is read-only");
 199         return NULL;
 200     }
 201     rfd = (struct rset_bool_rfd *) xmalloc (sizeof(*rfd));
 202     logf(LOG_DEBUG,"rsbool (%s) open [%p]", ct->control->desc, rfd);
 203     rfd->next = info->rfd_list;
 204     info->rfd_list = rfd;
 205     rfd->info = info;
 206     rfd->hits=0;
 207
 208     rfd->buf_l = xmalloc (info->key_size);
 209     rfd->buf_r = xmalloc (info->key_size);
 210     rfd->rfd_l = rset_open (info->rset_l, RSETF_READ);
 211     rfd->rfd_r = rset_open (info->rset_r, RSETF_READ);
 212     rfd->more_l = rset_read (info->rset_l, rfd->rfd_l, rfd->buf_l);
 213     rfd->more_r = rset_read (info->rset_r, rfd->rfd_r, rfd->buf_r);
 214     rfd->tail = 0;
 215     return rfd;
 216 }
 217
 218 static void r_close (RSFD rfd)
 219 {
 220     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 221     struct rset_bool_rfd **rfdp;
 222
 223     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 224         if (*rfdp == rfd)
 225         {
 226             xfree ((*rfdp)->buf_l);
 227             xfree ((*rfdp)->buf_r);
 228             rset_close (info->rset_l, (*rfdp)->rfd_l);
 229             rset_close (info->rset_r, (*rfdp)->rfd_r);
 230             *rfdp = (*rfdp)->next;
 231             xfree (rfd);
 232             return;
 233         }
 234     logf (LOG_FATAL, "r_close but no rfd match!");
 235     assert (0);
 236 }
 237
 238
 239 static void r_rewind (RSFD rfd)
 240 {
 241     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 242     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 243
 244     logf (LOG_DEBUG, "rsbool_rewind");
 245     rset_rewind (info->rset_l, p->rfd_l);
 246     rset_rewind (info->rset_r, p->rfd_r);
 247     p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 248     p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 249     p->hits=0;
 250 }
 251
 252 static int r_forward (RSET ct, RSFD rfd, void *buf,
 253                      int (*cmpfunc)(const void *p1, const void *p2),
 254                      const void *untilbuf)
 255 {
 256     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 257     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 258     int rc;
 259
 260 #if RSET_DEBUG
 261     logf (LOG_DEBUG, "rsbool_forward (L) [%p] '%s' (ct=%p rfd=%p m=%d,%d)",
 262                       rfd, ct->control->desc, ct, rfd, p->more_l, p->more_r);
 263 #endif
 264     if ( p->more_l && ((cmpfunc)(untilbuf,p->buf_l)==2) )
 265         p->more_l = rset_forward(info->rset_l, p->rfd_l, p->buf_l,
 266                         info->cmp, untilbuf);
 267 #if RSET_DEBUG
 268     logf (LOG_DEBUG, "rsbool_forward (R) [%p] '%s' (ct=%p rfd=%p m=%d,%d)",
 269                       rfd, ct->control->desc, ct, rfd, p->more_l, p->more_r);
 270 #endif
 271     if ( p->more_r && ((cmpfunc)(untilbuf,p->buf_r)==2))
 272         p->more_r = rset_forward(info->rset_r, p->rfd_r, p->buf_r,
 273                         info->cmp, untilbuf);
 274 #if RSET_DEBUG
 275     logf (LOG_DEBUG, "rsbool_forward [%p] calling read, m=%d,%d t=%d",
 276                        rfd, p->more_l, p->more_r, p->tail);
 277 #endif
 278
 279     p->tail=0;
 280     rc = rset_read(ct,rfd,buf);
 281 #if RSET_DEBUG
 282     logf (LOG_DEBUG, "rsbool_forward returning [%p] %d m=%d,%d",
 283                        rfd, rc, p->more_l, p->more_r);
 284 #endif
 285     return rc;
 286 }
 287
 288
 289 /*
 290     1,1         1,3
 291     1,9         2,1
 292     1,11        3,1
 293     2,9
 294
 295   1,1     1,1
 296   1,3     1,3
 297           1,9
 298           1,11
 299   2,1     2,1
 300           2,9
 301           3,1
 302 */
 303
 304 static int r_read_and (RSFD rfd, void *buf)
 305 {
 306     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 307     struct rset_bool_info *info = p->info;
 308
 309     while (p->more_l || p->more_r)
 310     {
 311         int cmp;
 312
 313         if (p->more_l && p->more_r)
 314             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 315         else if (p->more_l)
 316             cmp = -2;
 317         else
 318             cmp = 2;
 319 #if RSET_DEBUG
 320         logf (LOG_DEBUG, "r_read_and [%p] looping: m=%d/%d c=%d t=%d",
 321                         rfd, p->more_l, p->more_r, cmp, p->tail);
 322         (*info->log_item)(LOG_DEBUG, p->buf_l, "left ");
 323         (*info->log_item)(LOG_DEBUG, p->buf_r, "right ");
 324 #endif
 325         if (!cmp)
 326         {
 327             memcpy (buf, p->buf_l, info->key_size);
 328             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 329             p->tail = 1;
 330         }
 331         else if (cmp == 1)
 332         {
 333             memcpy (buf, p->buf_r, info->key_size);
 334             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 335             p->tail = 1;
 336 #if RSET_DEBUG
 337             logf (LOG_DEBUG, "r_read_and [%p] returning R m=%d/%d c=%d",
 338                     rfd, p->more_l, p->more_r, cmp);
 339             key_logdump(LOG_DEBUG,buf);
 340             (*info->log_item)(LOG_DEBUG, buf, "");
 341 #endif
 342             p->hits++;
 343             return 1;
 344         }
 345         else if (cmp == -1)
 346         {
 347             memcpy (buf, p->buf_l, info->key_size);
 348             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 349             p->tail = 1;
 350 #if RSET_DEBUG
 351             logf (LOG_DEBUG, "r_read_and [%p] returning L m=%d/%d c=%d",
 352                     rfd, p->more_l, p->more_r, cmp);
 353             (*info->log_item)(LOG_DEBUG, buf, "");
 354 #endif
 355             p->hits++;
 356             return 1;
 357         }
 358         else if (cmp > 1)  /* cmp == 2 */
 359         {
 360 #define OLDCODE 0
 361 #if OLDCODE
 362             memcpy (buf, p->buf_r, info->key_size);
 363
 364             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 365             if (p->tail)
 366             {
 367                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 368                     p->tail = 0;
 369 #if RSET_DEBUG
 370                 logf (LOG_DEBUG, "r_read_and returning C m=%d/%d c=%d",
 371                         p->more_l, p->more_r, cmp);
 372                 (*info->log_item)(LOG_DEBUG, buf, "");
 373 #endif
 374                 p->hits++;
 375                 return 1;
 376             }
 377 #else
 378
 379             if (p->tail)
 380             {
 381                 memcpy (buf, p->buf_r, info->key_size);
 382                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 383                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 384                     p->tail = 0;
 385 #if RSET_DEBUG
 386                 logf (LOG_DEBUG, "r_read_and [%p] returning R tail m=%d/%d c=%d",
 387                         rfd, p->more_l, p->more_r, cmp);
 388                 (*info->log_item)(LOG_DEBUG, buf, "");
 389 #endif
 390                 p->hits++;
 391                 return 1;
 392             }
 393             else
 394             {
 395 #if RSET_DEBUG
 396                 logf (LOG_DEBUG, "r_read_and [%p] about to forward R m=%d/%d c=%d",
 397                         rfd, p->more_l, p->more_r, cmp);
 398 #endif
 399                 if (p->more_r && p->more_l)
 400                     p->more_r = rset_forward( info->rset_r, p->rfd_r,
 401                                     p->buf_r, (info->cmp), p->buf_l);
 402                 else
 403                     return 0; /* no point in reading further */
 404             }
 405 #endif
 406         }
 407         else  /* cmp == -2 */
 408         {
 409 #if OLDCODE
 410              memcpy (buf, p->buf_l, info->key_size);
 411              p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 412              if (p->tail)
 413              {
 414                  if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 415                      p->tail = 0;
 416 #if RSET_DEBUG
 417                  logf (LOG_DEBUG, "r_read_and [%p] returning R tail m=%d/%d c=%d",
 418                         rfd, p->more_l, p->more_r, cmp);
 419                  (*info->log_item)(LOG_DEBUG, buf, "");
 420 #endif
 421                  p->hits++;
 422                  return 1;
 423              }
 424 #else
 425             if (p->tail)
 426             {
 427                 memcpy (buf, p->buf_l, info->key_size);
 428                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 429                 if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 430                     p->tail = 0;
 431 #if RSET_DEBUG
 432                 logf (LOG_DEBUG, "r_read_and [%p] returning L tail m=%d/%d c=%d",
 433                         rfd, p->more_l, p->more_r, cmp);
 434                 (*info->log_item)(LOG_DEBUG, buf, "");
 435 #endif
 436                 p->hits++;
 437                 return 1;
 438             }
 439             else
 440             {
 441 #if RSET_DEBUG
 442                 logf (LOG_DEBUG, "r_read_and [%p] about to forward L m=%d/%d c=%d",
 443                         rfd, p->more_l, p->more_r, cmp);
 444 #endif
 445                 if (p->more_r && p->more_l)
 446                     p->more_l = rset_forward(
 447                                     info->rset_l, p->rfd_l,
 448                                     p->buf_l, (info->cmp), p->buf_r);
 449                 else
 450                     return 0; /* no point in reading further */
 451             }
 452 #endif
 453         }
 454     }
 455 #if RSET_DEBUG
 456     logf (LOG_DEBUG, "r_read_and [%p] reached its end",rfd);
 457 #endif
 458     return 0;
 459 }
 460
 461 static int r_read_or (RSFD rfd, void *buf)
 462 {
 463     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 464     struct rset_bool_info *info = p->info;
 465
 466     while (p->more_l || p->more_r)
 467     {
 468         int cmp;
 469
 470         if (p->more_l && p->more_r)
 471             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 472         else if (p->more_r)
 473             cmp = 2;
 474         else
 475             cmp = -2;
 476         if (!cmp)
 477         {
 478             memcpy (buf, p->buf_l, info->key_size);
 479             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 480             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 481 #if RSET_DEBUG
 482             logf (LOG_DEBUG, "r_read_or returning A m=%d/%d c=%d",
 483                     p->more_l, p->more_r, cmp);
 484             (*info->log_item)(LOG_DEBUG, buf, "");
 485 #endif
 486             p->hits++;
 487             return 1;
 488         }
 489         else if (cmp > 0)
 490         {
 491             memcpy (buf, p->buf_r, info->key_size);
 492             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 493 #if RSET_DEBUG
 494             logf (LOG_DEBUG, "r_read_or returning B m=%d/%d c=%d",
 495                     p->more_l, p->more_r, cmp);
 496             (*info->log_item)(LOG_DEBUG, buf, "");
 497 #endif
 498             p->hits++;
 499             return 1;
 500         }
 501         else
 502         {
 503             memcpy (buf, p->buf_l, info->key_size);
 504             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 505 #if RSET_DEBUG
 506             logf (LOG_DEBUG, "r_read_or returning C m=%d/%d c=%d",
 507                     p->more_l, p->more_r, cmp);
 508             (*info->log_item)(LOG_DEBUG, buf, "");
 509 #endif
 510             p->hits++;
 511             return 1;
 512         }
 513     }
 514     return 0;
 515 }
 516
 517 static int r_read_not (RSFD rfd, void *buf)
 518 {
 519     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 520     struct rset_bool_info *info = p->info;
 521
 522     while (p->more_l || p->more_r)
 523     {
 524         int cmp;
 525
 526         if (p->more_l && p->more_r)
 527             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 528         else if (p->more_r)
 529             cmp = 2;
 530         else
 531             cmp = -2;
 532         if (cmp < -1)
 533         {
 534             memcpy (buf, p->buf_l, info->key_size);
 535             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 536             p->hits++;
 537             return 1;
 538         }
 539         else if (cmp > 1)
 540         {
 541                 p->more_r = rset_forward(
 542                     info->rset_r, p->rfd_r,
 543                     p->buf_r, (info->cmp), p->buf_l);
 544         }
 545         else
 546         {
 547             memcpy (buf, p->buf_l, info->key_size);
 548             do
 549             {
 550                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 551                 if (!p->more_l)
 552                     break;
 553                 cmp = (*info->cmp)(p->buf_l, buf);
 554             } while (cmp >= -1 && cmp <= 1);
 555             do
 556             {
 557                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 558                 if (!p->more_r)
 559                     break;
 560                 cmp = (*info->cmp)(p->buf_r, buf);
 561             } while (cmp >= -1 && cmp <= 1);
 562         }
 563     }
 564     return 0;
 565 }
 566
 567
 568 static int r_write (RSFD rfd, const void *buf)
 569 {
 570     logf (LOG_FATAL, "bool set type is read-only");
 571     return -1;
 572 }
 573
 574 static void r_pos (RSFD rfd, double *current, double *total)
 575 {
 576     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 577     struct rset_bool_info *info = p->info;
 578     double lcur,ltot;
 579     double rcur,rtot;
 580     double r;
 581     ltot=-1; rtot=-1;
 582     rset_pos(info->rset_l, p->rfd_l,  &lcur, &ltot);
 583     rset_pos(info->rset_r, p->rfd_r,  &rcur, &rtot);
 584     if ( (rtot<0) && (ltot<0)) { /*no position */
 585         *current=rcur;  /* return same as you got */
 586         *total=rtot;    /* probably -1 for not available */
 587     }
 588     if ( rtot<0) { rtot=0; rcur=0;} /* if only one useful, use it */
 589     if ( ltot<0) { ltot=0; lcur=0;}
 590     if ( rtot+ltot < 1 ) { /* empty rset */
 591         *current=0;
 592         *total=0;
 593         return;
 594     }
 595     r=1.0*(lcur+rcur)/(ltot+rtot); /* weighed average of l and r */
 596     *current=(double) (p->hits);
 597     *total=*current/r ;
 598 #if RSET_DEBUG
 599     yaz_log(LOG_DEBUG,"bool_pos: (%s/%s) %0.1f/%0.1f= %0.4f ",
 600                     info->rset_l->control->desc, info->rset_r->control->desc,
 601                     *current, *total, r);
 602 #endif
 603 }