Add diff_string_lists utility function

Includes a unit test

4 files changed, 449 insertions, 1 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 8eea7ac2d..847e97ad3 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -82,7 +82,8 @@ if HAVE_CHECK
         find_uid-tests \
         auth-tests \
         ipa_ldap_opt-tests \
-        simple_access-tests
+        simple_access-tests \
+        util-tests
 endif
 
 check_PROGRAMS = \
@@ -678,6 +679,17 @@ simple_access_tests_LDADD = \
     $(SSSD_LIBS) \
     $(CHECK_LIBS)
 
+util_tests_SOURCES = \
+    tests/util-tests.c \
+    $(SSSD_UTIL_OBJ)
+util_tests_CFLAGS = \
+    $(AM_CFLAGS) \
+    $(CHECK_CFLAGS)
+util_tests_LDADD = \
+    $(SSSD_LIBS) \
+    $(CHECK_LIBS) \
+    libsss_test_common.la
+
 endif
 
 stress_tests_SOURCES = \
diff --git a/src/tests/util-tests.c b/src/tests/util-tests.c
new file mode 100644
index 000000000..d8d3800fd
--- /dev/null
+++ b/src/tests/util-tests.c
@@ -0,0 +1,227 @@
+/*
+    SSSD
+
+    util-tests.c
+
+    Authors:
+        Stephen Gallagher <sgallagh@redhat.com>
+
+    Copyright (C) 2010 Red Hat
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <popt.h>
+#include <talloc.h>
+#include <check.h>
+#include "util/util.h"
+#include "tests/common.h"
+
+START_TEST(test_diff_string_lists)
+{
+    TALLOC_CTX *test_ctx;
+    char **l1;
+    char **l2;
+    char **l3;
+    char **only_l1;
+    char **only_l2;
+    char **both;
+    int ret;
+
+    test_ctx = talloc_new(NULL);
+
+    /* Test with all values returned */
+    l1 = talloc_array(test_ctx, char *, 4);
+    l1[0] = talloc_strdup(l1, "a");
+    l1[1] = talloc_strdup(l1, "b");
+    l1[2] = talloc_strdup(l1, "c");
+    l1[3] = NULL;
+
+    l2 = talloc_array(test_ctx, char *, 4);
+    l2[0] = talloc_strdup(l1, "d");
+    l2[1] = talloc_strdup(l1, "c");
+    l2[2] = talloc_strdup(l1, "b");
+    l2[3] = NULL;
+
+    ret = diff_string_lists(test_ctx,
+                            l1, l2,
+                            &only_l1, &only_l2, &both);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l1[0], "a") == 0, "Missing \"a\" from only_l1");
+    fail_unless(only_l1[1] == NULL, "only_l1 not NULL-terminated");
+    fail_unless(strcmp(only_l2[0], "d") == 0, "Missing \"d\" from only_l2");
+    fail_unless(only_l2[1] == NULL, "only_l2 not NULL-terminated");
+    fail_unless(strcmp(both[0], "c") == 0, "Missing \"c\" from both");
+    fail_unless(strcmp(both[1], "b") == 0, "Missing \"b\" from both");
+    fail_unless(both[2] == NULL, "both not NULL-terminated");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    /* Test with restricted return values */
+    ret = diff_string_lists(test_ctx,
+                            l1, l2,
+                            &only_l1, &only_l2, NULL);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l1[0], "a") == 0, "Missing \"a\" from only_l1");
+    fail_unless(only_l1[1] == NULL, "only_l1 not NULL-terminated");
+    fail_unless(strcmp(only_l2[0], "d") == 0, "Missing \"d\" from only_l2");
+    fail_unless(only_l2[1] == NULL, "only_l2 not NULL-terminated");
+    fail_unless(both == NULL, "Nothing returned to both");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    ret = diff_string_lists(test_ctx,
+                            l1, l2,
+                            &only_l1, NULL, NULL);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l1[0], "a") == 0, "Missing \"a\" from only_l1");
+    fail_unless(only_l1[1] == NULL, "only_l1 not NULL-terminated");
+    fail_unless(only_l2 == NULL, "Nothing returned to only_l2");
+    fail_unless(both == NULL, "Nothing returned to both");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    ret = diff_string_lists(test_ctx,
+                            l1, l2,
+                            NULL, &only_l2, NULL);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l2[0], "d") == 0, "Missing \"d\" from only_l2");
+    fail_unless(only_l2[1] == NULL, "only_l2 not NULL-terminated");
+    fail_unless(only_l1 == NULL, "Nothing returned to only_l1");
+    fail_unless(both == NULL, "Nothing returned to both");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    /* Test with no overlap */
+    l3 = talloc_array(test_ctx, char *, 4);
+    l3[0] = talloc_strdup(l1, "d");
+    l3[1] = talloc_strdup(l1, "e");
+    l3[2] = talloc_strdup(l1, "f");
+    l3[3] = NULL;
+
+    ret = diff_string_lists(test_ctx,
+                            l1, l3,
+                            &only_l1, &only_l2, &both);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l1[0], "a") == 0, "Missing \"a\" from only_l1");
+    fail_unless(strcmp(only_l1[1], "b") == 0, "Missing \"b\" from only_l1");
+    fail_unless(strcmp(only_l1[2], "c") == 0, "Missing \"c\" from only_l1");
+    fail_unless(only_l1[3] == NULL, "only_l1 not NULL-terminated");
+    fail_unless(strcmp(only_l2[0], "d") == 0, "Missing \"f\" from only_l2");
+    fail_unless(strcmp(only_l2[1], "e") == 0, "Missing \"e\" from only_l2");
+    fail_unless(strcmp(only_l2[2], "f") == 0, "Missing \"d\" from only_l2");
+    fail_unless(only_l2[3] == NULL, "only_l2 not NULL-terminated");
+    fail_unless(both[0] == NULL, "both should have zero entries");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    /* Test with 100% overlap */
+    ret = diff_string_lists(test_ctx,
+                            l1, l1,
+                            &only_l1, &only_l2, &both);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(only_l1[0] == NULL, "only_l1 should have zero entries");
+    fail_unless(only_l2[0] == NULL, "only_l2 should have zero entries");
+    fail_unless(strcmp(both[0], "a") == 0, "Missing \"a\" from both");
+    fail_unless(strcmp(both[1], "b") == 0, "Missing \"b\" from both");
+    fail_unless(strcmp(both[2], "c") == 0, "Missing \"c\" from both");
+    fail_unless(both[3] == NULL, "both is not NULL-terminated");
+
+    talloc_zfree(only_l1);
+    talloc_zfree(only_l2);
+    talloc_zfree(both);
+
+    /* Test with no second list */
+    ret = diff_string_lists(test_ctx,
+                            l1, NULL,
+                            &only_l1, &only_l2, &both);
+
+    fail_unless(ret == EOK, "diff_string_lists returned error [%d]", ret);
+    fail_unless(strcmp(only_l1[0], "a") == 0, "Missing \"a\" from only_l1");
+    fail_unless(strcmp(only_l1[1], "b") == 0, "Missing \"b\" from only_l1");
+    fail_unless(strcmp(only_l1[2], "c") == 0, "Missing \"c\" from only_l1");
+    fail_unless(only_l1[3] == NULL, "only_l1 not NULL-terminated");
+    fail_unless(only_l2[0] == NULL, "only_l2 should have zero entries");
+    fail_unless(both[0] == NULL, "both should have zero entries");
+
+    talloc_free(test_ctx);
+}
+END_TEST
+
+Suite *util_suite(void)
+{
+    Suite *s = suite_create("util");
+
+    TCase *tc_util = tcase_create("util");
+
+    tcase_add_test (tc_util, test_diff_string_lists);
+    tcase_set_timeout(tc_util, 60);
+
+    suite_add_tcase (s, tc_util);
+
+    return s;
+}
+
+int main(int argc, const char *argv[])
+{
+    int opt;
+    int failure_count;
+    poptContext pc;
+    Suite *s = util_suite();
+    SRunner *sr = srunner_create (s);
+
+    struct poptOption long_options[] = {
+        POPT_AUTOHELP
+        SSSD_MAIN_OPTS
+        { NULL }
+    };
+
+    pc = poptGetContext(argv[0], argc, argv, long_options, 0);
+    while((opt = poptGetNextOpt(pc)) != -1) {
+        switch(opt) {
+        default:
+            fprintf(stderr, "\nInvalid option %s: %s\n\n",
+                    poptBadOption(pc, 0), poptStrerror(opt));
+            poptPrintUsage(pc, stderr, 0);
+            return 1;
+        }
+    }
+    poptFreeContext(pc);
+
+    tests_set_cwd();
+
+    srunner_run_all(sr, CK_ENV);
+    failure_count = srunner_ntests_failed (sr);
+    srunner_free (sr);
+    if (failure_count == 0) {
+        return EXIT_SUCCESS;
+    }
+    return  EXIT_FAILURE;
+}
diff --git a/src/util/util.c b/src/util/util.c
index 9a9731222..206984c7a 100644
--- a/src/util/util.c
+++ b/src/util/util.c
@@ -22,6 +22,7 @@
 
 #include "talloc.h"
 #include "util/util.h"
