rset/rsbool.c

   1 /* $Id: rsbool.c,v 1.42 2004-08-25 13:21:43 adam 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     struct rset_bool_rfd *free_list;
 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
 208     logf(LOG_DEBUG,"rsbool (%s) open [%p]", ct->control->desc, rfd);
 209     rfd->next = info->rfd_list;
 210     info->rfd_list = rfd;
 211     rfd->info = info;
 212     rfd->hits=0;
 213
 214     rfd->buf_l = nmem_malloc(ct->nmem, info->key_size);
 215     rfd->buf_r = nmem_malloc(ct->nmem, info->key_size);
 216     rfd->rfd_l = rset_open (info->rset_l, RSETF_READ);
 217     rfd->rfd_r = rset_open (info->rset_r, RSETF_READ);
 218     rfd->more_l = rset_read (info->rset_l, rfd->rfd_l, rfd->buf_l);
 219     rfd->more_r = rset_read (info->rset_r, rfd->rfd_r, rfd->buf_r);
 220     rfd->tail = 0;
 221     return rfd;
 222 }
 223
 224 static void r_close (RSFD rfd)
 225 {
 226     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 227     struct rset_bool_rfd **rfdp;
 228
 229     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 230         if (*rfdp == rfd)
 231         {
 232             struct rset_bool_rfd *rfd_tmp = *rfdp;
 233
 234             rset_close (info->rset_l, (*rfdp)->rfd_l);
 235             rset_close (info->rset_r, (*rfdp)->rfd_r);
 236             *rfdp = (*rfdp)->next;
 237
 238             rfd_tmp->next = info->free_list;
 239             info->free_list = rfd_tmp;
 240
 241             return;
 242         }
 243     logf (LOG_FATAL, "r_close but no rfd match!");
 244     assert (0);
 245 }
 246
 247
 248 static void r_rewind (RSFD rfd)
 249 {
 250     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 251     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 252
 253     logf (LOG_DEBUG, "rsbool_rewind");
 254     rset_rewind (info->rset_l, p->rfd_l);
 255     rset_rewind (info->rset_r, p->rfd_r);
 256     p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 257     p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 258     p->hits=0;
 259 }
 260
 261 static int r_forward (RSET ct, RSFD rfd, void *buf,
 262                      int (*cmpfunc)(const void *p1, const void *p2),
 263                      const void *untilbuf)
 264 {
 265     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 266     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 267     int rc;
 268
 269 #if RSET_DEBUG
 270     logf (LOG_DEBUG, "rsbool_forward (L) [%p] '%s' (ct=%p rfd=%p m=%d,%d)",
 271                       rfd, ct->control->desc, ct, rfd, p->more_l, p->more_r);
 272 #endif
 273     if ( p->more_l && ((cmpfunc)(untilbuf,p->buf_l)==2) )
 274         p->more_l = rset_forward(info->rset_l, p->rfd_l, p->buf_l,
 275                         info->cmp, untilbuf);
 276 #if RSET_DEBUG
 277     logf (LOG_DEBUG, "rsbool_forward (R) [%p] '%s' (ct=%p rfd=%p m=%d,%d)",
 278                       rfd, ct->control->desc, ct, rfd, p->more_l, p->more_r);
 279 #endif
 280     if ( p->more_r && ((cmpfunc)(untilbuf,p->buf_r)==2))
 281         p->more_r = rset_forward(info->rset_r, p->rfd_r, p->buf_r,
 282                         info->cmp, untilbuf);
 283 #if RSET_DEBUG
 284     logf (LOG_DEBUG, "rsbool_forward [%p] calling read, m=%d,%d t=%d",
 285                        rfd, p->more_l, p->more_r, p->tail);
 286 #endif
 287
 288     p->tail=0;
 289     rc = rset_read(ct,rfd,buf);
 290 #if RSET_DEBUG
 291     logf (LOG_DEBUG, "rsbool_forward returning [%p] %d m=%d,%d",
 292                        rfd, rc, p->more_l, p->more_r);
 293 #endif
 294     return rc;
 295 }
 296
 297
 298 /*
 299     1,1         1,3
 300     1,9         2,1
 301     1,11        3,1
 302     2,9
 303
 304   1,1     1,1
 305   1,3     1,3
 306           1,9
 307           1,11
 308   2,1     2,1
 309           2,9
 310           3,1
 311 */
 312
 313 static int r_read_and (RSFD rfd, void *buf)
 314 {
 315     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 316     struct rset_bool_info *info = p->info;
 317
 318     while (p->more_l || p->more_r)
 319     {
 320         int cmp;
 321
 322         if (p->more_l && p->more_r)
 323             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 324         else if (p->more_l)
 325             cmp = -2;
 326         else
 327             cmp = 2;
 328 #if RSET_DEBUG
 329         logf (LOG_DEBUG, "r_read_and [%p] looping: m=%d/%d c=%d t=%d",
 330                         rfd, p->more_l, p->more_r, cmp, p->tail);
 331         (*info->log_item)(LOG_DEBUG, p->buf_l, "left ");
 332         (*info->log_item)(LOG_DEBUG, p->buf_r, "right ");
 333 #endif
 334         if (!cmp)
 335         {
 336             memcpy (buf, p->buf_l, info->key_size);
 337             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 338             p->tail = 1;
 339         }
 340         else if (cmp == 1)
 341         {
 342             memcpy (buf, p->buf_r, info->key_size);
 343             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 344             p->tail = 1;
 345 #if RSET_DEBUG
 346             logf (LOG_DEBUG, "r_read_and [%p] returning R m=%d/%d c=%d",
 347                     rfd, p->more_l, p->more_r, cmp);
 348             key_logdump(LOG_DEBUG,buf);
 349             (*info->log_item)(LOG_DEBUG, buf, "");
 350 #endif
 351             p->hits++;
 352             return 1;
 353         }
 354         else if (cmp == -1)
 355         {
 356             memcpy (buf, p->buf_l, info->key_size);
 357             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 358             p->tail = 1;
 359 #if RSET_DEBUG
 360             logf (LOG_DEBUG, "r_read_and [%p] returning L m=%d/%d c=%d",
 361                     rfd, p->more_l, p->more_r, cmp);
 362             (*info->log_item)(LOG_DEBUG, buf, "");
 363 #endif
 364             p->hits++;
 365             return 1;
 366         }
 367         else if (cmp > 1)  /* cmp == 2 */
 368         {
 369 #define OLDCODE 0
 370 #if OLDCODE
 371             memcpy (buf, p->buf_r, info->key_size);
 372
 373             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 374             if (p->tail)
 375             {
 376                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 377                     p->tail = 0;
 378 #if RSET_DEBUG
 379                 logf (LOG_DEBUG, "r_read_and returning C m=%d/%d c=%d",
 380                         p->more_l, p->more_r, cmp);
 381                 (*info->log_item)(LOG_DEBUG, buf, "");
 382 #endif
 383                 p->hits++;
 384                 return 1;
 385             }
 386 #else
 387
 388             if (p->tail)
 389             {
 390                 memcpy (buf, p->buf_r, info->key_size);
 391                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 392                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 393                     p->tail = 0;
 394 #if RSET_DEBUG
 395                 logf (LOG_DEBUG, "r_read_and [%p] returning R tail m=%d/%d c=%d",
 396                         rfd, p->more_l, p->more_r, cmp);
 397                 (*info->log_item)(LOG_DEBUG, buf, "");
 398 #endif
 399                 p->hits++;
 400                 return 1;
 401             }
 402             else
 403             {
 404 #if RSET_DEBUG
 405                 logf (LOG_DEBUG, "r_read_and [%p] about to forward R m=%d/%d c=%d",
 406                         rfd, p->more_l, p->more_r, cmp);
 407 #endif
 408                 if (p->more_r && p->more_l)
 409                     p->more_r = rset_forward( info->rset_r, p->rfd_r,
 410                                     p->buf_r, (info->cmp), p->buf_l);
 411                 else
 412                     return 0; /* no point in reading further */
 413             }
 414 #endif
 415         }
 416         else  /* cmp == -2 */
 417         {
 418 #if OLDCODE
 419              memcpy (buf, p->buf_l, info->key_size);
 420              p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 421              if (p->tail)
 422              {
 423                  if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 424                      p->tail = 0;
 425 #if RSET_DEBUG
 426                  logf (LOG_DEBUG, "r_read_and [%p] returning R tail m=%d/%d c=%d",
 427                         rfd, p->more_l, p->more_r, cmp);
 428                  (*info->log_item)(LOG_DEBUG, buf, "");
 429 #endif
 430                  p->hits++;
 431                  return 1;
 432              }
 433 #else
 434             if (p->tail)
 435             {
 436                 memcpy (buf, p->buf_l, info->key_size);
 437                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 438                 if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 439                     p->tail = 0;
 440 #if RSET_DEBUG
 441                 logf (LOG_DEBUG, "r_read_and [%p] returning L tail m=%d/%d c=%d",
 442                         rfd, p->more_l, p->more_r, cmp);
 443                 (*info->log_item)(LOG_DEBUG, buf, "");
 444 #endif
 445                 p->hits++;
 446                 return 1;
 447             }
 448             else
 449             {
 450 #if RSET_DEBUG
 451                 logf (LOG_DEBUG, "r_read_and [%p] about to forward L m=%d/%d c=%d",
 452                         rfd, p->more_l, p->more_r, cmp);
 453 #endif
 454                 if (p->more_r && p->more_l)
 455                     p->more_l = rset_forward(
 456                                     info->rset_l, p->rfd_l,
 457                                     p->buf_l, (info->cmp), p->buf_r);
 458                 else
 459                     return 0; /* no point in reading further */
 460             }
 461 #endif
 462         }
 463     }
 464 #if RSET_DEBUG
 465     logf (LOG_DEBUG, "r_read_and [%p] reached its end",rfd);
 466 #endif
 467     return 0;
 468 }
 469
 470 static int r_read_or (RSFD rfd, void *buf)
 471 {
 472     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 473     struct rset_bool_info *info = p->info;
 474
 475     while (p->more_l || p->more_r)
 476     {
 477         int cmp;
 478
 479         if (p->more_l && p->more_r)
 480             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 481         else if (p->more_r)
 482             cmp = 2;
 483         else
 484             cmp = -2;
 485         if (!cmp)
 486         {
 487             memcpy (buf, p->buf_l, info->key_size);
 488             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 489             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 490 #if RSET_DEBUG
 491             logf (LOG_DEBUG, "r_read_or returning A m=%d/%d c=%d",
 492                     p->more_l, p->more_r, cmp);
 493             (*info->log_item)(LOG_DEBUG, buf, "");
 494 #endif
 495             p->hits++;
 496             return 1;
 497         }
 498         else if (cmp > 0)
 499         {
 500             memcpy (buf, p->buf_r, info->key_size);
 501             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 502 #if RSET_DEBUG
 503             logf (LOG_DEBUG, "r_read_or returning B m=%d/%d c=%d",
 504                     p->more_l, p->more_r, cmp);
 505             (*info->log_item)(LOG_DEBUG, buf, "");
 506 #endif
 507             p->hits++;
 508             return 1;
 509         }
 510         else
 511         {
 512             memcpy (buf, p->buf_l, info->key_size);
 513             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 514 #if RSET_DEBUG
 515             logf (LOG_DEBUG, "r_read_or returning C m=%d/%d c=%d",
 516                     p->more_l, p->more_r, cmp);
 517             (*info->log_item)(LOG_DEBUG, buf, "");
 518 #endif
 519             p->hits++;
 520             return 1;
 521         }
 522     }
 523     return 0;
 524 }
 525
 526 static int r_read_not (RSFD rfd, void *buf)
 527 {
 528     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 529     struct rset_bool_info *info = p->info;
 530
 531     while (p->more_l || p->more_r)
 532     {
 533         int cmp;
 534
 535         if (p->more_l && p->more_r)
 536             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 537         else if (p->more_r)
 538             cmp = 2;
 539         else
 540             cmp = -2;
 541         if (cmp < -1)
 542         {
 543             memcpy (buf, p->buf_l, info->key_size);
 544             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 545             p->hits++;
 546             return 1;
 547         }
 548         else if (cmp > 1)
 549         {
 550                 p->more_r = rset_forward(
 551                     info->rset_r, p->rfd_r,
 552                     p->buf_r, (info->cmp), p->buf_l);
 553         }
 554         else
 555         {
 556             memcpy (buf, p->buf_l, info->key_size);
 557             do
 558             {
 559                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l);
 560                 if (!p->more_l)
 561                     break;
 562                 cmp = (*info->cmp)(p->buf_l, buf);
 563             } while (cmp >= -1 && cmp <= 1);
 564             do
 565             {
 566                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r);
 567                 if (!p->more_r)
 568                     break;
 569                 cmp = (*info->cmp)(p->buf_r, buf);
 570             } while (cmp >= -1 && cmp <= 1);
 571         }
 572     }
 573     return 0;
 574 }
 575
 576
 577 static int r_write (RSFD rfd, const void *buf)
 578 {
 579     logf (LOG_FATAL, "bool set type is read-only");
 580     return -1;
 581 }
 582
 583 static void r_pos (RSFD rfd, double *current, double *total)
 584 {
 585     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 586     struct rset_bool_info *info = p->info;
 587     double lcur,ltot;
 588     double rcur,rtot;
 589     double r;
 590     ltot=-1; rtot=-1;
 591     rset_pos(info->rset_l, p->rfd_l,  &lcur, &ltot);
 592     rset_pos(info->rset_r, p->rfd_r,  &rcur, &rtot);
 593     if ( (rtot<0) && (ltot<0)) { /*no position */
 594         *current=rcur;  /* return same as you got */
 595         *total=rtot;    /* probably -1 for not available */
 596     }
 597     if ( rtot<0) { rtot=0; rcur=0;} /* if only one useful, use it */
 598     if ( ltot<0) { ltot=0; lcur=0;}
 599     if ( rtot+ltot < 1 ) { /* empty rset */
 600         *current=0;
 601         *total=0;
 602         return;
 603     }
 604     r=1.0*(lcur+rcur)/(ltot+rtot); /* weighed average of l and r */
 605     *current=(double) (p->hits);
 606     *total=*current/r ;
 607 #if RSET_DEBUG
 608     yaz_log(LOG_DEBUG,"bool_pos: (%s/%s) %0.1f/%0.1f= %0.4f ",
 609                     info->rset_l->control->desc, info->rset_r->control->desc,
 610                     *current, *total, r);
 611 #endif
 612 }