rset/rsbool.c

   1 /* $Id: rsbool.c,v 1.24 2004-01-30 11:43:41 heikki Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003
   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
  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 #include <../index/index.h> /* for log_keydump. Debugging only */
  34
  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     rfd->next = info->rfd_list;
 164     info->rfd_list = rfd;
 165     rfd->info = info;
 166
 167     rfd->buf_l = xmalloc (info->key_size);
 168     rfd->buf_r = xmalloc (info->key_size);
 169     rfd->rfd_l = rset_open (info->rset_l, RSETF_READ);
 170     rfd->rfd_r = rset_open (info->rset_r, RSETF_READ);
 171     rfd->more_l = rset_read (info->rset_l, rfd->rfd_l, rfd->buf_l,
 172                              &rfd->term_index_l);
 173     rfd->more_r = rset_read (info->rset_r, rfd->rfd_r, rfd->buf_r,
 174                              &rfd->term_index_r);
 175     rfd->tail = 0;
 176     return rfd;
 177 }
 178
 179 static void r_close (RSFD rfd)
 180 {
 181     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 182     struct rset_bool_rfd **rfdp;
 183
 184     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 185         if (*rfdp == rfd)
 186         {
 187             xfree ((*rfdp)->buf_l);
 188             xfree ((*rfdp)->buf_r);
 189             rset_close (info->rset_l, (*rfdp)->rfd_l);
 190             rset_close (info->rset_r, (*rfdp)->rfd_r);
 191             *rfdp = (*rfdp)->next;
 192             xfree (rfd);
 193             return;
 194         }
 195     logf (LOG_FATAL, "r_close but no rfd match!");
 196     assert (0);
 197 }
 198
 199 static void r_delete (RSET ct)
 200 {
 201     struct rset_bool_info *info = (struct rset_bool_info *) ct->buf;
 202
 203     assert (info->rfd_list == NULL);
 204     xfree (ct->rset_terms);
 205     rset_delete (info->rset_l);
 206     rset_delete (info->rset_r);
 207     xfree (info);
 208 }
 209
 210 static void r_rewind (RSFD rfd)
 211 {
 212     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 213     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 214
 215     logf (LOG_DEBUG, "rsbool_rewind");
 216     rset_rewind (info->rset_l, p->rfd_l);
 217     rset_rewind (info->rset_r, p->rfd_r);
 218     p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l, &p->term_index_l);
 219     p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r, &p->term_index_r);
 220 }
 221
 222 static int r_forward(RSET ct, RSFD rfd, void *buf, int *term_index,
 223                      int (*cmpfunc)(const void *p1, const void *p2),
 224                      const void *untilbuf)
 225 {
 226     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 227     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 228     int cmp=0;
 229
 230     logf (LOG_DEBUG, "rsbool_forward '%s' (ct=%p rfd=%p m=%d,%d)",
 231                       ct->control->desc, ct, rfd, p->more_l, p->more_r);
 232     if ( p->more_l)
 233         p->more_l = rset_forward(info->rset_l, p->rfd_l, p->buf_l,
 234                         &p->term_index_l, info->cmp, untilbuf);
 235     if ( p->more_r)
 236         p->more_r = rset_forward(info->rset_r, p->rfd_r, p->buf_r,
 237                         &p->term_index_r, info->cmp, untilbuf);
 238     if (p->more_l && p->more_r)
 239            cmp = (*info->cmp)(p->buf_l, p->buf_r);
 240        else if (p->more_l)
 241            cmp = -2;
 242        else
 243            cmp = 2;
 244     if ( (cmp<0) && (p->more_l) )
 245     {
 246         memcpy (buf, p->buf_l, info->key_size);
 247             *term_index = p->term_index_l;
 248     } else if ( (cmp>0) && (p->more_r) )
 249     {
 250         memcpy (buf, p->buf_r, info->key_size);
 251             *term_index = p->term_index_r + info->term_index_s;
 252     }
 253     return ( p->more_l || p->more_r);
 254 }
 255
 256 static int r_count (RSET ct)
 257 {
 258     return 0;
 259 }
 260
 261
 262 /*
 263     1,1         1,3
 264     1,9         2,1
 265     1,11        3,1
 266     2,9
 267
 268   1,1     1,1
 269   1,3     1,3
 270           1,9
 271           1,11
 272   2,1     2,1
 273           2,9
 274           3,1
 275 */
 276
 277 static int r_read_and (RSFD rfd, void *buf, int *term_index)
 278 {
 279     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 280     struct rset_bool_info *info = p->info;
 281
 282     while (p->more_l || p->more_r)
 283     {
 284         int cmp;
 285
 286         if (p->more_l && p->more_r)
 287             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 288         else if (p->more_l)
 289             cmp = -2;
 290         else
 291             cmp = 2;
 292         logf (LOG_DEBUG, "r_read_and looping: m=%d/%d c=%d t=%d",
 293                         p->more_l, p->more_r, cmp, p->tail);
 294         key_logdump(LOG_DEBUG,p->buf_l);
 295         key_logdump(LOG_DEBUG,p->buf_r);
 296         if (!cmp)
 297         {
 298             memcpy (buf, p->buf_l, info->key_size);
 299                 *term_index = p->term_index_l;
 300             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 301                                    &p->term_index_l);
 302             p->tail = 1;
 303         }
 304         else if (cmp == 1)
 305         {
 306             memcpy (buf, p->buf_r, info->key_size);
 307                 *term_index = p->term_index_r + info->term_index_s;
 308             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 309                                    &p->term_index_r);
 310             p->tail = 1;
 311             logf (LOG_DEBUG, "r_read_and returning A m=%d/%d c=%d",
 312                     p->more_l, p->more_r, cmp);
 313             key_logdump(LOG_DEBUG,buf);
 314             return 1;
 315         }
 316         else if (cmp == -1)
 317         {
 318             memcpy (buf, p->buf_l, info->key_size);
 319                 *term_index = p->term_index_l;
 320             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 321                                    &p->term_index_l);
 322             p->tail = 1;
 323             logf (LOG_DEBUG, "r_read_and returning B m=%d/%d c=%d",
 324                     p->more_l, p->more_r, cmp);
 325             key_logdump(LOG_DEBUG,buf);
 326             return 1;
 327         }
 328         else if (cmp > 1)
 329         {
 330 #define OLDCODE 0
 331 #if OLDCODE
 332             memcpy (buf, p->buf_r, info->key_size);
 333             *term_index = p->term_index_r + info->term_index_s;
 334
 335             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 336                                    &p->term_index_r);
 337             if (p->tail)
 338             {
 339                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 340                     p->tail = 0;
 341                 logf (LOG_DEBUG, "r_read_and returning C m=%d/%d c=%d",
 342                         p->more_l, p->more_r, cmp);
 343                 key_logdump(LOG_DEBUG,buf);
 344                 return 1;
 345             }
 346 #else
 347
 348             if (p->tail)
 349             {
 350                 logf (LOG_DEBUG, "r_read_and returning R tail m=%d/%d c=%d",
 351                         p->more_l, p->more_r, cmp);
 352                 memcpy (buf, p->buf_r, info->key_size);
 353                 *term_index = p->term_index_r + info->term_index_s;
 354                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 355                                    &p->term_index_r);
 356                 if (!p->more_r || (*info->cmp)(p->buf_r, buf) > 1)
 357                     p->tail = 0;
 358                 logf (LOG_DEBUG, "r_read_and returning D m=%d/%d c=%d",
 359                         p->more_l, p->more_r, cmp);
 360                 key_logdump(LOG_DEBUG,buf);
 361                 return 1;
 362             } else
 363             {
 364                 logf (LOG_DEBUG, "r_read_and about to forward R m=%d/%d c=%d",
 365                         p->more_l, p->more_r, cmp);
 366                 if (p->more_r && p->more_l)
 367                     p->more_r = rset_forward(
 368                                     info->rset_r, p->rfd_r,
 369                                     p->buf_r, &p->term_index_r,
 370                                     (info->cmp), p->buf_l);
 371                 else
 372                     return 0; /* no point in reading further */
 373             }
 374 #endif
 375         }
 376         else
 377         {
 378 #if OLDCODE
 379              memcpy (buf, p->buf_l, info->key_size);
 380              *term_index = p->term_index_l;
 381              p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 382                                     &p->term_index_l);
 383              if (p->tail)
 384              {
 385                  if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 386                      p->tail = 0;
 387                  logf (LOG_DEBUG, "r_read_and returning E m=%d/%d c=%d",
 388                         p->more_l, p->more_r, cmp);
 389                  key_logdump(LOG_DEBUG,buf);
 390                  return 1;
 391              }
 392 #else
 393             if (p->tail)
 394             {
 395                 logf (LOG_DEBUG, "r_read_and returning L tail m=%d/%d c=%d",
 396                         p->more_l, p->more_r, cmp);
 397                 memcpy (buf, p->buf_l, info->key_size);
 398                     *term_index = p->term_index_l;
 399                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 400                                    &p->term_index_l);
 401                 if (!p->more_l || (*info->cmp)(p->buf_l, buf) > 1)
 402                     p->tail = 0;
 403                  logf (LOG_DEBUG, "r_read_and returning F m=%d/%d c=%d",
 404                         p->more_l, p->more_r, cmp);
 405                  key_logdump(LOG_DEBUG,buf);
 406                 return 1;
 407             }
 408             else
 409             {
 410                 logf (LOG_DEBUG, "r_read_and about to forward L m=%d/%d c=%d",
 411                         p->more_l, p->more_r, cmp);
 412                 if (p->more_r && p->more_l)
 413                     p->more_l = rset_forward(
 414                     /* p->more_l = rset_default_forward( */
 415                                     info->rset_l, p->rfd_l,
 416                                     p->buf_l, &p->term_index_l,
 417                                     (info->cmp), p->buf_r);
 418                 else
 419                     return 0; /* no point in reading further */
 420             }
 421 #endif
 422         }
 423     }
 424     return 0;
 425 }
 426
 427 static int r_read_or (RSFD rfd, void *buf, int *term_index)
 428 {
 429     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 430     struct rset_bool_info *info = p->info;
 431
 432     while (p->more_l || p->more_r)
 433     {
 434         int cmp;
 435
 436         if (p->more_l && p->more_r)
 437             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 438         else if (p->more_r)
 439             cmp = 2;
 440         else
 441             cmp = -2;
 442         if (!cmp)
 443         {
 444             memcpy (buf, p->buf_l, info->key_size);
 445                 *term_index = p->term_index_l;
 446             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 447                                    &p->term_index_l);
 448             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 449                                    &p->term_index_r);
 450             logf (LOG_DEBUG, "r_read_or returning A m=%d/%d c=%d",
 451                     p->more_l, p->more_r, cmp);
 452             key_logdump(LOG_DEBUG,buf);
 453             return 1;
 454         }
 455         else if (cmp > 0)
 456         {
 457             memcpy (buf, p->buf_r, info->key_size);
 458                 *term_index = p->term_index_r + info->term_index_s;
 459             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 460                                    &p->term_index_r);
 461             logf (LOG_DEBUG, "r_read_or returning B m=%d/%d c=%d",
 462                     p->more_l, p->more_r, cmp);
 463             key_logdump(LOG_DEBUG,buf);
 464             return 1;
 465         }
 466         else
 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             logf (LOG_DEBUG, "r_read_or returning C m=%d/%d c=%d",
 473                     p->more_l, p->more_r, cmp);
 474             key_logdump(LOG_DEBUG,buf);
 475             return 1;
 476         }
 477     }
 478     return 0;
 479 }
 480
 481 static int r_read_not (RSFD rfd, void *buf, int *term_index)
 482 {
 483     struct rset_bool_rfd *p = (struct rset_bool_rfd *) rfd;
 484     struct rset_bool_info *info = p->info;
 485
 486     while (p->more_l || p->more_r)
 487     {
 488         int cmp;
 489
 490         if (p->more_l && p->more_r)
 491             cmp = (*info->cmp)(p->buf_l, p->buf_r);
 492         else if (p->more_r)
 493             cmp = 2;
 494         else
 495             cmp = -2;
 496         if (cmp < -1)
 497         {
 498             memcpy (buf, p->buf_l, info->key_size);
 499                 *term_index = p->term_index_l;
 500             p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 501                                    &p->term_index_l);
 502             return 1;
 503         }
 504         else if (cmp > 1)
 505 #if 0
 506             p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 507                                    &p->term_index_r);
 508 #else
 509             p->more_r = rset_forward(
 510                             info->rset_r, p->rfd_r,
 511                             p->buf_r, &p->term_index_r,
 512                             (info->cmp), p->buf_l);
 513 #endif
 514         else
 515         {
 516             memcpy (buf, p->buf_l, info->key_size);
 517             do
 518             {
 519                 p->more_l = rset_read (info->rset_l, p->rfd_l, p->buf_l,
 520                                        &p->term_index_l);
 521                 if (!p->more_l)
 522                     break;
 523                 cmp = (*info->cmp)(p->buf_l, buf);
 524             } while (cmp >= -1 && cmp <= 1);
 525             do
 526             {
 527                 p->more_r = rset_read (info->rset_r, p->rfd_r, p->buf_r,
 528                                        &p->term_index_r);
 529                 if (!p->more_r)
 530                     break;
 531                 cmp = (*info->cmp)(p->buf_r, buf);
 532             } while (cmp >= -1 && cmp <= 1);
 533         }
 534     }
 535     return 0;
 536 }
 537
 538
 539 static int r_write (RSFD rfd, const void *buf)
 540 {
 541     logf (LOG_FATAL, "bool set type is read-only");
 542     return -1;
 543 }
 544