rset/rsbool.c

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