From 45c1fbf4dfe5c7a7243b625eb8a600bdce6c748f Mon Sep 17 00:00:00 2001 From: Blake Romero Date: Wed, 18 Sep 2024 00:32:53 +0100 Subject: Add makefile & tests --- .gitignore | 2 + Makefile | 38 +++++++++++++++++ linkedlist/ll.c | 120 ------------------------------------------------------ linkedlist/ll.h | 54 ------------------------ linkedlist/main.c | 44 -------------------- main.c | 42 +++++++++++++++++++ src/ll.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/ll.h | 54 ++++++++++++++++++++++++ tests/lltests.c | 46 +++++++++++++++++++++ 9 files changed, 300 insertions(+), 218 deletions(-) create mode 100644 Makefile delete mode 100644 linkedlist/ll.c delete mode 100644 linkedlist/ll.h delete mode 100644 linkedlist/main.c create mode 100644 main.c create mode 100644 src/ll.c create mode 100644 src/ll.h create mode 100644 tests/lltests.c diff --git a/.gitignore b/.gitignore index f47cb20..a67e5a6 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,3 @@ *.out +**/bin +**/obj \ No newline at end of file diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..d20a7d3 --- /dev/null +++ b/Makefile @@ -0,0 +1,38 @@ +CC=gcc +CFLAGS=-std=c17 -Wall -Werror -g +TESTFW=criterion + +# Directories +BIN=bin +OBJ=obj +SRC=src +TEST=tests + +# Files +OBJS=$(patsubst $(SRC)/%.c, $(OBJ)/%.o, $(wildcard $(SRC)/*.c)) +TESTBINS=$(patsubst $(TEST)/%.c, $(BIN)/%, $(wildcard $(TEST)/*.c)) + +all: test + +# Target Directories +$(OBJ): + mkdir $@ + +$(BIN): + mkdir $@ + +# Target Files +$(OBJ)/%.o: $(SRC)/%.c $(OBJ) + $(CC) $(CFLAGS) -o $@ -c $< + +$(BIN)/%: $(BIN) $(TEST)/%.c $(OBJS) + $(CC) $(CFLAGS) -o $@ -l $(TESTFW) $(filter-out $<,$^) + +# Actions +.PHONY: test +test: $(TESTBINS) + for test in $(TESTBINS); do ./$$test --verbose; done + +.PHONY: clean +clean: + rm -r $(BIN) $(OBJ) diff --git a/linkedlist/ll.c b/linkedlist/ll.c deleted file mode 100644 index 43bfa27..0000000 --- a/linkedlist/ll.c +++ /dev/null @@ -1,120 +0,0 @@ -// Implementation of a Linked List -#include -#include -#include "ll.h" - -Node* llnode() { - Node* n = (Node*) malloc(sizeof(Node)); - n->value = 0; - n->next = NULL; - return n; -} - -void llprint(Node* head) { - Node* node = head; - printf("[ "); - do { - printf("%i ", node->value); - node = node->next; - } while (node != NULL); - printf("]\n"); -} - -void llvprint(Node* head) { - Node* node = head; - do { - printf("[*] %i\n", node->value); - node = node->next; - printf(" |\n"); - } while (node != NULL); - printf("[/] %p\n", node); -} - -int llcount(Node* head) { - Node* node = head; - int count = 0; - while (node != NULL) { - count++; - node = node->next; - } - return count; -} - -void llappend(Node* head, int value) { - Node* n = head; - while (n->next != NULL) n = n->next; - n->next = NEW_NODE; - n->next->value = value; - n->next->next = NULL; -} - -void llpush(Node** head, int value) { - Node* n = NEW_NODE; - n->value = value; - n->next = *head; - *head = n; -} - -void llinsert(Node** head, int value, int index) { - Node* n = *head; - Node* cur = NULL; - Node* node = NEW_NODE; - int i = 0; - node->value = value; - while (n->next != NULL && i < index) { - cur = n; - n = n->next; - ++i; - } - cur->next = node; - node->next = n; -} - -void llfree(Node* head) { - Node* n = NULL; - while (head != NULL) { - n = head; - head = head->next; - free(n); - } -} - -int llpop(Node** head) { - Node* n = *head; - int val = n->value; - *head = n->next; - free(n); - return val; -} - -int llrmlast(Node** head) { - Node* n = *head; - Node* cur = NEW_NODE; - while (n->next != NULL) { - cur = n; - n = n->next; - } - int val = n->value; - cur->next = NULL; - free(n); - return val; -} - -int llrm(Node** head, int index) { - Node* n = *head; - Node* cur = NEW_NODE; - Node* node = NEW_NODE; - int i = 0; - int val = 0; - while (n->next != NULL && i < index) { - cur = n; - n = n->next; - ++i; - } - cur->next = n->next; - node->next = n; - val = n->value; - free(n); - return val; -} - diff --git a/linkedlist/ll.h b/linkedlist/ll.h deleted file mode 100644 index 0e15c43..0000000 --- a/linkedlist/ll.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef LL -#define LL - -#define NEW_NODE llnode(); - -#include -#include - -// Node -typedef struct Node { - int value; - struct Node* next; -} Node; - -// Create & initialise a new node -Node* llnode(); - -// Print linked list values -// O() -void llprint(Node* head); -void llvprint(Node* head); - -// Return number of nodes in list -// O(n) -int llcount(Node* head); - -// Append value to the end of the list -// O(n) -void llappend(Node* head, int value); - -// Prepend a value to the list -// O(1) -void llpush(Node** head, int value); - -// Insert a value to the list at index -// O(n) -void llinsert(Node** head, int value, int index); - -// Free nodes from memory -void llfree(Node* head); - -// Pop (remove) first node -// O(1) -int llpop(Node** head); - -// Remove last node -// O(n) -int llrmlast(Node** head); - -// Remove node at index -// O(n) -int llrm(Node** head, int index); - -#endif //LL diff --git a/linkedlist/main.c b/linkedlist/main.c deleted file mode 100644 index 3ba95a3..0000000 --- a/linkedlist/main.c +++ /dev/null @@ -1,44 +0,0 @@ -#include "ll.h" - -int main() { - Node* head = NEW_NODE; - int val; - - val = 7; - head->value = val; - printf("Init with %i:\t", val); - llprint(head); - - val = 12; - llpush(&head, val); - printf("Push %i:\t", val); - llprint(head); - - val = 99; - printf("Append %i:\t", val); - llappend(head,val); - llprint(head); - - val = 45; - printf("Insert %i:\t", val); - llinsert(&head, val, 2); - llprint(head); - - val = 42; - printf("Insert %i:\t", val); - llinsert(&head, val, 1); - llprint(head); - - printf("Pop %i:\t\t", llpop(&head)); - llprint(head); - - printf("Remove %i:\t",llrmlast(&head)); - llprint(head); - - printf("Remove %i:\t",llrm(&head,1)); - llprint(head); - - llvprint(head); - - llfree(head); -} diff --git a/main.c b/main.c new file mode 100644 index 0000000..739a949 --- /dev/null +++ b/main.c @@ -0,0 +1,42 @@ +#include "../src/ll.h" + +int main() { + int val = 7; + Node* head = llnode(val); + printf("Init with %i:\t", val); + llprint(head); + + val = 12; + llpush(&head, val); + printf("Push %i:\t", val); + llprint(head); + + val = 99; + printf("Append %i:\t", val); + llappend(head,val); + llprint(head); + + val = 45; + printf("Insert %i:\t", val); + llinsert(&head, val, 2); + llprint(head); + + val = 42; + printf("Insert %i:\t", val); + llinsert(&head, val, 1); + llprint(head); + + printf("Pop %i:\t\t", llpop(&head)); + llprint(head); + + printf("Remove %i:\t",llrmlast(&head)); + llprint(head); + + printf("Remove %i:\t",llrm(&head,1)); + llprint(head); + + llvprint(head); + + /* llfree(head); */ + printf("Length: %i\n",lllength(head)); +} diff --git a/src/ll.c b/src/ll.c new file mode 100644 index 0000000..7059ec5 --- /dev/null +++ b/src/ll.c @@ -0,0 +1,118 @@ +// Implementation of a Linked List +#include +#include +#include "ll.h" + +Node* llnode(int value) { + Node* n = (Node*) malloc(sizeof(Node)); + n->value = value; + n->next = NULL; + return n; +} + +void llprint(Node* head) { + Node* node = head; + printf("[ "); + do { + printf("%i ", node->value); + node = node->next; + } while (node != NULL); + printf("]\n"); + free(node); +} + +void llvprint(Node* head) { + Node* node = head; + do { + printf("[*] %i\n", node->value); + node = node->next; + printf(" |\n"); + } while (node != NULL); + printf("[/] %s\n", (char*) node); +} + +int lllength(Node* head) { + Node* node = head; + int count = 0; + while (node != NULL) { + ++count; + node = node->next; + } + return count; +} + +void llpush(Node** head, int value) { + Node* n = llnode(value); + n->next = *head; + *head = n; +} + +int llpop(Node** head) { + int val = (*head)->value; + *head = (*head)->next; + return val; +} + +void llappend(Node* head, int value) { + Node* n = head; + while (n->next != NULL) n = n->next; + n->next = llnode(value); +} + +void llinsert(Node** head, int value, int index) { + Node* n = *head; + Node* cur = NULL; + Node* node = llnode(value); + int i = 0; + while (n->next != NULL && i < index) { + cur = n; + n = n->next; + ++i; + } + cur->next = node; + node->next = n; +} + +void llfree(Node* head) { + Node* n = NULL; + while (head != NULL) { + n = head; + head = head->next; + free(n); + } +} + +int llrmlast(Node** head) { + Node* n = *head; + Node* cur = NULL; + while (n->next != NULL) { + cur = n; + n = n->next; + } + int val = n->value; + cur->next = NULL; + free(n); + return val; +} + +int llrm(Node** head, int index) { + Node* n = *head; + Node* cur = NULL; + if (index == -1) { + while (n->next != NULL) { + cur = n; + n = n->next; + } + } else { + int i = 0; + while (n->next != NULL && i < index) { + cur = n; + n = n->next; + ++i; + } + } + cur->next = n->next; + int val = n->value; + free(n); + return val; +} diff --git a/src/ll.h b/src/ll.h new file mode 100644 index 0000000..f777ace --- /dev/null +++ b/src/ll.h @@ -0,0 +1,54 @@ +#ifndef LL +#define LL + +#define NEW_NODE llnode(); + +#include +#include + +// Node +typedef struct Node { + int value; + struct Node* next; +} Node; + +// Create & initialise a new node +Node* llnode(int value); + +// Print linked list values +void llprint(Node* head); +void llvprint(Node* head); + +// Return number of nodes in list +// O(n) +int lllength(Node* head); + +// Prepend a value to the list +// O(1) +void llpush(Node** head, int value); + +// Pop (remove) first node +// O(1) +int llpop(Node** head); + +// Append value to the end of the list +// O(n) +void llappend(Node* head, int value); + +// Insert a value to the list at index +// O(n) +void llinsert(Node** head, int value, int index); + +// Free nodes from memory +// O(n) +void llfree(Node* head); + +// Remove last node +// O(n) +int llrmlast(Node** head); + +// Remove node at index +// O(n) +int llrm(Node** head, int index); + +#endif //LL diff --git a/tests/lltests.c b/tests/lltests.c new file mode 100644 index 0000000..265a276 --- /dev/null +++ b/tests/lltests.c @@ -0,0 +1,46 @@ +#include +#include "../src/ll.h" + +Node* head = NULL; + +// Run on every test +void setup() { + head = llnode(7); +} + +// Run after every test +void teardown() {} + +TestSuite(lltest, .init=setup, .fini=teardown); + +// Node +Test(lltest, llnode) { + int val = 17; + head = llnode(val); + cr_expect(head != NULL && head->value == val); +} + +// Push +Test(lltest,llpush) { + int val = 12; + llpush(&head,val); + cr_expect(head->next->value == val); +} + +// Pop +// ... + +// Append +// ... + +// Insert +// ... + +// Remove +// ... + +// Length +// ... + +// Free +// ... -- cgit