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