aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <eriklio@stud.ntnu.no>2017-11-16 13:44:22 +0100
committerErik Liodden <eriklio@stud.ntnu.no>2017-11-16 13:44:43 +0100
commita3b67cf359f841b570501d2cc26afc5b0ed80ff0 (patch)
tree878bfcdaea6bc048633efe39fd1340abc587dec2
parentacd916d5d87417ef362a29472189dba142ddae7a (diff)
downloadalgdat-a3b67cf359f841b570501d2cc26afc5b0ed80ff0.tar.gz
massive restructure
hold on to your butt. this is a massive restructure of the source tree. i deciced to remove the "pleasing to look at" folder structure with a way more practical flat structure. i also decided to make a algdat library containing everything i need for the assignments. the makefile is inspired by an early version of the makefile used in git, and it should probably be tweaked a bit when i know better what i am doing. since this commit touches almost every file in the project, i expect git-blame to be messed up for all commits prior to this. ah well.
-rw-r--r--.gitignore2
-rw-r--r--Makefile47
-rw-r--r--include/options.h18
-rw-r--r--include/oving.h13
-rw-r--r--io.c (renamed from src/misc/io.c)0
-rw-r--r--io.h (renamed from include/io.h)0
-rw-r--r--llist.c (renamed from src/misc/list.c)130
-rw-r--r--misc.c (renamed from src/misc/misc.c)0
-rw-r--r--misc.h (renamed from include/misc.h)0
-rw-r--r--oving1.c (renamed from src/oving/oving1.c)7
-rw-r--r--queue.c71
-rw-r--r--sort.h22
-rw-r--r--src/Makefile31
-rw-r--r--src/main.c33
-rw-r--r--src/misc/module.mk4
-rw-r--r--src/misc/options.c73
-rw-r--r--src/oving/module.mk2
-rw-r--r--stack.c65
-rw-r--r--structure.h (renamed from include/list.h)0
-rw-r--r--structure.txt74
20 files changed, 194 insertions, 398 deletions
diff --git a/.gitignore b/.gitignore
index c06ec9c..06d49d8 100644
--- a/.gitignore
+++ b/.gitignore
@@ -203,3 +203,5 @@ bin/
src/prog
src/prog-debug
test/
+
+oving1
diff --git a/Makefile b/Makefile
index 937cbbd..8be7414 100644
--- a/Makefile
+++ b/Makefile
@@ -1,25 +1,34 @@
-all: prog
+CFLAGS=-g -O2 -Wall -Wextra -Wvla
-prog:
- @$(MAKE) -C src --no-print-directory
- @mkdir -p bin
- @cp ./src/prog ./bin
+CC=gcc
+AR=ar
-debug:
- @make -C src debug --no-print-directory
- @mkdir -p bin
- @cp src/prog ./bin/prog-debug
+PROG= oving1
+all: $(PROG)
-# test:
-# make -C test/
-# @cp test/test ./
-# @./test
+LIB_OBJS=stack.o queue.o llist.o io.o misc.o
+LIB_FILE=libalgdat.a
+LIB_H=structure.h misc.h io.h
-.PHONY : clean test
+LIBS = $(LIB_FILE)
-clean :
- rm -rf bin
- rm -rf *.dSYM
- @make clean -C test --no-print-directory
- @make clean -C src --no-print-directory
+$(LIB_FILE): $(LIB_OBJS)
+ $(AR) rcs $@ $(LIB_OBJS)
+
+%: %.c $(LIB_FILE)
+ $(CC) $(CFLAGS) -o $@ $(filter %.c,$^) $(LIBS)
+
+oving1.o: $(LIB_H)
+misc.o: $(LIB_H)
+io.o: $(LIB_H)
+stack.o: $(LIB_H)
+queue.o: $(LIB_H)
+llist.o: $(LIB_H)
+
+
+clean:
+ rm -rf *.o $(PROG) $(LIB_FILE) *.dSYM
+
+backup: clean
+ cd .. ; tar czvf algdat.tar.gz algdat
diff --git a/include/options.h b/include/options.h
deleted file mode 100644
index 7e50c8f..0000000
--- a/include/options.h
+++ /dev/null
@@ -1,18 +0,0 @@
-/*
- * 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/include/oving.h b/include/oving.h
deleted file mode 100644
index f2b1dcf..0000000
--- a/include/oving.h
+++ /dev/null
@@ -1,13 +0,0 @@
-/*
- * oving.h
- * list all exercise functions
- *
- * Erik Liodden
- */
-
-#ifndef OVING_H
-#define OVING_H
-
-int oving1(void);
-
-#endif /* OVING_H */
diff --git a/src/misc/io.c b/io.c
index 7611f33..7611f33 100644
--- a/src/misc/io.c
+++ b/io.c
diff --git a/include/io.h b/io.h
index ee28320..ee28320 100644
--- a/include/io.h
+++ b/io.h
diff --git a/src/misc/list.c b/llist.c
index fc7ae7f..3c846a6 100644
--- a/src/misc/list.c
+++ b/llist.c
@@ -1,6 +1,6 @@
/*
- * list.c
- * implementation of different lists
+ * llist.c
+ * implementation of a linked list
*
* Erik Liodden
*/
@@ -8,132 +8,9 @@
#include <stdlib.h>
#include <assert.h>
#include <string.h>
-#include "list.h"
+#include "structure.h"
#include "misc.h"
-
-
-/****************************************************************************
- * Stack *
- ****************************************************************************/
-
-static void grow_stack(struct stack *s)
-{
- s->alloc_length *= 2;
- s->elems = realloc(s->elems, s->alloc_length * s->elem_size);
- assert(s->elems != NULL);
-}
-
-void stack_init(struct stack *s, size_t elem_size, void (*freefn)(void *))
-{
- s->elem_size = elem_size;
- s->log_length = 0;
- s->alloc_length = 4;
- s->elems = allocate(s->alloc_length * elem_size);
- s->freefn = freefn;
-}
-
-void stack_dispose(struct stack *s)
-{
- int i;
- if (s->freefn) {
- for (i = 0; i < s->log_length; i++)
- s->freefn((char *)s->elems + (i * s->elem_size));
- }
- free(s->elems);
-}
-
-void stack_push(struct stack *s, void *elem_addr)
-{
- if (s->log_length == s->alloc_length)
- grow_stack(s);
- void *target = (char *)s->elems + (s->log_length * s->elem_size);
- memcpy(target, elem_addr, s->elem_size);
- s->log_length++;
-}
-
-void stack_peek(struct stack *s, void *elem_addr)
-{
- assert(s->log_length > 0);
- void *source = (char *)s->elems + ((s->log_length-1) * s->elem_size);
- memcpy(elem_addr, source, s->elem_size);
-}
-
-void stack_pop(struct stack *s, void *elem_addr)
-{
- stack_peek(s, elem_addr);
- s->log_length--;
-}
-
-int stack_length(struct stack *s)
-{
- return s->log_length;
-}
-
-
-/****************************************************************************
- * Queue *
- ****************************************************************************/
-
-static void grow_queue(struct queue *q)
-{
- void *middle = (char *)q->elems + q->head * q->elem_size;
- void *end = (char *)q->elems + q->log_length * q->elem_size;
- q->head = 0;
- q->tail = q->log_length;
- q->alloc_length *= 2;
- if (q->head != 0)
- rotate(q->elems, middle, end);
- q->elems = realloc(q->elems, q->alloc_length * q->elem_size);
- assert(q->elems != NULL);
-}
-
-void queue_init(struct queue *q, size_t elem_size, void (*freefn)(void *))
-{
- q->elem_size = elem_size;
- q->head = 0;
- q->tail = 0;
- q->log_length = 0;
- q->alloc_length = 4;
- q->elems = allocate(q->alloc_length * elem_size);
- q->freefn = freefn;
-}
-
-void queue_dispose(struct queue *q)
-{
- int i;
- if (q->freefn) {
- for (i = 0; i < q->log_length; i++)
- q->freefn((char *)q->elems + (((q->head + i) %
- q->alloc_length) * q->elem_size));
- }
- free(q->elems);
-}
-
-void queue_enqueue(struct queue *q, void *elem_addr)
-{
- if (q->log_length == q->alloc_length)
- grow_queue(q);
- void *target = (char *)q->elems + (q->tail * q->elem_size);
- memcpy(target, elem_addr, q->elem_size);
- q->tail = (q->tail + 1) % q->alloc_length;
- q->log_length++;
-}
-
-void queue_dequeue(struct queue *q, void *elem_addr)
-{
- assert(q->log_length != 0);
- void *source = (char *)q->elems + (q->head * q->elem_size);
- memcpy(elem_addr, source, q->elem_size);
- q->head = (q->head + 1) % q->alloc_length;
- q->log_length--;
-}
-
-int queue_length(struct queue *q)
-{
- return q->log_length;
-}
-
static struct llist_node *create_node(void *data)
{
struct llist_node *node = malloc(sizeof(*node));
@@ -329,4 +206,3 @@ void llist_free_data_list(struct llist *list)
}
free(list);
}
-
diff --git a/src/misc/misc.c b/misc.c
index bc5a584..bc5a584 100644
--- a/src/misc/misc.c
+++ b/misc.c
diff --git a/include/misc.h b/misc.h
index 7dc7387..7dc7387 100644
--- a/include/misc.h
+++ b/misc.h
diff --git a/src/oving/oving1.c b/oving1.c
index 2233062..e295853 100644
--- a/src/oving/oving1.c
+++ b/oving1.c
@@ -8,11 +8,10 @@
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
-#include "list.h"
+#include "structure.h"
#include "io.h"
-#include "oving.h"
-int oving1(void)
+int main(void)
{
int num, max;
char buf[BUF_SIZE];
@@ -45,5 +44,5 @@ int oving1(void)
/* free memory allocated by the list */
llist_free_data_list(list);
- return max;
+ return 0;
}
diff --git a/queue.c b/queue.c
new file mode 100644
index 0000000..b34dd56
--- /dev/null
+++ b/queue.c
@@ -0,0 +1,71 @@
+/*
+ * queue.c
+ * implementation of a generic queue
+ *
+ * Erik Liodden
+ */
+
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include "structure.h"
+#include "misc.h"
+
+static void grow_queue(struct queue *q)
+{
+ void *middle = (char *)q->elems + q->head * q->elem_size;
+ void *end = (char *)q->elems + q->log_length * q->elem_size;
+ q->head = 0;
+ q->tail = q->log_length;
+ q->alloc_length *= 2;
+ if (q->head != 0)
+ rotate(q->elems, middle, end);
+ q->elems = realloc(q->elems, q->alloc_length * q->elem_size);
+ assert(q->elems != NULL);
+}
+
+void queue_init(struct queue *q, size_t elem_size, void (*freefn)(void *))
+{
+ q->elem_size = elem_size;
+ q->head = 0;
+ q->tail = 0;
+ q->log_length = 0;
+ q->alloc_length = 4;
+ q->elems = allocate(q->alloc_length * elem_size);
+ q->freefn = freefn;
+}
+
+void queue_dispose(struct queue *q)
+{
+ int i;
+ if (q->freefn) {
+ for (i = 0; i < q->log_length; i++)
+ q->freefn((char *)q->elems + (((q->head + i) %
+ q->alloc_length) * q->elem_size));
+ }
+ free(q->elems);
+}
+
+void queue_enqueue(struct queue *q, void *elem_addr)
+{
+ if (q->log_length == q->alloc_length)
+ grow_queue(q);
+ void *target = (char *)q->elems + (q->tail * q->elem_size);
+ memcpy(target, elem_addr, q->elem_size);
+ q->tail = (q->tail + 1) % q->alloc_length;
+ q->log_length++;
+}
+
+void queue_dequeue(struct queue *q, void *elem_addr)
+{
+ assert(q->log_length != 0);
+ void *source = (char *)q->elems + (q->head * q->elem_size);
+ memcpy(elem_addr, source, q->elem_size);
+ q->head = (q->head + 1) % q->alloc_length;
+ q->log_length--;
+}
+
+int queue_length(struct queue *q)
+{
+ return q->log_length;
+}
diff --git a/sort.h b/sort.h
new file mode 100644
index 0000000..a292c3c
--- /dev/null
+++ b/sort.h
@@ -0,0 +1,22 @@
+/*
+ * sort.h
+ * decleration of different sort operations
+ *
+ * Erik Liodden
+ */
+
+#ifndef SORT_H
+#define SORT_H
+
+/*
+ * insertion_sort
+ * merge_sort
+ * quick_sort
+ * heap_sort
+ * bucket_sort
+ * counting_sort
+ * radix_sort
+ */
+
+
+#endif /* SORT_H */
diff --git a/src/Makefile b/src/Makefile
deleted file mode 100644
index aaa3b3f..0000000
--- a/src/Makefile
+++ /dev/null
@@ -1,31 +0,0 @@
-CC=gcc
-OUTPUT_OPTION=-MMD -MP -o $@
-
-CFLAGS += -Wall -Wextra -O2 --std=c99 -Wvla -I../include
-MODULES := misc oving
-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
deleted file mode 100644
index 19988ba..0000000
--- a/src/main.c
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- * 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"
-#include "oving.h"
-
-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;
- default:
- print_usage();
- }
- free(options);
- return 0;
-}
diff --git a/src/misc/module.mk b/src/misc/module.mk
deleted file mode 100644
index 6bc1a20..0000000
--- a/src/misc/module.mk
+++ /dev/null
@@ -1,4 +0,0 @@
-SRC += misc/list.c
-SRC += misc/io.c
-SRC += misc/misc.c
-SRC += misc/options.c
diff --git a/src/misc/options.c b/src/misc/options.c
deleted file mode 100644
index 49cf068..0000000
--- a/src/misc/options.c
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
- * 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;
-}
-
diff --git a/src/oving/module.mk b/src/oving/module.mk
deleted file mode 100644
index 8d4fa0b..0000000
--- a/src/oving/module.mk
+++ /dev/null
@@ -1,2 +0,0 @@
-SRC += oving/oving1.c
-# SRC += oving/oving2.c
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..3d2b219
--- /dev/null
+++ b/stack.c
@@ -0,0 +1,65 @@
+/*
+ * stack.c
+ * implementation of a generic stack
+ *
+ * Erik Liodden
+ */
+
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include "structure.h"
+#include "misc.h"
+
+static void grow_stack(struct stack *s)
+{
+ s->alloc_length *= 2;
+ s->elems = realloc(s->elems, s->alloc_length * s->elem_size);
+ assert(s->elems != NULL);
+}
+
+void stack_init(struct stack *s, size_t elem_size, void (*freefn)(void *))
+{
+ s->elem_size = elem_size;
+ s->log_length = 0;
+ s->alloc_length = 4;
+ s->elems = allocate(s->alloc_length * elem_size);
+ s->freefn = freefn;
+}
+
+void stack_dispose(struct stack *s)
+{
+ int i;
+ if (s->freefn) {
+ for (i = 0; i < s->log_length; i++)
+ s->freefn((char *)s->elems + (i * s->elem_size));
+ }
+ free(s->elems);
+}
+
+void stack_push(struct stack *s, void *elem_addr)
+{
+ if (s->log_length == s->alloc_length)
+ grow_stack(s);
+ void *target = (char *)s->elems + (s->log_length * s->elem_size);
+ memcpy(target, elem_addr, s->elem_size);
+ s->log_length++;
+}
+
+void stack_peek(struct stack *s, void *elem_addr)
+{
+ assert(s->log_length > 0);
+ void *source = (char *)s->elems + ((s->log_length-1) * s->elem_size);
+ memcpy(elem_addr, source, s->elem_size);
+}
+
+void stack_pop(struct stack *s, void *elem_addr)
+{
+ stack_peek(s, elem_addr);
+ s->log_length--;
+}
+
+int stack_length(struct stack *s)
+{
+ return s->log_length;
+}
diff --git a/include/list.h b/structure.h
index 73ed377..73ed377 100644
--- a/include/list.h
+++ b/structure.h
diff --git a/structure.txt b/structure.txt
deleted file mode 100644
index 284d676..0000000
--- a/structure.txt
+++ /dev/null
@@ -1,74 +0,0 @@
-.
-|-- Makefile
-|-- README
-|-- include/
-| |-- structures.h
-| |-- tree_traversal.h
-| |-- sort.h
-| |-- search.h
-| |-- shortest_path.h
-| `-- oving.h
-|
-|-- src/
-| |-- Makefile
-| |-- main.c /* will let you select algorithm */
-| |-- structures/
-| | |-- module.mk
-| | |-- stack.c
-| | |-- queue.c
-| | |-- heap.c
-| | |-- graph.c
-| | |-- tree.c
-| | `-- list.c
-| |
-| |-- tree_traversal/
-| | |-- module.mk
-| | |-- bfs.c
-| | |-- dfs.c
-| | `-- topological_sort.c
-| |
-| |-- sort/
-| | |-- module.mk
-| | |-- comparison_sort.c
-| | |-- quick_sort.c
-| | |-- merge_sort.c
-| | |-- heap_sort.c
-| | |-- bucket_sort.c
-| | |-- counting_sort.c
-| | `-- radix_sort.c
-| |
-| |-- search/
-| | |-- module.mk
-| | |-- linear_search.c
-| | `-- binary_search.c
-| |
-| |-- shortest_path/
-| | |-- module.mk
-| | |-- djikstra.c
-| | |-- dag_shortest_path.c
-| | `-- bellman_ford.c
-| |
-| |-- max_flow/
-| | `-- module.mk
-| |
-| `-- oving/
-| |-- module.mk
-| |-- oving1.c
-| |-- oving2.c
-| |-- oving3.c
-| |-- oving4.c
-| |-- oving5.c
-| |-- oving6.c
-| |-- oving7.c
-| |-- oving8.c
-| `-- oving9.c
-|
-|-- test/
-| |-- Makefile
-| |-- structures/
-| |-- tree_traversal/
-| |-- sort/
-| |-- search/
-| |-- shortest_path/
-| |-- max_flow/
-| `-- oving/