tools/qhash.cpp

Source code Switch to Preprocessed file

Line Source Code Coverage

1 -

2 /**************************************************************************** -

3 ** -

6 ** Contact: http://www.qt-project.org/legal -

7 ** -

8 ** This file is part of the QtCore module of the Qt Toolkit. -

9 ** -

10 ** $QT_BEGIN_LICENSE:LGPL$ -

11 ** Commercial License Usage -

12 ** Licensees holding valid commercial Qt licenses may use this file in -

13 ** accordance with the commercial license agreement provided with the -

14 ** Software or, alternatively, in accordance with the terms contained in -

15 ** a written agreement between you and Digia. For licensing terms and -

16 ** conditions see http://qt.digia.com/licensing. For further information -

17 ** use the contact form at http://qt.digia.com/contact-us. -

18 ** -

19 ** GNU Lesser General Public License Usage -

20 ** Alternatively, this file may be used under the terms of the GNU Lesser -

21 ** General Public License version 2.1 as published by the Free Software -

22 ** Foundation and appearing in the file LICENSE.LGPL included in the -

23 ** packaging of this file. Please review the following information to -

24 ** ensure the GNU Lesser General Public License version 2.1 requirements -

25 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -

26 ** -

27 ** In addition, as a special exception, Digia gives you certain additional -

28 ** rights. These rights are described in the Digia Qt LGPL Exception -

29 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -

30 ** -

31 ** GNU General Public License Usage -

32 ** Alternatively, this file may be used under the terms of the GNU -

33 ** General Public License version 3.0 as published by the Free Software -

34 ** Foundation and appearing in the file LICENSE.GPL included in the -

35 ** packaging of this file. Please review the following information to -

36 ** ensure the GNU General Public License version 3.0 requirements will be -

37 ** met: http://www.gnu.org/copyleft/gpl.html. -

38 ** -

39 ** -

40 ** $QT_END_LICENSE$ -

41 ** -

42 ****************************************************************************/ -

43 -

44 // for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h. -

45 // put it at the beginning so some indirect inclusion doesn't break it -

46 #ifndef _CRT_RAND_S -

47 #define _CRT_RAND_S -

48 #endif -

49 #include <stdlib.h> -

50 -

51 #include "qhash.h" -

52 -

53 #ifdef truncate -

54 #undef truncate -

55 #endif -

56 -

57 #include <qbitarray.h> -

58 #include <qstring.h> -

59 #include <qglobal.h> -

60 #include <qbytearray.h> -

61 #include <qdatetime.h> -

62 #include <qbasicatomic.h> -

63 -

64 #ifndef QT_BOOTSTRAPPED -

65 #include <qcoreapplication.h> -

66 #endif // QT_BOOTSTRAPPED -

67 -

68 #ifdef Q_OS_UNIX -

69 #include <stdio.h> -

70 #include "private/qcore_unix_p.h" -

71 #endif // Q_OS_UNIX -

72 -

73 #include <limits.h> -

74 -

75 QT_BEGIN_NAMESPACE -

76 -

77 /* -

78 The Java's hashing algorithm for strings is a variation of D. J. Bernstein -

79 hashing algorithm appeared here http://cr.yp.to/cdb/cdb.txt -

80 and informally known as DJB33XX - DJB's 33 Times Xor. -

81 Java uses DJB31XA, that is, 31 Times Add. -

82 -

83 The original algorithm was a loop around -

84 (h << 5) + h ^ c -

85 (which is indeed h*33 ^ c); it was then changed to -

86 (h << 5) - h ^ c -

87 (so h*31^c: DJB31XX), and the XOR changed to a sum: -

88 (h << 5) - h + c -

89 (DJB31XA), which can save some assembly instructions. -

90 -

91 Still, we can avoid writing the multiplication as "(h << 5) - h" -

92 -- the compiler will turn it into a shift and an addition anyway -

93 (for instance, gcc 4.4 does that even at -O0). -

94 */ -

95 -

96 static inline uint hash(const uchar *p, int len, uint seed) Q_DECL_NOTHROW -

97 { -

uint h = seed;

executed (the execution status of this line is deduced): uint h = seed;

99 -

100

for (int i = 0; i < len; ++i)

evaluated: i < len

TRUE	FALSE
yes Evaluation Count:1348206	yes Evaluation Count:62150

62150-1348206

101

h = 31 * h + p[i];

executed: h = 31 * h + p[i];

Execution Count:1348206

1348206

102 -

103

return h;

executed: return h;

Execution Count:62150

62150

104 } -

105 -

106 static inline uint hash(const QChar *p, int len, uint seed) Q_DECL_NOTHROW -

107 { -

108

uint h = seed;

executed (the execution status of this line is deduced): uint h = seed;

109 -

110

for (int i = 0; i < len; ++i)

evaluated: i < len

TRUE	FALSE
yes Evaluation Count:9443070	yes Evaluation Count:1367149

1367149-9443070

111

h = 31 * h + p[i].unicode();

executed: h = 31 * h + p[i].unicode();

Execution Count:9443069

9443069

112 -

113

return h;

executed: return h;

Execution Count:1367150

1367150

114 } -

115 -

116 uint qHash(const QByteArray &key, uint seed) Q_DECL_NOTHROW -

117 { -

118

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

119 } -

120 -

121 uint qHash(const QString &key, uint seed) Q_DECL_NOTHROW -

122 { -

123

return hash(key.unicode(), key.size(), seed);

executed: return hash(key.unicode(), key.size(), seed);

Execution Count:1367139

1367139

124 } -

125 -

126 uint qHash(const QStringRef &key, uint seed) Q_DECL_NOTHROW -

127 { -

128

return hash(key.unicode(), key.size(), seed);

executed: return hash(key.unicode(), key.size(), seed);

Execution Count:12

129 } -

130 -

131 uint qHash(const QBitArray &bitArray, uint seed) Q_DECL_NOTHROW -

132 { -

133

int m = bitArray.d.size() - 1;

executed (the execution status of this line is deduced): int m = bitArray.d.size() - 1;

134

uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()), qMax(0, m), seed);

executed (the execution status of this line is deduced): uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()), qMax(0, m), seed);

135 -

136 // deal with the last 0 to 7 bits manually, because we can't trust that -

137 // the padding is initialized to 0 in bitArray.d -

138

int n = bitArray.size();

executed (the execution status of this line is deduced): int n = bitArray.size();

139

if (n & 0x7)

evaluated: n & 0x7

TRUE	FALSE
yes Evaluation Count:9	yes Evaluation Count:1

1-9

140

result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);

executed: result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);

Execution Count:9

141

return result;

executed: return result;

Execution Count:10

142 } -

143 -

144 uint qHash(QLatin1String key, uint seed) Q_DECL_NOTHROW -

145 { -

146

return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed);

never executed: return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed);

147 } -

148 -

149 /*! -

150 \internal -

151 -

152 Creates the QHash random seed from various sources. -

153 In order of decreasing precedence: -

154 - under Unix, it attemps to read from /dev/urandom; -

155 - under Unix, it attemps to read from /dev/random; -

156 - under Windows, it attempts to use rand_s; -

157 - as a general fallback, the application's PID, a timestamp and the -

158 address of a stack-local variable are used. -

159 */ -

160 static uint qt_create_qhash_seed() -

161 { -

162

QByteArray envSeed = qgetenv("QT_HASH_SEED");

executed (the execution status of this line is deduced): QByteArray envSeed = qgetenv("QT_HASH_SEED");

163

if (!envSeed.isNull())

partially evaluated: !envSeed.isNull()

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:103

0-103

164

return envSeed.toUInt();

never executed: return envSeed.toUInt();

165 -

166

uint seed = 0;

executed (the execution status of this line is deduced): uint seed = 0;

167 -

168 #ifdef Q_OS_UNIX -

169

int randomfd = qt_safe_open("/dev/urandom", O_RDONLY);

executed (the execution status of this line is deduced): int randomfd = qt_safe_open("/dev/urandom", 00);

170

if (randomfd == -1)

partially evaluated: randomfd == -1

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:103

0-103

171

randomfd = qt_safe_open("/dev/random", O_RDONLY | O_NONBLOCK);

never executed: randomfd = qt_safe_open("/dev/random", 00 | 04000);

172

if (randomfd != -1) {

partially evaluated: randomfd != -1

TRUE	FALSE
yes Evaluation Count:103	no Evaluation Count:0

0-103

173

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)

TRUE	FALSE
yes Evaluation Count:103	no Evaluation Count:0

0-103

174

qt_safe_close(randomfd);

executed (the execution status of this line is deduced): qt_safe_close(randomfd);

175

return seed;

executed: return seed;

Execution Count:103

103

176 } -

177

qt_safe_close(randomfd);

never executed (the execution status of this line is deduced): qt_safe_close(randomfd);

178

}

never executed: }

179 #endif // Q_OS_UNIX -

180 -

181 #if defined(Q_OS_WIN32) && !defined(Q_CC_GNU) -

182 errno_t err; -

183 err = rand_s(&seed); -

184 if (err == 0) -

185 return seed; -

186 #endif // Q_OS_WIN32 -

187 -

188 // general fallback: initialize from the current timestamp, pid, -

189 // and address of a stack-local variable -

190

quint64 timestamp = QDateTime::currentMSecsSinceEpoch();

never executed (the execution status of this line is deduced): quint64 timestamp = QDateTime::currentMSecsSinceEpoch();

191

seed ^= timestamp;

never executed (the execution status of this line is deduced): seed ^= timestamp;

192

seed ^= (timestamp >> 32);

never executed (the execution status of this line is deduced): seed ^= (timestamp >> 32);

193 -

194 #ifndef QT_BOOTSTRAPPED -

195

quint64 pid = QCoreApplication::applicationPid();

never executed (the execution status of this line is deduced): quint64 pid = QCoreApplication::applicationPid();

196

seed ^= pid;

never executed (the execution status of this line is deduced): seed ^= pid;

197

seed ^= (pid >> 32);

never executed (the execution status of this line is deduced): seed ^= (pid >> 32);

198 #endif // QT_BOOTSTRAPPED -

199 -

200

quintptr seedPtr = reinterpret_cast<quintptr>(&seed);

never executed (the execution status of this line is deduced): quintptr seedPtr = reinterpret_cast<quintptr>(&seed);

201

seed ^= seedPtr;

never executed (the execution status of this line is deduced): seed ^= seedPtr;

202 #if QT_POINTER_SIZE == 8 -

203

seed ^= (seedPtr >> 32);

never executed (the execution status of this line is deduced): seed ^= (seedPtr >> 32);

204 #endif -

205 -

206

return seed;

never executed: return seed;

207 } -

208 -

209 /* -

210 The QHash seed itself. -

211 */ -

212 Q_CORE_EXPORT QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1); -

213 -

214 /*! -

215 \internal -

216 -

217 Seed == -1 means it that it was not initialized yet. -

218 -

219 We let qt_create_qhash_seed return any unsigned integer, -

220 but convert it to signed in order to initialize the seed. -

221 -

222 We don't actually care about the fact that different calls to -

223 qt_create_qhash_seed() might return different values, -

224 as long as in the end everyone uses the very same value. -

225 */ -

226 static void qt_initialize_qhash_seed() -

