| 2447 | |
| 2448 | |
| 2449 | static void zdiffAlgorithm2(zsetopsrc *src, long setnum, zset *dstzset, size_t *maxelelen, size_t *totelelen) { |
| 2450 | /* DIFF Algorithm 2: |
| 2451 | * |
| 2452 | * Add all the elements of the first set to the auxiliary set. |
| 2453 | * Then remove all the elements of all the next sets from it. |
| 2454 | * |
| 2455 | |
| 2456 | * This is O(L + (N-K)log(N)) where L is the sum of all the elements in every |
| 2457 | * set, N is the size of the first set, and K is the size of the result set. |
| 2458 | * |
| 2459 | * Note that from the (L-N) dict searches, (N-K) got to the zsetRemoveFromSkiplist |
| 2460 | * which costs log(N) |
| 2461 | * |
| 2462 | * There is also a O(K) cost at the end for finding the largest element |
| 2463 | * size, but this doesn't change the algorithm complexity since K < L, and |
| 2464 | * O(2L) is the same as O(L). */ |
| 2465 | int j; |
| 2466 | int cardinality = 0; |
| 2467 | zsetopval zval; |
| 2468 | zskiplistNode *znode; |
| 2469 | sds tmp; |
| 2470 | |
| 2471 | for (j = 0; j < setnum; j++) { |
| 2472 | if (zuiLength(&src[j]) == 0) continue; |
| 2473 | |
| 2474 | memset(&zval, 0, sizeof(zval)); |
| 2475 | zuiInitIterator(&src[j]); |
| 2476 | while (zuiNext(&src[j],&zval)) { |
| 2477 | if (j == 0) { |
| 2478 | tmp = zuiNewSdsFromValue(&zval); |
| 2479 | znode = zslInsert(dstzset->zsl,zval.score,tmp); |
| 2480 | dictAdd(dstzset->dict,tmp,&znode->score); |
| 2481 | cardinality++; |
| 2482 | } else { |
| 2483 | tmp = zuiSdsFromValue(&zval); |
| 2484 | if (zsetRemoveFromSkiplist(dstzset, tmp)) { |
| 2485 | cardinality--; |
| 2486 | } |
| 2487 | } |
| 2488 | |
| 2489 | /* Exit if result set is empty as any additional removal |
| 2490 | * of elements will have no effect. */ |
| 2491 | if (cardinality == 0) break; |
| 2492 | } |
| 2493 | zuiClearIterator(&src[j]); |
| 2494 | |
| 2495 | if (cardinality == 0) break; |
| 2496 | } |
| 2497 | |
| 2498 | /* Redize dict if needed after removing multiple elements */ |
| 2499 | if (htNeedsResize(dstzset->dict)) dictResize(dstzset->dict); |
| 2500 | |
| 2501 | /* Using this algorithm, we can't calculate the max element as we go, |
| 2502 | * we have to iterate through all elements to find the max one after. */ |
| 2503 | *maxelelen = zsetDictGetMaxElementLength(dstzset->dict, totelelen); |
| 2504 | } |
| 2505 | |
| 2506 | static int zsetChooseDiffAlgorithm(zsetopsrc *src, long setnum) { |
no test coverage detected