rpm
4.5
Main Page
Related Pages
Modules
Data Structures
Files
File List
Globals
rpmio
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
{
17
voidptr
key
;
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
;
30
hashFunctionType
fn
;
31
hashEqualityType
eq
;
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,
116
hashFunctionType
fn,
hashEqualityType
eq)
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
167
hashTable
htFree
(
hashTable
ht)
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
}
Generated on Tue Aug 28 2012 18:13:48 for rpm by
1.8.2