common: added bc_slist_sort

5 files changed, 230 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index 299f37f..e97005c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -81,6 +81,7 @@ blogc*.html
 /tests/blogc-runserver/check_mime
 /tests/common/check_config_parser
 /tests/common/check_error
+/tests/common/check_sort
 /tests/common/check_stdin
 /tests/common/check_utf8
 /tests/common/check_utils
diff --git a/Makefile.am b/Makefile.am
index b136f9f..12f9036 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -69,6 +69,7 @@ noinst_HEADERS = \
 	src/common/config-parser.h \
 	src/common/error.h \
 	src/common/file.h \
+	src/common/sort.h \
 	src/common/stdin.h \
 	src/common/utf8.h \
 	src/common/utils.h \
@@ -151,6 +152,7 @@ libblogc_common_la_SOURCES = \
 	src/common/config-parser.c \
 	src/common/error.c \
 	src/common/file.c \
+	src/common/sort.c \
 	src/common/stdin.c \
 	src/common/utf8.c \
 	src/common/utils.c \
@@ -472,6 +474,7 @@ check_PROGRAMS += \
 	tests/blogc/check_template_parser \
 	tests/common/check_config_parser \
 	tests/common/check_error \
+	tests/common/check_sort \
 	tests/common/check_utf8 \
 	tests/common/check_utils \
 	$(NULL)
@@ -746,6 +749,23 @@ tests_common_check_error_LDADD = \
 	libblogc_common.la \
 	$(NULL)
 
+tests_common_check_sort_SOURCES = \
+	tests/common/check_sort.c \
+	$(NULL)
+
+tests_common_check_sort_CFLAGS = \
+	$(CMOCKA_CFLAGS) \
+	$(NULL)
+
+tests_common_check_sort_LDFLAGS = \
+	-no-install \
+	$(NULL)
+
+tests_common_check_sort_LDADD = \
+	$(CMOCKA_LIBS) \
+	libblogc_common.la \
+	$(NULL)
+
 tests_common_check_utf8_SOURCES = \
 	tests/common/check_utf8.c \
 	$(NULL)
diff --git a/src/common/sort.c b/src/common/sort.c
new file mode 100644
index 0000000..3e24706
--- /dev/null
+++ b/src/common/sort.c
@@ -0,0 +1,44 @@
+/*
+ * blogc: A blog compiler.
+ * Copyright (C) 2014-2019 Rafael G. Martins <rafael@rafaelmartins.eng.br>
+ *
+ * This program can be distributed under the terms of the BSD License.
+ * See the file LICENSE.
+ */
+
+#include <stdbool.h>
+#include "utils.h"
+#include "sort.h"
+
+
+bc_slist_t*
+bc_slist_sort(bc_slist_t *l, bc_sort_func_t cmp)
+{
+    if (l == NULL) {
+        return NULL;
+    }
+
+    bool swapped = false;
+    bc_slist_t *lptr = NULL;
+    bc_slist_t *rptr = NULL;
+
+    do {
+        swapped = false;
+        lptr = l;
+
+        while (lptr->next != rptr) {
+            if (0 < cmp(lptr->data, lptr->next->data)) {
+                void *tmp = lptr->data;
+                lptr->data = lptr->next->data;
+                lptr->next->data = tmp;
+                swapped = true;
+            }
+
+            lptr = lptr->next;
+        }
+
+        rptr = lptr;
+    } while(swapped);
+
+    return l;
+}
diff --git a/src/common/sort.h b/src/common/sort.h
new file mode 100644
index 0000000..9f4dda2
--- /dev/null
+++ b/src/common/sort.h
@@ -0,0 +1,18 @@
+/*
+ * blogc: A blog compiler.
+ * Copyright (C) 2014-2019 Rafael G. Martins <rafael@rafaelmartins.eng.br>
+ *
+ * This program can be distributed under the terms of the BSD License.
+ * See the file LICENSE.
+ */
+
+#ifndef _SORT_H
+#define _SORT_H
+
+#include "utils.h"
+
+typedef int (*bc_sort_func_t) (const void *a, const void *b);
+
+bc_slist_t* bc_slist_sort(bc_slist_t *l, bc_sort_func_t cmp);
+
+#endif /* _SORT_H */
diff --git a/tests/common/check_sort.c b/tests/common/check_sort.c
new file mode 100644
index 0000000..3c4764f
--- /dev/null
+++ b/tests/common/check_sort.c
@@ -0,0 +1,147 @@
+/*
+ * blogc: A blog compiler.
+ * Copyright (C) 2014-2019 Rafael G. Martins <rafael@rafaelmartins.eng.br>
+ *
+ * This program can be distributed under the terms of the BSD License.
+ * See the file LICENSE.
+ */
+
+#include <stdarg.h>
+#include <stddef.h>
+#include <setjmp.h>
+#include <cmocka.h>
+#include <stdlib.h>
+#include "../../src/common/utils.h"
+#include "../../src/common/sort.h"
+
+
+static int
+sort_func(void *a, void *b)
+{
+    return strcmp((char*) a, (char*) b);
+}
+
+
+static void
+test_slist_sort_empty(void **state)
+{
+    bc_slist_t *l = NULL;
+    assert_null(bc_slist_sort(l, sort_func));
+}
+
+
+static void
+test_slist_sort_single(void **state)
+{
+    bc_slist_t *l = NULL;
+    l = bc_slist_append(l, bc_strdup("a"));
+
+    l = bc_slist_sort(l, sort_func);
+
+    assert_non_null(l);
+    assert_string_equal(l->data, "a");
+    assert_null(l->next);
+
+    bc_slist_free_full(l, free);
+}
+
+
+static void
+test_slist_sort_sorted(void **state)
+{
+    bc_slist_t *l = NULL;
+    l = bc_slist_append(l, bc_strdup("a"));
+    l = bc_slist_append(l, bc_strdup("b"));
+    l = bc_slist_append(l, bc_strdup("c"));
+
+    l = bc_slist_sort(l, sort_func);
+
+    assert_non_null(l);
+    assert_string_equal(l->data, "a");
+    assert_string_equal(l->next->data, "b");
+    assert_string_equal(l->next->next->data, "c");
+    assert_null(l->next->next->next);
+
+    bc_slist_free_full(l, free);
+}
+
+
+static void
+test_slist_sort_reverse(void **state)
+{
+    bc_slist_t *l = NULL;
+    l = bc_slist_append(l, bc_strdup("d"));
+    l = bc_slist_append(l, bc_strdup("c"));
+    l = bc_slist_append(l, bc_strdup("b"));
+    l = bc_slist_append(l, bc_strdup("a"));
+
+    l = bc_slist_sort(l, sort_func);
+
+    assert_non_null(l);
+    assert_string_equal(l->data, "a");
+    assert_string_equal(l->next->data, "b");
+    assert_string_equal(l->next->next->data, "c");
+    assert_string_equal(l->next->next->next->data, "d");
+    assert_null(l->next->next->next->next);
+
+    bc_slist_free_full(l, free);
+}
+
+
+static void
+test_slist_sort_mixed1(void **state)
+{
+    bc_slist_t *l = NULL;
+    l = bc_slist_append(l, bc_strdup("a"));
+    l = bc_slist_append(l, bc_strdup("d"));
+    l = bc_slist_append(l, bc_strdup("c"));
+    l = bc_slist_append(l, bc_strdup("b"));
+
+    l = bc_slist_sort(l, sort_func);
+
+    assert_non_null(l);
+    assert_string_equal(l->data, "a");
+    assert_string_equal(l->next->data, "b");
+    assert_string_equal(l->next->next->data, "c");
+    assert_string_equal(l->next->next->next->data, "d");
+    assert_null(l->next->next->next->next);
+
+    bc_slist_free_full(l, free);
+}
+
+
+static void
+test_slist_sort_mixed2(void **state)
+{
+    bc_slist_t *l = NULL;
+    l = bc_slist_append(l, bc_strdup("c"));
+    l = bc_slist_append(l, bc_strdup("b"));
+    l = bc_slist_append(l, bc_strdup("a"));
+    l = bc_slist_append(l, bc_strdup("d"));
+
+    l = bc_slist_sort(l, sort_func);
+
+    assert_non_null(l);
+    assert_string_equal(l->data, "a");
+    assert_string_equal(l->next->data, "b");
+    assert_string_equal(l->next->next->data, "c");
+    assert_string_equal(l->next->next->next->data, "d");
+    assert_null(l->next->next->next->next);
+
+    bc_slist_free_full(l, free);
+}
+
+
+int
+main(void)
+{
+    const UnitTest tests[] = {
+        unit_test(test_slist_sort_empty),
+        unit_test(test_slist_sort_single),
+        unit_test(test_slist_sort_sorted),
+        unit_test(test_slist_sort_reverse),
+        unit_test(test_slist_sort_mixed1),
+        unit_test(test_slist_sort_mixed2),
+    };
+    return run_tests(tests);
+}