aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <eriklio@stud.ntnu.no>2017-09-21 11:39:31 +0200
committerErik Liodden <eriklio@stud.ntnu.no>2017-09-21 11:39:31 +0200
commit760593ae352b964ec7a0b51367548123cb24e155 (patch)
tree366b2f6131f27ed6b64ccc2f76fe4080ca661101
parentc8d288eeb7c3e51c8584691f28cdaa1325fd1029 (diff)
downloadalgdat-760593ae352b964ec7a0b51367548123cb24e155.tar.gz
add misc and general structure of the program
this commit adds the basic structure of the main program as well as a linked list implementation on the heap, a way to help the user (using -h) and some basic io operations. the idea is that the user specifies which exercise should be executed using the -o option when executing the program and pipe the input text file using stdin. for example if i want to run exercise 1 with input.txt, i would run: ./bin/prog -o 1 < input.txt the program can build by running `make` from the top directory.
-rw-r--r--Makefile25
-rw-r--r--include/io.h35
-rw-r--r--include/list.h113
-rw-r--r--include/options.h18
-rw-r--r--src/Makefile31
-rw-r--r--src/main.c85
-rw-r--r--src/misc/io.c66
-rw-r--r--src/misc/list.c207
-rw-r--r--src/misc/module.mk2
-rw-r--r--src/options/module.mk1
-rw-r--r--src/options/options.c73
11 files changed, 656 insertions, 0 deletions
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..937cbbd
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,25 @@
+all: prog
+
+prog:
+ @$(MAKE) -C src --no-print-directory
+ @mkdir -p bin
+ @cp ./src/prog ./bin
+
+debug:
+ @make -C src debug --no-print-directory
+ @mkdir -p bin
+ @cp src/prog ./bin/prog-debug
+
+
+# test:
+# make -C test/
+# @cp test/test ./
+# @./test
+
+.PHONY : clean test
+
+clean :
+ rm -rf bin
+ rm -rf *.dSYM
+ @make clean -C test --no-print-directory
+ @make clean -C src --no-print-directory
diff --git a/include/io.h b/include/io.h
new file mode 100644
index 0000000..ee28320
--- /dev/null
+++ b/include/io.h
@@ -0,0 +1,35 @@
+/*
+ * io.h
+ * decleration of basic io operations
+ *
+ * Erik Liodden
+ */
+
+#ifndef IO_H
+#define IO_H
+
+#define BUF_SIZE 1024
+
+
+/*
+ * read_line:
+ * read line from stream. I should probably delete this as fgets works just
+ * fine.
+ */
+int read_line(char *buf, FILE *stream);
+
+/*
+ * str_count_words:
+ * count words in the string `str` and return this number
+ */
+int str_count_words(char *str);
+
+/*
+ * string_to_int_array:
+ * convert a string `buf` of ints reperated by spaces into the array `numbers`
+ * the function returns a pointer to the array of ints
+ */
+int *string_to_int_array(char *buf, int *numbers);
+
+
+#endif /* IO_H */
diff --git a/include/list.h b/include/list.h
new file mode 100644
index 0000000..2881f4c
--- /dev/null
+++ b/include/list.h
@@ -0,0 +1,113 @@
+/*
+ * list.h
+ * decleration of different lists and corresponding functions
+ *
+ * Erik Liodden
+ */
+
+#ifndef LIST_H
+#define LIST_H
+
+/* linked lists */
+struct llist {
+ struct llist_node *head;
+ struct llist_node *tail;
+};
+
+/* linked list node */
+struct llist_node {
+ struct llist_node *prev;
+ struct llist_node *next;
+ void *data;
+};
+
+/*
+ * 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);
+
+#endif /* LIST_H */
diff --git a/include/options.h b/include/options.h
new file mode 100644
index 0000000..7e50c8f
--- /dev/null
+++ b/include/options.h
@@ -0,0 +1,18 @@
+/*
+ * options.h
+ * decleration of basic io operations
+ *
+ * Erik Liodden
+ */
+
+#ifndef OPTIONS_H
+#define OPTIONS_H
+
+struct opts {
+ int oving;
+};
+
+void print_usage(void);
+struct opts *get_options(int argc, char **argv);
+
+#endif /* OPTIONS_H */
diff --git a/src/Makefile b/src/Makefile
new file mode 100644
index 0000000..6e17cdf
--- /dev/null
+++ b/src/Makefile
@@ -0,0 +1,31 @@
+CC=gcc
+OUTPUT_OPTION=-MMD -MP -o $@
+
+CFLAGS += -Wall -Ofast --std=c99 -Wvla -I../include
+MODULES := misc options oving1
+CFLAGS += $(patsubst %,-I%,$(MODULES))
+
+LIBS :=
+SRC := main.c
+include $(patsubst %,%/module.mk,$(MODULES))
+OBJ := $(patsubst %.c,%.o,$(filter %.c,$(SRC)))
+DEP := $(patsubst %.c,%.d,$(filter %.c,$(SRC)))
+
+all : prog
+
+prog : $(OBJ)
+ $(CC) -o $@ $(OBJ) $(LIBS)
+
+debug : CFLAGS += -O0 -g
+debug : clean prog
+
+valgrind: debug
+ valgrind ./prog
+
+-include $(DEP)
+
+.PHONY: clean
+
+clean:
+ rm -f $(OBJ) $(DEP) prog
+ rm -rf *.dSYM
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..5d1924a
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,85 @@
+/*
+ * main.c
+ * sample main.c file containing the main() function.
+ *
+ * Erik Liodden
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "list.h"
+#include "io.h"
+#include "options.h"
+
+int io(void);
+int llist(void);
+int oving1(void);
+
+int main(int argc, char *argv[])
+{
+ struct opts *options;
+ options = get_options(argc, argv);
+
+ if (options->oving) {
+ printf("\nTDT4120 - AlgDat - Oving %2d\n", options->oving);
+ printf("===========================\n\n");
+ }
+
+ switch(options->oving) {
+ case 1:
+ oving1();
+ break;
+ case 2:
+ llist();
+ break;
+ default:
+ print_usage();
+ }
+
+ free(options);
+
+ return 0;
+}
+
+int io(void)
+{
+ char buf[BUF_SIZE];
+ int *numbers;
+ /* int numbers[BUF_SIZE]; can also be put on the stack */
+ int n, i;
+
+
+ read_line(buf, stdin);
+ n = str_count_words(buf);
+ numbers = malloc(n * sizeof(*numbers));
+
+ string_to_int_array(buf, numbers);
+
+ printf("number of elements: %d\n", n);
+ for (i = 0; i < n; i++)
+ printf("number[%d]: %d\n", i, numbers[i]);
+
+ free(numbers);
+ return 0;
+}
+
+int llist(void)
+{
+ struct llist *list = llist_init();
+ struct llist_node *node1 = malloc(sizeof(*node1));
+ int a = 1;
+ node1->data = &a;
+
+ llist_insert_beginning(list, node1);
+
+ struct llist_node *x = list->head;
+ while(x != NULL) {
+ printf("node: %d\n", *(int *)x->data);
+ x = x->next;
+ }
+
+ free(node1);
+ free(list);
+ return 0;
+}
+
diff --git a/src/misc/io.c b/src/misc/io.c
new file mode 100644
index 0000000..7611f33
--- /dev/null
+++ b/src/misc/io.c
@@ -0,0 +1,66 @@
+/*
+ * io.c
+ * implementation of basic io operations
+ *
+ * Erik Liodden
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include "io.h"
+
+/*
+ * read_line:
+ * read line from stream. I should probably delete this as fgets works just
+ * fine.
+ */
+int read_line(char *buf, FILE *stream)
+{
+ fgets(buf, BUF_SIZE, stream);
+ return 0;
+}
+
+/*
+ * str_count_words:
+ * count words in the string `str` and return this number
+ */
+int str_count_words(char *str)
+{
+ int nwords = 0;
+ int in = 0;
+ while (*str) {
+ if (isspace(*str)) {
+ in = 0;
+ } else if (in == 0) {
+ in = 1;
+ nwords++;
+ }
+ str++;
+ }
+ return nwords;
+}
+
+/*
+ * string_to_int_array:
+ * convert a string `buf` of ints reperated by spaces into the array `numbers`
+ * the function returns a pointer to the array of ints
+ * the caller has to make sure *numbers has enough space
+ */
+int *string_to_int_array(char *buf, int *numbers)
+{
+ char *token;
+ int n = 0;
+
+ /* put numbers in array */
+ token = strtok(buf, " ");
+ while (token != NULL) {
+ if (!isspace(*token)) {
+ numbers[n] = atoi(token);
+ n++;
+ }
+ token = strtok(NULL, " ");
+ }
+ return numbers;
+}
diff --git a/src/misc/list.c b/src/misc/list.c
new file mode 100644
index 0000000..4164812
--- /dev/null
+++ b/src/misc/list.c
@@ -0,0 +1,207 @@
+/*
+ * list.c
+ * implementation of different lists
+ *
+ * Erik Liodden
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "list.h"
+
+static struct llist_node *create_node(void *data)
+{
+ 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;
+}
+
+/*
+ * llist_insert_after:
+ * insert new_node after node
+ */
+void llist_insert_after(struct llist *list, struct llist_node *node,
+ struct llist_node *new_node)
+{
+ 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;
+}
+
+/*
+ * llist_insert_before:
+ * insert new_node before node.
+ */
+void llist_insert_before(struct llist *list, struct llist_node *node,
+ struct llist_node *new_node)
+{
+ 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;
+}
+
+/*
+ * llist_insert_beginning:
+ * insert new_node at the beginning of the list
+ */
+void llist_insert_beginning(struct llist *list, struct llist_node *new_node)
+{
+ 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);
+ }
+}
+
+/*
+ * 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)
+{
+ 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);
+}
+
+/*
+ * llist_insert_end:
+ * insert new_node at the end of the list
+ */
+void llist_insert_end(struct llist *list, 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_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)
+{
+ int *n = malloc(sizeof(*n));
+ *n = data;
+ llist_insert_data_end(list, n);
+}
+
+/*
+ * 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)
+{
+ /* 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_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(llist_remove(list, node));
+}
+
+/*
+ * llist_free_node:
+ * assume the node is allocated on the heap
+ */
+void llist_free_node(struct llist_node *node)
+{
+ if (node != NULL) {
+ free(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)
+{
+ if (node != NULL) {
+ free(node->data);
+ 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)
+{
+ 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);
+}
+
diff --git a/src/misc/module.mk b/src/misc/module.mk
new file mode 100644
index 0000000..e659246
--- /dev/null
+++ b/src/misc/module.mk
@@ -0,0 +1,2 @@
+SRC += misc/list.c \
+ misc/io.c
diff --git a/src/options/module.mk b/src/options/module.mk
new file mode 100644
index 0000000..1dc06eb
--- /dev/null
+++ b/src/options/module.mk
@@ -0,0 +1 @@
+SRC += options/options.c
diff --git a/src/options/options.c b/src/options/options.c
new file mode 100644
index 0000000..49cf068
--- /dev/null
+++ b/src/options/options.c
@@ -0,0 +1,73 @@
+/*
+ * options.c
+ * help and options at runtime
+ *
+ * Erik Liodden
+ */
+
+#include <ctype.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "options.h"
+
+void print_usage(void)
+{
+ fprintf(stderr, "usage: ./prog [option] < input.txt (> output.txt)\n");
+ fprintf(stderr, "\nthis program solves the exercises in tdt4120 - algdat.\n");
+ fprintf(stderr, "includes solution to exercise: 1\n");
+ fprintf(stderr, "\noptions:\n");
+ fprintf(stderr, "\t-o, --oving N\tselect code for oving N\n");
+ fprintf(stderr, "\t-h, --help\tshows this help text\n");
+}
+
+struct opts *get_options(int argc, char **argv)
+{
+ int option_index = 0;
+ int c;
+ opterr = 0;
+
+ struct opts *options = calloc(1, sizeof(struct opts));
+ struct option long_options[] = {
+ /* These options set a flag.
+ * {"verbose", no_argument, &verbose_flag, 1},
+ * {"brief", no_argument, &verbose_flag, 0},
+ */
+ /* These options don’t set a flag.
+ We distinguish them by their indices. */
+ /* {"merge", no_argument, 0, 'm'},
+ * {"file", required_argument, 0, 'f'},
+ */
+ {"help", no_argument, 0, 'h'},
+ {"oving", required_argument, 0, 'o'},
+ {0, 0, 0, 0}
+ };
+
+
+ while((c = getopt_long(argc, argv, "ho:",
+ long_options, &option_index)) != -1)
+ switch (c) {
+ case 'o':
+ options->oving = atoi(optarg);
+ break;
+ case 'h':
+ print_usage();
+ exit(EXIT_SUCCESS);
+ case '?':
+ if (optopt == 'o')
+ fprintf (stderr, "Option -%c" \
+ "requires an argument.\n", optopt);
+ else if (isprint(optopt))
+ fprintf(stderr, "Unknown option `-%c'.\n", optopt);
+ else
+ fprintf(stderr,
+ "Unknown option character `\\x%x'.\n", optopt);
+ fprintf(stderr, "\n");
+ print_usage();
+ exit(EXIT_FAILURE);
+ default:
+ abort();
+ }
+ return options;
+}
+