227 { -

228

if (qt_qhash_seed.load() == -1) {

evaluated: qt_qhash_seed.load() == -1

TRUE	FALSE
yes Evaluation Count:103	yes Evaluation Count:68335

103-68335

229

int x(qt_create_qhash_seed() & INT_MAX);

executed (the execution status of this line is deduced): int x(qt_create_qhash_seed() & 2147483647);

230

qt_qhash_seed.testAndSetRelaxed(-1, x);

executed (the execution status of this line is deduced): qt_qhash_seed.testAndSetRelaxed(-1, x);

231

}

executed: }

Execution Count:103

103

232

}

executed: }

Execution Count:68438

68438

233 -

234 /*! -

235 \internal -

236 -

237 Private copy of the implementation of the Qt 4 qHash algorithm for strings, -

238 to be used wherever the result is somehow stored or reused across multiple -

239 Qt versions. The public qHash implementation can change at any time, -

240 therefore one must not rely on the fact that it will always give the same -

241 results. -

242 -

243 This function must *never* change its results. -

244 */ -

245 uint qt_hash(const QString &key) Q_DECL_NOTHROW -

246 { -

247

const QChar *p = key.unicode();

executed (the execution status of this line is deduced): const QChar *p = key.unicode();

248

int n = key.size();

executed (the execution status of this line is deduced): int n = key.size();

249

uint h = 0;

executed (the execution status of this line is deduced): uint h = 0;

250 -

251

while (n--) {

evaluated: n--

TRUE	FALSE
yes Evaluation Count:572944	yes Evaluation Count:62256

62256-572944

252

h = (h << 4) + (*p++).unicode();

executed (the execution status of this line is deduced): h = (h << 4) + (*p++).unicode();

253

h ^= (h & 0xf0000000) >> 23;

executed (the execution status of this line is deduced): h ^= (h & 0xf0000000) >> 23;

254

h &= 0x0fffffff;

executed (the execution status of this line is deduced): h &= 0x0fffffff;

255

}

executed: }

Execution Count:572944

572944

256

return h;

executed: return h;

Execution Count:62256

62256

257 } -

258 -

259 /* -

260 The prime_deltas array is a table of selected prime values, even -

261 though it doesn't look like one. The primes we are using are 1, -

262 2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate -

263 surrounding of a power of two. -

264 -

265 The primeForNumBits() function returns the prime associated to a -

266 power of two. For example, primeForNumBits(8) returns 257. -

267 */ -

268 -

269 static const uchar prime_deltas[] = { -

270 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, -

271 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 -

272 }; -

273 -

274 static inline int primeForNumBits(int numBits) -

275 { -

276

return (1 << numBits) + prime_deltas[numBits];

executed: return (1 << numBits) + prime_deltas[numBits];

Execution Count:77630

77630

277 } -

278 -

279 /* -

280 Returns the smallest integer n such that -

281 primeForNumBits(n) >= hint. -

282 */ -

283 static int countBits(int hint) -

284 { -

285

int numBits = 0;

executed (the execution status of this line is deduced): int numBits = 0;

286

int bits = hint;

executed (the execution status of this line is deduced): int bits = hint;

287 -

288

while (bits > 1) {

evaluated: bits > 1

TRUE	FALSE
yes Evaluation Count:192	yes Evaluation Count:5511

192-5511

289

bits >>= 1;

executed (the execution status of this line is deduced): bits >>= 1;

290

numBits++;

executed (the execution status of this line is deduced): numBits++;

291

}

executed: }

Execution Count:192

192

292 -

293

if (numBits >= (int)sizeof(prime_deltas)) {

partially evaluated: numBits >= (int)sizeof(prime_deltas)

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:5511

0-5511

294

numBits = sizeof(prime_deltas) - 1;

never executed (the execution status of this line is deduced): numBits = sizeof(prime_deltas) - 1;

295

} else if (primeForNumBits(numBits) < hint) {

never executed: }

evaluated: primeForNumBits(numBits) < hint

TRUE	FALSE
yes Evaluation Count:54	yes Evaluation Count:5457

0-5457

296

++numBits;

executed (the execution status of this line is deduced): ++numBits;

297

}

executed: }

Execution Count:54

298

return numBits;

executed: return numBits;

Execution Count:5511

5511

299 } -

300 -

301 /* -

302 A QHash has initially around pow(2, MinNumBits) buckets. For -

303 example, if MinNumBits is 4, it has 17 buckets. -

304 */ -

305 const int MinNumBits = 4; -

306 -

307 const QHashData QHashData::shared_null = { -

308 0, 0, Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, MinNumBits, 0, 0, 0, true, false, 0 -

309 }; -

310 -

311 void *QHashData::allocateNode(int nodeAlign) -

312 { -

313

void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : malloc(nodeSize);

evaluated: strictAlignment

TRUE	FALSE
yes Evaluation Count:600	yes Evaluation Count:3352256

600-3352256

314

Q_CHECK_PTR(ptr);

never executed: qBadAlloc();

executed: }

Execution Count:3352856

partially evaluated: !(ptr)

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:3352856

partially evaluated: 0

TRUE	FALSE
no Evaluation Count:0	yes Evaluation Count:3352856

0-3352856

315

return ptr;

executed: return ptr;

Execution Count:3352856

3352856

316 } -

317 -

318 void QHashData::freeNode(void *node) -

319 { -

320

if (strictAlignment)

evaluated: strictAlignment

TRUE	FALSE
yes Evaluation Count:600	yes Evaluation Count:3376886

600-3376886

321

qFreeAligned(node);

executed: qFreeAligned(node);

Execution Count:600

600

322 else -

323

free(node);

executed: free(node);

Execution Count:3376886

3376886

324 } -

325 -

326 QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), -

327 void (*node_delete)(Node *), -

328 int nodeSize, -

329 int nodeAlign) -

330 { -

331

union {

executed (the execution status of this line is deduced): union {

332

QHashData *d;

executed (the execution status of this line is deduced): QHashData *d;

333

Node *e;

executed (the execution status of this line is deduced): Node *e;

334

};

executed (the execution status of this line is deduced): };

335

if (this == &shared_null)

evaluated: this == &shared_null

TRUE	FALSE
yes Evaluation Count:68438	yes Evaluation Count:1979

1979-68438

336

qt_initialize_qhash_seed();

executed: qt_initialize_qhash_seed();

Execution Count:68438

68438

337

d = new QHashData;

executed (the execution status of this line is deduced): d = new QHashData;

338

d->fakeNext = 0;

executed (the execution status of this line is deduced): d->fakeNext = 0;

339

d->buckets = 0;

executed (the execution status of this line is deduced): d->buckets = 0;

340

d->ref.initializeOwned();

executed (the execution status of this line is deduced): d->ref.initializeOwned();

341

d->size = size;

executed (the execution status of this line is deduced): d->size = size;

342

d->nodeSize = nodeSize;

executed (the execution status of this line is deduced): d->nodeSize = nodeSize;

343

d->userNumBits = userNumBits;

executed (the execution status of this line is deduced): d->userNumBits = userNumBits;

344

d->numBits = numBits;

executed (the execution status of this line is deduced): d->numBits = numBits;

345

d->numBuckets = numBuckets;

executed (the execution status of this line is deduced): d->numBuckets = numBuckets;

346

d->seed = uint(qt_qhash_seed.load());

executed (the execution status of this line is deduced): d->seed = uint(qt_qhash_seed.load());

347

d->sharable = true;

executed (the execution status of this line is deduced): d->sharable = true;

348

d->strictAlignment = nodeAlign > 8;

executed (the execution status of this line is deduced): d->strictAlignment = nodeAlign > 8;

349

d->reserved = 0;

executed (the execution status of this line is deduced): d->reserved = 0;

350 -

351

if (numBuckets) {

evaluated: numBuckets

TRUE	FALSE
yes Evaluation Count:1979	yes Evaluation Count:68438

1979-68438

352 QT_TRY { -

353

d->buckets = new Node *[numBuckets];

executed (the execution status of this line is deduced): d->buckets = new Node *[numBuckets];

354

} QT_CATCH(...) {

executed: }

Execution Count:1979

1979

355 // restore a consistent state for d -

356

d->numBuckets = 0;

never executed (the execution status of this line is deduced): d->numBuckets = 0;

357 // roll back -

358

d->free_helper(node_delete);

never executed (the execution status of this line is deduced): d->free_helper(node_delete);

359

QT_RETHROW;

never executed: throw;

360 } -

361 -

362

Node *this_e = reinterpret_cast<Node *>(this);

executed (the execution status of this line is deduced): Node *this_e = reinterpret_cast<Node *>(this);

363

for (int i = 0; i < numBuckets; ++i) {

evaluated: i < numBuckets

TRUE	FALSE
yes Evaluation Count:197517	yes Evaluation Count:1978

1978-197517

364

Node **nextNode = &d->buckets[i];

executed (the execution status of this line is deduced): Node **nextNode = &d->buckets[i];

365

Node *oldNode = buckets[i];

executed (the execution status of this line is deduced): Node *oldNode = buckets[i];

366

while (oldNode != this_e) {

evaluated: oldNode != this_e

TRUE	FALSE
yes Evaluation Count:129154	yes Evaluation Count:197516

129154-197516

367 QT_TRY { -

368

Node *dup = static_cast<Node *>(allocateNode(nodeAlign));

executed (the execution status of this line is deduced): Node *dup = static_cast<Node *>(allocateNode(nodeAlign));

369 -

370 QT_TRY { -

371

node_duplicate(oldNode, dup);

executed (the execution status of this line is deduced): node_duplicate(oldNode, dup);

372

} QT_CATCH(...) {

executed: }

Execution Count:129153

129153

373

freeNode( dup );

executed (the execution status of this line is deduced): freeNode( dup );

374

QT_RETHROW;

executed: throw;

Execution Count:1

375 } -

376 -

377

*nextNode = dup;

executed (the execution status of this line is deduced): *nextNode = dup;

378

nextNode = &dup->next;

executed (the execution status of this line is deduced): nextNode = &dup->next;

379

oldNode = oldNode->next;

executed (the execution status of this line is deduced): oldNode = oldNode->next;

380

} QT_CATCH(...) {

executed: }

Execution Count:129153

129153

381 // restore a consistent state for d -

382

*nextNode = e;

executed (the execution status of this line is deduced): *nextNode = e;

383

d->numBuckets = i+1;

executed (the execution status of this line is deduced): d->numBuckets = i+1;

384 // roll back -

385

d->free_helper(node_delete);

executed (the execution status of this line is deduced): d->free_helper(node_delete);

386

QT_RETHROW;

executed: throw;

Execution Count:1

387 } -

388

}

executed: }

Execution Count:129153

129153

389

*nextNode = e;

executed (the execution status of this line is deduced): *nextNode = e;

390

}

executed: }

Execution Count:197516

197516

391

}

executed: }

Execution Count:1978

1978

392

return d;

executed: return d;

Execution Count:70416

70416

393 } -

394 -

395 void QHashData::free_helper(void (*node_delete)(Node *)) -

