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