fd49cfaf60da6ceb049b29f233358b83fddb03ac
[pazpar2-moved-to-github.git] / src / termlists.c
1 /* This file is part of Pazpar2.
2    Copyright (C) 2006-2009 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
30 // Discussion:
31 // As terms are found in incoming records, they are added to (or updated in) a
32 // Hash table. When term records are updated, a frequency value is updated. At
33 // the same time, a highscore is maintained for the most frequent terms.
34
35 struct termlist_bucket
36 {
37     struct termlist_score term;
38     struct termlist_bucket *next;
39 };
40
41 struct termlist
42 {
43     struct termlist_bucket **hashtable;
44     int hashtable_size;
45     int hashmask;
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
56 // Jenkins one-at-a-time hash (from wikipedia)
57 static unsigned int hash(const unsigned char *key)
58 {
59     unsigned int hash = 0;
60
61     while (*key)
62     {
63         hash += *(key++);
64         hash += (hash << 10);
65         hash ^= (hash >> 6);
66     }
67     hash += (hash << 3);
68     hash ^= (hash >> 11);
69     hash += (hash << 15);
70     return hash;
71 }
72
73 struct termlist *termlist_create(NMEM nmem, int numterms, int highscore_size)
74 {
75     int hashsize = 1;
76     int halfnumterms;
77     struct termlist *res;
78
79     // Calculate a hash size smallest power of 2 larger than 50% of expected numterms
80     halfnumterms = numterms >> 1;
81     if (halfnumterms < 0)
82         halfnumterms = 1;
83     while (hashsize < halfnumterms)
84         hashsize <<= 1;
85     res = nmem_malloc(nmem, sizeof(struct termlist));
86     res->hashtable = nmem_malloc(nmem, hashsize * sizeof(struct termlist_bucket*));
87     memset(res->hashtable, 0, hashsize * sizeof(struct termlist_bucket*));
88     res->hashtable_size = hashsize;
89     res->nmem = nmem;
90     res->hashmask = hashsize - 1; // Creates a bitmask
91
92     res->highscore = nmem_malloc(nmem, highscore_size * sizeof(struct termlist_score *));
93     res->highscore_size = highscore_size;
94     res->highscore_num = 0;
95     res->highscore_min = 0;
96
97     return res;
98 }
99
100 static void update_highscore(struct termlist *tl, struct termlist_score *t)
101 {
102     int i;
103     int smallest;
104     int me = -1;
105
106     if (tl->highscore_num > tl->highscore_size && t->frequency < tl->highscore_min)
107         return;
108
109     smallest = 0;
110     for (i = 0; i < tl->highscore_num; i++)
111     {
112         if (tl->highscore[i]->frequency < tl->highscore[smallest]->frequency)
113             smallest = i;
114         if (tl->highscore[i] == t)
115             me = i;
116     }
117     if (tl->highscore_num)
118         tl->highscore_min = tl->highscore[smallest]->frequency;
119     if (t->frequency < tl->highscore_min)
120         tl->highscore_min = t->frequency;
121     if (me >= 0)
122         return;
123     if (tl->highscore_num < tl->highscore_size)
124     {
125         tl->highscore[tl->highscore_num++] = t;
126         if (t->frequency < tl->highscore_min)
127             tl->highscore_min = t->frequency;
128     }
129     else
130     {
131         if (t->frequency > tl->highscore[smallest]->frequency)
132         {
133             tl->highscore[smallest] = t;
134         }
135     }
136 }
137
138 void termlist_insert(struct termlist *tl, const char *term)
139 {
140     unsigned int bucket;
141     struct termlist_bucket **p;
142     char buf[256], *cp;
143
144     if (strlen(term) > 255)
145         return;
146     strcpy(buf, term);
147     /* chop right */
148     for (cp = buf + strlen(buf); cp != buf && strchr(",. -", cp[-1]); cp--)
149         cp[-1] = '\0';
150     
151     bucket = hash((unsigned char *)buf) & tl->hashmask;
152     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
153     {
154         if (!strcmp(buf, (*p)->term.term))
155         {
156             (*p)->term.frequency++;
157             update_highscore(tl, &((*p)->term));
158             break;
159         }
160     }
161     if (!*p) // We made it to the end of the bucket without finding match
162     {
163         struct termlist_bucket *new = nmem_malloc(tl->nmem,
164                 sizeof(struct termlist_bucket));
165         new->term.term = nmem_strdup(tl->nmem, buf);
166         new->term.frequency = 1;
167         new->next = 0;
168         *p = new;
169         update_highscore(tl, &new->term);
170     }
171 }
172
173 static int compare(const void *s1, const void *s2)
174 {
175     struct termlist_score **p1 = (struct termlist_score**) s1, **p2 = (struct termlist_score **) s2;
176     return (*p2)->frequency - (*p1)->frequency;
177 }
178
179 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
180 {
181     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
182     *len = tl->highscore_num;
183     return tl->highscore;
184 }
185
186 /*
187  * Local variables:
188  * c-basic-offset: 4
189  * indent-tabs-mode: nil
190  * End:
191  * vim: shiftwidth=4 tabstop=8 expandtab
192  */