From ab4685070515230c9aa64f9e69eec7fc061ee8d7 Mon Sep 17 00:00:00 2001 From: "Rafael G. Martins" Date: Fri, 26 Apr 2019 19:18:11 +0200 Subject: common: added bc_slist_sort --- .gitignore | 1 + Makefile.am | 20 +++++++ src/common/sort.c | 44 ++++++++++++++ src/common/sort.h | 18 ++++++ tests/common/check_sort.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 230 insertions(+) create mode 100644 src/common/sort.c create mode 100644 src/common/sort.h create mode 100644 tests/common/check_sort.c 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 + * + * This program can be distributed under the terms of the BSD License. + * See the file LICENSE. + */ + +#include +#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 + * + * 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 + * + * This program can be distributed under the terms of the BSD License. + * See the file LICENSE. + */ + +#include +#include +#include +#include +#include +#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); +} -- cgit v1.2.3-18-g5258