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