index/zsets.c

   1 /*
   2  * Copyright (C) 1994-1998, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: zsets.c,v $
   7  * Revision 1.20  1998-11-16 10:10:53  adam
   8  * Fixed problem with zebraPosSetCreate that occurred when positions were
   9  * less than 1.
  10  *
  11  * Revision 1.19  1998/09/22 10:48:22  adam
  12  * Minor changes in search API.
  13  *
  14  * Revision 1.18  1998/09/22 10:03:45  adam
  15  * Changed result sets to be persistent in the sense that they can
  16  * be re-searched if needed.
  17  * Fixed memory leak in rsm_or.
  18  *
  19  * Revision 1.17  1998/06/23 15:33:36  adam
  20  * Added feature to specify sort criteria in query (type 7 specifies
  21  * sort flags).
  22  *
  23  * Revision 1.16  1998/05/20 10:12:24  adam
  24  * Implemented automatic EXPLAIN database maintenance.
  25  * Modified Zebra to work with ASN.1 compiled version of YAZ.
  26  *
  27  * Revision 1.15  1998/03/05 08:45:14  adam
  28  * New result set model and modular ranking system. Moved towards
  29  * descent server API. System information stored as "SGML" records.
  30  *
  31  * Revision 1.14  1998/02/10 16:39:15  adam
  32  * Minor change.
  33  *
  34  * Revision 1.13  1998/02/10 12:03:06  adam
  35  * Implemented Sort.
  36  *
  37  * Revision 1.12  1997/09/25 14:57:36  adam
  38  * Windows NT port.
  39  *
  40  * Revision 1.11  1996/12/23 15:30:46  adam
  41  * Work on truncation.
  42  * Bug fix: result sets weren't deleted after server shut down.
  43  *
  44  * Revision 1.10  1995/10/30 15:08:08  adam
  45  * Bug fixes.
  46  *
  47  * Revision 1.9  1995/10/17  18:02:14  adam
  48  * New feature: databases. Implemented as prefix to words in dictionary.
  49  *
  50  * Revision 1.8  1995/10/10  13:59:25  adam
  51  * Function rset_open changed its wflag parameter to general flags.
  52  *
  53  * Revision 1.7  1995/10/06  14:38:01  adam
  54  * New result set method: r_score.
  55  * Local no (sysno) and score is transferred to retrieveCtrl.
  56  *
  57  * Revision 1.6  1995/09/28  09:19:49  adam
  58  * xfree/xmalloc used everywhere.
  59  * Extract/retrieve method seems to work for text records.
  60  *
  61  * Revision 1.5  1995/09/27  16:17:32  adam
  62  * More work on retrieve.
  63  *
  64  * Revision 1.4  1995/09/07  13:58:36  adam
  65  * New parameter: result-set file descriptor (RSFD) to support multiple
  66  * positions within the same result-set.
  67  * Boolean operators: and, or, not implemented.
  68  * Result-set references.
  69  *
  70  * Revision 1.3  1995/09/06  16:11:19  adam
  71  * Option: only one word key per file.
  72  *
  73  * Revision 1.2  1995/09/06  10:33:04  adam
  74  * More work on present. Some log messages removed.
  75  *
  76  * Revision 1.1  1995/09/05  15:28:40  adam
  77  * More work on search engine.
  78  *
  79  */
  80 #include <stdio.h>
  81 #include <assert.h>
  82 #ifdef WINDOWS
  83 #include <io.h>
  84 #else
  85 #include <unistd.h>
  86 #endif
  87
  88 #include "zserver.h"
  89 #include <rstemp.h>
  90
  91 #define SORT_IDX_ENTRYSIZE 64
  92 #define ZSET_SORT_MAX_LEVEL 3
  93
  94 struct zebra_set {
  95     char *name;
  96     RSET rset;
  97     NMEM nmem;
  98     int hits;
  99     int num_bases;
 100     char **basenames;
 101     Z_RPNQuery *rpn;
 102     struct zset_sort_info *sort_info;
 103     struct zebra_set *next;
 104 };
 105
 106 struct zset_sort_entry {
 107     int sysno;
 108     int score;
 109     char buf[ZSET_SORT_MAX_LEVEL][SORT_IDX_ENTRYSIZE];
 110 };
 111
 112 struct zset_sort_info {
 113     int max_entries;
 114     int num_entries;
 115     struct zset_sort_entry *all_entries;
 116     struct zset_sort_entry **entries;
 117 };
 118
 119 ZebraSet resultSetAddRPN (ZebraHandle zh, ODR input, ODR output,
 120                           Z_RPNQuery *rpn, int num_bases, char **basenames,
 121                           const char *setname)
 122 {
 123     ZebraSet zebraSet;
 124
 125     zlog_rpn (rpn);
 126
 127     zh->errCode = 0;
 128     zh->errString = NULL;
 129     zh->hits = 0;
 130
 131     zebraSet = resultSetAdd (zh, setname, 1);
 132     if (!zebraSet)
 133         return 0;
 134     zebraSet->rpn = 0;
 135     zebraSet->num_bases = num_bases;
 136     zebraSet->basenames = basenames;
 137     zebraSet->nmem = odr_extract_mem (input);
 138
 139     zebraSet->rset = rpn_search (zh, output->mem, rpn,
 140                                  zebraSet->num_bases,
 141                                  zebraSet->basenames, zebraSet->name,
 142                                  zebraSet);
 143     zh->hits = zebraSet->hits;
 144     if (zebraSet->rset)
 145         zebraSet->rpn = rpn;
 146     return zebraSet;
 147 }
 148
 149 ZebraSet resultSetAdd (ZebraHandle zh, const char *name, int ov)
 150 {
 151     ZebraSet s;
 152     int i;
 153
 154     for (s = zh->sets; s; s = s->next)
 155         if (!strcmp (s->name, name))
 156             break;
 157     if (s)
 158     {
 159         logf (LOG_DEBUG, "updating result set %s", name);
 160         if (!ov)
 161             return NULL;
 162         if (s->rset)
 163             rset_delete (s->rset);
 164         if (s->nmem)
 165             nmem_destroy (s->nmem);
 166     }
 167     else
 168     {
 169         logf (LOG_DEBUG, "adding result set %s", name);
 170         s = xmalloc (sizeof(*s));
 171         s->next = zh->sets;
 172         zh->sets = s;
 173         s->name = xmalloc (strlen(name)+1);
 174         strcpy (s->name, name);
 175
 176         s->sort_info = xmalloc (sizeof(*s->sort_info));
 177         s->sort_info->max_entries = 1000;
 178         s->sort_info->entries =
 179             xmalloc (sizeof(*s->sort_info->entries) *
 180                      s->sort_info->max_entries);
 181         s->sort_info->all_entries =
 182             xmalloc (sizeof(*s->sort_info->all_entries) *
 183                      s->sort_info->max_entries);
 184         for (i = 0; i < s->sort_info->max_entries; i++)
 185             s->sort_info->entries[i] = s->sort_info->all_entries + i;
 186     }
 187     s->rset = 0;
 188     s->nmem = 0;
 189     return s;
 190 }
 191
 192 ZebraSet resultSetGet (ZebraHandle zh, const char *name)
 193 {
 194     ZebraSet s;
 195
 196     for (s = zh->sets; s; s = s->next)
 197         if (!strcmp (s->name, name))
 198         {
 199             if (!s->rset && s->rpn)
 200             {
 201                 NMEM nmem = nmem_create ();
 202                 s->rset =
 203                     rpn_search (zh, nmem, s->rpn, s->num_bases,
 204                                 s->basenames, s->name, s);
 205                 nmem_destroy (nmem);
 206
 207             }
 208             return s;
 209         }
 210     return NULL;
 211 }
 212
 213
 214 void resultSetDestroy (ZebraHandle zh)
 215 {
 216     ZebraSet s, s1;
 217
 218     for (s = zh->sets; s; s = s1)
 219     {
 220         s1 = s->next;
 221
 222         xfree (s->sort_info->all_entries);
 223         xfree (s->sort_info->entries);
 224         xfree (s->sort_info);
 225
 226         if (s->nmem)
 227             nmem_destroy (s->nmem);
 228         rset_delete (s->rset);
 229         xfree (s->name);
 230         xfree (s);
 231     }
 232     zh->sets = NULL;
 233 }
 234
 235 ZebraPosSet zebraPosSetCreate (ZebraHandle zh, const char *name,
 236                                int num, int *positions)
 237 {
 238     ZebraSet sset;
 239     ZebraPosSet sr;
 240     RSET rset;
 241     int i;
 242     struct zset_sort_info *sort_info;
 243
 244     if (!(sset = resultSetGet (zh, name)))
 245         return NULL;
 246     if (!(rset = sset->rset))
 247         return NULL;
 248     sr = xmalloc (sizeof(*sr) * num);
 249     for (i = 0; i<num; i++)
 250     {
 251         sr[i].sysno = 0;
 252         sr[i].score = -1;
 253     }
 254     sort_info = sset->sort_info;
 255     if (sort_info)
 256     {
 257         int position;
 258
 259         for (i = 0; i<num; i++)
 260         {
 261             position = positions[i];
 262             if (position > 0 && position <= sort_info->num_entries)
 263             {
 264                 logf (LOG_DEBUG, "got pos=%d (sorted)", position);
 265                 sr[i].sysno = sort_info->entries[position-1]->sysno;
 266                 sr[i].score = sort_info->entries[position-1]->score;
 267             }
 268         }
 269     }
 270     /* did we really get all entries using sort ? */
 271     for (i = 0; i<num; i++)
 272     {
 273         if (!sr[i].sysno)
 274             break;
 275     }
 276     if (i < num) /* nope, get the rest, unsorted - sorry */
 277     {
 278         int position = 0;
 279         int num_i = 0;
 280         int psysno = 0;
 281         int term_index;
 282         RSFD rfd;
 283         struct it_key key;
 284
 285         if (sort_info)
 286             position = sort_info->num_entries;
 287         while (num_i < num && positions[num_i] < position)
 288             num_i++;
 289         rfd = rset_open (rset, RSETF_READ);
 290         while (num_i < num && rset_read (rset, rfd, &key, &term_index))
 291         {
 292             if (key.sysno != psysno)
 293             {
 294                 psysno = key.sysno;
 295                 if (sort_info)
 296                 {
 297                     /* determine we alreay have this in our set */
 298                     for (i = sort_info->num_entries; --i >= 0; )
 299                         if (psysno == sort_info->entries[i]->sysno)
 300                             break;
 301                     if (i >= 0)
 302                         continue;
 303                 }
 304                 position++;
 305                 assert (num_i < num);
 306                 if (position == positions[num_i])
 307                 {
 308                     sr[num_i].sysno = psysno;
 309                     logf (LOG_DEBUG, "got pos=%d (unsorted)", position);
 310                     sr[num_i].score = -1;
 311                     num_i++;
 312                 }
 313             }
 314         }
 315         rset_close (rset, rfd);
 316     }
 317     return sr;
 318 }
 319
 320 void zebraPosSetDestroy (ZebraHandle zh, ZebraPosSet records, int num)
 321 {
 322     xfree (records);
 323 }
 324
 325 struct sortKey {
 326     int relation;
 327     int attrUse;
 328 };
 329
 330 void resultSetInsertSort (ZebraHandle zh, ZebraSet sset,
 331                           struct sortKey *criteria, int num_criteria,
 332                           int sysno)
 333 {
 334     struct zset_sort_entry this_entry;
 335     struct zset_sort_entry *new_entry = NULL;
 336     struct zset_sort_info *sort_info = sset->sort_info;
 337     int i, j;
 338
 339     sortIdx_sysno (zh->sortIdx, sysno);
 340     for (i = 0; i<num_criteria; i++)
 341     {
 342         sortIdx_type (zh->sortIdx, criteria[i].attrUse);
 343         sortIdx_read (zh->sortIdx, this_entry.buf[i]);
 344     }
 345     i = sort_info->num_entries;
 346     while (--i >= 0)
 347     {
 348         int rel = 0;
 349         for (j = 0; j<num_criteria; j++)
 350         {
 351             rel = memcmp (this_entry.buf[j], sort_info->entries[i]->buf[j],
 352                           SORT_IDX_ENTRYSIZE);
 353             if (rel)
 354                 break;
 355         }
 356         if (!rel)
 357             break;
 358         if (criteria[j].relation == 'A')
 359         {
 360             if (rel > 0)
 361                 break;
 362         }
 363         else if (criteria[j].relation == 'D')
 364         {
 365             if (rel < 0)
 366                 break;
 367         }
 368     }
 369     j = sort_info->max_entries-1;
 370     if (i == j)
 371         return;
 372     ++i;
 373     new_entry = sort_info->entries[j];
 374     while (j != i)
 375     {
 376         sort_info->entries[j] = sort_info->entries[j-1];
 377         --j;
 378     }
 379     sort_info->entries[j] = new_entry;
 380     assert (new_entry);
 381     if (sort_info->num_entries != sort_info->max_entries)
 382         (sort_info->num_entries)++;
 383     for (i = 0; i<num_criteria; i++)
 384         memcpy (new_entry->buf[i], this_entry.buf[i], SORT_IDX_ENTRYSIZE);
 385     new_entry->sysno = sysno;
 386     new_entry->score = -1;
 387 }
 388
 389 void resultSetInsertRank (ZebraHandle zh, struct zset_sort_info *sort_info,
 390                           int sysno, int score, int relation)
 391 {
 392     struct zset_sort_entry *new_entry = NULL;
 393     int i, j;
 394
 395     i = sort_info->num_entries;
 396     while (--i >= 0)
 397     {
 398         int rel = 0;
 399
 400         rel = score - sort_info->entries[i]->score;
 401
 402         if (relation == 'D')
 403         {
 404             if (rel >= 0)
 405                 break;
 406         }
 407         else if (relation == 'A')
 408         {
 409             if (rel <= 0)
 410                 break;
 411         }
 412     }
 413     j = sort_info->max_entries-1;
 414     if (i == j)
 415         return;
 416     ++i;
 417     new_entry = sort_info->entries[j];
 418     while (j != i)
 419     {
 420         sort_info->entries[j] = sort_info->entries[j-1];
 421         --j;
 422     }
 423     sort_info->entries[j] = new_entry;
 424     assert (new_entry);
 425     if (sort_info->num_entries != sort_info->max_entries)
 426         (sort_info->num_entries)++;
 427     new_entry->sysno = sysno;
 428     new_entry->score = score;
 429 }
 430
 431 void resultSetSort (ZebraHandle zh, NMEM nmem,
 432                     int num_input_setnames, const char **input_setnames,
 433                     const char *output_setname,
 434                     Z_SortKeySpecList *sort_sequence, int *sort_status)
 435 {
 436     ZebraSet sset;
 437     RSET rset;
 438
 439     if (num_input_setnames == 0)
 440     {
 441         zh->errCode = 208;
 442         return ;
 443     }
 444     if (num_input_setnames > 1)
 445     {
 446         zh->errCode = 230;
 447         return;
 448     }
 449     logf (LOG_DEBUG, "result set sort input=%s output=%s",
 450           *input_setnames, output_setname);
 451     sset = resultSetGet (zh, input_setnames[0]);
 452     if (!sset)
 453     {
 454         zh->errCode = 30;
 455         zh->errString = nmem_strdup (nmem, input_setnames[0]);
 456         return;
 457     }
 458     if (!(rset = sset->rset))
 459     {
 460         zh->errCode = 30;
 461         zh->errString = nmem_strdup (nmem, input_setnames[0]);
 462         return;
 463     }
 464     if (strcmp (output_setname, input_setnames[0]))
 465     {
 466         rset = rset_dup (rset);
 467         sset = resultSetAdd (zh, output_setname, 1);
 468         sset->rset = rset;
 469     }
 470     resultSetSortSingle (zh, nmem, sset, rset, sort_sequence, sort_status);
 471 }
 472
 473 void resultSetSortSingle (ZebraHandle zh, NMEM nmem,
 474                           ZebraSet sset, RSET rset,
 475                           Z_SortKeySpecList *sort_sequence, int *sort_status)
 476 {
 477     int i, psysno = 0;
 478     struct it_key key;
 479     struct sortKey sort_criteria[3];
 480     int num_criteria;
 481     int term_index;
 482     RSFD rfd;
 483
 484     logf (LOG_DEBUG, "resultSetSortSingle start");
 485     sset->sort_info->num_entries = 0;
 486
 487     sset->hits = 0;
 488     num_criteria = sort_sequence->num_specs;
 489     if (num_criteria > 3)
 490         num_criteria = 3;
 491     for (i = 0; i < num_criteria; i++)
 492     {
 493         Z_SortKeySpec *sks = sort_sequence->specs[i];
 494         Z_SortKey *sk;
 495
 496         if (*sks->sortRelation == Z_SortRelation_ascending)
 497             sort_criteria[i].relation = 'A';
 498         else if (*sks->sortRelation == Z_SortRelation_descending)
 499             sort_criteria[i].relation = 'D';
 500         else
 501         {
 502             zh->errCode = 214;
 503             return;
 504         }
 505         if (sks->sortElement->which == Z_SortElement_databaseSpecific)
 506         {
 507             zh->errCode = 210;
 508             return;
 509         }
 510         else if (sks->sortElement->which != Z_SortElement_generic)
 511         {
 512             zh->errCode = 237;
 513             return;
 514         }
 515         sk = sks->sortElement->u.generic;
 516         switch (sk->which)
 517         {
 518         case Z_SortKey_sortField:
 519             logf (LOG_DEBUG, "Sort: key %d is of type sortField", i+1);
 520             zh->errCode = 207;
 521             return;
 522         case Z_SortKey_elementSpec:
 523             logf (LOG_DEBUG, "Sort: key %d is of type elementSpec", i+1);
 524             zh->errCode = 207;
 525             return;
 526         case Z_SortKey_sortAttributes:
 527             logf (LOG_DEBUG, "Sort: key %d is of type sortAttributes", i+1);
 528             sort_criteria[i].attrUse =
 529                 zebra_maps_sort (zh->zebra_maps, sk->u.sortAttributes);
 530             logf (LOG_DEBUG, "use value = %d", sort_criteria[i].attrUse);
 531             if (sort_criteria[i].attrUse == -1)
 532             {
 533                 zh->errCode = 116;
 534                 return;
 535             }
 536             if (sortIdx_type (zh->sortIdx, sort_criteria[i].attrUse))
 537             {
 538                 zh->errCode = 207;
 539                 return;
 540             }
 541             break;
 542         }
 543     }
 544     rfd = rset_open (rset, RSETF_READ);
 545     while (rset_read (rset, rfd, &key, &term_index))
 546     {
 547         if (key.sysno != psysno)
 548         {
 549             (sset->hits)++;
 550             psysno = key.sysno;
 551             resultSetInsertSort (zh, sset,
 552                                  sort_criteria, num_criteria, psysno);
 553         }
 554     }
 555     rset_close (rset, rfd);
 556
 557     zh->errCode = 0;
 558     *sort_status = Z_SortStatus_success;
 559     logf (LOG_DEBUG, "resultSetSortSingle end");
 560 }
 561
 562 RSET resultSetRef (ZebraHandle zh, Z_ResultSetId *resultSetId)
 563 {
 564     ZebraSet s;
 565
 566     if ((s = resultSetGet (zh, resultSetId)))
 567         return s->rset;
 568     return NULL;
 569 }
 570
 571 void resultSetRank (ZebraHandle zh, ZebraSet zebraSet, RSET rset)
 572 {
 573     int kno = 0;
 574     struct it_key key;
 575     RSFD rfd;
 576     int term_index, i;
 577     ZebraRankClass rank_class;
 578     struct rank_control *rc;
 579     struct zset_sort_info *sort_info;
 580
 581     sort_info = zebraSet->sort_info;
 582     sort_info->num_entries = 0;
 583     zebraSet->hits = 0;
 584     rfd = rset_open (rset, RSETF_READ);
 585
 586     logf (LOG_DEBUG, "resultSetRank");
 587     for (i = 0; i < rset->no_rset_terms; i++)
 588         logf (LOG_DEBUG, "term=\"%s\" cnt=%d type=%s",
 589               rset->rset_terms[i]->name,
 590               rset->rset_terms[i]->nn,
 591               rset->rset_terms[i]->flags);
 592
 593     rank_class = zebraRankLookup (zh, "rank-1");
 594     rc = rank_class->control;
 595
 596     if (rset_read (rset, rfd, &key, &term_index))
 597     {
 598         int psysno = key.sysno;
 599         int score;
 600         void *handle =
 601             (*rc->begin) (zh, rank_class->class_handle, rset);
 602         (zebraSet->hits)++;
 603         do
 604         {
 605             kno++;
 606             if (key.sysno != psysno)
 607             {
 608                 score = (*rc->calc) (handle, psysno);
 609
 610                 resultSetInsertRank (zh, sort_info, psysno, score, 'A');
 611                 (zebraSet->hits)++;
 612                 psysno = key.sysno;
 613             }
 614             (*rc->add) (handle, key.seqno, term_index);
 615         }
 616         while (rset_read (rset, rfd, &key, &term_index));
 617         score = (*rc->calc) (handle, psysno);
 618         resultSetInsertRank (zh, sort_info, psysno, score, 'A');
 619         (*rc->end) (zh, handle);
 620     }
 621     rset_close (rset, rfd);
 622     logf (LOG_DEBUG, "%d keys, %d distinct sysnos", kno, zebraSet->hits);
 623 }
 624
 625 ZebraRankClass zebraRankLookup (ZebraHandle zh, const char *name)
 626 {
 627     ZebraRankClass p = zh->rank_classes;
 628     while (p && strcmp (p->control->name, name))
 629         p = p->next;
 630     if (p && !p->init_flag)
 631     {
 632         if (p->control->create)
 633             p->class_handle = (*p->control->create)(zh);
 634         p->init_flag = 1;
 635     }
 636     return p;
 637 }
 638
 639 void zebraRankInstall (ZebraHandle zh, struct rank_control *ctrl)
 640 {
 641     ZebraRankClass p = xmalloc (sizeof(*p));
 642     p->control = xmalloc (sizeof(*p->control));
 643     memcpy (p->control, ctrl, sizeof(*p->control));
 644     p->control->name = xstrdup (ctrl->name);
 645     p->init_flag = 0;
 646     p->next = zh->rank_classes;
 647     zh->rank_classes = p;
 648 }
 649
 650 void zebraRankDestroy (ZebraHandle zh)
 651 {
 652     ZebraRankClass p = zh->rank_classes;
 653     while (p)
 654     {
 655         ZebraRankClass p_next = p->next;
 656         if (p->init_flag && p->control->destroy)
 657             (*p->control->destroy)(zh, p->class_handle);
 658         xfree (p->control->name);
 659         xfree (p->control);
 660         xfree (p);
 661         p = p_next;
 662     }
 663     zh->rank_classes = NULL;
 664 }