rset/rsbool.c

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