1 /* $Id: zsets.c,v 1.82 2005-05-11 12:39:37 adam Exp $
2 Copyright (C) 1995-2005
5 This file is part of the Zebra server.
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra. If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
33 #include <yaz/diagbib1.h>
36 #define SORT_IDX_ENTRYSIZE 64
37 #define ZSET_SORT_MAX_LEVEL 3
39 struct zebra_set_term_entry {
50 NMEM rset_nmem; /* for creating the rsets in */
55 struct zset_sort_info *sort_info;
56 struct zebra_set_term_entry *term_entries;
58 struct zebra_set *next;
61 zint cache_position; /* last position */
62 RSFD cache_rfd; /* rfd (NULL if not existing) */
63 zint cache_psysno; /* sysno for last position */
66 struct zset_sort_entry {
69 char buf[ZSET_SORT_MAX_LEVEL][SORT_IDX_ENTRYSIZE];
72 struct zset_sort_info {
75 struct zset_sort_entry *all_entries;
76 struct zset_sort_entry **entries;
79 static int log_level_set=0;
80 static int log_level_sort=0;
81 static int log_level_searchhits=0;
82 static int log_level_searchterms=0;
83 static int log_level_resultsets=0;
85 static void loglevels()
89 log_level_sort = yaz_log_module_level("sorting");
90 log_level_searchhits = yaz_log_module_level("searchhits");
91 log_level_searchterms = yaz_log_module_level("searchterms");
92 log_level_resultsets = yaz_log_module_level("resultsets");
96 ZEBRA_RES resultSetSearch(ZebraHandle zh, NMEM nmem, NMEM rset_nmem,
97 Z_RPNQuery *rpn, ZebraSet sset)
101 Z_SortKeySpecList *sort_sequence;
103 ZEBRA_RES res = ZEBRA_OK;
107 sort_sequence = (Z_SortKeySpecList *)
108 nmem_malloc(nmem, sizeof(*sort_sequence));
109 sort_sequence->num_specs = 10; /* FIXME - Hard-coded number */
110 sort_sequence->specs = (Z_SortKeySpec **)
111 nmem_malloc(nmem, sort_sequence->num_specs *
112 sizeof(*sort_sequence->specs));
113 for (i = 0; i<sort_sequence->num_specs; i++)
114 sort_sequence->specs[i] = 0;
116 attrset = oid_getentbyoid (rpn->attributeSetId);
117 res = rpn_search_top(zh, rpn->RPNStructure, attrset->value,
120 sset->num_bases, sset->basenames,
127 for (i = 0; sort_sequence->specs[i]; i++)
129 sort_sequence->num_specs = i;
132 res = resultSetRank (zh, sset, rset, rset_nmem);
136 res = resultSetSortSingle (zh, nmem, sset, rset,
137 sort_sequence, &sort_status);
144 ZEBRA_RES resultSetAddRPN (ZebraHandle zh, NMEM m, Z_RPNQuery *rpn,
145 int num_bases, char **basenames,
154 zebraSet = resultSetAdd (zh, setname, 1);
157 zebraSet->locked = 1;
160 zebraSet->rset_nmem = nmem_create();
162 zebraSet->num_bases = num_bases;
163 zebraSet->basenames =
164 nmem_malloc (zebraSet->nmem, num_bases * sizeof(*zebraSet->basenames));
165 for (i = 0; i<num_bases; i++)
166 zebraSet->basenames[i] = nmem_strdup (zebraSet->nmem, basenames[i]);
168 res = resultSetSearch(zh, zebraSet->nmem, zebraSet->rset_nmem,
170 zh->hits = zebraSet->hits;
173 zebraSet->locked = 0;
179 void resultSetAddTerm (ZebraHandle zh, ZebraSet s, int reg_type,
180 const char *db, int set,
181 int use, const char *term)
183 assert(zh); /* compiler shut up */
185 s->nmem = nmem_create ();
186 if (!s->term_entries)
189 s->term_entries_max = 1000;
191 nmem_malloc (s->nmem, s->term_entries_max *
192 sizeof(*s->term_entries));
193 for (i = 0; i < s->term_entries_max; i++)
194 s->term_entries[i].term = 0;
196 if (s->hits < s->term_entries_max)
198 s->term_entries[s->hits].reg_type = reg_type;
199 s->term_entries[s->hits].db = nmem_strdup (s->nmem, db);
200 s->term_entries[s->hits].set = set;
201 s->term_entries[s->hits].use = use;
202 s->term_entries[s->hits].term = nmem_strdup (s->nmem, term);
207 ZebraSet resultSetAdd (ZebraHandle zh, const char *name, int ov)
212 for (s = zh->sets; s; s = s->next)
213 if (!strcmp (s->name, name))
220 yaz_log(log_level_resultsets, "updating result set %s", name);
221 if (!ov || s->locked)
226 rset_close(s->cache_rfd);
227 rset_delete (s->rset);
230 nmem_destroy (s->rset_nmem);
232 nmem_destroy (s->nmem);
236 const char *sort_max_str = zebra_get_resource(zh, "sortmax", "1000");
238 yaz_log(log_level_resultsets, "adding result set %s", name);
239 s = (ZebraSet) xmalloc (sizeof(*s));
242 s->name = (char *) xmalloc (strlen(name)+1);
243 strcpy (s->name, name);
245 s->sort_info = (struct zset_sort_info *)
246 xmalloc (sizeof(*s->sort_info));
247 s->sort_info->max_entries = atoi(sort_max_str);
248 if (s->sort_info->max_entries < 2)
249 s->sort_info->max_entries = 2;
251 s->sort_info->entries = (struct zset_sort_entry **)
252 xmalloc (sizeof(*s->sort_info->entries) *
253 s->sort_info->max_entries);
254 s->sort_info->all_entries = (struct zset_sort_entry *)
255 xmalloc (sizeof(*s->sort_info->all_entries) *
256 s->sort_info->max_entries);
257 for (i = 0; i < s->sort_info->max_entries; i++)
258 s->sort_info->entries[i] = s->sort_info->all_entries + i;
267 s->cache_position = 0;
272 ZebraSet resultSetGet (ZebraHandle zh, const char *name)
276 for (s = zh->sets; s; s = s->next)
277 if (!strcmp (s->name, name))
279 if (!s->term_entries && !s->rset && s->rpn)
281 NMEM nmem = nmem_create ();
282 yaz_log(log_level_resultsets, "research %s", name);
284 s->rset_nmem=nmem_create();
285 resultSetSearch(zh, nmem, s->rset_nmem, s->rpn, s);
293 void resultSetInvalidate (ZebraHandle zh)
295 ZebraSet s = zh->sets;
297 yaz_log(log_level_resultsets, "invalidating result sets");
298 for (; s; s = s->next)
303 rset_close(s->cache_rfd);
304 rset_delete (s->rset);
308 s->cache_position = 0;
310 nmem_destroy(s->rset_nmem);
315 void resultSetDestroy (ZebraHandle zh, int num, char **names,int *statuses)
317 ZebraSet * ss = &zh->sets;
321 for (i = 0; i<num; i++)
322 statuses[i] = Z_DeleteStatus_resultSetDidNotExist;
329 for (i = 0; i<num; i++)
330 if (!strcmp (s->name, names[i]))
333 statuses[i] = Z_DeleteStatus_success;
342 xfree (s->sort_info->all_entries);
343 xfree (s->sort_info->entries);
344 xfree (s->sort_info);
347 nmem_destroy (s->nmem);
351 rset_close(s->cache_rfd);
352 rset_delete (s->rset);
355 nmem_destroy(s->rset_nmem);
364 ZebraMetaRecord *zebra_meta_records_create_range (ZebraHandle zh,
369 zint *pos = pos_small;
373 if (num > 10000 || num <= 0)
377 pos = xmalloc(sizeof(*pos) * num);
379 for (i = 0; i<num; i++)
382 mr = zebra_meta_records_create(zh, name, num, pos);
389 ZebraMetaRecord *zebra_meta_records_create (ZebraHandle zh, const char *name,
390 int num, zint *positions)
393 ZebraMetaRecord *sr = 0;
396 struct zset_sort_info *sort_info;
400 if (!(sset = resultSetGet (zh, name)))
402 if (!(rset = sset->rset))
404 if (!sset->term_entries)
406 sr = (ZebraMetaRecord *) xmalloc (sizeof(*sr) * num);
407 for (i = 0; i<num; i++)
414 if (positions[i] <= sset->term_entries_max)
416 sr[i].term = sset->term_entries[positions[i]-1].term;
417 sr[i].db = sset->term_entries[positions[i]-1].db;
423 sr = (ZebraMetaRecord *) xmalloc (sizeof(*sr) * num);
424 for (i = 0; i<num; i++)
431 sort_info = sset->sort_info;
436 for (i = 0; i<num; i++)
438 position = positions[i];
439 if (position > 0 && position <= sort_info->num_entries)
441 yaz_log(log_level_sort, "got pos=" ZINT_FORMAT
442 " (sorted)", position);
443 sr[i].sysno = sort_info->entries[position-1]->sysno;
444 sr[i].score = sort_info->entries[position-1]->score;
448 /* did we really get all entries using sort ? */
449 for (i = 0; i<num; i++)
454 if (i < num) /* nope, get the rest, unsorted - sorry */
463 position = sort_info->num_entries;
464 while (num_i < num && positions[num_i] <= position)
467 if (sset->cache_rfd &&
468 num_i < num && positions[num_i] > sset->cache_position)
470 position = sset->cache_position;
471 rfd = sset->cache_rfd;
472 psysno = sset->cache_psysno;
477 rset_close(sset->cache_rfd);
478 rfd = rset_open (rset, RSETF_READ);
480 while (num_i < num && rset_read (rfd, &key, 0))
482 zint this_sys = key.mem[0];
483 if (this_sys != psysno)
488 /* determine we alreay have this in our set */
489 for (i = sort_info->num_entries; --i >= 0; )
490 if (psysno == sort_info->entries[i]->sysno)
496 assert (num_i < num);
497 if (position == positions[num_i])
499 sr[num_i].sysno = psysno;
500 yaz_log(log_level_sort, "got pos=" ZINT_FORMAT " (unsorted)", position);
501 sr[num_i].score = -1;
506 sset->cache_position = position;
507 sset->cache_psysno = psysno;
508 sset->cache_rfd = rfd;
514 void zebra_meta_records_destroy (ZebraHandle zh, ZebraMetaRecord *records,
517 assert(zh); /* compiler shut up about unused arg */
527 void resultSetInsertSort (ZebraHandle zh, ZebraSet sset,
528 struct sortKeyInfo *criteria, int num_criteria,
531 struct zset_sort_entry this_entry;
532 struct zset_sort_entry *new_entry = NULL;
533 struct zset_sort_info *sort_info = sset->sort_info;
536 sortIdx_sysno (zh->reg->sortIdx, sysno);
537 for (i = 0; i<num_criteria; i++)
539 sortIdx_type (zh->reg->sortIdx, criteria[i].attrUse);
540 sortIdx_read (zh->reg->sortIdx, this_entry.buf[i]);
542 i = sort_info->num_entries;
546 for (j = 0; j<num_criteria; j++)
548 if (criteria[j].numerical)
550 double diff = atof(this_entry.buf[j]) -
551 atof(sort_info->entries[i]->buf[j]);
560 rel = memcmp (this_entry.buf[j], sort_info->entries[i]->buf[j],
568 if (criteria[j].relation == 'A')
573 else if (criteria[j].relation == 'D')
580 j = sort_info->max_entries;
584 if (sort_info->num_entries == j)
587 j = (sort_info->num_entries)++;
588 new_entry = sort_info->entries[j];
591 sort_info->entries[j] = sort_info->entries[j-1];
594 sort_info->entries[i] = new_entry;
596 for (i = 0; i<num_criteria; i++)
597 memcpy (new_entry->buf[i], this_entry.buf[i], SORT_IDX_ENTRYSIZE);
598 new_entry->sysno = sysno;
599 new_entry->score = -1;
602 void resultSetInsertRank (ZebraHandle zh, struct zset_sort_info *sort_info,
603 zint sysno, int score, int relation)
605 struct zset_sort_entry *new_entry = NULL;
607 assert(zh); /* compiler shut up about unused arg */
609 i = sort_info->num_entries;
614 rel = score - sort_info->entries[i]->score;
621 else if (relation == 'A')
628 j = sort_info->max_entries;
632 if (sort_info->num_entries == j)
635 j = (sort_info->num_entries)++;
637 new_entry = sort_info->entries[j];
640 sort_info->entries[j] = sort_info->entries[j-1];
643 sort_info->entries[i] = new_entry;
645 new_entry->sysno = sysno;
646 new_entry->score = score;
649 ZEBRA_RES resultSetSort(ZebraHandle zh, NMEM nmem,
650 int num_input_setnames, const char **input_setnames,
651 const char *output_setname,
652 Z_SortKeySpecList *sort_sequence, int *sort_status)
657 if (num_input_setnames == 0)
659 zebra_setError(zh, YAZ_BIB1_NO_RESULT_SET_NAME_SUPPLIED_ON_SORT, 0);
662 if (num_input_setnames > 1)
664 zebra_setError(zh, YAZ_BIB1_SORT_TOO_MANY_INPUT_RESULTS, 0);
669 yaz_log(log_level_sort, "result set sort input=%s output=%s",
670 *input_setnames, output_setname);
671 sset = resultSetGet (zh, input_setnames[0]);
674 zebra_setError(zh, YAZ_BIB1_SPECIFIED_RESULT_SET_DOES_NOT_EXIST,
678 if (!(rset = sset->rset))
680 zebra_setError(zh, YAZ_BIB1_SPECIFIED_RESULT_SET_DOES_NOT_EXIST,
684 if (strcmp (output_setname, input_setnames[0]))
686 rset = rset_dup (rset);
687 sset = resultSetAdd (zh, output_setname, 1);
690 return resultSetSortSingle (zh, nmem, sset, rset, sort_sequence,
694 ZEBRA_RES resultSetSortSingle(ZebraHandle zh, NMEM nmem,
695 ZebraSet sset, RSET rset,
696 Z_SortKeySpecList *sort_sequence,
704 struct sortKeyInfo sort_criteria[3];
711 assert(nmem); /* compiler shut up about unused param */
712 sset->sort_info->num_entries = 0;
714 rset_getterms(rset, 0, 0, &n);
715 terms = (TERMID *) nmem_malloc(nmem, sizeof(*terms)*n);
716 rset_getterms(rset, terms, n, &numTerms);
719 num_criteria = sort_sequence->num_specs;
720 if (num_criteria > 3)
722 for (i = 0; i < num_criteria; i++)
724 Z_SortKeySpec *sks = sort_sequence->specs[i];
727 if (*sks->sortRelation == Z_SortKeySpec_ascending)
728 sort_criteria[i].relation = 'A';
729 else if (*sks->sortRelation == Z_SortKeySpec_descending)
730 sort_criteria[i].relation = 'D';
733 zebra_setError(zh, YAZ_BIB1_ILLEGAL_SORT_RELATION, 0);
736 if (sks->sortElement->which == Z_SortElement_databaseSpecific)
738 zebra_setError(zh, YAZ_BIB1_DATABASE_SPECIFIC_SORT_UNSUPP, 0);
741 else if (sks->sortElement->which != Z_SortElement_generic)
743 zebra_setError(zh, YAZ_BIB1_SORT_ILLEGAL_SORT, 0);
746 sk = sks->sortElement->u.generic;
749 case Z_SortKey_sortField:
750 yaz_log(log_level_sort, "key %d is of type sortField",
752 zebra_setError(zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
754 case Z_SortKey_elementSpec:
755 yaz_log(log_level_sort, "key %d is of type elementSpec",
757 zebra_setError(zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
759 case Z_SortKey_sortAttributes:
760 yaz_log(log_level_sort, "key %d is of type sortAttributes", i+1);
761 sort_criteria[i].attrUse =
762 zebra_maps_sort (zh->reg->zebra_maps,
763 sk->u.sortAttributes,
764 &sort_criteria[i].numerical);
765 yaz_log(log_level_sort, "use value = %d", sort_criteria[i].attrUse);
766 if (sort_criteria[i].attrUse == -1)
769 zh, YAZ_BIB1_USE_ATTRIBUTE_REQUIRED_BUT_NOT_SUPPLIED, 0);
772 if (sortIdx_type (zh->reg->sortIdx, sort_criteria[i].attrUse))
775 zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
781 rfd = rset_open (rset, RSETF_READ);
782 /* FIXME - pass a TERMID *, and use it for something below !! */
783 while (rset_read (rfd, &key, &termid))
785 zint this_sys = key.mem[0];
787 if (this_sys != psysno)
791 resultSetInsertSort (zh, sset,
792 sort_criteria, num_criteria, psysno);
796 yaz_log(log_level_sort, ZINT_FORMAT " keys, " ZINT_FORMAT " sysnos, sort",
798 for (i = 0; i < numTerms; i++)
799 yaz_log(log_level_sort, "term=\"%s\" type=%s count=" ZINT_FORMAT,
800 terms[i]->name, terms[i]->flags, rset_count(terms[i]->rset));
801 *sort_status = Z_SortResponse_success;
805 RSET resultSetRef (ZebraHandle zh, const char *resultSetId)
809 if ((s = resultSetGet (zh, resultSetId)))
814 ZEBRA_RES resultSetRank (ZebraHandle zh, ZebraSet zebraSet,
815 RSET rset, NMEM nmem)
825 ZebraRankClass rank_class;
826 struct rank_control *rc;
827 struct zset_sort_info *sort_info;
828 const char *rank_handler_name = res_get_def(zh->res, "rank", "rank-1");
830 zint est=-2; /* -2 not done, -1 can't do, >0 actual estimate*/
836 sort_info = zebraSet->sort_info;
837 sort_info->num_entries = 0;
839 rset_getterms(rset, 0, 0, &n);
840 yaz_log(YLOG_LOG, "Got %d terms", n);
841 terms = (TERMID *) nmem_malloc(nmem, sizeof(*terms)*n);
842 rset_getterms(rset, terms, n, &numTerms);
844 rfd = rset_open (rset, RSETF_READ);
846 rank_class = zebraRankLookup (zh, rank_handler_name);
849 yaz_log(YLOG_WARN, "No such rank handler: %s", rank_handler_name);
850 zebra_setError(zh, YAZ_BIB1_UNSUPP_SEARCH, "Cannot find rank handler");
853 rc = rank_class->control;
855 if (rset_read (rfd, &key, &termid))
857 zint psysno = key.mem[0];
860 (*rc->begin) (zh->reg, rank_class->class_handle, rset, nmem,
863 esthits = atoi(res_get_def(zh->res, "estimatehits","0"));
865 est = -1; /* can not do */
868 zint this_sys = key.mem[0]; /* FIXME - assumes scope==2 */
869 zint seqno = key.mem[key.len-1]; /* FIXME - assumes scope==2 */
871 key_logdump_txt(log_level_searchhits,&key," Got hit");
872 if (this_sys != psysno)
874 score = (*rc->calc) (handle, psysno);
876 resultSetInsertRank (zh, sort_info, psysno, score, 'A');
880 (*rc->add) (handle, CAST_ZINT_TO_INT(seqno), termid);
882 if ((est==-2) && (zebraSet->hits==esthits))
883 { /* time to estimate the hits */
884 rset_pos(rfd,&cur,&tot);
887 est = (zint)(0.5+zebraSet->hits/ratio);
888 yaz_log(log_level_searchhits, "Estimating hits (%s) "
889 "%0.1f->" ZINT_FORMAT
890 "; %0.1f->" ZINT_FORMAT,
894 i = 0; /* round to 3 significant digits */
901 zebraSet->hits = est;
905 while (rset_read (rfd, &key,&termid) && (est<0) );
906 score = (*rc->calc)(handle, psysno);
907 resultSetInsertRank(zh, sort_info, psysno, score, 'A');
908 (*rc->end) (zh->reg, handle);
912 yaz_log(log_level_searchterms, ZINT_FORMAT " keys, "
913 ZINT_FORMAT " sysnos, rank", kno, zebraSet->hits);
914 for (i = 0; i < numTerms; i++)
916 yaz_log(log_level_searchterms, "term=\"%s\" type=%s count="
918 terms[i]->name, terms[i]->flags, rset_count(terms[i]->rset));
923 ZebraRankClass zebraRankLookup (ZebraHandle zh, const char *name)
925 ZebraRankClass p = zh->reg->rank_classes;
926 while (p && strcmp (p->control->name, name))
928 if (p && !p->init_flag)
930 if (p->control->create)
931 p->class_handle = (*p->control->create)(zh);
937 void zebraRankInstall (struct zebra_register *reg, struct rank_control *ctrl)
939 ZebraRankClass p = (ZebraRankClass) xmalloc (sizeof(*p));
940 p->control = (struct rank_control *) xmalloc (sizeof(*p->control));
941 memcpy (p->control, ctrl, sizeof(*p->control));
942 p->control->name = xstrdup (ctrl->name);
944 p->next = reg->rank_classes;
945 reg->rank_classes = p;
948 void zebraRankDestroy (struct zebra_register *reg)
950 ZebraRankClass p = reg->rank_classes;
953 ZebraRankClass p_next = p->next;
954 if (p->init_flag && p->control->destroy)
955 (*p->control->destroy)(reg, p->class_handle);
956 xfree(p->control->name);
961 reg->rank_classes = NULL;