diff options
Diffstat (limited to 'sem1/algo/mm2/linked')
| -rw-r--r-- | sem1/algo/mm2/linked/Makefile | 31 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/Readme.md | 22 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/llist.c | 89 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/llist.h | 22 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/main.c | 45 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/node.c | 57 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/node.h | 23 |
7 files changed, 289 insertions, 0 deletions
diff --git a/sem1/algo/mm2/linked/Makefile b/sem1/algo/mm2/linked/Makefile new file mode 100644 index 0000000..881143c --- /dev/null +++ b/sem1/algo/mm2/linked/Makefile @@ -0,0 +1,31 @@ +CC = gcc +# Enable gdb and pull include files from current dir +CFLAGS = -ggdb -I. +LDFLAGS = + +BINARY = linked +BUILD_DIR = build + +# Capture c files +c_files = $(wildcard *.c) + +# Convert c names to corrosponding o names +OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files)) + +# $@ is the %.o file and $^ is the %.c file +$(BUILD_DIR)/%.o: %.c + mkdir -p $(dir $@) + $(CC) -c -o $@ $^ $(CFLAGS) + +# $@ becomes left part thus linked +$(BINARY): $(OBJ) + $(CC) -o $@ $^ $(LDFLAGS) + +.PHONY: clean run + +run: $(BINARY) + ./$(BINARY) + +clean: + rm -f $(OBJ) $(BINARY) + rmdir $(BUILD_DIR) diff --git a/sem1/algo/mm2/linked/Readme.md b/sem1/algo/mm2/linked/Readme.md new file mode 100644 index 0000000..679dcf3 --- /dev/null +++ b/sem1/algo/mm2/linked/Readme.md @@ -0,0 +1,22 @@ +# Linked list assignment + +The linked list stuff is in node.c and higher level list functions in llist.c. + +Build with make: + +``` +make +``` + +To build and run + +``` +make run +``` + +To clean up when we are done. + +``` +make clean +``` + diff --git a/sem1/algo/mm2/linked/llist.c b/sem1/algo/mm2/linked/llist.c new file mode 100644 index 0000000..41ab892 --- /dev/null +++ b/sem1/algo/mm2/linked/llist.c @@ -0,0 +1,89 @@ +#include "llist.h" + +#include <string.h> +#include <stdio.h> + + +#define OUT_OFF_BOUNDS 2 + +void llist_init(llist_t *list) { + /* Zero out structure */ + list->head = list->root = NULL; + + list->len = 0; + +} + +void llist_append(llist_t *list, int val) { + /* Insert node after HEAD */ + list->head = node_insert(list->head, val); + + /* Check if was list is empty */ + if( list->len == 0 ) { + /* Set root */ + list->root = list->head; + } + + /* Increase count */ + list->len++; +} + +node_t *llist_get_node(llist_t *list, unsigned int index) { + /* Check if we have it */ + if( index >= list->len ) { + return NULL; + } + + /* Find the best way to go down the list */ + int direc = index > (list->len / 2) ? -1 : 1; + + /* Setup start location */ + int pos = direc > 0 ? 0 : list->len-1; + node_t *node = direc > 0 ? list->root : list->head; + + /* Go to index */ + while( pos != index ) { + /* TODO kinda risky, we trust our math and len */ + node = direc > 0 ? node->next : node->prev; + + pos += direc; + } + + return node; +} + +int llist_get(llist_t *list, unsigned int index) { + /* Get node */ + node_t *node = llist_get_node(list, index); + if( node == NULL ) { + /* Yes i know this is stupid */ + return -1; + } + + /* Return value */ + return node->val; +} + + +int llist_pop(llist_t *list, unsigned int index) { + /* Get node */ + node_t *node = llist_get_node(list, index); + if( node == NULL ) { + /* Yes i know this is stupid */ + return -1; + } + + /* Update root and head if we delete it */ + if( node == list->root ) { + list->root = node->next; + } + if( node == list->head ) { + list->head = node->prev; + } + + /* Keep len up to date */ + list->len--; + + /* Delete stuff */ + return node_pop(node); +} diff --git a/sem1/algo/mm2/linked/llist.h b/sem1/algo/mm2/linked/llist.h new file mode 100644 index 0000000..e52be89 --- /dev/null +++ b/sem1/algo/mm2/linked/llist.h @@ -0,0 +1,22 @@ +#ifndef LIST_H +#define LIST_H + +#include "node.h" + +typedef struct { + node_t *root; + node_t *head; + unsigned int len; +} llist_t; + +void llist_init(llist_t *list); + +void llist_append(llist_t *list, int val); + +node_t *llist_get_node(llist_t *list, unsigned int index); + +int llist_get(llist_t *list, unsigned int index); + +int llist_pop(llist_t *list, unsigned int index); + +#endif diff --git a/sem1/algo/mm2/linked/main.c b/sem1/algo/mm2/linked/main.c new file mode 100644 index 0000000..72b62cc --- /dev/null +++ b/sem1/algo/mm2/linked/main.c @@ -0,0 +1,45 @@ +#include <stdio.h> +#include "node.h" +#include "llist.h" + +void list_print(node_t *root) { + int index = 0; + /* Loop through notes and print them */ + while( root != NULL ) { + /* Print a value */ + printf("%d: %d\n", index++, root->val); + + /* Next value */ + root = root->next; + } +} + +/* Remove node */ +int main() { + + /* Do some stuff */ + llist_t list; + llist_init(&list); + + llist_append(&list, 11); // 0 + llist_append(&list, 22); // 1 + llist_append(&list, 33); // 2 + llist_append(&list, 44); // 3 + llist_append(&list, 89); // 4 + llist_append(&list, 12); // 5 + llist_append(&list, 2); // 6 + llist_append(&list, 1); // 7 + llist_append(&list, 7); // 8 + llist_append(&list, 232);// 9 + + list_print(list.root); + printf("%d\n", llist_get(&list, 5)); + llist_pop(&list, 9); + printf("%d\n", llist_get(&list, 7)); + + list_print(list.root); + + while( list.len ) { + printf("Popped %d\n", llist_pop(&list, 0)); + } +} diff --git a/sem1/algo/mm2/linked/node.c b/sem1/algo/mm2/linked/node.c new file mode 100644 index 0000000..cce1be0 --- /dev/null +++ b/sem1/algo/mm2/linked/node.c @@ -0,0 +1,57 @@ +#include "node.h" + +#include <string.h> +#include <stdlib.h> + +/* Insert after node */ +node_t *node_insert(node_t *node, int val) { + /* Create new node */ + node_t *newNode = (node_t *) malloc( sizeof(node_t) ); + if( newNode == NULL ) { + return NULL; + } + + + newNode->val = val; + newNode->prev = node; + + /* Check if there is node before */ + if( node == NULL ) { + /* If not then there is no after */ + newNode->next = NULL; + return newNode; + } + + /* Set next node */ + newNode->next = node->next; + node->next = newNode; + + /* Check node after */ + if( newNode->next != NULL ) { + /* Backlink next node */ + newNode->next->prev = newNode; + } + + return newNode; +} + +/* Pop node */ +int node_pop(node_t *node) { + int val = node->val; + + /* Check prev */ + if( node->prev != NULL ) { + /* Point last node to next node */ + node->prev->next = node->next; + } + + /* Check next */ + if( node->next != NULL ) { + node->next->prev = node->prev; + } + + /* Free memory */ + free(node); + + return val; +} diff --git a/sem1/algo/mm2/linked/node.h b/sem1/algo/mm2/linked/node.h new file mode 100644 index 0000000..027926b --- /dev/null +++ b/sem1/algo/mm2/linked/node.h @@ -0,0 +1,23 @@ +#ifndef NODE_H +#define NODE_H + +typedef struct node_struct { + int val; + struct node_struct *next; + struct node_struct *prev; +} node_t; + +/** @brief Create a new node after specified node + * + * @param node Pointer to node where new node should be inserted, can also be NULL + * @param val Value to add to new node + */ +node_t *node_insert(node_t *node, int val); + +/** @brief Pop node from chain and free's the resource + * + * @return Value in node + */ +int node_pop(node_t *node); + +#endif |