rset/rsbool.c

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