summaryrefslogtreecommitdiffstats
path: root/libdimension/dimension
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-04-29 16:21:55 -0600
committerTavian Barnes <tavianator@gmail.com>2010-04-30 09:52:26 -0600
commitaeaa9a4e80244a5c66b1afe7e6ee1bcf48e70766 (patch)
treedf6be7525af3e537e22beb13649a473434628835 /libdimension/dimension
parent3133fafb0fbd44d687d5549a060260dd7fb93bcf (diff)
downloaddimension-aeaa9a4e80244a5c66b1afe7e6ee1bcf48e70766.tar.xz
Add a generic list type.
Diffstat (limited to 'libdimension/dimension')
-rw-r--r--libdimension/dimension/array.h4
-rw-r--r--libdimension/dimension/list.h194
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 */