396 { -

397

if (node_delete) {

partially evaluated: node_delete

TRUE	FALSE
yes Evaluation Count:72846	no Evaluation Count:0

0-72846

398

Node *this_e = reinterpret_cast<Node *>(this);

executed (the execution status of this line is deduced): Node *this_e = reinterpret_cast<Node *>(this);

399

Node **bucket = reinterpret_cast<Node **>(this->buckets);

executed (the execution status of this line is deduced): Node **bucket = reinterpret_cast<Node **>(this->buckets);

400 -

401

int n = numBuckets;

executed (the execution status of this line is deduced): int n = numBuckets;

402

while (n--) {

evaluated: n--

TRUE	FALSE
yes Evaluation Count:4153091	yes Evaluation Count:72846

72846-4153091

403

Node *cur = *bucket++;

executed (the execution status of this line is deduced): Node *cur = *bucket++;

404

while (cur != this_e) {

evaluated: cur != this_e

TRUE	FALSE
yes Evaluation Count:2842542	yes Evaluation Count:4153091

2842542-4153091

405

Node *next = cur->next;

executed (the execution status of this line is deduced): Node *next = cur->next;

406

node_delete(cur);

executed (the execution status of this line is deduced): node_delete(cur);

407

freeNode(cur);

executed (the execution status of this line is deduced): freeNode(cur);

408

cur = next;

executed (the execution status of this line is deduced): cur = next;

409

}

executed: }

Execution Count:2842542

2842542

410

}

executed: }

Execution Count:4153091

4153091

411

}

executed: }

Execution Count:72846

72846

412

delete [] buckets;

executed (the execution status of this line is deduced): delete [] buckets;

413

delete this;

executed (the execution status of this line is deduced): delete this;

414

}

executed: }

Execution Count:72846

72846

415 -

416 QHashData::Node *QHashData::nextNode(Node *node) -

417 { -

418

union {

executed (the execution status of this line is deduced): union {

419

Node *next;

executed (the execution status of this line is deduced): Node *next;

420

Node *e;

executed (the execution status of this line is deduced): Node *e;

421

QHashData *d;

executed (the execution status of this line is deduced): QHashData *d;

422

};

executed (the execution status of this line is deduced): };

423

next = node->next;

executed (the execution status of this line is deduced): next = node->next;

424

Q_ASSERT_X(next, "QHash", "Iterating beyond end()");

executed (the execution status of this line is deduced): qt_noop();

425

if (next->next)

evaluated: next->next

TRUE	FALSE
yes Evaluation Count:298261	yes Evaluation Count:868181

298261-868181

426

return next;

executed: return next;

Execution Count:298261

298261

427 -

428

int start = (node->h % d->numBuckets) + 1;

executed (the execution status of this line is deduced): int start = (node->h % d->numBuckets) + 1;

429

Node **bucket = d->buckets + start;

executed (the execution status of this line is deduced): Node **bucket = d->buckets + start;

430

int n = d->numBuckets - start;

executed (the execution status of this line is deduced): int n = d->numBuckets - start;

431

while (n--) {

evaluated: n--

TRUE	FALSE
yes Evaluation Count:895518721	yes Evaluation Count:140399

140399-895518721

432

if (*bucket != e)

evaluated: *bucket != e

TRUE	FALSE
yes Evaluation Count:727782	yes Evaluation Count:894790939

727782-894790939

433

return *bucket;

executed: return *bucket;

Execution Count:727782

727782

434

++bucket;

executed (the execution status of this line is deduced): ++bucket;

435

}

executed: }

Execution Count:894790939

894790939

436

return e;

executed: return e;

Execution Count:140399

140399

437 } -

438 -

439 QHashData::Node *QHashData::previousNode(Node *node) -

440 { -

441

union {

executed (the execution status of this line is deduced): union {

442

Node *e;

executed (the execution status of this line is deduced): Node *e;

443

QHashData *d;

executed (the execution status of this line is deduced): QHashData *d;

444

};

executed (the execution status of this line is deduced): };

445 -

446

e = node;

executed (the execution status of this line is deduced): e = node;

447

while (e->next)

evaluated: e->next

TRUE	FALSE
yes Evaluation Count:456488	yes Evaluation Count:354178

354178-456488

448

e = e->next;

executed: e = e->next;

Execution Count:456488

456488

449 -

450

int start;

executed (the execution status of this line is deduced): int start;

451

if (node == e)

evaluated: node == e

TRUE	FALSE
yes Evaluation Count:28130	yes Evaluation Count:326048

28130-326048

452

start = d->numBuckets - 1;

executed: start = d->numBuckets - 1;

Execution Count:28130

28130

453 else -

454

start = node->h % d->numBuckets;

executed: start = node->h % d->numBuckets;

Execution Count:326048

326048

455 -

456

Node *sentinel = node;

executed (the execution status of this line is deduced): Node *sentinel = node;

457

Node **bucket = d->buckets + start;

executed (the execution status of this line is deduced): Node **bucket = d->buckets + start;

458

while (start >= 0) {

partially evaluated: start >= 0

TRUE	FALSE
yes Evaluation Count:447497573	no Evaluation Count:0

0-447497573

459

if (*bucket != sentinel) {

evaluated: *bucket != sentinel

TRUE	FALSE
yes Evaluation Count:354178	yes Evaluation Count:447143395

354178-447143395

460

Node *prev = *bucket;

executed (the execution status of this line is deduced): Node *prev = *bucket;

461

while (prev->next != sentinel)

evaluated: prev->next != sentinel

TRUE	FALSE
yes Evaluation Count:152162	yes Evaluation Count:354178

152162-354178

462

prev = prev->next;

executed: prev = prev->next;

Execution Count:152162

152162

463

return prev;

executed: return prev;

Execution Count:354178

354178

464 } -

465 -

466

sentinel = e;

executed (the execution status of this line is deduced): sentinel = e;

467

--bucket;

executed (the execution status of this line is deduced): --bucket;

468

--start;

executed (the execution status of this line is deduced): --start;

469

}

executed: }

Execution Count:447143395

447143395

470

Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");

never executed (the execution status of this line is deduced): qt_noop();

471

return e;

never executed: return e;

472 } -

473 -

474 /* -

475 If hint is negative, -hint gives the approximate number of -

476 buckets that should be used for the hash table. If hint is -

477 nonnegative, (1 << hint) gives the approximate number -

478 of buckets that should be used. -

479 */ -

480 void QHashData::rehash(int hint) -

481 { -

482

if (hint < 0) {

evaluated: hint < 0

TRUE	FALSE
yes Evaluation Count:5511	yes Evaluation Count:61076

5511-61076

483

hint = countBits(-hint);

executed (the execution status of this line is deduced): hint = countBits(-hint);

484

if (hint < MinNumBits)

evaluated: hint < MinNumBits

TRUE	FALSE
yes Evaluation Count:5474	yes Evaluation Count:37

37-5474

485

hint = MinNumBits;

executed: hint = MinNumBits;

Execution Count:5474

5474

486

userNumBits = hint;

executed (the execution status of this line is deduced): userNumBits = hint;

487

while (primeForNumBits(hint) < (size >> 1))

evaluated: primeForNumBits(hint) < (size >> 1)

TRUE	FALSE
yes Evaluation Count:25	yes Evaluation Count:5511

25-5511

488

++hint;

executed: ++hint;

Execution Count:25

489

} else if (hint < MinNumBits) {

executed: }

Execution Count:5511

evaluated: hint < MinNumBits

TRUE	FALSE
yes Evaluation Count:57502	yes Evaluation Count:3574

3574-57502

490

hint = MinNumBits;

executed (the execution status of this line is deduced): hint = MinNumBits;

491

}

executed: }

Execution Count:57502

57502

492 -

493

if (numBits != hint) {

evaluated: numBits != hint

TRUE	FALSE
yes Evaluation Count:66583	yes Evaluation Count:4

4-66583

494

Node *e = reinterpret_cast<Node *>(this);

executed (the execution status of this line is deduced): Node *e = reinterpret_cast<Node *>(this);

495

Node **oldBuckets = buckets;

executed (the execution status of this line is deduced): Node **oldBuckets = buckets;

496

int oldNumBuckets = numBuckets;

executed (the execution status of this line is deduced): int oldNumBuckets = numBuckets;

497 -

498

int nb = primeForNumBits(hint);

executed (the execution status of this line is deduced): int nb = primeForNumBits(hint);

499

buckets = new Node *[nb];

executed (the execution status of this line is deduced): buckets = new Node *[nb];

500

numBits = hint;

executed (the execution status of this line is deduced): numBits = hint;

501

numBuckets = nb;

executed (the execution status of this line is deduced): numBuckets = nb;

502

for (int i = 0; i < numBuckets; ++i)

evaluated: i < numBuckets

TRUE	FALSE
yes Evaluation Count:6928205	yes Evaluation Count:66583

66583-6928205

503

buckets[i] = e;

executed: buckets[i] = e;

Execution Count:6928205

6928205

504 -

505

for (int i = 0; i < oldNumBuckets; ++i) {

evaluated: i < oldNumBuckets

TRUE	FALSE
yes Evaluation Count:3038572	yes Evaluation Count:66583

66583-3038572

506

Node *firstNode = oldBuckets[i];

executed (the execution status of this line is deduced): Node *firstNode = oldBuckets[i];

507

while (firstNode != e) {

evaluated: firstNode != e

TRUE	FALSE
yes Evaluation Count:273044	yes Evaluation Count:3038572

273044-3038572

508

uint h = firstNode->h;

executed (the execution status of this line is deduced): uint h = firstNode->h;

509

Node *lastNode = firstNode;

executed (the execution status of this line is deduced): Node *lastNode = firstNode;

510

while (lastNode->next != e && lastNode->next->h == h)

evaluated: lastNode->next != e

TRUE	FALSE
yes Evaluation Count:2704984	yes Evaluation Count:191970

evaluated: lastNode->next->h == h

TRUE	FALSE
yes Evaluation Count:2623910	yes Evaluation Count:81074

81074-2704984

511

lastNode = lastNode->next;

executed: lastNode = lastNode->next;

Execution Count:2623910

2623910

512 -

513

Node *afterLastNode = lastNode->next;

executed (the execution status of this line is deduced): Node *afterLastNode = lastNode->next;

514

Node **beforeFirstNode = &buckets[h % numBuckets];

executed (the execution status of this line is deduced): Node **beforeFirstNode = &buckets[h % numBuckets];

515

while (*beforeFirstNode != e)

evaluated: *beforeFirstNode != e

TRUE	FALSE
yes Evaluation Count:51204	yes Evaluation Count:273044

51204-273044

516

beforeFirstNode = &(*beforeFirstNode)->next;

executed: beforeFirstNode = &(*beforeFirstNode)->next;

Execution Count:51204

51204

517

lastNode->next = *beforeFirstNode;

executed (the execution status of this line is deduced): lastNode->next = *beforeFirstNode;

518

*beforeFirstNode = firstNode;

executed (the execution status of this line is deduced): *beforeFirstNode = firstNode;

519

firstNode = afterLastNode;

executed (the execution status of this line is deduced): firstNode = afterLastNode;

520

}

executed: }

Execution Count:273044

273044

521

}

executed: }

Execution Count:3038572

3038572

522

delete [] oldBuckets;

executed (the execution status of this line is deduced): delete [] oldBuckets;

523

}

executed: }

Execution Count:66583

66583

524

}

executed: }

Execution Count:66587

66587

525 -

526 #ifdef QT_QHASH_DEBUG -

527 -

528 void QHashData::dump() -

