index/zsets.c

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