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     Bucket next;        /*!< pointer to next item in bucket */
  18     HTKEYTYPE key;      /*!< hash key */
  19 #ifdef HTDATATYPE
  20     int dataCount;      /*!< data entries */
  21     HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
  22 #endif
  23 };
  24
  25 /**
  26  */
  27 struct HASHSTRUCT {
  28     int numBuckets;                     /*!< number of hash buckets */
  29     Bucket * buckets;                   /*!< hash bucket array */
  30     hashFunctionType fn;                /*!< generate hash value for key */
  31     hashEqualityType eq;                /*!< compare hash keys for equality */
  32     hashFreeKey freeKey;
  33 #ifdef HTDATATYPE
  34     hashFreeData freeData;
  35 #endif
  36 };
  37
  38 /**
  39  * Find entry in hash table.
  40  * @param ht            pointer to hash table
  41  * @param key           pointer to key value
  42  * @return pointer to hash bucket of key (or NULL)
  43  */
  44 static
  45 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
  46 {
  47     unsigned int hash;
  48     Bucket b;
  49
  50     hash = ht->fn(key) % ht->numBuckets;
  51     b = ht->buckets[hash];
  52
  53     while (b && ht->eq(b->key, key))
  54         b = b->next;
  55
  56     return b;
  57 }
  58
  59 HASHTYPE HASHPREFIX(Create)(int numBuckets,
  60                             hashFunctionType fn, hashEqualityType eq,
  61                             hashFreeKey freeKey
  62 #ifdef HTDATATYPE
  63 , hashFreeData freeData
  64 #endif
  65 )
  66 {
  67     HASHTYPE ht;
  68
  69     ht = xmalloc(sizeof(*ht));
  70     ht->numBuckets = numBuckets;
  71     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
  72     ht->freeKey = freeKey;
  73 #ifdef HTDATATYPE
  74     ht->freeData = freeData;
  75 #endif
  76     ht->fn = fn;
  77     ht->eq = eq;
  78     return ht;
  79 }
  80
  81 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
  82 #ifdef HTDATATYPE
  83 , HTDATATYPE data
  84 #endif
  85 )
  86 {
  87     unsigned int hash;
  88     Bucket b;
  89     Bucket * b_addr;
  90
  91     hash = ht->fn(key) % ht->numBuckets;
  92     b = ht->buckets[hash];
  93     b_addr = ht->buckets + hash;
  94
  95     while (b && ht->eq(b->key, key)) {
  96         b_addr = &(b->next);
  97         b = b->next;
  98     }
  99
 100     if (b == NULL) {
 101         b = xmalloc(sizeof(*b));
 102         b->key = key;
 103 #ifdef HTDATATYPE
 104         b->dataCount = 1;
 105         b->data[0] = data;
 106 #endif
 107         b->next = ht->buckets[hash];
 108         ht->buckets[hash] = b;
 109     }
 110 #ifdef HTDATATYPE
 111     else {
 112         // resizing bucket TODO: increase exponentially
 113         // Bucket_s already contains space for one dataset
 114         b = *b_addr = xrealloc(
 115             b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
 116         // though increasing dataCount after the resize
 117         b->data[b->dataCount++] = data;
 118     }
 119 #endif
 120 }
 121
 122 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
 123 {
 124     Bucket b, n;
 125     int i;
 126     if (ht==NULL)
 127         return ht;
 128     for (i = 0; i < ht->numBuckets; i++) {
 129         b = ht->buckets[i];
 130         if (b == NULL)
 131             continue;
 132         ht->buckets[i] = NULL;
 133
 134         do {
 135             n = b->next;
 136             if (ht->freeKey)
 137                 b->key = ht->freeKey(b->key);
 138 #ifdef HTDATATYPE
 139             if (ht->freeData) {
 140                 int j;
 141                 for (j=0; j < b->dataCount; j++ ) {
 142                     b->data[j] = ht->freeData(b->data[j]);
 143                 }
 144             }
 145 #endif
 146             b = _free(b);
 147         } while ((b = n) != NULL);
 148     }
 149
 150     ht->buckets = _free(ht->buckets);
 151     ht = _free(ht);
 152
 153     return NULL;
 154 }
 155
 156 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
 157 {
 158     Bucket b;
 159
 160     if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
 161 }
 162
 163 #ifdef HTDATATYPE
 164
 165 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE** data,
 166                int * dataCount, HTKEYTYPE* tableKey)
 167 {
 168     Bucket b;
 169     int rc = ((b = HASHPREFIX(findEntry)(ht, key)) != NULL);
 170
 171     if (data)
 172         *data = rc ? b->data : NULL;
 173     if (dataCount)
 174         *dataCount = rc ? b->dataCount : 0;
 175     if (tableKey && rc)
 176         *tableKey = b->key;
 177
 178     return rc;
 179 }
 180
 181 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
 182     int i;
 183     Bucket bucket;
 184
 185     int hashcnt=0, bucketcnt=0, datacnt=0;
 186     int maxbuckets=0;
 187
 188     for (i=0; i<ht->numBuckets; i++) {
 189         int buckets = 0;
 190         for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
 191             buckets++;
 192 #ifdef HTDATATYPE
 193             datacnt += bucket->dataCount;
 194 #endif
 195         }
 196         if (maxbuckets < buckets) maxbuckets = buckets;
 197         if (buckets) hashcnt++;
 198         bucketcnt += buckets;
 199     }
 200     fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
 201     fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
 202     fprintf(stderr, "Keys: %i\n", bucketcnt);
 203     fprintf(stderr, "Values: %i\n", datacnt);
 204     fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);
 205 }
 206
 207 #endif