529 { -

530 qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)", -

531 int(ref), size, nodeSize, userNumBits, numBits, -

532 numBuckets); -

533 qDebug(" %p (fakeNode = %p)", this, fakeNext); -

534 for (int i = 0; i < numBuckets; ++i) { -

535 QString line; -

536 Node *n = buckets[i]; -

537 if (n != reinterpret_cast<Node *>(this)) { -

538 line.sprintf("%d:", i); -

539 while (n != reinterpret_cast<Node *>(this)) { -

540 line += QString().sprintf(" -> [%p]", n); -

541 if (!n) { -

542 line += " (CORRUPT)"; -

543 break; -

544 } -

545 n = n->next; -

546 } -

547 qDebug("%s", qPrintable(line)); -

548 } -

549 } -

550 } -

551 -

552 void QHashData::checkSanity() -

553 { -

554 if (fakeNext) -

555 qFatal("Fake next isn't 0"); -

556 -

557 for (int i = 0; i < numBuckets; ++i) { -

558 Node *n = buckets[i]; -

559 Node *p = n; -

560 if (!n) -

561 qFatal("%d: Bucket entry is 0", i); -

562 if (n != reinterpret_cast<Node *>(this)) { -

563 while (n != reinterpret_cast<Node *>(this)) { -

564 if (!n->next) -

565 qFatal("%d: Next of %p is 0, should be %p", i, n, this); -

566 n = n->next; -

567 } -

568 } -

569 } -

570 } -

571 #endif -

572 -

573 /*! -

574 \fn uint qHash(const QPair<T1, T2> &key, uint seed = 0) -

575 \since 5.0 -

576 \relates QHash -

577 -

578 Returns the hash value for the \a key, using \a seed to seed the calculation. -

579 -

580 Types \c T1 and \c T2 must be supported by qHash(). -

581 */ -

582 -

583 /*! \fn uint qHash(char key, uint seed = 0) -

584 \relates QHash -

585 \since 5.0 -

586 -

587 Returns the hash value for the \a key, using \a seed to seed the calculation. -

588 */ -

589 -

590 /*! \fn uint qHash(uchar key, uint seed = 0) -

591 \relates QHash -

592 \since 5.0 -

593 -

594 Returns the hash value for the \a key, using \a seed to seed the calculation. -

595 */ -

596 -

597 /*! \fn uint qHash(signed char key, uint seed = 0) -

598 \relates QHash -

599 \since 5.0 -

600 -

601 Returns the hash value for the \a key, using \a seed to seed the calculation. -

602 */ -

603 -

604 /*! \fn uint qHash(ushort key, uint seed = 0) -

605 \relates QHash -

606 \since 5.0 -

607 -

608 Returns the hash value for the \a key, using \a seed to seed the calculation. -

609 */ -

610 -

611 /*! \fn uint qHash(short key, uint seed = 0) -

612 \relates QHash -

613 \since 5.0 -

614 -

615 Returns the hash value for the \a key, using \a seed to seed the calculation. -

616 */ -

617 -

618 /*! \fn uint qHash(uint key, uint seed = 0) -

619 \relates QHash -

620 \since 5.0 -

621 -

622 Returns the hash value for the \a key, using \a seed to seed the calculation. -

623 */ -

624 -

625 /*! \fn uint qHash(int key, uint seed = 0) -

626 \relates QHash -

627 \since 5.0 -

628 -

629 Returns the hash value for the \a key, using \a seed to seed the calculation. -

630 */ -

631 -

632 /*! \fn uint qHash(ulong key, uint seed = 0) -

633 \relates QHash -

634 \since 5.0 -

635 -

636 Returns the hash value for the \a key, using \a seed to seed the calculation. -

637 */ -

638 -

639 /*! \fn uint qHash(long key, uint seed = 0) -

640 \relates QHash -

641 \since 5.0 -

642 -

643 Returns the hash value for the \a key, using \a seed to seed the calculation. -

644 */ -

645 -

646 /*! \fn uint qHash(quint64 key, uint seed = 0) -

647 \relates QHash -

648 \since 5.0 -

649 -

650 Returns the hash value for the \a key, using \a seed to seed the calculation. -

651 */ -

652 -

653 /*! \fn uint qHash(qint64 key, uint seed = 0) -

654 \relates QHash -

655 \since 5.0 -

656 -

657 Returns the hash value for the \a key, using \a seed to seed the calculation. -

658 */ -

659 -

660 /*! \fn uint qHash(QChar key, uint seed = 0) -

661 \relates QHash -

662 \since 5.0 -

663 -

664 Returns the hash value for the \a key, using \a seed to seed the calculation. -

665 */ -

666 -

667 /*! \fn uint qHash(const QByteArray &key, uint seed = 0) -

668 \relates QHash -

669 \since 5.0 -

670 -

671 Returns the hash value for the \a key, using \a seed to seed the calculation. -

672 */ -

673 -

674 /*! \fn uint qHash(const QBitArray &key, uint seed = 0) -

675 \relates QHash -

676 \since 5.0 -

677 -

678 Returns the hash value for the \a key, using \a seed to seed the calculation. -

679 */ -

680 -

681 /*! \fn uint qHash(const QString &key, uint seed = 0) -

682 \relates QHash -

683 \since 5.0 -

684 -

685 Returns the hash value for the \a key, using \a seed to seed the calculation. -

686 */ -

687 -

688 /*! \fn uint qHash(const QStringRef &key, uint seed = 0) -

689 \relates QHash -

690 \since 5.0 -

691 -

692 Returns the hash value for the \a key, using \a seed to seed the calculation. -

693 */ -

694 -

695 /*! \fn uint qHash(QLatin1String key, uint seed = 0) -

696 \relates QHash -

697 \since 5.0 -

698 -

699 Returns the hash value for the \a key, using \a seed to seed the calculation. -

700 */ -

701 -

702 /*! \fn uint qHash(const T *key, uint seed = 0) -

703 \relates QHash -

704 \since 5.0 -

705 -

706 Returns the hash value for the \a key, using \a seed to seed the calculation. -

707 */ -

708 -

709 /*! -

710 \class QHash -

711 \inmodule QtCore -

712 \brief The QHash class is a template class that provides a hash-table-based dictionary. -

713 -

714 \ingroup tools -

715 \ingroup shared -

716 -

717 \reentrant -

718 -

719 QHash\<Key, T\> is one of Qt's generic \l{container classes}. It -

720 stores (key, value) pairs and provides very fast lookup of the -

721 value associated with a key. -

722 -

723 QHash provides very similar functionality to QMap. The -

724 differences are: -

725 -

726 \list -

727 \li QHash provides faster lookups than QMap. (See \l{Algorithmic -

728 Complexity} for details.) -

729 \li When iterating over a QMap, the items are always sorted by -

730 key. With QHash, the items are arbitrarily ordered. -

731 \li The key type of a QMap must provide operator<(). The key -

732 type of a QHash must provide operator==() and a global -

733 hash function called qHash() (see \l{qHash}). -

734 \endlist -

735 -

736 Here's an example QHash with QString keys and \c int values: -

737 \snippet code/src_corelib_tools_qhash.cpp 0 -

738 -

739 To insert a (key, value) pair into the hash, you can use operator[](): -

740 -

741 \snippet code/src_corelib_tools_qhash.cpp 1 -

742 -

743 This inserts the following three (key, value) pairs into the -

744 QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to -

745 insert items into the hash is to use insert(): -

746 -

747 \snippet code/src_corelib_tools_qhash.cpp 2 -

748 -

749 To look up a value, use operator[]() or value(): -

750 -

751 \snippet code/src_corelib_tools_qhash.cpp 3 -

752 -

753 If there is no item with the specified key in the hash, these -

754 functions return a \l{default-constructed value}. -

755 -

756 If you want to check whether the hash contains a particular key, -

757 use contains(): -

758 -

759 \snippet code/src_corelib_tools_qhash.cpp 4 -

760 -

761 There is also a value() overload that uses its second argument as -

762 a default value if there is no item with the specified key: -

763 -

764 \snippet code/src_corelib_tools_qhash.cpp 5 -

765 -

766 In general, we recommend that you use contains() and value() -

767 rather than operator[]() for looking up a key in a hash. The -

768 reason is that operator[]() silently inserts an item into the -

769 hash if no item exists with the same key (unless the hash is -

770 const). For example, the following code snippet will create 1000 -

771 items in memory: -

772 -

773 \snippet code/src_corelib_tools_qhash.cpp 6 -

774 -

775 To avoid this problem, replace \c hash[i] with \c hash.value(i) -

776 in the code above. -

777 -

778 Internally, QHash uses a hash table to perform lookups. Unlike Qt -

779 3's \c QDict class, which needed to be initialized with a prime -

780 number, QHash's hash table automatically grows and shrinks to -

781 provide fast lookups without wasting too much memory. You can -

782 still control the size of the hash table by calling reserve() if -

783 you already know approximately how many items the QHash will -

784 contain, but this isn't necessary to obtain good performance. You -

785 can also call capacity() to retrieve the hash table's size. -

786 -

787 If you want to navigate through all the (key, value) pairs stored -

788 in a QHash, you can use an iterator. QHash provides both -

789 \l{Java-style iterators} (QHashIterator and QMutableHashIterator) -

790 and \l{STL-style iterators} (QHash::const_iterator and -

791 QHash::iterator). Here's how to iterate over a QHash<QString, -

792 int> using a Java-style iterator: -

793 -

794 \snippet code/src_corelib_tools_qhash.cpp 7 -

795 -

796 Here's the same code, but using an STL-style iterator: -

797 -

798 \snippet code/src_corelib_tools_qhash.cpp 8 -

799 -

800 QHash is unordered, so an iterator's sequence cannot be assumed -

801 to be predictable. If ordering by key is required, use a QMap. -

802 -

803 Normally, a QHash allows only one value per key. If you call -

804 insert() with a key that already exists in the QHash, the -

805 previous value is erased. For example: -

806 -

807 \snippet code/src_corelib_tools_qhash.cpp 9 -

808 -

809 However, you can store multiple values per key by using -

810 insertMulti() instead of insert() (or using the convenience -

811 subclass QMultiHash). If you want to retrieve all -

812 the values for a single key, you can use values(const Key &key), -

813 which returns a QList<T>: -

814 -

815 \snippet code/src_corelib_tools_qhash.cpp 10 -

816 -

817 The items that share the same key are available from most -

818 recently to least recently inserted. A more efficient approach is -

819 to call find() to get the iterator for the first item with a key -

820 and iterate from there: -

821 -

822 \snippet code/src_corelib_tools_qhash.cpp 11 -

823 -

824 If you only need to extract the values from a hash (not the keys), -

825 you can also use \l{foreach}: -

826 -

827 \snippet code/src_corelib_tools_qhash.cpp 12 -

828 -

829 Items can be removed from the hash in several ways. One way is to -

830 call remove(); this will remove any item with the given key. -

831 Another way is to use QMutableHashIterator::remove(). In addition, -

832 you can clear the entire hash using clear(). -

833 -

834 QHash's key and value data types must be \l{assignable data -

835 types}. You cannot, for example, store a QWidget as a value; -

836 instead, store a QWidget *. -

837 -

838 \target qHash -

839 \section2 The qHash() hashing function -

840 -

841 A QHash's key type has additional requirements other than being an -

842 assignable data type: it must provide operator==(), and there must also be -

843 a global qHash() function that returns a hash value for an argument of the -

844 key's type. -

845 -

846 The qHash() function computes a numeric value based on a key. It -

847 can use any algorithm imaginable, as long as it always returns -

848 the same value if given the same argument. In other words, if -

849 \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well. -

850 However, to obtain good performance, the qHash() function should -

851 attempt to return different hash values for different keys to the -

852 largest extent possible. -

853 -

854 For a key type \c{K}, the qHash function must have one of these signatures: -

855 -

856 \code -

857 uint qHash(K key); -

858 uint qHash(const K &key); -

859 -

860 uint qHash(K key, uint seed); -

861 uint qHash(const K &key, uint seed); -

862 \endcode -

863 -

864 The two-arguments overloads take an unsigned integer that should be used to -

865 seed the calculation of the hash function. This seed is provided by QHash -

866 in order to prevent a family of \l{algorithmic complexity attacks}. If both -

867 a one-argument and a two-arguments overload are defined for a key type, -

868 the latter is used by QHash (note that you can simply define a -

869 two-arguments version, and use a default value for the seed parameter). -

870 -

871 Here's a partial list of the C++ and Qt types that can serve as keys in a -

872 QHash: any integer type (char, unsigned long, etc.), any pointer type, -

873 QChar, QString, and QByteArray. For all of these, the \c <QHash> header -

874 defines a qHash() function that computes an adequate hash value. Many other -

875 Qt classes also declare a qHash overload for their type; please refer to -

876 the documentation of each class. -

877 -

878 If you want to use other types as the key, make sure that you provide -

879 operator==() and a qHash() implementation. -

880 -

881 Example: -

882 \snippet code/src_corelib_tools_qhash.cpp 13 -

883 -

884 In the example above, we've relied on Qt's global qHash(const -

885 QString &, uint) to give us a hash value for the employee's name, and -

886 XOR'ed this with the day they were born to help produce unique -

887 hashes for people with the same name. -

888 -

889 Note that the implementation of the qHash() overloads offered by Qt -

890 may change at any time. You \b{must not} rely on the fact that qHash() -

891 will give the same results (for the same inputs) across different Qt -

892 versions. -

893 -

894 \section2 Algorithmic complexity attacks -

895 -

896 All hash tables are vulnerable to a particular class of denial of service -

897 attacks, in which the attacker carefully pre-computes a set of different -

898 keys that are going to be hashed in the same bucket of a hash table (or -

899 even have the very same hash value). The attack aims at getting the -

900 worst-case algorithmic behavior (O(n) instead of amortized O(1), see -

901 \l{Algorithmic Complexity} for the details) when the data is fed into the -

902 table. -

903 -

904 In order to avoid this worst-case behavior, the calculation of the hash -

905 value done by qHash() can be salted by a random seed, that nullifies the -

906 attack's extent. This seed is automatically generated by QHash once per -

907 process, and then passed by QHash as the second argument of the -

908 two-arguments overload of the qHash() function. -

909 -

910 This randomization of QHash is enabled by default. Even though programs -

911 should never depend on a particular QHash ordering, there may be situations -

912 where you temporarily need deterministic behavior, e.g. for debugging or -

913 regression testing. To disable the randomization, define the environment -

914 variable \c QT_HASH_SEED. The contents of that variable, interpreted as a -

915 decimal value, will be used as the seed for qHash(). -

916 -

917 \sa QHashIterator, QMutableHashIterator, QMap, QSet -

918 */ -

