index/zrpn.c

   1 /*
   2  * Copyright (C) 1994-1995, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: zrpn.c,v $
   7  * Revision 1.12  1995-09-15 14:45:21  adam
   8  * Retrieve control.
   9  * Work on truncation.
  10  *
  11  * Revision 1.11  1995/09/14  11:53:27  adam
  12  * First work on regular expressions/truncations.
  13  *
  14  * Revision 1.10  1995/09/11  15:23:26  adam
  15  * More work on relevance search.
  16  *
  17  * Revision 1.9  1995/09/11  13:09:35  adam
  18  * More work on relevance feedback.
  19  *
  20  * Revision 1.8  1995/09/08  14:52:27  adam
  21  * Minor changes. Dictionary is lower case now.
  22  *
  23  * Revision 1.7  1995/09/07  13:58:36  adam
  24  * New parameter: result-set file descriptor (RSFD) to support multiple
  25  * positions within the same result-set.
  26  * Boolean operators: and, or, not implemented.
  27  * Result-set references.
  28  *
  29  * Revision 1.6  1995/09/06  16:11:18  adam
  30  * Option: only one word key per file.
  31  *
  32  * Revision 1.5  1995/09/06  10:33:04  adam
  33  * More work on present. Some log messages removed.
  34  *
  35  * Revision 1.4  1995/09/05  15:28:40  adam
  36  * More work on search engine.
  37  *
  38  * Revision 1.3  1995/09/04  15:20:22  adam
  39  * Minor changes.
  40  *
  41  * Revision 1.2  1995/09/04  12:33:43  adam
  42  * Various cleanup. YAZ util used instead.
  43  *
  44  * Revision 1.1  1995/09/04  09:10:40  adam
  45  * More work on index add/del/update.
  46  * Merge sort implemented.
  47  * Initial work on z39 server.
  48  *
  49  */
  50 #include <stdio.h>
  51 #include <assert.h>
  52 #include <unistd.h>
  53
  54 #include "zserver.h"
  55
  56 #include <rsisam.h>
  57 #include <rstemp.h>
  58 #include <rsnull.h>
  59 #include <rsbool.h>
  60 #include <rsrel.h>
  61
  62 /*
  63  * attr_print: log attributes
  64  */
  65 static void attr_print (Z_AttributesPlusTerm *t)
  66 {
  67     int of, i;
  68     for (of = 0; of < t->num_attributes; of++)
  69     {
  70         Z_AttributeElement *element;
  71         element = t->attributeList[of];
  72
  73         switch (element->which)
  74         {
  75         case Z_AttributeValue_numeric:
  76             logf (LOG_DEBUG, "attributeType=%d value=%d",
  77                   *element->attributeType,
  78                   *element->value.numeric);
  79             break;
  80         case Z_AttributeValue_complex:
  81             logf (LOG_DEBUG, "attributeType=%d complex",
  82                   *element->attributeType);
  83             for (i = 0; i<element->value.complex->num_list; i++)
  84             {
  85                 if (element->value.complex->list[i]->which ==
  86                     Z_StringOrNumeric_string)
  87                     logf (LOG_DEBUG, "   string: '%s'",
  88                           element->value.complex->list[i]->u.string);
  89                 else if (element->value.complex->list[i]->which ==
  90                          Z_StringOrNumeric_numeric)
  91                     logf (LOG_DEBUG, "   numeric: '%d'",
  92                           *element->value.complex->list[i]->u.numeric);
  93             }
  94             break;
  95         default:
  96             assert (0);
  97         }
  98     }
  99 }
 100
 101 typedef struct {
 102     int type;
 103     int major;
 104     int minor;
 105     Z_AttributesPlusTerm *zapt;
 106 } AttrType;
 107
 108 static int attr_find (AttrType *src)
 109 {
 110     while (src->major < src->zapt->num_attributes)
 111     {
 112         Z_AttributeElement *element;
 113         element = src->zapt->attributeList[src->major];
 114
 115         if (src->type == *element->attributeType)
 116         {
 117             switch (element->which)
 118             {
 119             case Z_AttributeValue_numeric:
 120                 ++(src->major);
 121                 return *element->value.numeric;
 122                 break;
 123             case Z_AttributeValue_complex:
 124                 if (src->minor >= element->value.complex->num_list ||
 125                     element->value.complex->list[src->minor]->which !=
 126                     Z_StringOrNumeric_numeric)
 127                     break;
 128                 ++(src->minor);
 129                 return *element->value.complex->list[src->minor-1]->u.numeric;
 130             default:
 131                 assert (0);
 132             }
 133         }
 134         ++(src->major);
 135     }
 136     return -1;
 137 }
 138
 139 static void attr_init (AttrType *src, Z_AttributesPlusTerm *zapt,
 140                        int type)
 141 {
 142     src->zapt = zapt;
 143     src->type = type;
 144     src->major = 0;
 145     src->minor = 0;
 146 }
 147
 148 struct trunc_info {
 149     int  *indx;
 150     char **heap;
 151     int  heapnum;
 152     int  (*cmp)(const void *p1, const void *p2);
 153     int  keysize;
 154     char *swapbuf;
 155     char *tmpbuf;
 156     char *buf;
 157 };
 158
 159 static void heap_swap (struct trunc_info *ti, int i1, int i2)
 160 {
 161     int swap;
 162
 163     memcpy (ti->swapbuf, ti->heap[i1], ti->keysize);
 164     memcpy (ti->heap[i1], ti->heap[i2], ti->keysize);
 165     memcpy (ti->heap[i2], ti->swapbuf, ti->keysize);
 166
 167     swap = ti->indx[i1];
 168     ti->indx[i1] = ti->indx[i2];
 169     ti->indx[i2] = swap;
 170 }
 171
 172 static void heap_delete (struct trunc_info *ti)
 173 {
 174     int cur = 1, child = 2;
 175
 176     assert (ti->heapnum > 0);
 177     memcpy (ti->heap[1], ti->heap[ti->heapnum], ti->keysize);
 178     ti->indx[1] = ti->indx[ti->heapnum--];
 179     while (child <= ti->heapnum) {
 180         if (child < ti->heapnum &&
 181             (*ti->cmp)(ti->heap[child], ti->heap[1+child]) > 0)
 182             child++;
 183         if ((*ti->cmp)(ti->heap[cur], ti->heap[child]) > 0)
 184         {
 185             heap_swap (ti, cur, child);
 186             cur = child;
 187             child = 2*cur;
 188         }
 189         else
 190             break;
 191     }
 192 }
 193
 194 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
 195 {
 196     int cur, parent;
 197
 198     cur = ++(ti->heapnum);
 199     memcpy (ti->heap[cur], buf, ti->keysize);
 200     ti->indx[cur] = indx;
 201     parent = cur/2;
 202     while (parent && (*ti->cmp)(ti->heap[parent], ti->heap[cur]) > 0)
 203     {
 204         heap_swap (ti, cur, parent);
 205         cur = parent;
 206         parent = cur/2;
 207     }
 208 }
 209
 210 static
 211 struct trunc_info *heap_init (int size, int key_size,
 212                               int (*cmp)(const void *p1, const void *p2))
 213 {
 214     struct trunc_info *ti = xmalloc (sizeof(*ti));
 215     int i;
 216
 217     ++size;
 218     ti->heapnum = 0;
 219     ti->keysize = key_size;
 220     ti->cmp = cmp;
 221     ti->indx = xmalloc (size * sizeof(*ti->indx));
 222     ti->heap = xmalloc (size * sizeof(*ti->heap));
 223     ti->swapbuf = xmalloc (ti->keysize);
 224     ti->tmpbuf = xmalloc (ti->keysize);
 225     ti->buf = xmalloc (size * ti->keysize);
 226     for (i = size; --i >= 0; )
 227         ti->heap[i] = ti->buf + ti->keysize * i;
 228     return ti;
 229 }
 230
 231 static void heap_close (struct trunc_info *ti)
 232 {
 233     xfree (ti->indx);
 234     xfree (ti->heap);
 235     xfree (ti->swapbuf);
 236     xfree (ti->tmpbuf);
 237     xfree (ti);
 238 }
 239
 240 static RSET rset_trunc (ISAM isam, ISAM_P *isam_p, int from, int to,
 241                         int merge_chunk)
 242 {
 243     logf (LOG_DEBUG, "rset_trunc, range=%d-%d", from, to-1);
 244     if (from - to > merge_chunk)
 245     {
 246         return NULL;
 247     }
 248     else
 249     {
 250         ISPT *ispt;
 251         int i;
 252         struct trunc_info *ti;
 253         RSET result;
 254         RSFD rsfd;
 255         rset_temp_parms parms;
 256
 257         parms.key_size = sizeof (struct it_key);
 258         result = rset_create (rset_kind_temp, &parms);
 259         rsfd = rset_open (result, 1);
 260
 261         ti = heap_init (to-from, sizeof(struct it_key),
 262                         key_compare);
 263         for (i = to-from; --i >= 0; )
 264         {
 265             ispt[i] = is_position (isam, isam_p[from+i]);
 266             if (is_readkey (ispt[i], ti->tmpbuf))
 267                 heap_insert (ti, ti->tmpbuf, i);
 268         }
 269         while (ti->heapnum)
 270         {
 271             int n = ti->indx[1];
 272
 273             rset_write (result, rsfd, ti->heap[1]);
 274             heap_delete (ti);
 275             if (is_readkey (ispt[n], ti->tmpbuf))
 276                 heap_insert (ti, ti->tmpbuf, n);
 277         }
 278         for (i = to-from; --i >= 0; )
 279             is_pt_free (ispt[i]);
 280         rset_close (result, rsfd);
 281         heap_close (ti);
 282         return result;
 283     }
 284 }
 285
 286 static ISAM_P *isam_p_buf = NULL;
 287 static int isam_p_size = 0;
 288 static int isam_p_indx;
 289
 290 static void add_isam_p (const char *info)
 291 {
 292     if (isam_p_indx == isam_p_size)
 293     {
 294         ISAM_P *new_isam_p_buf;
 295
 296         isam_p_size = 2*isam_p_size + 100;
 297         new_isam_p_buf = xmalloc (sizeof(*new_isam_p_buf) *
 298                                   isam_p_size);
 299         if (isam_p_buf)
 300         {
 301             memcpy (new_isam_p_buf, isam_p_buf,
 302                     isam_p_indx * sizeof(*isam_p_buf));
 303             xfree (isam_p_buf);
 304         }
 305         isam_p_buf = new_isam_p_buf;
 306     }
 307     assert (*info == sizeof(*isam_p_buf));
 308     memcpy (isam_p_buf + isam_p_indx, info+1, sizeof(*isam_p_buf));
 309     isam_p_indx++;
 310 }
 311
 312 static int grep_handle (Dict_char *name, const char *info)
 313 {
 314     logf (LOG_DEBUG, "dict name: %s", name);
 315     add_isam_p (info);
 316     return 0;
 317 }
 318
 319 static int trunc_term (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
 320                        const char *term_sub, ISAM_P **isam_ps)
 321 {
 322     char term_dict[2*IT_MAX_WORD+2];
 323     int i, j;
 324     const char *info;
 325     AttrType truncation;
 326     int truncation_value;
 327
 328     attr_init (&truncation, zapt, 5);
 329     truncation_value = attr_find (&truncation);
 330     logf (LOG_DEBUG, "truncation value %d", truncation_value);
 331     switch (truncation_value)
 332     {
 333     case -1:         /* not specified */
 334     case 100:        /* do not truncate */
 335         strcpy (term_dict, term_sub);
 336         logf (LOG_DEBUG, "dict_lookup: %s", term_dict);
 337         if ((info = dict_lookup (zi->wordDict, term_dict)))
 338             add_isam_p (info);
 339         break;
 340     case 1:          /* right truncation */
 341         strcpy (term_dict, term_sub);
 342         strcat (term_dict, ".*");
 343         dict_lookup_grep (zi->wordDict, term_dict, 0, grep_handle);
 344         break;
 345     case 2:          /* left truncation */
 346     case 3:          /* left&right truncation */
 347         zi->errCode = 120;
 348         return -1;
 349     case 101:        /* process # in term */
 350         for (j = 0, i = 0; term_sub[i] && i < 3; i++)
 351             term_dict[j++] = term_sub[i];
 352         for (; term_sub[i]; i++)
 353             if (term_sub[i] == '#')
 354             {
 355                 term_dict[j++] = '.';
 356                 term_dict[j++] = '*';
 357             }
 358             else
 359                 term_dict[j++] = term_sub[i];
 360         term_dict[j] = '\0';
 361         dict_lookup_grep (zi->wordDict, term_dict, 0, grep_handle);
 362         break;
 363     case 102:        /* regular expression */
 364         strcpy (term_dict, term_sub);
 365         dict_lookup_grep (zi->wordDict, term_dict, 0, grep_handle);
 366         break;
 367     }
 368     *isam_ps = isam_p_buf;
 369     logf (LOG_DEBUG, "%d positions", isam_p_indx);
 370     return 0;
 371 }
 372
 373 static RSET rpn_search_APT_relevance (ZServerInfo *zi,
 374                                       Z_AttributesPlusTerm *zapt)
 375 {
 376     rset_relevance_parms parms;
 377     char termz[IT_MAX_WORD+1];
 378     char term_sub[IT_MAX_WORD+1];
 379     char *p0 = termz, *p1 = NULL;
 380     Z_Term *term = zapt->term;
 381     size_t sizez, i;
 382
 383     parms.key_size = sizeof(struct it_key);
 384     parms.max_rec = 100;
 385     parms.cmp = key_compare;
 386     parms.is = zi->wordIsam;
 387
 388     if (term->which != Z_Term_general)
 389     {
 390         zi->errCode = 124;
 391         return NULL;
 392     }
 393     sizez = term->u.general->len;
 394     if (sizez > IT_MAX_WORD)
 395         sizez = IT_MAX_WORD;
 396     for (i = 0; i<sizez; i++)
 397         termz[i] = index_char_cvt (term->u.general->buf[i]);
 398     termz[i] = '\0';
 399
 400     isam_p_indx = 0;  /* global, set by trunc_term - see below */
 401     while (1)
 402     {
 403         if ((p1 = strchr (p0, ' ')))
 404         {
 405             memcpy (term_sub, p0, p1-p0);
 406             term_sub[p1-p0] = '\0';
 407         }
 408         else
 409             strcpy (term_sub, p0);
 410         if (trunc_term (zi, zapt, term_sub, &parms.isam_positions))
 411             return NULL;
 412         if (!p1)
 413             break;
 414         p0 = p1+1;
 415     }
 416     parms.no_isam_positions = isam_p_indx;
 417     if (isam_p_indx > 0)
 418         return rset_create (rset_kind_relevance, &parms);
 419     else
 420         return rset_create (rset_kind_null, NULL);
 421 }
 422
 423 static RSET rpn_search_APT_word (ZServerInfo *zi,
 424                                  Z_AttributesPlusTerm *zapt)
 425 {
 426     ISAM_P *isam_positions;
 427     rset_isam_parms parms;
 428
 429     char termz[IT_MAX_WORD+1];
 430     Z_Term *term = zapt->term;
 431     size_t sizez, i;
 432
 433     if (term->which != Z_Term_general)
 434     {
 435         zi->errCode = 124;
 436         return NULL;
 437     }
 438     sizez = term->u.general->len;
 439     if (sizez > IT_MAX_WORD)
 440         sizez = IT_MAX_WORD;
 441     for (i = 0; i<sizez; i++)
 442         termz[i] = index_char_cvt (term->u.general->buf[i]);
 443     termz[i] = '\0';
 444
 445     isam_p_indx = 0;  /* global, set by trunc_term - see below */
 446     if (trunc_term (zi, zapt, termz, &isam_positions))
 447         return NULL;
 448     if (isam_p_indx < 1)
 449         return rset_create (rset_kind_null, NULL);
 450     else if (isam_p_indx == 1)
 451     {
 452         parms.is = zi->wordIsam;
 453         parms.pos = *isam_positions;
 454         return rset_create (rset_kind_isam, &parms);
 455     }
 456     else
 457         return rset_trunc (zi->wordIsam, isam_positions, 0, isam_p_indx, 200);
 458 }
 459
 460 static RSET rpn_search_APT_phrase (ZServerInfo *zi,
 461                                    Z_AttributesPlusTerm *zapt)
 462 {
 463     ISAM_P *isam_positions;
 464     rset_isam_parms parms;
 465
 466     char termz[IT_MAX_WORD+1];
 467     Z_Term *term = zapt->term;
 468     size_t sizez, i;
 469
 470     if (term->which != Z_Term_general)
 471     {
 472         zi->errCode = 124;
 473         return NULL;
 474     }
 475     sizez = term->u.general->len;
 476     if (sizez > IT_MAX_WORD)
 477         sizez = IT_MAX_WORD;
 478     for (i = 0; i<sizez; i++)
 479         termz[i] = index_char_cvt (term->u.general->buf[i]);
 480     termz[i] = '\0';
 481
 482     isam_p_indx = 0;  /* global, set by trunc_term - see below */
 483     if (trunc_term (zi, zapt, termz, &isam_positions))
 484         return NULL;
 485     if (isam_p_indx != 1)
 486         return rset_create (rset_kind_null, NULL);
 487     parms.is = zi->wordIsam;
 488     parms.pos = *isam_positions;
 489     return rset_create (rset_kind_isam, &parms);
 490 }
 491
 492 static RSET rpn_search_APT (ZServerInfo *zi, Z_AttributesPlusTerm *zapt)
 493 {
 494     AttrType relation;
 495     AttrType structure;
 496     int relation_value, structure_value;
 497
 498     attr_init (&relation, zapt, 2);
 499     attr_init (&structure, zapt, 4);
 500
 501     relation_value = attr_find (&relation);
 502     structure_value = attr_find (&structure);
 503     switch (structure_value)
 504     {
 505     case -1:
 506         if (relation_value == 102) /* relevance relation */
 507             return rpn_search_APT_relevance (zi, zapt);
 508         return rpn_search_APT_word (zi, zapt);
 509     case 1: /* phrase */
 510         if (relation_value == 102) /* relevance relation */
 511             return rpn_search_APT_relevance (zi, zapt);
 512         return rpn_search_APT_phrase (zi, zapt);
 513         break;
 514     case 2: /* word */
 515         if (relation_value == 102) /* relevance relation */
 516             return rpn_search_APT_relevance (zi, zapt);
 517         return rpn_search_APT_word (zi, zapt);
 518     case 3: /* key */
 519         break;
 520     case 4: /* year */
 521         break;
 522     case 5: /* date - normalized */
 523         break;
 524     case 6: /* word list */
 525         return rpn_search_APT_relevance (zi, zapt);
 526     case 100: /* date - un-normalized */
 527         break;
 528     case 101: /* name - normalized */
 529         break;
 530     case 102: /* date - un-normalized */
 531         break;
 532     case 103: /* structure */
 533         break;
 534     case 104: /* urx */
 535         break;
 536     case 105: /* free-form-text */
 537         return rpn_search_APT_relevance (zi, zapt);
 538     case 106: /* document-text */
 539         return rpn_search_APT_relevance (zi, zapt);
 540     case 107: /* local-number */
 541         break;
 542     case 108: /* string */
 543         return rpn_search_APT_word (zi, zapt);
 544     case 109: /* numeric string */
 545         break;
 546     }
 547     zi->errCode = 118;
 548     return NULL;
 549 }
 550
 551 static RSET rpn_search_ref (ZServerInfo *zi, Z_ResultSetId *resultSetId)
 552 {
 553     ZServerSet *s;
 554
 555     if (!(s = resultSetGet (zi, resultSetId)))
 556         return rset_create (rset_kind_null, NULL);
 557     return s->rset;
 558 }
 559
 560 static RSET rpn_search_structure (ZServerInfo *zi, Z_RPNStructure *zs)
 561 {
 562     RSET r = NULL;
 563     if (zs->which == Z_RPNStructure_complex)
 564     {
 565         rset_bool_parms bool_parms;
 566
 567         bool_parms.rset_l = rpn_search_structure (zi, zs->u.complex->s1);
 568         if (bool_parms.rset_l == NULL)
 569             return NULL;
 570         bool_parms.rset_r = rpn_search_structure (zi, zs->u.complex->s2);
 571         if (bool_parms.rset_r == NULL)
 572         {
 573             rset_delete (bool_parms.rset_l);
 574             return NULL;
 575         }
 576         bool_parms.key_size = sizeof(struct it_key);
 577         bool_parms.cmp = key_compare;
 578
 579         switch (zs->u.complex->operator->which)
 580         {
 581         case Z_Operator_and:
 582             r = rset_create (rset_kind_and, &bool_parms);
 583             break;
 584         case Z_Operator_or:
 585             r = rset_create (rset_kind_or, &bool_parms);
 586             break;
 587         case Z_Operator_and_not:
 588             r = rset_create (rset_kind_not, &bool_parms);
 589             break;
 590         default:
 591             assert (0);
 592         }
 593     }
 594     else if (zs->which == Z_RPNStructure_simple)
 595     {
 596         if (zs->u.simple->which == Z_Operand_APT)
 597         {
 598             logf (LOG_DEBUG, "rpn_search_APT");
 599             r = rpn_search_APT (zi, zs->u.simple->u.attributesPlusTerm);
 600         }
 601         else if (zs->u.simple->which == Z_Operand_resultSetId)
 602         {
 603             logf (LOG_DEBUG, "rpn_search_ref");
 604             r = rpn_search_ref (zi, zs->u.simple->u.resultSetId);
 605         }
 606         else
 607         {
 608             assert (0);
 609         }
 610     }
 611     else
 612     {
 613         assert (0);
 614     }
 615     return r;
 616 }
 617
 618 static void count_set (RSET r, int *count)
 619 {
 620     int psysno = 0;
 621     struct it_key key;
 622     RSFD rfd;
 623
 624     logf (LOG_DEBUG, "rpn_save_set");
 625     *count = 0;
 626     rfd = rset_open (r, 0);
 627     while (rset_read (r, rfd, &key))
 628     {
 629         if (key.sysno != psysno)
 630         {
 631             psysno = key.sysno;
 632             (*count)++;
 633         }
 634     }
 635     rset_close (r, rfd);
 636     logf (LOG_DEBUG, "%d distinct sysnos", *count);
 637 }
 638
 639 int rpn_search (ZServerInfo *zi,
 640                 Z_RPNQuery *rpn, int num_bases, char **basenames,
 641                 const char *setname, int *hits)
 642 {
 643     RSET rset;
 644
 645     zi->errCode = 0;
 646     zi->errString = NULL;
 647     rset = rpn_search_structure (zi, rpn->RPNStructure);
 648     if (!rset)
 649         return zi->errCode;
 650     count_set (rset, hits);
 651     resultSetAdd (zi, setname, 1, rset);
 652     return zi->errCode;
 653 }
 654