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
| 1058 | * statistics. However the function is much faster than dictGetRandomKey() |
| 1059 | * at producing N elements. */ |
| 1060 | unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) { |
| 1061 | unsigned long j; /* internal hash table id, 0 or 1. */ |
| 1062 | unsigned long tables; /* 1 or 2 tables? */ |
| 1063 | unsigned long stored = 0, maxsizemask; |
| 1064 | unsigned long maxsteps; |
| 1065 | |
| 1066 | if (dictSize(d) < count) count = dictSize(d); |
| 1067 | maxsteps = count*10; |
| 1068 | |
| 1069 | /* Try to do a rehashing work proportional to 'count'. */ |
| 1070 | for (j = 0; j < count; j++) { |
| 1071 | if (dictIsRehashing(d)) |
| 1072 | _dictRehashStep(d); |
| 1073 | else |
| 1074 | break; |
| 1075 | } |
| 1076 | |
| 1077 | tables = dictIsRehashing(d) ? 2 : 1; |
| 1078 | maxsizemask = d->ht[0].sizemask; |
| 1079 | if (tables > 1 && maxsizemask < d->ht[1].sizemask) |
| 1080 | maxsizemask = d->ht[1].sizemask; |
| 1081 | |
| 1082 | /* Pick a random point inside the larger table. */ |
| 1083 | unsigned long i = randomULong() & maxsizemask; |
| 1084 | unsigned long emptylen = 0; /* Continuous empty entries so far. */ |
| 1085 | while(stored < count && maxsteps--) { |
| 1086 | for (j = 0; j < tables; j++) { |
| 1087 | /* Invariant of the dict.c rehashing: up to the indexes already |
| 1088 | * visited in ht[0] during the rehashing, there are no populated |
| 1089 | * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */ |
| 1090 | if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) { |
| 1091 | /* Moreover, if we are currently out of range in the second |
| 1092 | * table, there will be no elements in both tables up to |
| 1093 | * the current rehashing index, so we jump if possible. |
| 1094 | * (this happens when going from big to small table). */ |
| 1095 | if (i >= d->ht[1].size) |
| 1096 | i = d->rehashidx; |
| 1097 | else |
| 1098 | continue; |
| 1099 | } |
| 1100 | if (i >= d->ht[j].size) continue; /* Out of range for this table. */ |
| 1101 | dictEntry *he = d->ht[j].table[i]; |
| 1102 | |
| 1103 | /* Count contiguous empty buckets, and jump to other |
| 1104 | * locations if they reach 'count' (with a minimum of 5). */ |
| 1105 | if (he == NULL) { |
| 1106 | emptylen++; |
| 1107 | if (emptylen >= 5 && emptylen > count) { |
| 1108 | i = randomULong() & maxsizemask; |
| 1109 | emptylen = 0; |
| 1110 | } |
| 1111 | } else { |
| 1112 | emptylen = 0; |
| 1113 | while (he) { |
| 1114 | /* Collect all the elements of the buckets found non |
| 1115 | * empty while iterating. */ |
| 1116 | *des = he; |
| 1117 | des++; |
no test coverage detected