919 -

920 /*! \fn QHash::QHash() -

921 -

922 Constructs an empty hash. -

923 -

924 \sa clear() -

925 */ -

926 -

927 /*! \fn QHash::QHash(const QHash<Key, T> &other) -

928 -

929 Constructs a copy of \a other. -

930 -

931 This operation occurs in \l{constant time}, because QHash is -

932 \l{implicitly shared}. This makes returning a QHash from a -

933 function very fast. If a shared instance is modified, it will be -

934 copied (copy-on-write), and this takes \l{linear time}. -

935 -

936 \sa operator=() -

937 */ -

938 -

939 /*! \fn QHash::~QHash() -

940 -

941 Destroys the hash. References to the values in the hash and all -

942 iterators of this hash become invalid. -

943 */ -

944 -

945 /*! \fn QHash<Key, T> &QHash::operator=(const QHash<Key, T> &other) -

946 -

947 Assigns \a other to this hash and returns a reference to this hash. -

948 */ -

949 -

950 /*! \fn void QHash::swap(QHash<Key, T> &other) -

951 \since 4.8 -

952 -

953 Swaps hash \a other with this hash. This operation is very -

954 fast and never fails. -

955 */ -

956 -

957 /*! \fn void QMultiHash::swap(QMultiHash<Key, T> &other) -

958 \since 4.8 -

959 -

960 Swaps hash \a other with this hash. This operation is very -

961 fast and never fails. -

962 */ -

963 -

964 /*! \fn bool QHash::operator==(const QHash<Key, T> &other) const -

965 -

966 Returns true if \a other is equal to this hash; otherwise returns -

967 false. -

968 -

969 Two hashes are considered equal if they contain the same (key, -

970 value) pairs. -

971 -

972 This function requires the value type to implement \c operator==(). -

973 -

974 \sa operator!=() -

975 */ -

976 -

977 /*! \fn bool QHash::operator!=(const QHash<Key, T> &other) const -

978 -

979 Returns true if \a other is not equal to this hash; otherwise -

980 returns false. -

981 -

982 Two hashes are considered equal if they contain the same (key, -

983 value) pairs. -

984 -

985 This function requires the value type to implement \c operator==(). -

986 -

987 \sa operator==() -

988 */ -

989 -

990 /*! \fn int QHash::size() const -

991 -

992 Returns the number of items in the hash. -

993 -

994 \sa isEmpty(), count() -

995 */ -

996 -

997 /*! \fn bool QHash::isEmpty() const -

998 -

999 Returns true if the hash contains no items; otherwise returns -

1000 false. -

1001 -

1002 \sa size() -

1003 */ -

1004 -

1005 /*! \fn int QHash::capacity() const -

1006 -

1007 Returns the number of buckets in the QHash's internal hash table. -

1008 -

1009 The sole purpose of this function is to provide a means of fine -

1010 tuning QHash's memory usage. In general, you will rarely ever -

1011 need to call this function. If you want to know how many items are -

1012 in the hash, call size(). -

1013 -

1014 \sa reserve(), squeeze() -

1015 */ -

1016 -

1017 /*! \fn void QHash::reserve(int size) -

1018 -

1019 Ensures that the QHash's internal hash table consists of at least -

1020 \a size buckets. -

1021 -

1022 This function is useful for code that needs to build a huge hash -

1023 and wants to avoid repeated reallocation. For example: -

1024 -

1025 \snippet code/src_corelib_tools_qhash.cpp 14 -

1026 -

1027 Ideally, \a size should be slightly more than the maximum number -

1028 of items expected in the hash. \a size doesn't have to be prime, -

1029 because QHash will use a prime number internally anyway. If \a size -

1030 is an underestimate, the worst that will happen is that the QHash -

1031 will be a bit slower. -

1032 -

1033 In general, you will rarely ever need to call this function. -

1034 QHash's internal hash table automatically shrinks or grows to -

1035 provide good performance without wasting too much memory. -

1036 -

1037 \sa squeeze(), capacity() -

1038 */ -

1039 -

1040 /*! \fn void QHash::squeeze() -

1041 -

1042 Reduces the size of the QHash's internal hash table to save -

1043 memory. -

1044 -

1045 The sole purpose of this function is to provide a means of fine -

1046 tuning QHash's memory usage. In general, you will rarely ever -

1047 need to call this function. -

1048 -

1049 \sa reserve(), capacity() -

1050 */ -

1051 -

1052 /*! \fn void QHash::detach() -

1053 -

1054 \internal -

1055 -

1056 Detaches this hash from any other hashes with which it may share -

1057 data. -

1058 -

1059 \sa isDetached() -

1060 */ -

1061 -

1062 /*! \fn bool QHash::isDetached() const -

1063 -

1064 \internal -

1065 -

1066 Returns true if the hash's internal data isn't shared with any -

1067 other hash object; otherwise returns false. -

1068 -

1069 \sa detach() -

1070 */ -

1071 -

1072 /*! \fn void QHash::setSharable(bool sharable) -

1073 -

1074 \internal -

1075 */ -

1076 -

1077 /*! \fn bool QHash::isSharedWith(const QHash<Key, T> &other) const -

1078 -

1079 \internal -

1080 */ -

1081 -

1082 /*! \fn void QHash::clear() -

1083 -

1084 Removes all items from the hash. -

1085 -

1086 \sa remove() -

1087 */ -

1088 -

1089 /*! \fn int QHash::remove(const Key &key) -

1090 -

1091 Removes all the items that have the \a key from the hash. -

1092 Returns the number of items removed which is usually 1 but will -

1093 be 0 if the key isn't in the hash, or greater than 1 if -

1094 insertMulti() has been used with the \a key. -

1095 -

1096 \sa clear(), take(), QMultiHash::remove() -

1097 */ -

1098 -

1099 /*! \fn T QHash::take(const Key &key) -

1100 -

1101 Removes the item with the \a key from the hash and returns -

1102 the value associated with it. -

1103 -

1104 If the item does not exist in the hash, the function simply -

1105 returns a \l{default-constructed value}. If there are multiple -

1106 items for \a key in the hash, only the most recently inserted one -

1107 is removed. -

1108 -

1109 If you don't use the return value, remove() is more efficient. -

1110 -

1111 \sa remove() -

1112 */ -

1113 -

1114 /*! \fn bool QHash::contains(const Key &key) const -

1115 -

1116 Returns true if the hash contains an item with the \a key; -

1117 otherwise returns false. -

1118 -

1119 \sa count(), QMultiHash::contains() -

1120 */ -

1121 -

1122 /*! \fn const T QHash::value(const Key &key) const -

1123 -

1124 Returns the value associated with the \a key. -

1125 -

1126 If the hash contains no item with the \a key, the function -

1127 returns a \l{default-constructed value}. If there are multiple -

1128 items for the \a key in the hash, the value of the most recently -

1129 inserted one is returned. -

1130 -

1131 \sa key(), values(), contains(), operator[]() -

1132 */ -

1133 -

1134 /*! \fn const T QHash::value(const Key &key, const T &defaultValue) const -

1135 \overload -

1136 -

1137 If the hash contains no item with the given \a key, the function returns -

1138 \a defaultValue. -

1139 */ -

1140 -

1141 /*! \fn T &QHash::operator[](const Key &key) -

1142 -

1143 Returns the value associated with the \a key as a modifiable -

1144 reference. -

1145 -

1146 If the hash contains no item with the \a key, the function inserts -

1147 a \l{default-constructed value} into the hash with the \a key, and -

1148 returns a reference to it. If the hash contains multiple items -

1149 with the \a key, this function returns a reference to the most -

1150 recently inserted value. -

1151 -

1152 \sa insert(), value() -

1153 */ -

1154 -

1155 /*! \fn const T QHash::operator[](const Key &key) const -

1156 -

1157 \overload -

1158 -

1159 Same as value(). -

1160 */ -

