From ccc143b9ed802f5b0aa3069423227972de039ba5 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 10 May 2011 13:20:49 -0600 Subject: Use arrays for PR-tree construction instead of lists. --- libdimension/dimension/array.h | 55 ++++++- libdimension/dimension/list.h | 357 ----------------------------------------- 2 files changed, 54 insertions(+), 358 deletions(-) delete mode 100644 libdimension/dimension/list.h (limited to 'libdimension/dimension') 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 /* For size_t */ -#include /* For memcpy */ +#include /* For qsort() */ +#include /* For memcpy() */ /** Dynamic array type. */ typedef struct dmnsn_array { @@ -97,6 +98,38 @@ dmnsn_array_resize(dmnsn_array *array, size_t length) array->length = 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. @@ -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 * - * * - * 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 * - * . * - *************************************************************************/ - -/** - * @file - * Simple doubly-linked lists. - */ - -#ifndef DIMENSION_LIST_H -#define DIMENSION_LIST_H - -#include -#include -#include - -/** - * 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 */ -- cgit v1.2.3