| 1016 | #define SET_OP_INTER 2 |
| 1017 | |
| 1018 | void sunionDiffGenericCommand(client *c, robj **setkeys, int setnum, |
| 1019 | robj *dstkey, int op) { |
| 1020 | robj **sets = (robj**)zmalloc(sizeof(robj*)*setnum, MALLOC_SHARED); |
| 1021 | setTypeIterator *si; |
| 1022 | robj *dstset = NULL; |
| 1023 | sds ele; |
| 1024 | int j, cardinality = 0; |
| 1025 | int diff_algo = 1; |
| 1026 | |
| 1027 | for (j = 0; j < setnum; j++) { |
| 1028 | robj *setobj = dstkey ? |
| 1029 | lookupKeyWrite(c->db,setkeys[j]) : |
| 1030 | lookupKeyRead(c->db,setkeys[j]).unsafe_robjcast(); |
| 1031 | if (!setobj) { |
| 1032 | sets[j] = NULL; |
| 1033 | continue; |
| 1034 | } |
| 1035 | if (checkType(c,setobj,OBJ_SET)) { |
| 1036 | zfree(sets); |
| 1037 | return; |
| 1038 | } |
| 1039 | sets[j] = setobj; |
| 1040 | } |
| 1041 | |
| 1042 | /* Select what DIFF algorithm to use. |
| 1043 | * |
| 1044 | * Algorithm 1 is O(N*M) where N is the size of the element first set |
| 1045 | * and M the total number of sets. |
| 1046 | * |
| 1047 | * Algorithm 2 is O(N) where N is the total number of elements in all |
| 1048 | * the sets. |
| 1049 | * |
| 1050 | * We compute what is the best bet with the current input here. */ |
| 1051 | if (op == SET_OP_DIFF && sets[0]) { |
| 1052 | long long algo_one_work = 0, algo_two_work = 0; |
| 1053 | |
| 1054 | for (j = 0; j < setnum; j++) { |
| 1055 | if (sets[j] == NULL) continue; |
| 1056 | |
| 1057 | algo_one_work += setTypeSize(sets[0]); |
| 1058 | algo_two_work += setTypeSize(sets[j]); |
| 1059 | } |
| 1060 | |
| 1061 | /* Algorithm 1 has better constant times and performs less operations |
| 1062 | * if there are elements in common. Give it some advantage. */ |
| 1063 | algo_one_work /= 2; |
| 1064 | diff_algo = (algo_one_work <= algo_two_work) ? 1 : 2; |
| 1065 | |
| 1066 | if (diff_algo == 1 && setnum > 1) { |
| 1067 | /* With algorithm 1 it is better to order the sets to subtract |
| 1068 | * by decreasing size, so that we are more likely to find |
| 1069 | * duplicated elements ASAP. */ |
| 1070 | qsort(sets+1,setnum-1,sizeof(robj*), |
| 1071 | qsortCompareSetsByRevCardinality); |
| 1072 | } |
| 1073 | } |
| 1074 | |
| 1075 | /* We need a temp set object to store our union. If the dstkey |
no test coverage detected