rset/rssbool.c

   1 /*
   2  * Copyright (C) 1994-1996, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: rssbool.c,v $
   7  * Revision 1.6  1997-12-18 10:54:25  adam
   8  * New method result set method rs_hits that returns the number of
   9  * hits in result-set (if known). The ranked result set returns real
  10  * number of hits but only when not combined with other operands.
  11  *
  12  * Revision 1.5  1997/09/09 13:38:16  adam
  13  * Partial port to WIN95/NT.
  14  *
  15  * Revision 1.4  1996/10/29 13:55:27  adam
  16  * Include of zebrautl.h instead of alexutil.h.
  17  *
  18  * Revision 1.3  1996/10/08 13:00:41  adam
  19  * Bug fix: result sets with ranked operands in boolean operations weren't
  20  * sorted.
  21  *
  22  * Revision 1.2  1996/05/15  18:35:17  adam
  23  * Implemented snot operation.
  24  *
  25  * Revision 1.1  1995/12/11  09:15:27  adam
  26  * New set types: sand/sor/snot - ranked versions of and/or/not in
  27  * ranked/semi-ranked result sets.
  28  * Note: the snot not finished yet.
  29  * New rset member: flag.
  30  * Bug fix: r_delete in rsrel.c did free bad memory block.
  31  *
  32  */
  33
  34 #include <assert.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37
  38 #include <rsbool.h>
  39 #include <zebrautl.h>
  40
  41 static void *r_create_and(const struct rset_control *sel, void *parms,
  42                          int *flags);
  43 static void *r_create_or(const struct rset_control *sel, void *parms,
  44                          int *flags);
  45 static void *r_create_not(const struct rset_control *sel, void *parms,
  46                          int *flags);
  47 static RSFD r_open (RSET ct, int flag);
  48 static void r_close (RSFD rfd);
  49 static void r_delete (RSET ct);
  50 static void r_rewind (RSFD rfd);
  51 static int r_count (RSET ct);
  52 static int r_hits (RSET ct, void *oi);
  53 static int r_read (RSFD rfd, void *buf);
  54 static int r_write (RSFD rfd, const void *buf);
  55 static int r_score (RSFD rfd, int *score);
  56
  57 static const rset_control control_sand =
  58 {
  59     "sand",
  60     r_create_and,
  61     r_open,
  62     r_close,
  63     r_delete,
  64     r_rewind,
  65     r_count,
  66     r_hits,
  67     r_read,
  68     r_write,
  69     r_score
  70 };
  71
  72 static const rset_control control_sor =
  73 {
  74     "sor",
  75     r_create_or,
  76     r_open,
  77     r_close,
  78     r_delete,
  79     r_rewind,
  80     r_count,
  81     r_hits,
  82     r_read,
  83     r_write,
  84     r_score
  85 };
  86
  87 static const rset_control control_snot =
  88 {
  89     "snot",
  90     r_create_not,
  91     r_open,
  92     r_close,
  93     r_delete,
  94     r_rewind,
  95     r_count,
  96     r_hits,
  97     r_read,
  98     r_write,
  99     r_score
 100 };
 101
 102
 103 const rset_control *rset_kind_sand = &control_sand;
 104 const rset_control *rset_kind_sor = &control_sor;
 105 const rset_control *rset_kind_snot = &control_snot;
 106
 107 struct rset_bool_info {
 108     int key_size;
 109     RSET rset_l;
 110     RSET rset_r;
 111     char *key_buf;
 112     int *score_buf;
 113     int *score_idx;
 114     int key_no;
 115     int key_max;
 116     int (*cmp)(const void *p1, const void *p2);
 117     struct rset_bool_rfd *rfd_list;
 118 };
 119
 120 struct rset_bool_rfd {
 121     struct rset_bool_rfd *next;
 122     struct rset_bool_info *info;
 123     int position;
 124     int last_pos;
 125     int flag;
 126 };
 127
 128 static void *r_create_common (const struct rset_control *sel,
 129                               rset_bool_parms *bool_parms, int *flags);
 130
 131 static struct rset_bool_info *qsort_info;
 132
 133 static int qcomp (const void *p1, const void *p2)
 134 {
 135     int i1 = *(int*) p1;
 136     int i2 = *(int*) p2;
 137     return qsort_info->score_buf[i2] - qsort_info->score_buf[i1];
 138 }
 139
 140 static void key_add (struct rset_bool_info *info,
 141                      char *buf, int score)
 142 {
 143     if (info->key_no == info->key_max)
 144         return;
 145     memcpy (info->key_buf + info->key_size * info->key_no,
 146             buf, info->key_size);
 147     info->score_buf[info->key_no] = score;
 148     info->score_idx[info->key_no] = info->key_no;
 149     (info->key_no)++;
 150 }
 151
 152 static void *r_create_and (const struct rset_control *sel, void *parms,
 153                            int *flags)
 154 {
 155     int more_l, more_r;
 156     RSFD fd_l, fd_r;
 157     char *buf_l, *buf_r;
 158
 159     struct rset_bool_info *info;
 160     info = r_create_common (sel, parms, flags);
 161
 162     buf_l = xmalloc (info->key_size);
 163     buf_r = xmalloc (info->key_size);
 164     fd_l = rset_open (info->rset_l, RSETF_SORT_SYSNO|RSETF_READ);
 165     fd_r = rset_open (info->rset_r, RSETF_SORT_SYSNO|RSETF_READ);
 166
 167     more_l = rset_read(info->rset_l, fd_l, buf_l);
 168     more_r = rset_read(info->rset_r, fd_r, buf_r);
 169
 170     while (more_l || more_r)
 171     {
 172         int cmp;
 173         int score, score_l, score_r;
 174
 175         if (more_l && more_r)
 176             cmp = (*info->cmp)(buf_l, buf_r);
 177         else if (more_r)
 178             cmp = 2;
 179         else
 180             cmp = -2;
 181
 182         if (cmp >= -1 && cmp <= 1)
 183         {
 184             rset_score (info->rset_l, fd_l, &score_l);
 185             rset_score (info->rset_r, fd_r, &score_r);
 186             if (score_l == -1)
 187                 score = score_r;
 188             else if (score_r == -1)
 189                 score = score_l;
 190             else
 191                 score = score_l > score_r ? score_r : score_l;
 192             key_add (info, buf_l, score);
 193
 194             more_l = rset_read (info->rset_l, fd_l, buf_l);
 195             more_r = rset_read (info->rset_r, fd_r, buf_r);
 196         }
 197         else if (cmp > 1)
 198             more_r = rset_read (info->rset_r, fd_r, buf_r);
 199         else
 200             more_l = rset_read (info->rset_l, fd_l, buf_l);
 201     }
 202     rset_close (info->rset_l, fd_l);
 203     rset_close (info->rset_r, fd_r);
 204     rset_delete (info->rset_l);
 205     rset_delete (info->rset_r);
 206     xfree (buf_l);
 207     xfree (buf_r);
 208     qsort_info = info;
 209     qsort (info->score_idx, info->key_no, sizeof(*info->score_idx), qcomp);
 210     return info;
 211 }
 212
 213 static void *r_create_or (const struct rset_control *sel, void *parms,
 214                           int *flags)
 215 {
 216     int more_l, more_r;
 217     RSFD fd_l, fd_r;
 218     char *buf_l, *buf_r;
 219
 220     struct rset_bool_info *info;
 221     info = r_create_common (sel, parms, flags);
 222
 223     buf_l = xmalloc (info->key_size);
 224     buf_r = xmalloc (info->key_size);
 225     fd_l = rset_open (info->rset_l, RSETF_SORT_SYSNO|RSETF_READ);
 226     fd_r = rset_open (info->rset_r, RSETF_SORT_SYSNO|RSETF_READ);
 227
 228     more_l = rset_read(info->rset_l, fd_l, buf_l);
 229     more_r = rset_read(info->rset_r, fd_r, buf_r);
 230
 231     while (more_l || more_r)
 232     {
 233         int cmp;
 234         int score, score_l, score_r;
 235
 236         if (more_l && more_r)
 237             cmp = (*info->cmp)(buf_l, buf_r);
 238         else if (more_r)
 239             cmp = 2;
 240         else
 241             cmp = -2;
 242
 243         if (cmp >= -1 && cmp <= 1)
 244         {
 245             rset_score (info->rset_l, fd_l, &score_l);
 246             rset_score (info->rset_r, fd_r, &score_r);
 247             if (score_l == -1)
 248                 score = score_r;
 249             else if (score_r == -1)
 250                 score = score_l;
 251             else
 252                 score = score_r > score_l ? score_r : score_l;
 253             key_add (info, buf_l, score);
 254
 255             more_l = rset_read (info->rset_l, fd_l, buf_l);
 256             more_r = rset_read (info->rset_r, fd_r, buf_r);
 257         }
 258         else if (cmp > 1)
 259         {
 260             rset_score (info->rset_r, fd_r, &score_r);
 261             if (score_r != -1)
 262                 key_add (info, buf_r, score_r / 2);
 263             more_r = rset_read (info->rset_r, fd_r, buf_r);
 264         }
 265         else
 266         {
 267             rset_score (info->rset_l, fd_l, &score_l);
 268             if (score_l != -1)
 269                 key_add (info, buf_l, score_l / 2);
 270             more_l = rset_read (info->rset_l, fd_l, buf_l);
 271         }
 272     }
 273     rset_close (info->rset_l, fd_l);
 274     rset_close (info->rset_r, fd_r);
 275     rset_delete (info->rset_l);
 276     rset_delete (info->rset_r);
 277     xfree (buf_l);
 278     xfree (buf_r);
 279     qsort_info = info;
 280     qsort (info->score_idx, info->key_no, sizeof(*info->score_idx), qcomp);
 281     return info;
 282 }
 283
 284 static void *r_create_not (const struct rset_control *sel, void *parms,
 285                            int *flags)
 286 {
 287     char *buf_l, *buf_r;
 288     int more_l, more_r;
 289     RSFD fd_l, fd_r;
 290
 291     struct rset_bool_info *info;
 292     info = r_create_common (sel, parms, flags);
 293
 294     buf_l = xmalloc (info->key_size);
 295     buf_r = xmalloc (info->key_size);
 296
 297     fd_l = rset_open (info->rset_l, RSETF_SORT_SYSNO|RSETF_READ);
 298     fd_r = rset_open (info->rset_r, RSETF_SORT_SYSNO|RSETF_READ);
 299
 300     more_l = rset_read(info->rset_l, fd_l, buf_l);
 301     more_r = rset_read(info->rset_r, fd_r, buf_r);
 302
 303     while (more_l || more_r)
 304     {
 305         int cmp;
 306         int score;
 307
 308         if (more_l && more_r)
 309             cmp = (*info->cmp)(buf_l, buf_r);
 310         else if (more_r)
 311             cmp = 2;
 312         else
 313             cmp = -2;
 314
 315         if (cmp >= -1 && cmp <= 1)
 316             more_l = rset_read (info->rset_l, fd_l, buf_l);
 317         else if (cmp > 1)
 318         {
 319             more_r = rset_read (info->rset_r, fd_r, buf_r);
 320         }
 321         else
 322         {
 323             rset_score (info->rset_l, fd_l, &score);
 324             key_add (info, buf_l, score == -1 ? 1 : score);
 325             more_l = rset_read (info->rset_l, fd_l, buf_l);
 326         }
 327     }
 328     rset_close (info->rset_l, fd_l);
 329     rset_close (info->rset_r, fd_r);
 330
 331     rset_delete (info->rset_l);
 332     rset_delete (info->rset_r);
 333     xfree (buf_l);
 334     xfree (buf_r);
 335     qsort_info = info;
 336     qsort (info->score_idx, info->key_no, sizeof(*info->score_idx), qcomp);
 337     return info;
 338 }
 339
 340 static void *r_create_common (const struct rset_control *sel,
 341                               rset_bool_parms *bool_parms, int *flags)
 342 {
 343     struct rset_bool_info *info;
 344
 345     info = xmalloc (sizeof(*info));
 346     info->key_size = bool_parms->key_size;
 347     info->rset_l = bool_parms->rset_l;
 348     info->rset_r = bool_parms->rset_r;
 349     info->cmp = bool_parms->cmp;
 350     info->rfd_list = NULL;
 351
 352     if (rset_is_ranked(info->rset_l) || rset_is_ranked(info->rset_r))
 353         *flags |= RSET_FLAG_RANKED;
 354
 355     info->key_max = rset_count(bool_parms->rset_l)
 356                    +rset_count(bool_parms->rset_r);
 357     if (!info->key_max)
 358         info->key_max = 1;
 359     if (info->key_max > 1000)
 360         info->key_max = 1000;
 361     info->key_buf = xmalloc (info->key_size * info->key_max);
 362     info->score_buf = xmalloc (info->key_max * sizeof(*info->score_buf));
 363     info->score_idx = xmalloc (info->key_max * sizeof(*info->score_idx));
 364     info->key_no = 0;
 365
 366     return info;
 367 }
 368
 369 static RSFD r_open (RSET ct, int flag)
 370 {
 371     struct rset_bool_info *info = ct->buf;
 372     struct rset_bool_rfd *rfd;
 373
 374     if (flag & RSETF_WRITE)
 375     {
 376         logf (LOG_FATAL, "sbool set type is read-only");
 377         return NULL;
 378     }
 379     rfd = xmalloc (sizeof(*rfd));
 380     rfd->next = info->rfd_list;
 381     info->rfd_list = rfd;
 382     rfd->info = info;
 383
 384     rfd->position = 0;
 385     rfd->last_pos = 0;
 386     rfd->flag = flag;
 387
 388     return rfd;
 389 }
 390
 391 static void r_close (RSFD rfd)
 392 {
 393     struct rset_bool_info *info = ((struct rset_bool_rfd*)rfd)->info;
 394     struct rset_bool_rfd **rfdp;
 395
 396     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 397         if (*rfdp == rfd)
 398         {
 399             *rfdp = (*rfdp)->next;
 400             xfree (rfd);
 401             return;
 402         }
 403     logf (LOG_FATAL, "r_close but no rfd match!");
 404     assert (0);
 405 }
 406
 407 static void r_delete (RSET ct)
 408 {
 409     struct rset_bool_info *info = ct->buf;
 410
 411     assert (info->rfd_list == NULL);
 412     xfree (info->score_buf);
 413     xfree (info->score_idx);
 414     xfree (info->key_buf);
 415     xfree (info);
 416 }
 417
 418 static void r_rewind (RSFD rfd)
 419 {
 420     struct rset_bool_rfd *p = rfd;
 421
 422     logf (LOG_DEBUG, "rsbool_rewind");
 423     p->position = p->last_pos = 0;
 424 }
 425
 426 static int r_count (RSET ct)
 427 {
 428     struct rset_bool_info *info = ct->buf;
 429
 430     return info->key_no;
 431 }
 432
 433 static int r_hits (RSET ct, void *oi)
 434 {
 435     return -1;
 436 }
 437
 438 static int r_read (RSFD rfd, void *buf)
 439 {
 440     struct rset_bool_rfd *p = rfd;
 441     struct rset_bool_info *info = p->info;
 442
 443     if (p->position >= info->key_no)
 444         return 0;
 445     if (p->flag & RSETF_SORT_RANK)
 446         p->last_pos = info->score_idx[(p->position)++];
 447     else
 448         p->last_pos = (p->position)++;
 449     memcpy (buf, info->key_buf + info->key_size * p->last_pos,
 450             info->key_size);
 451     return 1;
 452 }
 453
 454 static int r_write (RSFD rfd, const void *buf)
 455 {
 456     logf (LOG_FATAL, "sbool set type is read-only");
 457     return -1;
 458 }
 459
 460 static int r_score (RSFD rfd, int *score)
 461 {
 462     struct rset_bool_rfd *p = rfd;
 463     struct rset_bool_info *info = p->info;
 464
 465     *score = info->score_buf[p->last_pos];
 466     return 1;
 467 }
 468