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