From 403678ce69d3992fbe72bd3cf9030eec67aaaed8 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 28 Jan 2011 16:11:13 -0500 Subject: Use insertion sort for small lists, new list test. --- tests/libdimension/Makefile.am | 4 +++ tests/libdimension/list.c | 75 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+) create mode 100644 tests/libdimension/list.c (limited to 'tests/libdimension') diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am index 4dbe761..651fbaa 100644 --- a/tests/libdimension/Makefile.am +++ b/tests/libdimension/Makefile.am @@ -22,6 +22,7 @@ INCLUDES = -I$(top_srcdir)/libdimension check_LTLIBRARIES = libdimension-tests.la check_PROGRAMS = error-test \ warning-test \ + list-test \ polynomial-test \ prtree-test \ png-test \ @@ -60,6 +61,9 @@ error_test_LDADD = libdimension-tests.la warning_test_SOURCES = warning.c warning_test_LDADD = libdimension-tests.la +list_test_SOURCES = list.c +list_test_LDADD = libdimension-tests.la + polynomial_test_SOURCES = polynomial.c polynomial_test_LDADD = libdimension-tests.la diff --git a/tests/libdimension/list.c b/tests/libdimension/list.c new file mode 100644 index 0000000..6a98fda --- /dev/null +++ b/tests/libdimension/list.c @@ -0,0 +1,75 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * This file is part of The Dimension Test Suite. * + * * + * The Dimension Test Suite 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. * + * * + * The Dimension Test Suite 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 . * + *************************************************************************/ + +/* + * Basic tests of linked lists + */ + +#include "dimension.h" +#include +#include + +typedef struct dmnsn_item { + int value; + size_t seq; +} dmnsn_item; + +static bool +dmnsn_comparator(const dmnsn_list_iterator *i, const dmnsn_list_iterator *j) +{ + dmnsn_item *a = dmnsn_list_at(i), *b = dmnsn_list_at(j); + return a->value < b->value; +} + +int +main() +{ + dmnsn_list *list = dmnsn_new_list(sizeof(dmnsn_item)); + + /* Fill up the list with random numbers */ + srand(1); + const size_t list_size = 10000; + for (size_t i = 0; i < list_size; ++i) { + dmnsn_item item; + item.value = rand()%(list_size/10); + item.seq = i; + dmnsn_list_push(list, &item); + } + + /* Ensure that sorting works */ + dmnsn_list_sort(list, &dmnsn_comparator); + for (dmnsn_list_iterator *i = dmnsn_list_first(list); + i != dmnsn_list_last(list); + i = dmnsn_list_next(i)) + { + dmnsn_item *a = dmnsn_list_at(i), *b = dmnsn_list_at(dmnsn_list_next(i)); + if (a->value > b->value) { + fprintf(stderr, "--- Sorting failed (%d > %d)! ---\n", + a->value, b->value); + return EXIT_FAILURE; + } else if (a->value == b->value && a->seq > b->seq) { + fprintf(stderr, "--- Sorting was unstable (%zu > %zu)! ---\n", + a->seq, b->seq); + return EXIT_FAILURE; + } + } + + dmnsn_delete_list(list); + return EXIT_SUCCESS; +} -- cgit v1.2.3