Bug Summary

File:lib/./rpmhash.C
Warning:line 215, column 5
Value stored to 'ht' is never read

Annotated Source Code

1/**
2 * \file lib/rpmhash.c
3 * Hash table implemenation
4 */
5
6#include "system.h"
7#include <stdio.h>
8#include "debug.h"
9
10#define BucketHASHTYPEBuket JOIN(HASHTYPE,Buket)HASHTYPEBuket
11#define Bucket_sHASHTYPEBuket_s JOIN(HASHTYPE,Buket_s)HASHTYPEBuket_s
12
13typedef struct Bucket_sHASHTYPEBuket_s * BucketHASHTYPEBuket;
14
15/**
16 */
17struct Bucket_sHASHTYPEBuket_s {
18 BucketHASHTYPEBuket next; /*!< pointer to next item in bucket */
19 HTKEYTYPE key; /*!< hash key */
20#ifdef HTDATATYPE
21 int dataCount; /*!< data entries */
22 HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
23#endif
24};
25
26/**
27 */
28struct HASHSTRUCTHASHTYPE_s {
29 int numBuckets; /*!< number of hash buckets */
30 BucketHASHTYPEBuket * buckets; /*!< hash bucket array */
31 hashFunctionTypeHASHTYPEHashFunctionType fn; /*!< generate hash value for key */
32 hashEqualityTypeHASHTYPEHashEqualityType eq; /*!< compare hash keys for equality */
33 hashFreeKeyHASHTYPEFreeKey freeKey;
34 int bucketCount; /*!< number of used buckets */
35 int keyCount; /*!< number of keys */
36#ifdef HTDATATYPE
37 int dataCount; /*!< number of data entries */
38 hashFreeDataHASHTYPEFreeData freeData;
39#endif
40};
41
42/**
43 * Find entry in hash table.
44 * @param ht pointer to hash table
45 * @param key pointer to key value
46 * @param keyHash key hash
47 * @return pointer to hash bucket of key (or NULL)
48 */
49static
50BucketHASHTYPEBuket HASHPREFIX(findEntry)HASHTYPEfindEntry(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
51{
52 unsigned int hash = keyHash % ht->numBuckets;
53 BucketHASHTYPEBuket b = ht->buckets[hash];
54
55 while (b && ht->eq(b->key, key))
56 b = b->next;
57
58 return b;
59}
60
61HASHTYPE HASHPREFIX(Create)HASHTYPECreate(int numBuckets,
62 hashFunctionTypeHASHTYPEHashFunctionType fn, hashEqualityTypeHASHTYPEHashEqualityType eq,
63 hashFreeKeyHASHTYPEFreeKey freeKey
64#ifdef HTDATATYPE
65, hashFreeDataHASHTYPEFreeData freeData
66#endif
67)
68{
69 HASHTYPE ht;
70
71 ht = xmalloc(sizeof(*ht))rmalloc((sizeof(*ht)));
72 ht->numBuckets = numBuckets > 11 ? numBuckets : 11;
73 ht->buckets = xcalloc(ht->numBuckets, sizeof(*ht->buckets))rcalloc((ht->numBuckets), (sizeof(*ht->buckets)));
74 ht->freeKey = freeKey;
75#ifdef HTDATATYPE
76 ht->freeData = freeData;
77 ht->dataCount = 0;
78#endif
79 ht->fn = fn;
80 ht->eq = eq;
81 ht->bucketCount = ht->keyCount = 0;
82 return ht;
83}
84
85static void HASHPREFIX(Resize)HASHTYPEResize(HASHTYPE ht, int numBuckets) {
86 BucketHASHTYPEBuket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets))rcalloc((numBuckets), (sizeof(*ht->buckets)));
87
88 for (int i=0; i<ht->numBuckets; i++) {
89 BucketHASHTYPEBuket b = ht->buckets[i];
90 BucketHASHTYPEBuket nextB;
91 while (b != NULL((void*)0)) {
92 unsigned int hash = ht->fn(b->key) % numBuckets;
93 nextB = b->next;
94 b->next = buckets[hash];
95 buckets[hash] = b;
96 b = nextB;
97 }
98 }
99 free(ht->buckets);
100 ht->buckets = buckets;
101 ht->numBuckets = numBuckets;
102}
103
104unsigned int HASHPREFIX(KeyHash)HASHTYPEKeyHash(HASHTYPE ht, HTKEYTYPE key)
105{
106 return ht->fn(key);
107}
108
109void HASHPREFIX(AddHEntry)HASHTYPEAddHEntry(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash
110#ifdef HTDATATYPE
111, HTDATATYPE data
112#endif
113)
114{
115 unsigned int hash = keyHash % ht->numBuckets;
116 BucketHASHTYPEBuket b = ht->buckets[hash];
117#ifdef HTDATATYPE
118 BucketHASHTYPEBuket * b_addr = ht->buckets + hash;
119#endif
120
121 if (b == NULL((void*)0)) {
122 ht->bucketCount += 1;
123 }
124
125 while (b && ht->eq(b->key, key)) {
126#ifdef HTDATATYPE
127 b_addr = &(b->next);
128#endif
129 b = b->next;
130 }
131
132 if (b == NULL((void*)0)) {
133 ht->keyCount += 1;
134 b = xmalloc(sizeof(*b))rmalloc((sizeof(*b)));
135 b->key = key;
136#ifdef HTDATATYPE
137 b->dataCount = 1;
138 b->data[0] = data;
139#endif
140 b->next = ht->buckets[hash];
141 ht->buckets[hash] = b;
142 }
143#ifdef HTDATATYPE
144 else {
145 if (ht->freeKey)
146 ht->freeKey(key);
147 // resizing bucket TODO: increase exponentially
148 // Bucket_s already contains space for one dataset
149 b = *b_addr = xrealloc(rrealloc((b), (sizeof(*b) + sizeof(b->data[0]) * (b->dataCount
)))
150 b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount))rrealloc((b), (sizeof(*b) + sizeof(b->data[0]) * (b->dataCount
)));
151 // though increasing dataCount after the resize
152 b->data[b->dataCount++] = data;
153 }
154 ht->dataCount += 1;
155#endif
156 if (ht->keyCount > ht->numBuckets) {
157 HASHPREFIX(Resize)HASHTYPEResize(ht, ht->numBuckets * 2);
158 }
159}
160
161void HASHPREFIX(AddEntry)HASHTYPEAddEntry(HASHTYPE ht, HTKEYTYPE key
162#ifdef HTDATATYPE
163, HTDATATYPE data
164#endif
165)
166{
167#ifdef HTDATATYPE
168 HASHPREFIX(AddHEntry)HASHTYPEAddHEntry(ht, key, ht->fn(key), data);
169#else
170 HASHPREFIX(AddHEntry)HASHTYPEAddHEntry(ht, key, ht->fn(key));
171#endif
172}
173
174void HASHPREFIX(Empty)HASHTYPEEmpty( HASHTYPE ht)
175{
176 BucketHASHTYPEBuket b, n;
177 int i;
178
179 if (ht->bucketCount == 0) return;
180
181 for (i = 0; i < ht->numBuckets; i++) {
182 b = ht->buckets[i];
183 if (b == NULL((void*)0))
184 continue;
185 ht->buckets[i] = NULL((void*)0);
186
187 do {
188 n = b->next;
189 if (ht->freeKey)
190 b->key = ht->freeKey(b->key);
191#ifdef HTDATATYPE
192 if (ht->freeData) {
193 int j;
194 for (j=0; j < b->dataCount; j++ ) {
195 b->data[j] = ht->freeData(b->data[j]);
196 }
197 }
198#endif
199 b = _free(b)rfree((b));
200 } while ((b = n) != NULL((void*)0));
201 }
202 ht->bucketCount = 0;
203 ht->keyCount = 0;
204#ifdef HTDATATYPE
205 ht->dataCount = 0;
206#endif
207}
208
209HASHTYPE HASHPREFIX(Free)HASHTYPEFree(HASHTYPE ht)
210{
211 if (ht==NULL((void*)0))
212 return ht;
213 HASHPREFIX(Empty)HASHTYPEEmpty(ht);
214 ht->buckets = _free(ht->buckets)rfree((ht->buckets));
215 ht = _free(ht)rfree((ht));
Value stored to 'ht' is never read
216
217 return NULL((void*)0);
218}
219
220int HASHPREFIX(HasHEntry)HASHTYPEHasHEntry(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
221{
222 BucketHASHTYPEBuket b;
223
224 if (!(b = HASHPREFIX(findEntry)HASHTYPEfindEntry(ht, key, keyHash))) return 0; else return 1;
225}
226
227int HASHPREFIX(HasEntry)HASHTYPEHasEntry(HASHTYPE ht, HTKEYTYPE key)
228{
229 return HASHPREFIX(HasHEntry)HASHTYPEHasHEntry(ht, key, ht->fn(key));
230}
231
232int HASHPREFIX(GetHEntry)HASHTYPEGetHEntry(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash,
233#ifdef HTDATATYPE
234 HTDATATYPE** data, int * dataCount,
235#endif
236 HTKEYTYPE* tableKey)
237{
238 BucketHASHTYPEBuket b;
239 int rc = ((b = HASHPREFIX(findEntry)HASHTYPEfindEntry(ht, key, keyHash)) != NULL((void*)0));
240
241#ifdef HTDATATYPE
242 if (data)
243 *data = rc ? b->data : NULL((void*)0);
244 if (dataCount)
245 *dataCount = rc ? b->dataCount : 0;
246#endif
247 if (tableKey && rc)
248 *tableKey = b->key;
249
250 return rc;
251}
252
253int HASHPREFIX(GetEntry)HASHTYPEGetEntry(HASHTYPE ht, HTKEYTYPE key,
254#ifdef HTDATATYPE
255 HTDATATYPE** data, int * dataCount,
256#endif
257 HTKEYTYPE* tableKey)
258{
259 return HASHPREFIX(GetHEntry)HASHTYPEGetHEntry(ht, key, ht->fn(key),
260#ifdef HTDATATYPE
261 data, dataCount,
262#endif
263 tableKey);
264}
265
266unsigned int HASHPREFIX(NumBuckets)HASHTYPENumBuckets(HASHTYPE ht) {
267 return ht->numBuckets;
268}
269
270unsigned int HASHPREFIX(UsedBuckets)HASHTYPEUsedBuckets(HASHTYPE ht) {
271 return ht->bucketCount;
272}
273
274unsigned int HASHPREFIX(NumKeys)HASHTYPENumKeys(HASHTYPE ht) {
275 return ht->keyCount;
276}
277
278#ifdef HTDATATYPE
279unsigned int HASHPREFIX(NumData)HASHTYPENumData(HASHTYPE ht) {
280 return ht->dataCount;
281}
282#endif
283
284
285void HASHPREFIX(PrintStats)HASHTYPEPrintStats(HASHTYPE ht) {
286 int i;
287 BucketHASHTYPEBuket bucket;
288
289 int hashcnt=0, bucketcnt=0, datacnt=0;
290 int maxbuckets=0;
291
292 for (i=0; i<ht->numBuckets; i++) {
293 int buckets = 0;
294 for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
295 buckets++;
296#ifdef HTDATATYPE
297 datacnt += bucket->dataCount;
298#endif
299 }
300 if (maxbuckets < buckets) maxbuckets = buckets;
301 if (buckets) hashcnt++;
302 bucketcnt += buckets;
303 }
304 fprintf(stderrstderr, "Hashsize: %i\n", ht->numBuckets);
305 fprintf(stderrstderr, "Hashbuckets: %i\n", hashcnt);
306 fprintf(stderrstderr, "Keys: %i\n", bucketcnt);
307 fprintf(stderrstderr, "Values: %i\n", datacnt);
308 fprintf(stderrstderr, "Max Keys/Bucket: %i\n", maxbuckets);
309}