Add a generic list type.

2 files changed, 196 insertions, 2 deletions

diff --git a/libdimension/dimension/array.h b/libdimension/dimension/array.h
index f840e58..e383ece 100644
--- a/libdimension/dimension/array.h
+++ b/libdimension/dimension/array.h
@@ -105,11 +105,11 @@ dmnsn_array_set(dmnsn_array *array, size_t i, const void *obj)
 
 /* Element access */
 DMNSN_INLINE void *
-dmnsn_array_at(dmnsn_array *array, size_t i)
+dmnsn_array_at(const dmnsn_array *array, size_t i)
 {
   if (i >= dmnsn_array_size(array)) {
     /* Resize if i is out of range */
-    dmnsn_array_resize(array, i + 1);
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Array index out of bounds.");
   }
   return (char *)array->ptr + array->obj_size*i;
 }
diff --git a/libdimension/dimension/list.h b/libdimension/dimension/list.h
new file mode 100644
index 0000000..deb7622
--- /dev/null
+++ b/libdimension/dimension/list.h
@@ -0,0 +1,194 @@
+/*************************************************************************
+ * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.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/>.                                       *
+ *************************************************************************/
+
+/*
+ * Simple generalized doubly-linked lists.
+ */
+
+#ifndef DIMENSION_LIST_H
+#define DIMENSION_LIST_H
+
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct dmnsn_list_iterator {
+  void *ptr;
+  size_t obj_size;
+  struct dmnsn_list_iterator *prev, *next;
+} dmnsn_list_iterator;
+
+/* Internal iterator allocation */
+
+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;
+}
+
+DMNSN_INLINE void
+dmnsn_delete_list_iterator(dmnsn_list_iterator *i)
+{
+  if (i) {
+    free(i->ptr);
+    free(i);
+  }
+}
+
+typedef struct dmnsn_list {
+  dmnsn_list_iterator *first, *last;
+  size_t obj_size, length;
+} dmnsn_list;
+
+/* List allocation */
+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;
+}
+
+/* Construction from arrays */
+dmnsn_list *dmnsn_list_from_array(const dmnsn_array *array);
+/* Delete a list */
+void dmnsn_delete_list(dmnsn_list *list);
+
+DMNSN_INLINE dmnsn_list_iterator *
+dmnsn_list_first(dmnsn_list *list)
+{
+  return list->first;
+}
+
+DMNSN_INLINE dmnsn_list_iterator *
+dmnsn_list_last(dmnsn_list *list)
+{
+  return list->last;
+}
+
+DMNSN_INLINE dmnsn_list_iterator *
+dmnsn_list_prev(dmnsn_list_iterator *i)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  return i->prev;
+}
+
+DMNSN_INLINE dmnsn_list_iterator *
+dmnsn_list_next(dmnsn_list_iterator *i)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  return i->next;
+}
+
+DMNSN_INLINE size_t
+dmnsn_list_size(dmnsn_list *list)
+{
+  return list->length;
+}
+
+/* Get the i'th object */
+DMNSN_INLINE void
+dmnsn_list_get(const dmnsn_list_iterator *i, void *obj)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  memcpy(obj, i->ptr, i->obj_size);
+}
+
+/* Set the i'th object, expanding the list if necessary */
+DMNSN_INLINE void
+dmnsn_list_set(dmnsn_list_iterator *i, const void *obj)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  memcpy(i->ptr, obj, i->obj_size);
+}
+
+/* Insert an item before `i' */
+DMNSN_INLINE void
+dmnsn_list_insert(dmnsn_list *list, dmnsn_list_iterator *i, const void *obj)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  dmnsn_list_iterator *j = dmnsn_new_list_iterator(obj, list->obj_size);
+  if (list->first == i)
+    list->first = j;
+  j->next = i;
+  j->prev = i->prev;
+  i->prev = j;
+  ++list->length;
+}
+
+/* Remove the specified item */
+DMNSN_INLINE void
+dmnsn_list_remove(dmnsn_list *list, dmnsn_list_iterator *i)
+{
+  if (!i)
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "NULL list iterator.");
+  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;
+  dmnsn_delete_list_iterator(i);
+  --list->length;
+}
+
+/* Push obj to the end of the list */
+DMNSN_INLINE void
+dmnsn_list_push(dmnsn_list *list, const void *obj)
+{
+  dmnsn_list_iterator *i = dmnsn_new_list_iterator(obj, list->obj_size);
+  if (!list->first) {
+    list->first = i;
+  } else {
+    i->prev = list->last;
+    i->prev->next = i;
+  }
+  list->last = i;
+  ++list->length;
+}
+
+/* Pop obj from the end of the list */
+DMNSN_INLINE void
+dmnsn_list_pop(dmnsn_list *list, void *obj)
+{
+  if (!list->last) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "List is empty.");
+  }
+  dmnsn_list_get(list->last, obj);
+  dmnsn_list_remove(list, list->last);
+}
+
+#endif /* DIMENSION_LIST_H */