tools/qhash.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3 -
4 -
5 -
6 -
7 -
8 -
9 -
10 -
11 -
12 -
13 -
14 -
15 -
16 -
17static inline uint hash(const uchar *p, int len, uint seed) -
18{ -
19 uint h = seed; -
20 -
21 for (int i = 0; i < len; ++i)
evaluated: i < len
TRUEFALSE
yes
Evaluation Count:1348206
yes
Evaluation Count:62150
62150-1348206
22 h = 31 * h + p[i];
executed: h = 31 * h + p[i];
Execution Count:1348206
1348206
23 -
24 return h;
executed: return h;
Execution Count:62150
62150
25} -
26 -
27static inline uint hash(const QChar *p, int len, uint seed) -
28{ -
29 uint h = seed; -
30 -
31 for (int i = 0; i < len; ++i)
evaluated: i < len
TRUEFALSE
yes
Evaluation Count:9443070
yes
Evaluation Count:1367149
1367149-9443070
32 h = 31 * h + p[i].unicode();
executed: h = 31 * h + p[i].unicode();
Execution Count:9443069
9443069
33 -
34 return h;
executed: return h;
Execution Count:1367150
1367150
35} -
36 -
37uint qHash(const QByteArray &key, uint seed) -
38{ -
39 return hash(reinterpret_cast<const uchar *>(key.constData()), key.size(), seed);
executed: return hash(reinterpret_cast<const uchar *>(key.constData()), key.size(), seed);
Execution Count:62140
62140
40} -
41 -
42uint qHash(const QString &key, uint seed) -
43{ -
44 return hash(key.unicode(), key.size(), seed);
executed: return hash(key.unicode(), key.size(), seed);
Execution Count:1367139
1367139
45} -
46 -
47uint qHash(const QStringRef &key, uint seed) -
48{ -
49 return hash(key.unicode(), key.size(), seed);
executed: return hash(key.unicode(), key.size(), seed);
Execution Count:12
12
50} -
51 -
52uint qHash(const QBitArray &bitArray, uint seed) -
53{ -
54 int m = bitArray.d.size() - 1; -
55 uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()), qMax(0, m), seed); -
56 -
57 -
58 -
59 int n = bitArray.size(); -
60 if (n & 0x7)
evaluated: n & 0x7
TRUEFALSE
yes
Evaluation Count:9
yes
Evaluation Count:1
1-9
61 result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);
executed: result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);
Execution Count:9
9
62 return result;
executed: return result;
Execution Count:10
10
63} -
64 -
65uint qHash(QLatin1String key, uint seed) -
66{ -
67 return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed);
never executed: return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed);
0
68} -
69static uint qt_create_qhash_seed() -
70{ -
71 QByteArray envSeed = qgetenv("QT_HASH_SEED"); -
72 if (!envSeed.isNull())
partially evaluated: !envSeed.isNull()
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:103
0-103
73 return envSeed.toUInt();
never executed: return envSeed.toUInt();
0
74 -
75 uint seed = 0; -
76 -
77 -
78 int randomfd = qt_safe_open("/dev/urandom", 00); -
79 if (randomfd == -1)
partially evaluated: randomfd == -1
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:103
0-103
80 randomfd = qt_safe_open("/dev/random", 00 | 04000);
never executed: randomfd = qt_safe_open("/dev/random", 00 | 04000);
0
81 if (randomfd != -1) {
partially evaluated: randomfd != -1
TRUEFALSE
yes
Evaluation Count:103
no
Evaluation Count:0
0-103
82 if (qt_safe_read(randomfd, reinterpret_cast<char *>(&seed), sizeof(seed)) == sizeof(seed)) {
partially evaluated: qt_safe_read(randomfd, reinterpret_cast<char *>(&seed), sizeof(seed)) == sizeof(seed)
TRUEFALSE
yes
Evaluation Count:103
no
Evaluation Count:0
0-103
83 qt_safe_close(randomfd); -
84 return seed;
executed: return seed;
Execution Count:103
103
85 } -
86 qt_safe_close(randomfd); -
87 }
never executed: }
0
88 quint64 timestamp = QDateTime::currentMSecsSinceEpoch(); -
89 seed ^= timestamp; -
90 seed ^= (timestamp >> 32); -
91 -
92 -
93 quint64 pid = QCoreApplication::applicationPid(); -
94 seed ^= pid; -
95 seed ^= (pid >> 32); -
96 -
97 -
98 quintptr seedPtr = reinterpret_cast<quintptr>(&seed); -
99 seed ^= seedPtr; -
100 -
101 seed ^= (seedPtr >> 32); -
102 -
103 -
104 return seed;
never executed: return seed;
0
105} -
106 -
107 -
108 -
109 -
110__attribute__((visibility("default"))) QBasicAtomicInt qt_qhash_seed = { (-1) }; -
111static void qt_initialize_qhash_seed() -
112{ -
113 if (qt_qhash_seed.load() == -1) {
evaluated: qt_qhash_seed.load() == -1
TRUEFALSE
yes
Evaluation Count:103
yes
Evaluation Count:68335
103-68335
114 int x(qt_create_qhash_seed() & 2147483647); -
115 qt_qhash_seed.testAndSetRelaxed(-1, x); -
116 }
executed: }
Execution Count:103
103
117}
executed: }
Execution Count:68438
68438
118uint qt_hash(const QString &key) -
119{ -
120 const QChar *p = key.unicode(); -
121 int n = key.size(); -
122 uint h = 0; -
123 -
124 while (n--) {
evaluated: n--
TRUEFALSE
yes
Evaluation Count:572944
yes
Evaluation Count:62256
62256-572944
125 h = (h << 4) + (*p++).unicode(); -
126 h ^= (h & 0xf0000000) >> 23; -
127 h &= 0x0fffffff; -
128 }
executed: }
Execution Count:572944
572944
129 return h;
executed: return h;
Execution Count:62256
62256
130} -
131static const uchar prime_deltas[] = { -
132 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, -
133 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 -
134}; -
135 -
136static inline int primeForNumBits(int numBits) -
137{ -
138 return (1 << numBits) + prime_deltas[numBits];
executed: return (1 << numBits) + prime_deltas[numBits];
Execution Count:77630
77630
139} -
140 -
141 -
142 -
143 -
144 -
145static int countBits(int hint) -
146{ -
147 int numBits = 0; -
148 int bits = hint; -
149 -
150 while (bits > 1) {
evaluated: bits > 1
TRUEFALSE
yes
Evaluation Count:192
yes
Evaluation Count:5511
192-5511
151 bits >>= 1; -
152 numBits++; -
153 }
executed: }
Execution Count:192
192
154 -
155 if (numBits >= (int)sizeof(prime_deltas)) {
partially evaluated: numBits >= (int)sizeof(prime_deltas)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:5511
0-5511
156 numBits = sizeof(prime_deltas) - 1; -
157 } else if (primeForNumBits(numBits) < hint) {
never executed: }
evaluated: primeForNumBits(numBits) < hint
TRUEFALSE
yes
Evaluation Count:54
yes
Evaluation Count:5457
0-5457
158 ++numBits; -
159 }
executed: }
Execution Count:54
54
160 return numBits;
executed: return numBits;
Execution Count:5511
5511
161} -
162 -
163 -
164 -
165 -
166 -
167const int MinNumBits = 4; -
168 -
169const QHashData QHashData::shared_null = { -
170 0, 0, { { (-1) } }, 0, 0, MinNumBits, 0, 0, 0, true, false, 0 -
171}; -
172 -
173void *QHashData::allocateNode(int nodeAlign) -
174{ -
175 void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : malloc(nodeSize);
evaluated: strictAlignment
TRUEFALSE
yes
Evaluation Count:600
yes
Evaluation Count:3352256
600-3352256
176 do { if (!(ptr)) qBadAlloc(); } while (0);
never executed: qBadAlloc();
executed: }
Execution Count:3352856
partially evaluated: !(ptr)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:3352856
partially evaluated: 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:3352856
0-3352856
177 return ptr;
executed: return ptr;
Execution Count:3352856
3352856
178} -
179 -
180void QHashData::freeNode(void *node) -
181{ -
182 if (strictAlignment)
evaluated: strictAlignment
TRUEFALSE
yes
Evaluation Count:600
yes
Evaluation Count:3376886
600-3376886
183 qFreeAligned(node);
executed: qFreeAligned(node);
Execution Count:600
600
184 else -
185 free(node);
executed: free(node);
Execution Count:3376886
3376886
186} -
187 -
188QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), -
189 void (*node_delete)(Node *), -
190 int nodeSize, -
191 int nodeAlign) -
192{ -
193 union { -
194 QHashData *d; -
195 Node *e; -
196 }; -
197 if (this == &shared_null)
evaluated: this == &shared_null
TRUEFALSE
yes
Evaluation Count:68438
yes
Evaluation Count:1979
1979-68438
198 qt_initialize_qhash_seed();
executed: qt_initialize_qhash_seed();
Execution Count:68438
68438
199 d = new QHashData; -
200 d->fakeNext = 0; -
201 d->buckets = 0; -
202 d->ref.initializeOwned(); -
203 d->size = size; -
204 d->nodeSize = nodeSize; -
205 d->userNumBits = userNumBits; -
206 d->numBits = numBits; -
207 d->numBuckets = numBuckets; -
208 d->seed = uint(qt_qhash_seed.load()); -
209 d->sharable = true; -
210 d->strictAlignment = nodeAlign > 8; -
211 d->reserved = 0; -
212 -
213 if (numBuckets) {
evaluated: numBuckets
TRUEFALSE
yes
Evaluation Count:1979
yes
Evaluation Count:68438
1979-68438
214 try { -
215 d->buckets = new Node *[numBuckets]; -
216 } catch (...) {
executed: }
Execution Count:1979
1979
217 -
218 d->numBuckets = 0; -
219 -
220 d->free_helper(node_delete); -
221 throw;
never executed: throw;
0
222 } -
223 -
224 Node *this_e = reinterpret_cast<Node *>(this); -
225 for (int i = 0; i < numBuckets; ++i) {
evaluated: i < numBuckets
TRUEFALSE
yes
Evaluation Count:197517
yes
Evaluation Count:1978
1978-197517
226 Node **nextNode = &d->buckets[i]; -
227 Node *oldNode = buckets[i]; -
228 while (oldNode != this_e) {
evaluated: oldNode != this_e
TRUEFALSE
yes
Evaluation Count:129154
yes
Evaluation Count:197516
129154-197516
229 try { -
230 Node *dup = static_cast<Node *>(allocateNode(nodeAlign)); -
231 -
232 try { -
233 node_duplicate(oldNode, dup); -
234 } catch (...) {
executed: }
Execution Count:129153
129153
235 freeNode( dup ); -
236 throw;
executed: throw;
Execution Count:1
1
237 } -
238 -
239 *nextNode = dup; -
240 nextNode = &dup->next; -
241 oldNode = oldNode->next; -
242 } catch (...) {
executed: }
Execution Count:129153
129153
243 -
244 *nextNode = e; -
245 d->numBuckets = i+1; -
246 -
247 d->free_helper(node_delete); -
248 throw;
executed: throw;
Execution Count:1
1
249 } -
250 }
executed: }
Execution Count:129153
129153
251 *nextNode = e; -
252 }
executed: }
Execution Count:197516
197516
253 }
executed: }
Execution Count:1978
1978
254 return d;
executed: return d;
Execution Count:70416
70416
255} -
256 -
257void QHashData::free_helper(void (*node_delete)(Node *)) -
258{ -
259 if (node_delete) {
partially evaluated: node_delete
TRUEFALSE
yes
Evaluation Count:72846
no
Evaluation Count:0
0-72846
260 Node *this_e = reinterpret_cast<Node *>(this); -
261 Node **bucket = reinterpret_cast<Node **>(this->buckets); -
262 -
263 int n = numBuckets; -
264 while (n--) {
evaluated: n--
TRUEFALSE
yes
Evaluation Count:4153091
yes
Evaluation Count:72846
72846-4153091
265 Node *cur = *bucket++; -
266 while (cur != this_e) {
evaluated: cur != this_e
TRUEFALSE
yes
Evaluation Count:2842542
yes
Evaluation Count:4153091
2842542-4153091
267 Node *next = cur->next; -
268 node_delete(cur); -
269 freeNode(cur); -
270 cur = next; -
271 }
executed: }
Execution Count:2842542
2842542
272 }
executed: }
Execution Count:4153091
4153091
273 }
executed: }
Execution Count:72846
72846
274 delete [] buckets; -
275 delete this; -
276}
executed: }
Execution Count:72846
72846
277 -
278QHashData::Node *QHashData::nextNode(Node *node) -
279{ -
280 union { -
281 Node *next; -
282 Node *e; -
283 QHashData *d; -
284 }; -
285 next = node->next; -
286 qt_noop(); -
287 if (next->next)
evaluated: next->next
TRUEFALSE
yes
Evaluation Count:298261
yes
Evaluation Count:868181
298261-868181
288 return next;
executed: return next;
Execution Count:298261
298261
289 -
290 int start = (node->h % d->numBuckets) + 1; -
291 Node **bucket = d->buckets + start; -
292 int n = d->numBuckets - start; -
293 while (n--) {
evaluated: n--
TRUEFALSE
yes
Evaluation Count:895518721
yes
Evaluation Count:140399
140399-895518721
294 if (*bucket != e)
evaluated: *bucket != e
TRUEFALSE
yes
Evaluation Count:727782
yes
Evaluation Count:894790939
727782-894790939
295 return *bucket;
executed: return *bucket;
Execution Count:727782
727782
296 ++bucket; -
297 }
executed: }
Execution Count:894790939
894790939
298 return e;
executed: return e;
Execution Count:140399
140399
299} -
300 -
301QHashData::Node *QHashData::previousNode(Node *node) -
302{ -
303 union { -
304 Node *e; -
305 QHashData *d; -
306 }; -
307 -
308 e = node; -
309 while (e->next)
evaluated: e->next
TRUEFALSE
yes
Evaluation Count:456488
yes
Evaluation Count:354178
354178-456488
310 e = e->next;
executed: e = e->next;
Execution Count:456488
456488
311 -
312 int start; -
313 if (node == e)
evaluated: node == e
TRUEFALSE
yes
Evaluation Count:28130
yes
Evaluation Count:326048
28130-326048
314 start = d->numBuckets - 1;
executed: start = d->numBuckets - 1;
Execution Count:28130
28130
315 else -
316 start = node->h % d->numBuckets;
executed: start = node->h % d->numBuckets;
Execution Count:326048
326048
317 -
318 Node *sentinel = node; -
319 Node **bucket = d->buckets + start; -
320 while (start >= 0) {
partially evaluated: start >= 0
TRUEFALSE
yes
Evaluation Count:447497573
no
Evaluation Count:0
0-447497573
321 if (*bucket != sentinel) {
evaluated: *bucket != sentinel
TRUEFALSE
yes
Evaluation Count:354178
yes
Evaluation Count:447143395
354178-447143395
322 Node *prev = *bucket; -
323 while (prev->next != sentinel)
evaluated: prev->next != sentinel
TRUEFALSE
yes
Evaluation Count:152162
yes
Evaluation Count:354178
152162-354178
324 prev = prev->next;
executed: prev = prev->next;
Execution Count:152162
152162
325 return prev;
executed: return prev;
Execution Count:354178
354178
326 } -
327 -
328 sentinel = e; -
329 --bucket; -
330 --start; -
331 }
executed: }
Execution Count:447143395
447143395
332 qt_noop(); -
333 return e;
never executed: return e;
0
334} -
335 -
336 -
337 -
338 -
339 -
340 -
341 -
342void QHashData::rehash(int hint) -
343{ -
344 if (hint < 0) {
evaluated: hint < 0
TRUEFALSE
yes
Evaluation Count:5511
yes
Evaluation Count:61076
5511-61076
345 hint = countBits(-hint); -
346 if (hint < MinNumBits)
evaluated: hint < MinNumBits
TRUEFALSE
yes
Evaluation Count:5474
yes
Evaluation Count:37
37-5474
347 hint = MinNumBits;
executed: hint = MinNumBits;
Execution Count:5474
5474
348 userNumBits = hint; -
349 while (primeForNumBits(hint) < (size >> 1))
evaluated: primeForNumBits(hint) < (size >> 1)
TRUEFALSE
yes
Evaluation Count:25
yes
Evaluation Count:5511
25-5511
350 ++hint;
executed: ++hint;
Execution Count:25
25
351 } else if (hint < MinNumBits) {
executed: }
Execution Count:5511
evaluated: hint < MinNumBits
TRUEFALSE
yes
Evaluation Count:57502
yes
Evaluation Count:3574
3574-57502
352 hint = MinNumBits; -
353 }
executed: }
Execution Count:57502
57502
354 -
355 if (numBits != hint) {
evaluated: numBits != hint
TRUEFALSE
yes
Evaluation Count:66583
yes
Evaluation Count:4
4-66583
356 Node *e = reinterpret_cast<Node *>(this); -
357 Node **oldBuckets = buckets; -
358 int oldNumBuckets = numBuckets; -
359 -
360 int nb = primeForNumBits(hint); -
361 buckets = new Node *[nb]; -
362 numBits = hint; -
363 numBuckets = nb; -
364 for (int i = 0; i < numBuckets; ++i)
evaluated: i < numBuckets
TRUEFALSE
yes
Evaluation Count:6928205
yes
Evaluation Count:66583
66583-6928205
365 buckets[i] = e;
executed: buckets[i] = e;
Execution Count:6928205
6928205
366 -
367 for (int i = 0; i < oldNumBuckets; ++i) {
evaluated: i < oldNumBuckets
TRUEFALSE
yes
Evaluation Count:3038572
yes
Evaluation Count:66583
66583-3038572
368 Node *firstNode = oldBuckets[i]; -
369 while (firstNode != e) {
evaluated: firstNode != e
TRUEFALSE
yes
Evaluation Count:273044
yes
Evaluation Count:3038572
273044-3038572
370 uint h = firstNode->h; -
371 Node *lastNode = firstNode; -
372 while (lastNode->next != e && lastNode->next->h == h)
evaluated: lastNode->next != e
TRUEFALSE
yes
Evaluation Count:2704984
yes
Evaluation Count:191970
evaluated: lastNode->next->h == h
TRUEFALSE
yes
Evaluation Count:2623910
yes
Evaluation Count:81074
81074-2704984
373 lastNode = lastNode->next;
executed: lastNode = lastNode->next;
Execution Count:2623910
2623910
374 -
375 Node *afterLastNode = lastNode->next; -
376 Node **beforeFirstNode = &buckets[h % numBuckets]; -
377 while (*beforeFirstNode != e)
evaluated: *beforeFirstNode != e
TRUEFALSE
yes
Evaluation Count:51204
yes
Evaluation Count:273044
51204-273044
378 beforeFirstNode = &(*beforeFirstNode)->next;
executed: beforeFirstNode = &(*beforeFirstNode)->next;
Execution Count:51204
51204
379 lastNode->next = *beforeFirstNode; -
380 *beforeFirstNode = firstNode; -
381 firstNode = afterLastNode; -
382 }
executed: }
Execution Count:273044
273044
383 }
executed: }
Execution Count:3038572
3038572
384 delete [] oldBuckets; -
385 }
executed: }
Execution Count:66583
66583
386}
executed: }
Execution Count:66587
66587
387 -
388 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial