rpm  4.5
rpmhash.c
Go to the documentation of this file.
1 
6 #include "system.h"
7 #include <rpmhash.h>
8 #include "debug.h"
9 
10 typedef /*@owned@*/ const void * voidptr;
11 
12 typedef struct hashBucket_s * hashBucket;
13 
16 struct hashBucket_s {
18 /*@owned@*/ voidptr * data;
19  int dataCount;
20 /*@dependent@*/hashBucket next;
21 };
22 
25 struct hashTable_s {
26  int numBuckets;
27  int keySize;
28  int freeData;
29  hashBucket * buckets;
32 };
33 
39 /*@unused@*/ static inline /*@null@*/ void *
40 _free(/*@only@*/ /*@null@*/ const void * p) /*@modifies p@*/
41 {
42  if (p != NULL) free((void *)p);
43  return NULL;
44 }
45 
52 static /*@shared@*/ /*@null@*/
53 hashBucket findEntry(hashTable ht, const void * key)
54  /*@*/
55 {
56  uint32_t hash = 0;
57  hashBucket b;
58 
59  /*@-modunconnomods@*/
60  hash = ht->fn(hash, key, 0) % ht->numBuckets;
61 /*@-boundsread@*/
62  b = ht->buckets[hash];
63 /*@=boundsread@*/
64 
65  while (b && b->key && ht->eq(b->key, key))
66  b = b->next;
67  /*@=modunconnomods@*/
68 
69  return b;
70 }
71 
79 static uint32_t hashFunctionString(uint32_t h, const void * data, size_t size)
80  /*@*/
81 {
82  const char * chp = data;
83  unsigned char sum = 0;
84  unsigned char xor = 0;
85  int i;
86 
87  if (size == 0)
88  size = strlen(chp);
89 /*@-boundsread@*/
90  for (i = 0; i < size; i++, chp++) {
91  xor ^= *chp;
92  sum += *chp;
93  }
94 /*@=boundsread@*/
95 
96  h += ((size << 16) + (sum << 8) + xor);
97 
98  return h;
99 }
100 
107 static int hashEqualityString(const void * key1, const void * key2)
108  /*@*/
109 {
110  const char *k1 = (const char *)key1;
111  const char *k2 = (const char *)key2;
112  return strcmp(k1, k2);
113 }
114 
115 hashTable htCreate(int numBuckets, int keySize, int freeData,
117 {
118  hashTable ht;
119 
120  ht = xmalloc(sizeof(*ht));
121  ht->numBuckets = numBuckets;
122  ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
123  ht->keySize = keySize;
124  ht->freeData = freeData;
125  /*@-assignexpose@*/
126  ht->fn = (fn != NULL ? fn : hashFunctionString);
127  ht->eq = (eq != NULL ? eq : hashEqualityString);
128  /*@=assignexpose@*/
129 
130  return ht;
131 }
132 
133 /*@-boundswrite@*/
134 void htAddEntry(hashTable ht, const void * key, const void * data)
135 {
136  uint32_t hash = 0;
137  hashBucket b;
138 
139  hash = ht->fn(hash, key, 0) % ht->numBuckets;
140  b = ht->buckets[hash];
141 
142  while (b && b->key && ht->eq(b->key, key))
143  b = b->next;
144 
145  /*@-branchstate@*/
146  if (b == NULL) {
147  b = xmalloc(sizeof(*b));
148  if (ht->keySize) {
149  char *k = xmalloc(ht->keySize);
150  memcpy(k, key, ht->keySize);
151  b->key = k;
152  } else {
153  b->key = key;
154  }
155  b->dataCount = 0;
156  b->next = ht->buckets[hash];
157  b->data = NULL;
158  ht->buckets[hash] = b;
159  }
160  /*@=branchstate@*/
161 
162  b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
163  b->data[b->dataCount++] = data;
164 }
165 /*@=boundswrite@*/
166 
168 {
169  hashBucket b, n;
170  int i;
171 
172  for (i = 0; i < ht->numBuckets; i++) {
173 /*@-boundsread@*/
174  b = ht->buckets[i];
175 /*@=boundsread@*/
176  if (b == NULL)
177  continue;
178 /*@-boundswrite@*/
179  ht->buckets[i] = NULL;
180 /*@=boundswrite@*/
181  if (ht->keySize > 0)
182  b->key = _free(b->key);
183  do {
184  n = b->next;
185  /*@-branchstate@*/
186  if (b->data) {
187 /*@-boundswrite@*/
188  if (ht->freeData)
189  *b->data = _free(*b->data);
190 /*@=boundswrite@*/
191  b->data = _free(b->data);
192  }
193  /*@=branchstate@*/
194  b = _free(b);
195  } while ((b = n) != NULL);
196  }
197 
198  ht->buckets = _free(ht->buckets);
199  ht = _free(ht);
200  return NULL;
201 }
202 
203 int htHasEntry(hashTable ht, const void * key)
204 {
205  hashBucket b;
206 
207  if (!(b = findEntry(ht, key))) return 0; else return 1;
208 }
209 
210 int htGetEntry(hashTable ht, const void * key, const void *** data,
211  int * dataCount, const void ** tableKey)
212 {
213  hashBucket b;
214 
215  if ((b = findEntry(ht, key)) == NULL)
216  return 1;
217 
218 /*@-boundswrite@*/
219  if (data)
220  *data = (const void **) b->data;
221  if (dataCount)
222  *dataCount = b->dataCount;
223  if (tableKey)
224  *tableKey = b->key;
225 /*@=boundswrite@*/
226 
227  return 0;
228 }