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