1161 -

1162 /*! \fn QList<Key> QHash::uniqueKeys() const -

1163 \since 4.2 -

1164 -

1165 Returns a list containing all the keys in the map. Keys that occur multiple -

1166 times in the map (because items were inserted with insertMulti(), or -

1167 unite() was used) occur only once in the returned list. -

1168 -

1169 \sa keys(), values() -

1170 */ -

1171 -

1172 /*! \fn QList<Key> QHash::keys() const -

1173 -

1174 Returns a list containing all the keys in the hash, in an -

1175 arbitrary order. Keys that occur multiple times in the hash -

1176 (because items were inserted with insertMulti(), or unite() was -

1177 used) also occur multiple times in the list. -

1178 -

1179 To obtain a list of unique keys, where each key from the map only -

1180 occurs once, use uniqueKeys(). -

1181 -

1182 The order is guaranteed to be the same as that used by values(). -

1183 -

1184 \sa uniqueKeys(), values(), key() -

1185 */ -

1186 -

1187 /*! \fn QList<Key> QHash::keys(const T &value) const -

1188 -

1189 \overload -

1190 -

1191 Returns a list containing all the keys associated with value \a -

1192 value, in an arbitrary order. -

1193 -

1194 This function can be slow (\l{linear time}), because QHash's -

1195 internal data structure is optimized for fast lookup by key, not -

1196 by value. -

1197 */ -

1198 -

1199 /*! \fn QList<T> QHash::values() const -

1200 -

1201 Returns a list containing all the values in the hash, in an -

1202 arbitrary order. If a key is associated multiple values, all of -

1203 its values will be in the list, and not just the most recently -

1204 inserted one. -

1205 -

1206 The order is guaranteed to be the same as that used by keys(). -

1207 -

1208 \sa keys(), value() -

1209 */ -

1210 -

1211 /*! \fn QList<T> QHash::values(const Key &key) const -

1212 -

1213 \overload -

1214 -

1215 Returns a list of all the values associated with the \a key, -

1216 from the most recently inserted to the least recently inserted. -

1217 -

1218 \sa count(), insertMulti() -

1219 */ -

1220 -

1221 /*! \fn Key QHash::key(const T &value) const -

1222 -

1223 Returns the first key mapped to \a value. -

1224 -

1225 If the hash contains no item with the \a value, the function -

1226 returns a \l{default-constructed value}{default-constructed key}. -

1227 -

1228 This function can be slow (\l{linear time}), because QHash's -

1229 internal data structure is optimized for fast lookup by key, not -

1230 by value. -

1231 -

1232 \sa value(), keys() -

1233 */ -

1234 -

1235 /*! -

1236 \fn Key QHash::key(const T &value, const Key &defaultKey) const -

1237 \since 4.3 -

1238 \overload -

1239 -

1240 Returns the first key mapped to \a value, or \a defaultKey if the -

1241 hash contains no item mapped to \a value. -

1242 -

1243 This function can be slow (\l{linear time}), because QHash's -

1244 internal data structure is optimized for fast lookup by key, not -

1245 by value. -

1246 */ -

1247 -

1248 /*! \fn int QHash::count(const Key &key) const -

1249 -

1250 Returns the number of items associated with the \a key. -

1251 -

1252 \sa contains(), insertMulti() -

1253 */ -

1254 -

1255 /*! \fn int QHash::count() const -

1256 -

1257 \overload -

1258 -

1259 Same as size(). -

1260 */ -

1261 -

1262 /*! \fn QHash::iterator QHash::begin() -

1263 -

1264 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in -

1265 the hash. -

1266 -

1267 \sa constBegin(), end() -

1268 */ -

1269 -

1270 /*! \fn QHash::const_iterator QHash::begin() const -

1271 -

1272 \overload -

1273 */ -

1274 -

1275 /*! \fn QHash::const_iterator QHash::cbegin() const -

1276 \since 5.0 -

1277 -

1278 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item -

1279 in the hash. -

1280 -

1281 \sa begin(), cend() -

1282 */ -

1283 -

1284 /*! \fn QHash::const_iterator QHash::constBegin() const -

1285 -

1286 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item -

1287 in the hash. -

1288 -

1289 \sa begin(), constEnd() -

1290 */ -

1291 -

1292 /*! \fn QHash::iterator QHash::end() -

1293 -

1294 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item -

1295 after the last item in the hash. -

1296 -

1297 \sa begin(), constEnd() -

1298 */ -

1299 -

1300 /*! \fn QHash::const_iterator QHash::end() const -

1301 -

1302 \overload -

1303 */ -

1304 -

1305 /*! \fn QHash::const_iterator QHash::constEnd() const -

1306 -

1307 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary -

1308 item after the last item in the hash. -

1309 -

1310 \sa constBegin(), end() -

1311 */ -

1312 -

1313 /*! \fn QHash::const_iterator QHash::cend() const -

1314 \since 5.0 -

1315 -

1316 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary -

1317 item after the last item in the hash. -

1318 -

1319 \sa cbegin(), end() -

1320 */ -

1321 -

1322 /*! \fn QHash::iterator QHash::erase(iterator pos) -

1323 -

1324 Removes the (key, value) pair associated with the iterator \a pos -

1325 from the hash, and returns an iterator to the next item in the -

1326 hash. -

1327 -

1328 Unlike remove() and take(), this function never causes QHash to -

1329 rehash its internal data structure. This means that it can safely -

1330 be called while iterating, and won't affect the order of items in -

1331 the hash. For example: -

1332 -

1333 \snippet code/src_corelib_tools_qhash.cpp 15 -

1334 -

1335 \sa remove(), take(), find() -

1336 */ -

1337 -

1338 /*! \fn QHash::iterator QHash::find(const Key &key) -

1339 -

1340 Returns an iterator pointing to the item with the \a key in the -

1341 hash. -

1342 -

1343 If the hash contains no item with the \a key, the function -

1344 returns end(). -

1345 -

1346 If the hash contains multiple items with the \a key, this -

1347 function returns an iterator that points to the most recently -

1348 inserted value. The other values are accessible by incrementing -

1349 the iterator. For example, here's some code that iterates over all -

1350 the items with the same key: -

1351 -

1352 \snippet code/src_corelib_tools_qhash.cpp 16 -

1353 -

1354 \sa value(), values(), QMultiHash::find() -

1355 */ -

1356 -

1357 /*! \fn QHash::const_iterator QHash::find(const Key &key) const -

1358 -

1359 \overload -

1360 */ -

1361 -

1362 /*! \fn QHash::const_iterator QHash::constFind(const Key &key) const -

1363 \since 4.1 -

1364 -

1365 Returns an iterator pointing to the item with the \a key in the -

1366 hash. -

1367 -

1368 If the hash contains no item with the \a key, the function -

1369 returns constEnd(). -

1370 -

1371 \sa find(), QMultiHash::constFind() -

1372 */ -

1373 -

1374 /*! \fn QHash::iterator QHash::insert(const Key &key, const T &value) -

1375 -

1376 Inserts a new item with the \a key and a value of \a value. -

1377 -

1378 If there is already an item with the \a key, that item's value -

1379 is replaced with \a value. -

1380 -

1381 If there are multiple items with the \a key, the most -

1382 recently inserted item's value is replaced with \a value. -

1383 -

1384 \sa insertMulti() -

1385 */ -

1386 -

1387 /*! \fn QHash::iterator QHash::insertMulti(const Key &key, const T &value) -

1388 -

1389 Inserts a new item with the \a key and a value of \a value. -

1390 -

1391 If there is already an item with the same key in the hash, this -

1392 function will simply create a new one. (This behavior is -

1393 different from insert(), which overwrites the value of an -

1394 existing item.) -

1395 -

1396 \sa insert(), values() -

1397 */ -

1398 -

1399 /*! \fn QHash<Key, T> &QHash::unite(const QHash<Key, T> &other) -

1400 -

1401 Inserts all the items in the \a other hash into this hash. If a -

1402 key is common to both hashes, the resulting hash will contain the -

1403 key multiple times. -

1404 -

1405 \sa insertMulti() -

1406 */ -

1407 -

1408 /*! \fn bool QHash::empty() const -

1409 -

1410 This function is provided for STL compatibility. It is equivalent -

1411 to isEmpty(), returning true if the hash is empty; otherwise -

1412 returns false. -

1413 */ -

1414 -

1415 /*! \typedef QHash::ConstIterator -

1416 -

1417 Qt-style synonym for QHash::const_iterator. -

1418 */ -

1419 -

1420 /*! \typedef QHash::Iterator -

1421 -

1422 Qt-style synonym for QHash::iterator. -

1423 */ -

1424 -

1425 /*! \typedef QHash::difference_type -

1426 -

1427 Typedef for ptrdiff_t. Provided for STL compatibility. -

1428 */ -

1429 -

1430 /*! \typedef QHash::key_type -

1431 -

1432 Typedef for Key. Provided for STL compatibility. -

1433 */ -

1434 -

1435 /*! \typedef QHash::mapped_type -

1436 -

1437 Typedef for T. Provided for STL compatibility. -

1438 */ -

1439 -

1440 /*! \typedef QHash::size_type -

1441 -

1442 Typedef for int. Provided for STL compatibility. -

1443 */ -

1444 -

1445 /*! \typedef QHash::iterator::difference_type -

1446 \internal -

1447 */ -

1448 -

1449 /*! \typedef QHash::iterator::iterator_category -

1450 \internal -

1451 */ -

1452 -

1453 /*! \typedef QHash::iterator::pointer -

1454 \internal -

1455 */ -

1456 -

1457 /*! \typedef QHash::iterator::reference -

1458 \internal -

1459 */ -

1460 -

1461 /*! \typedef QHash::iterator::value_type -

1462 \internal -

1463 */ -

1464 -

1465 /*! \typedef QHash::const_iterator::difference_type -

1466 \internal -

1467 */ -

1468 -

1469 /*! \typedef QHash::const_iterator::iterator_category -

1470 \internal -

1471 */ -

1472 -

1473 /*! \typedef QHash::const_iterator::pointer -

1474 \internal -

1475 */ -

1476 -

1477 /*! \typedef QHash::const_iterator::reference -

1478 \internal -

1479 */ -

1480 -

1481 /*! \typedef QHash::const_iterator::value_type -

1482 \internal -

1483 */ -

1484 -

