src/termlists.c

   1 /*
   2  * $Id: termlists.c,v 1.5 2007-01-15 19:01:15 quinn Exp $
   3  */
   4
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <ctype.h>
   8 #include <yaz/yaz-util.h>
   9
  10 #if HAVE_CONFIG_H
  11 #include <cconfig.h>
  12 #endif
  13
  14 #include "termlists.h"
  15
  16 // Discussion:
  17 // As terms are found in incoming records, they are added to (or updated in) a
  18 // Hash table. When term records are updated, a frequency value is updated. At
  19 // the same time, a highscore is maintained for the most frequent terms.
  20
  21 struct termlist_bucket
  22 {
  23     struct termlist_score term;
  24     struct termlist_bucket *next;
  25 };
  26
  27 struct termlist
  28 {
  29     struct termlist_bucket **hashtable;
  30     int hashtable_size;
  31     int hashmask;
  32
  33     struct termlist_score **highscore;
  34     int highscore_size;
  35     int highscore_num;
  36     int highscore_min;
  37
  38     NMEM nmem;
  39 };
  40
  41
  42 // Jenkins one-at-a-time hash (from wikipedia)
  43 static unsigned int hash(const unsigned char *key)
  44 {
  45     unsigned int hash = 0;
  46
  47     while (*key)
  48     {
  49         hash += *(key++);
  50         hash += (hash << 10);
  51         hash ^= (hash >> 6);
  52     }
  53     hash += (hash << 3);
  54     hash ^= (hash >> 11);
  55     hash += (hash << 15);
  56     return hash;
  57 }
  58
  59 struct termlist *termlist_create(NMEM nmem, int numterms, int highscore_size)
  60 {
  61     int hashsize = 1;
  62     int halfnumterms;
  63     struct termlist *res;
  64
  65     // Calculate a hash size smallest power of 2 larger than 50% of expected numterms
  66     halfnumterms = numterms >> 1;
  67     if (halfnumterms < 0)
  68         halfnumterms = 1;
  69     while (hashsize < halfnumterms)
  70         hashsize <<= 1;
  71     res = nmem_malloc(nmem, sizeof(struct termlist));
  72     res->hashtable = nmem_malloc(nmem, hashsize * sizeof(struct termlist_bucket*));
  73     memset(res->hashtable, 0, hashsize * sizeof(struct termlist_bucket*));
  74     res->hashtable_size = hashsize;
  75     res->nmem = nmem;
  76     res->hashmask = hashsize - 1; // Creates a bitmask
  77
  78     res->highscore = nmem_malloc(nmem, highscore_size * sizeof(struct termlist_score *));
  79     res->highscore_size = highscore_size;
  80     res->highscore_num = 0;
  81     res->highscore_min = 0;
  82
  83     return res;
  84 }
  85
  86 static void update_highscore(struct termlist *tl, struct termlist_score *t)
  87 {
  88     int i;
  89     int smallest;
  90     int me = -1;
  91
  92     if (tl->highscore_num > tl->highscore_size && t->frequency < tl->highscore_min)
  93         return;
  94
  95     smallest = 0;
  96     for (i = 0; i < tl->highscore_num; i++)
  97     {
  98         if (tl->highscore[i]->frequency < tl->highscore[smallest]->frequency)
  99             smallest = i;
 100         if (tl->highscore[i] == t)
 101             me = i;
 102     }
 103     if (tl->highscore_num)
 104         tl->highscore_min = tl->highscore[smallest]->frequency;
 105     if (t->frequency < tl->highscore_min)
 106         tl->highscore_min = t->frequency;
 107     if (me >= 0)
 108         return;
 109     if (tl->highscore_num < tl->highscore_size)
 110     {
 111         tl->highscore[tl->highscore_num++] = t;
 112         if (t->frequency < tl->highscore_min)
 113             tl->highscore_min = t->frequency;
 114     }
 115     else
 116     {
 117         if (t->frequency > tl->highscore[smallest]->frequency)
 118         {
 119             tl->highscore[smallest] = t;
 120         }
 121     }
 122 }
 123
 124 void termlist_insert(struct termlist *tl, const char *term)
 125 {
 126     unsigned int bucket;
 127     struct termlist_bucket **p;
 128     char buf[256], *cp;
 129
 130     if (strlen(term) > 255)
 131         return;
 132     strcpy(buf, term);
 133     for (cp = buf + strlen(buf) - 1; cp > buf &&
 134             (*cp == ',' || *cp == '.' || *cp == ' '); cp--)
 135         *cp = '\0';
 136
 137     bucket = hash((unsigned char *)buf) & tl->hashmask;
 138     for (p = &tl->hashtable[bucket]; *p; p = &(*p)->next)
 139     {
 140         if (!strcmp(buf, (*p)->term.term))
 141         {
 142             (*p)->term.frequency++;
 143             update_highscore(tl, &((*p)->term));
 144             break;
 145         }
 146     }
 147     if (!*p) // We made it to the end of the bucket without finding match
 148     {
 149         struct termlist_bucket *new = nmem_malloc(tl->nmem,
 150                 sizeof(struct termlist_bucket));
 151         new->term.term = nmem_strdup(tl->nmem, buf);
 152         new->term.frequency = 1;
 153         new->next = 0;
 154         *p = new;
 155         update_highscore(tl, &new->term);
 156     }
 157 }
 158
 159 static int compare(const void *s1, const void *s2)
 160 {
 161     struct termlist_score **p1 = (struct termlist_score**) s1, **p2 = (struct termlist_score **) s2;
 162     return (*p2)->frequency - (*p1)->frequency;
 163 }
 164
 165 struct termlist_score **termlist_highscore(struct termlist *tl, int *len)
 166 {
 167     qsort(tl->highscore, tl->highscore_num, sizeof(struct termlist_score*), compare);
 168     *len = tl->highscore_num;
 169     return tl->highscore;
 170 }
 171
 172 /*
 173  * Local variables:
 174  * c-basic-offset: 4
 175  * indent-tabs-mode: nil
 176  * End:
 177  * vim: shiftwidth=4 tabstop=8 expandtab
 178  */