817c1339f988ff26b54be4b4ddc756b976cce81d
[pazpar2-moved-to-github.git] / src / reclists.c
1 /* This file is part of Pazpar2.
2    Copyright (C) 2006-2013 Index Data
3
4 Pazpar2 is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Pazpar2 is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20 #include <assert.h>
21
22 #if HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <yaz/yaz-util.h>
27
28 #include "ppmutex.h"
29 #include "session.h"
30 #include "reclists.h"
31 #include "jenkins_hash.h"
32
33 struct reclist
34 {
35     struct reclist_bucket **hashtable;
36     unsigned hash_size;
37
38     int num_records;
39     struct record_cluster *sorted_list;
40     struct record_cluster *sorted_ptr;
41     NMEM nmem;
42     YAZ_MUTEX mutex;
43 };
44
45 struct reclist_bucket
46 {
47     struct record_cluster *record;
48     struct reclist_bucket *hash_next;
49 };
50
51 static void append_merge_keys(struct record_metadata_attr **p,
52                               const struct record_metadata_attr *a,
53                               NMEM nmem)
54 {
55     for (; a; a = a->next)
56     {
57         struct record_metadata_attr **pi = p;
58         for (; *pi; pi = &(*pi)->next)
59             if (!strcmp((*pi)->value, a->value))
60                 break;
61         if (!*pi)
62         {
63             *pi = (struct record_metadata_attr *) nmem_malloc(nmem, sizeof(**p));
64             (*pi)->name = nmem_strdup_null(nmem, a->name);
65             (*pi)->value = nmem_strdup_null(nmem, a->value);
66             (*pi)->next = 0;
67         }
68     }
69 }
70
71 struct reclist_sortparms *reclist_parse_sortparms(NMEM nmem, const char *parms,
72                                                   struct conf_service *service)
73 {
74     struct reclist_sortparms *res = 0;
75     struct reclist_sortparms **rp = &res;
76
77     if (strlen(parms) > 256)
78         return 0;
79     while (*parms)
80     {
81         char parm[256];
82         char *pp;
83         const char *cpp;
84         int increasing = 0;
85         int i;
86         int offset = 0;
87         enum conf_metadata_type type = Metadata_type_generic;
88         struct reclist_sortparms *new;
89
90         if (!(cpp = strchr(parms, ',')))
91             cpp = parms + strlen(parms);
92         strncpy(parm, parms, cpp - parms);
93         parm[cpp-parms] = '\0';
94
95         if ((pp = strchr(parm, ':')))
96         {
97             if (pp[1] == '1')
98                 increasing = 1;
99             else if (pp[1] == '0')
100                 increasing = 0;
101             else
102             {
103                 yaz_log(YLOG_FATAL, "Bad sortkey modifier: %s", parm);
104                 return 0;
105             }
106
107             if (pp[2])
108             {
109                 if (pp[2] == 'p')
110                     type = Metadata_type_position;
111                 else
112                     yaz_log(YLOG_FATAL, "Bad sortkey modifier: %s", parm);
113             }
114             *pp = '\0';
115         }
116         if (type != Metadata_type_position)
117         {
118             if (!strcmp(parm, "relevance"))
119             {
120                 type = Metadata_type_relevance;
121             }
122             else if (!strcmp(parm, "position"))
123             {
124                 type = Metadata_type_position;
125             }
126             else
127             {
128                 for (i = 0; i < service->num_sortkeys; i++)
129                 {
130                     struct conf_sortkey *sk = &service->sortkeys[i];
131                     if (!strcmp(sk->name, parm))
132                     {
133                         type = sk->type;
134                         break;
135                     }
136                 }
137                 if (i >= service->num_sortkeys)
138                 {
139                     yaz_log(YLOG_FATAL, "Sortkey not defined in service: %s",
140                             parm);
141                     return 0;
142                 }
143                 offset = i;
144             }
145         }
146         new = *rp = nmem_malloc(nmem, sizeof(struct reclist_sortparms));
147         new->next = 0;
148         new->offset = offset;
149         new->type = type;
150         new->increasing = increasing;
151         new->name = nmem_strdup(nmem, parm);
152         rp = &new->next;
153         if (*(parms = cpp))
154             parms++;
155     }
156     return res;
157 }
158
159 static int reclist_cmp(const void *p1, const void *p2)
160 {
161     struct record_cluster *r1 = (*(struct record_cluster**) p1);
162     struct record_cluster *r2 = (*(struct record_cluster**) p2);
163     struct reclist_sortparms *sortparms = r1->sort_parms;
164     struct reclist_sortparms *s;
165     int res = 0;
166
167     for (s = sortparms; s && res == 0; s = s->next)
168     {
169         union data_types *ut1 = r1->sortkeys[s->offset];
170         union data_types *ut2 = r2->sortkeys[s->offset];
171         const char *s1, *s2;
172         switch (s->type)
173         {
174         case Metadata_type_relevance:
175             res = r1->relevance_score - r2->relevance_score;
176             break;
177         case Metadata_type_generic:
178         case Metadata_type_skiparticle:
179             s1 = ut1 ? ut1->text.sort : "";
180             s2 = ut2 ? ut2->text.sort : "";
181             res = strcmp(s1, s2);
182             break;
183         case Metadata_type_year:
184         case Metadata_type_date:
185             if (ut1 && ut2)
186             {
187                 if (s->increasing)
188                     res = ut1->number.min  - ut2->number.min;
189                 else
190                     res = ut1->number.max  - ut2->number.max;
191             }
192             else if (ut1 && !ut2)
193             {
194                 res = -1; /* without date/year: last! */
195                 continue;
196             }
197             else if (!ut1 && ut2)
198             {
199                 res = 1; /* without date/year: last! */
200                 continue;
201             }
202             else
203                 res = 0;
204             break;
205         case Metadata_type_position:
206             if (r1->records && r2->records)
207             {
208                 int pos1 = 0, pos2 = 0;
209                 struct record *rec;
210                 for (rec = r1->records; rec; rec = rec->next)
211                     if (pos1 == 0 || rec->position < pos1)
212                         pos1 = rec->position;
213                 for (rec = r2->records; rec; rec = rec->next)
214                     if (pos2 == 0 || rec->position < pos2)
215                         pos2 = rec->position;
216                 res = pos1 - pos2;
217                 continue;
218             }
219             break;
220         case Metadata_type_float:
221             if (ut1 && ut2)
222             {
223                 if (ut1->fnumber == ut2->fnumber)
224                     res = 0;
225                 else if (ut1->fnumber > ut2->fnumber)
226                     res = 1;
227                 else
228                     res = -1;
229             }
230             else if (ut1)
231                 res = 1;
232             else if (ut2)
233                 res = -1;
234             else
235                 res = 0;
236             break;
237         }
238         if (res && !s->increasing)
239             res *= -1;
240     }
241     if (res == 0)
242         res = strcmp(r1->recid, r2->recid);
243     return res;
244 }
245
246 void reclist_limit(struct reclist *l, struct session *se, int lazy)
247 {
248     unsigned i;
249     int num = 0;
250     struct record_cluster **pp = &l->sorted_list;
251
252     reclist_enter(l);
253
254     if (!lazy || !*pp)
255     {
256         for (i = 0; i < l->hash_size; i++)
257         {
258             struct reclist_bucket *p;
259             for (p = l->hashtable[i]; p; p = p->hash_next)
260                 p->record->sorted_next = 0;
261         }
262         for (i = 0; i < l->hash_size; i++)
263         {
264             struct reclist_bucket *p;
265             for (p = l->hashtable[i]; p; p = p->hash_next)
266             {
267                 if (session_check_cluster_limit(se, p->record))
268                 {
269                     if (!p->record->sorted_next)
270                     {
271                         *pp = p->record;
272                         pp = &p->record->sorted_next;
273                         *pp = p->record; /* signal already in use */
274                         num++;
275                     }
276                 }
277             }
278         }
279         *pp = 0;
280     }
281     l->num_records = num;
282     reclist_leave(l);
283 }
284
285 void reclist_sort(struct reclist *l, struct reclist_sortparms *parms)
286 {
287     struct record_cluster **flatlist = xmalloc(sizeof(*flatlist) * l->num_records);
288     struct record_cluster *ptr;
289     struct record_cluster **prev;
290     int i = 0;
291
292     reclist_enter(l);
293
294     ptr = l->sorted_list;
295     prev = &l->sorted_list;
296     while (ptr)
297     {
298         ptr->sort_parms = parms;
299         flatlist[i] = ptr;
300         ptr = ptr->sorted_next;
301         i++;
302     }
303     assert(i == l->num_records);
304
305     qsort(flatlist, l->num_records, sizeof(*flatlist), reclist_cmp);
306     for (i = 0; i < l->num_records; i++)
307     {
308         *prev = flatlist[i];
309         prev = &flatlist[i]->sorted_next;
310     }
311     *prev = 0;
312
313     xfree(flatlist);
314
315     reclist_leave(l);
316 }
317
318 struct record_cluster *reclist_read_record(struct reclist *l)
319 {
320     if (l && l->sorted_ptr)
321     {
322         struct record_cluster *t = l->sorted_ptr;
323         l->sorted_ptr = l->sorted_ptr->sorted_next;
324         return t;
325     }
326     else
327         return 0;
328 }
329
330 void reclist_enter(struct reclist *l)
331 {
332     yaz_mutex_enter(l->mutex);
333     if (l)
334         l->sorted_ptr = l->sorted_list;
335 }
336
337
338 void reclist_leave(struct reclist *l)
339 {
340     yaz_mutex_leave(l->mutex);
341     if (l)
342         l->sorted_ptr = l->sorted_list;
343 }
344
345
346 struct reclist *reclist_create(NMEM nmem)
347 {
348     struct reclist *res = nmem_malloc(nmem, sizeof(struct reclist));
349     res->hash_size = 399;
350     res->hashtable
351         = nmem_malloc(nmem, res->hash_size * sizeof(struct reclist_bucket*));
352     memset(res->hashtable, 0, res->hash_size * sizeof(struct reclist_bucket*));
353     res->nmem = nmem;
354
355     res->sorted_ptr = 0;
356     res->sorted_list = 0;
357
358     res->num_records = 0;
359     res->mutex = 0;
360     pazpar2_mutex_create(&res->mutex, "reclist");
361     return res;
362 }
363
364 void reclist_destroy(struct reclist *l)
365 {
366     if (l)
367     {
368         unsigned i;
369         for (i = 0; i < l->hash_size; i++)
370         {
371             struct reclist_bucket *p;
372             for (p = l->hashtable[i]; p; p = p->hash_next)
373             {
374                 wrbuf_destroy(p->record->relevance_explain1);
375                 wrbuf_destroy(p->record->relevance_explain2);
376                 p->record->relevance_explain1 = 0;
377                 p->record->relevance_explain2 = 0;
378             }
379         }
380         yaz_mutex_destroy(&l->mutex);
381     }
382 }
383
384 int reclist_get_num_records(struct reclist *l)
385 {
386     if (l)
387         return l->num_records;
388     return 0;
389 }
390
391 static void merge_cluster(struct reclist *l,
392                           struct relevance *r,
393                           struct record_cluster *dst,
394                           struct record_cluster *src)
395 {
396     struct record_metadata_attr *mkl;
397     struct record **rp = &dst->records;
398     for (; *rp; rp = &(*rp)->next)
399         ;
400     *rp = src->records;
401
402     for (mkl = src->merge_keys; mkl; mkl = mkl->next)
403     {
404         const char *merge_key = mkl->value;
405         unsigned int bucket =
406             jenkins_hash((unsigned char*) merge_key) % l->hash_size;
407         struct reclist_bucket *p;
408
409         for (p = l->hashtable[bucket]; p; p = p->hash_next)
410             if (p->record == src)
411                 p->record = dst;
412     }
413
414     /* not merging metadata and sortkeys yet */
415
416     relevance_mergerec(r, dst, src);
417
418     wrbuf_puts(dst->relevance_explain1, wrbuf_cstr(src->relevance_explain1));
419     wrbuf_puts(dst->relevance_explain2, wrbuf_cstr(src->relevance_explain2));
420
421     wrbuf_destroy(src->relevance_explain1);
422     src->relevance_explain1 = 0;
423     wrbuf_destroy(src->relevance_explain2);
424     src->relevance_explain2 = 0;
425
426     append_merge_keys(&dst->merge_keys, src->merge_keys, l->nmem);
427 }
428
429 static struct record_cluster *new_cluster(
430     struct reclist *l,
431     struct relevance *r,
432     struct conf_service *service,
433     struct record *record,
434     struct record_metadata_attr *merge_keys
435     )
436 {
437     struct record_cluster *cluster;
438     cluster = nmem_malloc(l->nmem, sizeof(*cluster));
439
440     record->next = 0;
441     cluster->records = record;
442     cluster->merge_keys = 0;
443     append_merge_keys(&cluster->merge_keys, merge_keys, l->nmem);
444     cluster->relevance_score = 0;
445     cluster->recid = cluster->merge_keys->value;
446     cluster->metadata =
447         nmem_malloc(l->nmem,
448                     sizeof(struct record_metadata*) * service->num_metadata);
449     memset(cluster->metadata, 0,
450            sizeof(struct record_metadata*) * service->num_metadata);
451     cluster->sortkeys =
452         nmem_malloc(l->nmem, sizeof(struct record_metadata*) * service->num_sortkeys);
453     memset(cluster->sortkeys, 0,
454            sizeof(union data_types*) * service->num_sortkeys);
455     relevance_newrec(r, cluster);
456     cluster->relevance_explain1 = wrbuf_alloc();
457     cluster->relevance_explain2 = wrbuf_alloc();
458     /* attach to hash list */
459     l->num_records++;
460     l->sorted_list = l->sorted_ptr = 0;
461     return cluster;
462 }
463
464 // Insert a record. Return record cluster (newly formed or pre-existing)
465 struct record_cluster *reclist_insert(struct reclist *l,
466                                       struct relevance *r,
467                                       struct conf_service *service,
468                                       struct record *record,
469                                       struct record_metadata_attr *merge_keys,
470                                       int *total)
471 {
472     struct record_cluster *cluster = 0;
473     struct record_metadata_attr *mkl = merge_keys;
474
475     assert(service);
476     assert(l);
477     assert(record);
478     assert(merge_keys);
479     assert(total);
480
481     yaz_mutex_enter(l->mutex);
482
483     for (; mkl; mkl = mkl->next)
484     {
485         const char *merge_key = mkl->value;
486         unsigned int bucket =
487             jenkins_hash((unsigned char*) merge_key) % l->hash_size;
488         struct reclist_bucket **p;
489         struct reclist_bucket *rb = 0;
490
491         for (p = &l->hashtable[bucket]; *p; p = &(*p)->hash_next)
492         {
493             struct record_metadata_attr *mkr = (*p)->record->merge_keys;
494             for (; mkr; mkr = mkr->next)
495             {
496                 // We found a matching record. Merge them
497                 if (!strcmp(merge_key, mkr->value))
498                 {
499                     rb = *p;
500                     if (!cluster)
501                     {
502                         struct record **re;
503                         for (re = &rb->record->records; *re; re = &(*re)->next)
504                         {
505                             if ((*re)->client == record->client &&
506                                 record_compare(record, *re, service))
507                             {
508                                 yaz_mutex_leave(l->mutex);
509                                 return 0;
510                             }
511                         }
512                         cluster = rb->record;
513                         *re = record;
514                         record->next = 0;
515                     }
516                     else
517                     {
518                         if (cluster != rb->record)
519                         {
520                             assert(rb->record->relevance_explain1);
521                             merge_cluster(l, r, cluster, rb->record);
522                             (*total)--;
523                         }
524                     }
525                 }
526             }
527         }
528         if (!cluster)
529         {
530             (*total)++;
531             cluster = new_cluster(l, r, service, record, merge_keys);
532         }
533
534         if (!rb)
535         {
536             rb = nmem_malloc(l->nmem, sizeof(*rb));
537             rb->record = cluster;
538             rb->hash_next = 0;
539
540             *p = rb;
541         }
542     }
543     yaz_mutex_leave(l->mutex);
544     return cluster;
545 }
546
547 int reclist_sortparms_cmp(struct reclist_sortparms *sort1, struct reclist_sortparms *sort2)
548 {
549     int rc;
550     if (sort1 == sort2)
551         return 0;
552     if (sort1 == 0 || sort2 == 0)
553         return 1;
554     rc = strcmp(sort1->name, sort2->name) || sort1->increasing != sort2->increasing || sort1->type != sort2->type;
555     return rc;
556 }
557 /*
558  * Local variables:
559  * c-basic-offset: 4
560  * c-file-style: "Stroustrup"
561  * indent-tabs-mode: nil
562  * End:
563  * vim: shiftwidth=4 tabstop=8 expandtab
564  */
565