00001
00006 #include "system.h"
00007 #include <rpmlib.h>
00008 #include "rpmhash.h"
00009 #include "debug.h"
00010
00011 typedef const void * voidptr;
00012
00014 struct hashBucket {
00015 voidptr key;
00016 voidptr * data;
00017 int dataCount;
00018 struct hashBucket * next;
00019 };
00020
00022 struct hashTable_s {
00023 int numBuckets;
00024 int keySize;
00025 int freeData;
00026 struct hashBucket ** buckets;
00027 hashFunctionType fn;
00028 hashEqualityType eq;
00029 };
00030
00037 static
00038 struct hashBucket *findEntry(hashTable ht, const void * key)
00039
00040 {
00041 unsigned int hash;
00042 struct hashBucket * b;
00043
00044
00045 hash = ht->fn(key) % ht->numBuckets;
00046 b = ht->buckets[hash];
00047
00048 while (b && b->key && ht->eq(b->key, key))
00049 b = b->next;
00050
00051
00052 return b;
00053 }
00054
00055 int hashEqualityString(const void * key1, const void * key2)
00056 {
00057 const char *k1 = (const char *)key1;
00058 const char *k2 = (const char *)key2;
00059 return strcmp(k1, k2);
00060 }
00061
00062 unsigned int hashFunctionString(const void * string)
00063 {
00064 char xorValue = 0;
00065 char sum = 0;
00066 short len;
00067 int i;
00068 const char * chp = string;
00069
00070 len = strlen(string);
00071 for (i = 0; i < len; i++, chp++) {
00072 xorValue ^= *chp;
00073 sum += *chp;
00074 }
00075
00076 return ((((unsigned)len) << 16) + (((unsigned)sum) << 8) + xorValue);
00077 }
00078
00079 hashTable htCreate(int numBuckets, int keySize, int freeData, hashFunctionType fn,
00080 hashEqualityType eq)
00081 {
00082 hashTable ht;
00083
00084 ht = xmalloc(sizeof(*ht));
00085 ht->numBuckets = numBuckets;
00086 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
00087 ht->keySize = keySize;
00088 ht->freeData = freeData;
00089 ht->fn = fn;
00090 ht->eq = eq;
00091
00092 return ht;
00093 }
00094
00095 void htAddEntry(hashTable ht, const void * key, const void * data)
00096 {
00097 unsigned int hash;
00098 struct hashBucket * b;
00099
00100 hash = ht->fn(key) % ht->numBuckets;
00101 b = ht->buckets[hash];
00102
00103 while (b && b->key && ht->eq(b->key, key))
00104 b = b->next;
00105
00106 if (b == NULL) {
00107 b = xmalloc(sizeof(*b));
00108 if (ht->keySize) {
00109 char *k = xmalloc(ht->keySize);
00110 memcpy(k, key, ht->keySize);
00111 b->key = k;
00112 } else {
00113 b->key = key;
00114 }
00115 b->dataCount = 0;
00116 b->next = ht->buckets[hash];
00117 b->data = NULL;
00118 ht->buckets[hash] = b;
00119 }
00120
00121 b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
00122 b->data[b->dataCount++] = data;
00123 }
00124
00125 void htFree(hashTable ht)
00126 {
00127 struct hashBucket * b, * n;
00128 int i;
00129
00130 for (i = 0; i < ht->numBuckets; i++) {
00131 b = ht->buckets[i];
00132 if (ht->keySize && b) free((void *)b->key);
00133 while (b) {
00134 n = b->next;
00135 if (b->data) {
00136 if (ht->freeData)
00137 *b->data = _free(*b->data);
00138 b->data = _free(b->data);
00139 }
00140 b = _free(b);
00141 b = n;
00142 }
00143 }
00144
00145 ht->buckets = _free(ht->buckets);
00146 ht = _free(ht);
00147 }
00148
00149 int htHasEntry(hashTable ht, const void * key)
00150 {
00151 struct hashBucket * b;
00152
00153 if (!(b = findEntry(ht, key))) return 0; else return 1;
00154 }
00155
00156 int htGetEntry(hashTable ht, const void * key, const void *** data,
00157 int * dataCount, const void ** tableKey)
00158 {
00159 struct hashBucket * b;
00160
00161 if ((b = findEntry(ht, key)) == NULL)
00162 return 1;
00163
00164 if (data)
00165 *data = (const void **) b->data;
00166 if (dataCount)
00167 *dataCount = b->dataCount;
00168 if (tableKey)
00169 *tableKey = b->key;
00170
00171 return 0;
00172 }