1485 /*! \class QHash::iterator -

1486 \inmodule QtCore -

1487 \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash. -

1488 -

1489 QHash features both \l{STL-style iterators} and \l{Java-style -

1490 iterators}. The STL-style iterators are more low-level and more -

1491 cumbersome to use; on the other hand, they are slightly faster -

1492 and, for developers who already know STL, have the advantage of -

1493 familiarity. -

1494 -

1495 QHash\<Key, T\>::iterator allows you to iterate over a QHash (or -

1496 QMultiHash) and to modify the value (but not the key) associated -

1497 with a particular key. If you want to iterate over a const QHash, -

1498 you should use QHash::const_iterator. It is generally good -

1499 practice to use QHash::const_iterator on a non-const QHash as -

1500 well, unless you need to change the QHash through the iterator. -

1501 Const iterators are slightly faster, and can improve code -

1502 readability. -

1503 -

1504 The default QHash::iterator constructor creates an uninitialized -

1505 iterator. You must initialize it using a QHash function like -

1506 QHash::begin(), QHash::end(), or QHash::find() before you can -

1507 start iterating. Here's a typical loop that prints all the (key, -

1508 value) pairs stored in a hash: -

1509 -

1510 \snippet code/src_corelib_tools_qhash.cpp 17 -

1511 -

1512 Unlike QMap, which orders its items by key, QHash stores its -

1513 items in an arbitrary order. The only guarantee is that items that -

1514 share the same key (because they were inserted using -

1515 QHash::insertMulti()) will appear consecutively, from the most -

1516 recently to the least recently inserted value. -

1517 -

1518 Let's see a few examples of things we can do with a -

1519 QHash::iterator that we cannot do with a QHash::const_iterator. -

1520 Here's an example that increments every value stored in the QHash -

1521 by 2: -

1522 -

1523 \snippet code/src_corelib_tools_qhash.cpp 18 -

1524 -

1525 Here's an example that removes all the items whose key is a -

1526 string that starts with an underscore character: -

1527 -

1528 \snippet code/src_corelib_tools_qhash.cpp 19 -

1529 -

1530 The call to QHash::erase() removes the item pointed to by the -

1531 iterator from the hash, and returns an iterator to the next item. -

1532 Here's another way of removing an item while iterating: -

1533 -

1534 \snippet code/src_corelib_tools_qhash.cpp 20 -

1535 -

1536 It might be tempting to write code like this: -

1537 -

1538 \snippet code/src_corelib_tools_qhash.cpp 21 -

1539 -

1540 However, this will potentially crash in \c{++i}, because \c i is -

1541 a dangling iterator after the call to erase(). -

1542 -

1543 Multiple iterators can be used on the same hash. However, be -

1544 aware that any modification performed directly on the QHash has -

1545 the potential of dramatically changing the order in which the -

1546 items are stored in the hash, as they might cause QHash to rehash -

1547 its internal data structure. There is one notable exception: -

1548 QHash::erase(). This function can safely be called while -

1549 iterating, and won't affect the order of items in the hash. If you -

1550 need to keep iterators over a long period of time, we recommend -

1551 that you use QMap rather than QHash. -

1552 -

1553 \sa QHash::const_iterator, QMutableHashIterator -

1554 */ -

1555 -

1556 /*! \fn QHash::iterator::iterator() -

1557 -

1558 Constructs an uninitialized iterator. -

1559 -

1560 Functions like key(), value(), and operator++() must not be -

1561 called on an uninitialized iterator. Use operator=() to assign a -

1562 value to it before using it. -

1563 -

1564 \sa QHash::begin(), QHash::end() -

1565 */ -

1566 -

1567 /*! \fn QHash::iterator::iterator(void *node) -

1568 -

1569 \internal -

1570 */ -

1571 -

1572 /*! \fn const Key &QHash::iterator::key() const -

1573 -

1574 Returns the current item's key as a const reference. -

1575 -

1576 There is no direct way of changing an item's key through an -

1577 iterator, although it can be done by calling QHash::erase() -

1578 followed by QHash::insert() or QHash::insertMulti(). -

1579 -

1580 \sa value() -

1581 */ -

1582 -

1583 /*! \fn T &QHash::iterator::value() const -

1584 -

1585 Returns a modifiable reference to the current item's value. -

1586 -

1587 You can change the value of an item by using value() on -

1588 the left side of an assignment, for example: -

1589 -

1590 \snippet code/src_corelib_tools_qhash.cpp 22 -

1591 -

1592 \sa key(), operator*() -

1593 */ -

1594 -

1595 /*! \fn T &QHash::iterator::operator*() const -

1596 -

1597 Returns a modifiable reference to the current item's value. -

1598 -

1599 Same as value(). -

1600 -

1601 \sa key() -

1602 */ -

1603 -

1604 /*! \fn T *QHash::iterator::operator->() const -

1605 -

1606 Returns a pointer to the current item's value. -

1607 -

1608 \sa value() -

1609 */ -

1610 -

1611 /*! -

1612 \fn bool QHash::iterator::operator==(const iterator &other) const -

1613 \fn bool QHash::iterator::operator==(const const_iterator &other) const -

1614 -

1615 Returns true if \a other points to the same item as this -

1616 iterator; otherwise returns false. -

1617 -

1618 \sa operator!=() -

1619 */ -

1620 -

1621 /*! -

1622 \fn bool QHash::iterator::operator!=(const iterator &other) const -

1623 \fn bool QHash::iterator::operator!=(const const_iterator &other) const -

1624 -

1625 Returns true if \a other points to a different item than this -

1626 iterator; otherwise returns false. -

1627 -

1628 \sa operator==() -

1629 */ -

1630 -

1631 /*! -

1632 \fn QHash::iterator &QHash::iterator::operator++() -

1633 -

1634 The prefix ++ operator (\c{++i}) advances the iterator to the -

1635 next item in the hash and returns an iterator to the new current -

1636 item. -

1637 -

1638 Calling this function on QHash::end() leads to undefined results. -

1639 -

1640 \sa operator--() -

1641 */ -

1642 -

1643 /*! \fn QHash::iterator QHash::iterator::operator++(int) -

1644 -

1645 \overload -

1646 -

1647 The postfix ++ operator (\c{i++}) advances the iterator to the -

1648 next item in the hash and returns an iterator to the previously -

1649 current item. -

1650 */ -

1651 -

1652 /*! -

1653 \fn QHash::iterator &QHash::iterator::operator--() -

1654 -

1655 The prefix -- operator (\c{--i}) makes the preceding item -

1656 current and returns an iterator pointing to the new current item. -

1657 -

1658 Calling this function on QHash::begin() leads to undefined -

1659 results. -

1660 -

1661 \sa operator++() -

1662 */ -

1663 -

1664 /*! -

1665 \fn QHash::iterator QHash::iterator::operator--(int) -

1666 -

1667 \overload -

1668 -

1669 The postfix -- operator (\c{i--}) makes the preceding item -

1670 current and returns an iterator pointing to the previously -

1671 current item. -

1672 */ -

1673 -

1674 /*! \fn QHash::iterator QHash::iterator::operator+(int j) const -

1675 -

1676 Returns an iterator to the item at \a j positions forward from -

1677 this iterator. (If \a j is negative, the iterator goes backward.) -

1678 -

1679 This operation can be slow for large \a j values. -

1680 -

1681 \sa operator-() -

1682 -

1683 */ -

1684 -

1685 /*! \fn QHash::iterator QHash::iterator::operator-(int j) const -

1686 -

1687 Returns an iterator to the item at \a j positions backward from -

1688 this iterator. (If \a j is negative, the iterator goes forward.) -

1689 -

1690 This operation can be slow for large \a j values. -

1691 -

1692 \sa operator+() -

1693 */ -

1694 -

1695 /*! \fn QHash::iterator &QHash::iterator::operator+=(int j) -

1696 -

1697 Advances the iterator by \a j items. (If \a j is negative, the -

1698 iterator goes backward.) -

1699 -

1700 \sa operator-=(), operator+() -

1701 */ -

1702 -

1703 /*! \fn QHash::iterator &QHash::iterator::operator-=(int j) -

1704 -

1705 Makes the iterator go back by \a j items. (If \a j is negative, -

1706 the iterator goes forward.) -

1707 -

1708 \sa operator+=(), operator-() -

1709 */ -

1710 -

1711 /*! \class QHash::const_iterator -

1712 \inmodule QtCore -

1713 \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash. -

1714 -

1715 QHash features both \l{STL-style iterators} and \l{Java-style -

1716 iterators}. The STL-style iterators are more low-level and more -

1717 cumbersome to use; on the other hand, they are slightly faster -

1718 and, for developers who already know STL, have the advantage of -

1719 familiarity. -

1720 -

1721 QHash\<Key, T\>::const_iterator allows you to iterate over a -

1722 QHash (or a QMultiHash). If you want to modify the QHash as you -

1723 iterate over it, you must use QHash::iterator instead. It is -

1724 generally good practice to use QHash::const_iterator on a -

1725 non-const QHash as well, unless you need to change the QHash -

1726 through the iterator. Const iterators are slightly faster, and -

1727 can improve code readability. -

1728 -

1729 The default QHash::const_iterator constructor creates an -

1730 uninitialized iterator. You must initialize it using a QHash -

1731 function like QHash::constBegin(), QHash::constEnd(), or -

1732 QHash::find() before you can start iterating. Here's a typical -

1733 loop that prints all the (key, value) pairs stored in a hash: -

1734 -

1735 \snippet code/src_corelib_tools_qhash.cpp 23 -

1736 -

1737 Unlike QMap, which orders its items by key, QHash stores its -

1738 items in an arbitrary order. The only guarantee is that items that -

1739 share the same key (because they were inserted using -

1740 QHash::insertMulti()) will appear consecutively, from the most -

1741 recently to the least recently inserted value. -

1742 -

1743 Multiple iterators can be used on the same hash. However, be aware -

1744 that any modification performed directly on the QHash has the -

1745 potential of dramatically changing the order in which the items -

1746 are stored in the hash, as they might cause QHash to rehash its -

1747 internal data structure. If you need to keep iterators over a long -

1748 period of time, we recommend that you use QMap rather than QHash. -

1749 -

1750 \sa QHash::iterator, QHashIterator -

1751 */ -

1752 -

1753 /*! \fn QHash::const_iterator::const_iterator() -

1754 -

1755 Constructs an uninitialized iterator. -

1756 -

1757 Functions like key(), value(), and operator++() must not be -

1758 called on an uninitialized iterator. Use operator=() to assign a -

1759 value to it before using it. -

1760 -

1761 \sa QHash::constBegin(), QHash::constEnd() -

1762 */ -

1763 -

1764 /*! \fn QHash::const_iterator::const_iterator(void *node) -

1765 -

1766 \internal -

1767 */ -

1768 -

1769 /*! \fn QHash::const_iterator::const_iterator(const iterator &other) -

1770 -

1771 Constructs a copy of \a other. -

1772 */ -

1773 -

1774 /*! \fn const Key &QHash::const_iterator::key() const -

1775 -

1776 Returns the current item's key. -

1777 -

1778 \sa value() -

1779 */ -

1780 -

1781 /*! \fn const T &QHash::const_iterator::value() const -

1782 -

1783 Returns the current item's value. -

1784 -

1785 \sa key(), operator*() -

1786 */ -

1787 -

1788 /*! \fn const T &QHash::const_iterator::operator*() const -

1789 -

1790 Returns the current item's value. -

1791 -

1792 Same as value(). -

1793 -

1794 \sa key() -

1795 */ -

1796 -

1797 /*! \fn const T *QHash::const_iterator::operator->() const -

1798 -

1799 Returns a pointer to the current item's value. -

1800 -

1801 \sa value() -

1802 */ -

1803 -

1804 /*! \fn bool QHash::const_iterator::operator==(const const_iterator &other) const -

1805 -

1806 Returns true if \a other points to the same item as this -

1807 iterator; otherwise returns false. -

1808 -

1809 \sa operator!=() -

1810 */ -

1811 -

1812 /*! \fn bool QHash::const_iterator::operator!=(const const_iterator &other) const -

1813 -

1814 Returns true if \a other points to a different item than this -

1815 iterator; otherwise returns false. -

1816 -

1817 \sa operator==() -

1818 */ -

