aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <[email protected]>2017-11-30 08:25:42 +0100
committerErik Liodden <[email protected]>2017-11-30 15:21:41 +0100
commit6c9b2ee5b8e96ff66926d37626320cb7f7c1f0b1 (patch)
tree62618616ff11399a58f8740b6b5e9a6b0d539141
parent27697ae4c10b14d96275271e4b22b6578c2aac88 (diff)
downloadalgdat-6c9b2ee5b8e96ff66926d37626320cb7f7c1f0b1.tar.gz
add linked list
rewrote the linked list implementation to be more generic. important note: don't add nodes stored on the stack to the linked list yet. my poor implementation of the node_destroy method assumes that the node is created using the llist_create_node() function. create a linked list with: struct llist l; llist_init(&l); after that it is easy to create and add nodes: struct llist_node *node; node = llist_create_node(size_t elem_size, void (*freefn)(void *)); the freefn can be NULL if the element is not a pointer. to traverse the list use something like this (target is expected to be of correct type, same as elem in the node): node = l.nil; while ((node = node->next) != l.nil) { llist_get_elem(node, &target); /* do something with target */ } see structure.h for other available functions.
-rw-r--r--llist.c207
-rw-r--r--structure.h113
2 files changed, 64 insertions, 256 deletions
diff --git a/llist.c b/llist.c
index 3c846a6..fda2971 100644
--- a/llist.c
+++ b/llist.c
@@ -6,203 +6,88 @@
*/
#include <stdlib.h>
+#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "structure.h"
#include "misc.h"
-static struct llist_node *create_node(void *data)
+static void llist_node_init(struct llist_node *node, size_t elem_size,
+ void (*freefn)(void *))
{
- struct llist_node *node = malloc(sizeof(*node));
- node->data = data;
- return node;
-}
-
-/*
- * llist_init:
- * initialise a new linked list
- * returns a pointer to the new list
- */
-struct llist *llist_init(void)
-{
- struct llist *list = malloc(sizeof(*list));
- list->head = NULL;
- list->tail = NULL;
- return list;
+ node->prev = NULL;
+ node->next = NULL;
+ node->elem = allocate(elem_size);
+ node->elem_size = elem_size;
+ node->freefn = freefn;
}
-
-/*
- * llist_insert_after:
- * insert new_node after node
- */
-void llist_insert_after(struct llist *list, struct llist_node *node,
- struct llist_node *new_node)
+
+void llist_init(struct llist *l)
{
- new_node->prev = node;
- if (node->next == NULL) {
- new_node->next = NULL; /* not always necessary */
- list->tail = new_node;
- } else {
- new_node->next = node->next;
- node->next->prev = new_node;
- }
- node->next = new_node;
+ struct llist_node *sentinel = llist_create_node(0, NULL);
+ sentinel->next = sentinel;
+ sentinel->prev = sentinel;
+ l->nil = sentinel;
}
-/*
- * llist_insert_before:
- * insert new_node before node.
- */
-void llist_insert_before(struct llist *list, struct llist_node *node,
- struct llist_node *new_node)
+struct llist_node *llist_create_node(size_t elem_size, void (*freefn)(void *))
{
- new_node->next = node;
- if (node->prev == NULL) {
- new_node->prev = NULL; /* not always necessary */
- list->head = new_node;
- } else {
- new_node->prev = node->prev;
- node->prev->next = new_node;
- }
- node->prev = new_node;
+ struct llist_node *node = malloc(sizeof(*node));
+ llist_node_init(node, elem_size, freefn);
+ return node;
}
-/*
- * llist_insert_beginning:
- * insert new_node at the beginning of the list
- */
-void llist_insert_beginning(struct llist *list, struct llist_node *new_node)
+void llist_node_set_elem(struct llist_node *node, void *elem_addr)
{
- if (list->head == NULL) {
- list->head = new_node;
- list->tail = new_node;
- new_node->next = NULL;
- new_node->prev = NULL;
- } else {
- llist_insert_before(list, list->head, new_node);
- }
+ memcpy(node->elem, elem_addr, node->elem_size);
}
-/*
- * llist_insert_data_beginning:
- * create a new note at the beginning of the list point to data
- */
-void llist_insert_data_beginning(struct llist *list, void *data)
+void llist_insert_after(struct llist_node *node, struct llist_node *new_node)
{
- struct llist_node *new_node = create_node(data);
- llist_insert_beginning(list, new_node);
-}
-
-/*
- * llist_insert_int_beginning:
- * create a new note at the beginning of the list point to an int
- */
-void llist_insert_int_beginning(struct llist *list, int data)
-{
- int *n = malloc(sizeof(*n));
- *n = data;
- llist_insert_data_beginning(list, n);
+ new_node->next = node->next;
+ new_node->prev = node;
+ node->next->prev = new_node;
+ node->next = new_node;
}
-/*
- * llist_insert_end:
- * insert new_node at the end of the list
- */
-void llist_insert_end(struct llist *list, struct llist_node *new_node)
+void llist_insert_before(struct llist_node *node, struct llist_node *new_node)
{
- if (list->tail == NULL)
- llist_insert_beginning(list, new_node);
- else
- llist_insert_after(list, list->tail, new_node);
+ llist_insert_after(node->prev, new_node);
}
-/*
- * llist_insert_data_end:
- * create a new note at the end of the list point to data
- */
-void llist_insert_data_end(struct llist *list, void *data)
-{
- struct llist_node *new_node = create_node(data);
- llist_insert_end(list, new_node);
-}
-/*
- * llist_insert_int_end:
- * create a new note at the beginning of the list point to an int
- */
-void llist_insert_int_end(struct llist *list, int data)
+void llist_insert_end(struct llist *l, struct llist_node *node)
{
- int *n = malloc(sizeof(*n));
- *n = data;
- llist_insert_data_end(list, n);
+ llist_insert_before(l->nil, node);
}
-/*
- * llist_remove:
- * remove node from list and returns a pointer to the removed node
- */
-struct llist_node *llist_remove(struct llist *list, struct llist_node *node)
+void llist_insert_beginning(struct llist *l, struct llist_node *node)
{
- /* node is head */
- if (node->prev == NULL)
- list->head = node->next;
- else
- node->next->prev = node->prev;
- /* node is tail */
- if (node->next == NULL)
- list->tail = node->prev;
- else
- node->next->prev = node->prev;
-
- return node;
+ llist_insert_after(l->nil, node);
}
-/*
- * llist_delete_node:
- * removes node from list and free the memory allocated by the node
- */
-void llist_delete_node(struct llist *list, struct llist_node *node)
+void llist_remove_node(struct llist_node *node)
{
- llist_free_node(llist_remove(list, node));
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ /* TODO: destroy node */
}
-/*
- * llist_free_node:
- * assume the node is allocated on the heap
- */
-void llist_free_node(struct llist_node *node)
+void llist_get_elem(struct llist_node *node, void *elem_addr)
{
- if (node != NULL) {
- free(node);
- }
+ memcpy(elem_addr, node->elem, node->elem_size);
}
-/*
- * llist_free_data_node:
- * assume both node and data are allocated on the heap. frees memory of both
- */
-void llist_free_data_node(struct llist_node *node)
+void llist_destroy_node(struct llist_node *node)
{
- if (node != NULL) {
- free(node->data);
- free(node);
- }
+ if (node->freefn)
+ node->freefn(node->elem);
+ free(node);
}
-/*
- * llist_free_data_list:
- * assume the list is created using llist_insert_int_* or similar; eg all data
- * and nodes are allocated on the heap.
- * the function frees all memory assosiated with the list
- */
-void llist_free_data_list(struct llist *list)
+void llist_dispose(struct llist *l)
{
- struct llist_node *node = list->head;
- struct llist_node *next_node;
- while(node != NULL) {
- next_node = node->next;
- free(node->data);
- free(node);
- node = next_node;
- }
- free(list);
+ struct llist_node *node = l->nil;
+ while ((node = node->next) != l->nil)
+ llist_destroy_node(node->prev);
+ free(l->nil);
}
diff --git a/structure.h b/structure.h
index 8582c2e..6d45609 100644
--- a/structure.h
+++ b/structure.h
@@ -52,109 +52,32 @@ void queue_enqueue(struct queue *q, void *elem_addr);
void queue_dequeue(struct queue *q, void *elem_addr);
int queue_length(struct queue *q);
+/****************************************************************************
+ * Circular doubly linked list *
+ ****************************************************************************/
-
-
-/* linked lists */
struct llist {
- struct llist_node *head;
- struct llist_node *tail;
+ struct llist_node *nil;
+ void (*freefn)(void *);
};
-/* linked list node */
struct llist_node {
struct llist_node *prev;
struct llist_node *next;
- void *data;
+ void *elem;
+ size_t elem_size;
+ void (*freefn)(void *);
};
-/*
- * llist_init:
- * initialise a new linked list
- * returns a pointer to the new list
- */
-struct llist *llist_init(void);
-
-/*
- * llist_insert_after:
- * insert new_node after node
- */
-void llist_insert_after(struct llist *list, struct llist_node *node,
- struct llist_node *new_node);
-
-/*
- * llist_insert_before:
- * insert new_node before node.
- */
-void llist_insert_before(struct llist *list, struct llist_node *node,
- struct llist_node *new_node);
-
-/*
- * llist_insert_beginning:
- * insert new_node at the beginning of the list
- */
-void llist_insert_beginning(struct llist *list, struct llist_node *new_node);
-
-/*
- * llist_insert_data_beginning:
- * create a new note at the beginning of the list point to data
- */
-void llist_insert_data_beginning(struct llist *list, void *data);
-
-/*
- * llist_insert_int_beginning:
- * create a new note at the beginning of the list point to an int
- */
-void llist_insert_int_beginning(struct llist *list, int data);
-
-/*
- * llist_insert_end:
- * insert new_node at the end of the list
- */
-void llist_insert_end(struct llist *list, struct llist_node *new_node);
-
-/*
- * llist_insert_data_end:
- * create a new note at the end of the list point to data
- */
-void llist_insert_data_end(struct llist *list, void *data);
-
-/*
- * llist_insert_int_end:
- * create a new note at the beginning of the list point to an int
- */
-void llist_insert_int_end(struct llist *list, int data);
-
-/*
- * llist_remove:
- * remove node from list and returns a pointer to the removed node
- */
-struct llist_node *llist_remove(struct llist *list, struct llist_node *node);
-
-/*
- * llist_delete_node:
- * removes node from list and free the memory allocated by the node
- */
-void llist_delete_node(struct llist *list, struct llist_node *node);
-
-/*
- * llist_free_node:
- * assume the node is allocated on the heap
- */
-void llist_free_node(struct llist_node *node);
-
-/*
- * llist_free_data_node:
- * assume both node and data are allocated on the heap. frees memory of both
- */
-void llist_free_data_node(struct llist_node *node);
-
-/*
- * llist_free_data_list:
- * assume the list is created using llist_insert_int_* or similar; eg all data
- * and nodes are allocated on the heap.
- * the function frees all memory assosiated with the list
- */
-void llist_free_data_list(struct llist *list);
+void llist_init(struct llist *l);
+struct llist_node *llist_create_node(size_t elem_size, void (*freefn)(void *));
+void llist_node_set_elem(struct llist_node *node, void *elem_addr);
+void llist_insert_after(struct llist_node *node, struct llist_node *new_node);
+void llist_insert_before(struct llist_node *node, struct llist_node *new_node);
+void llist_insert_end(struct llist *l, struct llist_node *node);
+void llist_insert_beginning(struct llist *l, struct llist_node *node);
+void llist_remove_node(struct llist_node *node);
+void llist_get_elem(struct llist_node *node, void *elem_addr);
+void llist_dispose(struct llist *l);
#endif /* STRUCTURE_H */