Go to the documentation of this file.00001
00006 #include "system.h"
00007 #include <rpmiotypes.h>
00008 #include <rpmio.h>
00009 #include <rpmhash.h>
00010 #include "debug.h"
00011
00012
00013 int _ht_debug = 0;
00014
00015 typedef const void * voidptr;
00016
00017 typedef struct hashBucket_s * hashBucket;
00018
00021 struct hashBucket_s {
00022 voidptr key;
00023 voidptr * data;
00024 int dataCount;
00025 hashBucket next;
00026 };
00027
00030 struct hashTable_s {
00031 struct rpmioItem_s _item;
00032 int numBuckets;
00033 size_t keySize;
00034 int freeData;
00035 hashBucket * buckets;
00036
00037 hashFunctionType fn;
00038
00039 hashEqualityType eq;
00040 #if defined(__LCLINT__)
00041
00042 int nrefs;
00043 #endif
00044 };
00045
00052 static
00053 hashBucket findEntry(hashTable ht, const void * key)
00054
00055 {
00056 rpmuint32_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
00070 int hashEqualityString(const void * key1, const void * key2)
00071 {
00072 const char *k1 = (const char *)key1;
00073 const char *k2 = (const char *)key2;
00074 return strcmp(k1, k2);
00075 }
00076
00077 rpmuint32_t hashFunctionString(rpmuint32_t h, const void * data, size_t size)
00078 {
00079 const char *key = data;
00080
00081 if (size == 0)
00082 size = strlen(key);
00083
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 if (h == 0)
00119 h = 5381;
00120 for (; size >= 8; size -= 8) {
00121 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00122 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00123 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00124 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00125 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00126 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00127 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00128 h = ((h << 5) + h) + (rpmuint32_t)*key++;
00129 }
00130 switch (size) {
00131 case 7: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00132 case 6: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00133 case 5: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00134 case 4: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00135 case 3: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00136 case 2: h = ((h << 5) + h) + (rpmuint32_t)*key++;
00137 case 1: h = ((h << 5) + h) + (rpmuint32_t)*key++; break;
00138 default: break;
00139 }
00140
00141 return h;
00142 }
00143
00144 void htAddEntry(hashTable ht, const void * key, const void * data)
00145 {
00146 rpmuint32_t hash = 0;
00147 hashBucket b;
00148
00149 hash = ht->fn(hash, key, 0) % ht->numBuckets;
00150 b = ht->buckets[hash];
00151
00152 while (b && b->key && ht->eq(b->key, key))
00153 b = b->next;
00154
00155 if (b == NULL) {
00156 b = xmalloc(sizeof(*b));
00157 if (ht->keySize) {
00158 char *k = xmalloc(ht->keySize);
00159 memcpy(k, key, ht->keySize);
00160 b->key = k;
00161 } else {
00162 b->key = key;
00163 }
00164 b->dataCount = 0;
00165 b->next = ht->buckets[hash];
00166 b->data = NULL;
00167 ht->buckets[hash] = b;
00168 }
00169
00170 b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
00171 b->data[b->dataCount++] = data;
00172 }
00173
00174 int htHasEntry(hashTable ht, const void * key)
00175 {
00176 hashBucket b;
00177
00178 if (!(b = findEntry(ht, key))) return 0; else return 1;
00179 }
00180
00181 int htGetEntry(hashTable ht, const void * key, const void * data,
00182 int * dataCount, const void * tableKey)
00183 {
00184 hashBucket b;
00185
00186 if ((b = findEntry(ht, key)) == NULL)
00187 return 1;
00188
00189 if (data)
00190 *(const void ***)data = (const void **) b->data;
00191 if (dataCount)
00192 *dataCount = b->dataCount;
00193 if (tableKey)
00194 *(const void **)tableKey = b->key;
00195
00196 return 0;
00197 }
00198
00199 const void ** htGetKeys(hashTable ht)
00200 {
00201 const void ** keys = xcalloc(ht->numBuckets+1, sizeof(const void*));
00202 const void ** keypointer = keys;
00203 hashBucket b, n;
00204 int i;
00205
00206 for (i = 0; i < ht->numBuckets; i++) {
00207 b = ht->buckets[i];
00208 if (b == NULL)
00209 continue;
00210 if (b->data)
00211 *(keys++) = b->key;
00212 do {
00213 n = b->next;
00214 if(n != NULL)
00215 *(keys++) = n->key;
00216 } while ((b = n) != NULL);
00217 }
00218
00219 return keypointer;
00220 }
00221
00222
00223 static void htFini(void * _ht)
00224
00225 {
00226 hashTable ht = _ht;
00227 hashBucket b, n;
00228 int i;
00229
00230 for (i = 0; i < ht->numBuckets; i++) {
00231 b = ht->buckets[i];
00232 if (b == NULL)
00233 continue;
00234 ht->buckets[i] = NULL;
00235 if (ht->keySize > 0)
00236 b->key = _free(b->key);
00237 do {
00238 n = b->next;
00239 if (b->data) {
00240 if (ht->freeData)
00241 *b->data = _free(*b->data);
00242 b->data = _free(b->data);
00243 }
00244 b = _free(b);
00245 } while ((b = n) != NULL);
00246 }
00247
00248 ht->buckets = _free(ht->buckets);
00249 }
00250
00251
00252
00253 rpmioPool _htPool;
00254
00255 static hashTable htGetPool( rpmioPool pool)
00256
00257
00258 {
00259 hashTable ht;
00260
00261 if (_htPool == NULL) {
00262 _htPool = rpmioNewPool("ht", sizeof(*ht), -1, _ht_debug,
00263 NULL, NULL, htFini);
00264 pool = _htPool;
00265 }
00266 return (hashTable) rpmioGetPool(pool, sizeof(*ht));
00267 }
00268
00269 hashTable htCreate(int numBuckets, size_t keySize, int freeData,
00270 hashFunctionType fn, hashEqualityType eq)
00271 {
00272 hashTable ht = htGetPool(_htPool);
00273
00274 ht->numBuckets = numBuckets;
00275 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
00276 ht->keySize = keySize;
00277 ht->freeData = freeData;
00278
00279 ht->fn = (fn != NULL ? fn : hashFunctionString);
00280 ht->eq = (eq != NULL ? eq : hashEqualityString);
00281
00282
00283 return htLink(ht);
00284 }