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.32  1995-10-27 14:00:11  adam
   8  * Implemented detection of database availability.
   9  *
  10  * Revision 1.31  1995/10/17  18:02:10  adam
  11  * New feature: databases. Implemented as prefix to words in dictionary.
  12  *
  13  * Revision 1.30  1995/10/16  09:32:38  adam
  14  * More work on relational op.
  15  *
  16  * Revision 1.29  1995/10/13  16:01:49  adam
  17  * Work on relations.
  18  *
  19  * Revision 1.28  1995/10/13  12:26:43  adam
  20  * Optimization of truncation.
  21  *
  22  * Revision 1.27  1995/10/12  17:07:22  adam
  23  * Truncation works.
  24  *
  25  * Revision 1.26  1995/10/12  12:40:54  adam
  26  * Bug fixes in rpn_prox.
  27  *
  28  * Revision 1.25  1995/10/10  13:59:24  adam
  29  * Function rset_open changed its wflag parameter to general flags.
  30  *
  31  * Revision 1.24  1995/10/09  16:18:37  adam
  32  * Function dict_lookup_grep got extra client data parameter.
  33  *
  34  * Revision 1.23  1995/10/06  16:33:37  adam
  35  * Use attribute mappings.
  36  *
  37  * Revision 1.22  1995/10/06  15:07:39  adam
  38  * Structure 'local-number' handled.
  39  *
  40  * Revision 1.21  1995/10/06  13:52:06  adam
  41  * Bug fixes. Handler may abort further scanning.
  42  *
  43  * Revision 1.20  1995/10/06  11:06:33  adam
  44  * Scan entries include 'occurrences' now.
  45  *
  46  * Revision 1.19  1995/10/06  10:43:56  adam
  47  * Scan added. 'occurrences' in scan entries not set yet.
  48  *
  49  * Revision 1.18  1995/10/04  16:57:20  adam
  50  * Key input and merge sort in one pass.
  51  *
  52  * Revision 1.17  1995/10/04  12:55:17  adam
  53  * Bug fix in ranked search. Use=Any keys inserted.
  54  *
  55  * Revision 1.16  1995/10/02  16:24:40  adam
  56  * Use attribute actually used in search requests.
  57  *
  58  * Revision 1.15  1995/10/02  15:18:52  adam
  59  * New member in recRetrieveCtrl: diagnostic.
  60  *
  61  * Revision 1.14  1995/09/28  12:10:32  adam
  62  * Bug fixes. Field prefix used in queries.
  63  *
  64  * Revision 1.13  1995/09/18  14:17:50  adam
  65  * Minor changes.
  66  *
  67  * Revision 1.12  1995/09/15  14:45:21  adam
  68  * Retrieve control.
  69  * Work on truncation.
  70  *
  71  * Revision 1.11  1995/09/14  11:53:27  adam
  72  * First work on regular expressions/truncations.
  73  *
  74  * Revision 1.10  1995/09/11  15:23:26  adam
  75  * More work on relevance search.
  76  *
  77  * Revision 1.9  1995/09/11  13:09:35  adam
  78  * More work on relevance feedback.
  79  *
  80  * Revision 1.8  1995/09/08  14:52:27  adam
  81  * Minor changes. Dictionary is lower case now.
  82  *
  83  * Revision 1.7  1995/09/07  13:58:36  adam
  84  * New parameter: result-set file descriptor (RSFD) to support multiple
  85  * positions within the same result-set.
  86  * Boolean operators: and, or, not implemented.
  87  * Result-set references.
  88  *
  89  * Revision 1.6  1995/09/06  16:11:18  adam
  90  * Option: only one word key per file.
  91  *
  92  * Revision 1.5  1995/09/06  10:33:04  adam
  93  * More work on present. Some log messages removed.
  94  *
  95  * Revision 1.4  1995/09/05  15:28:40  adam
  96  * More work on search engine.
  97  *
  98  * Revision 1.3  1995/09/04  15:20:22  adam
  99  * Minor changes.
 100  *
 101  * Revision 1.2  1995/09/04  12:33:43  adam
 102  * Various cleanup. YAZ util used instead.
 103  *
 104  * Revision 1.1  1995/09/04  09:10:40  adam
 105  * More work on index add/del/update.
 106  * Merge sort implemented.
 107  * Initial work on z39 server.
 108  *
 109  */
 110 #include <stdio.h>
 111 #include <assert.h>
 112 #include <unistd.h>
 113
 114 #include "zserver.h"
 115 #include <attribute.h>
 116
 117 #include <rsisam.h>
 118 #include <rstemp.h>
 119 #include <rsnull.h>
 120 #include <rsbool.h>
 121 #include <rsrel.h>
 122
 123 int index_word_prefix_map (char *string, oid_value attrSet, int attrUse,
 124                            char *basename)
 125 {
 126     attent *attp;
 127
 128     logf (LOG_DEBUG, "oid_value attrSet = %d, attrUse = %d", attrSet, attrUse);
 129     attp = att_getentbyatt (attrSet, attrUse);
 130     if (!attp)
 131         return -1;
 132     logf (LOG_DEBUG, "ord=%d", attp->attset_ordinal);
 133     return index_word_prefix (string, attp->attset_ordinal,
 134                               attp->local_attribute, basename);
 135 }
 136
 137 /*
 138  * attr_print: log attributes
 139  */
 140 static void attr_print (Z_AttributesPlusTerm *t)
 141 {
 142     int of, i;
 143     for (of = 0; of < t->num_attributes; of++)
 144     {
 145         Z_AttributeElement *element;
 146         element = t->attributeList[of];
 147
 148         switch (element->which)
 149         {
 150         case Z_AttributeValue_numeric:
 151             logf (LOG_DEBUG, "attributeType=%d value=%d",
 152                   *element->attributeType,
 153                   *element->value.numeric);
 154             break;
 155         case Z_AttributeValue_complex:
 156             logf (LOG_DEBUG, "attributeType=%d complex",
 157                   *element->attributeType);
 158             for (i = 0; i<element->value.complex->num_list; i++)
 159             {
 160                 if (element->value.complex->list[i]->which ==
 161                     Z_StringOrNumeric_string)
 162                     logf (LOG_DEBUG, "   string: '%s'",
 163                           element->value.complex->list[i]->u.string);
 164                 else if (element->value.complex->list[i]->which ==
 165                          Z_StringOrNumeric_numeric)
 166                     logf (LOG_DEBUG, "   numeric: '%d'",
 167                           *element->value.complex->list[i]->u.numeric);
 168             }
 169             break;
 170         default:
 171             assert (0);
 172         }
 173     }
 174 }
 175
 176 typedef struct {
 177     int type;
 178     int major;
 179     int minor;
 180     Z_AttributesPlusTerm *zapt;
 181 } AttrType;
 182
 183 static int attr_find (AttrType *src, oid_value *attributeSetP)
 184 {
 185     while (src->major < src->zapt->num_attributes)
 186     {
 187         Z_AttributeElement *element;
 188
 189         element = src->zapt->attributeList[src->major];
 190         if (src->type == *element->attributeType)
 191         {
 192             switch (element->which)
 193             {
 194             case Z_AttributeValue_numeric:
 195                 ++(src->major);
 196                 if (element->attributeSet && attributeSetP)
 197                 {
 198                     oident *attrset;
 199
 200                     attrset = oid_getentbyoid (element->attributeSet);
 201                     *attributeSetP = attrset->value;
 202                 }
 203                 return *element->value.numeric;
 204                 break;
 205             case Z_AttributeValue_complex:
 206                 if (src->minor >= element->value.complex->num_list ||
 207                     element->value.complex->list[src->minor]->which !=
 208                     Z_StringOrNumeric_numeric)
 209                     break;
 210                 ++(src->minor);
 211                 if (element->attributeSet && attributeSetP)
 212                 {
 213                     oident *attrset;
 214
 215                     attrset = oid_getentbyoid (element->attributeSet);
 216                     *attributeSetP = attrset->value;
 217                 }
 218                 return *element->value.complex->list[src->minor-1]->u.numeric;
 219             default:
 220                 assert (0);
 221             }
 222         }
 223         ++(src->major);
 224     }
 225     return -1;
 226 }
 227
 228 static void attr_init (AttrType *src, Z_AttributesPlusTerm *zapt,
 229                        int type)
 230 {
 231     src->zapt = zapt;
 232     src->type = type;
 233     src->major = 0;
 234     src->minor = 0;
 235 }
 236
 237 struct trunc_info {
 238     int  *ptr;
 239     int  *indx;
 240     char **heap;
 241     int  heapnum;
 242     int  (*cmp)(const void *p1, const void *p2);
 243     int  keysize;
 244     char *swapbuf;
 245     char *tmpbuf;
 246     char *buf;
 247 };
 248
 249 static void heap_swap (struct trunc_info *ti, int i1, int i2)
 250 {
 251     int swap;
 252
 253     swap = ti->ptr[i1];
 254     ti->ptr[i1] = ti->ptr[i2];
 255     ti->ptr[i2] = swap;
 256 }
 257
 258 static void heap_delete (struct trunc_info *ti)
 259 {
 260     int cur = 1, child = 2;
 261
 262     heap_swap (ti, 1, ti->heapnum--);
 263     while (child <= ti->heapnum) {
 264         if (child < ti->heapnum &&
 265             (*ti->cmp)(ti->heap[ti->ptr[child]],
 266                        ti->heap[ti->ptr[1+child]]) > 0)
 267             child++;
 268         if ((*ti->cmp)(ti->heap[ti->ptr[cur]],
 269                        ti->heap[ti->ptr[child]]) > 0)
 270         {
 271             heap_swap (ti, cur, child);
 272             cur = child;
 273             child = 2*cur;
 274         }
 275         else
 276             break;
 277     }
 278 }
 279
 280 static void heap_insert (struct trunc_info *ti, const char *buf, int indx)
 281 {
 282     int cur, parent;
 283
 284     cur = ++(ti->heapnum);
 285     memcpy (ti->heap[ti->ptr[cur]], buf, ti->keysize);
 286     ti->indx[ti->ptr[cur]] = indx;
 287     parent = cur/2;
 288     while (parent && (*ti->cmp)(ti->heap[ti->ptr[parent]],
 289                                 ti->heap[ti->ptr[cur]]) > 0)
 290     {
 291         heap_swap (ti, cur, parent);
 292         cur = parent;
 293         parent = cur/2;
 294     }
 295 }
 296
 297 static
 298 struct trunc_info *heap_init (int size, int key_size,
 299                               int (*cmp)(const void *p1, const void *p2))
 300 {
 301     struct trunc_info *ti = xmalloc (sizeof(*ti));
 302     int i;
 303
 304     ++size;
 305     ti->heapnum = 0;
 306     ti->keysize = key_size;
 307     ti->cmp = cmp;
 308     ti->indx = xmalloc (size * sizeof(*ti->indx));
 309     ti->heap = xmalloc (size * sizeof(*ti->heap));
 310     ti->ptr = xmalloc (size * sizeof(*ti->ptr));
 311     ti->swapbuf = xmalloc (ti->keysize);
 312     ti->tmpbuf = xmalloc (ti->keysize);
 313     ti->buf = xmalloc (size * ti->keysize);
 314     for (i = size; --i >= 0; )
 315     {
 316         ti->ptr[i] = i;
 317         ti->heap[i] = ti->buf + ti->keysize * i;
 318     }
 319     return ti;
 320 }
 321
 322 static void heap_close (struct trunc_info *ti)
 323 {
 324     xfree (ti->ptr);
 325     xfree (ti->indx);
 326     xfree (ti->heap);
 327     xfree (ti->swapbuf);
 328     xfree (ti->tmpbuf);
 329     xfree (ti);
 330 }
 331
 332 static RSET rset_trunc_r (ISAM isam, ISAM_P *isam_p, int from, int to,
 333                          int merge_chunk)
 334 {
 335     RSET result;
 336     RSFD result_rsfd;
 337     rset_temp_parms parms;
 338
 339     parms.key_size = sizeof(struct it_key);
 340     result = rset_create (rset_kind_temp, &parms);
 341     result_rsfd = rset_open (result, RSETF_WRITE|RSETF_SORT_SYSNO);
 342
 343     if (to - from > merge_chunk)
 344     {
 345         RSFD *rsfd;
 346         RSET *rset;
 347         int i, i_add = (to-from)/merge_chunk + 1;
 348         struct trunc_info *ti;
 349         int rscur = 0;
 350         int rsmax = (to-from)/i_add + 1;
 351
 352         rset = xmalloc (sizeof(*rset) * rsmax);
 353         rsfd = xmalloc (sizeof(*rsfd) * rsmax);
 354
 355         for (i = from; i < to; i += i_add)
 356         {
 357             if (i_add <= to - i)
 358                 rset[rscur] = rset_trunc_r (isam, isam_p, i, i+i_add,
 359                                             merge_chunk);
 360             else
 361                 rset[rscur] = rset_trunc_r (isam, isam_p, i, to,
 362                                             merge_chunk);
 363             rscur++;
 364         }
 365         ti = heap_init (rscur, sizeof(struct it_key), key_compare);
 366         for (i = rscur; --i >= 0; )
 367         {
 368             rsfd[i] = rset_open (rset[i], RSETF_READ|RSETF_SORT_SYSNO);
 369             if (rset_read (rset[i], rsfd[i], ti->tmpbuf))
 370                 heap_insert (ti, ti->tmpbuf, i);
 371             else
 372             {
 373                 rset_close (rset[i], rsfd[i]);
 374                 rset_delete (rset[i]);
 375             }
 376         }
 377         while (ti->heapnum)
 378         {
 379             int n = ti->indx[ti->ptr[1]];
 380
 381             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 382
 383             while (1)
 384             {
 385                 if (!rset_read (rset[n], rsfd[n], ti->tmpbuf))
 386                 {
 387                     heap_delete (ti);
 388                     rset_close (rset[n], rsfd[n]);
 389                     rset_delete (rset[n]);
 390                     break;
 391                 }
 392                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 393                 {
 394                     heap_delete (ti);
 395                     heap_insert (ti, ti->tmpbuf, n);
 396                     break;
 397                 }
 398             }
 399         }
 400         xfree (rset);
 401         xfree (rsfd);
 402         heap_close (ti);
 403     }
 404     else
 405     {
 406         ISPT *ispt;
 407         int i;
 408         struct trunc_info *ti;
 409
 410         ispt = xmalloc (sizeof(*ispt) * (to-from));
 411
 412         ti = heap_init (to-from, sizeof(struct it_key),
 413                         key_compare);
 414         for (i = to-from; --i >= 0; )
 415         {
 416             ispt[i] = is_position (isam, isam_p[from+i]);
 417             if (is_readkey (ispt[i], ti->tmpbuf))
 418                 heap_insert (ti, ti->tmpbuf, i);
 419             else
 420                 is_pt_free (ispt[i]);
 421         }
 422         while (ti->heapnum)
 423         {
 424             int n = ti->indx[ti->ptr[1]];
 425
 426             rset_write (result, result_rsfd, ti->heap[ti->ptr[1]]);
 427 #if 0
 428 /* section that preserve all keys */
 429             heap_delete (ti);
 430             if (is_readkey (ispt[n], ti->tmpbuf))
 431                 heap_insert (ti, ti->tmpbuf, n);
 432             else
 433                 is_pt_free (ispt[n]);
 434 #else
 435 /* section that preserve all keys with unique sysnos */
 436             while (1)
 437             {
 438                 if (!is_readkey (ispt[n], ti->tmpbuf))
 439                 {
 440                     heap_delete (ti);
 441                     is_pt_free (ispt[n]);
 442                     break;
 443                 }
 444                 if ((*ti->cmp)(ti->tmpbuf, ti->heap[ti->ptr[1]]) > 1)
 445                 {
 446                     heap_delete (ti);
 447                     heap_insert (ti, ti->tmpbuf, n);
 448                     break;
 449                 }
 450             }
 451 #endif
 452         }
 453         heap_close (ti);
 454         xfree (ispt);
 455     }
 456     rset_close (result, result_rsfd);
 457     return result;
 458 }
 459
 460 static int isam_trunc_cmp (const void *p1, const void *p2)
 461 {
 462     ISAM_P i1 = *(ISAM_P*) p1;
 463     ISAM_P i2 = *(ISAM_P*) p2;
 464     int d;
 465
 466     d = is_type (i1) - is_type (i2);
 467     if (d)
 468         return d;
 469     return is_block (i1) - is_block (i2);
 470 }
 471
 472 static RSET rset_trunc (ISAM isam, ISAM_P *isam_p, int no)
 473 {
 474
 475     qsort (isam_p, no, sizeof(*isam_p), isam_trunc_cmp);
 476     return rset_trunc_r (isam, isam_p, 0, no, 100);
 477 }
 478
 479 struct grep_info {
 480     ISAM_P *isam_p_buf;
 481     int isam_p_size;
 482     int isam_p_indx;
 483 };
 484
 485 static void add_isam_p (const char *info, struct grep_info *p)
 486 {
 487     if (p->isam_p_indx == p->isam_p_size)
 488     {
 489         ISAM_P *new_isam_p_buf;
 490
 491         p->isam_p_size = 2*p->isam_p_size + 100;
 492         new_isam_p_buf = xmalloc (sizeof(*new_isam_p_buf) *
 493                                   p->isam_p_size);
 494         if (p->isam_p_buf)
 495         {
 496             memcpy (new_isam_p_buf, p->isam_p_buf,
 497                     p->isam_p_indx * sizeof(*p->isam_p_buf));
 498             xfree (p->isam_p_buf);
 499         }
 500         p->isam_p_buf = new_isam_p_buf;
 501     }
 502     assert (*info == sizeof(*p->isam_p_buf));
 503     memcpy (p->isam_p_buf + p->isam_p_indx, info+1, sizeof(*p->isam_p_buf));
 504     (p->isam_p_indx)++;
 505 }
 506
 507 static int grep_handle (Dict_char *name, const char *info, void *p)
 508 {
 509     logf (LOG_DEBUG, "dict name: %s", name);
 510     add_isam_p (info, p);
 511     return 0;
 512 }
 513
 514 static void gen_regular_rel (char *dst, int val, int islt)
 515 {
 516     int dst_p = 1;
 517     int w, d, i;
 518     int pos = 0;
 519     char numstr[20];
 520
 521     *dst = '(';
 522     sprintf (numstr, "%d", val);
 523     for (w = strlen(numstr); --w >= 0; pos++)
 524     {
 525         d = numstr[w];
 526         if (pos > 0)
 527         {
 528             if (islt)
 529             {
 530                 if (d == '0')
 531                     continue;
 532                 d--;
 533             }
 534             else
 535             {
 536                 if (d == '9')
 537                     continue;
 538                 d++;
 539             }
 540         }
 541
 542         strcpy (dst + dst_p, numstr);
 543         dst_p = strlen(dst) - pos - 1;
 544
 545         if (islt)
 546         {
 547             if (d != '0')
 548             {
 549                 dst[dst_p++] = '[';
 550                 dst[dst_p++] = '0';
 551                 dst[dst_p++] = '-';
 552                 dst[dst_p++] = d;
 553                 dst[dst_p++] = ']';
 554             }
 555             else
 556                 dst[dst_p++] = d;
 557         }
 558         else
 559         {
 560             if (d != '9')
 561             {
 562                 dst[dst_p++] = '[';
 563                 dst[dst_p++] = d;
 564                 dst[dst_p++] = '-';
 565                 dst[dst_p++] = '9';
 566                 dst[dst_p++] = ']';
 567             }
 568             else
 569                 dst[dst_p++] = d;
 570         }
 571         for (i = 0; i<pos; i++)
 572         {
 573             dst[dst_p++] = '[';
 574             dst[dst_p++] = '0';
 575             dst[dst_p++] = '-';
 576             dst[dst_p++] = '9';
 577             dst[dst_p++] = ']';
 578         }
 579         dst[dst_p++] = '|';
 580     }
 581     dst[dst_p] = '\0';
 582     if (islt)
 583     {
 584         for (i=1; i<pos; i++)
 585             strcat (dst, "[0-9]?");
 586     }
 587     else
 588     {
 589         for (i = 0; i <= pos; i++)
 590             strcat (dst, "[0-9]");
 591         strcat (dst, "[0-9]*");
 592     }
 593     strcat (dst, ")");
 594 }
 595
 596 static int relational_term (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
 597                             const char *term_sub,
 598                             char *term_dict,
 599                             oid_value attributeSet,
 600                             struct grep_info *grep_info,
 601                             int *max_pos)
 602 {
 603     AttrType relation;
 604     int relation_value;
 605     int term_value;
 606     int r;
 607
 608     attr_init (&relation, zapt, 2);
 609     relation_value = attr_find (&relation, NULL);
 610     term_value = atoi (term_sub);
 611
 612     switch (relation_value)
 613     {
 614     case 1:
 615         if (term_value <= 0)
 616             return 1;
 617         logf (LOG_DEBUG, "Relation <");
 618         gen_regular_rel (term_dict + strlen(term_dict), term_value-1, 1);
 619         break;
 620     case 2:
 621         if (term_value < 0)
 622             return 1;
 623         logf (LOG_DEBUG, "Relation <=");
 624         gen_regular_rel (term_dict + strlen(term_dict), term_value, 1);
 625         break;
 626     case 4:
 627         if (term_value < 0)
 628             term_value = 0;
 629         logf (LOG_DEBUG, "Relation >=");
 630         gen_regular_rel (term_dict + strlen(term_dict), term_value, 0);
 631         break;
 632     case 5:
 633         if (term_value < 0)
 634             term_value = 0;
 635         logf (LOG_DEBUG, "Relation >");
 636         gen_regular_rel (term_dict + strlen(term_dict), term_value+1, 0);
 637         break;
 638     default:
 639         return 0;
 640     }
 641     logf (LOG_DEBUG, "dict_lookup_grep: %s", term_dict);
 642     r = dict_lookup_grep (zi->wordDict, term_dict, 0, grep_info, max_pos,
 643                           grep_handle);
 644     if (r)
 645         logf (LOG_WARN, "dict_lookup_grep fail, rel=gt: %d", r);
 646     logf (LOG_DEBUG, "%d positions", grep_info->isam_p_indx);
 647     return 1;
 648 }
 649
 650 static int trunc_term (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
 651                        const char *term_sub,
 652                        oid_value attributeSet, struct grep_info *grep_info,
 653                        int num_bases, char **basenames)
 654 {
 655     char term_dict[2*IT_MAX_WORD+2];
 656     int i, j, r, base_no;
 657     AttrType truncation;
 658     int truncation_value;
 659     AttrType use;
 660     int use_value;
 661     oid_value curAttributeSet = attributeSet;
 662
 663     attr_init (&use, zapt, 1);
 664     use_value = attr_find (&use, &curAttributeSet);
 665     logf (LOG_DEBUG, "use value %d", use_value);
 666     attr_init (&truncation, zapt, 5);
 667     truncation_value = attr_find (&truncation, NULL);
 668     logf (LOG_DEBUG, "truncation value %d", truncation_value);
 669
 670     if (use_value == -1)
 671         use_value = 1016;
 672
 673     for (base_no = 0; base_no < num_bases; base_no++)
 674     {
 675         int max_pos;
 676         int prefix_len = index_word_prefix_map (term_dict, curAttributeSet,
 677                                                 use_value,
 678                                                 basenames[base_no]);
 679         if (prefix_len < 0)
 680         {
 681             zi->errCode = 114;
 682             return -1;
 683         }
 684         if (!relational_term (zi, zapt, term_sub, term_dict,
 685                               attributeSet, grep_info, &max_pos))
 686         {
 687             switch (truncation_value)
 688             {
 689             case -1:         /* not specified */
 690             case 100:        /* do not truncate */
 691                 strcat (term_dict, "(");
 692                 strcat (term_dict, term_sub);
 693                 strcat (term_dict, ")");
 694                 logf (LOG_DEBUG, "dict_lookup_grep: %s", term_dict);
 695                 r = dict_lookup_grep (zi->wordDict, term_dict, 0, grep_info,
 696                                       &max_pos, grep_handle);
 697                 if (r)
 698                     logf (LOG_WARN, "dict_lookup_grep err, trunc=none:%d", r);
 699                 break;
 700             case 1:          /* right truncation */
 701                 strcat (term_dict, term_sub);
 702                 strcat (term_dict, ".*");
 703                 dict_lookup_grep (zi->wordDict, term_dict, 0, grep_info,
 704                                   &max_pos, grep_handle);
 705                 break;
 706             case 2:          /* left truncation */
 707             case 3:          /* left&right truncation */
 708                 zi->errCode = 120;
 709                 return -1;
 710             case 101:        /* process # in term */
 711                 for (j = strlen(term_dict), i = 0; term_sub[i] && i < 2; i++)
 712                     term_dict[j++] = term_sub[i];
 713                 for (; term_sub[i]; i++)
 714                     if (term_sub[i] == '#')
 715                     {
 716                         term_dict[j++] = '.';
 717                         term_dict[j++] = '*';
 718                     }
 719                     else
 720                         term_dict[j++] = term_sub[i];
 721                 term_dict[j] = '\0';
 722                 r = dict_lookup_grep (zi->wordDict, term_dict, 0, grep_info,
 723                                       &max_pos, grep_handle);
 724                 if (r)
 725                     logf (LOG_WARN, "dict_lookup_grep err, trunc=#: %d",
 726                           r);
 727                 break;
 728             case 102:        /* regular expression */
 729                 strcat (term_dict, "(");
 730                 strcat (term_dict, term_sub);
 731                 strcat (term_dict, ")");
 732                 logf (LOG_DEBUG, "dict_lookup_grep: %s", term_dict);
 733                 r = dict_lookup_grep (zi->wordDict, term_dict, 0, grep_info,
 734                                       &max_pos, grep_handle);
 735                 if (r)
 736                     logf (LOG_WARN, "dict_lookup_grep err, trunc=regular: %d",
 737                           r);
 738                 break;
 739             }
 740         }
 741         logf (LOG_DEBUG, "max_pos = %d", max_pos);
 742         if (max_pos <= strlen(basenames[base_no]))
 743         {
 744             zi->errCode = 109; /* Database unavailable */
 745             zi->errString = basenames[base_no];
 746             return -1;
 747         }
 748     }
 749     logf (LOG_DEBUG, "%d positions", grep_info->isam_p_indx);
 750     return 0;
 751 }
 752
 753 static void trans_term (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
 754                         char *termz)
 755 {
 756     size_t i, sizez;
 757     Z_Term *term = zapt->term;
 758
 759     sizez = term->u.general->len;
 760     if (sizez > IT_MAX_WORD)
 761         sizez = IT_MAX_WORD;
 762     for (i = 0; i < sizez; i++)
 763         termz[i] = index_char_cvt (term->u.general->buf[i]);
 764     termz[i] = '\0';
 765 }
 766
 767 static RSET rpn_search_APT_relevance (ZServerInfo *zi,
 768                                       Z_AttributesPlusTerm *zapt,
 769                                       oid_value attributeSet,
 770                                       int num_bases, char **basenames)
 771 {
 772     rset_relevance_parms parms;
 773     char termz[IT_MAX_WORD+1];
 774     char term_sub[IT_MAX_WORD+1];
 775     struct grep_info grep_info;
 776     char *p0 = termz, *p1 = NULL;
 777     RSET result;
 778
 779     parms.key_size = sizeof(struct it_key);
 780     parms.max_rec = 100;
 781     parms.cmp = key_compare;
 782     parms.is = zi->wordIsam;
 783
 784     if (zapt->term->which != Z_Term_general)
 785     {
 786         zi->errCode = 124;
 787         return NULL;
 788     }
 789     trans_term (zi, zapt, termz);
 790     grep_info.isam_p_indx = 0;
 791     grep_info.isam_p_size = 0;
 792     grep_info.isam_p_buf = NULL;
 793     while (1)
 794     {
 795         if ((p1 = strchr (p0, ' ')))
 796         {
 797             memcpy (term_sub, p0, p1-p0);
 798             term_sub[p1-p0] = '\0';
 799         }
 800         else
 801             strcpy (term_sub, p0);
 802         if (trunc_term (zi, zapt, term_sub, attributeSet, &grep_info,
 803                         num_bases, basenames))
 804             return NULL;
 805         if (!p1)
 806             break;
 807         p0 = p1;
 808         while (*++p0 == ' ')
 809             ;
 810     }
 811     parms.isam_positions = grep_info.isam_p_buf;
 812     parms.no_isam_positions = grep_info.isam_p_indx;
 813     if (grep_info.isam_p_indx > 0)
 814         result = rset_create (rset_kind_relevance, &parms);
 815     else
 816         result = rset_create (rset_kind_null, NULL);
 817     xfree (grep_info.isam_p_buf);
 818     return result;
 819 }
 820
 821 static RSET rpn_search_APT_word (ZServerInfo *zi,
 822                                  Z_AttributesPlusTerm *zapt,
 823                                  oid_value attributeSet,
 824                                  int num_bases, char **basenames)
 825 {
 826     rset_isam_parms parms;
 827     char termz[IT_MAX_WORD+1];
 828     struct grep_info grep_info;
 829     RSET result;
 830
 831     if (zapt->term->which != Z_Term_general)
 832     {
 833         zi->errCode = 124;
 834         return NULL;
 835     }
 836     trans_term (zi, zapt, termz);
 837
 838     grep_info.isam_p_indx = 0;
 839     grep_info.isam_p_size = 0;
 840     grep_info.isam_p_buf = NULL;
 841
 842     if (trunc_term (zi, zapt, termz, attributeSet, &grep_info,
 843                     num_bases, basenames))
 844         return NULL;
 845     if (grep_info.isam_p_indx < 1)
 846         result = rset_create (rset_kind_null, NULL);
 847     else if (grep_info.isam_p_indx == 1)
 848     {
 849         parms.is = zi->wordIsam;
 850         parms.pos = *grep_info.isam_p_buf;
 851         result = rset_create (rset_kind_isam, &parms);
 852     }
 853     else
 854         result = rset_trunc (zi->wordIsam, grep_info.isam_p_buf,
 855                              grep_info.isam_p_indx);
 856     xfree (grep_info.isam_p_buf);
 857     return result;
 858 }
 859
 860 static RSET rpn_prox (RSET *rset, int rset_no)
 861 {
 862     int i;
 863     RSFD *rsfd;
 864     int  *more;
 865     struct it_key **buf;
 866     RSFD rsfd_result;
 867     RSET result;
 868     rset_temp_parms parms;
 869
 870     rsfd = xmalloc (sizeof(*rsfd)*rset_no);
 871     more = xmalloc (sizeof(*more)*rset_no);
 872     buf = xmalloc (sizeof(*buf)*rset_no);
 873
 874     for (i = 0; i<rset_no; i++)
 875     {
 876         buf[i] = xmalloc (sizeof(**buf));
 877         rsfd[i] = rset_open (rset[i], RSETF_READ|RSETF_SORT_SYSNO);
 878         if (!(more[i] = rset_read (rset[i], rsfd[i], buf[i])))
 879         {
 880             while (i >= 0)
 881             {
 882                 rset_close (rset[i], rsfd[i]);
 883                 xfree (buf[i]);
 884                 --i;
 885             }
 886             xfree (rsfd);
 887             xfree (more);
 888             xfree (buf);
 889             return rset_create (rset_kind_null, NULL);
 890         }
 891     }
 892     parms.key_size = sizeof (struct it_key);
 893     result = rset_create (rset_kind_temp, &parms);
 894     rsfd_result = rset_open (result, RSETF_WRITE|RSETF_SORT_SYSNO);
 895
 896     while (*more)
 897     {
 898         for (i = 1; i<rset_no; i++)
 899         {
 900             int cmp;
 901
 902             if (!more[i])
 903             {
 904                 *more = 0;
 905                 break;
 906             }
 907             cmp = key_compare (buf[i], buf[i-1]);
 908             if (cmp > 1)
 909             {
 910                 more[i-1] = rset_read (rset[i-1], rsfd[i-1], buf[i-1]);
 911                 break;
 912             }
 913             else if (cmp == 1)
 914             {
 915                 if (buf[i-1]->seqno+1 != buf[i]->seqno)
 916                 {
 917                     more[i-1] = rset_read (rset[i-1], rsfd[i-1], buf[i-1]);
 918                     break;
 919                 }
 920             }
 921             else
 922             {
 923                 more[i] = rset_read (rset[i], rsfd[i], buf[i]);
 924                 break;
 925             }
 926         }
 927         if (i == rset_no)
 928         {
 929             rset_write (result, rsfd_result, buf[0]);
 930             more[0] = rset_read (*rset, *rsfd, *buf);
 931         }
 932     }
 933
 934     for (i = 0; i<rset_no; i++)
 935     {
 936         rset_close (rset[i], rsfd[i]);
 937         xfree (buf[i]);
 938     }
 939     rset_close (result, rsfd_result);
 940     xfree (buf);
 941     xfree (more);
 942     xfree (rsfd);
 943     return result;
 944 }
 945
 946 static RSET rpn_search_APT_phrase (ZServerInfo *zi,
 947                                    Z_AttributesPlusTerm *zapt,
 948                                    oid_value attributeSet,
 949                                    int num_bases, char **basenames)
 950 {
 951     char termz[IT_MAX_WORD+1];
 952     char term_sub[IT_MAX_WORD+1];
 953     char *p0 = termz, *p1 = NULL;
 954     RSET rset[60], result;
 955     int i, rset_no = 0;
 956     struct grep_info grep_info;
 957
 958     if (zapt->term->which != Z_Term_general)
 959     {
 960         zi->errCode = 124;
 961         return NULL;
 962     }
 963     trans_term (zi, zapt, termz);
 964
 965     grep_info.isam_p_size = 0;
 966     grep_info.isam_p_buf = NULL;
 967
 968     while (1)
 969     {
 970         if ((p1 = strchr (p0, ' ')))
 971         {
 972             memcpy (term_sub, p0, p1-p0);
 973             term_sub[p1-p0] = '\0';
 974         }
 975         else
 976             strcpy (term_sub, p0);
 977
 978         grep_info.isam_p_indx = 0;
 979         if (trunc_term (zi, zapt, term_sub, attributeSet, &grep_info,
 980                         num_bases, basenames))
 981             return NULL;
 982         if (grep_info.isam_p_indx == 0)
 983             rset[rset_no] = rset_create (rset_kind_null, NULL);
 984         else if (grep_info.isam_p_indx > 1)
 985             rset[rset_no] = rset_trunc (zi->wordIsam,
 986                                         grep_info.isam_p_buf,
 987                                         grep_info.isam_p_indx);
 988         else
 989         {
 990             rset_isam_parms parms;
 991
 992             parms.is = zi->wordIsam;
 993             parms.pos = *grep_info.isam_p_buf;
 994             rset[rset_no] = rset_create (rset_kind_isam, &parms);
 995         }
 996         assert (rset[rset_no]);
 997         if (++rset_no >= sizeof(rset)/sizeof(*rset))
 998             break;
 999         if (!p1)
1000             break;
1001         p0 = p1;
1002         while (*++p0 == ' ')
1003             ;
1004     }
1005     xfree (grep_info.isam_p_buf);
1006     if (rset_no == 0)
1007         return rset_create (rset_kind_null, NULL);
1008     else if (rset_no == 1)
1009         return (rset[0]);
1010
1011     result = rpn_prox (rset, rset_no);
1012     for (i = 0; i<rset_no; i++)
1013         rset_delete (rset[i]);
1014     return result;
1015 }
1016
1017 static RSET rpn_search_APT_local (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
1018                                   oid_value attributeSet)
1019 {
1020     RSET result;
1021     RSFD rsfd;
1022     struct it_key key;
1023     rset_temp_parms parms;
1024     char termz[IT_MAX_WORD+1];
1025
1026     if (zapt->term->which != Z_Term_general)
1027     {
1028         zi->errCode = 124;
1029         return NULL;
1030     }
1031     parms.key_size = sizeof (struct it_key);
1032     result = rset_create (rset_kind_temp, &parms);
1033     rsfd = rset_open (result, RSETF_WRITE|RSETF_SORT_SYSNO);
1034
1035     trans_term (zi, zapt, termz);
1036     key.sysno = atoi (termz);
1037     if (key.sysno <= 0)
1038         key.sysno = 1;
1039     rset_write (result, rsfd, &key);
1040     rset_close (result, rsfd);
1041     return result;
1042 }
1043
1044 static RSET rpn_search_APT (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
1045                             oid_value attributeSet,
1046                             int num_bases, char **basenames)
1047 {
1048     AttrType relation;
1049     AttrType structure;
1050     int relation_value, structure_value;
1051
1052     attr_init (&relation, zapt, 2);
1053     attr_init (&structure, zapt, 4);
1054
1055     relation_value = attr_find (&relation, NULL);
1056     structure_value = attr_find (&structure, NULL);
1057     switch (structure_value)
1058     {
1059     case -1:
1060         if (relation_value == 102) /* relevance relation */
1061             return rpn_search_APT_relevance (zi, zapt, attributeSet,
1062                                              num_bases, basenames);
1063         return rpn_search_APT_phrase (zi, zapt, attributeSet,
1064                                       num_bases, basenames);
1065     case 1: /* phrase */
1066         if (relation_value == 102) /* relevance relation */
1067             return rpn_search_APT_relevance (zi, zapt, attributeSet,
1068                                              num_bases, basenames);
1069         return rpn_search_APT_phrase (zi, zapt, attributeSet,
1070                                       num_bases, basenames);
1071         break;
1072     case 2: /* word */
1073         if (relation_value == 102) /* relevance relation */
1074             return rpn_search_APT_relevance (zi, zapt, attributeSet,
1075                                              num_bases, basenames);
1076         return rpn_search_APT_word (zi, zapt, attributeSet,
1077                                     num_bases, basenames);
1078     case 3: /* key */
1079         break;
1080     case 4: /* year */
1081         break;
1082     case 5: /* date - normalized */
1083         break;
1084     case 6: /* word list */
1085         return rpn_search_APT_relevance (zi, zapt, attributeSet,
1086                                          num_bases, basenames);
1087     case 100: /* date - un-normalized */
1088         break;
1089     case 101: /* name - normalized */
1090         break;
1091     case 102: /* date - un-normalized */
1092         break;
1093     case 103: /* structure */
1094         break;
1095     case 104: /* urx */
1096         break;
1097     case 105: /* free-form-text */
1098         return rpn_search_APT_relevance (zi, zapt, attributeSet,
1099                                          num_bases, basenames);
1100     case 106: /* document-text */
1101         return rpn_search_APT_relevance (zi, zapt, attributeSet,
1102                                          num_bases, basenames);
1103     case 107: /* local-number */
1104         return rpn_search_APT_local (zi, zapt, attributeSet);
1105     case 108: /* string */
1106         return rpn_search_APT_word (zi, zapt, attributeSet,
1107                                     num_bases, basenames);
1108     case 109: /* numeric string */
1109         break;
1110     }
1111     zi->errCode = 118;
1112     return NULL;
1113 }
1114
1115 static RSET rpn_search_ref (ZServerInfo *zi, Z_ResultSetId *resultSetId)
1116 {
1117     ZServerSet *s;
1118
1119     if (!(s = resultSetGet (zi, resultSetId)))
1120         return rset_create (rset_kind_null, NULL);
1121     return s->rset;
1122 }
1123
1124 static RSET rpn_search_structure (ZServerInfo *zi, Z_RPNStructure *zs,
1125                                   oid_value attributeSet,
1126                                   int num_bases, char **basenames)
1127 {
1128     RSET r = NULL;
1129     if (zs->which == Z_RPNStructure_complex)
1130     {
1131         rset_bool_parms bool_parms;
1132
1133         bool_parms.rset_l = rpn_search_structure (zi, zs->u.complex->s1,
1134                                                   attributeSet,
1135                                                   num_bases, basenames);
1136         if (bool_parms.rset_l == NULL)
1137             return NULL;
1138         bool_parms.rset_r = rpn_search_structure (zi, zs->u.complex->s2,
1139                                                   attributeSet,
1140                                                   num_bases, basenames);
1141         if (bool_parms.rset_r == NULL)
1142         {
1143             rset_delete (bool_parms.rset_l);
1144             return NULL;
1145         }
1146         bool_parms.key_size = sizeof(struct it_key);
1147         bool_parms.cmp = key_compare;
1148
1149         switch (zs->u.complex->operator->which)
1150         {
1151         case Z_Operator_and:
1152             r = rset_create (rset_kind_and, &bool_parms);
1153             break;
1154         case Z_Operator_or:
1155             r = rset_create (rset_kind_or, &bool_parms);
1156             break;
1157         case Z_Operator_and_not:
1158             r = rset_create (rset_kind_not, &bool_parms);
1159             break;
1160         default:
1161             assert (0);
1162         }
1163     }
1164     else if (zs->which == Z_RPNStructure_simple)
1165     {
1166         if (zs->u.simple->which == Z_Operand_APT)
1167         {
1168             logf (LOG_DEBUG, "rpn_search_APT");
1169             r = rpn_search_APT (zi, zs->u.simple->u.attributesPlusTerm,
1170                                 attributeSet, num_bases, basenames);
1171         }
1172         else if (zs->u.simple->which == Z_Operand_resultSetId)
1173         {
1174             logf (LOG_DEBUG, "rpn_search_ref");
1175             r = rpn_search_ref (zi, zs->u.simple->u.resultSetId);
1176         }
1177         else
1178         {
1179             assert (0);
1180         }
1181     }
1182     else
1183     {
1184         assert (0);
1185     }
1186     return r;
1187 }
1188
1189 static void count_set (RSET r, int *count)
1190 {
1191     int psysno = 0;
1192     struct it_key key;
1193     RSFD rfd;
1194
1195     logf (LOG_DEBUG, "rpn_save_set");
1196     *count = 0;
1197     rfd = rset_open (r, RSETF_READ|RSETF_SORT_SYSNO);
1198     while (rset_read (r, rfd, &key))
1199     {
1200         if (key.sysno != psysno)
1201         {
1202             psysno = key.sysno;
1203             (*count)++;
1204         }
1205     }
1206     rset_close (r, rfd);
1207     logf (LOG_DEBUG, "%d distinct sysnos", *count);
1208 }
1209
1210 int rpn_search (ZServerInfo *zi,
1211                 Z_RPNQuery *rpn, int num_bases, char **basenames,
1212                 const char *setname, int *hits)
1213 {
1214     RSET rset;
1215     oident *attrset;
1216     oid_value attributeSet;
1217
1218     zi->errCode = 0;
1219     zi->errString = NULL;
1220
1221     attrset = oid_getentbyoid (rpn->attributeSetId);
1222     attributeSet = attrset->value;
1223
1224     rset = rpn_search_structure (zi, rpn->RPNStructure, attributeSet,
1225                                  num_bases, basenames);
1226     if (!rset)
1227         return zi->errCode;
1228     count_set (rset, hits);
1229     resultSetAdd (zi, setname, 1, rset);
1230     if (zi->errCode)
1231         logf (LOG_DEBUG, "search error: %d", zi->errCode);
1232     return zi->errCode;
1233 }
1234
1235 struct scan_info {
1236     struct scan_entry *list;
1237     ODR odr;
1238     int before, after;
1239     ISAM isam;
1240     char prefix[20];
1241 };
1242
1243 static int scan_handle (Dict_char *name, const char *info, int pos,
1244                         void *client)
1245 {
1246     int len_prefix, idx;
1247     ISAM_P isam_p;
1248     RSET rset;
1249     struct scan_info *scan_info = client;
1250
1251     rset_isam_parms parms;
1252
1253     len_prefix = strlen(scan_info->prefix);
1254     if (memcmp (name, scan_info->prefix, len_prefix))
1255         return 1;
1256     if (pos > 0)
1257         idx = scan_info->after - pos + scan_info->before;
1258     else
1259         idx = - pos - 1;
1260     scan_info->list[idx].term = odr_malloc (scan_info->odr,
1261                                             strlen(name + len_prefix)+1);
1262     strcpy (scan_info->list[idx].term, name + len_prefix);
1263     assert (*info == sizeof(isam_p));
1264     memcpy (&isam_p, info+1, sizeof(isam_p));
1265     parms.is = scan_info->isam;
1266     parms.pos = isam_p;
1267 #if 1
1268     rset = rset_create (rset_kind_isam, &parms);
1269     count_set (rset, &scan_info->list[idx].occurrences);
1270     rset_delete (rset);
1271 #else
1272     scan_info->list[idx].occurrences = 1;
1273 #endif
1274     logf (LOG_DEBUG, "pos=%3d idx=%3d name=%s", pos, idx, name);
1275     return 0;
1276 }
1277
1278
1279 static int dummy_handle (Dict_char *name, const char *info, void *p)
1280 {
1281     return 0;
1282 }
1283
1284 int rpn_scan (ZServerInfo *zi, Z_AttributesPlusTerm *zapt,
1285               int num_bases, char **basenames,
1286               int *position, int *num_entries, struct scan_entry **list,
1287               int *status)
1288 {
1289     int i, j, sizez, max_pos;
1290     int pos = *position;
1291     int num = *num_entries;
1292     int before;
1293     int after;
1294     char termz[IT_MAX_WORD+20];
1295     AttrType use;
1296     int use_value;
1297     Z_Term *term = zapt->term;
1298     struct scan_info scan_info;
1299
1300     logf (LOG_DEBUG, "scan, position = %d, num = %d", pos, num);
1301
1302     if (num_bases != 1)
1303         return 111;
1304     scan_info.before = before = pos-1;
1305     scan_info.after = after = 1+num-pos;
1306     scan_info.odr = zi->odr;
1307
1308     logf (LOG_DEBUG, "scan, before = %d, after = %d", before, after);
1309
1310     scan_info.isam = zi->wordIsam;
1311     scan_info.list = odr_malloc (zi->odr, (before+after)*
1312                                  sizeof(*scan_info.list));
1313     for (j = 0; j<before+after; j++)
1314         scan_info.list[j].term = NULL;
1315     attr_init (&use, zapt, 1);
1316     use_value = attr_find (&use, NULL);
1317     logf (LOG_DEBUG, "use value %d", use_value);
1318
1319     if (use_value == -1)
1320         use_value = 1016;
1321     i = index_word_prefix (termz, 1, use_value, *basenames);
1322
1323     dict_lookup_grep (zi->wordDict, termz, 0, NULL, &max_pos,
1324                       dummy_handle);
1325     if (max_pos <= strlen(*basenames))
1326     {
1327         zi->errString = *basenames;
1328         return zi->errCode = 109; /* Database unavailable */
1329     }
1330     strcpy (scan_info.prefix, termz);
1331     sizez = term->u.general->len;
1332     if (sizez > IT_MAX_WORD)
1333         sizez = IT_MAX_WORD;
1334     for (j = 0; j<sizez; j++)
1335         termz[j+i] = index_char_cvt (term->u.general->buf[j]);
1336     termz[j+i] = '\0';
1337
1338     dict_scan (zi->wordDict, termz, &before, &after, &scan_info, scan_handle);
1339
1340     *status = BEND_SCAN_SUCCESS;
1341
1342     for (i = 0; i<scan_info.after; i++)
1343         if (scan_info.list[scan_info.before+scan_info.after-i-1].term)
1344             break;
1345     *num_entries -= i;
1346     if (i)
1347         *status = BEND_SCAN_PARTIAL;
1348
1349     for (i = 0; i<scan_info.before; i++)
1350         if (scan_info.list[i].term)
1351             break;
1352     if (i)
1353         *status = BEND_SCAN_PARTIAL;
1354     *position -= i;
1355     *num_entries -= i;
1356
1357     *list = scan_info.list+i;       /* list is set to first 'real' entry */
1358
1359     if (*num_entries == 0)          /* signal 'unsupported use-attribute' */
1360         zi->errCode = 114;          /* if no entries was found */
1361     logf (LOG_DEBUG, "position = %d, num_entries = %d",
1362           *position, *num_entries);
1363     if (zi->errCode)
1364         logf (LOG_DEBUG, "scan error: %d", zi->errCode);
1365     return 0;
1366 }
1367
1368
1369