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 int 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
00062 b = ht->buckets[hash];
00063
00064
00065 while (b && b->key && ht->eq(b->key, key))
00066 b = b->next;
00067
00068
00069 return b;
00070 }
00071
00079 static uint32_t hashFunctionString(uint32_t h, const void * data, size_t size)
00080
00081 {
00082 const char * chp = data;
00083 unsigned char sum = 0;
00084 unsigned char xor = 0;
00085 int i;
00086
00087 if (size == 0)
00088 size = strlen(chp);
00089
00090 for (i = 0; i < size; i++, chp++) {
00091 xor ^= *chp;
00092 sum += *chp;
00093 }
00094
00095
00096 h += ((size << 16) + (sum << 8) + xor);
00097
00098 return h;
00099 }
00100
00107 static int hashEqualityString(const void * key1, const void * key2)
00108
00109 {
00110 const char *k1 = (const char *)key1;
00111 const char *k2 = (const char *)key2;
00112 return strcmp(k1, k2);
00113 }
00114
00115 hashTable htCreate(int numBuckets, int keySize, int freeData,
00116 hashFunctionType fn, hashEqualityType eq)
00117 {
00118 hashTable ht;
00119
00120 ht = xmalloc(sizeof(*ht));
00121 ht->numBuckets = numBuckets;
00122 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
00123 ht->keySize = keySize;
00124 ht->freeData = freeData;
00125
00126 ht->fn = (fn != NULL ? fn : hashFunctionString);
00127 ht->eq = (eq != NULL ? eq : hashEqualityString);
00128
00129
00130 return ht;
00131 }
00132
00133
00134 void htAddEntry(hashTable ht, const void * key, const void * data)
00135 {
00136 uint32_t hash = 0;
00137 hashBucket b;
00138
00139 hash = ht->fn(hash, key, 0) % ht->numBuckets;
00140 b = ht->buckets[hash];
00141
00142 while (b && b->key && ht->eq(b->key, key))
00143 b = b->next;
00144
00145
00146 if (b == NULL) {
00147 b = xmalloc(sizeof(*b));
00148 if (ht->keySize) {
00149 char *k = xmalloc(ht->keySize);
00150 memcpy(k, key, ht->keySize);
00151 b->key = k;
00152 } else {
00153 b->key = key;
00154 }
00155 b->dataCount = 0;
00156 b->next = ht->buckets[hash];
00157 b->data = NULL;
00158 ht->buckets[hash] = b;
00159 }
00160
00161
00162 b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
00163 b->data[b->dataCount++] = data;
00164 }
00165
00166
00167 hashTable htFree(hashTable ht)
00168 {
00169 hashBucket b, n;
00170 int i;
00171
00172 for (i = 0; i < ht->numBuckets; i++) {
00173
00174 b = ht->buckets[i];
00175
00176 if (b == NULL)
00177 continue;
00178
00179 ht->buckets[i] = NULL;
00180
00181 if (ht->keySize > 0)
00182 b->key = _free(b->key);
00183 do {
00184 n = b->next;
00185
00186 if (b->data) {
00187
00188 if (ht->freeData)
00189 *b->data = _free(*b->data);
00190
00191 b->data = _free(b->data);
00192 }
00193
00194 b = _free(b);
00195 } while ((b = n) != NULL);
00196 }
00197
00198 ht->buckets = _free(ht->buckets);
00199 ht = _free(ht);
00200 return NULL;
00201 }
00202
00203 int htHasEntry(hashTable ht, const void * key)
00204 {
00205 hashBucket b;
00206
00207 if (!(b = findEntry(ht, key))) return 0; else return 1;
00208 }
00209
00210 int htGetEntry(hashTable ht, const void * key, const void *** data,
00211 int * dataCount, const void ** tableKey)
00212 {
00213 hashBucket b;
00214
00215 if ((b = findEntry(ht, key)) == NULL)
00216 return 1;
00217
00218
00219 if (data)
00220 *data = (const void **) b->data;
00221 if (dataCount)
00222 *dataCount = b->dataCount;
00223 if (tableKey)
00224 *tableKey = b->key;
00225
00226
00227 return 0;
00228 }