From aeaa9a4e80244a5c66b1afe7e6ee1bcf48e70766 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 29 Apr 2010 16:21:55 -0600 Subject: Add a generic list type. --- libdimension/Makefile.am | 2 + libdimension/dimension.h | 1 + libdimension/dimension/array.h | 4 +- libdimension/dimension/list.h | 194 +++++++++++++++++++++++++++++++++++++++++ libdimension/list.c | 45 ++++++++++ 5 files changed, 244 insertions(+), 2 deletions(-) create mode 100644 libdimension/dimension/list.h create mode 100644 libdimension/list.c (limited to 'libdimension') diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am index 7b3cee0..535bd69 100644 --- a/libdimension/Makefile.am +++ b/libdimension/Makefile.am @@ -34,6 +34,7 @@ nobase_include_HEADERS = dimension.h \ dimension/interior.h \ dimension/light.h \ dimension/lights.h \ + dimension/list.h \ dimension/malloc.h \ dimension/object.h \ dimension/objects.h \ @@ -64,6 +65,7 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \ inlines.c \ interior.c \ light.c \ + list.c \ malloc.c \ object.c \ perspective.c \ diff --git a/libdimension/dimension.h b/libdimension/dimension.h index 5aca9b3..2ad0c16 100644 --- a/libdimension/dimension.h +++ b/libdimension/dimension.h @@ -63,6 +63,7 @@ typedef void dmnsn_free_fn(void *ptr); #include #include #include +#include #include #include #include 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 * + * * + * 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 * + * . * + *************************************************************************/ + +/* + * Simple generalized doubly-linked lists. + */ + +#ifndef DIMENSION_LIST_H +#define DIMENSION_LIST_H + +#include +#include + +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 */ diff --git a/libdimension/list.c b/libdimension/list.c new file mode 100644 index 0000000..0303513 --- /dev/null +++ b/libdimension/list.c @@ -0,0 +1,45 @@ +/************************************************************************* + * 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 * + * . * + *************************************************************************/ + +#include "dimension.h" + +dmnsn_list * +dmnsn_list_from_array(const dmnsn_array *array) +{ + dmnsn_list *list = dmnsn_new_list(array->obj_size); + + size_t i; + for (i = 0; i < dmnsn_array_size(array); ++i) { + dmnsn_list_push(list, dmnsn_array_at(array, i)); + } + + return list; +} + +void +dmnsn_delete_list(dmnsn_list *list) +{ + if (list) { + while (list->first) { + dmnsn_list_remove(list, list->first); + } + free(list); + } +} -- cgit v1.2.3