index/zsets.c

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