ICU chain "facet" honors YAC ICU element <display/>.
[pazpar2-moved-to-github.git] / src / termlists.c
1 /* This file is part of Pazpar2.
2    Copyright (C) 2006-2011 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     for (cp = buf + strlen(buf); cp != buf && strchr(",. -", cp[-1]); cp--)
122         cp[-1] = '\0';
123     
124     bucket = jenkins_hash((unsigned char *)buf) % tl->hash_size;
125     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
126     {
127         if (!strcmp(buf, (*p)->term.norm_term))
128         {
129             (*p)->term.frequency += freq;
130             update_highscore(tl, &((*p)->term));
131             break;
132         }
133     }
134     if (!*p) // We made it to the end of the bucket without finding match
135     {
136         struct termlist_bucket *new = nmem_malloc(tl->nmem,
137                 sizeof(struct termlist_bucket));
138         new->term.norm_term = nmem_strdup(tl->nmem, buf);
139         new->term.display_term = *display_term ?
140             nmem_strdup(tl->nmem, display_term) : new->term.norm_term;
141         new->term.frequency = freq;
142         new->next = 0;
143         *p = new;
144         update_highscore(tl, &new->term);
145     }
146 }
147
148 static int compare(const void *s1, const void *s2)
149 {
150     struct termlist_score **p1 = (struct termlist_score**) s1, **p2 = (struct termlist_score **) s2;
151     return (*p2)->frequency - (*p1)->frequency;
152 }
153
154 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
155 {
156     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
157     *len = tl->highscore_num;
158     return tl->highscore;
159 }
160
161 /*
162  * Local variables:
163  * c-basic-offset: 4
164  * c-file-style: "Stroustrup"
165  * indent-tabs-mode: nil
166  * End:
167  * vim: shiftwidth=4 tabstop=8 expandtab
168  */
169