rset/rsbool.c

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