lib/rpmhash.C

   1 /**
   2  * \file lib/rpmhash.c
   3  * Hash table implemenation
   4  */
   5
   6 #include "system.h"
   7 #include <stdio.h>
   8 #include "debug.h"
   9
  10 #define Bucket JOIN(HASHTYPE,Buket)
  11 #define Bucket_s JOIN(HASHTYPE,Buket_s)
  12
  13 typedef struct  Bucket_s * Bucket;
  14
  15 /**
  16  */
  17 struct  Bucket_s {
  18     Bucket next;        /*!< pointer to next item in bucket */
  19     HTKEYTYPE key;      /*!< hash key */
  20 #ifdef HTDATATYPE
  21     int dataCount;      /*!< data entries */
  22     HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
  23 #endif
  24 };
  25
  26 /**
  27  */
  28 struct HASHSTRUCT {
  29     int numBuckets;                     /*!< number of hash buckets */
  30     Bucket * buckets;                   /*!< hash bucket array */
  31     hashFunctionType fn;                /*!< generate hash value for key */
  32     hashEqualityType eq;                /*!< compare hash keys for equality */
  33     hashFreeKey freeKey;
  34     int bucketCount;                    /*!< number of used buckets */
  35     int keyCount;                       /*!< number of keys */
  36 #ifdef HTDATATYPE
  37     int dataCount;                      /*!< number of data entries */
  38     hashFreeData freeData;
  39 #endif
  40 };
  41
  42 /**
  43  * Find entry in hash table.
  44  * @param ht            pointer to hash table
  45  * @param key           pointer to key value
  46  * @param keyHash       key hash
  47  * @return pointer to hash bucket of key (or NULL)
  48  */
  49 static
  50 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
  51 {
  52     unsigned int hash = keyHash % ht->numBuckets;
  53     Bucket b = ht->buckets[hash];
  54
  55     while (b && ht->eq(b->key, key))
  56         b = b->next;
  57
  58     return b;
  59 }
  60
  61 HASHTYPE HASHPREFIX(Create)(int numBuckets,
  62                             hashFunctionType fn, hashEqualityType eq,
  63                             hashFreeKey freeKey
  64 #ifdef HTDATATYPE
  65 , hashFreeData freeData
  66 #endif
  67 )
  68 {
  69     HASHTYPE ht;
  70
  71     ht = xmalloc(sizeof(*ht));
  72     ht->numBuckets = numBuckets > 11 ? numBuckets : 11;
  73     ht->buckets = xcalloc(ht->numBuckets, sizeof(*ht->buckets));
  74     ht->freeKey = freeKey;
  75 #ifdef HTDATATYPE
  76     ht->freeData = freeData;
  77     ht->dataCount = 0;
  78 #endif
  79     ht->fn = fn;
  80     ht->eq = eq;
  81     ht->bucketCount = ht->keyCount = 0;
  82     return ht;
  83 }
  84
  85 static void HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) {
  86     Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
  87
  88     for (int i=0; i<ht->numBuckets; i++) {
  89         Bucket b = ht->buckets[i];
  90         Bucket nextB;
  91         while (b != NULL) {
  92             unsigned int hash = ht->fn(b->key) % numBuckets;
  93             nextB = b->next;
  94             b->next = buckets[hash];
  95             buckets[hash] = b;
  96             b = nextB;
  97         }
  98     }
  99     free(ht->buckets);
 100     ht->buckets = buckets;
 101     ht->numBuckets = numBuckets;
 102 }
 103
 104 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key)
 105 {
 106     return ht->fn(key);
 107 }
 108
 109 void HASHPREFIX(AddHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash
 110 #ifdef HTDATATYPE
 111 , HTDATATYPE data
 112 #endif
 113 )
 114 {
 115     unsigned int hash = keyHash % ht->numBuckets;
 116     Bucket b = ht->buckets[hash];
 117 #ifdef HTDATATYPE
 118     Bucket * b_addr = ht->buckets + hash;
 119 #endif
 120
 121     if (b == NULL) {
 122         ht->bucketCount += 1;
 123     }
 124
 125     while (b && ht->eq(b->key, key)) {
 126 #ifdef HTDATATYPE
 127         b_addr = &(b->next);
 128 #endif
 129         b = b->next;
 130     }
 131
 132     if (b == NULL) {
 133         ht->keyCount += 1;
 134         b = xmalloc(sizeof(*b));
 135         b->key = key;
 136 #ifdef HTDATATYPE
 137         b->dataCount = 1;
 138         b->data[0] = data;
 139 #endif
 140         b->next = ht->buckets[hash];
 141         ht->buckets[hash] = b;
 142     }
 143 #ifdef HTDATATYPE
 144     else {
 145         if (ht->freeKey)
 146             ht->freeKey(key);
 147         // resizing bucket TODO: increase exponentially
 148         // Bucket_s already contains space for one dataset
 149         b = *b_addr = xrealloc(
 150             b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
 151         // though increasing dataCount after the resize
 152         b->data[b->dataCount++] = data;
 153     }
 154     ht->dataCount += 1;
 155 #endif
 156     if (ht->keyCount > ht->numBuckets) {
 157         HASHPREFIX(Resize)(ht, ht->numBuckets * 2);
 158     }
 159 }
 160
 161 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
 162 #ifdef HTDATATYPE
 163 , HTDATATYPE data
 164 #endif
 165 )
 166 {
 167 #ifdef HTDATATYPE
 168     HASHPREFIX(AddHEntry)(ht, key, ht->fn(key), data);
 169 #else
 170     HASHPREFIX(AddHEntry)(ht, key, ht->fn(key));
 171 #endif
 172 }
 173
 174 void HASHPREFIX(Empty)( HASHTYPE ht)
 175 {
 176     Bucket b, n;
 177     int i;
 178
 179     if (ht->bucketCount == 0) return;
 180
 181     for (i = 0; i < ht->numBuckets; i++) {
 182         b = ht->buckets[i];
 183         if (b == NULL)
 184             continue;
 185         ht->buckets[i] = NULL;
 186
 187         do {
 188             n = b->next;
 189             if (ht->freeKey)
 190                 b->key = ht->freeKey(b->key);
 191 #ifdef HTDATATYPE
 192             if (ht->freeData) {
 193                 int j;
 194                 for (j=0; j < b->dataCount; j++ ) {
 195                     b->data[j] = ht->freeData(b->data[j]);
 196                 }
 197             }
 198 #endif
 199             b = _free(b);
 200         } while ((b = n) != NULL);
 201     }
 202     ht->bucketCount = 0;
 203     ht->keyCount = 0;
 204 #ifdef HTDATATYPE
 205     ht->dataCount = 0;
 206 #endif
 207 }
 208
 209 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
 210 {
 211     if (ht==NULL)
 212         return ht;
 213     HASHPREFIX(Empty)(ht);
 214     ht->buckets = _free(ht->buckets);
 215     ht = _free(ht);
 216
 217     return NULL;
 218 }
 219
 220 int HASHPREFIX(HasHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
 221 {
 222     Bucket b;
 223
 224     if (!(b = HASHPREFIX(findEntry)(ht, key, keyHash))) return 0; else return 1;
 225 }
 226
 227 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
 228 {
 229     return HASHPREFIX(HasHEntry)(ht, key, ht->fn(key));
 230 }
 231
 232 int HASHPREFIX(GetHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash,
 233 #ifdef HTDATATYPE
 234                          HTDATATYPE** data, int * dataCount,
 235 #endif
 236                          HTKEYTYPE* tableKey)
 237 {
 238     Bucket b;
 239     int rc = ((b = HASHPREFIX(findEntry)(ht, key, keyHash)) != NULL);
 240
 241 #ifdef HTDATATYPE
 242     if (data)
 243         *data = rc ? b->data : NULL;
 244     if (dataCount)
 245         *dataCount = rc ? b->dataCount : 0;
 246 #endif
 247     if (tableKey && rc)
 248         *tableKey = b->key;
 249
 250     return rc;
 251 }
 252
 253 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
 254 #ifdef HTDATATYPE
 255                          HTDATATYPE** data, int * dataCount,
 256 #endif
 257                          HTKEYTYPE* tableKey)
 258 {
 259     return HASHPREFIX(GetHEntry)(ht, key, ht->fn(key),
 260 #ifdef HTDATATYPE
 261                                  data, dataCount,
 262 #endif
 263                                  tableKey);
 264 }
 265
 266 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht) {
 267     return ht->numBuckets;
 268 }
 269
 270 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht) {
 271     return ht->bucketCount;
 272 }
 273
 274 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht) {
 275     return ht->keyCount;
 276 }
 277
 278 #ifdef HTDATATYPE
 279 unsigned int HASHPREFIX(NumData)(HASHTYPE ht) {
 280     return ht->dataCount;
 281 }
 282 #endif
 283
 284
 285 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
 286     int i;
 287     Bucket bucket;
 288
 289     int hashcnt=0, bucketcnt=0, datacnt=0;
 290     int maxbuckets=0;
 291
 292     for (i=0; i<ht->numBuckets; i++) {
 293         int buckets = 0;
 294         for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
 295             buckets++;
 296 #ifdef HTDATATYPE
 297             datacnt += bucket->dataCount;
 298 #endif
 299         }
 300         if (maxbuckets < buckets) maxbuckets = buckets;
 301         if (buckets) hashcnt++;
 302         bucketcnt += buckets;
 303     }
 304     fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
 305     fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
 306     fprintf(stderr, "Keys: %i\n", bucketcnt);
 307     fprintf(stderr, "Values: %i\n", datacnt);
 308     fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);
 309 }