diff options
| -rw-r--r-- | bench/libdimension/Makefile.am | 3 | ||||
| -rw-r--r-- | bench/libdimension/list.c | 136 | ||||
| -rw-r--r-- | libdimension/Makefile.am | 2 | ||||
| -rw-r--r-- | libdimension/dimension.h | 1 | ||||
| -rw-r--r-- | libdimension/dimension/array.h | 55 | ||||
| -rw-r--r-- | libdimension/dimension/list.h | 357 | ||||
| -rw-r--r-- | libdimension/list.c | 166 | ||||
| -rw-r--r-- | libdimension/prtree.c | 248 | ||||
| -rw-r--r-- | tests/libdimension/Makefile.am | 4 | ||||
| -rw-r--r-- | tests/libdimension/list.c | 78 |
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; -} |