+#include "dhash.h"
 
 /* split a string into an allocated array of strings.
  * the separator is a string, and is case-sensitive.
@@ -235,3 +236,198 @@ fail:
     free_args(ret);
     return NULL;
 }
+
+
+
+/* Take two string lists (terminated on a NULL char*)
+ * and return up to three arrays of strings based on
+ * shared ownership.
+ *
+ * Pass NULL to any return type you don't care about
+ */
+errno_t diff_string_lists(TALLOC_CTX *memctx,
+                          char **_list1,
+                          char **_list2,
+                          char ***_list1_only,
+                          char ***_list2_only,
+                          char ***_both_lists)
+{
+    int error;
+    errno_t ret;
+    int i;
+    int i2 = 0;
+    int i12 = 0;
+    hash_table_t *table;
+    hash_key_t key;
+    hash_value_t value;
+    char **list1 = NULL;
+    char **list2 = NULL;
+    char **list1_only = NULL;
+    char **list2_only = NULL;
+    char **both_lists = NULL;
+    unsigned long count;
+    hash_key_t *keys;
+
+    TALLOC_CTX *tmp_ctx = talloc_new(memctx);
+    if (!tmp_ctx) {
+        return ENOMEM;
+    }
+
+    if (!_list1) {
+        list1 = talloc_array(tmp_ctx, char *, 1);
+        if (!list1) {
+            talloc_free(tmp_ctx);
+            return ENOMEM;
+        }
+        list1[0] = NULL;
+    }
+    else {
+        list1 = _list1;
+    }
+
+    if (!_list2) {
+        list2 = talloc_array(tmp_ctx, char *, 1);
+        if (!list2) {
+            talloc_free(tmp_ctx);
+            return ENOMEM;
+        }
+        list2[0] = NULL;
+    }
+    else {
+        list2 = _list2;
+    }
+
+    error = hash_create(10, &table, NULL, NULL);
+    if (error != HASH_SUCCESS) {
+        talloc_free(tmp_ctx);
+        return EIO;
+    }
+
+    key.type = HASH_KEY_STRING;
+    value.type = HASH_VALUE_UNDEF;
+
+    /* Add all entries from list 1 into a hash table */
+    i = 0;
+    while (list1[i]) {
+        key.str = talloc_strdup(tmp_ctx, list1[i]);
+        error = hash_enter(table, &key, &value);
+        if (error != HASH_SUCCESS) {
+            ret = EIO;
+            goto done;
+        }
+        i++;
+    }
+
+    /* Iterate through list 2 and remove matching items */
+    i = 0;
+    while (list2[i]) {
+        key.str = talloc_strdup(tmp_ctx, list2[i]);
+        error = hash_delete(table, &key);
+        if (error == HASH_SUCCESS) {
+            if (_both_lists) {
+                /* String was present in both lists */
+                i12++;
+                both_lists = talloc_realloc(tmp_ctx, both_lists, char *, i12+1);
+                if (!both_lists) {
+                    ret = ENOMEM;
+                    goto done;
+                }
+                both_lists[i12-1] = talloc_strdup(both_lists, list2[i]);
+                if (!both_lists[i12-1]) {
+                    ret = ENOMEM;
+                    goto done;
+                }
+
+                both_lists[i12] = NULL;
+            }
+        }
+        else if (error == HASH_ERROR_KEY_NOT_FOUND) {
+            if (_list2_only) {
+                /* String was present only in list2 */
+                i2++;
+                list2_only = talloc_realloc(tmp_ctx, list2_only,
+                                            char *, i2+1);
+                if (!list2_only) {
+                    ret = ENOMEM;
+                    goto done;
+                }
+                list2_only[i2-1] = talloc_strdup(list2_only, list2[i]);
+                if (!list2_only[i2-1]) {
+                    ret = ENOMEM;
+                    goto done;
+                }
+
+                list2_only[i2] = NULL;
+            }
+        }
+        else {
+            /* An error occurred */
+            ret = EIO;
+            goto done;
+        }
+        i++;
+    }
+
+    /* Get the leftover entries in the hash table */
+    if (_list1_only) {
+        error = hash_keys(table, &count, &keys);
+        if (error != HASH_SUCCESS) {
+            ret = EIO;
+            goto done;
+        }
+
+        list1_only = talloc_array(tmp_ctx, char *, count+1);
+        if (!list1_only) {
+            ret = ENOMEM;
+            goto done;
+        }
+
+        for (i = 0; i < count; i++) {
+            list1_only[i] = talloc_strdup(list1_only, keys[i].str);
+            if (!list1_only[i]) {
+                ret = ENOMEM;
+                goto done;
+            }
+        }
+        list1_only[count] = NULL;
+
+        free(keys);
+
+        *_list1_only = talloc_steal(memctx, list1_only);
+    }
+
+    if (_list2_only) {
+        if (list2_only) {
+            *_list2_only = talloc_steal(memctx, list2_only);
+        }
+        else {
+            *_list2_only = talloc_array(memctx, char *, 1);
+            if (!(*_list2_only)) {
+                ret = ENOMEM;
+                goto done;
+            }
+            *_list2_only[0] = NULL;
+        }
+    }
+
+    if (_both_lists) {
+        if (both_lists) {
+            *_both_lists = talloc_steal(memctx, both_lists);
+        }
+        else {
+            *_both_lists = talloc_array(memctx, char *, 1);
+            if (!(*_both_lists)) {
+                ret = ENOMEM;
+                goto done;
+            }
+            *_both_lists[0] = NULL;
+        }
+    }
+
+    ret = EOK;
+
+done:
+    hash_destroy(table);
+    talloc_free(tmp_ctx);
+    return ret;
+}
diff --git a/src/util/util.h b/src/util/util.h
index 3c95f7a20..da92ae68c 100644
--- a/src/util/util.h
+++ b/src/util/util.h
@@ -331,4 +331,17 @@ int split_on_separator(TALLOC_CTX *mem_ctx, const char *str,
                        const char sep, bool trim, char ***_list, int *size);
 
 char **parse_args(const char *str);
+
+/* Take two string lists (terminated on a NULL char*)
+ * and return up to three arrays of strings based on
+ * shared ownership.
+ *
+ * Pass NULL to any return type you don't care about
+ */
+errno_t diff_string_lists(TALLOC_CTX *memctx,
+                          char **string1,
+                          char **string2,
+                          char ***string1_only,
+                          char ***string2_only,
+                          char ***both_strings);
 #endif /* __SSSD_UTIL_H__ */