aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <eriklio@stud.ntnu.no>2018-01-18 15:56:56 +0100
committerErik Liodden <eriklio@stud.ntnu.no>2018-01-18 15:56:56 +0100
commit17e5240104ee0bd43019be26cd05938c7421d23e (patch)
tree977d6fa74ec33e97709084232c092fa27e902069
parent461a5c82ac028ed88db548dfd871028793a831d3 (diff)
downloadalgdat-17e5240104ee0bd43019be26cd05938c7421d23e.tar.gz
add documentation
i have added some much needed documentation. i will continue to do this when i feel like it. i haven't decided on the multi line comment style yet, but i think i like this one: /* this is the first line in a multi line comment * this is the second line */ i will use that style for now and see how i feel about it
-rw-r--r--llist.c35
-rw-r--r--structure.h10
2 files changed, 44 insertions, 1 deletions
diff --git a/llist.c b/llist.c
index 3a612fe..4852f9f 100644
--- a/llist.c
+++ b/llist.c
@@ -1,6 +1,6 @@
/*
* llist.c
- * implementation of a linked list
+ * implementation of a doubly linked list with sentinel node
*
* Erik Liodden
*/
@@ -12,6 +12,9 @@
#include "structure.h"
#include "misc.h"
+/* llist_node_init: initialize a new node (allocated on the heap) for use in the
+ * list
+ */
static void llist_node_init(struct llist_node *node, size_t elem_size,
void (*freefn)(void *))
{
@@ -22,6 +25,9 @@ static void llist_node_init(struct llist_node *node, size_t elem_size,
node->freefn = freefn;
}
+/* llist_init: initialise a new list pointed to by l. l itself can be allocated
+ * by the caller on the stack.
+ */
void llist_init(struct llist *l)
{
struct llist_node *sentinel = llist_create_node(0, NULL);
@@ -30,6 +36,9 @@ void llist_init(struct llist *l)
l->nil = sentinel;
}
+/* llist_create_node: create a new node on the heap and set an element size
+ * and assign a free function for the data.
+ */
struct llist_node *llist_create_node(size_t elem_size, void (*freefn)(void *))
{
struct llist_node *node = malloc(sizeof(*node));
@@ -37,11 +46,17 @@ struct llist_node *llist_create_node(size_t elem_size, void (*freefn)(void *))
return node;
}
+/* llist_node_set_elem: copy the value located at elem_addr to the nodes element
+ * value. this assumes that elem_addr is of the same size as node->elem_size
+ * (which was set when the node was created)
+ */
void llist_node_set_elem(struct llist_node *node, void *elem_addr)
{
memcpy(node->elem, elem_addr, node->elem_size);
}
+/* llist_insert_after: insert new_node after node in the linked list
+ */
void llist_insert_after(struct llist_node *node, struct llist_node *new_node)
{
new_node->next = node->next;
@@ -50,21 +65,30 @@ void llist_insert_after(struct llist_node *node, struct llist_node *new_node)
node->next = new_node;
}
+/* llist_insert_before: insert new_node before node in the linked list
+ */
void llist_insert_before(struct llist_node *node, struct llist_node *new_node)
{
llist_insert_after(node->prev, new_node);
}
+/* llist_insert_end: insert new_node at the end of the linked list l
+ */
void llist_insert_end(struct llist *l, struct llist_node *node)
{
llist_insert_before(l->nil, node);
}
+/* llist_insert_beginning: insert new_node at the beginning of the linked list l
+ */
void llist_insert_beginning(struct llist *l, struct llist_node *node)
{
llist_insert_after(l->nil, node);
}
+/* llist_destroy_node: delete the node and free the memory pointed to by
+ * node->elem and the node itself.
+ */
void llist_destroy_node(struct llist_node *node)
{
if (node->freefn)
@@ -73,6 +97,9 @@ void llist_destroy_node(struct llist_node *node)
free(node);
}
+/* llist_remove_node: remove node from the linked list it belongs to. the node
+ * itself is not destroied afterwards.
+ */
void llist_remove_node(struct llist_node *node)
{
node->prev->next = node->next;
@@ -80,11 +107,17 @@ void llist_remove_node(struct llist_node *node)
/* llist_destroy_node(node); */
}
+/* llist_get_elem: copy the value in node->elem (node->elem_size number of
+ * bytes) to the memory location pointed to by elem_addr.
+ */
void llist_get_elem(struct llist_node *node, void *elem_addr)
{
memcpy(elem_addr, node->elem, node->elem_size);
}
+/* llist_dispose: destroy all the nodes in the list l, including the sentinel
+ * node.
+ */
void llist_dispose(struct llist *l)
{
struct llist_node *node = l->nil->next;
diff --git a/structure.h b/structure.h
index b3914a7..04db5a5 100644
--- a/structure.h
+++ b/structure.h
@@ -56,6 +56,14 @@ int queue_length(struct queue *q);
/*
* Circular doubly linked list
+ *
+ * this is an implementation of a circular doubly linked list with a sentinal
+ * node for a (potentially) cleaner implementation.
+ *
+ * the llist struct is the actual list and includes a functionpointer on how to
+ * free nodes. the llist_node is the node in the llist and includes a pointer to
+ * the data assosiated with the node as well as a freefn to free the data if
+ * necessary.
*/
struct llist {
@@ -85,6 +93,8 @@ void llist_dispose(struct llist *l);
/*
* heap
+ *
+ * this is a max-heap
*/
struct heap {