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     int bucketCount;                    /*!< number of used buckets */
  34     int keyCount;                       /*!< number of keys */
  35 #ifdef HTDATATYPE
  36     int dataCount;                      /*!< number of data entries */
  37     hashFreeData freeData;
  38 #endif
  39 };
  40
  41 /**
  42  * Find entry in hash table.
  43  * @param ht            pointer to hash table
  44  * @param key           pointer to key value
  45  * @return pointer to hash bucket of key (or NULL)
  46  */
  47 static
  48 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
  49 {
  50     unsigned int hash;
  51     Bucket b;
  52
  53     hash = ht->fn(key) % ht->numBuckets;
  54     b = ht->buckets[hash];
  55
  56     while (b && ht->eq(b->key, key))
  57         b = b->next;
  58
  59     return b;
  60 }
  61
  62 HASHTYPE HASHPREFIX(Create)(int numBuckets,
  63                             hashFunctionType fn, hashEqualityType eq,
  64                             hashFreeKey freeKey
  65 #ifdef HTDATATYPE
  66 , hashFreeData freeData
  67 #endif
  68 )
  69 {
  70     HASHTYPE ht;
  71
  72     ht = xmalloc(sizeof(*ht));
  73     ht->numBuckets = numBuckets;
  74     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
  75     ht->freeKey = freeKey;
  76 #ifdef HTDATATYPE
  77     ht->freeData = freeData;
  78     ht->dataCount = 0;
  79 #endif
  80     ht->fn = fn;
  81     ht->eq = eq;
  82     ht->bucketCount = ht->keyCount = 0;
  83     return ht;
  84 }
  85
  86 static void HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) {
  87     Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
  88
  89     for (int i=0; i<ht->numBuckets; i++) {
  90         Bucket b = ht->buckets[i];
  91         Bucket nextB;
  92         while (b != NULL) {
  93             unsigned int hash = ht->fn(b->key) % numBuckets;
  94             nextB = b->next;
  95             b->next = buckets[hash];
  96             buckets[hash] = b;
  97             b = nextB;
  98         }
  99     }
 100     free(ht->buckets);
 101     ht->buckets = buckets;
 102     ht->numBuckets = numBuckets;
 103 }
 104
 105 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key)
 106 {
 107     return ht->fn(key);
 108 }
 109
 110 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
 111 #ifdef HTDATATYPE
 112 , HTDATATYPE data
 113 #endif
 114 )
 115 {
 116     unsigned int hash = ht->fn(key) % ht->numBuckets;
 117     Bucket b = ht->buckets[hash];
 118 #ifdef HTDATATYPE
 119     Bucket * b_addr = ht->buckets + hash;
 120 #endif
 121
 122     if (b == NULL) {
 123         ht->bucketCount += 1;
 124     }
 125
 126     while (b && ht->eq(b->key, key)) {
 127 #ifdef HTDATATYPE
 128         b_addr = &(b->next);
 129 #endif
 130         b = b->next;
 131     }
 132
 133     if (b == NULL) {
 134         ht->keyCount += 1;
 135         b = xmalloc(sizeof(*b));
 136         b->key = key;
 137 #ifdef HTDATATYPE
 138         b->dataCount = 1;
 139         b->data[0] = data;
 140 #endif
 141         b->next = ht->buckets[hash];
 142         ht->buckets[hash] = b;
 143     }
 144 #ifdef HTDATATYPE
 145     else {
 146         // resizing bucket TODO: increase exponentially
 147         // Bucket_s already contains space for one dataset
 148         b = *b_addr = xrealloc(
 149             b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
 150         // though increasing dataCount after the resize
 151         b->data[b->dataCount++] = data;
 152     }
 153     ht->dataCount += 1;
 154 #endif
 155     if (ht->keyCount > ht->numBuckets) {
 156         HASHPREFIX(Resize)(ht, ht->numBuckets * 2);
 157     }
 158 }
 159
 160 void HASHPREFIX(Empty)( HASHTYPE ht)
 161 {
 162     Bucket b, n;
 163     int i;
 164
 165     if (ht->bucketCount == 0) return;
 166
 167     for (i = 0; i < ht->numBuckets; i++) {
 168         b = ht->buckets[i];
 169         if (b == NULL)
 170             continue;
 171         ht->buckets[i] = NULL;
 172
 173         do {
 174             n = b->next;
 175             if (ht->freeKey)
 176                 b->key = ht->freeKey(b->key);
 177 #ifdef HTDATATYPE
 178             if (ht->freeData) {
 179                 int j;
 180                 for (j=0; j < b->dataCount; j++ ) {
 181                     b->data[j] = ht->freeData(b->data[j]);
 182                 }
 183             }
 184 #endif
 185             b = _free(b);
 186         } while ((b = n) != NULL);
 187     }
 188     ht->bucketCount = 0;
 189     ht->keyCount = 0;
 190 #ifdef HTDATATYPE
 191     ht->dataCount = 0;
 192 #endif
 193 }
 194
 195 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
 196 {
 197     if (ht==NULL)
 198         return ht;
 199     HASHPREFIX(Empty)(ht);
 200     ht->buckets = _free(ht->buckets);
 201     ht = _free(ht);
 202
 203     return NULL;
 204 }
 205
 206 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
 207 {
 208     Bucket b;
 209
 210     if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
 211 }
 212
 213 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
 214 #ifdef HTDATATYPE
 215                          HTDATATYPE** data, int * dataCount,
 216 #endif
 217                          HTKEYTYPE* tableKey)
 218 {
 219     Bucket b;
 220     int rc = ((b = HASHPREFIX(findEntry)(ht, key)) != NULL);
 221
 222 #ifdef HTDATATYPE
 223     if (data)
 224         *data = rc ? b->data : NULL;
 225     if (dataCount)
 226         *dataCount = rc ? b->dataCount : 0;
 227 #endif
 228     if (tableKey && rc)
 229         *tableKey = b->key;
 230
 231     return rc;
 232 }
 233
 234 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht) {
 235     return ht->numBuckets;
 236 }
 237
 238 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht) {
 239     return ht->bucketCount;
 240 }
 241
 242 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht) {
 243     return ht->keyCount;
 244 }
 245
 246 #ifdef HTDATATYPE
 247 unsigned int HASHPREFIX(NumData)(HASHTYPE ht) {
 248     return ht->dataCount;
 249 }
 250 #endif
 251
 252
 253 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
 254     int i;
 255     Bucket bucket;
 256
 257     int hashcnt=0, bucketcnt=0, datacnt=0;
 258     int maxbuckets=0;
 259
 260     for (i=0; i<ht->numBuckets; i++) {
 261         int buckets = 0;
 262         for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
 263             buckets++;
 264 #ifdef HTDATATYPE
 265             datacnt += bucket->dataCount;
 266 #endif
 267         }
 268         if (maxbuckets < buckets) maxbuckets = buckets;
 269         if (buckets) hashcnt++;
 270         bucketcnt += buckets;
 271     }
 272     fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
 273     fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
 274     fprintf(stderr, "Keys: %i\n", bucketcnt);
 275     fprintf(stderr, "Values: %i\n", datacnt);
 276     fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);
 277 }