src/reclists.c

   1 /* This file is part of Pazpar2.
   2    Copyright (C) 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 if (!strcmp(parm, "retrieval"))
 127             {
 128                 type = Metadata_type_retrieval;
 129             }
 130             else if (service)
 131             {
 132                 for (i = 0; i < service->num_sortkeys; i++)
 133                 {
 134                     struct conf_sortkey *sk = &service->sortkeys[i];
 135                     if (!strcmp(sk->name, parm))
 136                     {
 137                         type = sk->type;
 138                         break;
 139                     }
 140                 }
 141                 if (i >= service->num_sortkeys)
 142                 {
 143                     yaz_log(YLOG_FATAL, "Sortkey not defined in service: %s",
 144                             parm);
 145                     return 0;
 146                 }
 147                 offset = i;
 148             }
 149             else
 150             {
 151                 yaz_log(YLOG_FATAL, "Sortkey not defined in service: %s",
 152                         parm);
 153                 return 0;
 154             }
 155         }
 156         new = *rp = nmem_malloc(nmem, sizeof(struct reclist_sortparms));
 157         new->next = 0;
 158         new->offset = offset;
 159         new->type = type;
 160         new->increasing = increasing;
 161         new->name = nmem_strdup(nmem, parm);
 162         rp = &new->next;
 163         if (*(parms = cpp))
 164             parms++;
 165     }
 166     return res;
 167 }
 168
 169 static int reclist_cmp(const void *p1, const void *p2)
 170 {
 171     struct record_cluster *r1 = (*(struct record_cluster**) p1);
 172     struct record_cluster *r2 = (*(struct record_cluster**) p2);
 173     struct reclist_sortparms *sortparms = r1->sort_parms;
 174     struct reclist_sortparms *s;
 175     int res = 0;
 176
 177     for (s = sortparms; s && res == 0; s = s->next)
 178     {
 179         union data_types *ut1 = r1->sortkeys[s->offset];
 180         union data_types *ut2 = r2->sortkeys[s->offset];
 181         const char *s1, *s2;
 182         switch (s->type)
 183         {
 184         case Metadata_type_relevance:
 185             res = r1->relevance_score - r2->relevance_score;
 186             break;
 187         case Metadata_type_generic:
 188         case Metadata_type_skiparticle:
 189             s1 = ut1 ? ut1->text.sort : "";
 190             s2 = ut2 ? ut2->text.sort : "";
 191             res = strcmp(s1, s2);
 192             break;
 193         case Metadata_type_year:
 194         case Metadata_type_date:
 195             if (ut1 && ut2)
 196             {
 197                 if (s->increasing)
 198                     res = ut1->number.min  - ut2->number.min;
 199                 else
 200                     res = ut1->number.max  - ut2->number.max;
 201             }
 202             else if (ut1 && !ut2)
 203             {
 204                 res = -1; /* without date/year: last! */
 205                 continue;
 206             }
 207             else if (!ut1 && ut2)
 208             {
 209                 res = 1; /* without date/year: last! */
 210                 continue;
 211             }
 212             else
 213                 res = 0;
 214             break;
 215         case Metadata_type_position:
 216             if (r1->records && r2->records)
 217             {
 218                 int pos1 = 0, pos2 = 0;
 219                 struct record *rec;
 220                 for (rec = r1->records; rec; rec = rec->next)
 221                     if (pos1 == 0 || rec->position < pos1)
 222                         pos1 = rec->position;
 223                 for (rec = r2->records; rec; rec = rec->next)
 224                     if (pos2 == 0 || rec->position < pos2)
 225                         pos2 = rec->position;
 226                 res = pos1 - pos2;
 227                 continue;
 228             }
 229             break;
 230         case Metadata_type_float:
 231             if (ut1 && ut2)
 232             {
 233                 if (ut1->fnumber == ut2->fnumber)
 234                     res = 0;
 235                 else if (ut1->fnumber > ut2->fnumber)
 236                     res = 1;
 237                 else
 238                     res = -1;
 239             }
 240             else if (ut1)
 241                 res = 1;
 242             else if (ut2)
 243                 res = -1;
 244             else
 245                 res = 0;
 246             break;
 247         case Metadata_type_retrieval:
 248             res = r1->retrieval_position - r2->retrieval_position;
 249             break;
 250         }
 251         if (res && !s->increasing)
 252             res *= -1;
 253     }
 254     if (res == 0)
 255         res = strcmp(r1->recid, r2->recid);
 256     return res;
 257 }
 258
 259 void reclist_limit(struct reclist *l, struct session *se, int lazy)
 260 {
 261     unsigned i;
 262     int num = 0;
 263     struct record_cluster **pp = &l->sorted_list;
 264
 265     reclist_enter(l);
 266
 267     if (!lazy || !*pp)
 268     {
 269         for (i = 0; i < l->hash_size; i++)
 270         {
 271             struct reclist_bucket *p;
 272             for (p = l->hashtable[i]; p; p = p->hash_next)
 273                 p->record->sorted_next = 0;
 274         }
 275         for (i = 0; i < l->hash_size; i++)
 276         {
 277             struct reclist_bucket *p;
 278             for (p = l->hashtable[i]; p; p = p->hash_next)
 279             {
 280                 if (session_check_cluster_limit(se, p->record))
 281                 {
 282                     if (!p->record->sorted_next)
 283                     {
 284                         *pp = p->record;
 285                         pp = &p->record->sorted_next;
 286                         *pp = p->record; /* signal already in use */
 287                         num++;
 288                     }
 289                 }
 290             }
 291         }
 292         *pp = 0;
 293     }
 294     l->num_records = num;
 295     reclist_leave(l);
 296 }
 297
 298 void reclist_sort(struct reclist *l, struct reclist_sortparms *parms)
 299 {
 300     struct record_cluster **flatlist = xmalloc(sizeof(*flatlist) * l->num_records);
 301     struct record_cluster *ptr;
 302     struct record_cluster **prev;
 303     int i = 0;
 304
 305     reclist_enter(l);
 306
 307     ptr = l->sorted_list;
 308     prev = &l->sorted_list;
 309     while (ptr)
 310     {
 311         ptr->sort_parms = parms;
 312         flatlist[i] = ptr;
 313         ptr = ptr->sorted_next;
 314         i++;
 315     }
 316     assert(i == l->num_records);
 317
 318     qsort(flatlist, l->num_records, sizeof(*flatlist), reclist_cmp);
 319     for (i = 0; i < l->num_records; i++)
 320     {
 321         *prev = flatlist[i];
 322         prev = &flatlist[i]->sorted_next;
 323     }
 324     *prev = 0;
 325
 326     xfree(flatlist);
 327
 328     reclist_leave(l);
 329 }
 330
 331 struct record_cluster *reclist_read_record(struct reclist *l)
 332 {
 333     if (l && l->sorted_ptr)
 334     {
 335         struct record_cluster *t = l->sorted_ptr;
 336         l->sorted_ptr = l->sorted_ptr->sorted_next;
 337         return t;
 338     }
 339     else
 340         return 0;
 341 }
 342
 343 void reclist_enter(struct reclist *l)
 344 {
 345     yaz_mutex_enter(l->mutex);
 346     l->sorted_ptr = l->sorted_list;
 347 }
 348
 349
 350 void reclist_leave(struct reclist *l)
 351 {
 352     yaz_mutex_leave(l->mutex);
 353     l->sorted_ptr = l->sorted_list;
 354 }
 355
 356 void reclist_rewind(struct reclist *l)
 357 {
 358     l->sorted_ptr = l->sorted_list;
 359 }
 360
 361
 362 struct reclist *reclist_create(NMEM nmem)
 363 {
 364     struct reclist *res = nmem_malloc(nmem, sizeof(struct reclist));
 365     res->hash_size = 399;
 366     res->hashtable
 367         = nmem_malloc(nmem, res->hash_size * sizeof(struct reclist_bucket*));
 368     memset(res->hashtable, 0, res->hash_size * sizeof(struct reclist_bucket*));
 369     res->nmem = nmem;
 370
 371     res->sorted_ptr = 0;
 372     res->sorted_list = 0;
 373
 374     res->num_records = 0;
 375     res->mutex = 0;
 376     pazpar2_mutex_create(&res->mutex, "reclist");
 377     return res;
 378 }
 379
 380 void reclist_destroy(struct reclist *l)
 381 {
 382     if (l)
 383     {
 384         unsigned i;
 385         for (i = 0; i < l->hash_size; i++)
 386         {
 387             struct reclist_bucket *p;
 388             for (p = l->hashtable[i]; p; p = p->hash_next)
 389             {
 390                 wrbuf_destroy(p->record->relevance_explain1);
 391                 wrbuf_destroy(p->record->relevance_explain2);
 392                 p->record->relevance_explain1 = 0;
 393                 p->record->relevance_explain2 = 0;
 394             }
 395         }
 396         yaz_mutex_destroy(&l->mutex);
 397     }
 398 }
 399
 400 int reclist_get_num_records(struct reclist *l)
 401 {
 402     if (l)
 403         return l->num_records;
 404     return 0;
 405 }
 406
 407 static void merge_cluster(struct reclist *l,
 408                           struct relevance *r,
 409                           struct record_cluster *dst,
 410                           struct record_cluster *src)
 411 {
 412     struct record_metadata_attr *mkl;
 413     struct record **rp = &dst->records;
 414     for (; *rp; rp = &(*rp)->next)
 415         ;
 416     *rp = src->records;
 417
 418     for (mkl = src->merge_keys; mkl; mkl = mkl->next)
 419     {
 420         const char *merge_key = mkl->value;
 421         unsigned int bucket =
 422             jenkins_hash((unsigned char*) merge_key) % l->hash_size;
 423         struct reclist_bucket *p;
 424
 425         for (p = l->hashtable[bucket]; p; p = p->hash_next)
 426             if (p->record == src)
 427                 p->record = dst;
 428     }
 429
 430     /* not merging metadata and sortkeys yet */
 431
 432     relevance_mergerec(r, dst, src);
 433
 434     wrbuf_puts(dst->relevance_explain1, wrbuf_cstr(src->relevance_explain1));
 435     wrbuf_puts(dst->relevance_explain2, wrbuf_cstr(src->relevance_explain2));
 436
 437     wrbuf_destroy(src->relevance_explain1);
 438     src->relevance_explain1 = 0;
 439     wrbuf_destroy(src->relevance_explain2);
 440     src->relevance_explain2 = 0;
 441
 442     append_merge_keys(&dst->merge_keys, src->merge_keys, l->nmem);
 443 }
 444
 445 static struct record_cluster *new_cluster(
 446     struct reclist *l,
 447     struct relevance *r,
 448     struct conf_service *service,
 449     struct record *record,
 450     struct record_metadata_attr *merge_keys
 451     )
 452 {
 453     struct record_cluster *cluster;
 454     cluster = nmem_malloc(l->nmem, sizeof(*cluster));
 455
 456     record->next = 0;
 457     cluster->retrieval_position = l->num_records;
 458     cluster->records = record;
 459     cluster->merge_keys = 0;
 460     append_merge_keys(&cluster->merge_keys, merge_keys, l->nmem);
 461     cluster->relevance_score = 0;
 462     cluster->recid = cluster->merge_keys->value;
 463     cluster->metadata =
 464         nmem_malloc(l->nmem,
 465                     sizeof(struct record_metadata*) * service->num_metadata);
 466     memset(cluster->metadata, 0,
 467            sizeof(struct record_metadata*) * service->num_metadata);
 468     cluster->sortkeys =
 469         nmem_malloc(l->nmem, sizeof(struct record_metadata*) * service->num_sortkeys);
 470     memset(cluster->sortkeys, 0,
 471            sizeof(union data_types*) * service->num_sortkeys);
 472     relevance_newrec(r, cluster);
 473     cluster->relevance_explain1 = wrbuf_alloc();
 474     cluster->relevance_explain2 = wrbuf_alloc();
 475     /* attach to hash list */
 476     l->num_records++;
 477     l->sorted_list = l->sorted_ptr = 0;
 478     return cluster;
 479 }
 480
 481 // Insert a record. Return record cluster (newly formed or pre-existing)
 482 struct record_cluster *reclist_insert(struct reclist *l,
 483                                       struct relevance *r,
 484                                       struct conf_service *service,
 485                                       struct record *record,
 486                                       struct record_metadata_attr *merge_keys,
 487                                       int *total)
 488 {
 489     struct record_cluster *cluster = 0;
 490     struct record_metadata_attr *mkl = merge_keys;
 491
 492     assert(service);
 493     assert(l);
 494     assert(record);
 495     assert(merge_keys);
 496     assert(total);
 497
 498     yaz_mutex_enter(l->mutex);
 499
 500     for (; mkl; mkl = mkl->next)
 501     {
 502         const char *merge_key = mkl->value;
 503         unsigned int bucket =
 504             jenkins_hash((unsigned char*) merge_key) % l->hash_size;
 505         struct reclist_bucket **p;
 506         struct reclist_bucket *rb = 0;
 507
 508         for (p = &l->hashtable[bucket]; *p; p = &(*p)->hash_next)
 509         {
 510             struct record_metadata_attr *mkr = (*p)->record->merge_keys;
 511             for (; mkr; mkr = mkr->next)
 512             {
 513                 // We found a matching record. Merge them
 514                 if (!strcmp(merge_key, mkr->value))
 515                 {
 516                     rb = *p;
 517                     if (!cluster)
 518                     {
 519                         struct record **re;
 520                         for (re = &rb->record->records; *re; re = &(*re)->next)
 521                         {
 522                             if ((*re)->client == record->client &&
 523                                 record_compare(record, *re, service))
 524                             {
 525                                 yaz_mutex_leave(l->mutex);
 526                                 return 0;
 527                             }
 528                         }
 529                         cluster = rb->record;
 530                         *re = record;
 531                         record->next = 0;
 532                     }
 533                     else
 534                     {
 535                         if (cluster != rb->record)
 536                         {
 537                             assert(rb->record->relevance_explain1);
 538                             merge_cluster(l, r, cluster, rb->record);
 539                             (*total)--;
 540                         }
 541                     }
 542                 }
 543             }
 544         }
 545         if (!cluster)
 546         {
 547             (*total)++;
 548             cluster = new_cluster(l, r, service, record, merge_keys);
 549         }
 550
 551         if (!rb)
 552         {
 553             rb = nmem_malloc(l->nmem, sizeof(*rb));
 554             rb->record = cluster;
 555             rb->hash_next = 0;
 556
 557             *p = rb;
 558         }
 559     }
 560     yaz_mutex_leave(l->mutex);
 561     return cluster;
 562 }
 563
 564 int reclist_sortparms_cmp(struct reclist_sortparms *sort1, struct reclist_sortparms *sort2)
 565 {
 566     int rc;
 567     if (sort1 == sort2)
 568         return 0;
 569     if (sort1 == 0 || sort2 == 0)
 570         return 1;
 571     rc = strcmp(sort1->name, sort2->name) || sort1->increasing != sort2->increasing || sort1->type != sort2->type;
 572     return rc;
 573 }
 574 /*
 575  * Local variables:
 576  * c-basic-offset: 4
 577  * c-file-style: "Stroustrup"
 578  * indent-tabs-mode: nil
 579  * End:
 580  * vim: shiftwidth=4 tabstop=8 expandtab
 581  */
 582