lib/rpmhash.C

   1 /**
   2  * \file lib/rpmhash.c
   3  * Hash table implemenation
   4  */
   5
   6 #include "system.h"
   7 #include "debug.h"
   8
   9 #define Bucket JOIN(HASHTYPE,Buket)
  10 #define Bucket_s JOIN(HASHTYPE,Buket_s)
  11
  12 typedef struct  Bucket_s * Bucket;
  13
  14 /**
  15  */
  16 struct  Bucket_s {
  17     HTKEYTYPE key;      /*!< hash key */
  18     HTDATATYPE * data;  /*!< pointer to hashed data */
  19     int dataCount;      /*!< length of data (0 if unknown) */
  20     Bucket next;        /*!< pointer to next item in bucket */
  21 };
  22
  23 /**
  24  */
  25 struct HASHSTRUCT {
  26     int numBuckets;                     /*!< number of hash buckets */
  27     Bucket * buckets;           /*!< hash bucket array */
  28     hashFunctionType fn;                /*!< generate hash value for key */
  29     hashEqualityType eq;                /*!< compare hash keys for equality */
  30     hashFreeKey freeKey;
  31     hashFreeData freeData;
  32 };
  33
  34 /**
  35  * Find entry in hash table.
  36  * @param ht            pointer to hash table
  37  * @param key           pointer to key value
  38  * @return pointer to hash bucket of key (or NULL)
  39  */
  40 static
  41 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
  42 {
  43     unsigned int hash;
  44     Bucket b;
  45
  46     hash = ht->fn(key) % ht->numBuckets;
  47     b = ht->buckets[hash];
  48
  49     while (b && b->key && ht->eq(b->key, key))
  50         b = b->next;
  51
  52     return b;
  53 }
  54
  55 HASHTYPE HASHPREFIX(Create)(int numBuckets,
  56                             hashFunctionType fn, hashEqualityType eq,
  57                             hashFreeKey freeKey, hashFreeData freeData)
  58 {
  59     HASHTYPE ht;
  60
  61     ht = xmalloc(sizeof(*ht));
  62     ht->numBuckets = numBuckets;
  63     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
  64     ht->freeKey = freeKey;
  65     ht->freeData = freeData;
  66     ht->fn = fn;
  67     ht->eq = eq;
  68     return ht;
  69 }
  70
  71 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE data)
  72 {
  73     unsigned int hash;
  74     Bucket b;
  75
  76     hash = ht->fn(key) % ht->numBuckets;
  77     b = ht->buckets[hash];
  78
  79     while (b && b->key && ht->eq(b->key, key))
  80         b = b->next;
  81
  82     if (b == NULL) {
  83         b = xmalloc(sizeof(*b));
  84         b->key = key;
  85         b->dataCount = 0;
  86         b->next = ht->buckets[hash];
  87         b->data = NULL;
  88         ht->buckets[hash] = b;
  89     }
  90
  91     b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
  92     b->data[b->dataCount++] = data;
  93 }
  94
  95 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
  96 {
  97     Bucket b, n;
  98     int i, j;
  99
 100     for (i = 0; i < ht->numBuckets; i++) {
 101         b = ht->buckets[i];
 102         if (b == NULL)
 103             continue;
 104         ht->buckets[i] = NULL;
 105         if (ht->freeKey)
 106             b->key = ht->freeKey(b->key);
 107
 108         do {
 109             n = b->next;
 110             if (b->data) {
 111                 if (ht->freeData) {
 112                   for (j=0; j < b->dataCount; j++ ) {
 113                     b->data[j] = ht->freeData(b->data[j]);
 114                   }
 115                 }
 116                 b->data = _free(b->data);
 117             }
 118             b = _free(b);
 119         } while ((b = n) != NULL);
 120     }
 121
 122     ht->buckets = _free(ht->buckets);
 123     ht = _free(ht);
 124
 125     return NULL;
 126 }
 127
 128 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
 129 {
 130     Bucket b;
 131
 132     if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
 133 }
 134
 135 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE** data,
 136                int * dataCount, HTKEYTYPE* tableKey)
 137 {
 138     Bucket b;
 139
 140     if ((b = HASHPREFIX(findEntry)(ht, key)) == NULL)
 141         return 1;
 142
 143     if (data)
 144         *data = b->data;
 145     if (dataCount)
 146         *dataCount = b->dataCount;
 147     if (tableKey)
 148         *tableKey = b->key;
 149
 150     return 0;
 151 }
 152
 153 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
 154     int i;
 155     Bucket bucket;
 156
 157     int hashcnt=0, bucketcnt=0, datacnt=0;
 158     int maxbuckets=0;
 159
 160     for (i=0; i<ht->numBuckets; i++) {
 161         int buckets = 0;
 162         for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
 163             buckets++;
 164             datacnt += bucket->dataCount;
 165         }
 166         if (maxbuckets < buckets) maxbuckets = buckets;
 167         if (buckets) hashcnt++;
 168         bucketcnt += buckets;
 169     }
 170     fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
 171     fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
 172     fprintf(stderr, "Keys: %i\n", bucketcnt);
 173     fprintf(stderr, "Values: %i\n", datacnt);
 174     fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);
 175 }