This function samples the dictionary to return a few keys from random * locations. * * It does not guarantee to return all the keys specified in 'count', nor * it does guarantee to return non-duplicated elements, however it will make * some effort to do both things. * * Returned pointers to hash table entries are stored into 'des' that * points to an array of dictEntry pointers. The array
| 696 | * statistics. However the function is much faster than dictGetRandomKey() |
| 697 | * at producing N elements. */ |
| 698 | unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) { |
| 699 | unsigned long j; /* internal hash table id, 0 or 1. */ |
| 700 | unsigned long tables; /* 1 or 2 tables? */ |
| 701 | unsigned long stored = 0, maxsizemask; |
| 702 | unsigned long maxsteps; |
| 703 | |
| 704 | if (dictSize(d) < count) count = dictSize(d); |
| 705 | maxsteps = count*10; |
| 706 | |
| 707 | /* Try to do a rehashing work proportional to 'count'. */ |
| 708 | for (j = 0; j < count; j++) { |
| 709 | if (dictIsRehashing(d)) |
| 710 | _dictRehashStep(d); |
| 711 | else |
| 712 | break; |
| 713 | } |
| 714 | |
| 715 | tables = dictIsRehashing(d) ? 2 : 1; |
| 716 | maxsizemask = d->ht[0].sizemask; |
| 717 | if (tables > 1 && maxsizemask < d->ht[1].sizemask) |
| 718 | maxsizemask = d->ht[1].sizemask; |
| 719 | |
| 720 | /* Pick a random point inside the larger table. */ |
| 721 | unsigned long i = randomULong() & maxsizemask; |
| 722 | unsigned long emptylen = 0; /* Continuous empty entries so far. */ |
| 723 | while(stored < count && maxsteps--) { |
| 724 | for (j = 0; j < tables; j++) { |
| 725 | /* Invariant of the dict.c rehashing: up to the indexes already |
| 726 | * visited in ht[0] during the rehashing, there are no populated |
| 727 | * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */ |
| 728 | if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) { |
| 729 | /* Moreover, if we are currently out of range in the second |
| 730 | * table, there will be no elements in both tables up to |
| 731 | * the current rehashing index, so we jump if possible. |
| 732 | * (this happens when going from big to small table). */ |
| 733 | if (i >= d->ht[1].size) |
| 734 | i = d->rehashidx; |
| 735 | else |
| 736 | continue; |
| 737 | } |
| 738 | if (i >= d->ht[j].size) continue; /* Out of range for this table. */ |
| 739 | dictEntry *he = d->ht[j].table[i]; |
| 740 | |
| 741 | /* Count contiguous empty buckets, and jump to other |
| 742 | * locations if they reach 'count' (with a minimum of 5). */ |
| 743 | if (he == NULL) { |
| 744 | emptylen++; |
| 745 | if (emptylen >= 5 && emptylen > count) { |
| 746 | i = randomULong() & maxsizemask; |
| 747 | emptylen = 0; |
| 748 | } |
| 749 | } else { |
| 750 | emptylen = 0; |
| 751 | while (he) { |
| 752 | /* Collect all the elements of the buckets found non |
| 753 | * empty while iterating. */ |
| 754 | *des = he; |
| 755 | des++; |
no test coverage detected