Line data Source code
1 : /*
2 : * Copyright (C) 2011 Gerd Lorscheid
3 : * Copyright (C) 2011-2017 Fulvio Benini
4 : *
5 : * This file is part of Scid (Shane's Chess Information Database).
6 : *
7 : * Scid is free software: you can redistribute it and/or modify
8 : * it under the terms of the GNU General Public License as published by
9 : * the Free Software Foundation.
10 : *
11 : * Scid is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with Scid. If not, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : /** @file
21 : * Implements the SortCache class, which sorts the games of an @e Index.
22 : */
23 :
24 : #include "sortcache.h"
25 : #include "hfilter.h"
26 : #include "index.h"
27 : #include "misc.h"
28 : #include <algorithm>
29 : #include <climits>
30 : #include <cstring>
31 : #include <numeric>
32 :
33 : #ifndef MULTITHREADING_OFF
34 : #include <thread>
35 :
36 : /**
37 : * Blocks the current thread until the thread @e th_ finishes its execution.
38 : */
39 15133 : void SortCache::th_join() {
40 15133 : if (th_ != nullptr) {
41 76 : static_cast<std::thread*>(th_)->join();
42 76 : delete static_cast<std::thread*>(th_);
43 76 : th_ = nullptr;
44 : }
45 15133 : }
46 :
47 : /**
48 : * Populate @e fullMap_ with the sorted ids of all the games contained into @e
49 : * index_. This function can run in a worker thread and can be interrupted.
50 : * It is necessary to invoke th_interrupt() or th_join() before modifying the
51 : * SortCache object, or the associated Index and NameBase objects.
52 : */
53 76 : void SortCache::th_sort() {
54 76 : size_t nGames = this->nGames_;
55 76 : gamenumT* v = this->fullMap_;
56 76 : gamenumT* begin = v;
57 76 : gamenumT* end = v + nGames;
58 76 : auto comp = SortCache::CmpLess(this);
59 :
60 76 : std::iota(begin, end, 0);
61 :
62 : // An interruptible implementation of:
63 : // std::make_heap(v.begin(), v.end(), comp);
64 76 : ASSERT(nGames < size_t(INT_MAX / 2));
65 76 : const int lastNode = static_cast<int>(nGames) - 1;
66 76 : const auto lastRoot = (lastNode - 1) / 2;
67 50251 : for (auto node = lastRoot; node >= 0; --node) {
68 50176 : if (this->th_interrupt_)
69 2 : return;
70 : // Sift down @e node
71 50175 : for (auto toSift = node;;) {
72 125330 : const auto leftChild = 2 * toSift + 1;
73 125330 : const auto rightChild = 2 * toSift + 2;
74 125330 : if (leftChild > lastNode)
75 32664 : break;
76 92666 : int maxChild = (rightChild <= lastNode && comp(v[leftChild], v[rightChild]))
77 145560 : ? rightChild
78 92666 : : leftChild;
79 92666 : if (!comp(v[toSift], v[maxChild]))
80 17511 : break;
81 75155 : std::swap(v[toSift], v[maxChild]);
82 75155 : toSift = maxChild;
83 75155 : }
84 : }
85 75 : ASSERT(std::is_heap(begin, end, comp));
86 :
87 : // An interruptible implementation of:
88 : // std::sort_heap(v.begin(), v.end(), comp);
89 100500 : for (auto it = end; it != begin; --it) {
90 100425 : if (this->th_interrupt_)
91 0 : return;
92 100425 : std::pop_heap(begin, it, comp);
93 : }
94 75 : ASSERT(std::is_sorted(begin, end, comp));
95 :
96 75 : this->valid_fullMap_ = true;
97 : }
98 :
99 : #else
100 : void SortCache::th_join() {}
101 : void SortCache::th_sort() {}
102 : #endif
103 :
104 :
105 15133 : SortCache::SortCache(const Index* idx, const NameBase* nbase)
106 : : nGames_(0), valid_fullMap_(false), th_interrupt_(false),
107 : partialHash_(false), fullMap_(NULL), th_(NULL), hash_(NULL), index_(idx),
108 15133 : nbase_(nbase), refCount_(0) {}
109 :
110 30266 : SortCache::~SortCache() {
111 15133 : th_interrupt();
112 15133 : delete[] hash_;
113 15133 : delete[] fullMap_;
114 15133 : }
115 :
116 15133 : SortCache* SortCache::create(const Index* idx, const NameBase* nb,
117 : const char* criteria) {
118 15133 : ASSERT(idx != NULL && nb != NULL && criteria != NULL);
119 :
120 : static const char fields[] = {
121 : SORTING_date, SORTING_year, SORTING_event,
122 : SORTING_site, SORTING_round, SORTING_white,
123 : SORTING_black, SORTING_eco, SORTING_result,
124 : SORTING_moveCount, SORTING_avgElo, SORTING_country,
125 : SORTING_deleted, SORTING_eventdate, SORTING_whiteelo,
126 : SORTING_blackelo, SORTING_commentcount, SORTING_varcount,
127 : SORTING_nagcount, SORTING_resultwin, SORTING_resultdraw,
128 : SORTING_resultloss, SORTING_rating, SORTING_number,
129 : SORTING_sentinel};
130 : static const char* fields_end = fields + sizeof(fields);
131 :
132 15133 : if (*criteria == '\0') // Invalid empty criteria.
133 0 : return NULL;
134 :
135 15133 : SortCache* sc = new SortCache(idx, nb);
136 :
137 : // Parse the sorting criteria.
138 15133 : size_t i = 0;
139 15361 : for (const char *it = criteria; *it != 0; ++it) {
140 15285 : bool valid = std::find(fields, fields_end, *it) != fields_end;
141 15285 : sc->criteria_[i++] = *it++;
142 15285 : bool reverse = (*it != '+');
143 15285 : sc->criteria_[i++] = reverse ? 1 : 0;
144 15285 : if (!valid // Unknown field
145 732 : || (reverse && *it != '-') // Invalid asc/desc param
146 228 : || i >= sizeof(sc->criteria_)) // No space left for SORTING_sentinel
147 : {
148 15057 : delete sc;
149 15057 : return NULL;
150 : }
151 : }
152 76 : sc->criteria_[i] = SORTING_sentinel;
153 :
154 76 : sc->generateHashCache();
155 76 : sc->sortAsynchronously();
156 :
157 76 : return sc;
158 : }
159 :
160 1560 : size_t SortCache::select(size_t row_offset, size_t row_count,
161 : const HFilter& filter, gamenumT* result) const {
162 1560 : ASSERT(filter != NULL && filter->size() <= nGames_);
163 1560 : ASSERT(result != NULL);
164 :
165 1560 : size_t maxResults = filter->size();
166 1560 : if (row_count == 0 || row_offset >= maxResults)
167 0 : return 0;
168 :
169 1560 : size_t row_end = std::min(row_offset + row_count, maxResults);
170 :
171 1560 : if (!valid_fullMap_) {
172 223 : gamenumT* v = new gamenumT[maxResults];
173 223 : gamenumT* v_end = v + maxResults;
174 223 : if (maxResults == nGames_) {
175 : // std::iota(v, v_end, 0);
176 298820 : for (gamenumT i = 0; i < maxResults; ++i) {
177 298597 : v[i] = i;
178 : }
179 : } else {
180 0 : std::copy(filter->begin(), filter->end(), v);
181 : }
182 :
183 223 : size_t skip = 0;
184 223 : if (row_offset > 1000) {
185 31 : skip = row_offset;
186 31 : std::nth_element(v, v + row_offset, v_end, CmpLess(this));
187 : }
188 223 : std::partial_sort(v + skip, v + row_end, v_end, CmpLess(this));
189 223 : std::copy(v + row_offset, v + row_end, result);
190 223 : delete[] v;
191 : } else {
192 1337 : if (maxResults == nGames_) {
193 557 : std::copy(fullMap_ + row_offset, fullMap_ + row_end, result);
194 : } else {
195 780 : size_t filterCount = 0;
196 780 : size_t i = 0;
197 1048040 : for (; filterCount < row_offset; i++) {
198 523630 : if (filter->get(fullMap_[i]) != 0)
199 260520 : filterCount++;
200 : }
201 1041160 : for (; filterCount != row_end; i++) {
202 520190 : if (filter->get(fullMap_[i]) != 0) {
203 262080 : *result++ = fullMap_[i];
204 262080 : filterCount++;
205 : }
206 : }
207 : }
208 : }
209 :
210 1560 : return row_end - row_offset;
211 : }
212 :
213 3120 : size_t SortCache::sortedPosition(gamenumT gameId, const HFilter& filter) const {
214 3120 : ASSERT(filter != 0 && filter->size() <= nGames_);
215 3120 : ASSERT(gameId < nGames_ && filter->get(gameId) != 0);
216 :
217 3120 : size_t res = 0;
218 3120 : if (valid_fullMap_) {
219 2108392 : for (gamenumT i = 0; i < nGames_; i++) {
220 2108392 : if (filter->get(fullMap_[i]) == 0)
221 534346 : continue;
222 1574046 : if (fullMap_[i] == gameId)
223 3086 : break;
224 1570960 : res++;
225 : }
226 : } else {
227 34 : CmpLess comp(this);
228 45560 : for (gamenumT i = 0; i < nGames_; i++) {
229 45526 : if (filter->get(i) == 0)
230 0 : continue;
231 45526 : if (comp(i, gameId))
232 21308 : ++res;
233 : }
234 : }
235 3120 : return res;
236 : }
237 :
238 0 : void SortCache::checkForChanges(gamenumT id) {
239 0 : th_interrupt();
240 0 : if (id >= nGames_) {
241 0 : generateHashCache();
242 0 : sortAsynchronously();
243 : } else {
244 0 : hash_[id] = calcHash(id);
245 0 : if (valid_fullMap_) {
246 0 : gamenumT* begin = fullMap_;
247 0 : gamenumT* end = fullMap_ + nGames_;
248 0 : gamenumT* it = std::find(begin, end, id);
249 0 : ASSERT(it != end);
250 : // Reposition the game if necessary:
251 : // - to the left if it compares less than the previous element;
252 : // - to the right if the next element is lower.
253 0 : CmpLess comp(this);
254 0 : if (it != begin && comp(*it, *(it - 1))) {
255 0 : std::rotate(
256 : std::upper_bound(begin, it, *it, comp),
257 : it, it + 1);
258 0 : } else if (it + 1 != end && comp(*(it + 1), *it)) {
259 0 : std::rotate(
260 : it, it + 1,
261 : std::lower_bound(it + 1, end, *it, comp));
262 : }
263 0 : ASSERT(std::is_sorted(begin, end, comp));
264 : } else {
265 0 : sortAsynchronously();
266 : }
267 : }
268 0 : }
269 :
270 : /*
271 : * Calculate the hashes of all games and store them into @e hash_.
272 : */
273 76 : void SortCache::generateHashCache() {
274 76 : ASSERT(th_ == nullptr);
275 :
276 76 : valid_fullMap_ = false;
277 76 : nGames_ = index_->GetNumGames();
278 :
279 : // Generate the hash table.
280 76 : delete[] hash_;
281 76 : hash_ = new uint32_t[nGames_];
282 101840 : for (gamenumT i = 0; i < nGames_; i++) {
283 101764 : hash_[i] = calcHash(i);
284 : }
285 76 : }
286 :
287 : /*
288 : * Start a background thread that will sort the gameIds and will populate @e
289 : * fullMap_.
290 : */
291 76 : void SortCache::sortAsynchronously() {
292 76 : ASSERT(th_ == nullptr);
293 :
294 : #ifndef MULTITHREADING_OFF
295 76 : delete[] fullMap_;
296 76 : fullMap_ = new gamenumT[nGames_];
297 76 : th_ = new std::thread(&SortCache::th_sort, this);
298 : #endif
299 76 : }
300 :
301 : /*
302 : * Compare two games according to @e criteria_.
303 : * The @e index_ is accessed only if the games' hashes are equal.
304 : * @param g1: the id of the first game.
305 : * @param g2: the id of the second game.
306 : * @returns true if @e g1 is ordered before @e g2.
307 : */
308 4320165 : bool SortCache::CmpLess::operator()(gamenumT g1, gamenumT g2) const {
309 4320165 : ASSERT(g1 < sc_->nGames_ && g2 < sc_->nGames_);
310 :
311 4320165 : if (sc_->hash_[g1] != sc_->hash_[g2])
312 2469334 : return sc_->hash_[g1] < sc_->hash_[g2];
313 1850831 : if (!sc_->partialHash_)
314 1347705 : return g1 < g2;
315 :
316 503126 : int cmp = sc_->fullCompare(g1, g2);
317 503126 : if (cmp != 0)
318 279202 : return cmp < 0;
319 :
320 223924 : return g1 < g2;
321 : }
322 :
323 : static const int RESULT_SORT[] = { 0, 3, 1, 2 };
324 228576 : static int nameComp(const NameBase* nbase, nameT nt, idNumberT id1,
325 : idNumberT id2) {
326 228576 : ASSERT(nbase != NULL);
327 313871 : return (id1 == id2) ? 0
328 85295 : : strCaseCompare(nbase->GetName(nt, id1),
329 228576 : nbase->GetName(nt, id2));
330 : }
331 :
332 : /*
333 : * Compare two games according to @e criteria_.
334 : * @param left: the id of the first game.
335 : * @param right: the id of the second game.
336 : * @returns
337 : * - <0 if @e left is ordered before @e right.
338 : * - >0 if @e right is ordered before @e left.
339 : * - 0 otherwise.
340 : */
341 503126 : int SortCache::fullCompare(gamenumT left, gamenumT right) const {
342 503126 : const IndexEntry *ie1 = index_->GetEntry(left);
343 503126 : const IndexEntry *ie2 = index_->GetEntry(right);
344 :
345 1594206 : for (const char* field = criteria_; *field != SORTING_sentinel; field += 2) {
346 : int res;
347 1370282 : switch (*field) {
348 26022 : case SORTING_date:
349 26022 : res = (int)ie1->GetDate() - (int)ie2->GetDate();
350 26022 : break;
351 :
352 31203 : case SORTING_year:
353 31203 : res = (int)ie1->GetYear() - (int)ie2->GetYear();
354 31203 : break;
355 :
356 47273 : case SORTING_eco:
357 47273 : res = (int)ie1->GetEcoCode() - (int)ie2->GetEcoCode();
358 47514 : break;
359 :
360 79296 : case SORTING_moveCount:
361 79296 : res = (int)ie1->GetNumHalfMoves() - (int)ie2->GetNumHalfMoves();
362 79296 : break;
363 :
364 49753 : case SORTING_white:
365 49753 : res = nameComp(nbase_, NAME_PLAYER, ie1->GetWhite(), ie2->GetWhite());
366 49753 : break;
367 :
368 88616 : case SORTING_black:
369 88616 : res = nameComp(nbase_, NAME_PLAYER, ie1->GetBlack(), ie2->GetBlack());
370 88616 : break;
371 :
372 38598 : case SORTING_event:
373 38598 : res = nameComp(nbase_, NAME_EVENT, ie1->GetEvent(), ie2->GetEvent());
374 38598 : break;
375 :
376 51609 : case SORTING_site:
377 51609 : res = nameComp(nbase_, NAME_SITE, ie1->GetSite(), ie2->GetSite());
378 51609 : break;
379 :
380 113423 : case SORTING_round: {
381 113423 : idNumberT id1 = ie1->GetRound();
382 113423 : idNumberT id2 = ie2->GetRound();
383 113423 : res = (id1 == id2)
384 149353 : ? 0
385 35930 : : strCompareRound(nbase_->GetName(NAME_ROUND, id1),
386 35930 : nbase_->GetName(NAME_ROUND, id2));
387 113423 : break;
388 : }
389 :
390 50202 : case SORTING_resultwin:
391 50202 : res = (ie1->GetResult() == RESULT_White ? 1 : 0) - (ie2->GetResult() == RESULT_White ? 1 : 0);
392 50202 : break;
393 :
394 92358 : case SORTING_resultdraw:
395 92358 : res = (ie1->GetResult() == RESULT_Draw ? 1 : 0) - (ie2->GetResult() == RESULT_Draw ? 1 : 0);
396 92358 : break;
397 :
398 144134 : case SORTING_resultloss:
399 144134 : res = (ie1->GetResult() == RESULT_Black ? 1 : 0) - (ie2->GetResult() == RESULT_Black ? 1 : 0);
400 144134 : break;
401 :
402 105371 : case SORTING_result:
403 105371 : res = RESULT_SORT[ie1->GetResult()] - RESULT_SORT[ie2->GetResult()];
404 105371 : break;
405 :
406 21885 : case SORTING_avgElo: // Average Elo rating:
407 : {
408 21885 : int r1 = ie1->GetWhiteElo(nbase_) + ie1->GetBlackElo(nbase_);
409 21885 : int r2 = ie2->GetWhiteElo(nbase_) + ie2->GetBlackElo(nbase_);
410 21885 : res = r1 - r2;
411 : }
412 21885 : break;
413 :
414 91405 : case SORTING_country: // Last 3 characters of site field:
415 : {
416 91405 : const char* sOne = ie1->GetSiteName(nbase_);
417 91405 : const char* sTwo = ie2->GetSiteName(nbase_);
418 91405 : size_t slenOne = std::strlen(sOne);
419 91405 : size_t slenTwo = std::strlen(sTwo);
420 91405 : if (slenOne > 3) { sOne += slenOne - 3; }
421 91405 : if (slenTwo > 3) { sTwo += slenTwo - 3; }
422 91405 : res = strCaseCompare (sOne, sTwo);
423 : }
424 91405 : break;
425 :
426 30355 : case SORTING_deleted:
427 30355 : res = (int)ie1->GetDeleteFlag() - (int)ie2->GetDeleteFlag();
428 30355 : break;
429 :
430 52056 : case SORTING_eventdate:
431 52056 : res = (int)ie1->GetEventDate() - (int)ie2->GetEventDate();
432 52056 : break;
433 :
434 7320 : case SORTING_whiteelo:
435 7320 : res = (int)ie1->GetWhiteElo(nbase_) - (int)ie2->GetWhiteElo(nbase_);
436 7320 : break;
437 :
438 43701 : case SORTING_blackelo:
439 43701 : res = (int)ie1->GetBlackElo(nbase_) - (int)ie2->GetBlackElo(nbase_);
440 43701 : break;
441 :
442 62371 : case SORTING_commentcount:
443 62371 : res = (int) ie1->GetCommentCount() - (int) ie2->GetCommentCount();
444 62371 : break;
445 :
446 68038 : case SORTING_varcount:
447 68038 : res = (int) ie1->GetVariationCount() - (int) ie2->GetVariationCount();
448 68038 : break;
449 :
450 44807 : case SORTING_nagcount:
451 44807 : res = (int) ie1->GetNagCount() - (int) ie2->GetNagCount();
452 44807 : break;
453 :
454 13217 : case SORTING_rating:
455 13217 : res = (int)ie1->GetRating(nbase_) - (int)ie2->GetRating(nbase_);
456 13217 : break;
457 :
458 17269 : case SORTING_number:
459 17269 : res = (int) left - (int) right;
460 17269 : break;
461 :
462 0 : default: // Should never happen:
463 0 : ASSERT(0);
464 : return 0;
465 : }
466 :
467 1370523 : if (res != 0)
468 279202 : return *(field + 1) ? -res : res;
469 : }
470 :
471 223924 : return 0;
472 : }
473 :
474 : /*
475 : * Calculate an order-preserving hash corresponding to the current criteria.
476 : * @param gameId: the id of the game whose hash should be calculated.
477 : * @returns the hash value.
478 : */
479 101764 : uint32_t SortCache::calcHash(gamenumT gameId) {
480 101764 : uint64_t retValue = 0;
481 101764 : const size_t nHashBits = 32;
482 101764 : size_t totalBitsUsed = 0;
483 101764 : const IndexEntry* ie = index_->GetEntry(gameId);
484 :
485 191477 : for (const char* field = criteria_; *field != SORTING_sentinel; ++field) {
486 : uint32_t value;
487 : size_t bitsUsed;
488 147290 : switch (*field) {
489 5356 : case SORTING_white:
490 5356 : value = strStartHash(ie->GetWhiteName(nbase_));
491 5356 : bitsUsed = nHashBits;
492 5356 : partialHash_ = true;
493 5356 : break;
494 4017 : case SORTING_black:
495 4017 : value = strStartHash(ie->GetBlackName(nbase_));
496 4017 : bitsUsed = nHashBits;
497 4017 : partialHash_ = true;
498 4017 : break;
499 5356 : case SORTING_site:
500 5356 : value = strStartHash(ie->GetSiteName(nbase_));
501 5356 : bitsUsed = nHashBits;
502 5356 : partialHash_ = true;
503 5356 : break;
504 6695 : case SORTING_event:
505 6695 : value = strStartHash(ie->GetEventName(nbase_));
506 6695 : bitsUsed = nHashBits;
507 6695 : partialHash_ = true;
508 6695 : break;
509 4017 : case SORTING_round:
510 4017 : value = strGetUnsigned(ie->GetRoundName(nbase_));
511 4017 : bitsUsed = nHashBits;
512 4017 : partialHash_ = true;
513 4017 : break;
514 8034 : case SORTING_country:
515 : {
516 8034 : const char *scountry = ie->GetSiteName (nbase_);
517 8034 : size_t slen = std::strlen(scountry);
518 8034 : if (slen > 3)
519 7452 : scountry += slen - 3;
520 8034 : value = strStartHash(scountry);
521 8034 : bitsUsed = nHashBits;
522 8034 : partialHash_ = true;
523 8034 : break;
524 : }
525 9373 : case SORTING_date:
526 9373 : value = ie->GetDate();
527 9373 : bitsUsed = 24;
528 9373 : break;
529 4017 : case SORTING_eventdate:
530 4017 : value = ie->GetEventDate();
531 4017 : bitsUsed = 32;
532 4017 : break;
533 4017 : case SORTING_year:
534 4017 : value = ie->GetYear();
535 4017 : bitsUsed = 16;
536 4017 : break;
537 5356 : case SORTING_whiteelo:
538 5356 : value = ie->GetWhiteElo(nbase_);
539 5356 : bitsUsed = 16;
540 5356 : break;
541 8034 : case SORTING_blackelo:
542 8034 : value = ie->GetBlackElo(nbase_);
543 8034 : bitsUsed = 16;
544 8034 : break;
545 4017 : case SORTING_avgElo:
546 4017 : value = ie->GetWhiteElo(nbase_) + ie->GetBlackElo(nbase_);
547 4017 : bitsUsed = 16;
548 4017 : break;
549 9373 : case SORTING_result:
550 9373 : value = RESULT_SORT[ie->GetResult()];
551 9373 : bitsUsed = 8;
552 9373 : break;
553 6695 : case SORTING_resultwin:
554 6695 : value = ie->GetResult() == RESULT_White ? 1 : 0;
555 6695 : bitsUsed = 8;
556 6695 : break;
557 8034 : case SORTING_resultdraw:
558 8034 : value = ie->GetResult() == RESULT_Draw ? 1 : 0;
559 8034 : bitsUsed = 8;
560 8034 : break;
561 12051 : case SORTING_resultloss:
562 12051 : value = ie->GetResult() == RESULT_Black ? 1 : 0;
563 12051 : bitsUsed = 8;
564 12051 : break;
565 9373 : case SORTING_moveCount:
566 9373 : value = ie->GetNumHalfMoves();
567 9373 : bitsUsed = 16;
568 9373 : break;
569 6695 : case SORTING_eco:
570 6695 : value = ie->GetEcoCode();
571 6695 : bitsUsed = 16;
572 6695 : break;
573 5356 : case SORTING_commentcount:
574 5356 : value = ie->GetCommentCount();
575 5356 : bitsUsed = 16;
576 5356 : break;
577 5356 : case SORTING_varcount:
578 5356 : value = ie->GetVariationCount();
579 5356 : bitsUsed = 16;
580 5356 : break;
581 2678 : case SORTING_nagcount:
582 2678 : value = ie->GetNagCount();
583 2678 : bitsUsed = 16;
584 2678 : break;
585 4017 : case SORTING_deleted:
586 4017 : value = (ie->GetDeleteFlag() ? 1 : 0);
587 4017 : bitsUsed = 8;
588 4017 : break;
589 5356 : case SORTING_rating:
590 5356 : value = ie->GetRating(nbase_);
591 5356 : bitsUsed = 8;
592 5356 : break;
593 4017 : case SORTING_number:
594 4017 : value = gameId;
595 4017 : bitsUsed = 32;
596 4017 : break;
597 0 : default: // Should never happen:
598 0 : ASSERT(0);
599 : partialHash_ = true;
600 : return 0;
601 : }
602 :
603 : // If reverse order, just negate the cache value
604 147290 : if (*++field) {
605 83018 : value = ~value;
606 83018 : if (sizeof(value) * 8 > bitsUsed) {
607 : // Clear the unused top bits
608 57577 : value <<= sizeof(value) * 8 - bitsUsed;
609 57577 : value >>= sizeof(value) * 8 - bitsUsed;
610 : }
611 : }
612 : // Combine with previous hash value
613 147290 : retValue <<= bitsUsed;
614 147290 : retValue |= value;
615 147290 : totalBitsUsed += bitsUsed;
616 :
617 : // If not all search attributes fit, then it is a partial hash
618 147290 : if (totalBitsUsed > nHashBits) {
619 18746 : retValue >>= totalBitsUsed - nHashBits;
620 18746 : partialHash_ = true;
621 18746 : break;
622 : }
623 128544 : if (totalBitsUsed == nHashBits) {
624 38831 : if (*(field + 1) != SORTING_sentinel)
625 17407 : partialHash_ = true;
626 38831 : break;
627 : }
628 : }
629 :
630 101764 : return static_cast<uint32_t>(retValue);
631 : }
|
