diff options
| -rw-r--r-- | bench/libdimension/list.c | 1 | ||||
| -rw-r--r-- | libdimension/list.c | 34 | ||||
| -rw-r--r-- | tests/libdimension/Makefile.am | 4 | ||||
| -rw-r--r-- | tests/libdimension/list.c | 75 |
4 files changed, 105 insertions, 9 deletions
diff --git a/bench/libdimension/list.c b/bench/libdimension/list.c index b177d47..be75aa1 100644 --- a/bench/libdimension/list.c +++ b/bench/libdimension/list.c @@ -61,6 +61,7 @@ main(void) for (size_t i = 0; i < count; ++i) { sandglass_bench_noprecache(&sandglass, dmnsn_list_push(list, &object)); + ++object; printf(" %ld", sandglass.grains); } printf("\n"); diff --git a/libdimension/list.c b/libdimension/list.c index 421a56e..3eaaa12 100644 --- a/libdimension/list.c +++ b/libdimension/list.c @@ -56,8 +56,8 @@ void dmnsn_delete_list(dmnsn_list *list) { if (list) { - while (list->first) { - dmnsn_list_remove(list, list->first); + while (dmnsn_list_first(list)) { + dmnsn_list_remove(list, dmnsn_list_first(list)); } dmnsn_free(list); } @@ -97,23 +97,39 @@ dmnsn_list_split(dmnsn_list *list) void dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator) { - /* Recursive merge sort */ if (dmnsn_list_size(list) < 2) { return; - } else if (dmnsn_list_size(list) == 2) { - if ((*comparator)(list->last, list->first)) { - dmnsn_list_swap(list->first, list->last); - } + } else if (dmnsn_list_size(list) <= 16) { + /* Use insertion sort on small lists */ + dmnsn_list_iterator *current = dmnsn_list_next(dmnsn_list_first(list)); + do { + dmnsn_list_iterator *next = dmnsn_list_next(current); + dmnsn_list_iterator_remove(list, current); + + dmnsn_list_iterator *i = next; + do { + dmnsn_list_iterator *prev = i ? dmnsn_list_prev(i) + : dmnsn_list_last(list); + if (!(*comparator)(current, prev)) + break; + i = prev; + } while (i != dmnsn_list_first(list)); + dmnsn_list_iterator_insert(list, i, current); + + current = next; + } while (current); } else { + /* Recursive merge sort */ dmnsn_list half; dmnsn_list_split_impl(list, &half); dmnsn_list_sort(list, comparator); dmnsn_list_sort(&half, comparator); - dmnsn_list_iterator *i = list->first, *j = half.first; + dmnsn_list_iterator *i = dmnsn_list_first(list); + dmnsn_list_iterator *j = dmnsn_list_first(&half); while (i || j) { if (!i) { - j->prev = list->last; + j->prev = dmnsn_list_last(list); list->last->next = j; list->last = half.last; list->length += half.length; 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 <tavianator@gmail.com> * + * * + * 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 <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/* + * Basic tests of linked lists + */ + +#include "dimension.h" +#include <stdio.h> +#include <stdlib.h> + +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; +} |