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