start

4 files changed, 419 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..714305c
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,24 @@
+CC = gcc
+CFLAGS = -Wall -Wextra -pedantic -std=c99 -O3 -g
+LDFLAGS = -g
+SOURCES = doll.c
+TARGET = doll.o
+DOLL_TEST = doll_test
+
+%.o: %.c
+	$(CC) $(CFLAGS) -c $<
+
+release: $(TARGET)
+
+$(DOLL_TEST): $(TARGET) $(DOLL_TEST).o
+	$(CC) $(LDFLAGS) $(TARGET) $(DOLL_TEST).o -o $(DOLL_TEST)
+
+test: $(TARGET) $(DOLL_TEST)
+	./$(DOLL_TEST)
+
+re: clean release
+
+clean:
+	rm -rf *.o doc $(DOLL_TEST) $(TARGET)
+
+.PHONY: release test re clean
diff --git a/doll.c b/doll.c
new file mode 100644
index 0000000..6fcf925
--- /dev/null
+++ b/doll.c
@@ -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;
+}
diff --git a/doll.h b/doll.h
new file mode 100644
index 0000000..5d6d981
--- /dev/null
+++ b/doll.h
@@ -0,0 +1,88 @@
+/*
+ * 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.
+ */
+
+#ifndef __DOLL_H
+#define __DOLL_H
+
+
+typedef struct doll {
+	struct doll_node *head;
+	struct doll_node *tail;
+	int length;
+} doll_t;
+
+typedef struct doll_node {
+	struct doll_node *prev;
+	struct doll_node *next;
+	void *data;
+} doll_node_t;
+
+
+struct doll_node *doll_iter;
+
+struct doll *doll_new(void);
+void doll_destroy(struct doll *list);
+int doll_prepend(struct doll *list, void *data);
+int doll_append(struct doll *list, void *data);
+int doll_remove(struct doll *list, void *data);
+void *doll_first(struct doll *list);
+void *doll_last(struct doll *list);
+void *doll_at(struct doll *list, int idx);
+
+#define doll_push(list, data) (doll_append((list), (data)))
+void *doll_pop(struct doll *list);
+
+
+#define doll_foreach(elem, list)		\
+	for (doll_iter = (list)->head,		\
+			(elem) = doll_iter ? (__typeof__(elem))doll_iter->data : NULL;	\
+		doll_iter;		\
+		doll_iter = doll_iter->next,		\
+			(elem) = doll_iter ? (__typeof__(elem))doll_iter->data : NULL)
+
+#define doll_foreach_r(elem, list)		\
+	for (doll_iter = (list)->tail,		\
+			(elem) = doll_iter ? (__typeof__(elem))doll_iter->data : NULL;	\
+		doll_iter;		\
+		doll_iter = doll_iter->prev,		\
+			(elem) = doll_iter ? (__typeof__(elem))doll_iter->data : NULL)
+
+#define doll_foreach_node(node, list)		\
+	for (node = (list)->head;		\
+		node;		\
+		node = node->next)
+
+#define doll_foreach_node_r(node, list)		\
+	for (node = (list)->tail;		\
+		node;		\
+		node = node->prev)
+
+
+#endif	/* __DOLL_H */
diff --git a/doll_test.c b/doll_test.c
new file mode 100644
index 0000000..73dd3b9
--- /dev/null
+++ b/doll_test.c
@@ -0,0 +1,81 @@
+#include <stdio.h>
+#include "doll.h"
+
+void iter(doll_t *list)
+{
+	int i;
+	char *elm;
+
+	printf("\nIterando (for)...\n");
+	for (i = 0; i < list->length; i++)
+		printf("%s\n", doll_at(list, i));
+
+	printf("\nIterando (doll_foreach)...\n");
+	doll_foreach(elm, list)
+		printf("%s\n", elm);
+
+	printf("\nIterando al revés (for)...\n");
+	for (i = -1; -i <= list->length; i--)
+		printf("%s\n", doll_at(list, i));
+
+	printf("\nIterando al revés (doll_foreach)...\n");
+	doll_foreach_r(elm, list)
+		printf("%s\n", elm);
+}
+
+void iter_doll(doll_t *list)
+{
+}
+
+int main(void)
+{
+	char *data1 = "Uno";
+	char *data2 = "Dos";
+	char *data3 = "Tres";
+	char *data4 = "Cuatro";
+	doll_t *mylist = doll_new();
+	doll_t *mylist2 = doll_new();
+	int i;
+
+	doll_append(mylist, data1);
+	doll_append(mylist, data2);
+	doll_append(mylist, data3);
+	doll_append(mylist, data4);
+	printf("Tamaño: %d\n", mylist->length);
+
+	printf("\nPrimer elemento: %s\n", (char *)doll_first(mylist));
+
+	iter(mylist);
+
+	printf("\nEliminando %s...\n", data2);
+	doll_remove(mylist, data2);
+	printf("\nTamaño: %d\n", mylist->length);
+
+	printf("\nÚltimo elemento: %s\n", (char *)doll_last(mylist));
+
+	iter(mylist);
+
+	printf("\nPush \"p1\"\n");
+	doll_push(mylist, "p1");
+	printf("Push \"p2\"\n");
+	doll_push(mylist, "p2");
+	while (mylist->head) {
+		printf("Pop: %s\n", (char *)doll_pop(mylist));
+		printf("Tamaño: %d\n", mylist->length);
+	}
+
+	for (i = 0; i < 3; i++)
+		doll_push(mylist2, "waka");
+
+	iter(mylist2);
+
+	while (mylist2->head) {
+		printf("Pop: %s\n", (char *)doll_pop(mylist2));
+		printf("Tamaño: %d\n", mylist2->length);
+	}
+
+	doll_destroy(mylist);
+	doll_destroy(mylist2);
+
+	return 0;
+}