1 /* $Id: zsets.c,v 1.84 2005-05-31 07:29:10 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 {
51 NMEM rset_nmem; /* for creating the rsets in */
56 struct zset_sort_info *sort_info;
57 struct zebra_set_term_entry *term_entries;
59 struct zebra_set *next;
62 zint cache_position; /* last position */
63 RSFD cache_rfd; /* rfd (NULL if not existing) */
64 zint cache_psysno; /* sysno for last position */
67 struct zset_sort_entry {
70 char buf[ZSET_SORT_MAX_LEVEL][SORT_IDX_ENTRYSIZE];
73 struct zset_sort_info {
76 struct zset_sort_entry *all_entries;
77 struct zset_sort_entry **entries;
80 static int log_level_set=0;
81 static int log_level_sort=0;
82 static int log_level_searchhits=0;
83 static int log_level_searchterms=0;
84 static int log_level_resultsets=0;
86 static void loglevels()
90 log_level_sort = yaz_log_module_level("sorting");
91 log_level_searchhits = yaz_log_module_level("searchhits");
92 log_level_searchterms = yaz_log_module_level("searchterms");
93 log_level_resultsets = yaz_log_module_level("resultsets");
97 ZEBRA_RES resultSetSearch(ZebraHandle zh, NMEM nmem, NMEM rset_nmem,
98 Z_RPNQuery *rpn, ZebraSet sset)
102 Z_SortKeySpecList *sort_sequence;
104 ZEBRA_RES res = ZEBRA_OK;
108 sort_sequence = (Z_SortKeySpecList *)
109 nmem_malloc(nmem, sizeof(*sort_sequence));
110 sort_sequence->num_specs = 10; /* FIXME - Hard-coded number */
111 sort_sequence->specs = (Z_SortKeySpec **)
112 nmem_malloc(nmem, sort_sequence->num_specs *
113 sizeof(*sort_sequence->specs));
114 for (i = 0; i<sort_sequence->num_specs; i++)
115 sort_sequence->specs[i] = 0;
117 attrset = oid_getentbyoid (rpn->attributeSetId);
118 res = rpn_search_top(zh, rpn->RPNStructure, attrset->value,
121 sset->num_bases, sset->basenames,
128 for (i = 0; sort_sequence->specs[i]; i++)
130 sort_sequence->num_specs = i;
133 res = resultSetRank (zh, sset, rset, rset_nmem);
137 res = resultSetSortSingle (zh, nmem, sset, rset,
138 sort_sequence, &sort_status);
145 ZEBRA_RES resultSetAddRPN (ZebraHandle zh, NMEM m, Z_RPNQuery *rpn,
146 int num_bases, char **basenames,
155 zebraSet = resultSetAdd (zh, setname, 1);
158 zebraSet->locked = 1;
161 zebraSet->rset_nmem = nmem_create();
163 zebraSet->num_bases = num_bases;
164 zebraSet->basenames =
165 nmem_malloc (zebraSet->nmem, num_bases * sizeof(*zebraSet->basenames));
166 for (i = 0; i<num_bases; i++)
167 zebraSet->basenames[i] = nmem_strdup (zebraSet->nmem, basenames[i]);
169 res = resultSetSearch(zh, zebraSet->nmem, zebraSet->rset_nmem,
171 zh->hits = zebraSet->hits;
174 zebraSet->locked = 0;
180 void resultSetAddTerm (ZebraHandle zh, ZebraSet s, int reg_type,
181 const char *db, int set,
182 int use, const char *term)
184 assert(zh); /* compiler shut up */
186 s->nmem = nmem_create ();
187 if (!s->term_entries)
190 s->term_entries_max = 1000;
192 nmem_malloc (s->nmem, s->term_entries_max *
193 sizeof(*s->term_entries));
194 for (i = 0; i < s->term_entries_max; i++)
195 s->term_entries[i].term = 0;
197 if (s->hits < s->term_entries_max)
199 s->term_entries[s->hits].reg_type = reg_type;
200 s->term_entries[s->hits].db = nmem_strdup (s->nmem, db);
201 s->term_entries[s->hits].set = set;
202 s->term_entries[s->hits].use = use;
203 s->term_entries[s->hits].term = nmem_strdup (s->nmem, term);
208 ZebraSet resultSetAdd (ZebraHandle zh, const char *name, int ov)
213 for (s = zh->sets; s; s = s->next)
214 if (!strcmp (s->name, name))
221 yaz_log(log_level_resultsets, "updating result set %s", name);
222 if (!ov || s->locked)
227 rset_close(s->cache_rfd);
228 rset_delete (s->rset);
231 nmem_destroy (s->rset_nmem);
233 nmem_destroy (s->nmem);
237 const char *sort_max_str = zebra_get_resource(zh, "sortmax", "1000");
239 yaz_log(log_level_resultsets, "adding result set %s", name);
240 s = (ZebraSet) xmalloc (sizeof(*s));
243 s->name = (char *) xmalloc (strlen(name)+1);
244 strcpy (s->name, name);
246 s->sort_info = (struct zset_sort_info *)
247 xmalloc (sizeof(*s->sort_info));
248 s->sort_info->max_entries = atoi(sort_max_str);
249 if (s->sort_info->max_entries < 2)
250 s->sort_info->max_entries = 2;
252 s->sort_info->entries = (struct zset_sort_entry **)
253 xmalloc (sizeof(*s->sort_info->entries) *
254 s->sort_info->max_entries);
255 s->sort_info->all_entries = (struct zset_sort_entry *)
256 xmalloc (sizeof(*s->sort_info->all_entries) *
257 s->sort_info->max_entries);
258 for (i = 0; i < s->sort_info->max_entries; i++)
259 s->sort_info->entries[i] = s->sort_info->all_entries + i;
268 s->cache_position = 0;
273 ZebraSet resultSetGet (ZebraHandle zh, const char *name)
277 for (s = zh->sets; s; s = s->next)
278 if (!strcmp (s->name, name))
280 if (!s->term_entries && !s->rset && s->rpn)
282 NMEM nmem = nmem_create ();
283 yaz_log(log_level_resultsets, "research %s", name);
285 s->rset_nmem=nmem_create();
286 resultSetSearch(zh, nmem, s->rset_nmem, s->rpn, s);
294 void resultSetInvalidate (ZebraHandle zh)
296 ZebraSet s = zh->sets;
298 yaz_log(log_level_resultsets, "invalidating result sets");
299 for (; s; s = s->next)
304 rset_close(s->cache_rfd);
305 rset_delete (s->rset);
309 s->cache_position = 0;
311 nmem_destroy(s->rset_nmem);
316 void resultSetDestroy (ZebraHandle zh, int num, char **names,int *statuses)
318 ZebraSet * ss = &zh->sets;
322 for (i = 0; i<num; i++)
323 statuses[i] = Z_DeleteStatus_resultSetDidNotExist;
330 for (i = 0; i<num; i++)
331 if (!strcmp (s->name, names[i]))
334 statuses[i] = Z_DeleteStatus_success;
343 xfree (s->sort_info->all_entries);
344 xfree (s->sort_info->entries);
345 xfree (s->sort_info);
348 nmem_destroy (s->nmem);
352 rset_close(s->cache_rfd);
353 rset_delete (s->rset);
356 nmem_destroy(s->rset_nmem);
365 ZebraMetaRecord *zebra_meta_records_create_range(ZebraHandle zh,
370 zint *pos = pos_small;
374 if (num > 10000 || num <= 0)
378 pos = xmalloc(sizeof(*pos) * num);
380 for (i = 0; i<num; i++)
383 mr = zebra_meta_records_create(zh, name, num, pos);
390 ZebraMetaRecord *zebra_meta_records_create(ZebraHandle zh, const char *name,
391 int num, zint *positions)
394 ZebraMetaRecord *sr = 0;
397 struct zset_sort_info *sort_info;
401 if (!(sset = resultSetGet (zh, name)))
403 if (!(rset = sset->rset))
405 if (!sset->term_entries)
407 sr = (ZebraMetaRecord *) xmalloc (sizeof(*sr) * num);
408 for (i = 0; i<num; i++)
415 if (positions[i] <= sset->term_entries_max)
417 sr[i].term = sset->term_entries[positions[i]-1].term;
418 sr[i].db = sset->term_entries[positions[i]-1].db;
424 sr = (ZebraMetaRecord *) xmalloc (sizeof(*sr) * num);
425 for (i = 0; i<num; i++)
432 sort_info = sset->sort_info;
437 for (i = 0; i<num; i++)
439 position = positions[i];
440 if (position > 0 && position <= sort_info->num_entries)
442 yaz_log(log_level_sort, "got pos=" ZINT_FORMAT
443 " (sorted)", position);
444 sr[i].sysno = sort_info->entries[position-1]->sysno;
445 sr[i].score = sort_info->entries[position-1]->score;
449 /* did we really get all entries using sort ? */
450 for (i = 0; i<num; i++)
455 if (i < num) /* nope, get the rest, unsorted - sorry */
464 position = sort_info->num_entries;
465 while (num_i < num && positions[num_i] <= position)
468 if (sset->cache_rfd &&
469 num_i < num && positions[num_i] > sset->cache_position)
471 position = sset->cache_position;
472 rfd = sset->cache_rfd;
473 psysno = sset->cache_psysno;
478 rset_close(sset->cache_rfd);
479 rfd = rset_open (rset, RSETF_READ);
481 while (num_i < num && rset_read (rfd, &key, 0))
483 zint this_sys = key.mem[0];
484 if (this_sys != psysno)
489 /* determine we alreay have this in our set */
490 for (i = sort_info->num_entries; --i >= 0; )
491 if (psysno == sort_info->entries[i]->sysno)
497 assert (num_i < num);
498 if (position == positions[num_i])
500 sr[num_i].sysno = psysno;
501 yaz_log(log_level_sort, "got pos=" ZINT_FORMAT " (unsorted)", position);
502 sr[num_i].score = -1;
507 sset->cache_position = position;
508 sset->cache_psysno = psysno;
509 sset->cache_rfd = rfd;
515 void zebra_meta_records_destroy (ZebraHandle zh, ZebraMetaRecord *records,
518 assert(zh); /* compiler shut up about unused arg */
528 void resultSetInsertSort (ZebraHandle zh, ZebraSet sset,
529 struct sortKeyInfo *criteria, int num_criteria,
532 struct zset_sort_entry this_entry;
533 struct zset_sort_entry *new_entry = NULL;
534 struct zset_sort_info *sort_info = sset->sort_info;
537 sortIdx_sysno (zh->reg->sortIdx, sysno);
538 for (i = 0; i<num_criteria; i++)
540 sortIdx_type (zh->reg->sortIdx, criteria[i].attrUse);
541 sortIdx_read (zh->reg->sortIdx, this_entry.buf[i]);
543 i = sort_info->num_entries;
547 for (j = 0; j<num_criteria; j++)
549 if (criteria[j].numerical)
551 double diff = atof(this_entry.buf[j]) -
552 atof(sort_info->entries[i]->buf[j]);
561 rel = memcmp (this_entry.buf[j], sort_info->entries[i]->buf[j],
569 if (criteria[j].relation == 'A')
574 else if (criteria[j].relation == 'D')
581 j = sort_info->max_entries;
585 if (sort_info->num_entries == j)
588 j = (sort_info->num_entries)++;
589 new_entry = sort_info->entries[j];
592 sort_info->entries[j] = sort_info->entries[j-1];
595 sort_info->entries[i] = new_entry;
597 for (i = 0; i<num_criteria; i++)
598 memcpy (new_entry->buf[i], this_entry.buf[i], SORT_IDX_ENTRYSIZE);
599 new_entry->sysno = sysno;
600 new_entry->score = -1;
603 void resultSetInsertRank (ZebraHandle zh, struct zset_sort_info *sort_info,
604 zint sysno, int score, int relation)
606 struct zset_sort_entry *new_entry = NULL;
608 assert(zh); /* compiler shut up about unused arg */
610 i = sort_info->num_entries;
615 rel = score - sort_info->entries[i]->score;
622 else if (relation == 'A')
629 j = sort_info->max_entries;
633 if (sort_info->num_entries == j)
636 j = (sort_info->num_entries)++;
638 new_entry = sort_info->entries[j];
641 sort_info->entries[j] = sort_info->entries[j-1];
644 sort_info->entries[i] = new_entry;
646 new_entry->sysno = sysno;
647 new_entry->score = score;
650 ZEBRA_RES resultSetSort(ZebraHandle zh, NMEM nmem,
651 int num_input_setnames, const char **input_setnames,
652 const char *output_setname,
653 Z_SortKeySpecList *sort_sequence, int *sort_status)
658 if (num_input_setnames == 0)
660 zebra_setError(zh, YAZ_BIB1_NO_RESULT_SET_NAME_SUPPLIED_ON_SORT, 0);
663 if (num_input_setnames > 1)
665 zebra_setError(zh, YAZ_BIB1_SORT_TOO_MANY_INPUT_RESULTS, 0);
670 yaz_log(log_level_sort, "result set sort input=%s output=%s",
671 *input_setnames, output_setname);
672 sset = resultSetGet (zh, input_setnames[0]);
675 zebra_setError(zh, YAZ_BIB1_SPECIFIED_RESULT_SET_DOES_NOT_EXIST,
679 if (!(rset = sset->rset))
681 zebra_setError(zh, YAZ_BIB1_SPECIFIED_RESULT_SET_DOES_NOT_EXIST,
685 if (strcmp (output_setname, input_setnames[0]))
687 rset = rset_dup (rset);
688 sset = resultSetAdd (zh, output_setname, 1);
691 return resultSetSortSingle (zh, nmem, sset, rset, sort_sequence,
695 ZEBRA_RES resultSetSortSingle(ZebraHandle zh, NMEM nmem,
696 ZebraSet sset, RSET rset,
697 Z_SortKeySpecList *sort_sequence,
705 struct sortKeyInfo sort_criteria[3];
712 assert(nmem); /* compiler shut up about unused param */
713 sset->sort_info->num_entries = 0;
715 rset_getterms(rset, 0, 0, &n);
716 terms = (TERMID *) nmem_malloc(nmem, sizeof(*terms)*n);
717 rset_getterms(rset, terms, n, &numTerms);
720 num_criteria = sort_sequence->num_specs;
721 if (num_criteria > 3)
723 for (i = 0; i < num_criteria; i++)
725 Z_SortKeySpec *sks = sort_sequence->specs[i];
728 if (*sks->sortRelation == Z_SortKeySpec_ascending)
729 sort_criteria[i].relation = 'A';
730 else if (*sks->sortRelation == Z_SortKeySpec_descending)
731 sort_criteria[i].relation = 'D';
734 zebra_setError(zh, YAZ_BIB1_ILLEGAL_SORT_RELATION, 0);
737 if (sks->sortElement->which == Z_SortElement_databaseSpecific)
739 zebra_setError(zh, YAZ_BIB1_DATABASE_SPECIFIC_SORT_UNSUPP, 0);
742 else if (sks->sortElement->which != Z_SortElement_generic)
744 zebra_setError(zh, YAZ_BIB1_SORT_ILLEGAL_SORT, 0);
747 sk = sks->sortElement->u.generic;
750 case Z_SortKey_sortField:
751 yaz_log(log_level_sort, "key %d is of type sortField",
753 zebra_setError(zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
755 case Z_SortKey_elementSpec:
756 yaz_log(log_level_sort, "key %d is of type elementSpec",
758 zebra_setError(zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
760 case Z_SortKey_sortAttributes:
761 yaz_log(log_level_sort, "key %d is of type sortAttributes", i+1);
762 sort_criteria[i].attrUse =
763 zebra_maps_sort (zh->reg->zebra_maps,
764 sk->u.sortAttributes,
765 &sort_criteria[i].numerical);
766 yaz_log(log_level_sort, "use value = %d", sort_criteria[i].attrUse);
767 if (sort_criteria[i].attrUse == -1)
770 zh, YAZ_BIB1_USE_ATTRIBUTE_REQUIRED_BUT_NOT_SUPPLIED, 0);
773 if (sortIdx_type (zh->reg->sortIdx, sort_criteria[i].attrUse))
776 zh, YAZ_BIB1_CANNOT_SORT_ACCORDING_TO_SEQUENCE, 0);
782 rfd = rset_open (rset, RSETF_READ);
783 while (rset_read (rfd, &key, &termid))
785 zint this_sys = key.mem[0];
786 if (log_level_searchhits)
787 key_logdump_txt(log_level_searchhits, &key, termid->name);
789 if (this_sys != psysno)
793 resultSetInsertSort (zh, sset,
794 sort_criteria, num_criteria, psysno);
798 yaz_log(log_level_sort, ZINT_FORMAT " keys, " ZINT_FORMAT " sysnos, sort",
800 for (i = 0; i < numTerms; i++)
801 yaz_log(log_level_sort, "term=\"%s\" type=%s count=" ZINT_FORMAT,
802 terms[i]->name, terms[i]->flags, terms[i]->rset->hits_count);
803 *sort_status = Z_SortResponse_success;
807 RSET resultSetRef(ZebraHandle zh, const char *resultSetId)
811 if ((s = resultSetGet (zh, resultSetId)))
816 ZEBRA_RES resultSetRank(ZebraHandle zh, ZebraSet zebraSet,
817 RSET rset, NMEM nmem)
826 ZebraRankClass rank_class;
827 struct zset_sort_info *sort_info;
828 const char *rank_handler_name = res_get_def(zh->res, "rank", "rank-1");
832 sort_info = zebraSet->sort_info;
833 sort_info->num_entries = 0;
835 rset_getterms(rset, 0, 0, &n);
836 terms = (TERMID *) nmem_malloc(nmem, sizeof(*terms)*n);
837 rset_getterms(rset, terms, n, &numTerms);
839 rank_class = zebraRankLookup(zh, rank_handler_name);
842 yaz_log(YLOG_WARN, "No such rank handler: %s", rank_handler_name);
843 zebra_setError(zh, YAZ_BIB1_UNSUPP_SEARCH, "Cannot find rank handler");
848 RSFD rfd = rset_open(rset, RSETF_READ);
849 struct rank_control *rc = rank_class->control;
853 (*rc->begin) (zh->reg, rank_class->class_handle, rset, nmem,
856 while (rset_read(rfd, &key, &termid))
858 zint this_sys = key.mem[0];
859 zint seqno = key.mem[key.len-1];
861 if (log_level_searchhits)
862 key_logdump_txt(log_level_searchhits, &key, termid->name);
863 if (this_sys != psysno)
865 if (rfd->counted_items >= rset->hits_limit)
869 score = (*rc->calc) (handle, psysno);
870 resultSetInsertRank (zh, sort_info, psysno, score, 'A');
874 (*rc->add) (handle, CAST_ZINT_TO_INT(seqno), termid);
878 score = (*rc->calc)(handle, psysno);
879 resultSetInsertRank(zh, sort_info, psysno, score, 'A');
881 (*rc->end) (zh->reg, handle);
884 zebraSet->hits = rset->hits_count;
886 yaz_log(log_level_searchterms, ZINT_FORMAT " keys, "
887 ZINT_FORMAT " sysnos, rank", kno, zebraSet->hits);
888 for (i = 0; i < numTerms; i++)
890 yaz_log(log_level_searchterms, "term=\"%s\" type=%s count="
892 terms[i]->name, terms[i]->flags, terms[i]->rset->hits_count);
897 ZebraRankClass zebraRankLookup(ZebraHandle zh, const char *name)
899 ZebraRankClass p = zh->reg->rank_classes;
900 while (p && strcmp (p->control->name, name))
902 if (p && !p->init_flag)
904 if (p->control->create)
905 p->class_handle = (*p->control->create)(zh);
911 void zebraRankInstall(struct zebra_register *reg, struct rank_control *ctrl)
913 ZebraRankClass p = (ZebraRankClass) xmalloc (sizeof(*p));
914 p->control = (struct rank_control *) xmalloc (sizeof(*p->control));
915 memcpy (p->control, ctrl, sizeof(*p->control));
916 p->control->name = xstrdup (ctrl->name);
918 p->next = reg->rank_classes;
919 reg->rank_classes = p;
922 void zebraRankDestroy(struct zebra_register *reg)
924 ZebraRankClass p = reg->rank_classes;
927 ZebraRankClass p_next = p->next;
928 if (p->init_flag && p->control->destroy)
929 (*p->control->destroy)(reg, p->class_handle);
930 xfree(p->control->name);
935 reg->rank_classes = NULL;
938 static int trav_rset_for_termids(RSET rset, TERMID *termid_array,
939 zint *hits_array, int *approx_array)
943 for (i = 0; i<rset->no_children; i++)
944 no += trav_rset_for_termids(rset->children[i],
945 (termid_array ? termid_array + no : 0),
946 (hits_array ? hits_array + no : 0),
947 (approx_array ? approx_array + no : 0));
951 termid_array[no] = rset->term;
953 hits_array[no] = rset->hits_count;
955 approx_array[no] = rset->hits_approx;
957 yaz_log(YLOG_LOG, "rset=%p term=%s count=" ZINT_FORMAT,
958 rset, rset->term->name, rset->hits_count);
965 ZEBRA_RES zebra_result_set_term_no(ZebraHandle zh, const char *setname,
968 ZebraSet sset = resultSetGet(zh, setname);
972 *num_terms = trav_rset_for_termids(sset->rset, 0, 0, 0);
978 ZEBRA_RES zebra_result_set_term_info(ZebraHandle zh, const char *setname,
979 int no, zint *count, int *approx,
980 char *termbuf, size_t *termlen)
982 ZebraSet sset = resultSetGet(zh, setname);
985 int num_terms = trav_rset_for_termids(sset->rset, 0, 0, 0);
986 if (no >= 0 && no < num_terms)
988 TERMID *term_array = xmalloc(num_terms * sizeof(*term_array));
989 zint *hits_array = xmalloc(num_terms * sizeof(*hits_array));
990 int *approx_array = xmalloc(num_terms * sizeof(*approx_array));
992 trav_rset_for_termids(sset->rset, term_array,
993 hits_array, approx_array);
996 *count = hits_array[no];
998 *approx = approx_array[no];
1001 char *inbuf = term_array[no]->name;
1002 size_t inleft = strlen(inbuf);
1003 size_t outleft = *termlen - 1;
1005 if (zh->iconv_from_utf8 != 0)
1007 char *outbuf = termbuf;
1010 ret = yaz_iconv(zh->iconv_from_utf8, &inbuf, &inleft,
1012 if (ret == (size_t)(-1))
1015 *termlen = outbuf - termbuf;
1019 if (inleft > outleft)
1022 memcpy(termbuf, inbuf, *termlen);
1024 termbuf[*termlen] = '\0';
1029 xfree(approx_array);