src/termlists.c

   1 /* This file is part of Pazpar2.
   2    Copyright (C) 2006-2012 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 #if HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <yaz/yaz-util.h>
  27
  28 #include "termlists.h"
  29 #include "jenkins_hash.h"
  30
  31 // Discussion:
  32 // As terms are found in incoming records, they are added to (or updated in) a
  33 // Hash table. When term records are updated, a frequency value is updated. At
  34 // the same time, a highscore is maintained for the most frequent terms.
  35
  36 struct termlist_bucket
  37 {
  38     struct termlist_score term;
  39     struct termlist_bucket *next;
  40 };
  41
  42 struct termlist
  43 {
  44     struct termlist_bucket **hashtable;
  45     unsigned hash_size;
  46
  47     struct termlist_score **highscore;
  48     int highscore_size;
  49     int highscore_num;
  50     int highscore_min;
  51
  52     NMEM nmem;
  53 };
  54
  55 struct termlist *termlist_create(NMEM nmem, int highscore_size)
  56 {
  57     struct termlist *res = nmem_malloc(nmem, sizeof(struct termlist));
  58     res->hash_size = 399;
  59     res->hashtable =
  60         nmem_malloc(nmem, res->hash_size * sizeof(struct termlist_bucket*));
  61     memset(res->hashtable, 0, res->hash_size * sizeof(struct termlist_bucket*));
  62     res->nmem = nmem;
  63
  64     res->highscore = nmem_malloc(nmem, highscore_size * sizeof(struct termlist_score *));
  65     res->highscore_size = highscore_size;
  66     res->highscore_num = 0;
  67     res->highscore_min = 0;
  68
  69     return res;
  70 }
  71
  72 static void update_highscore(struct termlist *tl, struct termlist_score *t)
  73 {
  74     int i;
  75     int smallest;
  76     int me = -1;
  77
  78     if (tl->highscore_num > tl->highscore_size && t->frequency < tl->highscore_min)
  79         return;
  80
  81     smallest = 0;
  82     for (i = 0; i < tl->highscore_num; i++)
  83     {
  84         if (tl->highscore[i]->frequency < tl->highscore[smallest]->frequency)
  85             smallest = i;
  86         if (tl->highscore[i] == t)
  87             me = i;
  88     }
  89     if (tl->highscore_num)
  90         tl->highscore_min = tl->highscore[smallest]->frequency;
  91     if (t->frequency < tl->highscore_min)
  92         tl->highscore_min = t->frequency;
  93     if (me >= 0)
  94         return;
  95     if (tl->highscore_num < tl->highscore_size)
  96     {
  97         tl->highscore[tl->highscore_num++] = t;
  98         if (t->frequency < tl->highscore_min)
  99             tl->highscore_min = t->frequency;
 100     }
 101     else
 102     {
 103         if (t->frequency > tl->highscore[smallest]->frequency)
 104         {
 105             tl->highscore[smallest] = t;
 106         }
 107     }
 108 }
 109
 110 void termlist_insert(struct termlist *tl, const char *display_term,
 111                      const char *norm_term, int freq)
 112 {
 113     unsigned int bucket;
 114     struct termlist_bucket **p;
 115     char buf[256], *cp;
 116
 117     if (strlen(norm_term) > 255)
 118         return;
 119     strcpy(buf, norm_term);
 120     /* chop right */
 121     /*
 122     for (cp = buf + strlen(buf); cp != buf && strchr(",. -", cp[-1]); cp--)
 123         cp[-1] = '\0';
 124     */
 125     bucket = jenkins_hash((unsigned char *)buf) % tl->hash_size;
 126     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
 127     {
 128         if (!strcmp(buf, (*p)->term.norm_term))
 129         {
 130             (*p)->term.frequency += freq;
 131             update_highscore(tl, &((*p)->term));
 132             break;
 133         }
 134     }
 135     if (!*p) // We made it to the end of the bucket without finding match
 136     {
 137         struct termlist_bucket *new = nmem_malloc(tl->nmem,
 138                 sizeof(struct termlist_bucket));
 139         new->term.norm_term = nmem_strdup(tl->nmem, buf);
 140         new->term.display_term = *display_term ?
 141             nmem_strdup(tl->nmem, display_term) : new->term.norm_term;
 142         new->term.frequency = freq;
 143         new->next = 0;
 144         *p = new;
 145         update_highscore(tl, &new->term);
 146     }
 147 }
 148
 149 static int compare(const void *s1, const void *s2)
 150 {
 151     struct termlist_score **p1 = (struct termlist_score **) s1;
 152     struct termlist_score **p2 = (struct termlist_score **) s2;
 153     int d = (*p2)->frequency - (*p1)->frequency;
 154     if (d)
 155         return d;
 156     return strcmp((*p1)->display_term, (*p2)->display_term);
 157 }
 158
 159 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
 160 {
 161     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
 162     *len = tl->highscore_num;
 163     return tl->highscore;
 164 }
 165
 166 /*
 167  * Local variables:
 168  * c-basic-offset: 4
 169  * c-file-style: "Stroustrup"
 170  * indent-tabs-mode: nil
 171  * End:
 172  * vim: shiftwidth=4 tabstop=8 expandtab
 173  */
 174