summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2011-05-10 13:20:49 -0600
committerTavian Barnes <tavianator@gmail.com>2011-05-10 13:20:49 -0600
commitccc143b9ed802f5b0aa3069423227972de039ba5 (patch)
tree461fe5a7cd94a525f93a188aaa6c927a01be3a83
parent3901e4f0e87665dbf8d622295adf45ba94832927 (diff)
downloaddimension-ccc143b9ed802f5b0aa3069423227972de039ba5.tar.xz
Use arrays for PR-tree construction instead of lists.
-rw-r--r--bench/libdimension/Makefile.am3
-rw-r--r--bench/libdimension/list.c136
-rw-r--r--libdimension/Makefile.am2
-rw-r--r--libdimension/dimension.h1
-rw-r--r--libdimension/dimension/array.h55
-rw-r--r--libdimension/dimension/list.h357
-rw-r--r--libdimension/list.c166
-rw-r--r--libdimension/prtree.c248
-rw-r--r--tests/libdimension/Makefile.am4
-rw-r--r--tests/libdimension/list.c78
10 files changed, 169 insertions, 881 deletions
diff --git a/bench/libdimension/Makefile.am b/bench/libdimension/Makefile.am
index 0f64e5b..353acb3 100644
--- a/bench/libdimension/Makefile.am
+++ b/bench/libdimension/Makefile.am
@@ -20,7 +20,6 @@
INCLUDES = -I$(top_srcdir)/libdimension
EXTRA_PROGRAMS = bench-array \
- bench-list \
bench-geometry \
bench-polynomial \
bench-prtree
@@ -29,14 +28,12 @@ AM_CFLAGS = $(libsandglass_CFLAGS) -fno-inline
AM_LDFLAGS = $(libsandglass_LIBS) $(top_builddir)/libdimension/libdimension.la
bench_array_SOURCES = array.c
-bench_list_SOURCES = list.c
bench_geometry_SOURCES = geometry.c
bench_polynomial_SOURCES = polynomial.c
bench_prtree_SOURCES = prtree.c
bench: $(EXTRA_PROGRAMS)
./bench-array
- ./bench-list
./bench-geometry
./bench-polynomial
./bench-prtree
diff --git a/bench/libdimension/list.c b/bench/libdimension/list.c
deleted file mode 100644
index e00b510..0000000
--- a/bench/libdimension/list.c
+++ /dev/null
@@ -1,136 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2009-2011 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * This file is part of The Dimension Benchmark Suite. *
- * *
- * The Dimension Benchmark 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 Benchmark 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/>. *
- *************************************************************************/
-
-#include "dimension.h"
-#include <sandglass.h>
-#include <stdbool.h>
-#include <stdlib.h>
-#include <stdint.h>
-
-static bool
-dmnsn_comparator(const dmnsn_list_iterator *i, const dmnsn_list_iterator *j)
-{
- uint32_t *a, *b;
- a = dmnsn_list_at(i);
- b = dmnsn_list_at(j);
- return *a < *b;
-}
-
-int
-main(void)
-{
- const size_t count = 32;
- uint32_t object = 1;
-
- sandglass_t sandglass;
- if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
- perror("sandglass_create()");
- return EXIT_FAILURE;
- }
-
- /* Benchmark allocation and deallocation */
- dmnsn_list *list;
- sandglass_bench_fine(&sandglass, {
- list = dmnsn_new_list(sizeof(object));
- dmnsn_delete_list(list);
- });
- printf("dmnsn_new_list() + dmnsn_delete_list(): %ld\n", sandglass.grains);
-
- /* Create our test list */
- list = dmnsn_new_list(sizeof(object));
-
- /* dmnsn_list_push() */
-
- printf("dmnsn_list_push():");
-
- for (size_t i = 0; i < count; ++i) {
- sandglass_bench_noprecache(&sandglass, dmnsn_list_push(list, &object));
- ++object;
- printf(" %ld", sandglass.grains);
- }
- printf("\n");
-
- /* dmnsn_list_first() */
- dmnsn_list_iterator *ii;
- sandglass_bench_fine(&sandglass, ii = dmnsn_list_first(list));
- printf("dmnsn_list_first(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_last() */
- sandglass_bench_fine(&sandglass, ii = dmnsn_list_last(list));
- printf("dmnsn_list_last(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_get() */
- sandglass_bench_fine(&sandglass, dmnsn_list_get(ii, &object));
- printf("dmnsn_list_get(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_set() */
- sandglass_bench_fine(&sandglass, dmnsn_list_set(ii, &object));
- printf("dmnsn_list_set(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_size() */
- size_t size;
- sandglass_bench_fine(&sandglass, size = dmnsn_list_size(list));
- printf("dmnsn_list_size() = %zu: %ld\n", size, sandglass.grains);
-
- /* dmnsn_list_insert() */
-
- printf("dmnsn_list_insert():");
-
- for (size_t i = 0; i < count; ++i) {
- sandglass_bench_noprecache(&sandglass,
- dmnsn_list_insert(list, ii, &object));
- printf(" %ld", sandglass.grains);
- }
- printf("\n");
-
- /* dmnsn_list_split() */
- dmnsn_list *split;
- sandglass_bench_noprecache(&sandglass, split = dmnsn_list_split(list));
- printf("dmnsn_list_split(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_sort() */
- sandglass_bench(&sandglass, dmnsn_list_sort(list, dmnsn_comparator));
- printf("dmnsn_list_sort(): %ld\n", sandglass.grains);
-
- /* dmnsn_list_remove() */
-
- printf("dmnsn_list_remove():");
-
- for (size_t i = 0; i < count; ++i) {
- ii = dmnsn_list_last(split);
- sandglass_bench_noprecache(&sandglass,
- dmnsn_list_remove(split, ii));
- printf(" %ld", sandglass.grains);
- }
- printf("\n");
-
- /* dmnsn_list_pop() */
-
- printf("dmnsn_list_pop():");
-
- for (size_t i = 0; i < count; ++i) {
- sandglass_bench_noprecache(&sandglass, dmnsn_list_pop(list, &object));
- printf(" %ld", sandglass.grains);
- }
- printf("\n");
-
- dmnsn_delete_list(split);
- dmnsn_delete_list(list);
- return EXIT_SUCCESS;
-}
diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 3622f08..4d4f58e 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -37,7 +37,6 @@ nobase_include_HEADERS = dimension.h \
dimension/interior.h \
dimension/light.h \
dimension/lights.h \
- dimension/list.h \
dimension/malloc.h \
dimension/map.h \
dimension/object.h \
@@ -80,7 +79,6 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \
inline.c \
interior.c \
light.c \
- list.c \
malloc.c \
map.c \
object.c \
diff --git a/libdimension/dimension.h b/libdimension/dimension.h
index bd055fc..3f0ea57 100644
--- a/libdimension/dimension.h
+++ b/libdimension/dimension.h
@@ -78,7 +78,6 @@ typedef void dmnsn_free_fn(void *ptr);
#include <dimension/error.h>
#include <dimension/malloc.h>
#include <dimension/array.h>
-#include <dimension/list.h>
#include <dimension/dictionary.h>
#include <dimension/progress.h>
#include <dimension/timer.h>
diff --git a/libdimension/dimension/array.h b/libdimension/dimension/array.h
index 51830e7..18affd7 100644
--- a/libdimension/dimension/array.h
+++ b/libdimension/dimension/array.h
@@ -27,7 +27,8 @@
#define DIMENSION_ARRAY_H
#include <stddef.h> /* For size_t */
-#include <string.h> /* For memcpy */
+#include <stdlib.h> /* For qsort() */
+#include <string.h> /* For memcpy() */
/** Dynamic array type. */
typedef struct dmnsn_array {
@@ -98,6 +99,38 @@ dmnsn_array_resize(dmnsn_array *array, size_t length)
}
/**
+ * Copy an array.
+ * @param[in] array The array to copy.
+ * @return A copy of the array.
+ */
+DMNSN_INLINE dmnsn_array *
+dmnsn_array_copy(const dmnsn_array *array)
+{
+ dmnsn_array *copy = dmnsn_new_array(array->obj_size);
+ dmnsn_array_resize(copy, dmnsn_array_size(array));
+ memcpy(copy->ptr, array->ptr, dmnsn_array_size(array)*array->obj_size);
+ return copy;
+}
+
+/**
+ * Split an array in half.
+ * @param[in,out] array The array to split.
+ * @return The second half of the array.
+ */
+DMNSN_INLINE dmnsn_array *
+dmnsn_array_split(dmnsn_array *array)
+{
+ dmnsn_array *half = dmnsn_new_array(array->obj_size);
+ size_t new_size = dmnsn_array_size(array)/2;
+ size_t old_size = dmnsn_array_size(array) - new_size;
+ dmnsn_array_resize(half, new_size);
+ memcpy(half->ptr, (char *)array->ptr + old_size*array->obj_size,
+ new_size*array->obj_size);
+ dmnsn_array_resize(array, old_size);
+ return half;
+}
+
+/**
* Get the i'th element.
* @param[in] array The array to access.
* @param[in] i The index of the element to extract.
@@ -240,6 +273,26 @@ dmnsn_array_apply(dmnsn_array *array, dmnsn_callback_fn *callback)
}
}
+/**
+ * Callback type for array sorting.
+ * @param[in] a The first element.
+ * @param[in] b The second element.
+ * @return A negative value iff a < b, zero iff a == b, and a positive value iff
+ * a > b.
+ */
+typedef int dmnsn_array_comparator_fn(const void *a, const void *b);
+
+/**
+ * Sort an array.
+ * @param[in,out] array The array to sort.
+ * @param[in] comparator The sorting comparator to use.
+ */
+DMNSN_INLINE void
+dmnsn_array_sort(dmnsn_array *array, dmnsn_array_comparator_fn *comparator)
+{
+ qsort(array->ptr, dmnsn_array_size(array), array->obj_size, comparator);
+}
+
/* Macros to shorten array iteration */
/**
diff --git a/libdimension/dimension/list.h b/libdimension/dimension/list.h
deleted file mode 100644
index 70c944c..0000000
--- a/libdimension/dimension/list.h
+++ /dev/null
@@ -1,357 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * This file is part of The Dimension Library. *
- * *
- * The Dimension Library is free software; you can redistribute it and/ *
- * or modify it under the terms of the GNU Lesser 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 Library 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 *
- * Lesser General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this program. If not, see *
- * <http://www.gnu.org/licenses/>. *
- *************************************************************************/
-
-/**
- * @file
- * Simple doubly-linked lists.
- */
-
-#ifndef DIMENSION_LIST_H
-#define DIMENSION_LIST_H
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-
-/**
- * A list iterator.
- */
-typedef struct dmnsn_list_iterator {
- void *ptr; /**< @internal The stored object. */
- size_t obj_size; /**< @internal The object size. */
- struct dmnsn_list_iterator *prev; /**< @internal The previous iterator. */
- struct dmnsn_list_iterator *next; /**< @internal The next iterator. */
-} dmnsn_list_iterator;
-
-/**
- * @internal
- * Iterator allocation.
- * @param[in] obj The location of the object to store in the iterator.
- * @param[in] obj_size The size of the object to store in the iterator.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_new_list_iterator(const void *obj, size_t obj_size)
-{
- dmnsn_list_iterator *i
- = (dmnsn_list_iterator *)dmnsn_malloc(sizeof(dmnsn_list_iterator));
- i->obj_size = obj_size;
- i->prev = NULL;
- i->next = NULL;
- i->ptr = dmnsn_malloc(obj_size);
- memcpy(i->ptr, obj, obj_size);
- return i;
-}
-
-/**
- * @internal
- * Iterator release.
- * @param[in,out] i The iterator to free.
- */
-DMNSN_INLINE void
-dmnsn_delete_list_iterator(dmnsn_list_iterator *i)
-{
- if (i) {
- dmnsn_free(i->ptr);
- dmnsn_free(i);
- }
-}
-
-/** A doubly-linked list. */
-typedef struct dmnsn_list {
- dmnsn_list_iterator *first; /**< @internal The first iterator in the list. */
- dmnsn_list_iterator *last; /**< @internal The last iterator in the list. */
- size_t length; /**< @internal The size of the list. */
- size_t obj_size; /**< @internal The size of list objects. */
-} dmnsn_list;
-
-/**
- * Allocate a list.
- * @param[in] obj_size The size of the objects to be stored.
- * @return An empty list.
- */
-DMNSN_INLINE dmnsn_list *
-dmnsn_new_list(size_t obj_size)
-{
- dmnsn_list *list = (dmnsn_list *)dmnsn_malloc(sizeof(dmnsn_list));
- list->first = NULL;
- list->last = NULL;
- list->obj_size = obj_size;
- list->length = 0;
- return list;
-}
-
-/**
- * Delete a list.
- * @param[in,out] list The list to delete.
- */
-void dmnsn_delete_list(dmnsn_list *list);
-
-/**
- * Copy a list.
- * @param[in] list The list to copy.
- * @return A list containing the same elements as \p list.
- */
-dmnsn_list *dmnsn_copy_list(const dmnsn_list *list);
-
-/**
- * Construct a list from an array.
- * @param[in] array The array to copy.
- * @return A list with the same contents as \p array.
- */
-dmnsn_list *dmnsn_list_from_array(const dmnsn_array *array);
-
-/**
- * Construct an array from a list.
- * @param[in] list The list to copy.
- * @return An array with the same contents as \p list.
- */
-dmnsn_array *dmnsn_array_from_list(const dmnsn_list *list);
-
-/**
- * First element.
- * @param[in] list The list to index.
- * @return An iterator to the first list element, or NULL if the list is empty.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_first(const dmnsn_list *list)
-{
- return list->first;
-}
-
-/**
- * Last element.
- * @param[in] list The list to index.
- * @return An iterator to the last list element, or NULL if the list is empty.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_last(const dmnsn_list *list)
-{
- return list->last;
-}
-
-/**
- * Previous element.
- * @param[in] i The iterator to follow.
- * @return The iterator preceding \c i.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_prev(const dmnsn_list_iterator *i)
-{
- dmnsn_assert(i, "NULL list iterator.");
- return i->prev;
-}
-
-/**
- * Next element.
- * @param[in] i The iterator to follow.
- * @return The iterator following \c i.
- */
-DMNSN_INLINE dmnsn_list_iterator *
-dmnsn_list_next(const dmnsn_list_iterator *i)
-{
- dmnsn_assert(i, "NULL list iterator.");
- return i->next;
-}
-
-/**
- * Get the size of the list.
- * @param[in] list The list in question.
- * @return The number of elements in the list.
- */
-DMNSN_INLINE size_t
-dmnsn_list_size(const dmnsn_list *list)
-{
- return list->length;
-}
-
-/**
- * Get the i'th object.
- * @param[in] i The iterator to dereference.
- * @param[out] obj The location to store the object.
- */
-DMNSN_INLINE void
-dmnsn_list_get(const dmnsn_list_iterator *i, void *obj)
-{
- dmnsn_assert(i, "NULL list iterator.");
- memcpy(obj, i->ptr, i->obj_size);
-}
-
-/**
- * Get a pointer to the i'th object.
- * @param[in] i The iterator to dereference.
- * @return A pointer to the object stored at \c i.
- */
-DMNSN_INLINE void *
-dmnsn_list_at(const dmnsn_list_iterator *i)
-{
- dmnsn_assert(i, "NULL list iterator.");
- return i->ptr;
-}
-
-/**
- * Set the i'th object.
- * @param[in,out] i The iterator to dereference.
- * @param[in] obj The object to store at \c i.
- */
-DMNSN_INLINE void
-dmnsn_list_set(dmnsn_list_iterator *i, const void *obj)
-{
- dmnsn_assert(i, "NULL list iterator.");
- memcpy(i->ptr, obj, i->obj_size);
-}
-
-/**
- * Swap the objects in two iterators.
- * @param[in,out] a The first iterator.
- * @param[in,out] b The second iterator.
- */
-DMNSN_INLINE void
-dmnsn_list_swap(dmnsn_list_iterator *a, dmnsn_list_iterator *b)
-{
- void *temp = a->ptr;
- a->ptr = b->ptr;
- b->ptr = temp;
-}
-
-/**
- * Insert a detached iterator into a list.
- * @param[in,out] list The list to insert into.
- * @param[in,out] i The iterator before which to insert, or NULL for the end
- * of the list.
- * @param[in,out] j The detached iterator to insert.
- */
-DMNSN_INLINE void
-dmnsn_list_iterator_insert(dmnsn_list *list,
- dmnsn_list_iterator *i, dmnsn_list_iterator *j)
-{
- if (list->first == i)
- list->first = j;
-
- if (i) {
- j->prev = i->prev;
- i->prev = j;
- } else {
- j->prev = list->last;
- list->last = j;
- }
-
- if (j->prev)
- j->prev->next = j;
- j->next = i;
- ++list->length;
-}
-
-/**
- * Insert an object.
- * @param[in,out] list The list to insert into.
- * @param[in,out] i The iterator before which to insert, or NULL for the end
- * of the list.
- * @param[in] obj The location of the object to insert.
- */
-DMNSN_INLINE void
-dmnsn_list_insert(dmnsn_list *list, dmnsn_list_iterator *i, const void *obj)
-{
- dmnsn_list_iterator *j = dmnsn_new_list_iterator(obj, list->obj_size);
- dmnsn_list_iterator_insert(list, i, j);
-}
-
-/**
- * Detach an iterator from a list.
- * @param[in,out] list The list to remove from.
- * @param[in,out] i The iterator to detach.
- */
-DMNSN_INLINE void
-dmnsn_list_iterator_remove(dmnsn_list *list, dmnsn_list_iterator *i)
-{
- dmnsn_assert(i, "NULL list iterator.");
- dmnsn_assert(list->first, "List is empty.");
- if (list->first == i)
- list->first = i->next;
- if (list->last == i)
- list->last = i->prev;
- if (i->prev)
- i->prev->next = i->next;
- if (i->next)
- i->next->prev = i->prev;
- i->prev = NULL;
- i->next = NULL;
- --list->length;
-}
-
-/**
- * Remove the specified item from a list.
- * @param[in,out] list The list to remove from.
- * @param[in,out] i The iterator to delete.
- */
-DMNSN_INLINE void
-dmnsn_list_remove(dmnsn_list *list, dmnsn_list_iterator *i)
-{
- dmnsn_list_iterator_remove(list, i);
- dmnsn_delete_list_iterator(i);
-}
-
-/**
- * Push an object to the end of the list.
- * @param[in,out] list The list to append to.
- * @param[in] obj The location of the object to push.
- */
-DMNSN_INLINE void
-dmnsn_list_push(dmnsn_list *list, const void *obj)
-{
- dmnsn_list_insert(list, NULL, obj);
-}
-
-/**
- * Pop an object from the end of the list.
- * @param[in,out] list The list to extract from.
- * @param[out] obj The location to store the extracted object.
- */
-DMNSN_INLINE void
-dmnsn_list_pop(dmnsn_list *list, void *obj)
-{
- dmnsn_assert(list->last, "List is empty.");
- dmnsn_list_get(list->last, obj);
- dmnsn_list_remove(list, list->last);
-}
-
-/**
- * Split a list in half, and return the second half.
- * @param[in,out] list The list to split.
- * @return A the second half of the list.
- */
-dmnsn_list *dmnsn_list_split(dmnsn_list *list);
-
-/**
- * List object comparator function type.
- * @param[in] l The first iterator.
- * @param[in] r The second iterator.
- * @return Whether \p l < \p r.
- */
-typedef bool dmnsn_list_comparator_fn(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r);
-
-/**
- * Sort a list, with O(n*log(n)) comparisons.
- * @param[in,out] list The list to sort.
- * @param[in] comparator The comparator to use for comparisons.
- */
-void dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator);
-
-#endif /* DIMENSION_LIST_H */
diff --git a/libdimension/list.c b/libdimension/list.c
deleted file mode 100644
index a44e8f0..0000000
--- a/libdimension/list.c
+++ /dev/null
@@ -1,166 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * This file is part of The Dimension Library. *
- * *
- * The Dimension Library is free software; you can redistribute it and/ *
- * or modify it under the terms of the GNU Lesser 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 Library 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 *
- * Lesser General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this program. If not, see *
- * <http://www.gnu.org/licenses/>. *
- *************************************************************************/
-
-/**
- * @file
- * Doubly-linked lists.
- */
-
-#include "dimension.h"
-
-dmnsn_list *
-dmnsn_copy_list(const dmnsn_list *list)
-{
- dmnsn_list *copy = dmnsn_new_list(list->obj_size);
-
- for (dmnsn_list_iterator *i = dmnsn_list_first(list);
- i != NULL;
- i = dmnsn_list_next(i))
- {
- dmnsn_list_push(copy, dmnsn_list_at(i));
- }
-
- return copy;
-}
-
-dmnsn_list *
-dmnsn_list_from_array(const dmnsn_array *array)
-{
- dmnsn_list *list = dmnsn_new_list(array->obj_size);
-
- for (size_t i = 0; i < dmnsn_array_size(array); ++i) {
- dmnsn_list_push(list, dmnsn_array_at(array, i));
- }
-
- return list;
-}
-
-dmnsn_array *
-dmnsn_array_from_list(const dmnsn_list *list)
-{
- dmnsn_array *array = dmnsn_new_array(list->obj_size);
-
- for (dmnsn_list_iterator *i = dmnsn_list_first(list);
- i != NULL;
- i = dmnsn_list_next(i))
- {
- dmnsn_array_push(array, dmnsn_list_at(i));
- }
-
- return array;
-}
-
-void
-dmnsn_delete_list(dmnsn_list *list)
-{
- if (list) {
- while (dmnsn_list_first(list)) {
- dmnsn_list_remove(list, dmnsn_list_first(list));
- }
- dmnsn_free(list);
- }
-}
-
-/** Split the second half of a list into a new list. */
-static void
-dmnsn_list_split_impl(dmnsn_list *list, dmnsn_list *half)
-{
- /* Find the halfway point */
- size_t i, max = dmnsn_list_size(list)/2;
- dmnsn_list_iterator *ii;
- for (i = 0, ii = dmnsn_list_last(list);
- i < max && ii;
- ++i, ii = dmnsn_list_prev(ii));
-
- if (ii && ii->next) {
- half->first = ii->next;
- half->last = list->last;
- list->last = ii;
- half->first->prev = NULL;
- list->last->next = NULL;
- }
-
- list->length -= max;
- half->length = max;
-}
-
-dmnsn_list *
-dmnsn_list_split(dmnsn_list *list)
-{
- dmnsn_list *half = dmnsn_new_list(list->obj_size);
- dmnsn_list_split_impl(list, half);
- return half;
-}
-
-void
-dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator)
-{
- if (dmnsn_list_size(list) < 2) {
- return;
- } 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 = dmnsn_list_first(list);
- dmnsn_list_iterator *j = dmnsn_list_first(&half);
- while (i || j) {
- if (!i) {
- j->prev = dmnsn_list_last(list);
- list->last->next = j;
- list->last = half.last;
- list->length += half.length;
- half.first = half.last = NULL;
- half.length = 0;
- break;
- } else if (!j) {
- break;
- } else if (comparator(j, i)) {
- dmnsn_list_iterator *temp = dmnsn_list_next(j);
- dmnsn_list_iterator_remove(&half, j);
- dmnsn_list_iterator_insert(list, i, j);
- j = temp;
- } else {
- i = dmnsn_list_next(i);
- }
- }
- }
-}
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index fc15860..7551fc8 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -103,10 +103,8 @@ enum {
/** Get a coordinate of the bounding box of a node. */
static inline double
-dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
+dmnsn_get_coordinate(const dmnsn_prnode * const *node, int comparator)
{
- dmnsn_prnode **node = dmnsn_list_at(i);
-
switch (comparator) {
case DMNSN_XMIN:
return (*node)->bounding_box.min.x;
@@ -130,56 +128,56 @@ dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
/* List sorting comparators */
-static bool
-dmnsn_xmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_xmin_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_XMIN);
double rval = dmnsn_get_coordinate(r, DMNSN_XMIN);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
-static bool
-dmnsn_ymin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_ymin_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_YMIN);
double rval = dmnsn_get_coordinate(r, DMNSN_YMIN);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
-static bool
-dmnsn_zmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_zmin_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_ZMIN);
double rval = dmnsn_get_coordinate(r, DMNSN_ZMIN);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
-static bool
-dmnsn_xmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_xmax_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_XMAX);
double rval = dmnsn_get_coordinate(r, DMNSN_XMAX);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
-static bool
-dmnsn_ymax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_ymax_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_YMAX);
double rval = dmnsn_get_coordinate(r, DMNSN_YMAX);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
-static bool
-dmnsn_zmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
+static int
+dmnsn_zmax_comp(const void *l, const void *r)
{
double lval = dmnsn_get_coordinate(l, DMNSN_ZMAX);
double rval = dmnsn_get_coordinate(r, DMNSN_ZMAX);
- return lval < rval;
+ return lval < rval ? -1 : 1;
}
/** All comparators. */
-static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
+static dmnsn_array_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
[DMNSN_XMIN] = dmnsn_xmin_comp,
[DMNSN_YMIN] = dmnsn_ymin_comp,
[DMNSN_ZMIN] = dmnsn_zmin_comp,
@@ -190,32 +188,32 @@ static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
/** Add the priority leaves for this level. */
static void
-dmnsn_add_priority_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
- dmnsn_list *new_leaves, int comparator)
+dmnsn_add_priority_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_array *new_leaves, int comparator)
{
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- dmnsn_prnode *leaf = dmnsn_new_prnode();
- size_t count = 0;
- dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
- while (count < DMNSN_PRTREE_B && j) {
+ dmnsn_prnode *leaf = NULL;
+ dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[i]);
+ for (size_t j = 0, count = 0, size = dmnsn_array_size(sorted_leaves[i]);
+ j < size && count < DMNSN_PRTREE_B;
+ ++j)
+ {
/* Skip all the previously found extreme nodes */
- dmnsn_prnode **node;
- do {
- node = dmnsn_list_at(j);
- j = dmnsn_list_next(j);
- } while ((*node)->location == DMNSN_PRTREE_LEAF && j);
-
- if ((*node)->location != DMNSN_PRTREE_LEAF) {
- (*node)->location = DMNSN_PRTREE_LEAF;
- leaf->children[count++] = *node;
- dmnsn_prnode_swallow(leaf, (*node)->bounding_box);
+ if (leaves[j]->location == DMNSN_PRTREE_LEAF) {
+ continue;
}
+
+ if (!leaf) {
+ leaf = dmnsn_new_prnode();
+ }
+ leaves[j]->location = DMNSN_PRTREE_LEAF;
+ leaf->children[count++] = leaves[j];
+ dmnsn_prnode_swallow(leaf, leaves[j]->bounding_box);
}
- if (count > 0) {
- dmnsn_list_push(new_leaves, &leaf);
+ if (leaf) {
+ dmnsn_array_push(new_leaves, &leaf);
} else {
- dmnsn_delete_prnode(leaf);
return;
}
}
@@ -223,59 +221,53 @@ dmnsn_add_priority_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
/** Split the sorted lists into the left and right subtrees. */
static bool
-dmnsn_split_sorted_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
- dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B],
+dmnsn_split_sorted_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_array *right_sorted_leaves[DMNSN_PSEUDO_B],
size_t i)
{
/* Get rid of the extreme nodes */
- dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
- while (j) {
- dmnsn_list_iterator *next = dmnsn_list_next(j);
- dmnsn_prnode **node = dmnsn_list_at(j);
- if ((*node)->location == DMNSN_PRTREE_LEAF) {
- dmnsn_list_remove(sorted_leaves[i], j);
+ dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[i]);
+ size_t j, skip;
+ for (j = 0, skip = 0; j < dmnsn_array_size(sorted_leaves[i]); ++j) {
+ if (leaves[j]->location == DMNSN_PRTREE_LEAF) {
+ ++skip;
+ } else {
+ leaves[j - skip] = leaves[j];
}
- j = next;
}
+ dmnsn_array_resize(sorted_leaves[i], j - skip);
- if (dmnsn_list_size(sorted_leaves[i]) == 0) {
+ if (dmnsn_array_size(sorted_leaves[i]) == 0) {
return false;
}
/* Split the appropriate list and mark the left and right child nodes */
- right_sorted_leaves[i] = dmnsn_list_split(sorted_leaves[i]);
- for (dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
- j != NULL;
- j = dmnsn_list_next(j))
- {
- dmnsn_prnode **node = dmnsn_list_at(j);
+ right_sorted_leaves[i] = dmnsn_array_split(sorted_leaves[i]);
+ DMNSN_ARRAY_FOREACH (dmnsn_prnode **, node, sorted_leaves[i]) {
(*node)->location = DMNSN_PRTREE_LEFT;
}
- for (dmnsn_list_iterator *j = dmnsn_list_first(right_sorted_leaves[i]);
- j != NULL;
- j = dmnsn_list_next(j))
- {
- dmnsn_prnode **node = dmnsn_list_at(j);
+ DMNSN_ARRAY_FOREACH (dmnsn_prnode **, node, right_sorted_leaves[i]) {
(*node)->location = DMNSN_PRTREE_RIGHT;
}
/* Split the rest of the lists */
for (size_t j = 0; j < DMNSN_PSEUDO_B; ++j) {
if (j != i) {
- right_sorted_leaves[j] = dmnsn_new_list(sizeof(dmnsn_prnode *));
-
- dmnsn_list_iterator *k = dmnsn_list_first(sorted_leaves[j]);
- while (k) {
- dmnsn_list_iterator *next = dmnsn_list_next(k);
- dmnsn_prnode **node = dmnsn_list_at(k);
- if ((*node)->location == DMNSN_PRTREE_LEAF) {
- dmnsn_list_remove(sorted_leaves[j], k);
- } else if ((*node)->location == DMNSN_PRTREE_RIGHT) {
- dmnsn_list_iterator_remove(sorted_leaves[j], k);
- dmnsn_list_iterator_insert(right_sorted_leaves[j], NULL, k);
+ right_sorted_leaves[j] = dmnsn_new_array(sizeof(dmnsn_prnode *));
+
+ dmnsn_prnode **leaves = dmnsn_array_first(sorted_leaves[j]);
+ size_t k, skip;
+ for (k = 0, skip = 0; k < dmnsn_array_size(sorted_leaves[j]); ++k) {
+ if (leaves[k]->location == DMNSN_PRTREE_LEAF) {
+ ++skip;
+ } else if (leaves[k]->location == DMNSN_PRTREE_RIGHT) {
+ dmnsn_array_push(right_sorted_leaves[j], &leaves[k]);
+ ++skip;
+ } else {
+ leaves[k - skip] = leaves[k];
}
- k = next;
}
+ dmnsn_array_resize(sorted_leaves[j], k - skip);
}
}
@@ -285,19 +277,19 @@ dmnsn_split_sorted_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
/** Recursively constructs an implicit pseudo-PR-tree and collects the priority
leaves. */
static void
-dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
- dmnsn_list *new_leaves,
+dmnsn_priority_leaves_recursive(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_array *new_leaves,
int comparator)
{
dmnsn_add_priority_leaves(sorted_leaves, new_leaves, comparator);
- dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B];
+ dmnsn_array *right_sorted_leaves[DMNSN_PSEUDO_B];
if (dmnsn_split_sorted_leaves(sorted_leaves, right_sorted_leaves, comparator))
{
dmnsn_priority_leaves_recursive(right_sorted_leaves, new_leaves,
(comparator + 1)%DMNSN_PSEUDO_B);
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- dmnsn_delete_list(right_sorted_leaves[i]);
+ dmnsn_delete_array(right_sorted_leaves[i]);
}
dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves,
@@ -306,20 +298,20 @@ dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
}
/** Constructs an implicit pseudo-PR-tree and returns the priority leaves. */
-static dmnsn_list *
-dmnsn_priority_leaves(const dmnsn_list *leaves)
+static dmnsn_array *
+dmnsn_priority_leaves(const dmnsn_array *leaves)
{
- dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B];
+ dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B];
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- sorted_leaves[i] = dmnsn_copy_list(leaves);
- dmnsn_list_sort(sorted_leaves[i], dmnsn_comparators[i]);
+ sorted_leaves[i] = dmnsn_array_copy(leaves);
+ dmnsn_array_sort(sorted_leaves[i], dmnsn_comparators[i]);
}
- dmnsn_list *new_leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+ dmnsn_array *new_leaves = dmnsn_new_array(sizeof(dmnsn_prnode *));
dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves, 0);
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- dmnsn_delete_list(sorted_leaves[i]);
+ dmnsn_delete_array(sorted_leaves[i]);
}
return new_leaves;
@@ -327,80 +319,73 @@ dmnsn_priority_leaves(const dmnsn_list *leaves)
/** Construct a non-flat PR-tree. */
static dmnsn_prnode *
-dmnsn_make_prtree(const dmnsn_list *objects)
+dmnsn_make_prtree(const dmnsn_array *objects)
{
- if (dmnsn_list_size(objects) == 0) {
+ if (dmnsn_array_size(objects) == 0) {
return NULL;
}
- /* Make the initial list of leaves */
- dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
- for (dmnsn_list_iterator *i = dmnsn_list_first(objects);
- i != NULL;
- i = dmnsn_list_next(i))
- {
- dmnsn_object **object = dmnsn_list_at(i);
+ /* Make the initial array of leaves */
+ dmnsn_array *leaves = dmnsn_new_array(sizeof(dmnsn_prnode *));
+ DMNSN_ARRAY_FOREACH (dmnsn_object **, object, objects) {
dmnsn_prnode *node = dmnsn_new_prnode();
node->bounding_box = (*object)->bounding_box;
node->object = *object;
- dmnsn_list_push(leaves, &node);
+ dmnsn_array_push(leaves, &node);
}
- while (dmnsn_list_size(leaves) > 1) {
- dmnsn_list *new_leaves = dmnsn_priority_leaves(leaves);
- dmnsn_delete_list(leaves);
+ while (dmnsn_array_size(leaves) > 1) {
+ dmnsn_array *new_leaves = dmnsn_priority_leaves(leaves);
+ dmnsn_delete_array(leaves);
leaves = new_leaves;
}
- dmnsn_prnode **leaf = dmnsn_list_at(dmnsn_list_first(leaves));
- dmnsn_prnode *root = *leaf;
- dmnsn_delete_list(leaves);
+ dmnsn_prnode *root = *(dmnsn_prnode **)dmnsn_array_first(leaves);
+ dmnsn_delete_array(leaves);
return root;
}
-/** Add an object or its children, if any, to a list. */
+/** Add an object or its children, if any, to an array. */
static void
-dmnsn_list_add_object(dmnsn_list *objects, const dmnsn_object *object)
+dmnsn_split_add_object(dmnsn_array *objects, const dmnsn_object *object)
{
if (dmnsn_array_size(object->children) == 0) {
- dmnsn_list_push(objects, &object);
+ dmnsn_array_push(objects, &object);
} else {
DMNSN_ARRAY_FOREACH (const dmnsn_object **, child, object->children) {
- dmnsn_list_add_object(objects, *child);
+ dmnsn_split_add_object(objects, *child);
}
}
}
-/** Add objects from an array to a list, splitting unions etc. */
-static dmnsn_list *
-dmnsn_object_list(const dmnsn_array *objects)
+/** Split unions to create the input for the PR-tree. */
+static dmnsn_array *
+dmnsn_split_objects(const dmnsn_array *objects)
{
- dmnsn_list *list = dmnsn_new_list(sizeof(dmnsn_object *));
+ dmnsn_array *split = dmnsn_new_array(sizeof(dmnsn_object *));
DMNSN_ARRAY_FOREACH (const dmnsn_object **, object, objects) {
- dmnsn_list_add_object(list, *object);
+ dmnsn_split_add_object(split, *object);
}
- return list;
+ return split;
}
-/** Split unbounded objects into a new list. */
-static dmnsn_list *
-dmnsn_split_unbounded(dmnsn_list *objects)
+/** Split unbounded objects into a new array. */
+static dmnsn_array *
+dmnsn_split_unbounded(dmnsn_array *objects)
{
- dmnsn_list *unbounded = dmnsn_new_list(sizeof(dmnsn_object *));
-
- dmnsn_list_iterator *i = dmnsn_list_first(objects);
- while (i) {
- dmnsn_object **object = dmnsn_list_at(i);
-
- if (dmnsn_bounding_box_is_infinite((*object)->bounding_box)) {
- dmnsn_list_iterator *next = dmnsn_list_next(i);
- dmnsn_list_iterator_remove(objects, i);
- dmnsn_list_iterator_insert(unbounded, NULL, i);
- i = next;
+ dmnsn_array *unbounded = dmnsn_new_array(sizeof(dmnsn_object *));
+
+ dmnsn_object **array = dmnsn_array_first(objects);
+ size_t i, skip;
+ for (i = 0, skip = 0; i < dmnsn_array_size(objects); ++i) {
+ if (dmnsn_bounding_box_is_infinite(array[i]->bounding_box)) {
+ dmnsn_array_push(unbounded, &array[i]);
+ ++skip;
} else {
- i = dmnsn_list_next(i);
+ array[i - skip] = array[i];
}
}
+ dmnsn_array_resize(objects, i - skip);
return unbounded;
}
@@ -445,17 +430,14 @@ dmnsn_new_prtree(const dmnsn_array *objects)
{
dmnsn_prtree *prtree = dmnsn_malloc(sizeof(dmnsn_prtree));
- dmnsn_list *object_list = dmnsn_object_list(objects);
-
- dmnsn_list *unbounded = dmnsn_split_unbounded(object_list);
- prtree->unbounded = dmnsn_array_from_list(unbounded);
+ dmnsn_array *bounded = dmnsn_split_objects(objects);
+ prtree->unbounded = dmnsn_split_unbounded(bounded);
- dmnsn_prnode *root = dmnsn_make_prtree(object_list);
+ dmnsn_prnode *root = dmnsn_make_prtree(bounded);
prtree->bounded = dmnsn_flatten_prtree(root);
dmnsn_delete_prnode(root);
- dmnsn_delete_list(unbounded);
- dmnsn_delete_list(object_list);
+ dmnsn_delete_array(bounded);
if (dmnsn_array_size(prtree->unbounded) > 0) {
prtree->bounding_box = dmnsn_infinite_bounding_box();
diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am
index 0f1e1e0..6b5f8ca 100644
--- a/tests/libdimension/Makefile.am
+++ b/tests/libdimension/Makefile.am
@@ -23,7 +23,6 @@ check_LTLIBRARIES = libdimension-tests.la
check_PROGRAMS = warning-test \
warning-as-error-test \
error-test \
- list-test \
polynomial-test \
prtree-test \
png-test \
@@ -60,9 +59,6 @@ warning_as_error_test_LDADD = libdimension-tests.la
error_test_SOURCES = error.c
error_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
deleted file mode 100644
index e70d943..0000000
--- a/tests/libdimension/list.c
+++ /dev/null
@@ -1,78 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.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(void)
-{
- /* Treat warnings as errors for tests */
- dmnsn_die_on_warnings(true);
-
- 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;
-}