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