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