Go to the documentation of this file.00001
00006 #include "system.h"
00007 #include <rpmhash.h>
00008 #include "debug.h"
00009
00010 typedef const void * voidptr;
00011
00012 typedef struct hashBucket_s * hashBucket;
00013
00016 struct hashBucket_s {
00017 voidptr key;
00018 voidptr * data;
00019 int dataCount;
00020 hashBucket next;
00021 };
00022
00025 struct hashTable_s {
00026 int numBuckets;
00027 size_t keySize;
00028 int freeData;
00029 hashBucket * buckets;
00030 hashFunctionType fn;
00031 hashEqualityType eq;
00032 };
00033
00039 static inline void *
00040 _free( const void * p)
00041 {
00042 if (p != NULL) free((void *)p);
00043 return NULL;
00044 }
00045
00052 static
00053 hashBucket findEntry(hashTable ht, const void * key)
00054
00055 {
00056 uint32_t hash = 0;
00057 hashBucket b;
00058
00059
00060 hash = ht->fn(hash, key, 0) % ht->numBuckets;
00061 b = ht->buckets[hash];
00062
00063 while (b && b->key && ht->eq(b->key, key))
00064 b = b->next;
00065
00066
00067 return b;
00068 }
00069
00077 static uint32_t hashFunctionString(uint32_t h, const void * data, size_t size)
00078
00079 {
00080 const char *key = data;
00081
00082 if (size == 0)
00083 size = strlen(key);
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119 if (h == 0)
00120 h = 5381;
00121 for (; size >= 8; size -= 8) {
00122 h = ((h << 5) + h) + (uint32_t)*key++;
00123 h = ((h << 5) + h) + (uint32_t)*key++;
00124 h = ((h << 5) + h) + (uint32_t)*key++;
00125 h = ((h << 5) + h) + (uint32_t)*key++;
00126 h = ((h << 5) + h) + (uint32_t)*key++;
00127 h = ((h << 5) + h) + (uint32_t)*key++;
00128 h = ((h << 5) + h) + (uint32_t)*key++;
00129 h = ((h << 5) + h) + (uint32_t)*key++;
00130 }
00131 switch (size) {
00132 case 7: h = ((h << 5) + h) + (uint32_t)*key++;
00133 case 6: h = ((h << 5) + h) + (uint32_t)*key++;
00134 case 5: h = ((h << 5) + h) + (uint32_t)*key++;
00135 case 4: h = ((h << 5) + h) + (uint32_t)*key++;
00136 case 3: h = ((h << 5) + h) + (uint32_t)*key++;
00137 case 2: h = ((h << 5) + h) + (uint32_t)*key++;
00138 case 1: h = ((h << 5) + h) + (uint32_t)*key++; break;
00139 default: break;
00140 }
00141
00142 return h;
00143 }
00144
00151 static int hashEqualityString(const void * key1, const void * key2)
00152
00153 {
00154 const char *k1 = (const char *)key1;
00155 const char *k2 = (const char *)key2;
00156 return strcmp(k1, k2);
00157 }
00158
00159 hashTable htCreate(int numBuckets, size_t keySize, int freeData,
00160 hashFunctionType fn, hashEqualityType eq)
00161 {
00162 hashTable ht;
00163
00164 ht = xmalloc(sizeof(*ht));
00165 ht->numBuckets = numBuckets;
00166 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
00167 ht->keySize = keySize;
00168 ht->freeData = freeData;
00169
00170 ht->fn = (fn != NULL ? fn : hashFunctionString);
00171 ht->eq = (eq != NULL ? eq : hashEqualityString);
00172
00173
00174 return ht;
00175 }
00176
00177 void htAddEntry(hashTable ht, const void * key, const void * data)
00178 {
00179 uint32_t hash = 0;
00180 hashBucket b;
00181
00182 hash = ht->fn(hash, key, 0) % ht->numBuckets;
00183 b = ht->buckets[hash];
00184
00185 while (b && b->key && ht->eq(b->key, key))
00186 b = b->next;
00187
00188 if (b == NULL) {
00189 b = xmalloc(sizeof(*b));
00190 if (ht->keySize) {
00191 char *k = xmalloc(ht->keySize);
00192 memcpy(k, key, ht->keySize);
00193 b->key = k;
00194 } else {
00195 b->key = key;
00196 }
00197 b->dataCount = 0;
00198 b->next = ht->buckets[hash];
00199 b->data = NULL;
00200 ht->buckets[hash] = b;
00201 }
00202
00203 b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
00204 b->data[b->dataCount++] = data;
00205 }
00206
00207 hashTable htFree(hashTable ht)
00208 {
00209 hashBucket b, n;
00210 int i;
00211
00212 for (i = 0; i < ht->numBuckets; i++) {
00213 b = ht->buckets[i];
00214 if (b == NULL)
00215 continue;
00216 ht->buckets[i] = NULL;
00217 if (ht->keySize > 0)
00218 b->key = _free(b->key);
00219 do {
00220 n = b->next;
00221 if (b->data) {
00222 if (ht->freeData)
00223 *b->data = _free(*b->data);
00224 b->data = _free(b->data);
00225 }
00226 b = _free(b);
00227 } while ((b = n) != NULL);
00228 }
00229
00230 ht->buckets = _free(ht->buckets);
00231 ht = _free(ht);
00232 return NULL;
00233 }
00234
00235 int htHasEntry(hashTable ht, const void * key)
00236 {
00237 hashBucket b;
00238
00239 if (!(b = findEntry(ht, key))) return 0; else return 1;
00240 }
00241
00242 int htGetEntry(hashTable ht, const void * key, const void * data,
00243 int * dataCount, const void * tableKey)
00244 {
00245 hashBucket b;
00246
00247 if ((b = findEntry(ht, key)) == NULL)
00248 return 1;
00249
00250 if (data)
00251 *(const void ***)data = (const void **) b->data;
00252 if (dataCount)
00253 *dataCount = b->dataCount;
00254 if (tableKey)
00255 *(const void **)tableKey = b->key;
00256
00257 return 0;
00258 }