| Absolute File Name: | /home/qt/qt5_coco/qt5/qtbase/src/corelib/tools/qhash.cpp |
| Source code | Switch to Preprocessed file |
| Line | Source | Count | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | /**************************************************************************** | - | ||||||||||||
| 2 | ** | - | ||||||||||||
| 3 | ** Copyright (C) 2015 The Qt Company Ltd. | - | ||||||||||||
| 4 | ** Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>. | - | ||||||||||||
| 5 | ** Contact: http://www.qt.io/licensing/ | - | ||||||||||||
| 6 | ** | - | ||||||||||||
| 7 | ** This file is part of the QtCore module of the Qt Toolkit. | - | ||||||||||||
| 8 | ** | - | ||||||||||||
| 9 | ** $QT_BEGIN_LICENSE:LGPL21$ | - | ||||||||||||
| 10 | ** Commercial License Usage | - | ||||||||||||
| 11 | ** Licensees holding valid commercial Qt licenses may use this file in | - | ||||||||||||
| 12 | ** accordance with the commercial license agreement provided with the | - | ||||||||||||
| 13 | ** Software or, alternatively, in accordance with the terms contained in | - | ||||||||||||
| 14 | ** a written agreement between you and The Qt Company. For licensing terms | - | ||||||||||||
| 15 | ** and conditions see http://www.qt.io/terms-conditions. For further | - | ||||||||||||
| 16 | ** information use the contact form at http://www.qt.io/contact-us. | - | ||||||||||||
| 17 | ** | - | ||||||||||||
| 18 | ** GNU Lesser General Public License Usage | - | ||||||||||||
| 19 | ** Alternatively, this file may be used under the terms of the GNU Lesser | - | ||||||||||||
| 20 | ** General Public License version 2.1 or version 3 as published by the Free | - | ||||||||||||
| 21 | ** Software Foundation and appearing in the file LICENSE.LGPLv21 and | - | ||||||||||||
| 22 | ** LICENSE.LGPLv3 included in the packaging of this file. Please review the | - | ||||||||||||
| 23 | ** following information to ensure the GNU Lesser General Public License | - | ||||||||||||
| 24 | ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and | - | ||||||||||||
| 25 | ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. | - | ||||||||||||
| 26 | ** | - | ||||||||||||
| 27 | ** As a special exception, The Qt Company gives you certain additional | - | ||||||||||||
| 28 | ** rights. These rights are described in The Qt Company LGPL Exception | - | ||||||||||||
| 29 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. | - | ||||||||||||
| 30 | ** | - | ||||||||||||
| 31 | ** $QT_END_LICENSE$ | - | ||||||||||||
| 32 | ** | - | ||||||||||||
| 33 | ****************************************************************************/ | - | ||||||||||||
| 34 | - | |||||||||||||
| 35 | // for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h. | - | ||||||||||||
| 36 | // put it at the beginning so some indirect inclusion doesn't break it | - | ||||||||||||
| 37 | #ifndef _CRT_RAND_S | - | ||||||||||||
| 38 | #define _CRT_RAND_S | - | ||||||||||||
| 39 | #endif | - | ||||||||||||
| 40 | #include <stdlib.h> | - | ||||||||||||
| 41 | - | |||||||||||||
| 42 | #include "qhash.h" | - | ||||||||||||
| 43 | - | |||||||||||||
| 44 | #ifdef truncate | - | ||||||||||||
| 45 | #undef truncate | - | ||||||||||||
| 46 | #endif | - | ||||||||||||
| 47 | - | |||||||||||||
| 48 | #include <qbitarray.h> | - | ||||||||||||
| 49 | #include <qstring.h> | - | ||||||||||||
| 50 | #include <qglobal.h> | - | ||||||||||||
| 51 | #include <qbytearray.h> | - | ||||||||||||
| 52 | #include <qdatetime.h> | - | ||||||||||||
| 53 | #include <qbasicatomic.h> | - | ||||||||||||
| 54 | #include <qendian.h> | - | ||||||||||||
| 55 | #include <private/qsimd_p.h> | - | ||||||||||||
| 56 | - | |||||||||||||
| 57 | #ifndef QT_BOOTSTRAPPED | - | ||||||||||||
| 58 | #include <qcoreapplication.h> | - | ||||||||||||
| 59 | #endif // QT_BOOTSTRAPPED | - | ||||||||||||
| 60 | - | |||||||||||||
| 61 | #ifdef Q_OS_UNIX | - | ||||||||||||
| 62 | #include <stdio.h> | - | ||||||||||||
| 63 | #include "private/qcore_unix_p.h" | - | ||||||||||||
| 64 | #endif // Q_OS_UNIX | - | ||||||||||||
| 65 | - | |||||||||||||
| 66 | #include <limits.h> | - | ||||||||||||
| 67 | - | |||||||||||||
| 68 | QT_BEGIN_NAMESPACE | - | ||||||||||||
| 69 | - | |||||||||||||
| 70 | /* | - | ||||||||||||
| 71 | The Java's hashing algorithm for strings is a variation of D. J. Bernstein | - | ||||||||||||
| 72 | hashing algorithm appeared here http://cr.yp.to/cdb/cdb.txt | - | ||||||||||||
| 73 | and informally known as DJB33XX - DJB's 33 Times Xor. | - | ||||||||||||
| 74 | Java uses DJB31XA, that is, 31 Times Add. | - | ||||||||||||
| 75 | - | |||||||||||||
| 76 | The original algorithm was a loop around | - | ||||||||||||
| 77 | (h << 5) + h ^ c | - | ||||||||||||
| 78 | (which is indeed h*33 ^ c); it was then changed to | - | ||||||||||||
| 79 | (h << 5) - h ^ c | - | ||||||||||||
| 80 | (so h*31^c: DJB31XX), and the XOR changed to a sum: | - | ||||||||||||
| 81 | (h << 5) - h + c | - | ||||||||||||
| 82 | (DJB31XA), which can save some assembly instructions. | - | ||||||||||||
| 83 | - | |||||||||||||
| 84 | Still, we can avoid writing the multiplication as "(h << 5) - h" | - | ||||||||||||
| 85 | -- the compiler will turn it into a shift and an addition anyway | - | ||||||||||||
| 86 | (for instance, gcc 4.4 does that even at -O0). | - | ||||||||||||
| 87 | */ | - | ||||||||||||
| 88 | - | |||||||||||||
| 89 | #if QT_COMPILER_SUPPORTS_HERE(SSE4_2) | - | ||||||||||||
| 90 | static inline bool hasFastCrc32() | - | ||||||||||||
| 91 | { | - | ||||||||||||
| 92 | return qCpuHasFeature(SSE4_2); executed 2342760 times by 479 tests: return ((qCompilerCpuFeatures & (static_cast<unsigned long long>(1ULL) << CpuFeatureSSE4_2)) || (qCpuFeatures() & (static_cast<unsigned long long>(1ULL) << CpuFeatureSSE4_2)));Executed by:
| 0-2342760 | ||||||||||||
| 93 | } | - | ||||||||||||
| 94 | - | |||||||||||||
| 95 | template <typename Char> | - | ||||||||||||
| 96 | QT_FUNCTION_TARGET(SSE4_2) | - | ||||||||||||
| 97 | static uint crc32(const Char *ptr, size_t len, uint h) | - | ||||||||||||
| 98 | { | - | ||||||||||||
| 99 | // The CRC32 instructions from Nehalem calculate a 32-bit CRC32 checksum | - | ||||||||||||
| 100 | const uchar *p = reinterpret_cast<const uchar *>(ptr); | - | ||||||||||||
| 101 | const uchar *const e = p + (len * sizeof(Char)); | - | ||||||||||||
| 102 | # ifdef Q_PROCESSOR_X86_64 | - | ||||||||||||
| 103 | // The 64-bit instruction still calculates only 32-bit, but without this | - | ||||||||||||
| 104 | // variable GCC 4.9 still tries to clear the high bits on every loop | - | ||||||||||||
| 105 | qulonglong h2 = h; | - | ||||||||||||
| 106 | - | |||||||||||||
| 107 | p += 8; | - | ||||||||||||
| 108 | for ( ; p <= e; p += 8)
| 2342760-3100157 | ||||||||||||
| 109 | h2 = _mm_crc32_u64(h2, qFromUnaligned<qlonglong>(p - 8)); executed 3100157 times by 459 tests: h2 = _mm_crc32_u64(h2, qFromUnaligned<qlonglong>(p - 8));Executed by:
| 3100157 | ||||||||||||
| 110 | h = h2; | - | ||||||||||||
| 111 | p -= 8; | - | ||||||||||||
| 112 | - | |||||||||||||
| 113 | len = e - p; | - | ||||||||||||
| 114 | if (len & 4) {
| 838710-1504050 | ||||||||||||
| 115 | h = _mm_crc32_u32(h, qFromUnaligned<uint>(p)); | - | ||||||||||||
| 116 | p += 4; | - | ||||||||||||
| 117 | } executed 838710 times by 428 tests: end of blockExecuted by:
| 838710 | ||||||||||||
| 118 | # else | - | ||||||||||||
| 119 | p += 4; | - | ||||||||||||
| 120 | for ( ; p <= e; p += 4) | - | ||||||||||||
| 121 | h = _mm_crc32_u32(h, qFromUnaligned<uint>(p - 4)); | - | ||||||||||||
| 122 | p -= 4; | - | ||||||||||||
| 123 | len = e - p; | - | ||||||||||||
| 124 | # endif | - | ||||||||||||
| 125 | if (len & 2) {
| 853228-1489532 | ||||||||||||
| 126 | h = _mm_crc32_u16(h, qFromUnaligned<ushort>(p)); | - | ||||||||||||
| 127 | p += 2; | - | ||||||||||||
| 128 | } executed 1489532 times by 459 tests: end of blockExecuted by:
| 1489532 | ||||||||||||
| 129 | if (sizeof(Char) == 1 && len & 1)
| 41156-2206713 | ||||||||||||
| 130 | h = _mm_crc32_u8(h, *p); executed 41156 times by 325 tests: h = _mm_crc32_u8(h, *p);Executed by:
| 41156 | ||||||||||||
| 131 | return h; executed 2342760 times by 479 tests: return h;Executed by:
| 2342760 | ||||||||||||
| 132 | } | - | ||||||||||||
| 133 | #else | - | ||||||||||||
| 134 | static inline bool hasFastCrc32() | - | ||||||||||||
| 135 | { | - | ||||||||||||
| 136 | return false; | - | ||||||||||||
| 137 | } | - | ||||||||||||
| 138 | - | |||||||||||||
| 139 | static uint crc32(...) | - | ||||||||||||
| 140 | { | - | ||||||||||||
| 141 | Q_UNREACHABLE(); | - | ||||||||||||
| 142 | return 0; | - | ||||||||||||
| 143 | } | - | ||||||||||||
| 144 | #endif | - | ||||||||||||
| 145 | - | |||||||||||||
| 146 | static inline uint hash(const uchar *p, int len, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 147 | { | - | ||||||||||||
| 148 | uint h = seed; | - | ||||||||||||
| 149 | - | |||||||||||||
| 150 | if (hasFastCrc32())
| 0-136047 | ||||||||||||
| 151 | return crc32(p, size_t(len), h); executed 136047 times by 399 tests: return crc32(p, size_t(len), h);Executed by:
| 136047 | ||||||||||||
| 152 | - | |||||||||||||
| 153 | for (int i = 0; i < len; ++i)
| 0 | ||||||||||||
| 154 | h = 31 * h + p[i]; never executed: h = 31 * h + p[i]; | 0 | ||||||||||||
| 155 | - | |||||||||||||
| 156 | return h; never executed: return h; | 0 | ||||||||||||
| 157 | } | - | ||||||||||||
| 158 | - | |||||||||||||
| 159 | uint qHashBits(const void *p, size_t len, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 160 | { | - | ||||||||||||
| 161 | return hash(static_cast<const uchar*>(p), int(len), seed); executed 10 times by 1 test: return hash(static_cast<const uchar*>(p), int(len), seed);Executed by:
| 10 | ||||||||||||
| 162 | } | - | ||||||||||||
| 163 | - | |||||||||||||
| 164 | static inline uint hash(const QChar *p, int len, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 165 | { | - | ||||||||||||
| 166 | uint h = seed; | - | ||||||||||||
| 167 | - | |||||||||||||
| 168 | if (hasFastCrc32())
| 0-2206713 | ||||||||||||
| 169 | return crc32(p, size_t(len), h); executed 2206713 times by 442 tests: return crc32(p, size_t(len), h);Executed by:
| 2206713 | ||||||||||||
| 170 | - | |||||||||||||
| 171 | for (int i = 0; i < len; ++i)
| 0 | ||||||||||||
| 172 | h = 31 * h + p[i].unicode(); never executed: h = 31 * h + p[i].unicode(); | 0 | ||||||||||||
| 173 | - | |||||||||||||
| 174 | return h; never executed: return h; | 0 | ||||||||||||
| 175 | } | - | ||||||||||||
| 176 | - | |||||||||||||
| 177 | uint qHash(const QByteArray &key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 178 | { | - | ||||||||||||
| 179 | return hash(reinterpret_cast<const uchar *>(key.constData()), key.size(), seed); executed 100610 times by 395 tests: return hash(reinterpret_cast<const uchar *>(key.constData()), key.size(), seed);Executed by:
| 100610 | ||||||||||||
| 180 | } | - | ||||||||||||
| 181 | - | |||||||||||||
| 182 | uint qHash(const QString &key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 183 | { | - | ||||||||||||
| 184 | return hash(key.unicode(), key.size(), seed); executed 2206701 times by 442 tests: return hash(key.unicode(), key.size(), seed);Executed by:
| 2206701 | ||||||||||||
| 185 | } | - | ||||||||||||
| 186 | - | |||||||||||||
| 187 | uint qHash(const QStringRef &key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 188 | { | - | ||||||||||||
| 189 | return hash(key.unicode(), key.size(), seed); executed 12 times by 1 test: return hash(key.unicode(), key.size(), seed);Executed by:
| 12 | ||||||||||||
| 190 | } | - | ||||||||||||
| 191 | - | |||||||||||||
| 192 | uint qHash(const QBitArray &bitArray, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 193 | { | - | ||||||||||||
| 194 | int m = bitArray.d.size() - 1; | - | ||||||||||||
| 195 | uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()), qMax(0, m), seed); | - | ||||||||||||
| 196 | - | |||||||||||||
| 197 | // deal with the last 0 to 7 bits manually, because we can't trust that | - | ||||||||||||
| 198 | // the padding is initialized to 0 in bitArray.d | - | ||||||||||||
| 199 | int n = bitArray.size(); | - | ||||||||||||
| 200 | if (n & 0x7)
| 1-9 | ||||||||||||
| 201 | result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1); executed 9 times by 1 test: result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);Executed by:
| 9 | ||||||||||||
| 202 | return result; executed 10 times by 1 test: return result;Executed by:
| 10 | ||||||||||||
| 203 | } | - | ||||||||||||
| 204 | - | |||||||||||||
| 205 | uint qHash(QLatin1String key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 206 | { | - | ||||||||||||
| 207 | return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed); executed 18091 times by 1 test: return hash(reinterpret_cast<const uchar *>(key.data()), key.size(), seed);Executed by:
| 18091 | ||||||||||||
| 208 | } | - | ||||||||||||
| 209 | - | |||||||||||||
| 210 | /*! | - | ||||||||||||
| 211 | \internal | - | ||||||||||||
| 212 | - | |||||||||||||
| 213 | Creates the QHash random seed from various sources. | - | ||||||||||||
| 214 | In order of decreasing precedence: | - | ||||||||||||
| 215 | - under Unix, it attemps to read from /dev/urandom; | - | ||||||||||||
| 216 | - under Unix, it attemps to read from /dev/random; | - | ||||||||||||
| 217 | - under Windows, it attempts to use rand_s; | - | ||||||||||||
| 218 | - as a general fallback, the application's PID, a timestamp and the | - | ||||||||||||
| 219 | address of a stack-local variable are used. | - | ||||||||||||
| 220 | */ | - | ||||||||||||
| 221 | static uint qt_create_qhash_seed() | - | ||||||||||||
| 222 | { | - | ||||||||||||
| 223 | uint seed = 0; | - | ||||||||||||
| 224 | - | |||||||||||||
| 225 | #ifndef QT_BOOTSTRAPPED | - | ||||||||||||
| 226 | QByteArray envSeed = qgetenv("QT_HASH_SEED"); | - | ||||||||||||
| 227 | if (!envSeed.isNull())
| 0-1108 | ||||||||||||
| 228 | return envSeed.toUInt(); never executed: return envSeed.toUInt(); | 0 | ||||||||||||
| 229 | - | |||||||||||||
| 230 | #ifdef Q_OS_UNIX | - | ||||||||||||
| 231 | int randomfd = qt_safe_open("/dev/urandom", O_RDONLY); | - | ||||||||||||
| 232 | if (randomfd == -1)
| 0-1108 | ||||||||||||
| 233 | randomfd = qt_safe_open("/dev/random", O_RDONLY | O_NONBLOCK); never executed: randomfd = qt_safe_open("/dev/random", 00 | 04000); | 0 | ||||||||||||
| 234 | if (randomfd != -1) {
| 0-1108 | ||||||||||||
| 235 | if (qt_safe_read(randomfd, reinterpret_cast<char *>(&seed), sizeof(seed)) == sizeof(seed)) {
| 0-1108 | ||||||||||||
| 236 | qt_safe_close(randomfd); | - | ||||||||||||
| 237 | return seed; executed 1108 times by 148 tests: return seed;Executed by:
| 1108 | ||||||||||||
| 238 | } | - | ||||||||||||
| 239 | qt_safe_close(randomfd); | - | ||||||||||||
| 240 | } never executed: end of block | 0 | ||||||||||||
| 241 | #endif // Q_OS_UNIX | - | ||||||||||||
| 242 | - | |||||||||||||
| 243 | #if defined(Q_OS_WIN32) && !defined(Q_CC_GNU) | - | ||||||||||||
| 244 | errno_t err; | - | ||||||||||||
| 245 | err = rand_s(&seed); | - | ||||||||||||
| 246 | if (err == 0) | - | ||||||||||||
| 247 | return seed; | - | ||||||||||||
| 248 | #endif // Q_OS_WIN32 | - | ||||||||||||
| 249 | - | |||||||||||||
| 250 | // general fallback: initialize from the current timestamp, pid, | - | ||||||||||||
| 251 | // and address of a stack-local variable | - | ||||||||||||
| 252 | quint64 timestamp = QDateTime::currentMSecsSinceEpoch(); | - | ||||||||||||
| 253 | seed ^= timestamp; | - | ||||||||||||
| 254 | seed ^= (timestamp >> 32); | - | ||||||||||||
| 255 | - | |||||||||||||
| 256 | quint64 pid = QCoreApplication::applicationPid(); | - | ||||||||||||
| 257 | seed ^= pid; | - | ||||||||||||
| 258 | seed ^= (pid >> 32); | - | ||||||||||||
| 259 | - | |||||||||||||
| 260 | quintptr seedPtr = reinterpret_cast<quintptr>(&seed); | - | ||||||||||||
| 261 | seed ^= seedPtr; | - | ||||||||||||
| 262 | seed ^= (qulonglong(seedPtr) >> 32); // no-op on 32-bit platforms | - | ||||||||||||
| 263 | #endif // QT_BOOTSTRAPPED | - | ||||||||||||
| 264 | - | |||||||||||||
| 265 | return seed; never executed: return seed; | 0 | ||||||||||||
| 266 | } | - | ||||||||||||
| 267 | - | |||||||||||||
| 268 | /* | - | ||||||||||||
| 269 | The QHash seed itself. | - | ||||||||||||
| 270 | */ | - | ||||||||||||
| 271 | Q_CORE_EXPORT QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1); | - | ||||||||||||
| 272 | - | |||||||||||||
| 273 | /*! | - | ||||||||||||
| 274 | \internal | - | ||||||||||||
| 275 | - | |||||||||||||
| 276 | Seed == -1 means it that it was not initialized yet. | - | ||||||||||||
| 277 | - | |||||||||||||
| 278 | We let qt_create_qhash_seed return any unsigned integer, | - | ||||||||||||
| 279 | but convert it to signed in order to initialize the seed. | - | ||||||||||||
| 280 | - | |||||||||||||
| 281 | We don't actually care about the fact that different calls to | - | ||||||||||||
| 282 | qt_create_qhash_seed() might return different values, | - | ||||||||||||
| 283 | as long as in the end everyone uses the very same value. | - | ||||||||||||
| 284 | */ | - | ||||||||||||
| 285 | static void qt_initialize_qhash_seed() | - | ||||||||||||
| 286 | { | - | ||||||||||||
| 287 | if (qt_qhash_seed.load() == -1) {
| 1107-114754 | ||||||||||||
| 288 | int x(qt_create_qhash_seed() & INT_MAX); | - | ||||||||||||
| 289 | qt_qhash_seed.testAndSetRelaxed(-1, x); | - | ||||||||||||
| 290 | } executed 1107 times by 147 tests: end of blockExecuted by:
| 1107 | ||||||||||||
| 291 | } executed 115861 times by 537 tests: end of blockExecuted by:
| 115861 | ||||||||||||
| 292 | - | |||||||||||||
| 293 | /*! \relates QHash | - | ||||||||||||
| 294 | \since 5.6 | - | ||||||||||||
| 295 | - | |||||||||||||
| 296 | Returns the current global QHash seed. | - | ||||||||||||
| 297 | - | |||||||||||||
| 298 | The seed is set in any newly created QHash. See \l{qHash} about how this seed | - | ||||||||||||
| 299 | is being used by QHash. | - | ||||||||||||
| 300 | - | |||||||||||||
| 301 | \sa qSetGlobalQHashSeed | - | ||||||||||||
| 302 | */ | - | ||||||||||||
| 303 | int qGlobalQHashSeed() | - | ||||||||||||
| 304 | { | - | ||||||||||||
| 305 | return qt_qhash_seed.load(); executed 3 times by 1 test: return qt_qhash_seed.load();Executed by:
| 3 | ||||||||||||
| 306 | } | - | ||||||||||||
| 307 | - | |||||||||||||
| 308 | /*! \relates QHash | - | ||||||||||||
| 309 | \since 5.6 | - | ||||||||||||
| 310 | - | |||||||||||||
| 311 | Sets the global QHash seed to \a newSeed. | - | ||||||||||||
| 312 | - | |||||||||||||
| 313 | Manually setting the global QHash seed value should be done only for testing | - | ||||||||||||
| 314 | and debugging purposes, when deterministic and reproducible behavior on a QHash | - | ||||||||||||
| 315 | is needed. We discourage to do it in production code as it can make your | - | ||||||||||||
| 316 | application susceptible to \l{algorithmic complexity attacks}. | - | ||||||||||||
| 317 | - | |||||||||||||
| 318 | The seed is set in any newly created QHash. See \l{qHash} about how this seed | - | ||||||||||||
| 319 | is being used by QHash. | - | ||||||||||||
| 320 | - | |||||||||||||
| 321 | If the environment variable \c QT_HASH_SEED is set, calling this function will | - | ||||||||||||
| 322 | result in a no-op. | - | ||||||||||||
| 323 | - | |||||||||||||
| 324 | Passing the value -1 will reinitialize the global QHash seed to a random value. | - | ||||||||||||
| 325 | - | |||||||||||||
| 326 | \sa qGlobalQHashSeed | - | ||||||||||||
| 327 | */ | - | ||||||||||||
| 328 | void qSetGlobalQHashSeed(int newSeed) | - | ||||||||||||
| 329 | { | - | ||||||||||||
| 330 | if (qEnvironmentVariableIsSet("QT_HASH_SEED"))
| 0-6 | ||||||||||||
| 331 | return; never executed: return; | 0 | ||||||||||||
| 332 | if (newSeed == -1) {
| 1-5 | ||||||||||||
| 333 | int x(qt_create_qhash_seed() & INT_MAX); | - | ||||||||||||
| 334 | qt_qhash_seed.store(x); | - | ||||||||||||
| 335 | } else { executed 1 time by 1 test: end of blockExecuted by:
| 1 | ||||||||||||
| 336 | qt_qhash_seed.store(newSeed & INT_MAX); | - | ||||||||||||
| 337 | } executed 5 times by 3 tests: end of blockExecuted by:
| 5 | ||||||||||||
| 338 | } | - | ||||||||||||
| 339 | - | |||||||||||||
| 340 | /*! | - | ||||||||||||
| 341 | \internal | - | ||||||||||||
| 342 | - | |||||||||||||
| 343 | Private copy of the implementation of the Qt 4 qHash algorithm for strings, | - | ||||||||||||
| 344 | (that is, QChar-based arrays, so all QString-like classes), | - | ||||||||||||
| 345 | to be used wherever the result is somehow stored or reused across multiple | - | ||||||||||||
| 346 | Qt versions. The public qHash implementation can change at any time, | - | ||||||||||||
| 347 | therefore one must not rely on the fact that it will always give the same | - | ||||||||||||
| 348 | results. | - | ||||||||||||
| 349 | - | |||||||||||||
| 350 | The qt_hash functions must *never* change their results. | - | ||||||||||||
| 351 | */ | - | ||||||||||||
| 352 | static uint qt_hash(const QChar *p, int n) Q_DECL_NOTHROW | - | ||||||||||||
| 353 | { | - | ||||||||||||
| 354 | uint h = 0; | - | ||||||||||||
| 355 | - | |||||||||||||
| 356 | while (n--) {
| 368933-3646531 | ||||||||||||
| 357 | h = (h << 4) + (*p++).unicode(); | - | ||||||||||||
| 358 | h ^= (h & 0xf0000000) >> 23; | - | ||||||||||||
| 359 | h &= 0x0fffffff; | - | ||||||||||||
| 360 | } executed 3646531 times by 115 tests: end of blockExecuted by:
| 3646531 | ||||||||||||
| 361 | return h; executed 368933 times by 115 tests: return h;Executed by:
| 368933 | ||||||||||||
| 362 | } | - | ||||||||||||
| 363 | - | |||||||||||||
| 364 | /*! | - | ||||||||||||
| 365 | \internal | - | ||||||||||||
| 366 | \overload | - | ||||||||||||
| 367 | */ | - | ||||||||||||
| 368 | uint qt_hash(const QString &key) Q_DECL_NOTHROW | - | ||||||||||||
| 369 | { | - | ||||||||||||
| 370 | return qt_hash(key.unicode(), key.size()); executed 769 times by 4 tests: return qt_hash(key.unicode(), key.size());Executed by:
| 769 | ||||||||||||
| 371 | } | - | ||||||||||||
| 372 | - | |||||||||||||
| 373 | /*! | - | ||||||||||||
| 374 | \internal | - | ||||||||||||
| 375 | \overload | - | ||||||||||||
| 376 | */ | - | ||||||||||||
| 377 | uint qt_hash(const QStringRef &key) Q_DECL_NOTHROW | - | ||||||||||||
| 378 | { | - | ||||||||||||
| 379 | return qt_hash(key.unicode(), key.size()); executed 368164 times by 112 tests: return qt_hash(key.unicode(), key.size());Executed by:
| 368164 | ||||||||||||
| 380 | } | - | ||||||||||||
| 381 | - | |||||||||||||
| 382 | /* | - | ||||||||||||
| 383 | The prime_deltas array contains the difference between a power | - | ||||||||||||
| 384 | of two and the next prime number: | - | ||||||||||||
| 385 | - | |||||||||||||
| 386 | prime_deltas[i] = nextprime(2^i) - 2^i | - | ||||||||||||
| 387 | - | |||||||||||||
| 388 | Basically, it's sequence A092131 from OEIS, assuming: | - | ||||||||||||
| 389 | - nextprime(1) = 1 | - | ||||||||||||
| 390 | - nextprime(2) = 2 | - | ||||||||||||
| 391 | and | - | ||||||||||||
| 392 | - left-extending it for the offset 0 (A092131 starts at i=1) | - | ||||||||||||
| 393 | - stopping the sequence at i = 28 (the table is big enough...) | - | ||||||||||||
| 394 | */ | - | ||||||||||||
| 395 | - | |||||||||||||
| 396 | static const uchar prime_deltas[] = { | - | ||||||||||||
| 397 | 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3, | - | ||||||||||||
| 398 | 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 0, 0, 0, 0, 0 | - | ||||||||||||
| 399 | }; | - | ||||||||||||
| 400 | - | |||||||||||||
| 401 | /* | - | ||||||||||||
| 402 | The primeForNumBits() function returns the prime associated to a | - | ||||||||||||
| 403 | power of two. For example, primeForNumBits(8) returns 257. | - | ||||||||||||
| 404 | */ | - | ||||||||||||
| 405 | - | |||||||||||||
| 406 | static inline int primeForNumBits(int numBits) | - | ||||||||||||
| 407 | { | - | ||||||||||||
| 408 | return (1 << numBits) + prime_deltas[numBits]; executed 152194 times by 539 tests: return (1 << numBits) + prime_deltas[numBits];Executed by:
| 152194 | ||||||||||||
| 409 | } | - | ||||||||||||
| 410 | - | |||||||||||||
| 411 | /* | - | ||||||||||||
| 412 | Returns the smallest integer n such that | - | ||||||||||||
| 413 | primeForNumBits(n) >= hint. | - | ||||||||||||
| 414 | */ | - | ||||||||||||
| 415 | static int countBits(int hint) | - | ||||||||||||
| 416 | { | - | ||||||||||||
| 417 | int numBits = 0; | - | ||||||||||||
| 418 | int bits = hint; | - | ||||||||||||
| 419 | - | |||||||||||||
| 420 | while (bits > 1) {
| 6779-14479 | ||||||||||||
| 421 | bits >>= 1; | - | ||||||||||||
| 422 | numBits++; | - | ||||||||||||
| 423 | } executed 6779 times by 135 tests: end of blockExecuted by:
| 6779 | ||||||||||||
| 424 | - | |||||||||||||
| 425 | if (numBits >= (int)sizeof(prime_deltas)) {
| 0-14479 | ||||||||||||
| 426 | numBits = sizeof(prime_deltas) - 1; | - | ||||||||||||
| 427 | } else if (primeForNumBits(numBits) < hint) { never executed: end of block
| 0-12884 | ||||||||||||
| 428 | ++numBits; | - | ||||||||||||
| 429 | } executed 1595 times by 132 tests: end of blockExecuted by:
| 1595 | ||||||||||||
| 430 | return numBits; executed 14479 times by 161 tests: return numBits;Executed by:
| 14479 | ||||||||||||
| 431 | } | - | ||||||||||||
| 432 | - | |||||||||||||
| 433 | /* | - | ||||||||||||
| 434 | A QHash has initially around pow(2, MinNumBits) buckets. For | - | ||||||||||||
| 435 | example, if MinNumBits is 4, it has 17 buckets. | - | ||||||||||||
| 436 | */ | - | ||||||||||||
| 437 | const int MinNumBits = 4; | - | ||||||||||||
| 438 | - | |||||||||||||
| 439 | const QHashData QHashData::shared_null = { | - | ||||||||||||
| 440 | 0, 0, Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, MinNumBits, 0, 0, 0, true, false, 0 | - | ||||||||||||
| 441 | }; | - | ||||||||||||
| 442 | - | |||||||||||||
| 443 | void *QHashData::allocateNode(int nodeAlign) | - | ||||||||||||
| 444 | { | - | ||||||||||||
| 445 | void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : malloc(nodeSize);
| 600-6677060 | ||||||||||||
| 446 | Q_CHECK_PTR(ptr); never executed: qBadAlloc();
| 0-6677660 | ||||||||||||
| 447 | return ptr; executed 6677660 times by 542 tests: return ptr;Executed by:
| 6677660 | ||||||||||||
| 448 | } | - | ||||||||||||
| 449 | - | |||||||||||||
| 450 | void QHashData::freeNode(void *node) | - | ||||||||||||
| 451 | { | - | ||||||||||||
| 452 | if (strictAlignment)
| 600-6678971 | ||||||||||||
| 453 | qFreeAligned(node); executed 600 times by 1 test: qFreeAligned(node);Executed by:
| 600 | ||||||||||||
| 454 | else | - | ||||||||||||
| 455 | free(node); executed 6678971 times by 698 tests: free(node);Executed by:
| 6678971 | ||||||||||||
| 456 | } | - | ||||||||||||
| 457 | - | |||||||||||||
| 458 | QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), | - | ||||||||||||
| 459 | void (*node_delete)(Node *), | - | ||||||||||||
| 460 | int nodeSize, | - | ||||||||||||
| 461 | int nodeAlign) | - | ||||||||||||
| 462 | { | - | ||||||||||||
| 463 | union { | - | ||||||||||||
| 464 | QHashData *d; | - | ||||||||||||
| 465 | Node *e; | - | ||||||||||||
| 466 | }; | - | ||||||||||||
| 467 | if (this == &shared_null)
| 12278-115861 | ||||||||||||
| 468 | qt_initialize_qhash_seed(); // may throw executed 115861 times by 537 tests: qt_initialize_qhash_seed();Executed by:
| 115861 | ||||||||||||
| 469 | d = new QHashData; | - | ||||||||||||
| 470 | d->fakeNext = 0; | - | ||||||||||||
| 471 | d->buckets = 0; | - | ||||||||||||
| 472 | d->ref.initializeOwned(); | - | ||||||||||||
| 473 | d->size = size; | - | ||||||||||||
| 474 | d->nodeSize = nodeSize; | - | ||||||||||||
| 475 | d->userNumBits = userNumBits; | - | ||||||||||||
| 476 | d->numBits = numBits; | - | ||||||||||||
| 477 | d->numBuckets = numBuckets; | - | ||||||||||||
| 478 | d->seed = (this == &shared_null) ? uint(qt_qhash_seed.load()) : seed;
| 12278-115861 | ||||||||||||
| 479 | d->sharable = true; | - | ||||||||||||
| 480 | d->strictAlignment = nodeAlign > 8; | - | ||||||||||||
| 481 | d->reserved = 0; | - | ||||||||||||
| 482 | - | |||||||||||||
| 483 | if (numBuckets) {
| 12278-115861 | ||||||||||||
| 484 | QT_TRY { | - | ||||||||||||
| 485 | d->buckets = new Node *[numBuckets]; | - | ||||||||||||
| 486 | } QT_CATCH(...) { executed 12278 times by 50 tests: end of blockExecuted by:
| 12278 | ||||||||||||
| 487 | // restore a consistent state for d | - | ||||||||||||
| 488 | d->numBuckets = 0; | - | ||||||||||||
| 489 | // roll back | - | ||||||||||||
| 490 | d->free_helper(node_delete); | - | ||||||||||||
| 491 | QT_RETHROW; never executed: throw; | 0 | ||||||||||||
| 492 | } | - | ||||||||||||
| 493 | - | |||||||||||||
| 494 | Node *this_e = reinterpret_cast<Node *>(this); | - | ||||||||||||
| 495 | for (int i = 0; i < numBuckets; ++i) {
| 12278-377426 | ||||||||||||
| 496 | Node **nextNode = &d->buckets[i]; | - | ||||||||||||
| 497 | Node *oldNode = buckets[i]; | - | ||||||||||||
| 498 | while (oldNode != this_e) {
| 175811-377426 | ||||||||||||
| 499 | QT_TRY { | - | ||||||||||||
| 500 | Node *dup = static_cast<Node *>(allocateNode(nodeAlign)); | - | ||||||||||||
| 501 | - | |||||||||||||
| 502 | QT_TRY { | - | ||||||||||||
| 503 | node_duplicate(oldNode, dup); | - | ||||||||||||
| 504 | } QT_CATCH(...) { executed 175811 times by 50 tests: end of blockExecuted by:
| 175811 | ||||||||||||
| 505 | freeNode( dup ); | - | ||||||||||||
| 506 | QT_RETHROW; never executed: throw; | 0 | ||||||||||||
| 507 | } | - | ||||||||||||
| 508 | - | |||||||||||||
| 509 | *nextNode = dup; | - | ||||||||||||
| 510 | nextNode = &dup->next; | - | ||||||||||||
| 511 | oldNode = oldNode->next; | - | ||||||||||||
| 512 | } QT_CATCH(...) { executed 175811 times by 50 tests: end of blockExecuted by:
| 175811 | ||||||||||||
| 513 | // restore a consistent state for d | - | ||||||||||||
| 514 | *nextNode = e; | - | ||||||||||||
| 515 | d->numBuckets = i+1; | - | ||||||||||||
| 516 | // roll back | - | ||||||||||||
| 517 | d->free_helper(node_delete); | - | ||||||||||||
| 518 | QT_RETHROW; never executed: throw; | 0 | ||||||||||||
| 519 | } | - | ||||||||||||
| 520 | } | - | ||||||||||||
| 521 | *nextNode = e; | - | ||||||||||||
| 522 | } executed 377426 times by 50 tests: end of blockExecuted by:
| 377426 | ||||||||||||
| 523 | } executed 12278 times by 50 tests: end of blockExecuted by:
| 12278 | ||||||||||||
| 524 | return d; executed 128139 times by 537 tests: return d;Executed by:
| 128139 | ||||||||||||
| 525 | } | - | ||||||||||||
| 526 | - | |||||||||||||
| 527 | void QHashData::free_helper(void (*node_delete)(Node *)) | - | ||||||||||||
| 528 | { | - | ||||||||||||
| 529 | if (node_delete) {
| 0-128522 | ||||||||||||
| 530 | Node *this_e = reinterpret_cast<Node *>(this); | - | ||||||||||||
| 531 | Node **bucket = reinterpret_cast<Node **>(this->buckets); | - | ||||||||||||
| 532 | - | |||||||||||||
| 533 | int n = numBuckets; | - | ||||||||||||
| 534 | while (n--) {
| 128522-8186904 | ||||||||||||
| 535 | Node *cur = *bucket++; | - | ||||||||||||
| 536 | while (cur != this_e) {
| 5805670-8186904 | ||||||||||||
| 537 | Node *next = cur->next; | - | ||||||||||||
| 538 | node_delete(cur); | - | ||||||||||||
| 539 | freeNode(cur); | - | ||||||||||||
| 540 | cur = next; | - | ||||||||||||
| 541 | } executed 5805670 times by 593 tests: end of blockExecuted by:
| 5805670 | ||||||||||||
| 542 | } executed 8186904 times by 659 tests: end of blockExecuted by:
| 8186904 | ||||||||||||
| 543 | } executed 128522 times by 660 tests: end of blockExecuted by:
| 128522 | ||||||||||||
| 544 | delete [] buckets; | - | ||||||||||||
| 545 | delete this; | - | ||||||||||||
| 546 | } executed 128522 times by 660 tests: end of blockExecuted by:
| 128522 | ||||||||||||
| 547 | - | |||||||||||||
| 548 | QHashData::Node *QHashData::nextNode(Node *node) | - | ||||||||||||
| 549 | { | - | ||||||||||||
| 550 | union { | - | ||||||||||||
| 551 | Node *next; | - | ||||||||||||
| 552 | Node *e; | - | ||||||||||||
| 553 | QHashData *d; | - | ||||||||||||
| 554 | }; | - | ||||||||||||
| 555 | next = node->next; | - | ||||||||||||
| 556 | Q_ASSERT_X(next, "QHash", "Iterating beyond end()"); | - | ||||||||||||
| 557 | if (next->next)
| 2658281-9315642 | ||||||||||||
| 558 | return next; executed 9315642 times by 358 tests: return next;Executed by:
| 9315642 | ||||||||||||
| 559 | - | |||||||||||||
| 560 | int start = (node->h % d->numBuckets) + 1; | - | ||||||||||||
| 561 | Node **bucket = d->buckets + start; | - | ||||||||||||
| 562 | int n = d->numBuckets - start; | - | ||||||||||||
| 563 | while (n--) {
| 234703-837338358 | ||||||||||||
| 564 | if (*bucket != e)
| 2423578-834914780 | ||||||||||||
| 565 | return *bucket; executed 2423578 times by 392 tests: return *bucket;Executed by:
| 2423578 | ||||||||||||
| 566 | ++bucket; | - | ||||||||||||
| 567 | } executed 834914780 times by 452 tests: end of blockExecuted by:
| 834914780 | ||||||||||||
| 568 | return e; executed 234703 times by 456 tests: return e;Executed by:
| 234703 | ||||||||||||
| 569 | } | - | ||||||||||||
| 570 | - | |||||||||||||
| 571 | QHashData::Node *QHashData::previousNode(Node *node) | - | ||||||||||||
| 572 | { | - | ||||||||||||
| 573 | union { | - | ||||||||||||
| 574 | Node *e; | - | ||||||||||||
| 575 | QHashData *d; | - | ||||||||||||
| 576 | }; | - | ||||||||||||
| 577 | - | |||||||||||||
| 578 | e = node; | - | ||||||||||||
| 579 | while (e->next)
| 388532-466230 | ||||||||||||
| 580 | e = e->next; executed 466230 times by 15 tests: e = e->next;Executed by:
| 466230 | ||||||||||||
| 581 | - | |||||||||||||
| 582 | int start; | - | ||||||||||||
| 583 | if (node == e)
| 39660-348872 | ||||||||||||
| 584 | start = d->numBuckets - 1; executed 39660 times by 23 tests: start = d->numBuckets - 1;Executed by:
| 39660 | ||||||||||||
| 585 | else | - | ||||||||||||
| 586 | start = node->h % d->numBuckets; executed 348872 times by 15 tests: start = node->h % d->numBuckets;Executed by:
| 348872 | ||||||||||||
| 587 | - | |||||||||||||
| 588 | Node *sentinel = node; | - | ||||||||||||
| 589 | Node **bucket = d->buckets + start; | - | ||||||||||||
| 590 | while (start >= 0) {
| 0-410367489 | ||||||||||||
| 591 | if (*bucket != sentinel) {
| 388532-409978957 | ||||||||||||
| 592 | Node *prev = *bucket; | - | ||||||||||||
| 593 | while (prev->next != sentinel)
| 137332-388532 | ||||||||||||
| 594 | prev = prev->next; executed 137332 times by 11 tests: prev = prev->next;Executed by:
| 137332 | ||||||||||||
| 595 | return prev; executed 388532 times by 23 tests: return prev;Executed by:
| 388532 | ||||||||||||
| 596 | } | - | ||||||||||||
| 597 | - | |||||||||||||
| 598 | sentinel = e; | - | ||||||||||||
| 599 | --bucket; | - | ||||||||||||
| 600 | --start; | - | ||||||||||||
| 601 | } executed 409978957 times by 23 tests: end of blockExecuted by:
| 409978957 | ||||||||||||
| 602 | Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()"); | - | ||||||||||||
| 603 | return e; never executed: return e; | 0 | ||||||||||||
| 604 | } | - | ||||||||||||
| 605 | - | |||||||||||||
| 606 | /* | - | ||||||||||||
| 607 | If hint is negative, -hint gives the approximate number of | - | ||||||||||||
| 608 | buckets that should be used for the hash table. If hint is | - | ||||||||||||
| 609 | nonnegative, (1 << hint) gives the approximate number | - | ||||||||||||
| 610 | of buckets that should be used. | - | ||||||||||||
| 611 | */ | - | ||||||||||||
| 612 | void QHashData::rehash(int hint) | - | ||||||||||||
| 613 | { | - | ||||||||||||
| 614 | if (hint < 0) {
| 14479-108724 | ||||||||||||
| 615 | hint = countBits(-hint); | - | ||||||||||||
| 616 | if (hint < MinNumBits)
| 515-13964 | ||||||||||||
| 617 | hint = MinNumBits; executed 13964 times by 104 tests: hint = MinNumBits;Executed by:
| 13964 | ||||||||||||
| 618 | userNumBits = hint; | - | ||||||||||||
| 619 | while (primeForNumBits(hint) < (size >> 1))
| 37-14479 | ||||||||||||
| 620 | ++hint; executed 37 times by 4 tests: ++hint;Executed by:
| 37 | ||||||||||||
| 621 | } else if (hint < MinNumBits) { executed 14479 times by 161 tests: end of blockExecuted by:
| 13369-95355 | ||||||||||||
| 622 | hint = MinNumBits; | - | ||||||||||||
| 623 | } executed 95355 times by 534 tests: end of blockExecuted by:
| 95355 | ||||||||||||
| 624 | - | |||||||||||||
| 625 | if (numBits != hint) {
| 4-123199 | ||||||||||||
| 626 | Node *e = reinterpret_cast<Node *>(this); | - | ||||||||||||
| 627 | Node **oldBuckets = buckets; | - | ||||||||||||
| 628 | int oldNumBuckets = numBuckets; | - | ||||||||||||
| 629 | - | |||||||||||||
| 630 | int nb = primeForNumBits(hint); | - | ||||||||||||
| 631 | buckets = new Node *[nb]; | - | ||||||||||||
| 632 | numBits = hint; | - | ||||||||||||
| 633 | numBuckets = nb; | - | ||||||||||||
| 634 | for (int i = 0; i < numBuckets; ++i)
| 123199-14129829 | ||||||||||||
| 635 | buckets[i] = e; executed 14129829 times by 539 tests: buckets[i] = e;Executed by:
| 14129829 | ||||||||||||
| 636 | - | |||||||||||||
| 637 | for (int i = 0; i < oldNumBuckets; ++i) {
| 123199-6327020 | ||||||||||||
| 638 | Node *firstNode = oldBuckets[i]; | - | ||||||||||||
| 639 | while (firstNode != e) {
| 704921-6327020 | ||||||||||||
| 640 | uint h = firstNode->h; | - | ||||||||||||
| 641 | Node *lastNode = firstNode; | - | ||||||||||||
| 642 | while (lastNode->next != e && lastNode->next->h == h)
| 199084-5576692 | ||||||||||||
| 643 | lastNode = lastNode->next; executed 5377608 times by 39 tests: lastNode = lastNode->next;Executed by:
| 5377608 | ||||||||||||
| 644 | - | |||||||||||||
| 645 | Node *afterLastNode = lastNode->next; | - | ||||||||||||
| 646 | Node **beforeFirstNode = &buckets[h % numBuckets]; | - | ||||||||||||
| 647 | while (*beforeFirstNode != e)
| 128973-704921 | ||||||||||||
| 648 | beforeFirstNode = &(*beforeFirstNode)->next; executed 128973 times by 134 tests: beforeFirstNode = &(*beforeFirstNode)->next;Executed by:
| 128973 | ||||||||||||
| 649 | lastNode->next = *beforeFirstNode; | - | ||||||||||||
| 650 | *beforeFirstNode = firstNode; | - | ||||||||||||
| 651 | firstNode = afterLastNode; | - | ||||||||||||
| 652 | } executed 704921 times by 148 tests: end of blockExecuted by:
| 704921 | ||||||||||||
| 653 | } executed 6327020 times by 148 tests: end of blockExecuted by:
| 6327020 | ||||||||||||
| 654 | delete [] oldBuckets; | - | ||||||||||||
| 655 | } executed 123199 times by 539 tests: end of blockExecuted by:
| 123199 | ||||||||||||
| 656 | } executed 123203 times by 539 tests: end of blockExecuted by:
| 123203 | ||||||||||||
| 657 | - | |||||||||||||
| 658 | #ifdef QT_QHASH_DEBUG | - | ||||||||||||
| 659 | - | |||||||||||||
| 660 | void QHashData::dump() | - | ||||||||||||
| 661 | { | - | ||||||||||||
| 662 | qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)", | - | ||||||||||||
| 663 | int(ref), size, nodeSize, userNumBits, numBits, | - | ||||||||||||
| 664 | numBuckets); | - | ||||||||||||
| 665 | qDebug(" %p (fakeNode = %p)", this, fakeNext); | - | ||||||||||||
| 666 | for (int i = 0; i < numBuckets; ++i) { | - | ||||||||||||
| 667 | Node *n = buckets[i]; | - | ||||||||||||
| 668 | if (n != reinterpret_cast<Node *>(this)) { | - | ||||||||||||
| 669 | QString line = QString::asprintf("%d:", i); | - | ||||||||||||
| 670 | while (n != reinterpret_cast<Node *>(this)) { | - | ||||||||||||
| 671 | line += QString::asprintf(" -> [%p]", n); | - | ||||||||||||
| 672 | if (!n) { | - | ||||||||||||
| 673 | line += " (CORRUPT)"; | - | ||||||||||||
| 674 | break; | - | ||||||||||||
| 675 | } | - | ||||||||||||
| 676 | n = n->next; | - | ||||||||||||
| 677 | } | - | ||||||||||||
| 678 | qDebug("%s", qPrintable(line)); | - | ||||||||||||
| 679 | } | - | ||||||||||||
| 680 | } | - | ||||||||||||
| 681 | } | - | ||||||||||||
| 682 | - | |||||||||||||
| 683 | void QHashData::checkSanity() | - | ||||||||||||
| 684 | { | - | ||||||||||||
| 685 | if (fakeNext) | - | ||||||||||||
| 686 | qFatal("Fake next isn't 0"); | - | ||||||||||||
| 687 | - | |||||||||||||
| 688 | for (int i = 0; i < numBuckets; ++i) { | - | ||||||||||||
| 689 | Node *n = buckets[i]; | - | ||||||||||||
| 690 | Node *p = n; | - | ||||||||||||
| 691 | if (!n) | - | ||||||||||||
| 692 | qFatal("%d: Bucket entry is 0", i); | - | ||||||||||||
| 693 | if (n != reinterpret_cast<Node *>(this)) { | - | ||||||||||||
| 694 | while (n != reinterpret_cast<Node *>(this)) { | - | ||||||||||||
| 695 | if (!n->next) | - | ||||||||||||
| 696 | qFatal("%d: Next of %p is 0, should be %p", i, n, this); | - | ||||||||||||
| 697 | n = n->next; | - | ||||||||||||
| 698 | } | - | ||||||||||||
| 699 | } | - | ||||||||||||
| 700 | } | - | ||||||||||||
| 701 | } | - | ||||||||||||
| 702 | #endif | - | ||||||||||||
| 703 | - | |||||||||||||
| 704 | /*! | - | ||||||||||||
| 705 | \fn uint qHash(const QPair<T1, T2> &key, uint seed = 0) | - | ||||||||||||
| 706 | \since 5.0 | - | ||||||||||||
| 707 | \relates QHash | - | ||||||||||||
| 708 | - | |||||||||||||
| 709 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 710 | - | |||||||||||||
| 711 | Types \c T1 and \c T2 must be supported by qHash(). | - | ||||||||||||
| 712 | */ | - | ||||||||||||
| 713 | - | |||||||||||||
| 714 | /*! \fn uint qHashRange(InputIterator first, InputIterator last, uint seed = 0) | - | ||||||||||||
| 715 | \relates QHash | - | ||||||||||||
| 716 | \since 5.5 | - | ||||||||||||
| 717 | - | |||||||||||||
| 718 | Returns the hash value for the range [\a{first},\a{last}), using \a seed | - | ||||||||||||
| 719 | to seed the calculation, by successively applying qHash() to each | - | ||||||||||||
| 720 | element and combining the hash values into a single one. | - | ||||||||||||
| 721 | - | |||||||||||||
| 722 | The return value of this function depends on the order of elements | - | ||||||||||||
| 723 | in the range. That means that | - | ||||||||||||
| 724 | - | |||||||||||||
| 725 | \code | - | ||||||||||||
| 726 | {0, 1, 2} | - | ||||||||||||
| 727 | \endcode | - | ||||||||||||
| 728 | - | |||||||||||||
| 729 | and | - | ||||||||||||
| 730 | \code | - | ||||||||||||
| 731 | {1, 2, 0} | - | ||||||||||||
| 732 | \endcode | - | ||||||||||||
| 733 | - | |||||||||||||
| 734 | hash to \b{different} values. If order does not matter, for example for hash | - | ||||||||||||
| 735 | tables, use qHashRangeCommutative() instead. If you are hashing raw | - | ||||||||||||
| 736 | memory, use qHashBits(). | - | ||||||||||||
| 737 | - | |||||||||||||
| 738 | Use this function only to implement qHash() for your own custom | - | ||||||||||||
| 739 | types. For example, here's how you could implement a qHash() overload for | - | ||||||||||||
| 740 | std::vector<int>: | - | ||||||||||||
| 741 | - | |||||||||||||
| 742 | \snippet code/src_corelib_tools_qhash.cpp qhashrange | - | ||||||||||||
| 743 | - | |||||||||||||
| 744 | It bears repeating that the implementation of qHashRange() - like | - | ||||||||||||
| 745 | the qHash() overloads offered by Qt - may change at any time. You | - | ||||||||||||
| 746 | \b{must not} rely on the fact that qHashRange() will give the same | - | ||||||||||||
| 747 | results (for the same inputs) across different Qt versions, even | - | ||||||||||||
| 748 | if qHash() for the element type would. | - | ||||||||||||
| 749 | - | |||||||||||||
| 750 | \sa qHashBits(), qHashRangeCommutative() | - | ||||||||||||
| 751 | */ | - | ||||||||||||
| 752 | - | |||||||||||||
| 753 | /*! \fn uint qHashRangeCommutative(InputIterator first, InputIterator last, uint seed = 0) | - | ||||||||||||
| 754 | \relates QHash | - | ||||||||||||
| 755 | \since 5.5 | - | ||||||||||||
| 756 | - | |||||||||||||
| 757 | Returns the hash value for the range [\a{first},\a{last}), using \a seed | - | ||||||||||||
| 758 | to seed the calculation, by successively applying qHash() to each | - | ||||||||||||
| 759 | element and combining the hash values into a single one. | - | ||||||||||||
| 760 | - | |||||||||||||
| 761 | The return value of this function does not depend on the order of | - | ||||||||||||
| 762 | elements in the range. That means that | - | ||||||||||||
| 763 | - | |||||||||||||
| 764 | \code | - | ||||||||||||
| 765 | {0, 1, 2} | - | ||||||||||||
| 766 | \endcode | - | ||||||||||||
| 767 | - | |||||||||||||
| 768 | and | - | ||||||||||||
| 769 | \code | - | ||||||||||||
| 770 | {1, 2, 0} | - | ||||||||||||
| 771 | \endcode | - | ||||||||||||
| 772 | - | |||||||||||||
| 773 | hash to the \b{same} values. If order matters, for example, for vectors | - | ||||||||||||
| 774 | and arrays, use qHashRange() instead. If you are hashing raw | - | ||||||||||||
| 775 | memory, use qHashBits(). | - | ||||||||||||
| 776 | - | |||||||||||||
| 777 | Use this function only to implement qHash() for your own custom | - | ||||||||||||
| 778 | types. For example, here's how you could implement a qHash() overload for | - | ||||||||||||
| 779 | std::unordered_set<int>: | - | ||||||||||||
| 780 | - | |||||||||||||
| 781 | \snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative | - | ||||||||||||
| 782 | - | |||||||||||||
| 783 | It bears repeating that the implementation of | - | ||||||||||||
| 784 | qHashRangeCommutative() - like the qHash() overloads offered by Qt | - | ||||||||||||
| 785 | - may change at any time. You \b{must not} rely on the fact that | - | ||||||||||||
| 786 | qHashRangeCommutative() will give the same results (for the same | - | ||||||||||||
| 787 | inputs) across different Qt versions, even if qHash() for the | - | ||||||||||||
| 788 | element type would. | - | ||||||||||||
| 789 | - | |||||||||||||
| 790 | \sa qHashBits(), qHashRange() | - | ||||||||||||
| 791 | */ | - | ||||||||||||
| 792 | - | |||||||||||||
| 793 | /*! \fn uint qHashBits(const void *p, size_t len, uint seed = 0) | - | ||||||||||||
| 794 | \relates QHash | - | ||||||||||||
| 795 | \since 5.4 | - | ||||||||||||
| 796 | - | |||||||||||||
| 797 | Returns the hash value for the memory block of size \a len pointed | - | ||||||||||||
| 798 | to by \a p, using \a seed to seed the calculation. | - | ||||||||||||
| 799 | - | |||||||||||||
| 800 | Use this function only to implement qHash() for your own custom | - | ||||||||||||
| 801 | types. For example, here's how you could implement a qHash() overload for | - | ||||||||||||
| 802 | std::vector<int>: | - | ||||||||||||
| 803 | - | |||||||||||||
| 804 | \snippet code/src_corelib_tools_qhash.cpp qhashbits | - | ||||||||||||
| 805 | - | |||||||||||||
| 806 | This takes advantage of the fact that std::vector lays out its data | - | ||||||||||||
| 807 | contiguously. If that is not the case, or the contained type has | - | ||||||||||||
| 808 | padding, you should use qHashRange() instead. | - | ||||||||||||
| 809 | - | |||||||||||||
| 810 | It bears repeating that the implementation of qHashBits() - like | - | ||||||||||||
| 811 | the qHash() overloads offered by Qt - may change at any time. You | - | ||||||||||||
| 812 | \b{must not} rely on the fact that qHashBits() will give the same | - | ||||||||||||
| 813 | results (for the same inputs) across different Qt versions. | - | ||||||||||||
| 814 | - | |||||||||||||
| 815 | \sa qHashRange(), qHashRangeCommutative() | - | ||||||||||||
| 816 | */ | - | ||||||||||||
| 817 | - | |||||||||||||
| 818 | /*! \fn uint qHash(char key, uint seed = 0) | - | ||||||||||||
| 819 | \relates QHash | - | ||||||||||||
| 820 | \since 5.0 | - | ||||||||||||
| 821 | - | |||||||||||||
| 822 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 823 | */ | - | ||||||||||||
| 824 | - | |||||||||||||
| 825 | /*! \fn uint qHash(uchar key, uint seed = 0) | - | ||||||||||||
| 826 | \relates QHash | - | ||||||||||||
| 827 | \since 5.0 | - | ||||||||||||
| 828 | - | |||||||||||||
| 829 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 830 | */ | - | ||||||||||||
| 831 | - | |||||||||||||
| 832 | /*! \fn uint qHash(signed char key, uint seed = 0) | - | ||||||||||||
| 833 | \relates QHash | - | ||||||||||||
| 834 | \since 5.0 | - | ||||||||||||
| 835 | - | |||||||||||||
| 836 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 837 | */ | - | ||||||||||||
| 838 | - | |||||||||||||
| 839 | /*! \fn uint qHash(ushort key, uint seed = 0) | - | ||||||||||||
| 840 | \relates QHash | - | ||||||||||||
| 841 | \since 5.0 | - | ||||||||||||
| 842 | - | |||||||||||||
| 843 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 844 | */ | - | ||||||||||||
| 845 | - | |||||||||||||
| 846 | /*! \fn uint qHash(short key, uint seed = 0) | - | ||||||||||||
| 847 | \relates QHash | - | ||||||||||||
| 848 | \since 5.0 | - | ||||||||||||
| 849 | - | |||||||||||||
| 850 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 851 | */ | - | ||||||||||||
| 852 | - | |||||||||||||
| 853 | /*! \fn uint qHash(uint key, uint seed = 0) | - | ||||||||||||
| 854 | \relates QHash | - | ||||||||||||
| 855 | \since 5.0 | - | ||||||||||||
| 856 | - | |||||||||||||
| 857 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 858 | */ | - | ||||||||||||
| 859 | - | |||||||||||||
| 860 | /*! \fn uint qHash(int key, uint seed = 0) | - | ||||||||||||
| 861 | \relates QHash | - | ||||||||||||
| 862 | \since 5.0 | - | ||||||||||||
| 863 | - | |||||||||||||
| 864 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 865 | */ | - | ||||||||||||
| 866 | - | |||||||||||||
| 867 | /*! \fn uint qHash(ulong key, uint seed = 0) | - | ||||||||||||
| 868 | \relates QHash | - | ||||||||||||
| 869 | \since 5.0 | - | ||||||||||||
| 870 | - | |||||||||||||
| 871 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 872 | */ | - | ||||||||||||
| 873 | - | |||||||||||||
| 874 | /*! \fn uint qHash(long key, uint seed = 0) | - | ||||||||||||
| 875 | \relates QHash | - | ||||||||||||
| 876 | \since 5.0 | - | ||||||||||||
| 877 | - | |||||||||||||
| 878 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 879 | */ | - | ||||||||||||
| 880 | - | |||||||||||||
| 881 | /*! \fn uint qHash(quint64 key, uint seed = 0) | - | ||||||||||||
| 882 | \relates QHash | - | ||||||||||||
| 883 | \since 5.0 | - | ||||||||||||
| 884 | - | |||||||||||||
| 885 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 886 | */ | - | ||||||||||||
| 887 | - | |||||||||||||
| 888 | /*! \fn uint qHash(qint64 key, uint seed = 0) | - | ||||||||||||
| 889 | \relates QHash | - | ||||||||||||
| 890 | \since 5.0 | - | ||||||||||||
| 891 | - | |||||||||||||
| 892 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 893 | */ | - | ||||||||||||
| 894 | - | |||||||||||||
| 895 | /*! \relates QHash | - | ||||||||||||
| 896 | \since 5.3 | - | ||||||||||||
| 897 | - | |||||||||||||
| 898 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 899 | */ | - | ||||||||||||
| 900 | uint qHash(float key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 901 | { | - | ||||||||||||
| 902 | return key != 0.0f ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ; executed 2 times by 1 test: return key != 0.0f ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;Executed by:
| 0-2 | ||||||||||||
| 903 | } | - | ||||||||||||
| 904 | - | |||||||||||||
| 905 | /*! \relates QHash | - | ||||||||||||
| 906 | \since 5.3 | - | ||||||||||||
| 907 | - | |||||||||||||
| 908 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 909 | */ | - | ||||||||||||
| 910 | uint qHash(double key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 911 | { | - | ||||||||||||
| 912 | return key != 0.0 ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ; executed 19293 times by 41 tests: return key != 0.0 ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;Executed by:
| 1967-19293 | ||||||||||||
| 913 | } | - | ||||||||||||
| 914 | - | |||||||||||||
| 915 | #ifndef Q_OS_DARWIN | - | ||||||||||||
| 916 | /*! \relates QHash | - | ||||||||||||
| 917 | \since 5.3 | - | ||||||||||||
| 918 | - | |||||||||||||
| 919 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 920 | */ | - | ||||||||||||
| 921 | uint qHash(long double key, uint seed) Q_DECL_NOTHROW | - | ||||||||||||
| 922 | { | - | ||||||||||||
| 923 | return key != 0.0L ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ; executed 2 times by 1 test: return key != 0.0L ? hash(reinterpret_cast<const uchar *>(&key), sizeof(key), seed) : seed ;Executed by:
| 0-2 | ||||||||||||
| 924 | } | - | ||||||||||||
| 925 | #endif | - | ||||||||||||
| 926 | - | |||||||||||||
| 927 | /*! \fn uint qHash(const QChar key, uint seed = 0) | - | ||||||||||||
| 928 | \relates QHash | - | ||||||||||||
| 929 | \since 5.0 | - | ||||||||||||
| 930 | - | |||||||||||||
| 931 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 932 | */ | - | ||||||||||||
| 933 | - | |||||||||||||
| 934 | /*! \fn uint qHash(const QByteArray &key, uint seed = 0) | - | ||||||||||||
| 935 | \relates QHash | - | ||||||||||||
| 936 | \since 5.0 | - | ||||||||||||
| 937 | - | |||||||||||||
| 938 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 939 | */ | - | ||||||||||||
| 940 | - | |||||||||||||
| 941 | /*! \fn uint qHash(const QBitArray &key, uint seed = 0) | - | ||||||||||||
| 942 | \relates QHash | - | ||||||||||||
| 943 | \since 5.0 | - | ||||||||||||
| 944 | - | |||||||||||||
| 945 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 946 | */ | - | ||||||||||||
| 947 | - | |||||||||||||
| 948 | /*! \fn uint qHash(const QString &key, uint seed = 0) | - | ||||||||||||
| 949 | \relates QHash | - | ||||||||||||
| 950 | \since 5.0 | - | ||||||||||||
| 951 | - | |||||||||||||
| 952 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 953 | */ | - | ||||||||||||
| 954 | - | |||||||||||||
| 955 | /*! \fn uint qHash(const QStringRef &key, uint seed = 0) | - | ||||||||||||
| 956 | \relates QHash | - | ||||||||||||
| 957 | \since 5.0 | - | ||||||||||||
| 958 | - | |||||||||||||
| 959 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 960 | */ | - | ||||||||||||
| 961 | - | |||||||||||||
| 962 | /*! \fn uint qHash(QLatin1String key, uint seed = 0) | - | ||||||||||||
| 963 | \relates QHash | - | ||||||||||||
| 964 | \since 5.0 | - | ||||||||||||
| 965 | - | |||||||||||||
| 966 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 967 | */ | - | ||||||||||||
| 968 | - | |||||||||||||
| 969 | /*! \fn uint qHash(const T *key, uint seed = 0) | - | ||||||||||||
| 970 | \relates QHash | - | ||||||||||||
| 971 | \since 5.0 | - | ||||||||||||
| 972 | - | |||||||||||||
| 973 | Returns the hash value for the \a key, using \a seed to seed the calculation. | - | ||||||||||||
| 974 | */ | - | ||||||||||||
| 975 | - | |||||||||||||
| 976 | /*! | - | ||||||||||||
| 977 | \class QHash | - | ||||||||||||
| 978 | \inmodule QtCore | - | ||||||||||||
| 979 | \brief The QHash class is a template class that provides a hash-table-based dictionary. | - | ||||||||||||
| 980 | - | |||||||||||||
| 981 | \ingroup tools | - | ||||||||||||
| 982 | \ingroup shared | - | ||||||||||||
| 983 | - | |||||||||||||
| 984 | \reentrant | - | ||||||||||||
| 985 | - | |||||||||||||
| 986 | QHash\<Key, T\> is one of Qt's generic \l{container classes}. It | - | ||||||||||||
| 987 | stores (key, value) pairs and provides very fast lookup of the | - | ||||||||||||
| 988 | value associated with a key. | - | ||||||||||||
| 989 | - | |||||||||||||
| 990 | QHash provides very similar functionality to QMap. The | - | ||||||||||||
| 991 | differences are: | - | ||||||||||||
| 992 | - | |||||||||||||
| 993 | \list | - | ||||||||||||
| 994 | \li QHash provides faster lookups than QMap. (See \l{Algorithmic | - | ||||||||||||
| 995 | Complexity} for details.) | - | ||||||||||||
| 996 | \li When iterating over a QMap, the items are always sorted by | - | ||||||||||||
| 997 | key. With QHash, the items are arbitrarily ordered. | - | ||||||||||||
| 998 | \li The key type of a QMap must provide operator<(). The key | - | ||||||||||||
| 999 | type of a QHash must provide operator==() and a global | - | ||||||||||||
| 1000 | hash function called qHash() (see \l{qHash}). | - | ||||||||||||
| 1001 | \endlist | - | ||||||||||||
| 1002 | - | |||||||||||||
| 1003 | Here's an example QHash with QString keys and \c int values: | - | ||||||||||||
| 1004 | \snippet code/src_corelib_tools_qhash.cpp 0 | - | ||||||||||||
| 1005 | - | |||||||||||||
| 1006 | To insert a (key, value) pair into the hash, you can use operator[](): | - | ||||||||||||
| 1007 | - | |||||||||||||
| 1008 | \snippet code/src_corelib_tools_qhash.cpp 1 | - | ||||||||||||
| 1009 | - | |||||||||||||
| 1010 | This inserts the following three (key, value) pairs into the | - | ||||||||||||
| 1011 | QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to | - | ||||||||||||
| 1012 | insert items into the hash is to use insert(): | - | ||||||||||||
| 1013 | - | |||||||||||||
| 1014 | \snippet code/src_corelib_tools_qhash.cpp 2 | - | ||||||||||||
| 1015 | - | |||||||||||||
| 1016 | To look up a value, use operator[]() or value(): | - | ||||||||||||
| 1017 | - | |||||||||||||
| 1018 | \snippet code/src_corelib_tools_qhash.cpp 3 | - | ||||||||||||
| 1019 | - | |||||||||||||
| 1020 | If there is no item with the specified key in the hash, these | - | ||||||||||||
| 1021 | functions return a \l{default-constructed value}. | - | ||||||||||||
| 1022 | - | |||||||||||||
| 1023 | If you want to check whether the hash contains a particular key, | - | ||||||||||||
| 1024 | use contains(): | - | ||||||||||||
| 1025 | - | |||||||||||||
| 1026 | \snippet code/src_corelib_tools_qhash.cpp 4 | - | ||||||||||||
| 1027 | - | |||||||||||||
| 1028 | There is also a value() overload that uses its second argument as | - | ||||||||||||
| 1029 | a default value if there is no item with the specified key: | - | ||||||||||||
| 1030 | - | |||||||||||||
| 1031 | \snippet code/src_corelib_tools_qhash.cpp 5 | - | ||||||||||||
| 1032 | - | |||||||||||||
| 1033 | In general, we recommend that you use contains() and value() | - | ||||||||||||
| 1034 | rather than operator[]() for looking up a key in a hash. The | - | ||||||||||||
| 1035 | reason is that operator[]() silently inserts an item into the | - | ||||||||||||
| 1036 | hash if no item exists with the same key (unless the hash is | - | ||||||||||||
| 1037 | const). For example, the following code snippet will create 1000 | - | ||||||||||||
| 1038 | items in memory: | - | ||||||||||||
| 1039 | - | |||||||||||||
| 1040 | \snippet code/src_corelib_tools_qhash.cpp 6 | - | ||||||||||||
| 1041 | - | |||||||||||||
| 1042 | To avoid this problem, replace \c hash[i] with \c hash.value(i) | - | ||||||||||||
| 1043 | in the code above. | - | ||||||||||||
| 1044 | - | |||||||||||||
| 1045 | Internally, QHash uses a hash table to perform lookups. Unlike Qt | - | ||||||||||||
| 1046 | 3's \c QDict class, which needed to be initialized with a prime | - | ||||||||||||
| 1047 | number, QHash's hash table automatically grows and shrinks to | - | ||||||||||||
| 1048 | provide fast lookups without wasting too much memory. You can | - | ||||||||||||
| 1049 | still control the size of the hash table by calling reserve() if | - | ||||||||||||
| 1050 | you already know approximately how many items the QHash will | - | ||||||||||||
| 1051 | contain, but this isn't necessary to obtain good performance. You | - | ||||||||||||
| 1052 | can also call capacity() to retrieve the hash table's size. | - | ||||||||||||
| 1053 | - | |||||||||||||
| 1054 | If you want to navigate through all the (key, value) pairs stored | - | ||||||||||||
| 1055 | in a QHash, you can use an iterator. QHash provides both | - | ||||||||||||
| 1056 | \l{Java-style iterators} (QHashIterator and QMutableHashIterator) | - | ||||||||||||
| 1057 | and \l{STL-style iterators} (QHash::const_iterator and | - | ||||||||||||
| 1058 | QHash::iterator). Here's how to iterate over a QHash<QString, | - | ||||||||||||
| 1059 | int> using a Java-style iterator: | - | ||||||||||||
| 1060 | - | |||||||||||||
| 1061 | \snippet code/src_corelib_tools_qhash.cpp 7 | - | ||||||||||||
| 1062 | - | |||||||||||||
| 1063 | Here's the same code, but using an STL-style iterator: | - | ||||||||||||
| 1064 | - | |||||||||||||
| 1065 | \snippet code/src_corelib_tools_qhash.cpp 8 | - | ||||||||||||
| 1066 | - | |||||||||||||
| 1067 | QHash is unordered, so an iterator's sequence cannot be assumed | - | ||||||||||||
| 1068 | to be predictable. If ordering by key is required, use a QMap. | - | ||||||||||||
| 1069 | - | |||||||||||||
| 1070 | Normally, a QHash allows only one value per key. If you call | - | ||||||||||||
| 1071 | insert() with a key that already exists in the QHash, the | - | ||||||||||||
| 1072 | previous value is erased. For example: | - | ||||||||||||
| 1073 | - | |||||||||||||
| 1074 | \snippet code/src_corelib_tools_qhash.cpp 9 | - | ||||||||||||
| 1075 | - | |||||||||||||
| 1076 | However, you can store multiple values per key by using | - | ||||||||||||
| 1077 | insertMulti() instead of insert() (or using the convenience | - | ||||||||||||
| 1078 | subclass QMultiHash). If you want to retrieve all | - | ||||||||||||
| 1079 | the values for a single key, you can use values(const Key &key), | - | ||||||||||||
| 1080 | which returns a QList<T>: | - | ||||||||||||
| 1081 | - | |||||||||||||
| 1082 | \snippet code/src_corelib_tools_qhash.cpp 10 | - | ||||||||||||
| 1083 | - | |||||||||||||
| 1084 | The items that share the same key are available from most | - | ||||||||||||
| 1085 | recently to least recently inserted. A more efficient approach is | - | ||||||||||||
| 1086 | to call find() to get the iterator for the first item with a key | - | ||||||||||||
| 1087 | and iterate from there: | - | ||||||||||||
| 1088 | - | |||||||||||||
| 1089 | \snippet code/src_corelib_tools_qhash.cpp 11 | - | ||||||||||||
| 1090 | - | |||||||||||||
| 1091 | If you only need to extract the values from a hash (not the keys), | - | ||||||||||||
| 1092 | you can also use \l{foreach}: | - | ||||||||||||
| 1093 | - | |||||||||||||
| 1094 | \snippet code/src_corelib_tools_qhash.cpp 12 | - | ||||||||||||
| 1095 | - | |||||||||||||
| 1096 | Items can be removed from the hash in several ways. One way is to | - | ||||||||||||
| 1097 | call remove(); this will remove any item with the given key. | - | ||||||||||||
| 1098 | Another way is to use QMutableHashIterator::remove(). In addition, | - | ||||||||||||
| 1099 | you can clear the entire hash using clear(). | - | ||||||||||||
| 1100 | - | |||||||||||||
| 1101 | QHash's key and value data types must be \l{assignable data | - | ||||||||||||
| 1102 | types}. You cannot, for example, store a QWidget as a value; | - | ||||||||||||
| 1103 | instead, store a QWidget *. | - | ||||||||||||
| 1104 | - | |||||||||||||
| 1105 | \target qHash | - | ||||||||||||
| 1106 | \section2 The qHash() hashing function | - | ||||||||||||
| 1107 | - | |||||||||||||
| 1108 | A QHash's key type has additional requirements other than being an | - | ||||||||||||
| 1109 | assignable data type: it must provide operator==(), and there must also be | - | ||||||||||||
| 1110 | a qHash() function in the type's namespace that returns a hash value for an | - | ||||||||||||
| 1111 | argument of the key's type. | - | ||||||||||||
| 1112 | - | |||||||||||||
| 1113 | The qHash() function computes a numeric value based on a key. It | - | ||||||||||||
| 1114 | can use any algorithm imaginable, as long as it always returns | - | ||||||||||||
| 1115 | the same value if given the same argument. In other words, if | - | ||||||||||||
| 1116 | \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well. | - | ||||||||||||
| 1117 | However, to obtain good performance, the qHash() function should | - | ||||||||||||
| 1118 | attempt to return different hash values for different keys to the | - | ||||||||||||
| 1119 | largest extent possible. | - | ||||||||||||
| 1120 | - | |||||||||||||
| 1121 | For a key type \c{K}, the qHash function must have one of these signatures: | - | ||||||||||||
| 1122 | - | |||||||||||||
| 1123 | \code | - | ||||||||||||
| 1124 | uint qHash(K key); | - | ||||||||||||
| 1125 | uint qHash(const K &key); | - | ||||||||||||
| 1126 | - | |||||||||||||
| 1127 | uint qHash(K key, uint seed); | - | ||||||||||||
| 1128 | uint qHash(const K &key, uint seed); | - | ||||||||||||
| 1129 | \endcode | - | ||||||||||||
| 1130 | - | |||||||||||||
| 1131 | The two-arguments overloads take an unsigned integer that should be used to | - | ||||||||||||
| 1132 | seed the calculation of the hash function. This seed is provided by QHash | - | ||||||||||||
| 1133 | in order to prevent a family of \l{algorithmic complexity attacks}. If both | - | ||||||||||||
| 1134 | a one-argument and a two-arguments overload are defined for a key type, | - | ||||||||||||
| 1135 | the latter is used by QHash (note that you can simply define a | - | ||||||||||||
| 1136 | two-arguments version, and use a default value for the seed parameter). | - | ||||||||||||
| 1137 | - | |||||||||||||
| 1138 | Here's a partial list of the C++ and Qt types that can serve as keys in a | - | ||||||||||||
| 1139 | QHash: any integer type (char, unsigned long, etc.), any pointer type, | - | ||||||||||||
| 1140 | QChar, QString, and QByteArray. For all of these, the \c <QHash> header | - | ||||||||||||
| 1141 | defines a qHash() function that computes an adequate hash value. Many other | - | ||||||||||||
| 1142 | Qt classes also declare a qHash overload for their type; please refer to | - | ||||||||||||
| 1143 | the documentation of each class. | - | ||||||||||||
| 1144 | - | |||||||||||||
| 1145 | If you want to use other types as the key, make sure that you provide | - | ||||||||||||
| 1146 | operator==() and a qHash() implementation. | - | ||||||||||||
| 1147 | - | |||||||||||||
| 1148 | Example: | - | ||||||||||||
| 1149 | \snippet code/src_corelib_tools_qhash.cpp 13 | - | ||||||||||||
| 1150 | - | |||||||||||||
| 1151 | In the example above, we've relied on Qt's global qHash(const | - | ||||||||||||
| 1152 | QString &, uint) to give us a hash value for the employee's name, and | - | ||||||||||||
| 1153 | XOR'ed this with the day they were born to help produce unique | - | ||||||||||||
| 1154 | hashes for people with the same name. | - | ||||||||||||
| 1155 | - | |||||||||||||
| 1156 | Note that the implementation of the qHash() overloads offered by Qt | - | ||||||||||||
| 1157 | may change at any time. You \b{must not} rely on the fact that qHash() | - | ||||||||||||
| 1158 | will give the same results (for the same inputs) across different Qt | - | ||||||||||||
| 1159 | versions. | - | ||||||||||||
| 1160 | - | |||||||||||||
| 1161 | \section2 Algorithmic complexity attacks | - | ||||||||||||
| 1162 | - | |||||||||||||
| 1163 | All hash tables are vulnerable to a particular class of denial of service | - | ||||||||||||
| 1164 | attacks, in which the attacker carefully pre-computes a set of different | - | ||||||||||||
| 1165 | keys that are going to be hashed in the same bucket of a hash table (or | - | ||||||||||||
| 1166 | even have the very same hash value). The attack aims at getting the | - | ||||||||||||
| 1167 | worst-case algorithmic behavior (O(n) instead of amortized O(1), see | - | ||||||||||||
| 1168 | \l{Algorithmic Complexity} for the details) when the data is fed into the | - | ||||||||||||
| 1169 | table. | - | ||||||||||||
| 1170 | - | |||||||||||||
| 1171 | In order to avoid this worst-case behavior, the calculation of the hash | - | ||||||||||||
| 1172 | value done by qHash() can be salted by a random seed, that nullifies the | - | ||||||||||||
| 1173 | attack's extent. This seed is automatically generated by QHash once per | - | ||||||||||||
| 1174 | process, and then passed by QHash as the second argument of the | - | ||||||||||||
| 1175 | two-arguments overload of the qHash() function. | - | ||||||||||||
| 1176 | - | |||||||||||||
| 1177 | This randomization of QHash is enabled by default. Even though programs | - | ||||||||||||
| 1178 | should never depend on a particular QHash ordering, there may be situations | - | ||||||||||||
| 1179 | where you temporarily need deterministic behavior, for example for debugging or | - | ||||||||||||
| 1180 | regression testing. To disable the randomization, define the environment | - | ||||||||||||
| 1181 | variable \c QT_HASH_SEED. The contents of that variable, interpreted as a | - | ||||||||||||
| 1182 | decimal value, will be used as the seed for qHash(). Alternatively, you can | - | ||||||||||||
| 1183 | call the qSetGlobalQHashSeed() function. | - | ||||||||||||
| 1184 | - | |||||||||||||
| 1185 | \sa QHashIterator, QMutableHashIterator, QMap, QSet | - | ||||||||||||
| 1186 | */ | - | ||||||||||||
| 1187 | - | |||||||||||||
| 1188 | /*! \fn QHash::QHash() | - | ||||||||||||
| 1189 | - | |||||||||||||
| 1190 | Constructs an empty hash. | - | ||||||||||||
| 1191 | - | |||||||||||||
| 1192 | \sa clear() | - | ||||||||||||
| 1193 | */ | - | ||||||||||||
| 1194 | - | |||||||||||||
| 1195 | /*! | - | ||||||||||||
| 1196 | \fn QHash::QHash(QHash &&other) | - | ||||||||||||
| 1197 | - | |||||||||||||
| 1198 | Move-constructs a QHash instance, making it point at the same | - | ||||||||||||
| 1199 | object that \a other was pointing to. | - | ||||||||||||
| 1200 | - | |||||||||||||
| 1201 | \since 5.2 | - | ||||||||||||
| 1202 | */ | - | ||||||||||||
| 1203 | - | |||||||||||||
| 1204 | /*! \fn QHash::QHash(std::initializer_list<std::pair<Key,T> > list) | - | ||||||||||||
| 1205 | \since 5.1 | - | ||||||||||||
| 1206 | - | |||||||||||||
| 1207 | Constructs a hash with a copy of each of the elements in the | - | ||||||||||||
| 1208 | initializer list \a list. | - | ||||||||||||
| 1209 | - | |||||||||||||
| 1210 | This function is only available if the program is being | - | ||||||||||||
| 1211 | compiled in C++11 mode. | - | ||||||||||||
| 1212 | */ | - | ||||||||||||
| 1213 | - | |||||||||||||
| 1214 | /*! \fn QHash::QHash(const QHash &other) | - | ||||||||||||
| 1215 | - | |||||||||||||
| 1216 | Constructs a copy of \a other. | - | ||||||||||||
| 1217 | - | |||||||||||||
| 1218 | This operation occurs in \l{constant time}, because QHash is | - | ||||||||||||
| 1219 | \l{implicitly shared}. This makes returning a QHash from a | - | ||||||||||||
| 1220 | function very fast. If a shared instance is modified, it will be | - | ||||||||||||
| 1221 | copied (copy-on-write), and this takes \l{linear time}. | - | ||||||||||||
| 1222 | - | |||||||||||||
| 1223 | \sa operator=() | - | ||||||||||||
| 1224 | */ | - | ||||||||||||
| 1225 | - | |||||||||||||
| 1226 | /*! \fn QHash::~QHash() | - | ||||||||||||
| 1227 | - | |||||||||||||
| 1228 | Destroys the hash. References to the values in the hash and all | - | ||||||||||||
| 1229 | iterators of this hash become invalid. | - | ||||||||||||
| 1230 | */ | - | ||||||||||||
| 1231 | - | |||||||||||||
| 1232 | /*! \fn QHash &QHash::operator=(const QHash &other) | - | ||||||||||||
| 1233 | - | |||||||||||||
| 1234 | Assigns \a other to this hash and returns a reference to this hash. | - | ||||||||||||
| 1235 | */ | - | ||||||||||||
| 1236 | - | |||||||||||||
| 1237 | /*! | - | ||||||||||||
| 1238 | \fn QHash &QHash::operator=(QHash &&other) | - | ||||||||||||
| 1239 | - | |||||||||||||
| 1240 | Move-assigns \a other to this QHash instance. | - | ||||||||||||
| 1241 | - | |||||||||||||
| 1242 | \since 5.2 | - | ||||||||||||
| 1243 | */ | - | ||||||||||||
| 1244 | - | |||||||||||||
| 1245 | /*! \fn void QHash::swap(QHash &other) | - | ||||||||||||
| 1246 | \since 4.8 | - | ||||||||||||
| 1247 | - | |||||||||||||
| 1248 | Swaps hash \a other with this hash. This operation is very | - | ||||||||||||
| 1249 | fast and never fails. | - | ||||||||||||
| 1250 | */ | - | ||||||||||||
| 1251 | - | |||||||||||||
| 1252 | /*! \fn void QMultiHash::swap(QMultiHash &other) | - | ||||||||||||
| 1253 | \since 4.8 | - | ||||||||||||
| 1254 | - | |||||||||||||
| 1255 | Swaps hash \a other with this hash. This operation is very | - | ||||||||||||
| 1256 | fast and never fails. | - | ||||||||||||
| 1257 | */ | - | ||||||||||||
| 1258 | - | |||||||||||||
| 1259 | /*! \fn bool QHash::operator==(const QHash &other) const | - | ||||||||||||
| 1260 | - | |||||||||||||
| 1261 | Returns \c true if \a other is equal to this hash; otherwise returns | - | ||||||||||||
| 1262 | false. | - | ||||||||||||
| 1263 | - | |||||||||||||
| 1264 | Two hashes are considered equal if they contain the same (key, | - | ||||||||||||
| 1265 | value) pairs. | - | ||||||||||||
| 1266 | - | |||||||||||||
| 1267 | This function requires the value type to implement \c operator==(). | - | ||||||||||||
| 1268 | - | |||||||||||||
| 1269 | \sa operator!=() | - | ||||||||||||
| 1270 | */ | - | ||||||||||||
| 1271 | - | |||||||||||||
| 1272 | /*! \fn bool QHash::operator!=(const QHash &other) const | - | ||||||||||||
| 1273 | - | |||||||||||||
| 1274 | Returns \c true if \a other is not equal to this hash; otherwise | - | ||||||||||||
| 1275 | returns \c false. | - | ||||||||||||
| 1276 | - | |||||||||||||
| 1277 | Two hashes are considered equal if they contain the same (key, | - | ||||||||||||
| 1278 | value) pairs. | - | ||||||||||||
| 1279 | - | |||||||||||||
| 1280 | This function requires the value type to implement \c operator==(). | - | ||||||||||||
| 1281 | - | |||||||||||||
| 1282 | \sa operator==() | - | ||||||||||||
| 1283 | */ | - | ||||||||||||
| 1284 | - | |||||||||||||
| 1285 | /*! \fn int QHash::size() const | - | ||||||||||||
| 1286 | - | |||||||||||||
| 1287 | Returns the number of items in the hash. | - | ||||||||||||
| 1288 | - | |||||||||||||
| 1289 | \sa isEmpty(), count() | - | ||||||||||||
| 1290 | */ | - | ||||||||||||
| 1291 | - | |||||||||||||
| 1292 | /*! \fn bool QHash::isEmpty() const | - | ||||||||||||
| 1293 | - | |||||||||||||
| 1294 | Returns \c true if the hash contains no items; otherwise returns | - | ||||||||||||
| 1295 | false. | - | ||||||||||||
| 1296 | - | |||||||||||||
| 1297 | \sa size() | - | ||||||||||||
| 1298 | */ | - | ||||||||||||
| 1299 | - | |||||||||||||
| 1300 | /*! \fn int QHash::capacity() const | - | ||||||||||||
| 1301 | - | |||||||||||||
| 1302 | Returns the number of buckets in the QHash's internal hash table. | - | ||||||||||||
| 1303 | - | |||||||||||||
| 1304 | The sole purpose of this function is to provide a means of fine | - | ||||||||||||
| 1305 | tuning QHash's memory usage. In general, you will rarely ever | - | ||||||||||||
| 1306 | need to call this function. If you want to know how many items are | - | ||||||||||||
| 1307 | in the hash, call size(). | - | ||||||||||||
| 1308 | - | |||||||||||||
| 1309 | \sa reserve(), squeeze() | - | ||||||||||||
| 1310 | */ | - | ||||||||||||
| 1311 | - | |||||||||||||
| 1312 | /*! \fn void QHash::reserve(int size) | - | ||||||||||||
| 1313 | - | |||||||||||||
| 1314 | Ensures that the QHash's internal hash table consists of at least | - | ||||||||||||
| 1315 | \a size buckets. | - | ||||||||||||
| 1316 | - | |||||||||||||
| 1317 | This function is useful for code that needs to build a huge hash | - | ||||||||||||
| 1318 | and wants to avoid repeated reallocation. For example: | - | ||||||||||||
| 1319 | - | |||||||||||||
| 1320 | \snippet code/src_corelib_tools_qhash.cpp 14 | - | ||||||||||||
| 1321 | - | |||||||||||||
| 1322 | Ideally, \a size should be slightly more than the maximum number | - | ||||||||||||
| 1323 | of items expected in the hash. \a size doesn't have to be prime, | - | ||||||||||||
| 1324 | because QHash will use a prime number internally anyway. If \a size | - | ||||||||||||
| 1325 | is an underestimate, the worst that will happen is that the QHash | - | ||||||||||||
| 1326 | will be a bit slower. | - | ||||||||||||
| 1327 | - | |||||||||||||
| 1328 | In general, you will rarely ever need to call this function. | - | ||||||||||||
| 1329 | QHash's internal hash table automatically shrinks or grows to | - | ||||||||||||
| 1330 | provide good performance without wasting too much memory. | - | ||||||||||||
| 1331 | - | |||||||||||||
| 1332 | \sa squeeze(), capacity() | - | ||||||||||||
| 1333 | */ | - | ||||||||||||
| 1334 | - | |||||||||||||
| 1335 | /*! \fn void QHash::squeeze() | - | ||||||||||||
| 1336 | - | |||||||||||||
| 1337 | Reduces the size of the QHash's internal hash table to save | - | ||||||||||||
| 1338 | memory. | - | ||||||||||||
| 1339 | - | |||||||||||||
| 1340 | The sole purpose of this function is to provide a means of fine | - | ||||||||||||
| 1341 | tuning QHash's memory usage. In general, you will rarely ever | - | ||||||||||||
| 1342 | need to call this function. | - | ||||||||||||
| 1343 | - | |||||||||||||
| 1344 | \sa reserve(), capacity() | - | ||||||||||||
| 1345 | */ | - | ||||||||||||
| 1346 | - | |||||||||||||
| 1347 | /*! \fn void QHash::detach() | - | ||||||||||||
| 1348 | - | |||||||||||||
| 1349 | \internal | - | ||||||||||||
| 1350 | - | |||||||||||||
| 1351 | Detaches this hash from any other hashes with which it may share | - | ||||||||||||
| 1352 | data. | - | ||||||||||||
| 1353 | - | |||||||||||||
| 1354 | \sa isDetached() | - | ||||||||||||
| 1355 | */ | - | ||||||||||||
| 1356 | - | |||||||||||||
| 1357 | /*! \fn bool QHash::isDetached() const | - | ||||||||||||
| 1358 | - | |||||||||||||
| 1359 | \internal | - | ||||||||||||
| 1360 | - | |||||||||||||
| 1361 | Returns \c true if the hash's internal data isn't shared with any | - | ||||||||||||
| 1362 | other hash object; otherwise returns \c false. | - | ||||||||||||
| 1363 | - | |||||||||||||
| 1364 | \sa detach() | - | ||||||||||||
| 1365 | */ | - | ||||||||||||
| 1366 | - | |||||||||||||
| 1367 | /*! \fn void QHash::setSharable(bool sharable) | - | ||||||||||||
| 1368 | - | |||||||||||||
| 1369 | \internal | - | ||||||||||||
| 1370 | */ | - | ||||||||||||
| 1371 | - | |||||||||||||
| 1372 | /*! \fn bool QHash::isSharedWith(const QHash &other) const | - | ||||||||||||
| 1373 | - | |||||||||||||
| 1374 | \internal | - | ||||||||||||
| 1375 | */ | - | ||||||||||||
| 1376 | - | |||||||||||||
| 1377 | /*! \fn void QHash::clear() | - | ||||||||||||
| 1378 | - | |||||||||||||
| 1379 | Removes all items from the hash. | - | ||||||||||||
| 1380 | - | |||||||||||||
| 1381 | \sa remove() | - | ||||||||||||
| 1382 | */ | - | ||||||||||||
| 1383 | - | |||||||||||||
| 1384 | /*! \fn int QHash::remove(const Key &key) | - | ||||||||||||
| 1385 | - | |||||||||||||
| 1386 | Removes all the items that have the \a key from the hash. | - | ||||||||||||
| 1387 | Returns the number of items removed which is usually 1 but will | - | ||||||||||||
| 1388 | be 0 if the key isn't in the hash, or greater than 1 if | - | ||||||||||||
| 1389 | insertMulti() has been used with the \a key. | - | ||||||||||||
| 1390 | - | |||||||||||||
| 1391 | \sa clear(), take(), QMultiHash::remove() | - | ||||||||||||
| 1392 | */ | - | ||||||||||||
| 1393 | - | |||||||||||||
| 1394 | /*! \fn T QHash::take(const Key &key) | - | ||||||||||||
| 1395 | - | |||||||||||||
| 1396 | Removes the item with the \a key from the hash and returns | - | ||||||||||||
| 1397 | the value associated with it. | - | ||||||||||||
| 1398 | - | |||||||||||||
| 1399 | If the item does not exist in the hash, the function simply | - | ||||||||||||
| 1400 | returns a \l{default-constructed value}. If there are multiple | - | ||||||||||||
| 1401 | items for \a key in the hash, only the most recently inserted one | - | ||||||||||||
| 1402 | is removed. | - | ||||||||||||
| 1403 | - | |||||||||||||
| 1404 | If you don't use the return value, remove() is more efficient. | - | ||||||||||||
| 1405 | - | |||||||||||||
| 1406 | \sa remove() | - | ||||||||||||
| 1407 | */ | - | ||||||||||||
| 1408 | - | |||||||||||||
| 1409 | /*! \fn bool QHash::contains(const Key &key) const | - | ||||||||||||
| 1410 | - | |||||||||||||
| 1411 | Returns \c true if the hash contains an item with the \a key; | - | ||||||||||||
| 1412 | otherwise returns \c false. | - | ||||||||||||
| 1413 | - | |||||||||||||
| 1414 | \sa count(), QMultiHash::contains() | - | ||||||||||||
| 1415 | */ | - | ||||||||||||
| 1416 | - | |||||||||||||
| 1417 | /*! \fn const T QHash::value(const Key &key) const | - | ||||||||||||
| 1418 | - | |||||||||||||
| 1419 | Returns the value associated with the \a key. | - | ||||||||||||
| 1420 | - | |||||||||||||
| 1421 | If the hash contains no item with the \a key, the function | - | ||||||||||||
| 1422 | returns a \l{default-constructed value}. If there are multiple | - | ||||||||||||
| 1423 | items for the \a key in the hash, the value of the most recently | - | ||||||||||||
| 1424 | inserted one is returned. | - | ||||||||||||
| 1425 | - | |||||||||||||
| 1426 | \sa key(), values(), contains(), operator[]() | - | ||||||||||||
| 1427 | */ | - | ||||||||||||
| 1428 | - | |||||||||||||
| 1429 | /*! \fn const T QHash::value(const Key &key, const T &defaultValue) const | - | ||||||||||||
| 1430 | \overload | - | ||||||||||||
| 1431 | - | |||||||||||||
| 1432 | If the hash contains no item with the given \a key, the function returns | - | ||||||||||||
| 1433 | \a defaultValue. | - | ||||||||||||
| 1434 | */ | - | ||||||||||||
| 1435 | - | |||||||||||||
| 1436 | /*! \fn T &QHash::operator[](const Key &key) | - | ||||||||||||
| 1437 | - | |||||||||||||
| 1438 | Returns the value associated with the \a key as a modifiable | - | ||||||||||||
| 1439 | reference. | - | ||||||||||||
| 1440 | - | |||||||||||||
| 1441 | If the hash contains no item with the \a key, the function inserts | - | ||||||||||||
| 1442 | a \l{default-constructed value} into the hash with the \a key, and | - | ||||||||||||
| 1443 | returns a reference to it. If the hash contains multiple items | - | ||||||||||||
| 1444 | with the \a key, this function returns a reference to the most | - | ||||||||||||
| 1445 | recently inserted value. | - | ||||||||||||
| 1446 | - | |||||||||||||
| 1447 | \sa insert(), value() | - | ||||||||||||
| 1448 | */ | - | ||||||||||||
| 1449 | - | |||||||||||||
| 1450 | /*! \fn const T QHash::operator[](const Key &key) const | - | ||||||||||||
| 1451 | - | |||||||||||||
| 1452 | \overload | - | ||||||||||||
| 1453 | - | |||||||||||||
| 1454 | Same as value(). | - | ||||||||||||
| 1455 | */ | - | ||||||||||||
| 1456 | - | |||||||||||||
| 1457 | /*! \fn QList<Key> QHash::uniqueKeys() const | - | ||||||||||||
| 1458 | \since 4.2 | - | ||||||||||||
| 1459 | - | |||||||||||||
| 1460 | Returns a list containing all the keys in the map. Keys that occur multiple | - | ||||||||||||
| 1461 | times in the map (because items were inserted with insertMulti(), or | - | ||||||||||||
| 1462 | unite() was used) occur only once in the returned list. | - | ||||||||||||
| 1463 | - | |||||||||||||
| 1464 | \sa keys(), values() | - | ||||||||||||
| 1465 | */ | - | ||||||||||||
| 1466 | - | |||||||||||||
| 1467 | /*! \fn QList<Key> QHash::keys() const | - | ||||||||||||
| 1468 | - | |||||||||||||
| 1469 | Returns a list containing all the keys in the hash, in an | - | ||||||||||||
| 1470 | arbitrary order. Keys that occur multiple times in the hash | - | ||||||||||||
| 1471 | (because items were inserted with insertMulti(), or unite() was | - | ||||||||||||
| 1472 | used) also occur multiple times in the list. | - | ||||||||||||
| 1473 | - | |||||||||||||
| 1474 | To obtain a list of unique keys, where each key from the map only | - | ||||||||||||
| 1475 | occurs once, use uniqueKeys(). | - | ||||||||||||
| 1476 | - | |||||||||||||
| 1477 | The order is guaranteed to be the same as that used by values(). | - | ||||||||||||
| 1478 | - | |||||||||||||
| 1479 | \sa uniqueKeys(), values(), key() | - | ||||||||||||
| 1480 | */ | - | ||||||||||||
| 1481 | - | |||||||||||||
| 1482 | /*! \fn QList<Key> QHash::keys(const T &value) const | - | ||||||||||||
| 1483 | - | |||||||||||||
| 1484 | \overload | - | ||||||||||||
| 1485 | - | |||||||||||||
| 1486 | Returns a list containing all the keys associated with value \a | - | ||||||||||||
| 1487 | value, in an arbitrary order. | - | ||||||||||||
| 1488 | - | |||||||||||||
| 1489 | This function can be slow (\l{linear time}), because QHash's | - | ||||||||||||
| 1490 | internal data structure is optimized for fast lookup by key, not | - | ||||||||||||
| 1491 | by value. | - | ||||||||||||
| 1492 | */ | - | ||||||||||||
| 1493 | - | |||||||||||||
| 1494 | /*! \fn QList<T> QHash::values() const | - | ||||||||||||
| 1495 | - | |||||||||||||
| 1496 | Returns a list containing all the values in the hash, in an | - | ||||||||||||
| 1497 | arbitrary order. If a key is associated with multiple values, all of | - | ||||||||||||
| 1498 | its values will be in the list, and not just the most recently | - | ||||||||||||
| 1499 | inserted one. | - | ||||||||||||
| 1500 | - | |||||||||||||
| 1501 | The order is guaranteed to be the same as that used by keys(). | - | ||||||||||||
| 1502 | - | |||||||||||||
| 1503 | \sa keys(), value() | - | ||||||||||||
| 1504 | */ | - | ||||||||||||
| 1505 | - | |||||||||||||
| 1506 | /*! \fn QList<T> QHash::values(const Key &key) const | - | ||||||||||||
| 1507 | - | |||||||||||||
| 1508 | \overload | - | ||||||||||||
| 1509 | - | |||||||||||||
| 1510 | Returns a list of all the values associated with the \a key, | - | ||||||||||||
| 1511 | from the most recently inserted to the least recently inserted. | - | ||||||||||||
| 1512 | - | |||||||||||||
| 1513 | \sa count(), insertMulti() | - | ||||||||||||
| 1514 | */ | - | ||||||||||||
| 1515 | - | |||||||||||||
| 1516 | /*! \fn Key QHash::key(const T &value) const | - | ||||||||||||
| 1517 | - | |||||||||||||
| 1518 | Returns the first key mapped to \a value. | - | ||||||||||||
| 1519 | - | |||||||||||||
| 1520 | If the hash contains no item with the \a value, the function | - | ||||||||||||
| 1521 | returns a \l{default-constructed value}{default-constructed key}. | - | ||||||||||||
| 1522 | - | |||||||||||||
| 1523 | This function can be slow (\l{linear time}), because QHash's | - | ||||||||||||
| 1524 | internal data structure is optimized for fast lookup by key, not | - | ||||||||||||
| 1525 | by value. | - | ||||||||||||
| 1526 | - | |||||||||||||
| 1527 | \sa value(), keys() | - | ||||||||||||
| 1528 | */ | - | ||||||||||||
| 1529 | - | |||||||||||||
| 1530 | /*! | - | ||||||||||||
| 1531 | \fn Key QHash::key(const T &value, const Key &defaultKey) const | - | ||||||||||||
| 1532 | \since 4.3 | - | ||||||||||||
| 1533 | \overload | - | ||||||||||||
| 1534 | - | |||||||||||||
| 1535 | Returns the first key mapped to \a value, or \a defaultKey if the | - | ||||||||||||
| 1536 | hash contains no item mapped to \a value. | - | ||||||||||||
| 1537 | - | |||||||||||||
| 1538 | This function can be slow (\l{linear time}), because QHash's | - | ||||||||||||
| 1539 | internal data structure is optimized for fast lookup by key, not | - | ||||||||||||
| 1540 | by value. | - | ||||||||||||
| 1541 | */ | - | ||||||||||||
| 1542 | - | |||||||||||||
| 1543 | /*! \fn int QHash::count(const Key &key) const | - | ||||||||||||
| 1544 | - | |||||||||||||
| 1545 | Returns the number of items associated with the \a key. | - | ||||||||||||
| 1546 | - | |||||||||||||
| 1547 | \sa contains(), insertMulti() | - | ||||||||||||
| 1548 | */ | - | ||||||||||||
| 1549 | - | |||||||||||||
| 1550 | /*! \fn int QHash::count() const | - | ||||||||||||
| 1551 | - | |||||||||||||
| 1552 | \overload | - | ||||||||||||
| 1553 | - | |||||||||||||
| 1554 | Same as size(). | - | ||||||||||||
| 1555 | */ | - | ||||||||||||
| 1556 | - | |||||||||||||
| 1557 | /*! \fn QHash::iterator QHash::begin() | - | ||||||||||||
| 1558 | - | |||||||||||||
| 1559 | Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in | - | ||||||||||||
| 1560 | the hash. | - | ||||||||||||
| 1561 | - | |||||||||||||
| 1562 | \sa constBegin(), end() | - | ||||||||||||
| 1563 | */ | - | ||||||||||||
| 1564 | - | |||||||||||||
| 1565 | /*! \fn QHash::const_iterator QHash::begin() const | - | ||||||||||||
| 1566 | - | |||||||||||||
| 1567 | \overload | - | ||||||||||||
| 1568 | */ | - | ||||||||||||
| 1569 | - | |||||||||||||
| 1570 | /*! \fn QHash::const_iterator QHash::cbegin() const | - | ||||||||||||
| 1571 | \since 5.0 | - | ||||||||||||
| 1572 | - | |||||||||||||
| 1573 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item | - | ||||||||||||
| 1574 | in the hash. | - | ||||||||||||
| 1575 | - | |||||||||||||
| 1576 | \sa begin(), cend() | - | ||||||||||||
| 1577 | */ | - | ||||||||||||
| 1578 | - | |||||||||||||
| 1579 | /*! \fn QHash::const_iterator QHash::constBegin() const | - | ||||||||||||
| 1580 | - | |||||||||||||
| 1581 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item | - | ||||||||||||
| 1582 | in the hash. | - | ||||||||||||
| 1583 | - | |||||||||||||
| 1584 | \sa begin(), constEnd() | - | ||||||||||||
| 1585 | */ | - | ||||||||||||
| 1586 | - | |||||||||||||
| 1587 | /*! \fn QHash::key_iterator QHash::keyBegin() const | - | ||||||||||||
| 1588 | \since 5.6 | - | ||||||||||||
| 1589 | - | |||||||||||||
| 1590 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key | - | ||||||||||||
| 1591 | in the hash. | - | ||||||||||||
| 1592 | - | |||||||||||||
| 1593 | \sa keyEnd() | - | ||||||||||||
| 1594 | */ | - | ||||||||||||
| 1595 | - | |||||||||||||
| 1596 | /*! \fn QHash::iterator QHash::end() | - | ||||||||||||
| 1597 | - | |||||||||||||
| 1598 | Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item | - | ||||||||||||
| 1599 | after the last item in the hash. | - | ||||||||||||
| 1600 | - | |||||||||||||
| 1601 | \sa begin(), constEnd() | - | ||||||||||||
| 1602 | */ | - | ||||||||||||
| 1603 | - | |||||||||||||
| 1604 | /*! \fn QHash::const_iterator QHash::end() const | - | ||||||||||||
| 1605 | - | |||||||||||||
| 1606 | \overload | - | ||||||||||||
| 1607 | */ | - | ||||||||||||
| 1608 | - | |||||||||||||
| 1609 | /*! \fn QHash::const_iterator QHash::constEnd() const | - | ||||||||||||
| 1610 | - | |||||||||||||
| 1611 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary | - | ||||||||||||
| 1612 | item after the last item in the hash. | - | ||||||||||||
| 1613 | - | |||||||||||||
| 1614 | \sa constBegin(), end() | - | ||||||||||||
| 1615 | */ | - | ||||||||||||
| 1616 | - | |||||||||||||
| 1617 | /*! \fn QHash::const_iterator QHash::cend() const | - | ||||||||||||
| 1618 | \since 5.0 | - | ||||||||||||
| 1619 | - | |||||||||||||
| 1620 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary | - | ||||||||||||
| 1621 | item after the last item in the hash. | - | ||||||||||||
| 1622 | - | |||||||||||||
| 1623 | \sa cbegin(), end() | - | ||||||||||||
| 1624 | */ | - | ||||||||||||
| 1625 | - | |||||||||||||
| 1626 | /*! \fn QHash::key_iterator QHash::keyEnd() const | - | ||||||||||||
| 1627 | \since 5.6 | - | ||||||||||||
| 1628 | - | |||||||||||||
| 1629 | Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary | - | ||||||||||||
| 1630 | item after the last key in the hash. | - | ||||||||||||
| 1631 | - | |||||||||||||
| 1632 | \sa keyBegin() | - | ||||||||||||
| 1633 | */ | - | ||||||||||||
| 1634 | - | |||||||||||||
| 1635 | /*! \fn QHash::iterator QHash::erase(iterator pos) | - | ||||||||||||
| 1636 | - | |||||||||||||
| 1637 | Removes the (key, value) pair associated with the iterator \a pos | - | ||||||||||||
| 1638 | from the hash, and returns an iterator to the next item in the | - | ||||||||||||
| 1639 | hash. | - | ||||||||||||
| 1640 | - | |||||||||||||
| 1641 | Unlike remove() and take(), this function never causes QHash to | - | ||||||||||||
| 1642 | rehash its internal data structure. This means that it can safely | - | ||||||||||||
| 1643 | be called while iterating, and won't affect the order of items in | - | ||||||||||||
| 1644 | the hash. For example: | - | ||||||||||||
| 1645 | - | |||||||||||||
| 1646 | \snippet code/src_corelib_tools_qhash.cpp 15 | - | ||||||||||||
| 1647 | - | |||||||||||||
| 1648 | \sa remove(), take(), find() | - | ||||||||||||
| 1649 | */ | - | ||||||||||||
| 1650 | - | |||||||||||||
| 1651 | /*! \fn QHash::iterator QHash::find(const Key &key) | - | ||||||||||||
| 1652 | - | |||||||||||||
| 1653 | Returns an iterator pointing to the item with the \a key in the | - | ||||||||||||
| 1654 | hash. | - | ||||||||||||
| 1655 | - | |||||||||||||
| 1656 | If the hash contains no item with the \a key, the function | - | ||||||||||||
| 1657 | returns end(). | - | ||||||||||||
| 1658 | - | |||||||||||||
| 1659 | If the hash contains multiple items with the \a key, this | - | ||||||||||||
| 1660 | function returns an iterator that points to the most recently | - | ||||||||||||
| 1661 | inserted value. The other values are accessible by incrementing | - | ||||||||||||
| 1662 | the iterator. For example, here's some code that iterates over all | - | ||||||||||||
| 1663 | the items with the same key: | - | ||||||||||||
| 1664 | - | |||||||||||||
| 1665 | \snippet code/src_corelib_tools_qhash.cpp 16 | - | ||||||||||||
| 1666 | - | |||||||||||||
| 1667 | \sa value(), values(), QMultiHash::find() | - | ||||||||||||
| 1668 | */ | - | ||||||||||||
| 1669 | - | |||||||||||||
| 1670 | /*! \fn QHash::const_iterator QHash::find(const Key &key) const | - | ||||||||||||
| 1671 | - | |||||||||||||
| 1672 | \overload | - | ||||||||||||
| 1673 | */ | - | ||||||||||||
| 1674 | - | |||||||||||||
| 1675 | /*! \fn QHash::const_iterator QHash::constFind(const Key &key) const | - | ||||||||||||
| 1676 | \since 4.1 | - | ||||||||||||
| 1677 | - | |||||||||||||
| 1678 | Returns an iterator pointing to the item with the \a key in the | - | ||||||||||||
| 1679 | hash. | - | ||||||||||||
| 1680 | - | |||||||||||||
| 1681 | If the hash contains no item with the \a key, the function | - | ||||||||||||
| 1682 | returns constEnd(). | - | ||||||||||||
| 1683 | - | |||||||||||||
| 1684 | \sa find(), QMultiHash::constFind() | - | ||||||||||||
| 1685 | */ | - | ||||||||||||
| 1686 | - | |||||||||||||
| 1687 | /*! \fn QHash::iterator QHash::insert(const Key &key, const T &value) | - | ||||||||||||
| 1688 | - | |||||||||||||
| 1689 | Inserts a new item with the \a key and a value of \a value. | - | ||||||||||||
| 1690 | - | |||||||||||||
| 1691 | If there is already an item with the \a key, that item's value | - | ||||||||||||
| 1692 | is replaced with \a value. | - | ||||||||||||
| 1693 | - | |||||||||||||
| 1694 | If there are multiple items with the \a key, the most | - | ||||||||||||
| 1695 | recently inserted item's value is replaced with \a value. | - | ||||||||||||
| 1696 | - | |||||||||||||
| 1697 | \sa insertMulti() | - | ||||||||||||
| 1698 | */ | - | ||||||||||||
| 1699 | - | |||||||||||||
| 1700 | /*! \fn QHash::iterator QHash::insertMulti(const Key &key, const T &value) | - | ||||||||||||
| 1701 | - | |||||||||||||
| 1702 | Inserts a new item with the \a key and a value of \a value. | - | ||||||||||||
| 1703 | - | |||||||||||||
| 1704 | If there is already an item with the same key in the hash, this | - | ||||||||||||
| 1705 | function will simply create a new one. (This behavior is | - | ||||||||||||
| 1706 | different from insert(), which overwrites the value of an | - | ||||||||||||
| 1707 | existing item.) | - | ||||||||||||
| 1708 | - | |||||||||||||
| 1709 | \sa insert(), values() | - | ||||||||||||
| 1710 | */ | - | ||||||||||||
| 1711 | - | |||||||||||||
| 1712 | /*! \fn QHash &QHash::unite(const QHash &other) | - | ||||||||||||
| 1713 | - | |||||||||||||
| 1714 | Inserts all the items in the \a other hash into this hash. If a | - | ||||||||||||
| 1715 | key is common to both hashes, the resulting hash will contain the | - | ||||||||||||
| 1716 | key multiple times. | - | ||||||||||||
| 1717 | - | |||||||||||||
| 1718 | \sa insertMulti() | - | ||||||||||||
| 1719 | */ | - | ||||||||||||
| 1720 | - | |||||||||||||
| 1721 | /*! \fn bool QHash::empty() const | - | ||||||||||||
| 1722 | - | |||||||||||||
| 1723 | This function is provided for STL compatibility. It is equivalent | - | ||||||||||||
| 1724 | to isEmpty(), returning true if the hash is empty; otherwise | - | ||||||||||||
| 1725 | returns \c false. | - | ||||||||||||
| 1726 | */ | - | ||||||||||||
| 1727 | - | |||||||||||||
| 1728 | /*! \typedef QHash::ConstIterator | - | ||||||||||||
| 1729 | - | |||||||||||||
| 1730 | Qt-style synonym for QHash::const_iterator. | - | ||||||||||||
| 1731 | */ | - | ||||||||||||
| 1732 | - | |||||||||||||
| 1733 | /*! \typedef QHash::Iterator | - | ||||||||||||
| 1734 | - | |||||||||||||
| 1735 | Qt-style synonym for QHash::iterator. | - | ||||||||||||
| 1736 | */ | - | ||||||||||||
| 1737 | - | |||||||||||||
| 1738 | /*! \typedef QHash::difference_type | - | ||||||||||||
| 1739 | - | |||||||||||||
| 1740 | Typedef for ptrdiff_t. Provided for STL compatibility. | - | ||||||||||||
| 1741 | */ | - | ||||||||||||
| 1742 | - | |||||||||||||
| 1743 | /*! \typedef QHash::key_type | - | ||||||||||||
| 1744 | - | |||||||||||||
| 1745 | Typedef for Key. Provided for STL compatibility. | - | ||||||||||||
| 1746 | */ | - | ||||||||||||
| 1747 | - | |||||||||||||
| 1748 | /*! \typedef QHash::mapped_type | - | ||||||||||||
| 1749 | - | |||||||||||||
| 1750 | Typedef for T. Provided for STL compatibility. | - | ||||||||||||
| 1751 | */ | - | ||||||||||||
| 1752 | - | |||||||||||||
| 1753 | /*! \typedef QHash::size_type | - | ||||||||||||
| 1754 | - | |||||||||||||
| 1755 | Typedef for int. Provided for STL compatibility. | - | ||||||||||||
| 1756 | */ | - | ||||||||||||
| 1757 | - | |||||||||||||
| 1758 | /*! \typedef QHash::iterator::difference_type | - | ||||||||||||
| 1759 | \internal | - | ||||||||||||
| 1760 | */ | - | ||||||||||||
| 1761 | - | |||||||||||||
| 1762 | /*! \typedef QHash::iterator::iterator_category | - | ||||||||||||
| 1763 | \internal | - | ||||||||||||
| 1764 | */ | - | ||||||||||||
| 1765 | - | |||||||||||||
| 1766 | /*! \typedef QHash::iterator::pointer | - | ||||||||||||
| 1767 | \internal | - | ||||||||||||
| 1768 | */ | - | ||||||||||||
| 1769 | - | |||||||||||||
| 1770 | /*! \typedef QHash::iterator::reference | - | ||||||||||||
| 1771 | \internal | - | ||||||||||||
| 1772 | */ | - | ||||||||||||
| 1773 | - | |||||||||||||
| 1774 | /*! \typedef QHash::iterator::value_type | - | ||||||||||||
| 1775 | \internal | - | ||||||||||||
| 1776 | */ | - | ||||||||||||
| 1777 | - | |||||||||||||
| 1778 | /*! \typedef QHash::const_iterator::difference_type | - | ||||||||||||
| 1779 | \internal | - | ||||||||||||
| 1780 | */ | - | ||||||||||||
| 1781 | - | |||||||||||||
| 1782 | /*! \typedef QHash::const_iterator::iterator_category | - | ||||||||||||
| 1783 | \internal | - | ||||||||||||
| 1784 | */ | - | ||||||||||||
| 1785 | - | |||||||||||||
| 1786 | /*! \typedef QHash::const_iterator::pointer | - | ||||||||||||
| 1787 | \internal | - | ||||||||||||
| 1788 | */ | - | ||||||||||||
| 1789 | - | |||||||||||||
| 1790 | /*! \typedef QHash::const_iterator::reference | - | ||||||||||||
| 1791 | \internal | - | ||||||||||||
| 1792 | */ | - | ||||||||||||
| 1793 | - | |||||||||||||
| 1794 | /*! \typedef QHash::const_iterator::value_type | - | ||||||||||||
| 1795 | \internal | - | ||||||||||||
| 1796 | */ | - | ||||||||||||
| 1797 | - | |||||||||||||
| 1798 | /*! \typedef QHash::key_iterator::difference_type | - | ||||||||||||
| 1799 | \internal | - | ||||||||||||
| 1800 | */ | - | ||||||||||||
| 1801 | - | |||||||||||||
| 1802 | /*! \typedef QHash::key_iterator::iterator_category | - | ||||||||||||
| 1803 | \internal | - | ||||||||||||
| 1804 | */ | - | ||||||||||||
| 1805 | - | |||||||||||||
| 1806 | /*! \typedef QHash::key_iterator::pointer | - | ||||||||||||
| 1807 | \internal | - | ||||||||||||
| 1808 | */ | - | ||||||||||||
| 1809 | - | |||||||||||||
| 1810 | /*! \typedef QHash::key_iterator::reference | - | ||||||||||||
| 1811 | \internal | - | ||||||||||||
| 1812 | */ | - | ||||||||||||
| 1813 | - | |||||||||||||
| 1814 | /*! \typedef QHash::key_iterator::value_type | - | ||||||||||||
| 1815 | \internal | - | ||||||||||||
| 1816 | */ | - | ||||||||||||
| 1817 | - | |||||||||||||
| 1818 | /*! \class QHash::iterator | - | ||||||||||||
| 1819 | \inmodule QtCore | - | ||||||||||||
| 1820 | \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash. | - | ||||||||||||
| 1821 | - | |||||||||||||
| 1822 | QHash features both \l{STL-style iterators} and \l{Java-style | - | ||||||||||||
| 1823 | iterators}. The STL-style iterators are more low-level and more | - | ||||||||||||
| 1824 | cumbersome to use; on the other hand, they are slightly faster | - | ||||||||||||
| 1825 | and, for developers who already know STL, have the advantage of | - | ||||||||||||
| 1826 | familiarity. | - | ||||||||||||
| 1827 | - | |||||||||||||
| 1828 | QHash\<Key, T\>::iterator allows you to iterate over a QHash (or | - | ||||||||||||
| 1829 | QMultiHash) and to modify the value (but not the key) associated | - | ||||||||||||
| 1830 | with a particular key. If you want to iterate over a const QHash, | - | ||||||||||||
| 1831 | you should use QHash::const_iterator. It is generally good | - | ||||||||||||
| 1832 | practice to use QHash::const_iterator on a non-const QHash as | - | ||||||||||||
| 1833 | well, unless you need to change the QHash through the iterator. | - | ||||||||||||
| 1834 | Const iterators are slightly faster, and can improve code | - | ||||||||||||
| 1835 | readability. | - | ||||||||||||
| 1836 | - | |||||||||||||
| 1837 | The default QHash::iterator constructor creates an uninitialized | - | ||||||||||||
| 1838 | iterator. You must initialize it using a QHash function like | - | ||||||||||||
| 1839 | QHash::begin(), QHash::end(), or QHash::find() before you can | - | ||||||||||||
| 1840 | start iterating. Here's a typical loop that prints all the (key, | - | ||||||||||||
| 1841 | value) pairs stored in a hash: | - | ||||||||||||
| 1842 | - | |||||||||||||
| 1843 | \snippet code/src_corelib_tools_qhash.cpp 17 | - | ||||||||||||
| 1844 | - | |||||||||||||
| 1845 | Unlike QMap, which orders its items by key, QHash stores its | - | ||||||||||||
| 1846 | items in an arbitrary order. The only guarantee is that items that | - | ||||||||||||
| 1847 | share the same key (because they were inserted using | - | ||||||||||||
| 1848 | QHash::insertMulti()) will appear consecutively, from the most | - | ||||||||||||
| 1849 | recently to the least recently inserted value. | - | ||||||||||||
| 1850 | - | |||||||||||||
| 1851 | Let's see a few examples of things we can do with a | - | ||||||||||||
| 1852 | QHash::iterator that we cannot do with a QHash::const_iterator. | - | ||||||||||||
| 1853 | Here's an example that increments every value stored in the QHash | - | ||||||||||||
| 1854 | by 2: | - | ||||||||||||
| 1855 | - | |||||||||||||
| 1856 | \snippet code/src_corelib_tools_qhash.cpp 18 | - | ||||||||||||
| 1857 | - | |||||||||||||
| 1858 | Here's an example that removes all the items whose key is a | - | ||||||||||||
| 1859 | string that starts with an underscore character: | - | ||||||||||||
| 1860 | - | |||||||||||||
| 1861 | \snippet code/src_corelib_tools_qhash.cpp 19 | - | ||||||||||||
| 1862 | - | |||||||||||||
| 1863 | The call to QHash::erase() removes the item pointed to by the | - | ||||||||||||
| 1864 | iterator from the hash, and returns an iterator to the next item. | - | ||||||||||||
| 1865 | Here's another way of removing an item while iterating: | - | ||||||||||||
| 1866 | - | |||||||||||||
| 1867 | \snippet code/src_corelib_tools_qhash.cpp 20 | - | ||||||||||||
| 1868 | - | |||||||||||||
| 1869 | It might be tempting to write code like this: | - | ||||||||||||
| 1870 | - | |||||||||||||
| 1871 | \snippet code/src_corelib_tools_qhash.cpp 21 | - | ||||||||||||
| 1872 | - | |||||||||||||
| 1873 | However, this will potentially crash in \c{++i}, because \c i is | - | ||||||||||||
| 1874 | a dangling iterator after the call to erase(). | - | ||||||||||||
| 1875 | - | |||||||||||||
| 1876 | Multiple iterators can be used on the same hash. However, be | - | ||||||||||||
| 1877 | aware that any modification performed directly on the QHash has | - | ||||||||||||
| 1878 | the potential of dramatically changing the order in which the | - | ||||||||||||
| 1879 | items are stored in the hash, as they might cause QHash to rehash | - | ||||||||||||
| 1880 | its internal data structure. There is one notable exception: | - | ||||||||||||
| 1881 | QHash::erase(). This function can safely be called while | - | ||||||||||||
| 1882 | iterating, and won't affect the order of items in the hash. If you | - | ||||||||||||
| 1883 | need to keep iterators over a long period of time, we recommend | - | ||||||||||||
| 1884 | that you use QMap rather than QHash. | - | ||||||||||||
| 1885 | - | |||||||||||||
| 1886 | \warning Iterators on implicitly shared containers do not work | - | ||||||||||||
| 1887 | exactly like STL-iterators. You should avoid copying a container | - | ||||||||||||
| 1888 | while iterators are active on that container. For more information, | - | ||||||||||||
| 1889 | read \l{Implicit sharing iterator problem}. | - | ||||||||||||
| 1890 | - | |||||||||||||
| 1891 | \sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator | - | ||||||||||||
| 1892 | */ | - | ||||||||||||
| 1893 | - | |||||||||||||
| 1894 | /*! \fn QHash::iterator::iterator() | - | ||||||||||||
| 1895 | - | |||||||||||||
| 1896 | Constructs an uninitialized iterator. | - | ||||||||||||
| 1897 | - | |||||||||||||
| 1898 | Functions like key(), value(), and operator++() must not be | - | ||||||||||||
| 1899 | called on an uninitialized iterator. Use operator=() to assign a | - | ||||||||||||
| 1900 | value to it before using it. | - | ||||||||||||
| 1901 | - | |||||||||||||
| 1902 | \sa QHash::begin(), QHash::end() | - | ||||||||||||
| 1903 | */ | - | ||||||||||||
| 1904 | - | |||||||||||||
| 1905 | /*! \fn QHash::iterator::iterator(void *node) | - | ||||||||||||
| 1906 | - | |||||||||||||
| 1907 | \internal | - | ||||||||||||
| 1908 | */ | - | ||||||||||||
| 1909 | - | |||||||||||||
| 1910 | /*! \fn const Key &QHash::iterator::key() const | - | ||||||||||||
| 1911 | - | |||||||||||||
| 1912 | Returns the current item's key as a const reference. | - | ||||||||||||
| 1913 | - | |||||||||||||
| 1914 | There is no direct way of changing an item's key through an | - | ||||||||||||
| 1915 | iterator, although it can be done by calling QHash::erase() | - | ||||||||||||
| 1916 | followed by QHash::insert() or QHash::insertMulti(). | - | ||||||||||||
| 1917 | - | |||||||||||||
| 1918 | \sa value() | - | ||||||||||||
| 1919 | */ | - | ||||||||||||
| 1920 | - | |||||||||||||
| 1921 | /*! \fn T &QHash::iterator::value() const | - | ||||||||||||
| 1922 | - | |||||||||||||
| 1923 | Returns a modifiable reference to the current item's value. | - | ||||||||||||
| 1924 | - | |||||||||||||
| 1925 | You can change the value of an item by using value() on | - | ||||||||||||
| 1926 | the left side of an assignment, for example: | - | ||||||||||||
| 1927 | - | |||||||||||||
| 1928 | \snippet code/src_corelib_tools_qhash.cpp 22 | - | ||||||||||||
| 1929 | - | |||||||||||||
| 1930 | \sa key(), operator*() | - | ||||||||||||
| 1931 | */ | - | ||||||||||||
| 1932 | - | |||||||||||||
| 1933 | /*! \fn T &QHash::iterator::operator*() const | - | ||||||||||||
| 1934 | - | |||||||||||||
| 1935 | Returns a modifiable reference to the current item's value. | - | ||||||||||||
| 1936 | - | |||||||||||||
| 1937 | Same as value(). | - | ||||||||||||
| 1938 | - | |||||||||||||
| 1939 | \sa key() | - | ||||||||||||
| 1940 | */ | - | ||||||||||||
| 1941 | - | |||||||||||||
| 1942 | /*! \fn T *QHash::iterator::operator->() const | - | ||||||||||||
| 1943 | - | |||||||||||||
| 1944 | Returns a pointer to the current item's value. | - | ||||||||||||
| 1945 | - | |||||||||||||
| 1946 | \sa value() | - | ||||||||||||
| 1947 | */ | - | ||||||||||||
| 1948 | - | |||||||||||||
| 1949 | /*! | - | ||||||||||||
| 1950 | \fn bool QHash::iterator::operator==(const iterator &other) const | - | ||||||||||||
| 1951 | \fn bool QHash::iterator::operator==(const const_iterator &other) const | - | ||||||||||||
| 1952 | - | |||||||||||||
| 1953 | Returns \c true if \a other points to the same item as this | - | ||||||||||||
| 1954 | iterator; otherwise returns \c false. | - | ||||||||||||
| 1955 | - | |||||||||||||
| 1956 | \sa operator!=() | - | ||||||||||||
| 1957 | */ | - | ||||||||||||
| 1958 | - | |||||||||||||
| 1959 | /*! | - | ||||||||||||
| 1960 | \fn bool QHash::iterator::operator!=(const iterator &other) const | - | ||||||||||||
| 1961 | \fn bool QHash::iterator::operator!=(const const_iterator &other) const | - | ||||||||||||
| 1962 | - | |||||||||||||
| 1963 | Returns \c true if \a other points to a different item than this | - | ||||||||||||
| 1964 | iterator; otherwise returns \c false. | - | ||||||||||||
| 1965 | - | |||||||||||||
| 1966 | \sa operator==() | - | ||||||||||||
| 1967 | */ | - | ||||||||||||
| 1968 | - | |||||||||||||
| 1969 | /*! | - | ||||||||||||
| 1970 | \fn QHash::iterator &QHash::iterator::operator++() | - | ||||||||||||
| 1971 | - | |||||||||||||
| 1972 | The prefix ++ operator (\c{++i}) advances the iterator to the | - | ||||||||||||
| 1973 | next item in the hash and returns an iterator to the new current | - | ||||||||||||
| 1974 | item. | - | ||||||||||||
| 1975 | - | |||||||||||||
| 1976 | Calling this function on QHash::end() leads to undefined results. | - | ||||||||||||
| 1977 | - | |||||||||||||
| 1978 | \sa operator--() | - | ||||||||||||
| 1979 | */ | - | ||||||||||||
| 1980 | - | |||||||||||||
| 1981 | /*! \fn QHash::iterator QHash::iterator::operator++(int) | - | ||||||||||||
| 1982 | - | |||||||||||||
| 1983 | \overload | - | ||||||||||||
| 1984 | - | |||||||||||||
| 1985 | The postfix ++ operator (\c{i++}) advances the iterator to the | - | ||||||||||||
| 1986 | next item in the hash and returns an iterator to the previously | - | ||||||||||||
| 1987 | current item. | - | ||||||||||||
| 1988 | */ | - | ||||||||||||
| 1989 | - | |||||||||||||
| 1990 | /*! | - | ||||||||||||
| 1991 | \fn QHash::iterator &QHash::iterator::operator--() | - | ||||||||||||
| 1992 | - | |||||||||||||
| 1993 | The prefix -- operator (\c{--i}) makes the preceding item | - | ||||||||||||
| 1994 | current and returns an iterator pointing to the new current item. | - | ||||||||||||
| 1995 | - | |||||||||||||
| 1996 | Calling this function on QHash::begin() leads to undefined | - | ||||||||||||
| 1997 | results. | - | ||||||||||||
| 1998 | - | |||||||||||||
| 1999 | \sa operator++() | - | ||||||||||||
| 2000 | */ | - | ||||||||||||
| 2001 | - | |||||||||||||
| 2002 | /*! | - | ||||||||||||
| 2003 | \fn QHash::iterator QHash::iterator::operator--(int) | - | ||||||||||||
| 2004 | - | |||||||||||||
| 2005 | \overload | - | ||||||||||||
| 2006 | - | |||||||||||||
| 2007 | The postfix -- operator (\c{i--}) makes the preceding item | - | ||||||||||||
| 2008 | current and returns an iterator pointing to the previously | - | ||||||||||||
| 2009 | current item. | - | ||||||||||||
| 2010 | */ | - | ||||||||||||
| 2011 | - | |||||||||||||
| 2012 | /*! \fn QHash::iterator QHash::iterator::operator+(int j) const | - | ||||||||||||
| 2013 | - | |||||||||||||
| 2014 | Returns an iterator to the item at \a j positions forward from | - | ||||||||||||
| 2015 | this iterator. (If \a j is negative, the iterator goes backward.) | - | ||||||||||||
| 2016 | - | |||||||||||||
| 2017 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2018 | - | |||||||||||||
| 2019 | \sa operator-() | - | ||||||||||||
| 2020 | - | |||||||||||||
| 2021 | */ | - | ||||||||||||
| 2022 | - | |||||||||||||
| 2023 | /*! \fn QHash::iterator QHash::iterator::operator-(int j) const | - | ||||||||||||
| 2024 | - | |||||||||||||
| 2025 | Returns an iterator to the item at \a j positions backward from | - | ||||||||||||
| 2026 | this iterator. (If \a j is negative, the iterator goes forward.) | - | ||||||||||||
| 2027 | - | |||||||||||||
| 2028 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2029 | - | |||||||||||||
| 2030 | \sa operator+() | - | ||||||||||||
| 2031 | */ | - | ||||||||||||
| 2032 | - | |||||||||||||
| 2033 | /*! \fn QHash::iterator &QHash::iterator::operator+=(int j) | - | ||||||||||||
| 2034 | - | |||||||||||||
| 2035 | Advances the iterator by \a j items. (If \a j is negative, the | - | ||||||||||||
| 2036 | iterator goes backward.) | - | ||||||||||||
| 2037 | - | |||||||||||||
| 2038 | \sa operator-=(), operator+() | - | ||||||||||||
| 2039 | */ | - | ||||||||||||
| 2040 | - | |||||||||||||
| 2041 | /*! \fn QHash::iterator &QHash::iterator::operator-=(int j) | - | ||||||||||||
| 2042 | - | |||||||||||||
| 2043 | Makes the iterator go back by \a j items. (If \a j is negative, | - | ||||||||||||
| 2044 | the iterator goes forward.) | - | ||||||||||||
| 2045 | - | |||||||||||||
| 2046 | \sa operator+=(), operator-() | - | ||||||||||||
| 2047 | */ | - | ||||||||||||
| 2048 | - | |||||||||||||
| 2049 | /*! \class QHash::const_iterator | - | ||||||||||||
| 2050 | \inmodule QtCore | - | ||||||||||||
| 2051 | \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash. | - | ||||||||||||
| 2052 | - | |||||||||||||
| 2053 | QHash features both \l{STL-style iterators} and \l{Java-style | - | ||||||||||||
| 2054 | iterators}. The STL-style iterators are more low-level and more | - | ||||||||||||
| 2055 | cumbersome to use; on the other hand, they are slightly faster | - | ||||||||||||
| 2056 | and, for developers who already know STL, have the advantage of | - | ||||||||||||
| 2057 | familiarity. | - | ||||||||||||
| 2058 | - | |||||||||||||
| 2059 | QHash\<Key, T\>::const_iterator allows you to iterate over a | - | ||||||||||||
| 2060 | QHash (or a QMultiHash). If you want to modify the QHash as you | - | ||||||||||||
| 2061 | iterate over it, you must use QHash::iterator instead. It is | - | ||||||||||||
| 2062 | generally good practice to use QHash::const_iterator on a | - | ||||||||||||
| 2063 | non-const QHash as well, unless you need to change the QHash | - | ||||||||||||
| 2064 | through the iterator. Const iterators are slightly faster, and | - | ||||||||||||
| 2065 | can improve code readability. | - | ||||||||||||
| 2066 | - | |||||||||||||
| 2067 | The default QHash::const_iterator constructor creates an | - | ||||||||||||
| 2068 | uninitialized iterator. You must initialize it using a QHash | - | ||||||||||||
| 2069 | function like QHash::constBegin(), QHash::constEnd(), or | - | ||||||||||||
| 2070 | QHash::find() before you can start iterating. Here's a typical | - | ||||||||||||
| 2071 | loop that prints all the (key, value) pairs stored in a hash: | - | ||||||||||||
| 2072 | - | |||||||||||||
| 2073 | \snippet code/src_corelib_tools_qhash.cpp 23 | - | ||||||||||||
| 2074 | - | |||||||||||||
| 2075 | Unlike QMap, which orders its items by key, QHash stores its | - | ||||||||||||
| 2076 | items in an arbitrary order. The only guarantee is that items that | - | ||||||||||||
| 2077 | share the same key (because they were inserted using | - | ||||||||||||
| 2078 | QHash::insertMulti()) will appear consecutively, from the most | - | ||||||||||||
| 2079 | recently to the least recently inserted value. | - | ||||||||||||
| 2080 | - | |||||||||||||
| 2081 | Multiple iterators can be used on the same hash. However, be aware | - | ||||||||||||
| 2082 | that any modification performed directly on the QHash has the | - | ||||||||||||
| 2083 | potential of dramatically changing the order in which the items | - | ||||||||||||
| 2084 | are stored in the hash, as they might cause QHash to rehash its | - | ||||||||||||
| 2085 | internal data structure. If you need to keep iterators over a long | - | ||||||||||||
| 2086 | period of time, we recommend that you use QMap rather than QHash. | - | ||||||||||||
| 2087 | - | |||||||||||||
| 2088 | \warning Iterators on implicitly shared containers do not work | - | ||||||||||||
| 2089 | exactly like STL-iterators. You should avoid copying a container | - | ||||||||||||
| 2090 | while iterators are active on that container. For more information, | - | ||||||||||||
| 2091 | read \l{Implicit sharing iterator problem}. | - | ||||||||||||
| 2092 | - | |||||||||||||
| 2093 | \sa QHash::iterator, QHashIterator | - | ||||||||||||
| 2094 | */ | - | ||||||||||||
| 2095 | - | |||||||||||||
| 2096 | /*! \fn QHash::const_iterator::const_iterator() | - | ||||||||||||
| 2097 | - | |||||||||||||
| 2098 | Constructs an uninitialized iterator. | - | ||||||||||||
| 2099 | - | |||||||||||||
| 2100 | Functions like key(), value(), and operator++() must not be | - | ||||||||||||
| 2101 | called on an uninitialized iterator. Use operator=() to assign a | - | ||||||||||||
| 2102 | value to it before using it. | - | ||||||||||||
| 2103 | - | |||||||||||||
| 2104 | \sa QHash::constBegin(), QHash::constEnd() | - | ||||||||||||
| 2105 | */ | - | ||||||||||||
| 2106 | - | |||||||||||||
| 2107 | /*! \fn QHash::const_iterator::const_iterator(void *node) | - | ||||||||||||
| 2108 | - | |||||||||||||
| 2109 | \internal | - | ||||||||||||
| 2110 | */ | - | ||||||||||||
| 2111 | - | |||||||||||||
| 2112 | /*! \fn QHash::const_iterator::const_iterator(const iterator &other) | - | ||||||||||||
| 2113 | - | |||||||||||||
| 2114 | Constructs a copy of \a other. | - | ||||||||||||
| 2115 | */ | - | ||||||||||||
| 2116 | - | |||||||||||||
| 2117 | /*! \fn const Key &QHash::const_iterator::key() const | - | ||||||||||||
| 2118 | - | |||||||||||||
| 2119 | Returns the current item's key. | - | ||||||||||||
| 2120 | - | |||||||||||||
| 2121 | \sa value() | - | ||||||||||||
| 2122 | */ | - | ||||||||||||
| 2123 | - | |||||||||||||
| 2124 | /*! \fn const T &QHash::const_iterator::value() const | - | ||||||||||||
| 2125 | - | |||||||||||||
| 2126 | Returns the current item's value. | - | ||||||||||||
| 2127 | - | |||||||||||||
| 2128 | \sa key(), operator*() | - | ||||||||||||
| 2129 | */ | - | ||||||||||||
| 2130 | - | |||||||||||||
| 2131 | /*! \fn const T &QHash::const_iterator::operator*() const | - | ||||||||||||
| 2132 | - | |||||||||||||
| 2133 | Returns the current item's value. | - | ||||||||||||
| 2134 | - | |||||||||||||
| 2135 | Same as value(). | - | ||||||||||||
| 2136 | - | |||||||||||||
| 2137 | \sa key() | - | ||||||||||||
| 2138 | */ | - | ||||||||||||
| 2139 | - | |||||||||||||
| 2140 | /*! \fn const T *QHash::const_iterator::operator->() const | - | ||||||||||||
| 2141 | - | |||||||||||||
| 2142 | Returns a pointer to the current item's value. | - | ||||||||||||
| 2143 | - | |||||||||||||
| 2144 | \sa value() | - | ||||||||||||
| 2145 | */ | - | ||||||||||||
| 2146 | - | |||||||||||||
| 2147 | /*! \fn bool QHash::const_iterator::operator==(const const_iterator &other) const | - | ||||||||||||
| 2148 | - | |||||||||||||
| 2149 | Returns \c true if \a other points to the same item as this | - | ||||||||||||
| 2150 | iterator; otherwise returns \c false. | - | ||||||||||||
| 2151 | - | |||||||||||||
| 2152 | \sa operator!=() | - | ||||||||||||
| 2153 | */ | - | ||||||||||||
| 2154 | - | |||||||||||||
| 2155 | /*! \fn bool QHash::const_iterator::operator!=(const const_iterator &other) const | - | ||||||||||||
| 2156 | - | |||||||||||||
| 2157 | Returns \c true if \a other points to a different item than this | - | ||||||||||||
| 2158 | iterator; otherwise returns \c false. | - | ||||||||||||
| 2159 | - | |||||||||||||
| 2160 | \sa operator==() | - | ||||||||||||
| 2161 | */ | - | ||||||||||||
| 2162 | - | |||||||||||||
| 2163 | /*! | - | ||||||||||||
| 2164 | \fn QHash::const_iterator &QHash::const_iterator::operator++() | - | ||||||||||||
| 2165 | - | |||||||||||||
| 2166 | The prefix ++ operator (\c{++i}) advances the iterator to the | - | ||||||||||||
| 2167 | next item in the hash and returns an iterator to the new current | - | ||||||||||||
| 2168 | item. | - | ||||||||||||
| 2169 | - | |||||||||||||
| 2170 | Calling this function on QHash::end() leads to undefined results. | - | ||||||||||||
| 2171 | - | |||||||||||||
| 2172 | \sa operator--() | - | ||||||||||||
| 2173 | */ | - | ||||||||||||
| 2174 | - | |||||||||||||
| 2175 | /*! \fn QHash::const_iterator QHash::const_iterator::operator++(int) | - | ||||||||||||
| 2176 | - | |||||||||||||
| 2177 | \overload | - | ||||||||||||
| 2178 | - | |||||||||||||
| 2179 | The postfix ++ operator (\c{i++}) advances the iterator to the | - | ||||||||||||
| 2180 | next item in the hash and returns an iterator to the previously | - | ||||||||||||
| 2181 | current item. | - | ||||||||||||
| 2182 | */ | - | ||||||||||||
| 2183 | - | |||||||||||||
| 2184 | /*! \fn QHash::const_iterator &QHash::const_iterator::operator--() | - | ||||||||||||
| 2185 | - | |||||||||||||
| 2186 | The prefix -- operator (\c{--i}) makes the preceding item | - | ||||||||||||
| 2187 | current and returns an iterator pointing to the new current item. | - | ||||||||||||
| 2188 | - | |||||||||||||
| 2189 | Calling this function on QHash::begin() leads to undefined | - | ||||||||||||
| 2190 | results. | - | ||||||||||||
| 2191 | - | |||||||||||||
| 2192 | \sa operator++() | - | ||||||||||||
| 2193 | */ | - | ||||||||||||
| 2194 | - | |||||||||||||
| 2195 | /*! \fn QHash::const_iterator QHash::const_iterator::operator--(int) | - | ||||||||||||
| 2196 | - | |||||||||||||
| 2197 | \overload | - | ||||||||||||
| 2198 | - | |||||||||||||
| 2199 | The postfix -- operator (\c{i--}) makes the preceding item | - | ||||||||||||
| 2200 | current and returns an iterator pointing to the previously | - | ||||||||||||
| 2201 | current item. | - | ||||||||||||
| 2202 | */ | - | ||||||||||||
| 2203 | - | |||||||||||||
| 2204 | /*! \fn QHash::const_iterator QHash::const_iterator::operator+(int j) const | - | ||||||||||||
| 2205 | - | |||||||||||||
| 2206 | Returns an iterator to the item at \a j positions forward from | - | ||||||||||||
| 2207 | this iterator. (If \a j is negative, the iterator goes backward.) | - | ||||||||||||
| 2208 | - | |||||||||||||
| 2209 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2210 | - | |||||||||||||
| 2211 | \sa operator-() | - | ||||||||||||
| 2212 | */ | - | ||||||||||||
| 2213 | - | |||||||||||||
| 2214 | /*! \fn QHash::const_iterator QHash::const_iterator::operator-(int j) const | - | ||||||||||||
| 2215 | - | |||||||||||||
| 2216 | Returns an iterator to the item at \a j positions backward from | - | ||||||||||||
| 2217 | this iterator. (If \a j is negative, the iterator goes forward.) | - | ||||||||||||
| 2218 | - | |||||||||||||
| 2219 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2220 | - | |||||||||||||
| 2221 | \sa operator+() | - | ||||||||||||
| 2222 | */ | - | ||||||||||||
| 2223 | - | |||||||||||||
| 2224 | /*! \fn QHash::const_iterator &QHash::const_iterator::operator+=(int j) | - | ||||||||||||
| 2225 | - | |||||||||||||
| 2226 | Advances the iterator by \a j items. (If \a j is negative, the | - | ||||||||||||
| 2227 | iterator goes backward.) | - | ||||||||||||
| 2228 | - | |||||||||||||
| 2229 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2230 | - | |||||||||||||
| 2231 | \sa operator-=(), operator+() | - | ||||||||||||
| 2232 | */ | - | ||||||||||||
| 2233 | - | |||||||||||||
| 2234 | /*! \fn QHash::const_iterator &QHash::const_iterator::operator-=(int j) | - | ||||||||||||
| 2235 | - | |||||||||||||
| 2236 | Makes the iterator go back by \a j items. (If \a j is negative, | - | ||||||||||||
| 2237 | the iterator goes forward.) | - | ||||||||||||
| 2238 | - | |||||||||||||
| 2239 | This operation can be slow for large \a j values. | - | ||||||||||||
| 2240 | - | |||||||||||||
| 2241 | \sa operator+=(), operator-() | - | ||||||||||||
| 2242 | */ | - | ||||||||||||
| 2243 | - | |||||||||||||
| 2244 | /*! \class QHash::key_iterator | - | ||||||||||||
| 2245 | \inmodule QtCore | - | ||||||||||||
| 2246 | \since 5.6 | - | ||||||||||||
| 2247 | \brief The QHash::key_iterator class provides an STL-style const iterator for QHash and QMultiHash keys. | - | ||||||||||||
| 2248 | - | |||||||||||||
| 2249 | QHash::key_iterator is essentially the same as QHash::const_iterator | - | ||||||||||||
| 2250 | with the difference that operator*() and operator->() return a key | - | ||||||||||||
| 2251 | instead of a value. | - | ||||||||||||
| 2252 | - | |||||||||||||
| 2253 | For most uses QHash::iterator and QHash::const_iterator should be used, | - | ||||||||||||
| 2254 | you can easily access the key by calling QHash::iterator::key(): | - | ||||||||||||
| 2255 | - | |||||||||||||
| 2256 | \snippet code/src_corelib_tools_qhash.cpp 27 | - | ||||||||||||
| 2257 | - | |||||||||||||
| 2258 | However, to have interoperability between QHash's keys and STL-style | - | ||||||||||||
| 2259 | algorithms we need an iterator that dereferences to a key instead | - | ||||||||||||
| 2260 | of a value. With QHash::key_iterator we can apply an algorithm to a | - | ||||||||||||
| 2261 | range of keys without having to call QHash::keys(), which is inefficient | - | ||||||||||||
| 2262 | as it costs one QHash iteration and memory allocation to create a temporary | - | ||||||||||||
| 2263 | QList. | - | ||||||||||||
| 2264 | - | |||||||||||||
| 2265 | \snippet code/src_corelib_tools_qhash.cpp 28 | - | ||||||||||||
| 2266 | - | |||||||||||||
| 2267 | QHash::key_iterator is const, it's not possible to modify the key. | - | ||||||||||||
| 2268 | - | |||||||||||||
| 2269 | The default QHash::key_iterator constructor creates an uninitialized | - | ||||||||||||
| 2270 | iterator. You must initialize it using a QHash function like | - | ||||||||||||
| 2271 | QHash::keyBegin() or QHash::keyEnd(). | - | ||||||||||||
| 2272 | - | |||||||||||||
| 2273 | \warning Iterators on implicitly shared containers do not work | - | ||||||||||||
| 2274 | exactly like STL-iterators. You should avoid copying a container | - | ||||||||||||
| 2275 | while iterators are active on that container. For more information, | - | ||||||||||||
| 2276 | read \l{Implicit sharing iterator problem}. | - | ||||||||||||
| 2277 | - | |||||||||||||
| 2278 | \sa QHash::const_iterator, QHash::iterator | - | ||||||||||||
| 2279 | */ | - | ||||||||||||
| 2280 | - | |||||||||||||
| 2281 | /*! \fn const T &QHash::key_iterator::operator*() const | - | ||||||||||||
| 2282 | - | |||||||||||||
| 2283 | Returns the current item's key. | - | ||||||||||||
| 2284 | */ | - | ||||||||||||
| 2285 | - | |||||||||||||
| 2286 | /*! \fn const T *QHash::key_iterator::operator->() const | - | ||||||||||||
| 2287 | - | |||||||||||||
| 2288 | Returns a pointer to the current item's key. | - | ||||||||||||
| 2289 | */ | - | ||||||||||||
| 2290 | - | |||||||||||||
| 2291 | /*! \fn bool QHash::key_iterator::operator==(key_iterator other) const | - | ||||||||||||
| 2292 | - | |||||||||||||
| 2293 | Returns \c true if \a other points to the same item as this | - | ||||||||||||
| 2294 | iterator; otherwise returns \c false. | - | ||||||||||||
| 2295 | - | |||||||||||||
| 2296 | \sa operator!=() | - | ||||||||||||
| 2297 | */ | - | ||||||||||||
| 2298 | - | |||||||||||||
| 2299 | /*! \fn bool QHash::key_iterator::operator!=(key_iterator other) const | - | ||||||||||||
| 2300 | - | |||||||||||||
| 2301 | Returns \c true if \a other points to a different item than this | - | ||||||||||||
| 2302 | iterator; otherwise returns \c false. | - | ||||||||||||
| 2303 | - | |||||||||||||
| 2304 | \sa operator==() | - | ||||||||||||
| 2305 | */ | - | ||||||||||||
| 2306 | - | |||||||||||||
| 2307 | /*! | - | ||||||||||||
| 2308 | \fn QHash::key_iterator &QHash::key_iterator::operator++() | - | ||||||||||||
| 2309 | - | |||||||||||||
| 2310 | The prefix ++ operator (\c{++i}) advances the iterator to the | - | ||||||||||||
| 2311 | next item in the hash and returns an iterator to the new current | - | ||||||||||||
| 2312 | item. | - | ||||||||||||
| 2313 | - | |||||||||||||
| 2314 | Calling this function on QHash::keyEnd() leads to undefined results. | - | ||||||||||||
| 2315 | - | |||||||||||||
| 2316 | \sa operator--() | - | ||||||||||||
| 2317 | */ | - | ||||||||||||
| 2318 | - | |||||||||||||
| 2319 | /*! \fn QHash::key_iterator QHash::key_iterator::operator++(int) | - | ||||||||||||
| 2320 | - | |||||||||||||
| 2321 | \overload | - | ||||||||||||
| 2322 | - | |||||||||||||
| 2323 | The postfix ++ operator (\c{i++}) advances the iterator to the | - | ||||||||||||
| 2324 | next item in the hash and returns an iterator to the previous | - | ||||||||||||
| 2325 | item. | - | ||||||||||||
| 2326 | */ | - | ||||||||||||
| 2327 | - | |||||||||||||
| 2328 | /*! \fn QHash::key_iterator &QHash::key_iterator::operator--() | - | ||||||||||||
| 2329 | - | |||||||||||||
| 2330 | The prefix -- operator (\c{--i}) makes the preceding item | - | ||||||||||||
| 2331 | current and returns an iterator pointing to the new current item. | - | ||||||||||||
| 2332 | - | |||||||||||||
| 2333 | Calling this function on QHash::keyBegin() leads to undefined | - | ||||||||||||
| 2334 | results. | - | ||||||||||||
| 2335 | - | |||||||||||||
| 2336 | \sa operator++() | - | ||||||||||||
| 2337 | */ | - | ||||||||||||
| 2338 | - | |||||||||||||
| 2339 | /*! \fn QHash::key_iterator QHash::key_iterator::operator--(int) | - | ||||||||||||
| 2340 | - | |||||||||||||
| 2341 | \overload | - | ||||||||||||
| 2342 | - | |||||||||||||
| 2343 | The postfix -- operator (\c{i--}) makes the preceding item | - | ||||||||||||
| 2344 | current and returns an iterator pointing to the previous | - | ||||||||||||
| 2345 | item. | - | ||||||||||||
| 2346 | */ | - | ||||||||||||
| 2347 | - | |||||||||||||
| 2348 | /*! \fn const_iterator QHash::key_iterator::base() const | - | ||||||||||||
| 2349 | Returns the underlying const_iterator this key_iterator is based on. | - | ||||||||||||
| 2350 | */ | - | ||||||||||||
| 2351 | - | |||||||||||||
| 2352 | /*! \fn QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash) | - | ||||||||||||
| 2353 | \relates QHash | - | ||||||||||||
| 2354 | - | |||||||||||||
| 2355 | Writes the hash \a hash to stream \a out. | - | ||||||||||||
| 2356 | - | |||||||||||||
| 2357 | This function requires the key and value types to implement \c | - | ||||||||||||
| 2358 | operator<<(). | - | ||||||||||||
| 2359 | - | |||||||||||||
| 2360 | \sa {Serializing Qt Data Types} | - | ||||||||||||
| 2361 | */ | - | ||||||||||||
| 2362 | - | |||||||||||||
| 2363 | /*! \fn QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash) | - | ||||||||||||
| 2364 | \relates QHash | - | ||||||||||||
| 2365 | - | |||||||||||||
| 2366 | Reads a hash from stream \a in into \a hash. | - | ||||||||||||
| 2367 | - | |||||||||||||
| 2368 | This function requires the key and value types to implement \c | - | ||||||||||||
| 2369 | operator>>(). | - | ||||||||||||
| 2370 | - | |||||||||||||
| 2371 | \sa {Serializing Qt Data Types} | - | ||||||||||||
| 2372 | */ | - | ||||||||||||
| 2373 | - | |||||||||||||
| 2374 | /*! \class QMultiHash | - | ||||||||||||
| 2375 | \inmodule QtCore | - | ||||||||||||
| 2376 | \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes. | - | ||||||||||||
| 2377 | - | |||||||||||||
| 2378 | \ingroup tools | - | ||||||||||||
| 2379 | \ingroup shared | - | ||||||||||||
| 2380 | - | |||||||||||||
| 2381 | \reentrant | - | ||||||||||||
| 2382 | - | |||||||||||||
| 2383 | QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}. | - | ||||||||||||
| 2384 | It inherits QHash and extends it with a few convenience functions | - | ||||||||||||
| 2385 | that make it more suitable than QHash for storing multi-valued | - | ||||||||||||
| 2386 | hashes. A multi-valued hash is a hash that allows multiple values | - | ||||||||||||
| 2387 | with the same key; QHash normally doesn't allow that, unless you | - | ||||||||||||
| 2388 | call QHash::insertMulti(). | - | ||||||||||||
| 2389 | - | |||||||||||||
| 2390 | Because QMultiHash inherits QHash, all of QHash's functionality also | - | ||||||||||||
| 2391 | applies to QMultiHash. For example, you can use isEmpty() to test | - | ||||||||||||
| 2392 | whether the hash is empty, and you can traverse a QMultiHash using | - | ||||||||||||
| 2393 | QHash's iterator classes (for example, QHashIterator). But in | - | ||||||||||||
| 2394 | addition, it provides an insert() function that corresponds to | - | ||||||||||||
| 2395 | QHash::insertMulti(), and a replace() function that corresponds to | - | ||||||||||||
| 2396 | QHash::insert(). It also provides convenient operator+() and | - | ||||||||||||
| 2397 | operator+=(). | - | ||||||||||||
| 2398 | - | |||||||||||||
| 2399 | Example: | - | ||||||||||||
| 2400 | \snippet code/src_corelib_tools_qhash.cpp 24 | - | ||||||||||||
| 2401 | - | |||||||||||||
| 2402 | Unlike QHash, QMultiHash provides no operator[]. Use value() or | - | ||||||||||||
| 2403 | replace() if you want to access the most recently inserted item | - | ||||||||||||
| 2404 | with a certain key. | - | ||||||||||||
| 2405 | - | |||||||||||||
| 2406 | If you want to retrieve all the values for a single key, you can | - | ||||||||||||
| 2407 | use values(const Key &key), which returns a QList<T>: | - | ||||||||||||
| 2408 | - | |||||||||||||
| 2409 | \snippet code/src_corelib_tools_qhash.cpp 25 | - | ||||||||||||
| 2410 | - | |||||||||||||
| 2411 | The items that share the same key are available from most | - | ||||||||||||
| 2412 | recently to least recently inserted. | - | ||||||||||||
| 2413 | - | |||||||||||||
| 2414 | A more efficient approach is to call find() to get | - | ||||||||||||
| 2415 | the STL-style iterator for the first item with a key and iterate from | - | ||||||||||||
| 2416 | there: | - | ||||||||||||
| 2417 | - | |||||||||||||
| 2418 | \snippet code/src_corelib_tools_qhash.cpp 26 | - | ||||||||||||
| 2419 | - | |||||||||||||
| 2420 | QMultiHash's key and value data types must be \l{assignable data | - | ||||||||||||
| 2421 | types}. You cannot, for example, store a QWidget as a value; | - | ||||||||||||
| 2422 | instead, store a QWidget *. In addition, QMultiHash's key type | - | ||||||||||||
| 2423 | must provide operator==(), and there must also be a qHash() function | - | ||||||||||||
| 2424 | in the type's namespace that returns a hash value for an argument of the | - | ||||||||||||
| 2425 | key's type. See the QHash documentation for details. | - | ||||||||||||
| 2426 | - | |||||||||||||
| 2427 | \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap | - | ||||||||||||
| 2428 | */ | - | ||||||||||||
| 2429 | - | |||||||||||||
| 2430 | /*! \fn QMultiHash::QMultiHash() | - | ||||||||||||
| 2431 | - | |||||||||||||
| 2432 | Constructs an empty hash. | - | ||||||||||||
| 2433 | */ | - | ||||||||||||
| 2434 | - | |||||||||||||
| 2435 | /*! \fn QMultiHash::QMultiHash(std::initializer_list<std::pair<Key,T> > list) | - | ||||||||||||
| 2436 | \since 5.1 | - | ||||||||||||
| 2437 | - | |||||||||||||
| 2438 | Constructs a multi hash with a copy of each of the elements in the | - | ||||||||||||
| 2439 | initializer list \a list. | - | ||||||||||||
| 2440 | - | |||||||||||||
| 2441 | This function is only available if the program is being | - | ||||||||||||
| 2442 | compiled in C++11 mode. | - | ||||||||||||
| 2443 | */ | - | ||||||||||||
| 2444 | - | |||||||||||||
| 2445 | /*! \fn QMultiHash::QMultiHash(const QHash<Key, T> &other) | - | ||||||||||||
| 2446 | - | |||||||||||||
| 2447 | Constructs a copy of \a other (which can be a QHash or a | - | ||||||||||||
| 2448 | QMultiHash). | - | ||||||||||||
| 2449 | - | |||||||||||||
| 2450 | \sa operator=() | - | ||||||||||||
| 2451 | */ | - | ||||||||||||
| 2452 | - | |||||||||||||
| 2453 | /*! \fn QMultiHash::iterator QMultiHash::replace(const Key &key, const T &value) | - | ||||||||||||
| 2454 | - | |||||||||||||
| 2455 | Inserts a new item with the \a key and a value of \a value. | - | ||||||||||||
| 2456 | - | |||||||||||||
| 2457 | If there is already an item with the \a key, that item's value | - | ||||||||||||
| 2458 | is replaced with \a value. | - | ||||||||||||
| 2459 | - | |||||||||||||
| 2460 | If there are multiple items with the \a key, the most | - | ||||||||||||
| 2461 | recently inserted item's value is replaced with \a value. | - | ||||||||||||
| 2462 | - | |||||||||||||
| 2463 | \sa insert() | - | ||||||||||||
| 2464 | */ | - | ||||||||||||
| 2465 | - | |||||||||||||
| 2466 | /*! \fn QMultiHash::iterator QMultiHash::insert(const Key &key, const T &value) | - | ||||||||||||
| 2467 | - | |||||||||||||
| 2468 | Inserts a new item with the \a key and a value of \a value. | - | ||||||||||||
| 2469 | - | |||||||||||||
| 2470 | If there is already an item with the same key in the hash, this | - | ||||||||||||
| 2471 | function will simply create a new one. (This behavior is | - | ||||||||||||
| 2472 | different from replace(), which overwrites the value of an | - | ||||||||||||
| 2473 | existing item.) | - | ||||||||||||
| 2474 | - | |||||||||||||
| 2475 | \sa replace() | - | ||||||||||||
| 2476 | */ | - | ||||||||||||
| 2477 | - | |||||||||||||
| 2478 | /*! \fn QMultiHash &QMultiHash::operator+=(const QMultiHash &other) | - | ||||||||||||
| 2479 | - | |||||||||||||
| 2480 | Inserts all the items in the \a other hash into this hash | - | ||||||||||||
| 2481 | and returns a reference to this hash. | - | ||||||||||||
| 2482 | - | |||||||||||||
| 2483 | \sa insert() | - | ||||||||||||
| 2484 | */ | - | ||||||||||||
| 2485 | - | |||||||||||||
| 2486 | /*! \fn QMultiHash QMultiHash::operator+(const QMultiHash &other) const | - | ||||||||||||
| 2487 | - | |||||||||||||
| 2488 | Returns a hash that contains all the items in this hash in | - | ||||||||||||
| 2489 | addition to all the items in \a other. If a key is common to both | - | ||||||||||||
| 2490 | hashes, the resulting hash will contain the key multiple times. | - | ||||||||||||
| 2491 | - | |||||||||||||
| 2492 | \sa operator+=() | - | ||||||||||||
| 2493 | */ | - | ||||||||||||
| 2494 | - | |||||||||||||
| 2495 | /*! | - | ||||||||||||
| 2496 | \fn bool QMultiHash::contains(const Key &key, const T &value) const | - | ||||||||||||
| 2497 | \since 4.3 | - | ||||||||||||
| 2498 | - | |||||||||||||
| 2499 | Returns \c true if the hash contains an item with the \a key and | - | ||||||||||||
| 2500 | \a value; otherwise returns \c false. | - | ||||||||||||
| 2501 | - | |||||||||||||
| 2502 | \sa QHash::contains() | - | ||||||||||||
| 2503 | */ | - | ||||||||||||
| 2504 | - | |||||||||||||
| 2505 | /*! | - | ||||||||||||
| 2506 | \fn int QMultiHash::remove(const Key &key, const T &value) | - | ||||||||||||
| 2507 | \since 4.3 | - | ||||||||||||
| 2508 | - | |||||||||||||
| 2509 | Removes all the items that have the \a key and the value \a | - | ||||||||||||
| 2510 | value from the hash. Returns the number of items removed. | - | ||||||||||||
| 2511 | - | |||||||||||||
| 2512 | \sa QHash::remove() | - | ||||||||||||
| 2513 | */ | - | ||||||||||||
| 2514 | - | |||||||||||||
| 2515 | /*! | - | ||||||||||||
| 2516 | \fn int QMultiHash::count(const Key &key, const T &value) const | - | ||||||||||||
| 2517 | \since 4.3 | - | ||||||||||||
| 2518 | - | |||||||||||||
| 2519 | Returns the number of items with the \a key and \a value. | - | ||||||||||||
| 2520 | - | |||||||||||||
| 2521 | \sa QHash::count() | - | ||||||||||||
| 2522 | */ | - | ||||||||||||
| 2523 | - | |||||||||||||
| 2524 | /*! | - | ||||||||||||
| 2525 | \fn typename QHash<Key, T>::iterator QMultiHash::find(const Key &key, const T &value) | - | ||||||||||||
| 2526 | \since 4.3 | - | ||||||||||||
| 2527 | - | |||||||||||||
| 2528 | Returns an iterator pointing to the item with the \a key and \a value. | - | ||||||||||||
| 2529 | If the hash contains no such item, the function returns end(). | - | ||||||||||||
| 2530 | - | |||||||||||||
| 2531 | If the hash contains multiple items with the \a key and \a value, the | - | ||||||||||||
| 2532 | iterator returned points to the most recently inserted item. | - | ||||||||||||
| 2533 | - | |||||||||||||
| 2534 | \sa QHash::find() | - | ||||||||||||
| 2535 | */ | - | ||||||||||||
| 2536 | - | |||||||||||||
| 2537 | /*! | - | ||||||||||||
| 2538 | \fn typename QHash<Key, T>::const_iterator QMultiHash::find(const Key &key, const T &value) const | - | ||||||||||||
| 2539 | \since 4.3 | - | ||||||||||||
| 2540 | \overload | - | ||||||||||||
| 2541 | */ | - | ||||||||||||
| 2542 | - | |||||||||||||
| 2543 | /*! | - | ||||||||||||
| 2544 | \fn typename QHash<Key, T>::const_iterator QMultiHash::constFind(const Key &key, const T &value) const | - | ||||||||||||
| 2545 | \since 4.3 | - | ||||||||||||
| 2546 | - | |||||||||||||
| 2547 | Returns an iterator pointing to the item with the \a key and the | - | ||||||||||||
| 2548 | \a value in the hash. | - | ||||||||||||
| 2549 | - | |||||||||||||
| 2550 | If the hash contains no such item, the function returns | - | ||||||||||||
| 2551 | constEnd(). | - | ||||||||||||
| 2552 | - | |||||||||||||
| 2553 | \sa QHash::constFind() | - | ||||||||||||
| 2554 | */ | - | ||||||||||||
| 2555 | - | |||||||||||||
| 2556 | QT_END_NAMESPACE | - | ||||||||||||
| Source code | Switch to Preprocessed file |