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