Given a string element to add to the HyperLogLog, returns the length * of the pattern 000..1 of the element hash. As a side effect 'regp' is * set to the register index this element hashes to. */
| 449 | * of the pattern 000..1 of the element hash. As a side effect 'regp' is |
| 450 | * set to the register index this element hashes to. */ |
| 451 | int hllPatLen(unsigned char *ele, size_t elesize, long *regp) { |
| 452 | uint64_t hash, bit, index; |
| 453 | int count; |
| 454 | |
| 455 | /* Count the number of zeroes starting from bit HLL_REGISTERS |
| 456 | * (that is a power of two corresponding to the first bit we don't use |
| 457 | * as index). The max run can be 64-P+1 = Q+1 bits. |
| 458 | * |
| 459 | * Note that the final "1" ending the sequence of zeroes must be |
| 460 | * included in the count, so if we find "001" the count is 3, and |
| 461 | * the smallest count possible is no zeroes at all, just a 1 bit |
| 462 | * at the first position, that is a count of 1. |
| 463 | * |
| 464 | * This may sound like inefficient, but actually in the average case |
| 465 | * there are high probabilities to find a 1 after a few iterations. */ |
| 466 | hash = MurmurHash64A(ele,elesize,0xadc83b19ULL); |
| 467 | index = hash & HLL_P_MASK; /* Register index. */ |
| 468 | hash >>= HLL_P; /* Remove bits used to address the register. */ |
| 469 | hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates |
| 470 | and count will be <= Q+1. */ |
| 471 | bit = 1; |
| 472 | count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */ |
| 473 | while((hash & bit) == 0) { |
| 474 | count++; |
| 475 | bit <<= 1; |
| 476 | } |
| 477 | *regp = (int) index; |
| 478 | return count; |
| 479 | } |
| 480 | |
| 481 | /* ================== Dense representation implementation ================== */ |
| 482 |
no test coverage detected