aboutsummaryrefslogtreecommitdiffstats
AgeCommit message (Collapse)AuthorFilesLines
2018-01-18add io.h and io.cHEADmasterErik Liodden5-16/+80
i will try to collect all io based stuff in io.h and io.c. this way i won't have to reinvent the wheel every time.
2018-01-18add documentationErik Liodden2-1/+44
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
2018-01-18incude llist_destroy_node in the header fileErik Liodden1-0/+1
easy mistake. forgot to include the function prototype in structure.h
2018-01-18llist: a node points to itself after initErik Liodden1-2/+2
this makes a special case a part of the general case (yay). if the node is not part of a list it can still be used as a parameter for llist_remove_node() without giving segfaults. (it won't do anything).
2018-01-03remove io.Erik Liodden3-103/+2
this was a complete mess and wasn't used anyway. it should be rewritten. i think maybe a read_lines(char **lines, int *nlines) could be useful.
2018-01-03add oving 2Erik Liodden3-1/+117
this is the solution to oving 2. it is a heap of queues and should work(tm).
2018-01-03llist: clean up memoryErik Liodden1-8/+10
i am still not sure if remove_node should delete the node as well or if it should only remove it from the list. i will not delete it for the moment.
2018-01-03fix mismatch between prototype and implementationErik Liodden1-1/+1
2018-01-03queue: add queue peekErik Liodden2-1/+7
reveal the next element in the queue without removing it from the queue itself. similar to dequeue.
2018-01-03add heap_lengthErik Liodden2-0/+7
call heap_length to get the length of the heap. example: struct heap h; heap_length(&h); /* return length of heap */
2018-01-03remove `test` targetErik Liodden1-2/+1
and delete a.out when executing `make clean`
2017-12-10negate check on stack_getErik Liodden1-1/+1
this should be the bad conditions, not the good ones.
2017-12-04add make reinstallErik Liodden1-1/+3
this will first uninstall then install. as expected.
2017-12-04small cleanup of oving1.cErik Liodden1-4/+5
removed redundant includes and sanity check for the input file. it is more fun to just assume that the input will be on the correct format
2017-12-04structure.h is needed for heap_sortErik Liodden1-0/+2
2017-12-04add make install and make uninstallErik Liodden1-0/+14
`make install` will put the compiled library in /usr/local/lib so it can be included using -lalgdat. it will also put the library header files in /usr/local/include/algdat. to use the library use for examle: /* source.c */ #include <algdat/sort.h> ... gcc source.c -lalgdat header files available for now: sort.h io.h structures.h misc.h
2017-12-04add quick_sort.Erik Liodden2-0/+37
same prototype as the library function qsort.
2017-12-03add heap data structureErik Liodden4-11/+194
add a generic heap data structure. the heap is initialized with: struct heap h; heap_init(&h, elem_size, freefn, compar); to add elements to the heap use: heap_max_heap_insert(struct heap *h, void *key); (aka the most stupid name ever. should probably change that later.) and to get the maximum element use: heap_extract_max(struct heap *h, void *target_addr); heap_sort is implemented in heap.c and will sort an already existing array in place in O(n lg n) time. if the heap is initialized by the user (heap_init), the user must run heap_dispose() when the heap is no longer in use, to free up allocated space.
2017-12-03remove redundant header filesErik Liodden1-3/+1
string.h stdlib.h and stdio.h are not needed for now. stdlib.h probably will be when i need to allocate stuff alter (mergesort etc).
2017-12-03fix error when trying to free the sentinel twiceErik Liodden1-1/+1
the sentinel node should be freed last.
2017-12-03add insertion_sortErik Liodden3-8/+35
insertion_sort is decleared as follows: void insertion_sort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); the tricky part here is to get the compar funcion right. two examples: static int str_cmp(const void *s1, const void *s2) { char *c1 = *(char **)s1; char *c2 = *(char **)s2; return strcmp(c1, c2); } static int int_cmp(const void *s1, const void *s2) { int a = *(int *)s1; int b = *(int *)s2; return a - b; }
2017-11-30change isnumber() to isdigit()Erik Liodden1-1/+1
the code can now compile on macos and linux
2017-11-30fix call to llist_initErik Liodden1-1/+1
forgot this
2017-11-30oving1 rewritten using the new linked listErik Liodden1-20/+14
rewrote oving1 using the new and imporved linked list.
2017-11-30add test targetErik Liodden1-6/+7
`make test` will compile test.c useful for checking stuff.
2017-11-30add linked listErik Liodden2-256/+64
rewrote the linked list implementation to be more generic. important note: don't add nodes stored on the stack to the linked list yet. my poor implementation of the node_destroy method assumes that the node is created using the llist_create_node() function. create a linked list with: struct llist l; llist_init(&l); after that it is easy to create and add nodes: struct llist_node *node; node = llist_create_node(size_t elem_size, void (*freefn)(void *)); the freefn can be NULL if the element is not a pointer. to traverse the list use something like this (target is expected to be of correct type, same as elem in the node): node = l.nil; while ((node = node->next) != l.nil) { llist_get_elem(node, &target); /* do something with target */ } see structure.h for other available functions.
2017-11-30improve stackErik Liodden2-3/+28
get and replace a certain value in the stack
2017-11-16oving2 is not complete yetErik Liodden1-1/+1
2017-11-16add `make debug`Erik Liodden1-2/+5
this will first run `make clean` and then compile everything with -O0 -g compile flag
2017-11-16more compact makefileErik Liodden1-9/+8
also added more silent output
2017-11-16clean up structure.hErik Liodden1-5/+8
new header guard to reflect the name change
2017-11-16massive restructureErik Liodden20-398/+194
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.
2017-11-15clean up main and add a separate oving.hErik Liodden3-53/+15
oving.h contains the declerations of the exercises themself. not very interesting.
2017-11-15add a possible structure of the projectErik Liodden1-0/+74
just to give an idea to myself about where i am heading
2017-11-15add queue data structureErik Liodden2-0/+84
struct queue is a generic queue capable of holding an arbitrary number of elements of size elem_size. (all elements in the queue must be of the same size, but it could be pointers, so it is quite flexible). queue_init initializes a queue (preferably created by the caller on the stack). The queue is initially able to hold op to 4 elements in the queue at the same time. The elements in the queue are stored on the heap, and queue_dispose takes care of the free() calls if there is elements left on the queue. For this to work, the queue must be inititalized with a free-function accepting a void * as argument. The caller must provide this function. (note that is can, and probably should, be decleared as a statuc function at the caller). queue_enqueue takes in an adress of the variable to be put in the queue. If the queue is full, queue_enqueue will double the memory allocated to the queue. This is an expensice task, so by doubleing it, it will not happen that often. queue_dequeue expects an adress to a block of memory capable of storing the size of one element in the queue. This memory location should be provided by the caller. (initialize a variable on the stack and pass the adress of it to queue_dequeue). queue_length return the number of elements in the queue. This can also be accessed directly by the log_length field in the queue struct.
2017-11-15imporove stackErik Liodden2-4/+14
add stack_peek and stack_length functions. stack_peek places the top element of q in elem_addr (similar to stack_pop), but does not remove the element from the stack. stack_length return the logical length of the stack.
2017-11-15add more warningsErik Liodden1-1/+1
-Wextra could be useful for debugging and making good (or better) code.
2017-11-15add free function to stackErik Liodden2-5/+12
the caller specify a function to free the element. freefn is expected to be NULL if no such function is needed (the values are stored directly on the elems array)
2017-11-15restructureErik Liodden7-7/+8
put all oving files in one folder and put option under misc where it belong.
2017-11-15change to malloc wrapperErik Liodden2-3/+4
2017-11-15add basic stack functionalityErik Liodden2-0/+66
generic stack. the stack_destroy funcion must be extended to free memory the elements points to.
2017-11-15add various helper functionsErik Liodden2-0/+80
add allocate, swap and rotate.
2017-09-21add oving1 moduleErik Liodden2-0/+49
add oving1
2017-09-21add misc and general structure of the programErik Liodden11-0/+656
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.
2017-09-21add test directory from .gitignoreErik Liodden1-0/+1
the test directory is a mess. it will be added later when i have sorted out checkmk and other stuff.
2017-09-21initial commitErik Liodden2-0/+211
added README and .gitignore