diff options
Diffstat (limited to 'doll.c')
| -rw-r--r-- | doll.c | 226 |
1 files changed, 226 insertions, 0 deletions
@@ -0,0 +1,226 @@ +/* + * doll - Doubly linked list implementation + * Copyright (c) 2012 Guillermo Ramos Gutiérrez <0xwille@gmail.com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of copyright holders nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL COPYRIGHT HOLDERS OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdlib.h> +#include "doll.h" + + +static struct doll_node *doll_new_node(void *data) +{ + struct doll_node *new_node = malloc(sizeof(struct doll_node)); + new_node->data = data; + return new_node; +} + + +static void doll_destroy_node(struct doll_node *node) +{ + free(node); +} + + +static struct doll_node *doll_find(struct doll *list, void *data) +{ + struct doll_node *node; + doll_foreach_node(node, list) + if (node->data == data) + return node; + return NULL; +} + + +static struct doll_node *doll_insert_before(struct doll *list, + struct doll_node *new, struct doll_node *base) +{ + if (base == list->head) { + base->prev = new; + new->next = base; + new->prev = NULL; + list->head = new; + } else { + base->prev->next = new; + new->prev = base->prev; + base->prev = new; + new->next = base; + } + + list->length++; + + return new; +} + + +static struct doll_node *doll_insert_after(struct doll *list, + struct doll_node *new, struct doll_node *base) +{ + if (base == list->tail) { + base->next = new; + new->prev = base; + new->next = NULL; + list->tail = new; + } else { + base->next->prev = new; + new->next = base->next; + base->next = new; + new->prev = base; + } + + list->length++; + + return new; +} + + +static struct doll_node *doll_prepend_node(struct doll *list, struct doll_node *node) +{ + if (node == NULL) { + return NULL; + } else if (list->head == NULL && list->tail == NULL) { + list->head = list->tail = node; + node->prev = node->next = NULL; + list->length++; + } else { + doll_insert_before(list, node, list->head); + } + + return node; +} + + +static struct doll_node *doll_append_node(struct doll *list, struct doll_node *node) +{ + if (node == NULL) { + return NULL; + } else if (list->head == NULL && list->tail == NULL) { + list->head = list->tail = node; + node->prev = node->next = NULL; + list->length++; + } else { + doll_insert_after(list, node, list->tail); + } + + return node; +} + + +static void doll_remove_node(struct doll *list, struct doll_node *node) +{ + if (node->prev) + node->prev->next = node->next; + else + list->head = node->next; + + if (node->next) + node->next->prev = node->prev; + else + list->tail = node->prev; + + list->length--; + + doll_destroy_node(node); +} + + +struct doll *doll_new(void) +{ + struct doll *newlist = malloc(sizeof(struct doll)); + newlist->head = newlist->tail = NULL; + newlist->length = 0; + return newlist; +} + + +void doll_destroy(struct doll *list) +{ + struct doll_node *node; + doll_foreach_node(node, list) + doll_destroy_node(node); + free(list); +} + + +int doll_prepend(struct doll *list, void *data) +{ + return doll_prepend_node(list, doll_new_node(data)) ? 0 : -1; +} + + +int doll_append(struct doll *list, void *data) +{ + return doll_append_node(list, doll_new_node(data)) ? 0 : -1; +} + + +int doll_remove(struct doll *list, void *data) +{ + struct doll_node *node = doll_find(list, data); + if (node == NULL) + return -1; + + doll_remove_node(list, node); + return 0; +} + + +void *doll_first(struct doll *list) +{ + return list->head->data; +} + + +void *doll_last(struct doll *list) +{ + return list->tail->data; +} + + +void *doll_pop(struct doll *list) +{ + struct doll_node *head = list->tail; + if (head) + doll_remove_node(list, head); + return head ? head->data : NULL; +} + + + +void *doll_at(struct doll *list, int idx) +{ + struct doll_node *aux = list->head; + + if (idx < 0) + idx = list->length + idx; + if (idx < 0 || idx >= list->length) + return NULL; + + while (idx--) + aux = aux->next; + return aux->data; +} |