src/termlists.c

   1 /* $Id: termlists.c,v 1.7 2007-04-10 08:48:56 adam Exp $
   2    Copyright (c) 2006-2007, Index Data.
   3
   4 This file is part of Pazpar2.
   5
   6 Pazpar2 is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 Pazpar2 is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with Pazpar2; see the file LICENSE.  If not, write to the
  18 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.
  20  */
  21
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <ctype.h>
  25 #include <yaz/yaz-util.h>
  26
  27 #if HAVE_CONFIG_H
  28 #include <cconfig.h>
  29 #endif
  30
  31 #include "termlists.h"
  32
  33 // Discussion:
  34 // As terms are found in incoming records, they are added to (or updated in) a
  35 // Hash table. When term records are updated, a frequency value is updated. At
  36 // the same time, a highscore is maintained for the most frequent terms.
  37
  38 struct termlist_bucket
  39 {
  40     struct termlist_score term;
  41     struct termlist_bucket *next;
  42 };
  43
  44 struct termlist
  45 {
  46     struct termlist_bucket **hashtable;
  47     int hashtable_size;
  48     int hashmask;
  49
  50     struct termlist_score **highscore;
  51     int highscore_size;
  52     int highscore_num;
  53     int highscore_min;
  54
  55     NMEM nmem;
  56 };
  57
  58
  59 // Jenkins one-at-a-time hash (from wikipedia)
  60 static unsigned int hash(const unsigned char *key)
  61 {
  62     unsigned int hash = 0;
  63
  64     while (*key)
  65     {
  66         hash += *(key++);
  67         hash += (hash << 10);
  68         hash ^= (hash >> 6);
  69     }
  70     hash += (hash << 3);
  71     hash ^= (hash >> 11);
  72     hash += (hash << 15);
  73     return hash;
  74 }
  75
  76 struct termlist *termlist_create(NMEM nmem, int numterms, int highscore_size)
  77 {
  78     int hashsize = 1;
  79     int halfnumterms;
  80     struct termlist *res;
  81
  82     // Calculate a hash size smallest power of 2 larger than 50% of expected numterms
  83     halfnumterms = numterms >> 1;
  84     if (halfnumterms < 0)
  85         halfnumterms = 1;
  86     while (hashsize < halfnumterms)
  87         hashsize <<= 1;
  88     res = nmem_malloc(nmem, sizeof(struct termlist));
  89     res->hashtable = nmem_malloc(nmem, hashsize * sizeof(struct termlist_bucket*));
  90     memset(res->hashtable, 0, hashsize * sizeof(struct termlist_bucket*));
  91     res->hashtable_size = hashsize;
  92     res->nmem = nmem;
  93     res->hashmask = hashsize - 1; // Creates a bitmask
  94
  95     res->highscore = nmem_malloc(nmem, highscore_size * sizeof(struct termlist_score *));
  96     res->highscore_size = highscore_size;
  97     res->highscore_num = 0;
  98     res->highscore_min = 0;
  99
 100     return res;
 101 }
 102
 103 static void update_highscore(struct termlist *tl, struct termlist_score *t)
 104 {
 105     int i;
 106     int smallest;
 107     int me = -1;
 108
 109     if (tl->highscore_num > tl->highscore_size && t->frequency < tl->highscore_min)
 110         return;
 111
 112     smallest = 0;
 113     for (i = 0; i < tl->highscore_num; i++)
 114     {
 115         if (tl->highscore[i]->frequency < tl->highscore[smallest]->frequency)
 116             smallest = i;
 117         if (tl->highscore[i] == t)
 118             me = i;
 119     }
 120     if (tl->highscore_num)
 121         tl->highscore_min = tl->highscore[smallest]->frequency;
 122     if (t->frequency < tl->highscore_min)
 123         tl->highscore_min = t->frequency;
 124     if (me >= 0)
 125         return;
 126     if (tl->highscore_num < tl->highscore_size)
 127     {
 128         tl->highscore[tl->highscore_num++] = t;
 129         if (t->frequency < tl->highscore_min)
 130             tl->highscore_min = t->frequency;
 131     }
 132     else
 133     {
 134         if (t->frequency > tl->highscore[smallest]->frequency)
 135         {
 136             tl->highscore[smallest] = t;
 137         }
 138     }
 139 }
 140
 141 void termlist_insert(struct termlist *tl, const char *term)
 142 {
 143     unsigned int bucket;
 144     struct termlist_bucket **p;
 145     char buf[256], *cp;
 146
 147     if (strlen(term) > 255)
 148         return;
 149     strcpy(buf, term);
 150     for (cp = buf + strlen(buf) - 1; cp > buf &&
 151             (*cp == ',' || *cp == '.' || *cp == ' ' || *cp == '-'); cp--)
 152         *cp = '\0';
 153
 154     bucket = hash((unsigned char *)buf) & tl->hashmask;
 155     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
 156     {
 157         if (!strcmp(buf, (*p)->term.term))
 158         {
 159             (*p)->term.frequency++;
 160             update_highscore(tl, &((*p)->term));
 161             break;
 162         }
 163     }
 164     if (!*p) // We made it to the end of the bucket without finding match
 165     {
 166         struct termlist_bucket *new = nmem_malloc(tl->nmem,
 167                 sizeof(struct termlist_bucket));
 168         new->term.term = nmem_strdup(tl->nmem, buf);
 169         new->term.frequency = 1;
 170         new->next = 0;
 171         *p = new;
 172         update_highscore(tl, &new->term);
 173     }
 174 }
 175
 176 static int compare(const void *s1, const void *s2)
 177 {
 178     struct termlist_score **p1 = (struct termlist_score**) s1, **p2 = (struct termlist_score **) s2;
 179     return (*p2)->frequency - (*p1)->frequency;
 180 }
 181
 182 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
 183 {
 184     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
 185     *len = tl->highscore_num;
 186     return tl->highscore;
 187 }
 188
 189 /*
 190  * Local variables:
 191  * c-basic-offset: 4
 192  * indent-tabs-mode: nil
 193  * End:
 194  * vim: shiftwidth=4 tabstop=8 expandtab
 195  */