src/termlists.c

   1 /* This file is part of Pazpar2.
   2    Copyright (C) 2006-2008 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 <stdlib.h>
  21 #include <string.h>
  22 #include <ctype.h>
  23 #include <yaz/yaz-util.h>
  24
  25 #if HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include "termlists.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     int hashtable_size;
  46     int hashmask;
  47
  48     struct termlist_score **highscore;
  49     int highscore_size;
  50     int highscore_num;
  51     int highscore_min;
  52
  53     NMEM nmem;
  54 };
  55
  56
  57 // Jenkins one-at-a-time hash (from wikipedia)
  58 static unsigned int hash(const unsigned char *key)
  59 {
  60     unsigned int hash = 0;
  61
  62     while (*key)
  63     {
  64         hash += *(key++);
  65         hash += (hash << 10);
  66         hash ^= (hash >> 6);
  67     }
  68     hash += (hash << 3);
  69     hash ^= (hash >> 11);
  70     hash += (hash << 15);
  71     return hash;
  72 }
  73
  74 struct termlist *termlist_create(NMEM nmem, int numterms, int highscore_size)
  75 {
  76     int hashsize = 1;
  77     int halfnumterms;
  78     struct termlist *res;
  79
  80     // Calculate a hash size smallest power of 2 larger than 50% of expected numterms
  81     halfnumterms = numterms >> 1;
  82     if (halfnumterms < 0)
  83         halfnumterms = 1;
  84     while (hashsize < halfnumterms)
  85         hashsize <<= 1;
  86     res = nmem_malloc(nmem, sizeof(struct termlist));
  87     res->hashtable = nmem_malloc(nmem, hashsize * sizeof(struct termlist_bucket*));
  88     memset(res->hashtable, 0, hashsize * sizeof(struct termlist_bucket*));
  89     res->hashtable_size = hashsize;
  90     res->nmem = nmem;
  91     res->hashmask = hashsize - 1; // Creates a bitmask
  92
  93     res->highscore = nmem_malloc(nmem, highscore_size * sizeof(struct termlist_score *));
  94     res->highscore_size = highscore_size;
  95     res->highscore_num = 0;
  96     res->highscore_min = 0;
  97
  98     return res;
  99 }
 100
 101 static void update_highscore(struct termlist *tl, struct termlist_score *t)
 102 {
 103     int i;
 104     int smallest;
 105     int me = -1;
 106
 107     if (tl->highscore_num > tl->highscore_size && t->frequency < tl->highscore_min)
 108         return;
 109
 110     smallest = 0;
 111     for (i = 0; i < tl->highscore_num; i++)
 112     {
 113         if (tl->highscore[i]->frequency < tl->highscore[smallest]->frequency)
 114             smallest = i;
 115         if (tl->highscore[i] == t)
 116             me = i;
 117     }
 118     if (tl->highscore_num)
 119         tl->highscore_min = tl->highscore[smallest]->frequency;
 120     if (t->frequency < tl->highscore_min)
 121         tl->highscore_min = t->frequency;
 122     if (me >= 0)
 123         return;
 124     if (tl->highscore_num < tl->highscore_size)
 125     {
 126         tl->highscore[tl->highscore_num++] = t;
 127         if (t->frequency < tl->highscore_min)
 128             tl->highscore_min = t->frequency;
 129     }
 130     else
 131     {
 132         if (t->frequency > tl->highscore[smallest]->frequency)
 133         {
 134             tl->highscore[smallest] = t;
 135         }
 136     }
 137 }
 138
 139 void termlist_insert(struct termlist *tl, const char *term)
 140 {
 141     unsigned int bucket;
 142     struct termlist_bucket **p;
 143     char buf[256], *cp;
 144
 145     if (strlen(term) > 255)
 146         return;
 147     strcpy(buf, term);
 148     /* chop right */
 149     for (cp = buf + strlen(buf); cp != buf && strchr(",. -", cp[-1]); cp--)
 150         cp[-1] = '\0';
 151
 152     bucket = hash((unsigned char *)buf) & tl->hashmask;
 153     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
 154     {
 155         if (!strcmp(buf, (*p)->term.term))
 156         {
 157             (*p)->term.frequency++;
 158             update_highscore(tl, &((*p)->term));
 159             break;
 160         }
 161     }
 162     if (!*p) // We made it to the end of the bucket without finding match
 163     {
 164         struct termlist_bucket *new = nmem_malloc(tl->nmem,
 165                 sizeof(struct termlist_bucket));
 166         new->term.term = nmem_strdup(tl->nmem, buf);
 167         new->term.frequency = 1;
 168         new->next = 0;
 169         *p = new;
 170         update_highscore(tl, &new->term);
 171     }
 172 }
 173
 174 static int compare(const void *s1, const void *s2)
 175 {
 176     struct termlist_score **p1 = (struct termlist_score**) s1, **p2 = (struct termlist_score **) s2;
 177     return (*p2)->frequency - (*p1)->frequency;
 178 }
 179
 180 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
 181 {
 182     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
 183     *len = tl->highscore_num;
 184     return tl->highscore;
 185 }
 186
 187 /*
 188  * Local variables:
 189  * c-basic-offset: 4
 190  * indent-tabs-mode: nil
 191  * End:
 192  * vim: shiftwidth=4 tabstop=8 expandtab
 193  */