src/reclists.c

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