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