src/reclists.c

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