1819 -

1820 /*! -

1821 \fn QHash::const_iterator &QHash::const_iterator::operator++() -

1822 -

1823 The prefix ++ operator (\c{++i}) advances the iterator to the -

1824 next item in the hash and returns an iterator to the new current -

1825 item. -

1826 -

1827 Calling this function on QHash::end() leads to undefined results. -

1828 -

1829 \sa operator--() -

1830 */ -

1831 -

1832 /*! \fn QHash::const_iterator QHash::const_iterator::operator++(int) -

1833 -

1834 \overload -

1835 -

1836 The postfix ++ operator (\c{i++}) advances the iterator to the -

1837 next item in the hash and returns an iterator to the previously -

1838 current item. -

1839 */ -

1840 -

1841 /*! \fn QHash::const_iterator &QHash::const_iterator::operator--() -

1842 -

1843 The prefix -- operator (\c{--i}) makes the preceding item -

1844 current and returns an iterator pointing to the new current item. -

1845 -

1846 Calling this function on QHash::begin() leads to undefined -

1847 results. -

1848 -

1849 \sa operator++() -

1850 */ -

1851 -

1852 /*! \fn QHash::const_iterator QHash::const_iterator::operator--(int) -

1853 -

1854 \overload -

1855 -

1856 The postfix -- operator (\c{i--}) makes the preceding item -

1857 current and returns an iterator pointing to the previously -

1858 current item. -

1859 */ -

1860 -

1861 /*! \fn QHash::const_iterator QHash::const_iterator::operator+(int j) const -

1862 -

1863 Returns an iterator to the item at \a j positions forward from -

1864 this iterator. (If \a j is negative, the iterator goes backward.) -

1865 -

1866 This operation can be slow for large \a j values. -

1867 -

1868 \sa operator-() -

1869 */ -

1870 -

1871 /*! \fn QHash::const_iterator QHash::const_iterator::operator-(int j) const -

1872 -

1873 Returns an iterator to the item at \a j positions backward from -

1874 this iterator. (If \a j is negative, the iterator goes forward.) -

1875 -

1876 This operation can be slow for large \a j values. -

1877 -

1878 \sa operator+() -

1879 */ -

1880 -

1881 /*! \fn QHash::const_iterator &QHash::const_iterator::operator+=(int j) -

1882 -

1883 Advances the iterator by \a j items. (If \a j is negative, the -

1884 iterator goes backward.) -

1885 -

1886 This operation can be slow for large \a j values. -

1887 -

1888 \sa operator-=(), operator+() -

1889 */ -

1890 -

1891 /*! \fn QHash::const_iterator &QHash::const_iterator::operator-=(int j) -

1892 -

1893 Makes the iterator go back by \a j items. (If \a j is negative, -

1894 the iterator goes forward.) -

1895 -

1896 This operation can be slow for large \a j values. -

1897 -

1898 \sa operator+=(), operator-() -

1899 */ -

1900 -

1901 /*! \fn QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash) -

1902 \relates QHash -

1903 -

1904 Writes the hash \a hash to stream \a out. -

1905 -

1906 This function requires the key and value types to implement \c -

1907 operator<<(). -

1908 -

1909 \sa {Serializing Qt Data Types} -

1910 */ -

1911 -

1912 /*! \fn QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash) -

1913 \relates QHash -

1914 -

1915 Reads a hash from stream \a in into \a hash. -

1916 -

1917 This function requires the key and value types to implement \c -

1918 operator>>(). -

1919 -

1920 \sa {Serializing Qt Data Types} -

1921 */ -

1922 -

1923 /*! \class QMultiHash -

1924 \inmodule QtCore -

1925 \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes. -

1926 -

1927 \ingroup tools -

1928 \ingroup shared -

1929 -

1930 \reentrant -

1931 -

1932 QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}. -

1933 It inherits QHash and extends it with a few convenience functions -

1934 that make it more suitable than QHash for storing multi-valued -

1935 hashes. A multi-valued hash is a hash that allows multiple values -

1936 with the same key; QHash normally doesn't allow that, unless you -

1937 call QHash::insertMulti(). -

1938 -

1939 Because QMultiHash inherits QHash, all of QHash's functionality also -

1940 applies to QMultiHash. For example, you can use isEmpty() to test -

1941 whether the hash is empty, and you can traverse a QMultiHash using -

1942 QHash's iterator classes (for example, QHashIterator). But in -

1943 addition, it provides an insert() function that corresponds to -

1944 QHash::insertMulti(), and a replace() function that corresponds to -

1945 QHash::insert(). It also provides convenient operator+() and -

1946 operator+=(). -

1947 -

1948 Example: -

1949 \snippet code/src_corelib_tools_qhash.cpp 24 -

1950 -

1951 Unlike QHash, QMultiHash provides no operator[]. Use value() or -

1952 replace() if you want to access the most recently inserted item -

1953 with a certain key. -

1954 -

1955 If you want to retrieve all the values for a single key, you can -

1956 use values(const Key &key), which returns a QList<T>: -

1957 -

1958 \snippet code/src_corelib_tools_qhash.cpp 25 -

1959 -

1960 The items that share the same key are available from most -

1961 recently to least recently inserted. -

1962 -

1963 A more efficient approach is to call find() to get -

1964 the STL-style iterator for the first item with a key and iterate from -

1965 there: -

1966 -

1967 \snippet code/src_corelib_tools_qhash.cpp 26 -

1968 -

1969 QMultiHash's key and value data types must be \l{assignable data -

1970 types}. You cannot, for example, store a QWidget as a value; -

1971 instead, store a QWidget *. In addition, QMultiHash's key type -

1972 must provide operator==(), and there must also be a global -

1973 qHash() function that returns a hash value for an argument of the -

1974 key's type. See the QHash documentation for details. -

1975 -

1976 \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap -

1977 */ -

1978 -

1979 /*! \fn QMultiHash::QMultiHash() -

1980 -

1981 Constructs an empty hash. -

1982 */ -

1983 -

1984 /*! \fn QMultiHash::QMultiHash(const QHash<Key, T> &other) -

1985 -

1986 Constructs a copy of \a other (which can be a QHash or a -

1987 QMultiHash). -

1988 -

1989 \sa operator=() -

1990 */ -

1991 -

1992 /*! \fn QMultiHash::iterator QMultiHash::replace(const Key &key, const T &value) -

1993 -

1994 Inserts a new item with the \a key and a value of \a value. -

1995 -

1996 If there is already an item with the \a key, that item's value -

1997 is replaced with \a value. -

1998 -

1999 If there are multiple items with the \a key, the most -

2000 recently inserted item's value is replaced with \a value. -

2001 -

2002 \sa insert() -

2003 */ -

2004 -

2005 /*! \fn QMultiHash::iterator QMultiHash::insert(const Key &key, const T &value) -

2006 -

2007 Inserts a new item with the \a key and a value of \a value. -

2008 -

2009 If there is already an item with the same key in the hash, this -

2010 function will simply create a new one. (This behavior is -

2011 different from replace(), which overwrites the value of an -

2012 existing item.) -

2013 -

2014 \sa replace() -

2015 */ -

2016 -

2017 /*! \fn QMultiHash &QMultiHash::operator+=(const QMultiHash &other) -

2018 -

2019 Inserts all the items in the \a other hash into this hash -

2020 and returns a reference to this hash. -

2021 -

2022 \sa insert() -

2023 */ -

2024 -

2025 /*! \fn QMultiHash QMultiHash::operator+(const QMultiHash &other) const -

2026 -

2027 Returns a hash that contains all the items in this hash in -

2028 addition to all the items in \a other. If a key is common to both -

2029 hashes, the resulting hash will contain the key multiple times. -

2030 -

2031 \sa operator+=() -

2032 */ -

2033 -

2034 /*! -

2035 \fn bool QMultiHash::contains(const Key &key, const T &value) const -

2036 \since 4.3 -

2037 -

2038 Returns true if the hash contains an item with the \a key and -

2039 \a value; otherwise returns false. -

2040 -

2041 \sa QHash::contains() -

2042 */ -

2043 -

2044 /*! -

2045 \fn bool QMultiHash::contains(const Key &key) const -

2046 \overload -

2047 \sa QHash::contains() -

2048 */ -

2049 -

2050 /*! -

2051 \fn int QMultiHash::remove(const Key &key, const T &value) -

2052 \since 4.3 -

2053 -

2054 Removes all the items that have the \a key and the value \a -

2055 value from the hash. Returns the number of items removed. -

2056 -

2057 \sa QHash::remove() -

2058 */ -

2059 -

2060 /*! -

2061 \fn int QMultiHash::remove(const Key &key) -

2062 \overload -

2063 \sa QHash::remove() -

2064 */ -

2065 -

2066 /*! -

2067 \fn int QMultiHash::count(const Key &key, const T &value) const -

2068 \since 4.3 -

2069 -

2070 Returns the number of items with the \a key and \a value. -

2071 -

2072 \sa QHash::count() -

2073 */ -

2074 -

2075 /*! -

2076 \fn int QMultiHash::count(const Key &key) const -

2077 \overload -

2078 \sa QHash::count() -

2079 */ -

2080 -

2081 /*! -

2082 \fn int QMultiHash::count() const -

2083 \overload -

2084 \sa QHash::count() -

2085 */ -

2086 -

2087 /*! -

2088 \fn typename QHash<Key, T>::iterator QMultiHash::find(const Key &key, const T &value) -

2089 \since 4.3 -

2090 -

2091 Returns an iterator pointing to the item with the \a key and \a value. -

2092 If the hash contains no such item, the function returns end(). -

2093 -

2094 If the hash contains multiple items with the \a key and \a value, the -

2095 iterator returned points to the most recently inserted item. -

2096 -

2097 \sa QHash::find() -

2098 */ -

2099 -

2100 /*! -

2101 \fn typename QHash<Key, T>::iterator QMultiHash::find(const Key &key) -

2102 \overload -

2103 \sa QHash::find() -

2104 */ -

2105 -

2106 /*! -

2107 \fn typename QHash<Key, T>::const_iterator QMultiHash::find(const Key &key, const T &value) const -

2108 \since 4.3 -

2109 \overload -

2110 */ -

2111 -

2112 /*! -

2113 \fn typename QHash<Key, T>::const_iterator QMultiHash::find(const Key &key) const -

2114 \overload -

2115 \sa QHash::find() -

2116 */ -

2117 -

2118 /*! -

2119 \fn typename QHash<Key, T>::const_iterator QMultiHash::constFind(const Key &key, const T &value) const -

2120 \since 4.3 -

2121 -

2122 Returns an iterator pointing to the item with the \a key and the -

2123 \a value in the hash. -

2124 -

2125 If the hash contains no such item, the function returns -

2126 constEnd(). -

2127 -

2128 \sa QHash::constFind() -

2129 */ -

2130 -

2131 /*! -

2132 \fn typename QHash<Key, T>::const_iterator QMultiHash::constFind(const Key &key) const -

2133 \overload -

2134 \sa QHash::constFind() -

2135 */ -

2136 -

2137 QT_END_NAMESPACE -

2138 -

Source code Switch to Preprocessed file

Generated by Squish Coco Non-Commercial