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