Use arrays for PR-tree construction instead of lists.

2 files changed, 54 insertions, 358 deletions

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 */