reclists.c

   1 /*
   2  * $Id: reclists.c,v 1.1 2006-11-24 20:29:07 quinn Exp $
   3  */
   4
   5 #include <assert.h>
   6
   7 #include <yaz/yaz-util.h>
   8
   9 #include "pazpar2.h"
  10 #include "reclists.h"
  11
  12 struct reclist_bucket
  13 {
  14     struct record *record;
  15     struct reclist_bucket *next;
  16 };
  17
  18 struct reclist
  19 {
  20     struct reclist_bucket **hashtable;
  21     int hashtable_size;
  22     int hashmask;
  23
  24     struct record **flatlist;
  25     int flatlist_size;
  26     int num_records;
  27     int pointer;
  28
  29     NMEM nmem;
  30 };
  31
  32 struct record *reclist_read_record(struct reclist *l)
  33 {
  34     if (l->pointer < l->num_records)
  35         return l->flatlist[l->pointer++];
  36     else
  37         return 0;
  38 }
  39
  40 void reclist_rewind(struct reclist *l)
  41 {
  42     l->pointer = 0;
  43 }
  44
  45 // Jenkins one-at-a-time hash (from wikipedia)
  46 static unsigned int hash(const unsigned char *key)
  47 {
  48     unsigned int hash = 0;
  49
  50     while (*key)
  51     {
  52         hash += *(key++);
  53         hash += (hash << 10);
  54         hash ^= (hash >> 6);
  55     }
  56     hash += (hash << 3);
  57     hash ^= (hash >> 11);
  58     hash += (hash << 15);
  59     return hash;
  60 }
  61
  62 struct reclist *reclist_create(NMEM nmem, int numrecs)
  63 {
  64     int hashsize = 1;
  65     struct reclist *res;
  66
  67     assert(numrecs);
  68     while (hashsize < numrecs)
  69         hashsize <<= 1;
  70     res = nmem_malloc(nmem, sizeof(struct reclist));
  71     res->hashtable = nmem_malloc(nmem, hashsize * sizeof(struct reclist_bucket*));
  72     bzero(res->hashtable, hashsize * sizeof(struct reclist_bucket*));
  73     res->hashtable_size = hashsize;
  74     res->nmem = nmem;
  75     res->hashmask = hashsize - 1; // Creates a bitmask
  76
  77     res->num_records = 0;
  78     res->flatlist = nmem_malloc(nmem, numrecs * sizeof(struct record*));
  79     res->flatlist_size = numrecs;
  80
  81     return res;
  82 }
  83
  84 void reclist_insert(struct reclist *l, struct record  *record)
  85 {
  86     unsigned int bucket;
  87     struct reclist_bucket **p;
  88
  89     bucket = hash(record->merge_key) & l->hashmask;
  90     for (p = &l->hashtable[bucket]; *p; p = &(*p)->next)
  91     {
  92         // We found a matching record. Merge them
  93         if (!strcmp(record->merge_key, (*p)->record->merge_key))
  94         {
  95             struct record *existing = (*p)->record;
  96             yaz_log(YLOG_LOG, "Found a matching record: %s", record->merge_key);
  97             record->next_cluster = existing->next_cluster;
  98             existing->next_cluster = record;
  99             break;
 100         }
 101     }
 102     if (!*p) // We made it to the end of the bucket without finding match
 103     {
 104         yaz_log(YLOG_DEBUG, "Added a new record: %s", record->merge_key);
 105         struct reclist_bucket *new = nmem_malloc(l->nmem,
 106                 sizeof(struct reclist_bucket));
 107         new->record = record;
 108         record->next_cluster = 0;
 109         new->next = 0;
 110         *p = new;
 111         l->flatlist[l->num_records++] = record;
 112     }
 113 }
 114
 115
 116 /*
 117  * Local variables:
 118  * c-basic-offset: 4
 119  * indent-tabs-mode: nil
 120  * End:
 121  * vim: shiftwidth=4 tabstop=8 expandtab
 122  */