diff options
34 files changed, 1818 insertions, 1735 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..eff71c7 --- /dev/null +++ b/.clang-format @@ -0,0 +1,108 @@ +--- +AccessModifierOffset: -4 +AlignAfterOpenBracket: Align +AlignConsecutiveAssignments: false +AlignConsecutiveDeclarations: false +#AlignEscapedNewlines: Left # Unknown to clang-format-4.0 +AlignOperands: true +AlignTrailingComments: false +AllowAllParametersOfDeclarationOnNextLine: false +AllowShortBlocksOnASingleLine: false +AllowShortCaseLabelsOnASingleLine: false +AllowShortFunctionsOnASingleLine: None +AllowShortIfStatementsOnASingleLine: false +AllowShortLoopsOnASingleLine: false +AlwaysBreakAfterDefinitionReturnType: None +AlwaysBreakAfterReturnType: None +AlwaysBreakBeforeMultilineStrings: false +AlwaysBreakTemplateDeclarations: false +BinPackArguments: true +BinPackParameters: true +BraceWrapping: + AfterClass: false + AfterControlStatement: false + AfterEnum: false + AfterFunction: true + AfterNamespace: true + AfterObjCDeclaration: false + AfterStruct: false + AfterUnion: false + #AfterExternBlock: false # Unknown to clang-format-5.0 + BeforeCatch: false + BeforeElse: false + IndentBraces: false + #SplitEmptyFunction: true # Unknown to clang-format-4.0 + #SplitEmptyRecord: true # Unknown to clang-format-4.0 + #SplitEmptyNamespace: true # Unknown to clang-format-4.0 +BreakBeforeBinaryOperators: None +BreakBeforeBraces: Custom +#BreakBeforeInheritanceComma: false # Unknown to clang-format-4.0 +BreakBeforeTernaryOperators: false +BreakConstructorInitializersBeforeComma: false +#BreakConstructorInitializers: BeforeComma # Unknown to clang-format-4.0 +BreakAfterJavaFieldAnnotations: false +BreakStringLiterals: false +ColumnLimit: 80 +CommentPragmas: '^ IWYU pragma:' +#CompactNamespaces: false # Unknown to clang-format-4.0 +ConstructorInitializerAllOnOneLineOrOnePerLine: false +ConstructorInitializerIndentWidth: 4 +ContinuationIndentWidth: 4 +Cpp11BracedListStyle: false +DerivePointerAlignment: false +DisableFormat: false +ExperimentalAutoDetectBinPacking: false +#FixNamespaceComments: false # Unknown to clang-format-4.0 +#IncludeBlocks: Preserve # Unknown to clang-format-5.0 + +IncludeCategories: + - Regex: '.*' + Priority: 1 +IncludeIsMainRegex: '(Test)?$' +IndentCaseLabels: false +#IndentPPDirectives: None # Unknown to clang-format-5.0 +IndentWidth: 4 +IndentWrappedFunctionNames: false +JavaScriptQuotes: Leave +JavaScriptWrapImports: true +KeepEmptyLinesAtTheStartOfBlocks: false +MacroBlockBegin: '' +MacroBlockEnd: '' +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: None +#ObjCBinPackProtocolList: Auto # Unknown to clang-format-5.0 +ObjCBlockIndentWidth: 4 +ObjCSpaceAfterProperty: true +ObjCSpaceBeforeProtocolList: true + +# Taken from git's rules +#PenaltyBreakAssignment: 10 # Unknown to clang-format-4.0 +PenaltyBreakBeforeFirstCallParameter: 30 +PenaltyBreakComment: 10 +PenaltyBreakFirstLessLess: 0 +PenaltyBreakString: 10 +PenaltyExcessCharacter: 100 +PenaltyReturnTypeOnItsOwnLine: 60 + +PointerAlignment: Right +ReflowComments: false +SortIncludes: false +#SortUsingDeclarations: false # Unknown to clang-format-4.0 +SpaceAfterCStyleCast: false +SpaceAfterTemplateKeyword: true +SpaceBeforeAssignmentOperators: true +#SpaceBeforeCtorInitializerColon: true # Unknown to clang-format-5.0 +#SpaceBeforeInheritanceColon: true # Unknown to clang-format-5.0 +SpaceBeforeParens: ControlStatements +#SpaceBeforeRangeBasedForLoopColon: true # Unknown to clang-format-5.0 +SpaceInEmptyParentheses: false +SpacesBeforeTrailingComments: 1 +SpacesInAngles: false +SpacesInContainerLiterals: false +SpacesInCStyleCastParentheses: false +SpacesInParentheses: false +SpacesInSquareBrackets: false +Standard: Cpp03 +TabWidth: 4 +UseTab: Never +... diff --git a/clang/sec6/opg3.c b/clang/sec6/opg3.c index 981b696..9fab6d9 100644 --- a/clang/sec6/opg3.c +++ b/clang/sec6/opg3.c @@ -14,7 +14,7 @@ #define BLACKWORDS (sizeof(blacklist) / sizeof(blacklist[0])) // Sorted word blacklist -char *blacklist[] = {"a", "and", "of", "the"}; +char *blacklist[] = { "a", "and", "of", "the" }; bool checkchar(char c) { @@ -37,7 +37,7 @@ int getword(char *dest, size_t max) } *w++ = tolower(c); - for ( ; --max; w++) { + for (; --max; w++) { if (!checkchar(c = getchar())) { break; } @@ -52,18 +52,18 @@ exit: bool checkword(char *w) { int l = 0; - int r = BLACKWORDS-1; + int r = BLACKWORDS - 1; while (l <= r) { - int m = (l+r)/2; + int m = (l + r) / 2; int compare = strcmp(w, blacklist[m]); if (compare == 0) { return true; } if (compare < 0) { - r = m-1; + r = m - 1; } else { - l = m+1; + l = m + 1; } } @@ -86,7 +86,7 @@ typedef struct tree_node { occur_t *occur_insert(occur_t *l, unsigned line) { - occur_t *new = (occur_t *) malloc(sizeof(occur_t)); + occur_t *new = (occur_t *)malloc(sizeof(occur_t)); new->next = l ? l->next : new; new->line = line; @@ -97,12 +97,13 @@ occur_t *occur_insert(occur_t *l, unsigned line) return new; } -void occur_print(occur_t *l) { +void occur_print(occur_t *l) +{ if (!l) { return; } occur_t *n = l->next; - for ( ; n; n = n->next) { + for (; n; n = n->next) { printf("%d ", n->line); if (n == l) { break; @@ -113,7 +114,7 @@ void occur_print(occur_t *l) { treenode_t *tree_insert(treenode_t *t, char *word, unsigned line) { if (!t) { - treenode_t *node = (treenode_t *) malloc(sizeof(treenode_t)); + treenode_t *node = (treenode_t *)malloc(sizeof(treenode_t)); strcpy(node->word, word); node->left = node->right = NULL; @@ -170,8 +171,10 @@ int main() root = tree_insert(root, word, line); // This goto can be replaced by a for loop -next_word: - if (c == '\n') { line++; } + next_word: + if (c == '\n') { + line++; + } } tree_print_words(root, longest); diff --git a/sem3/algo/lek1/merge.c b/sem3/algo/lek1/merge.c index 945b86a..f2d908a 100644 --- a/sem3/algo/lek1/merge.c +++ b/sem3/algo/lek1/merge.c @@ -8,114 +8,111 @@ void printArr(int *arr, size_t len) { - printf("{"); - for (int i = 0; i < len; i++) { - printf(" %d%s", arr[i], i+1 == len ? " " : ","); - } - printf("}\n"); + printf("{"); + for (int i = 0; i < len; i++) { + printf(" %d%s", arr[i], i + 1 == len ? " " : ","); + } + printf("}\n"); } int *genArr(size_t len, int div) { - /* Make array */ - int *arr = (int *) malloc(len * sizeof(int)); + /* Make array */ + int *arr = (int *)malloc(len * sizeof(int)); - if (arr == NULL) { - return NULL; - } + if (arr == NULL) { + return NULL; + } - /* Fill it with random */ - while (len--) { - arr[len] = div - (rand() % (div*2)); - } - - return arr; + /* Fill it with random */ + while (len--) { + arr[len] = div - (rand() % (div * 2)); + } + return arr; } int mergeSort(int *arr, size_t len) { - /* Check if len is one(then it's sorted */ - if (len <= 1) { - return 0; - } - /* Calculate array sizes */ - size_t q = len/2; - size_t rl = len-q; - - /* Make arrays */ - int *left = (int *) malloc(q * sizeof(int)); - if (left == NULL) { - return 1; - } - int *right = (int *) malloc(rl * sizeof(int)); - if (right == NULL) { - return 1; - } - - /* Copy data */ - memcpy(left, arr, q * sizeof(int)); - memcpy(right, arr + q, rl * sizeof(int)); - - /* Sort each */ - mergeSort(left, q); - mergeSort(right, rl); - - /* Merge them into arr */ - for (int i=0, j=0, k = 0; k < len; k++) { - if ( i < q && ( j == rl || left[i] <= right[j] ) ) { - arr[k] = left[ i++ ]; - } else { - arr[k] = right[ j++ ]; - } - } - - /* Free the pointers */ - free(left); - free(right); - - return 0; + /* Check if len is one(then it's sorted */ + if (len <= 1) { + return 0; + } + /* Calculate array sizes */ + size_t q = len / 2; + size_t rl = len - q; + + /* Make arrays */ + int *left = (int *)malloc(q * sizeof(int)); + if (left == NULL) { + return 1; + } + int *right = (int *)malloc(rl * sizeof(int)); + if (right == NULL) { + return 1; + } + + /* Copy data */ + memcpy(left, arr, q * sizeof(int)); + memcpy(right, arr + q, rl * sizeof(int)); + + /* Sort each */ + mergeSort(left, q); + mergeSort(right, rl); + + /* Merge them into arr */ + for (int i = 0, j = 0, k = 0; k < len; k++) { + if (i < q && (j == rl || left[i] <= right[j])) { + arr[k] = left[i++]; + } else { + arr[k] = right[j++]; + } + } + + /* Free the pointers */ + free(left); + free(right); + + return 0; } -void test(size_t len) +void test(size_t len) { - - int *a = genArr(len, len); + int *a = genArr(len, len); #if DO_PRINT == 1 - printArr(a, len); - printf("\n\n"); + printArr(a, len); + printf("\n\n"); #endif - clock_t begin = clock(); - mergeSort(a, len); - clock_t end = clock(); + clock_t begin = clock(); + mergeSort(a, len); + clock_t end = clock(); #if DO_PRINT == 1 - printArr(a, len); + printArr(a, len); #endif - clock_t diff = end - begin; - printf("Sorting %d long array took %d : %f s\n", len, diff, (double)diff/CLOCKS_PER_SEC); + clock_t diff = end - begin; + printf("Sorting %d long array took %d : %f s\n", len, diff, + (double)diff / CLOCKS_PER_SEC); - free(a); + free(a); } void bench() { + size_t len = SIZE_MAX; - size_t len = SIZE_MAX; - - srand((unsigned) time(NULL)); - for (int i = 1; i < len; i *= 2) { - test(i); - } + srand((unsigned)time(NULL)); + for (int i = 1; i < len; i *= 2) { + test(i); + } } int main(void) { + bench(); - bench(); - - return 0; + return 0; } diff --git a/sem3/algo/mm10/bfs.c b/sem3/algo/mm10/bfs.c index 6f699f0..921340f 100644 --- a/sem3/algo/mm10/bfs.c +++ b/sem3/algo/mm10/bfs.c @@ -2,170 +2,167 @@ #include <stdlib.h> #define COL_WHITE 0 -#define COL_GRAY 1 +#define COL_GRAY 1 #define COL_BLACK 2 typedef struct list_node_t_struct { - struct list_node_t_struct *next; - void *val; + struct list_node_t_struct *next; + void *val; } list_node_t; typedef struct vertex_struct { - char ref; - int color; - int dist; - struct vertex_struct *p; - list_node_t *adj; + char ref; + int color; + int dist; + struct vertex_struct *p; + list_node_t *adj; } vertex_t; vertex_t *create_vertex(char ref) { - // Get some space TODO check for null - vertex_t *v = malloc(sizeof(vertex_t)); - - // Set values - v->ref = ref; - v->color = COL_WHITE; - v->dist = -1; - v->p = NULL; - v->adj = NULL; + // Get some space TODO check for null + vertex_t *v = malloc(sizeof(vertex_t)); + + // Set values + v->ref = ref; + v->color = COL_WHITE; + v->dist = -1; + v->p = NULL; + v->adj = NULL; } vertex_t *add_adj(vertex_t *v, vertex_t *add) { - list_node_t *oldN = v->adj; + list_node_t *oldN = v->adj; - // Create new list node - list_node_t *n = malloc(sizeof(list_node_t)); - n->val = add; - n->next = oldN; + // Create new list node + list_node_t *n = malloc(sizeof(list_node_t)); + n->val = add; + n->next = oldN; - v->adj = n; + v->adj = n; - return add; + return add; } void print_adj(vertex_t *v) { - list_node_t *n = v->adj; - printf("[ "); - while (n) { - printf("%c ", *((char *)n->val)); - n = n->next; - } - printf("]\n"); + list_node_t *n = v->adj; + printf("[ "); + while (n) { + printf("%c ", *((char *)n->val)); + n = n->next; + } + printf("]\n"); } vertex_t *vertexes[128]; void add_edge(char a, char b) { - // Does a exists - if ( vertexes[a] == NULL ) { - vertexes[a] = create_vertex(a); - } - // What about b - if ( vertexes[b] == NULL ) { - vertexes[b] = create_vertex(b); - } - - // Add edge - add_adj(vertexes[a], vertexes[b]); + // Does a exists + if (vertexes[a] == NULL) { + vertexes[a] = create_vertex(a); + } + // What about b + if (vertexes[b] == NULL) { + vertexes[b] = create_vertex(b); + } + + // Add edge + add_adj(vertexes[a], vertexes[b]); } typedef struct { - unsigned int len; - list_node_t *in; - list_node_t *out; + unsigned int len; + list_node_t *in; + list_node_t *out; } queue_t; void enqueue(queue_t *q, vertex_t *v) { - list_node_t *n = malloc(sizeof(list_node_t)); - n->val = v; - - // Add at end - list_node_t *old = q->in; - q->in = n; - if ( old ) { - old->next = n; - } - - // Make sure we have an out - if ( q->out == NULL ) { - q->out = n; - } - - q->len++; + list_node_t *n = malloc(sizeof(list_node_t)); + n->val = v; + + // Add at end + list_node_t *old = q->in; + q->in = n; + if (old) { + old->next = n; + } + + // Make sure we have an out + if (q->out == NULL) { + q->out = n; + } + + q->len++; } vertex_t *dequeue(queue_t *q) { - list_node_t *n = q->out; - if ( n == NULL ) { - return NULL; - } - vertex_t *v = (vertex_t *)n->val; - - // Move out forward - q->out = n->next; - q->len--; - - // Free node and return - free(n); - return v; + list_node_t *n = q->out; + if (n == NULL) { + return NULL; + } + vertex_t *v = (vertex_t *)n->val; + + // Move out forward + q->out = n->next; + q->len--; + + // Free node and return + free(n); + return v; } void bfs(vertex_t *s) { - queue_t q = {0, NULL, NULL }; - enqueue(&q, s); - s->dist = 0; - - while ( q.len ) { - vertex_t *u = dequeue(&q); - list_node_t *n = u->adj; - while ( n ) { - vertex_t *v = (vertex_t *)n->val; - if ( v->color == COL_WHITE ) { - v->color = COL_GRAY; - v->dist = u->dist + 1; - v->p = u; - enqueue(&q, v); - } - n = n->next; - } - u->color = COL_BLACK; - } - + queue_t q = { 0, NULL, NULL }; + enqueue(&q, s); + s->dist = 0; + + while (q.len) { + vertex_t *u = dequeue(&q); + list_node_t *n = u->adj; + while (n) { + vertex_t *v = (vertex_t *)n->val; + if (v->color == COL_WHITE) { + v->color = COL_GRAY; + v->dist = u->dist + 1; + v->p = u; + enqueue(&q, v); + } + n = n->next; + } + u->color = COL_BLACK; + } } int main() { - add_edge('s', 'd'); // S - add_edge('s', 'c'); - add_edge('s', 'a'); - add_edge('d', 'e'); // D - add_edge('d', 'c'); - add_edge('e', 'g'); // E - add_edge('e', 'f'); - add_edge('c', 's'); // C - add_edge('c', 'g'); - add_edge('g', 'f'); // G - - //print_adj(vertexes['d']); - bfs(vertexes['s']); - - char c; - while ( (c = getchar()) != EOF) { - if ( vertexes[c] != NULL ) { - print_adj(vertexes[c]); - printf("%d\n", vertexes[c]->dist); - } else if (c == 10) { - } else { - printf("Not found\n"); - } - } - - + add_edge('s', 'd'); // S + add_edge('s', 'c'); + add_edge('s', 'a'); + add_edge('d', 'e'); // D + add_edge('d', 'c'); + add_edge('e', 'g'); // E + add_edge('e', 'f'); + add_edge('c', 's'); // C + add_edge('c', 'g'); + add_edge('g', 'f'); // G + + //print_adj(vertexes['d']); + bfs(vertexes['s']); + + char c; + while ((c = getchar()) != EOF) { + if (vertexes[c] != NULL) { + print_adj(vertexes[c]); + printf("%d\n", vertexes[c]->dist); + } else if (c == 10) { + } else { + printf("Not found\n"); + } + } } diff --git a/sem3/algo/mm12/dijkstra.c b/sem3/algo/mm12/dijkstra.c index b4f0f94..b4f0063 100644 --- a/sem3/algo/mm12/dijkstra.c +++ b/sem3/algo/mm12/dijkstra.c @@ -3,68 +3,68 @@ #include "graph.h" typedef struct list_item { - vertex_t *v; - struct list_item *next; - struct list_item *prev; + vertex_t *v; + struct list_item *next; + struct list_item *prev; } list_item_t; typedef struct { - int len; - struct list_item *begin; - struct list_item *end; + int len; + struct list_item *begin; + struct list_item *end; } list_t; void list_push(list_t *s, vertex_t *v) { - // Create - list_item_t *i = malloc(sizeof(list_item_t)); - i->next = NULL; - i->prev = NULL; - i->v = v; - - // Link - if ( s->len == 0 ) { - s->begin = i; - } else { - s->end->next = i; - i->prev = s->end; - } - - s->end = i; - s->len++; + // Create + list_item_t *i = malloc(sizeof(list_item_t)); + i->next = NULL; + i->prev = NULL; + i->v = v; + + // Link + if (s->len == 0) { + s->begin = i; + } else { + s->end->next = i; + i->prev = s->end; + } + + s->end = i; + s->len++; } vertex_t *list_pop_smallest(list_t *s) { - list_item_t *smallest = s->begin; - - // Search - list_item_t *i = s->begin; - while ( i ) { - if ( i->v->dist != -1 && i->v->dist < smallest->v->dist ) { - smallest = i; - } - i = i->next; - } - - if ( smallest == s->begin ) { - s->begin = smallest->next; - } else { - smallest->prev->next = smallest->next; - } - - if ( smallest == s->end ) { - s->end = smallest->prev; - } else { - smallest->next->prev = smallest->prev; - } - - vertex_t *v = smallest->v; - free(smallest); - - s->len--; - - return v; + list_item_t *smallest = s->begin; + + // Search + list_item_t *i = s->begin; + while (i) { + if (i->v->dist != -1 && i->v->dist < smallest->v->dist) { + smallest = i; + } + i = i->next; + } + + if (smallest == s->begin) { + s->begin = smallest->next; + } else { + smallest->prev->next = smallest->next; + } + + if (smallest == s->end) { + s->end = smallest->prev; + } else { + smallest->next->prev = smallest->prev; + } + + vertex_t *v = smallest->v; + free(smallest); + + s->len--; + + return v; } graph_t g; @@ -72,66 +72,65 @@ graph_t g; // Assumes u has an edge to v void relax(vertex_t *u, vertex_t *v) { - // Get edge between these two guys - edge_t *e = u->adj; - while (e && e->next && e->to->ref != v->ref) { - e = e->next; - } - - if ( v->dist == -1 || v->dist > (u->dist + e->weight) ) { - v->dist = u->dist + e->weight; - v->p = u; - } + // Get edge between these two guys + edge_t *e = u->adj; + while (e && e->next && e->to->ref != v->ref) { + e = e->next; + } + + if (v->dist == -1 || v->dist > (u->dist + e->weight)) { + v->dist = u->dist + e->weight; + v->p = u; + } } void dijkstra(graph_t *g, vertex_t *s) { - list_t list; - list.len = 0; - list.end = list.begin = 0; - - s->dist = 0; - - { - vertex_t *v = vertex_next(g, NULL); - while ( v ) { - list_push(&list, v); - v = vertex_next(g, v); - } - } - - while ( list.len ) { - vertex_t *u = list_pop_smallest(&list); - edge_t *e = u->adj; - while( e ) { - relax(u, e->to ); - e = e->next; - } - } + list_t list; + list.len = 0; + list.end = list.begin = 0; + + s->dist = 0; + + { + vertex_t *v = vertex_next(g, NULL); + while (v) { + list_push(&list, v); + v = vertex_next(g, v); + } + } + + while (list.len) { + vertex_t *u = list_pop_smallest(&list); + edge_t *e = u->adj; + while (e) { + relax(u, e->to); + e = e->next; + } + } } int main() { + graph_edge(&g, 'a', 'b', 2); + graph_edge(&g, 'a', 'f', 1); - graph_edge(&g, 'a', 'b', 2); - graph_edge(&g, 'a', 'f', 1); + graph_edge(&g, 'b', 'd', 3); + graph_edge(&g, 'b', 'c', 4); - graph_edge(&g, 'b', 'd', 3); - graph_edge(&g, 'b', 'c', 4); + graph_edge(&g, 'd', 'b', 1); + graph_edge(&g, 'd', 'e', 8); - graph_edge(&g, 'd', 'b', 1); - graph_edge(&g, 'd', 'e', 8); + graph_edge(&g, 'c', 'a', 7); + graph_edge(&g, 'c', 'd', 7); + graph_edge(&g, 'c', 'f', 2); - graph_edge(&g, 'c', 'a', 7); - graph_edge(&g, 'c', 'd', 7); - graph_edge(&g, 'c', 'f', 2); + graph_edge(&g, 'e', 'c', 2); + graph_edge(&g, 'e', 'f', 2); - graph_edge(&g, 'e', 'c', 2); - graph_edge(&g, 'e', 'f', 2); + dijkstra(&g, g.vertexes['a']); - dijkstra(&g, g.vertexes['a']); + graph_to_dot(stdout, &g); - graph_to_dot(stdout, &g); - - return 0; + return 0; } diff --git a/sem3/algo/mm12/graph.c b/sem3/algo/mm12/graph.c index e478103..f4039ec 100644 --- a/sem3/algo/mm12/graph.c +++ b/sem3/algo/mm12/graph.c @@ -4,127 +4,129 @@ static vertex_t *create_vertex(char ref) { - // Get some space TODO check for null - vertex_t *v = malloc(sizeof(vertex_t)); - - // Set values - v->ref = ref; - v->dist = -1; - v->p = NULL; - v->adj = NULL; - return v; + // Get some space TODO check for null + vertex_t *v = malloc(sizeof(vertex_t)); + + // Set values + v->ref = ref; + v->dist = -1; + v->p = NULL; + v->adj = NULL; + return v; } static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) { - edge_t *old = from->adj; - - // Create new list node - edge_t *e = malloc(sizeof(edge_t)); - e->weight = weight; - e->from = from; - e->to = to; - - // Do new link - e->next = old; - if ( old ) { - e->prev = old->prev; - old->prev = e; - } else { e->prev = NULL; } - - if ( e->prev ) { - e->prev->next = e; - } - - from->adj = e; - - return e; + edge_t *old = from->adj; + + // Create new list node + edge_t *e = malloc(sizeof(edge_t)); + e->weight = weight; + e->from = from; + e->to = to; + + // Do new link + e->next = old; + if (old) { + e->prev = old->prev; + old->prev = e; + } else { + e->prev = NULL; + } + + if (e->prev) { + e->prev->next = e; + } + + from->adj = e; + + return e; } // For iterating edges edge_t *edge_next(graph_t *g, edge_t *e) { - if (e == NULL || e->next == NULL ) { - // Find next index - - // Chose starting index 0 if NULL e - unsigned char i = e ? e->from->ref+1 : 0; - for ( ; i < 128; i++ ) { - if ( g->vertexes[i] && g->vertexes[i]->adj ) { - return g->vertexes[i]->adj; - } - } - // No next vertex - return NULL; - } - - // Not finished with this adj list - return e->next; + if (e == NULL || e->next == NULL) { + // Find next index + + // Chose starting index 0 if NULL e + unsigned char i = e ? e->from->ref + 1 : 0; + for (; i < 128; i++) { + if (g->vertexes[i] && g->vertexes[i]->adj) { + return g->vertexes[i]->adj; + } + } + // No next vertex + return NULL; + } + + // Not finished with this adj list + return e->next; } vertex_t *vertex_next(graph_t *g, vertex_t *v) { - unsigned char ref = v ? v->ref+1 : 0; - for ( ; ref < 128; ref++ ) { - if ( g->vertexes[ref] ) { - return g->vertexes[ref]; - } - } - - return NULL; + unsigned char ref = v ? v->ref + 1 : 0; + for (; ref < 128; ref++) { + if (g->vertexes[ref]) { + return g->vertexes[ref]; + } + } + + return NULL; } void graph_edge(graph_t *g, char from, char to, int weight) { - // Does a exists - if ( g->vertexes[from] == NULL ) { - g->vertexes[from] = create_vertex(from); - } - // What about b - if ( g->vertexes[to] == NULL ) { - g->vertexes[to] = create_vertex(to); - } - - // Add edge - create_edge(g->vertexes[from], g->vertexes[to], weight); + // Does a exists + if (g->vertexes[from] == NULL) { + g->vertexes[from] = create_vertex(from); + } + // What about b + if (g->vertexes[to] == NULL) { + g->vertexes[to] = create_vertex(to); + } + + // Add edge + create_edge(g->vertexes[from], g->vertexes[to], weight); } int graph_print_adj(graph_t *g, char ref) { - if ( g->vertexes[ref] == NULL ) { - return 1; - } - - edge_t *e = g->vertexes[ref]->adj; - printf("[ "); - while (e && e->from->ref == ref) { - printf("%c[%d] ", e->to->ref, e->weight); - e = e->next; - } - printf("]\n"); - - return 0; + if (g->vertexes[ref] == NULL) { + return 1; + } + + edge_t *e = g->vertexes[ref]->adj; + printf("[ "); + while (e && e->from->ref == ref) { + printf("%c[%d] ", e->to->ref, e->weight); + e = e->next; + } + printf("]\n"); + + return 0; } int graph_to_dot(FILE *f, graph_t *g) { - // print pre stuff - fprintf(f, "digraph coolgraph {\n"); - - // Label all nodes - vertex_t *v = vertex_next(g, NULL); - while ( v ) { - fprintf(f, "%c [label=\"%c(%d)\"];\n", v->ref, v->ref, v->dist); - v = vertex_next(g, v); - } - // Print all the edges - edge_t *e = edge_next(g, NULL); - while ( e ) { - fprintf(f, "%c -> %c [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : ""); - e = edge_next(g, e); - } - - // done - fprintf(f, "}\n"); + // print pre stuff + fprintf(f, "digraph coolgraph {\n"); + + // Label all nodes + vertex_t *v = vertex_next(g, NULL); + while (v) { + fprintf(f, "%c [label=\"%c(%d)\"];\n", v->ref, v->ref, v->dist); + v = vertex_next(g, v); + } + // Print all the edges + edge_t *e = edge_next(g, NULL); + while (e) { + fprintf(f, "%c -> %c [label = %d%s];\n", e->from->ref, e->to->ref, + e->weight, e->to->p == e->from ? " color=blue" : ""); + e = edge_next(g, e); + } + + // done + fprintf(f, "}\n"); } - diff --git a/sem3/algo/mm12/graph.h b/sem3/algo/mm12/graph.h index e957c4d..f4f2c8f 100644 --- a/sem3/algo/mm12/graph.h +++ b/sem3/algo/mm12/graph.h @@ -5,23 +5,23 @@ struct vertex_struct; // Linked list typedef struct edge_struct { - int weight; - struct vertex_struct *from; - struct vertex_struct *to; - // Linked list stuff - struct edge_struct *next; - struct edge_struct *prev; + int weight; + struct vertex_struct *from; + struct vertex_struct *to; + // Linked list stuff + struct edge_struct *next; + struct edge_struct *prev; } edge_t; typedef struct vertex_struct { - char ref; - int dist; - struct vertex_struct *p; - edge_t *adj; + char ref; + int dist; + struct vertex_struct *p; + edge_t *adj; } vertex_t; typedef struct { - vertex_t *vertexes[128]; + vertex_t *vertexes[128]; } graph_t; diff --git a/sem3/algo/mm2/linked/llist.c b/sem3/algo/mm2/linked/llist.c index 8044e0b..e4166ee 100644 --- a/sem3/algo/mm2/linked/llist.c +++ b/sem3/algo/mm2/linked/llist.c @@ -3,92 +3,89 @@ #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; + /* 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); + /* 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; - } + /* Check if was list is empty */ + if (list->len == 0) { + /* Set root */ + list->root = list->head; + } - /* Increase count */ - list->len++; + /* 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; + /* 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; + /* 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); + /* 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/sem3/algo/mm2/linked/llist.h b/sem3/algo/mm2/linked/llist.h index e52be89..14130c4 100644 --- a/sem3/algo/mm2/linked/llist.h +++ b/sem3/algo/mm2/linked/llist.h @@ -4,9 +4,9 @@ #include "node.h" typedef struct { - node_t *root; - node_t *head; - unsigned int len; + node_t *root; + node_t *head; + unsigned int len; } llist_t; void llist_init(llist_t *list); @@ -19,4 +19,4 @@ int llist_get(llist_t *list, unsigned int index); int llist_pop(llist_t *list, unsigned int index); -#endif +#endif diff --git a/sem3/algo/mm2/linked/main.c b/sem3/algo/mm2/linked/main.c index 6f4eb6a..8637796 100644 --- a/sem3/algo/mm2/linked/main.c +++ b/sem3/algo/mm2/linked/main.c @@ -4,44 +4,43 @@ 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); + 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; - } + /* Next value */ + root = root->next; + } } /* Remove node */ int main() { - - /* Do some stuff */ - llist_t list; - llist_init(&list); + /* 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 + 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); + printf("%d\n", llist_get(&list, 5)); + llist_pop(&list, 9); + printf("%d\n", llist_get(&list, 7)); - list_print(list.root); + list_print(list.root); - while ( list.len ) { - printf("Popped %d\n", llist_pop(&list, 0)); - } + while (list.len) { + printf("Popped %d\n", llist_pop(&list, 0)); + } } diff --git a/sem3/algo/mm2/linked/node.c b/sem3/algo/mm2/linked/node.c index 21f0993..87f2e4c 100644 --- a/sem3/algo/mm2/linked/node.c +++ b/sem3/algo/mm2/linked/node.c @@ -6,54 +6,53 @@ /* 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; + /* 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; + int val = node->val; - /* Check prev */ - if ( node->prev != NULL ) { - /* Point last node to next node */ - node->prev->next = node->next; - } + /* 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; - } + /* Check next */ + if (node->next != NULL) { + node->next->prev = node->prev; + } - /* Free memory */ - free(node); + /* Free memory */ + free(node); - return val; + return val; } diff --git a/sem3/algo/mm2/linked/node.h b/sem3/algo/mm2/linked/node.h index 027926b..27f29c6 100644 --- a/sem3/algo/mm2/linked/node.h +++ b/sem3/algo/mm2/linked/node.h @@ -2,9 +2,9 @@ #define NODE_H typedef struct node_struct { - int val; - struct node_struct *next; - struct node_struct *prev; + int val; + struct node_struct *next; + struct node_struct *prev; } node_t; /** @brief Create a new node after specified node @@ -20,4 +20,4 @@ node_t *node_insert(node_t *node, int val); */ int node_pop(node_t *node); -#endif +#endif diff --git a/sem3/algo/mm2/queue.c b/sem3/algo/mm2/queue.c index a574acb..ef9309e 100644 --- a/sem3/algo/mm2/queue.c +++ b/sem3/algo/mm2/queue.c @@ -7,99 +7,98 @@ /* Queue stuff */ typedef struct { - int head; - int tail; - int len; - int cap; - int *buff; + int head; + int tail; + int len; + int cap; + int *buff; } queue_t; /* Queue functions */ int queue_init(queue_t *q, size_t cap) { - /* Make the struct and set i to zero */ - memset(q, 0, sizeof(queue_t)); - - /* Allocate the buffer */ - q->buff = (int *) malloc(cap * sizeof(int)); - if ( q->buff == NULL ) { - return 1; - } - - /* Set capacity, the rest should be zero form memset */ - q->cap = cap; - return 0; + /* Make the struct and set i to zero */ + memset(q, 0, sizeof(queue_t)); + + /* Allocate the buffer */ + q->buff = (int *)malloc(cap * sizeof(int)); + if (q->buff == NULL) { + return 1; + } + + /* Set capacity, the rest should be zero form memset */ + q->cap = cap; + return 0; } void queue_free(queue_t *q) { - /* Free the heap buffer */ - free(q->buff); + /* Free the heap buffer */ + free(q->buff); } int queue_place(queue_t *q, int val) { - /* Check if full */ - printf("len: %d\n", q->len); - if ( q->len >= q->cap) { - printf("ERR: Full\n"); - return EFULL; - } - - /* Add to queue */ - q->buff[q->head] = val; - - /* Increase values */ - q->head = (q->head+1) % q->cap; - q->len++; - - return 0; + /* Check if full */ + printf("len: %d\n", q->len); + if (q->len >= q->cap) { + printf("ERR: Full\n"); + return EFULL; + } + + /* Add to queue */ + q->buff[q->head] = val; + + /* Increase values */ + q->head = (q->head + 1) % q->cap; + q->len++; + + return 0; } int queue_get(queue_t *q, int *val) { - /* Check if empty */ - if ( !q->len ) { - printf("ERR: Empty\n"); - return EMPTY; - } - - /* Read value */ - if ( val != NULL ){ - *val = q->buff[q->tail]; - } - - /* Decrease values */ - q->tail = (q->tail+1) % q->cap; - q->len--; - - return 0; + /* Check if empty */ + if (!q->len) { + printf("ERR: Empty\n"); + return EMPTY; + } + + /* Read value */ + if (val != NULL) { + *val = q->buff[q->tail]; + } + + /* Decrease values */ + q->tail = (q->tail + 1) % q->cap; + q->len--; + + return 0; } int main(void) { - int in; - char com; - - queue_t q; - queue_init(&q, 16); - - for (;;) { - /* Read a command */ - scanf("%c", &com); - - if ( com == 'w') { - printf("> "); - scanf("%d", &in); - queue_place(&q, in); - } else if ( com == 'r' ) { - queue_get(&q, &in); - printf("%d\n", in); - } else if ( com == 'q' ) { - break; - } - } - - queue_free(&q); - + int in; + char com; + + queue_t q; + queue_init(&q, 16); + + for (;;) { + /* Read a command */ + scanf("%c", &com); + + if (com == 'w') { + printf("> "); + scanf("%d", &in); + queue_place(&q, in); + } else if (com == 'r') { + queue_get(&q, &in); + printf("%d\n", in); + } else if (com == 'q') { + break; + } + } + + queue_free(&q); } diff --git a/sem3/algo/mm3/multiply.c b/sem3/algo/mm3/multiply.c index da8068c..d931000 100644 --- a/sem3/algo/mm3/multiply.c +++ b/sem3/algo/mm3/multiply.c @@ -5,54 +5,53 @@ uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) { - /* Check if they expect more than 64 bits. */ - if ( bits > 64 ) { - printf("Sorry we cant handle higher than 64 bits\n"); - exit(1); - } else if (bits <= 1) { - return x && y; - } + /* Check if they expect more than 64 bits. */ + if (bits > 64) { + printf("Sorry we cant handle higher than 64 bits\n"); + exit(1); + } else if (bits <= 1) { + return x && y; + } - unsigned int newBits = bits >> 1; + unsigned int newBits = bits >> 1; #if DO_PRINT == 1 - printf("\n\n bits: %u, New bits: %u\n", bits, newBits); -#endif + printf("\n\n bits: %u, New bits: %u\n", bits, newBits); +#endif - /* Split up into to */ - uint32_t halvMask = ((uint64_t)1 << newBits) - 1; + /* Split up into to */ + uint32_t halvMask = ((uint64_t)1 << newBits) - 1; #if DO_PRINT == 1 - printf("Using mask 0x%08X\n", halvMask); -#endif - uint32_t a = (x >> (newBits)) & halvMask; - uint32_t b = x & halvMask; - uint32_t c = (y >> (newBits)) & halvMask; - uint32_t d = y & halvMask; + printf("Using mask 0x%08X\n", halvMask); +#endif + uint32_t a = (x >> (newBits)) & halvMask; + uint32_t b = x & halvMask; + uint32_t c = (y >> (newBits)) & halvMask; + uint32_t d = y & halvMask; #if DO_PRINT == 1 - printf("A: 0x%08X, B: 0x%08X, C: 0x%08X, D: 0x%08X\n", a, b, c, d); -#endif - - return (mult(a, c, newBits) << bits) + ((mult(a, d, newBits) + mult(b, c, newBits)) << newBits) + mult(b, d, newBits); + printf("A: 0x%08X, B: 0x%08X, C: 0x%08X, D: 0x%08X\n", a, b, c, d); +#endif + return (mult(a, c, newBits) << bits) + + ((mult(a, d, newBits) + mult(b, c, newBits)) << newBits) + + mult(b, d, newBits); } - int main(void) { + uint32_t a = 0xFFFFFF; + uint8_t b = 55; + uint64_t res; - uint32_t a = 0xFFFFFF; - uint8_t b = 55; - uint64_t res; + clock_t begin = clock(); + res = mult(a, b, 64); + clock_t end = clock(); - clock_t begin = clock(); - res = mult(a, b, 64); - clock_t end = clock(); + printf("Result: %lld\n", res); - printf("Result: %lld\n", res); + clock_t diff = end - begin; + printf("Took %d which is %f s\n", diff, (double)diff / CLOCKS_PER_SEC); - clock_t diff = end - begin; - printf("Took %d which is %f s\n", diff, (double)diff/CLOCKS_PER_SEC); - - return 0; + return 0; } diff --git a/sem3/algo/mm6/main.c b/sem3/algo/mm6/main.c index a93571e..be1b2a4 100644 --- a/sem3/algo/mm6/main.c +++ b/sem3/algo/mm6/main.c @@ -4,35 +4,33 @@ int main() { - tree_t t; - t.root = 0; + tree_t t; + t.root = 0; - node_t *a = tree_insert(&t, 1, "Hej"); + node_t *a = tree_insert(&t, 1, "Hej"); - node_t *b = tree_insert(&t, 3, "med"); + node_t *b = tree_insert(&t, 3, "med"); - tree_insert(&t, 11, "dig"); - tree_insert(&t, 9, "dig"); - tree_insert(&t, 12, "dig"); + tree_insert(&t, 11, "dig"); + tree_insert(&t, 9, "dig"); + tree_insert(&t, 12, "dig"); - tree_insert(&t, 10, "hvordan"); + tree_insert(&t, 10, "hvordan"); - tree_insert(&t, 8, "det"); + tree_insert(&t, 8, "det"); - tree_insert(&t, 4, "branch"); + tree_insert(&t, 4, "branch"); - tree_insert(&t, 5, "2"); + tree_insert(&t, 5, "2"); + tree_insert(&t, 0, "Og den sidste"); - tree_insert(&t, 0, "Og den sidste"); - - tree_insert(&t, 2, "Cool nok"); - tree_print(&t); - - printf("%s\n", tree_search(&t, 10)); - printf("%s\n", tree_search(&t, 11)); - printf("%s\n", tree_search(&t, 1)); - printf("%s\n", tree_search(&t, 0)); - printf("%s\n", tree_search(&t, 99)); + tree_insert(&t, 2, "Cool nok"); + tree_print(&t); + printf("%s\n", tree_search(&t, 10)); + printf("%s\n", tree_search(&t, 11)); + printf("%s\n", tree_search(&t, 1)); + printf("%s\n", tree_search(&t, 0)); + printf("%s\n", tree_search(&t, 99)); } diff --git a/sem3/algo/mm6/tree.c b/sem3/algo/mm6/tree.c index 4d58309..89b6bbe 100644 --- a/sem3/algo/mm6/tree.c +++ b/sem3/algo/mm6/tree.c @@ -6,161 +6,158 @@ static node_t *create_node(unsigned int index, char *val) { - node_t *node = malloc( sizeof(node_t) ); - memset(node, 0, sizeof(node_t)); + node_t *node = malloc(sizeof(node_t)); + memset(node, 0, sizeof(node_t)); - node->value = val; - node->index = index; + node->value = val; + node->index = index; } /* Comments are based of dir = CHILD_LEFT */ void node_rotate(tree_t *tree, node_t *x, int dir) { - /* Node below which we should rotate with */ - node_t *y = x->children[!dir]; - - /* Move y's left to x's right */ - x->children[!dir] = y->children[dir]; - - /* Update parent */ - if ( y->children[dir] ) { - y->children[dir]->p = x; - } - - /* Switch around x and y */ - y->p = x->p; - - /* Check if y is new root if not update x's parent */ - if ( !y->p ) { - tree->root = y; - } else if ( x == x->p->children[CHILD_LEFT]) { - x->p->children[CHILD_LEFT] = y; - } else { - x->p->children[CHILD_RIGHT] = y; - } - - /* Update y's ref */ - y->children[dir] = x; - x->p = y; - + /* Node below which we should rotate with */ + node_t *y = x->children[!dir]; + + /* Move y's left to x's right */ + x->children[!dir] = y->children[dir]; + + /* Update parent */ + if (y->children[dir]) { + y->children[dir]->p = x; + } + + /* Switch around x and y */ + y->p = x->p; + + /* Check if y is new root if not update x's parent */ + if (!y->p) { + tree->root = y; + } else if (x == x->p->children[CHILD_LEFT]) { + x->p->children[CHILD_LEFT] = y; + } else { + x->p->children[CHILD_RIGHT] = y; + } + + /* Update y's ref */ + y->children[dir] = x; + x->p = y; } static void insert_fixup(tree_t *tree, node_t *z) { - while ( z->p && z->p->black == false ) { - /* Set the right direction */ - int dir = (z->p == z->p->p->children[CHILD_LEFT]) ? CHILD_RIGHT : CHILD_LEFT; - - /* Get uncle */ - node_t *y = z->p->p->children[dir]; - if ( y && !y->black ) { - /* Case 1 */ - z->p->black = true; - y->black = true; - z->p->p->black = false; - - z = z->p->p; - } else if ( z == z->p->children[dir] ) { - /* Case 2 */ - z = z->p; - node_rotate(tree, z, !dir); - } else { - /* Case 3 */ - z->p->black = true; - z->p->p->black = false; - node_rotate(tree, z->p->p, dir); - } - } - - tree->root->black = true; - + while (z->p && z->p->black == false) { + /* Set the right direction */ + int dir = + (z->p == z->p->p->children[CHILD_LEFT]) ? CHILD_RIGHT : CHILD_LEFT; + + /* Get uncle */ + node_t *y = z->p->p->children[dir]; + if (y && !y->black) { + /* Case 1 */ + z->p->black = true; + y->black = true; + z->p->p->black = false; + + z = z->p->p; + } else if (z == z->p->children[dir]) { + /* Case 2 */ + z = z->p; + node_rotate(tree, z, !dir); + } else { + /* Case 3 */ + z->p->black = true; + z->p->p->black = false; + node_rotate(tree, z->p->p, dir); + } + } + + tree->root->black = true; } static node_t *insert_recur(node_t *node, unsigned int index, char *val) { - int dir = node->index < index ? CHILD_RIGHT : CHILD_LEFT; + int dir = node->index < index ? CHILD_RIGHT : CHILD_LEFT; - if ( node->children[dir] ) { - return insert_recur(node->children[dir], index, val); - } + if (node->children[dir]) { + return insert_recur(node->children[dir], index, val); + } - /* Found stop */ - node_t *new = create_node(index, val); - new->p = node; - node->children[dir] = new; + /* Found stop */ + node_t *new = create_node(index, val); + new->p = node; + node->children[dir] = new; - return new; + return new; } node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val) { - if ( !tree->root ) { - tree->root = create_node(index, val); - return tree->root; - } + if (!tree->root) { + tree->root = create_node(index, val); + return tree->root; + } - return insert_recur(tree->root, index, val); + return insert_recur(tree->root, index, val); } node_t *tree_insert(tree_t *tree, unsigned int index, char *val) { - if ( !tree->root ) { - tree->root = create_node(index, val); - tree->root->black = true; - return tree->root; - } + if (!tree->root) { + tree->root = create_node(index, val); + tree->root->black = true; + return tree->root; + } - node_t *new = insert_recur(tree->root, index, val); - insert_fixup(tree, new); + node_t *new = insert_recur(tree->root, index, val); + insert_fixup(tree, new); - return new; + return new; } char *tree_search(tree_t *tree, unsigned int index) { - node_t *z = tree->root; - while ( z->index != index ) { - z = z->children[z->index < index ? CHILD_RIGHT : CHILD_LEFT]; - if ( !z ) { - return NULL; - } - } - - return z->value; + node_t *z = tree->root; + while (z->index != index) { + z = z->children[z->index < index ? CHILD_RIGHT : CHILD_LEFT]; + if (!z) { + return NULL; + } + } + + return z->value; } static inline void print_indent(int num) { - for ( int i = 0; i < num; i++ ) { - printf(" "); - } + for (int i = 0; i < num; i++) { + printf(" "); + } } static inline void print_text(node_t *node, bool bold) { - if ( bold ) { - printf("\033[1m%d\033[22m\n", node->index); - } else { - printf("%d\n", node->index); - } - + if (bold) { + printf("\033[1m%d\033[22m\n", node->index); + } else { + printf("%d\n", node->index); + } } static void print_recur(node_t *node, int ident) { - if ( !node ) { - return; - } - print_recur(node->children[CHILD_RIGHT], ident+1); - - print_indent(ident); - print_text(node, node->black); - - print_recur(node->children[CHILD_LEFT], ident+1); + if (!node) { + return; + } + print_recur(node->children[CHILD_RIGHT], ident + 1); + + print_indent(ident); + print_text(node, node->black); + + print_recur(node->children[CHILD_LEFT], ident + 1); } void tree_print(tree_t *tree) { - print_recur(tree->root, 0); + print_recur(tree->root, 0); } - diff --git a/sem3/algo/mm6/tree.h b/sem3/algo/mm6/tree.h index 0d1c5c6..d94304f 100644 --- a/sem3/algo/mm6/tree.h +++ b/sem3/algo/mm6/tree.h @@ -6,16 +6,16 @@ #define CHILD_LEFT 0 #define CHILD_RIGHT 1 -typedef struct node_struct{ - struct node_struct *p; - struct node_struct *children[2]; - unsigned int index; - bool black; - char *value; +typedef struct node_struct { + struct node_struct *p; + struct node_struct *children[2]; + unsigned int index; + bool black; + char *value; } node_t; typedef struct { - node_t *root; + node_t *root; } tree_t; void tree_print(tree_t *tree); @@ -27,5 +27,4 @@ void node_rotate(tree_t *tree, node_t *x, int dir); char *tree_search(tree_t *tree, unsigned int index); - -#endif +#endif diff --git a/sem3/algo/workshop2/dfs/dfs.c b/sem3/algo/workshop2/dfs/dfs.c index aa80519..b2ce82b 100644 --- a/sem3/algo/workshop2/dfs/dfs.c +++ b/sem3/algo/workshop2/dfs/dfs.c @@ -12,99 +12,97 @@ int step; void dfs_visit(graph_t *g, vertex_t *u, bool doprint) { - if ( doprint ) { - printf("dfs_visit( %s )\n", u->ref); - } - step++; - u->dtime = step; - u->color = COLOR_GRAY; - - // For every adj - edge_t *e = u->adj; - while ( e ) { - vertex_t *v = e->to; - if ( v->color == COLOR_WHITE ) { - graph_edge(&newg, v->ref, u->ref, 1); - dfs_visit(g, v, doprint); - } - e = e->next; - } - - u->color = COLOR_BLACK; - step++; - u->ftime = step; + if (doprint) { + printf("dfs_visit( %s )\n", u->ref); + } + step++; + u->dtime = step; + u->color = COLOR_GRAY; + + // For every adj + edge_t *e = u->adj; + while (e) { + vertex_t *v = e->to; + if (v->color == COLOR_WHITE) { + graph_edge(&newg, v->ref, u->ref, 1); + dfs_visit(g, v, doprint); + } + e = e->next; + } + + u->color = COLOR_BLACK; + step++; + u->ftime = step; } - void dfs(graph_t *g, bool doprint) { - step = 0; - - // For every edge - vertex_t *u = vertex_next(g, NULL); - while ( u ) { - if ( u->color == COLOR_WHITE ) { - dfs_visit(g, u, doprint); - } - u = vertex_next(g, u); - } + step = 0; + + // For every edge + vertex_t *u = vertex_next(g, NULL); + while (u) { + if (u->color == COLOR_WHITE) { + dfs_visit(g, u, doprint); + } + u = vertex_next(g, u); + } } #define BENCH 9999 int main() { + // benchmark + + // Start by generating + for (int i = 0; i < BENCH; i++) { + char from[5]; + char to[5]; + sprintf(from, "%d", i); + sprintf(to, "%d", rand() % BENCH); + graph_edge(&g, from, to, 1); + } + FILE *f = fopen("hej.dot", "w"); + graph_to_dot(f, &g); + + { + // Timing start + clock_t t; + t = clock(); + + dfs(&g, true); + + // Timing stop + t = clock() - t; + double time_taken = ((double)t) / CLOCKS_PER_SEC; // in seconds + printf("Dfs took %f seconds\n", time_taken); + } + + return 0; + + graph_edge(&g, "hej", "med", 1); + graph_edge(&g, "med", "dig", 1); + graph_edge(&g, "dig", "hvordan", 1); + + graph_edge(&g, "det", "hvordan", 1); + graph_edge(&g, "hvordan", "det", 1); + + graph_to_dot(stdout, &g); + + // Timing start + clock_t t; + t = clock(); + + // Dfs slower when printing. + dfs(&g, true); + + // Timing stop + t = clock() - t; + double time_taken = ((double)t) / CLOCKS_PER_SEC; // in seconds + printf("Dfs took %f seconds\n", time_taken); + + //graph_to_dot(stdout, &newg); - // benchmark - - // Start by generating - for (int i = 0; i < BENCH; i++) { - char from[5]; - char to[5]; - sprintf(from, "%d", i); - sprintf(to, "%d", rand() % BENCH); - graph_edge(&g, from, to, 1); - } - FILE *f = fopen("hej.dot", "w"); - graph_to_dot(f, &g); - - { - // Timing start - clock_t t; - t = clock(); - - dfs(&g, true); - - // Timing stop - t = clock() - t; - double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds - printf("Dfs took %f seconds\n", time_taken); - } - - return 0; - - graph_edge(&g, "hej", "med", 1); - graph_edge(&g, "med", "dig", 1); - graph_edge(&g, "dig", "hvordan", 1); - - graph_edge(&g, "det", "hvordan", 1); - graph_edge(&g, "hvordan", "det", 1); - - graph_to_dot(stdout, &g); - - // Timing start - clock_t t; - t = clock(); - - // Dfs slower when printing. - dfs(&g, true); - - // Timing stop - t = clock() - t; - double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds - printf("Dfs took %f seconds\n", time_taken); - - //graph_to_dot(stdout, &newg); - - return 0; + return 0; } diff --git a/sem3/algo/workshop2/dfs/graph.c b/sem3/algo/workshop2/dfs/graph.c index 0ad4467..c1bf871 100644 --- a/sem3/algo/workshop2/dfs/graph.c +++ b/sem3/algo/workshop2/dfs/graph.c @@ -8,186 +8,185 @@ // Hashtable static unsigned int hash(char *s) { - uint32_t hv = 0; - for( int i = 0; s[i] != '\0'; i++ ) { - // take MSB 6 bits of hv and xors with LSB of s[i] - uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f); - - // Push those back on hv - hv = (hv << 4) | v; - } - // Return appropriate size - return hv % HASHSIZE; + uint32_t hv = 0; + for (int i = 0; s[i] != '\0'; i++) { + // take MSB 6 bits of hv and xors with LSB of s[i] + uint32_t v = (hv >> 26) ^ (s[i] & 0x3f); + + // Push those back on hv + hv = (hv << 4) | v; + } + // Return appropriate size + return hv % HASHSIZE; } - static void table_insert(graph_t *g, vertex_t *v, char *var) { - unsigned int index = hash(var); + unsigned int index = hash(var); - // Save old value - vertex_t *oldSym = g->hashtable[index]; + // Save old value + vertex_t *oldSym = g->hashtable[index]; - // Make new - g->hashtable[index] = v; + // Make new + g->hashtable[index] = v; - // Link old one - g->hashtable[index]->next = oldSym; + // Link old one + g->hashtable[index]->next = oldSym; } static vertex_t *table_lookup(graph_t *g, char *var) { - unsigned int index = hash(var); - vertex_t *n = g->hashtable[index]; + unsigned int index = hash(var); + vertex_t *n = g->hashtable[index]; - // Look trough list - while (n != NULL && strcmp(n->ref, var) != 0) { - n = n->next; - } + // Look trough list + while (n != NULL && strcmp(n->ref, var) != 0) { + n = n->next; + } - return n; + return n; } static vertex_t *create_vertex(char *ref) { - // Get some space TODO check for null - vertex_t *v = malloc(sizeof(vertex_t)); - - // Set values - v->ref = strdup(ref); - v->color = COLOR_WHITE; - v->next = NULL; - v->adj = NULL; - return v; + // Get some space TODO check for null + vertex_t *v = malloc(sizeof(vertex_t)); + + // Set values + v->ref = strdup(ref); + v->color = COLOR_WHITE; + v->next = NULL; + v->adj = NULL; + return v; } static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) { - edge_t *old = from->adj; - - // Create new list node - edge_t *e = malloc(sizeof(edge_t)); - e->weight = weight; - e->from = from; - e->to = to; - - // Do new link - e->next = old; - if ( old ) { - e->prev = old->prev; - old->prev = e; - } else { - e->prev = NULL; - } - - if ( e->prev ) { - e->prev->next = e; - } - - from->adj = e; - - return e; + edge_t *old = from->adj; + + // Create new list node + edge_t *e = malloc(sizeof(edge_t)); + e->weight = weight; + e->from = from; + e->to = to; + + // Do new link + e->next = old; + if (old) { + e->prev = old->prev; + old->prev = e; + } else { + e->prev = NULL; + } + + if (e->prev) { + e->prev->next = e; + } + + from->adj = e; + + return e; } // For iterating edges edge_t *edge_next(graph_t *g, edge_t *e) { - if (e == NULL || e->next == NULL ) { - // Find next index - vertex_t *v = e ? e->from : NULL; - - // Find next vertex - v = vertex_next(g, v); - while ( v ) { - // Check if found - if ( v->adj ) { - return v->adj; - } - - v = vertex_next(g, v); - } - - // No next vertex - return NULL; - } - - // Not finished with this adj list - return e->next; + if (e == NULL || e->next == NULL) { + // Find next index + vertex_t *v = e ? e->from : NULL; + + // Find next vertex + v = vertex_next(g, v); + while (v) { + // Check if found + if (v->adj) { + return v->adj; + } + + v = vertex_next(g, v); + } + + // No next vertex + return NULL; + } + + // Not finished with this adj list + return e->next; } vertex_t *vertex_next(graph_t *g, vertex_t *v) { - if ( v == NULL || v->next == NULL) { - // Go to next index in hashtable - int i = v ? hash(v->ref)+1 : 0; - for ( ; i < HASHSIZE; i++) { - if ( g->hashtable[i] ) { - return g->hashtable[i]; - } - } - - // No next - return NULL; - } - - return v->next; + if (v == NULL || v->next == NULL) { + // Go to next index in hashtable + int i = v ? hash(v->ref) + 1 : 0; + for (; i < HASHSIZE; i++) { + if (g->hashtable[i]) { + return g->hashtable[i]; + } + } + + // No next + return NULL; + } + + return v->next; } void graph_edge(graph_t *g, char *from, char *to, int weight) { - vertex_t *fromv, *tov; - // Does a exists - if ( (fromv = table_lookup(g, from)) == NULL ) { - fromv = create_vertex(from); - table_insert(g, fromv, from); - } - // What about b - if ( (tov = table_lookup(g, to)) == NULL ) { - tov = create_vertex(to); - table_insert(g, tov, to); - } - - // Add edge - create_edge(fromv, tov, weight); + vertex_t *fromv, *tov; + // Does a exists + if ((fromv = table_lookup(g, from)) == NULL) { + fromv = create_vertex(from); + table_insert(g, fromv, from); + } + // What about b + if ((tov = table_lookup(g, to)) == NULL) { + tov = create_vertex(to); + table_insert(g, tov, to); + } + + // Add edge + create_edge(fromv, tov, weight); } int graph_print_adj(graph_t *g, char *ref) { - vertex_t *v = table_lookup(g, ref); - if ( v == NULL ) { - return 1; - } - - edge_t *e = v->adj; - printf("[ "); - while (e && e->from->ref == ref) { - printf("%s[%d] ", e->to->ref, e->weight); - e = e->next; - } - printf("]\n"); - - return 0; + vertex_t *v = table_lookup(g, ref); + if (v == NULL) { + return 1; + } + + edge_t *e = v->adj; + printf("[ "); + while (e && e->from->ref == ref) { + printf("%s[%d] ", e->to->ref, e->weight); + e = e->next; + } + printf("]\n"); + + return 0; } int graph_to_dot(FILE *f, graph_t *g) { - // print pre stuff - fprintf(f, "digraph coolgraph {\n"); - - // Label all nodes - vertex_t *v = vertex_next(g, NULL); - while ( v ) { - fprintf(f, "%s [label=\"%s\"];\n", v->ref, v->ref); - v = vertex_next(g, v); - } - // Print all the edges - edge_t *e = edge_next(g, NULL); - while ( e ) { - fprintf(f, "%s -> %s [label = %d];\n", e->from->ref, e->to->ref, e->weight); - e = edge_next(g, e); - } - - // done - fprintf(f, "}\n"); + // print pre stuff + fprintf(f, "digraph coolgraph {\n"); + + // Label all nodes + vertex_t *v = vertex_next(g, NULL); + while (v) { + fprintf(f, "%s [label=\"%s\"];\n", v->ref, v->ref); + v = vertex_next(g, v); + } + // Print all the edges + edge_t *e = edge_next(g, NULL); + while (e) { + fprintf(f, "%s -> %s [label = %d];\n", e->from->ref, e->to->ref, + e->weight); + e = edge_next(g, e); + } + + // done + fprintf(f, "}\n"); } - diff --git a/sem3/algo/workshop2/dfs/graph.h b/sem3/algo/workshop2/dfs/graph.h index e169a8a..ad61b1e 100644 --- a/sem3/algo/workshop2/dfs/graph.h +++ b/sem3/algo/workshop2/dfs/graph.h @@ -2,7 +2,7 @@ #define GRAPH_H_ #define COLOR_WHITE 0 -#define COLOR_GRAY 1 +#define COLOR_GRAY 1 #define COLOR_BLACK 2 #define HASHSIZE 128 @@ -11,29 +11,29 @@ struct vertex_struct; // Linked list typedef struct edge_struct { - int weight; - struct vertex_struct *from; - struct vertex_struct *to; - // Linked list stuff - struct edge_struct *next; - struct edge_struct *prev; + int weight; + struct vertex_struct *from; + struct vertex_struct *to; + // Linked list stuff + struct edge_struct *next; + struct edge_struct *prev; } edge_t; typedef struct vertex_struct { - char *ref; - int color; + char *ref; + int color; - int dtime; - int ftime; + int dtime; + int ftime; - edge_t *adj; + edge_t *adj; - // Hash table stuff - struct vertex_struct *next; + // Hash table stuff + struct vertex_struct *next; } vertex_t; typedef struct { - vertex_t *hashtable[128]; + vertex_t *hashtable[128]; } graph_t; int graph_to_dot(FILE *f, graph_t *g); diff --git a/sem3/algo/workshop2/dijkstra/dijkstra.c b/sem3/algo/workshop2/dijkstra/dijkstra.c index c112c6d..d68492a 100644 --- a/sem3/algo/workshop2/dijkstra/dijkstra.c +++ b/sem3/algo/workshop2/dijkstra/dijkstra.c @@ -5,69 +5,70 @@ #include "graph.h" typedef struct list_item { - vertex_t *v; - struct list_item *next; - struct list_item *prev; + vertex_t *v; + struct list_item *next; + struct list_item *prev; } list_item_t; typedef struct { - int len; - struct list_item *begin; - struct list_item *end; + int len; + struct list_item *begin; + struct list_item *end; } list_t; void list_push(list_t *s, vertex_t *v) { - // Create - list_item_t *i = malloc(sizeof(list_item_t)); - i->next = NULL; - i->prev = NULL; - i->v = v; - - // Link - if ( s->len == 0 ) { - s->begin = i; - } else { - s->end->next = i; - i->prev = s->end; - } - - s->end = i; - s->len++; + // Create + list_item_t *i = malloc(sizeof(list_item_t)); + i->next = NULL; + i->prev = NULL; + i->v = v; + + // Link + if (s->len == 0) { + s->begin = i; + } else { + s->end->next = i; + i->prev = s->end; + } + + s->end = i; + s->len++; } vertex_t *list_pop_smallest(list_t *s) { - //printf("beginning %s(%d)\n", s->begin->v->ref, s->begin->v->dist); - list_item_t *smallest = s->begin; - - // Search - list_item_t *i = s->begin; - while ( i ) { - if ( smallest->v->dist == -1 || (i->v->dist != -1 && i->v->dist < smallest->v->dist) ) { - smallest = i; - } - i = i->next; - } - - if ( smallest == s->begin ) { - s->begin = smallest->next; - } else { - smallest->prev->next = smallest->next; - } - - if ( smallest == s->end ) { - s->end = smallest->prev; - } else { - smallest->next->prev = smallest->prev; - } - - vertex_t *v = smallest->v; - free(smallest); - - s->len--; - - return v; + //printf("beginning %s(%d)\n", s->begin->v->ref, s->begin->v->dist); + list_item_t *smallest = s->begin; + + // Search + list_item_t *i = s->begin; + while (i) { + if (smallest->v->dist == -1 || + (i->v->dist != -1 && i->v->dist < smallest->v->dist)) { + smallest = i; + } + i = i->next; + } + + if (smallest == s->begin) { + s->begin = smallest->next; + } else { + smallest->prev->next = smallest->next; + } + + if (smallest == s->end) { + s->end = smallest->prev; + } else { + smallest->next->prev = smallest->prev; + } + + vertex_t *v = smallest->v; + free(smallest); + + s->len--; + + return v; } graph_t g; @@ -75,59 +76,59 @@ graph_t g; // Assumes u has an edge to v void relax(vertex_t *u, vertex_t *v) { - // Get edge between these two guys - edge_t *e = u->adj; - while (e && e->next && strcmp(e->to->ref, v->ref)) { - e = e->next; - } - - if ( v->dist == -1 || v->dist > (u->dist + e->weight) ) { - v->dist = u->dist + e->weight; - v->p = u; - } + // Get edge between these two guys + edge_t *e = u->adj; + while (e && e->next && strcmp(e->to->ref, v->ref)) { + e = e->next; + } + + if (v->dist == -1 || v->dist > (u->dist + e->weight)) { + v->dist = u->dist + e->weight; + v->p = u; + } } void dijkstra(graph_t *g, vertex_t *s) { - list_t list; - list.len = 0; - list.end = list.begin = 0; - - s->dist = 0; - - { - vertex_t *v = vertex_next(g, NULL); - while ( v ) { - list_push(&list, v); - v = vertex_next(g, v); - } - } - - while ( list.len ) { - vertex_t *u = list_pop_smallest(&list); - edge_t *e = u->adj; - while ( e ) { - relax(u, e->to ); - e = e->next; - } - } + list_t list; + list.len = 0; + list.end = list.begin = 0; + + s->dist = 0; + + { + vertex_t *v = vertex_next(g, NULL); + while (v) { + list_push(&list, v); + v = vertex_next(g, v); + } + } + + while (list.len) { + vertex_t *u = list_pop_smallest(&list); + edge_t *e = u->adj; + while (e) { + relax(u, e->to); + e = e->next; + } + } } int main() { - int count = graph_from_dot(stdin, &g); + int count = graph_from_dot(stdin, &g); - clock_t start, end; - double cpu_time_used; + clock_t start, end; + double cpu_time_used; - start = clock(); - dijkstra(&g, graph_vertex(&g, "0")); - end = clock(); - cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; + start = clock(); + dijkstra(&g, graph_vertex(&g, "0")); + end = clock(); + cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; - printf("%d;%f\n", count, cpu_time_used); + printf("%d;%f\n", count, cpu_time_used); - //graph_to_dot(stdout, &g); + //graph_to_dot(stdout, &g); - return 0; + return 0; } diff --git a/sem3/algo/workshop2/dijkstra/graph.c b/sem3/algo/workshop2/dijkstra/graph.c index 51206c4..4f2e88f 100644 --- a/sem3/algo/workshop2/dijkstra/graph.c +++ b/sem3/algo/workshop2/dijkstra/graph.c @@ -8,224 +8,226 @@ // Hashtable static unsigned int hash(char *s) { - uint32_t hv = 0; - for ( int i = 0; s[i] != '\0'; i++ ) { - // take MSB 6 bits of hv and xors with LSB of s[i] - uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f); - - // Push those back on hv - hv = (hv << 4) | v; - } - // Return appropriate size - return hv % HASHSIZE; + uint32_t hv = 0; + for (int i = 0; s[i] != '\0'; i++) { + // take MSB 6 bits of hv and xors with LSB of s[i] + uint32_t v = (hv >> 26) ^ (s[i] & 0x3f); + + // Push those back on hv + hv = (hv << 4) | v; + } + // Return appropriate size + return hv % HASHSIZE; } - static void table_insert(graph_t *g, vertex_t *v, char *var) { - unsigned int index = hash(var); + unsigned int index = hash(var); - // Save old value - vertex_t *oldSym = g->hashtable[index]; + // Save old value + vertex_t *oldSym = g->hashtable[index]; - // Make new - g->hashtable[index] = v; + // Make new + g->hashtable[index] = v; - // Link old one - g->hashtable[index]->next = oldSym; + // Link old one + g->hashtable[index]->next = oldSym; } static vertex_t *table_lookup(graph_t *g, char *var) { - unsigned int index = hash(var); - vertex_t *n = g->hashtable[index]; + unsigned int index = hash(var); + vertex_t *n = g->hashtable[index]; - // Look trough list - while (n != NULL && strcmp(n->ref, var) != 0) { - n = n->next; - } + // Look trough list + while (n != NULL && strcmp(n->ref, var) != 0) { + n = n->next; + } - return n; + return n; } static vertex_t *create_vertex(char *ref) { - // Get some space TODO check for null - vertex_t *v = malloc(sizeof(vertex_t)); - - // Set values - v->ref = strdup(ref); - v->color = COLOR_WHITE; - v->p = NULL; - v->dist = -1; - v->adj = NULL; - return v; + // Get some space TODO check for null + vertex_t *v = malloc(sizeof(vertex_t)); + + // Set values + v->ref = strdup(ref); + v->color = COLOR_WHITE; + v->p = NULL; + v->dist = -1; + v->adj = NULL; + return v; } static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) { - edge_t *old = from->adj; - - // Create new list node - edge_t *e = malloc(sizeof(edge_t)); - e->weight = weight; - e->from = from; - e->to = to; - - // Do new link - e->next = old; - if ( old ) { - e->prev = old->prev; - old->prev = e; - } else { e->prev = NULL; } - - if ( e->prev ) { - e->prev->next = e; - } - - from->adj = e; - - return e; + edge_t *old = from->adj; + + // Create new list node + edge_t *e = malloc(sizeof(edge_t)); + e->weight = weight; + e->from = from; + e->to = to; + + // Do new link + e->next = old; + if (old) { + e->prev = old->prev; + old->prev = e; + } else { + e->prev = NULL; + } + + if (e->prev) { + e->prev->next = e; + } + + from->adj = e; + + return e; } // For iterating edges edge_t *edge_next(graph_t *g, edge_t *e) { - if (e == NULL || e->next == NULL ) { - // Find next index - vertex_t *v = e ? e->from : NULL; - - // Find next vertex - v = vertex_next(g, v); - while ( v ) { - // Check if found - if ( v->adj ) { - return v->adj; - } - - v = vertex_next(g, v); - } - - // No next vertex - return NULL; - } - - // Not finished with this adj list - return e->next; + if (e == NULL || e->next == NULL) { + // Find next index + vertex_t *v = e ? e->from : NULL; + + // Find next vertex + v = vertex_next(g, v); + while (v) { + // Check if found + if (v->adj) { + return v->adj; + } + + v = vertex_next(g, v); + } + + // No next vertex + return NULL; + } + + // Not finished with this adj list + return e->next; } vertex_t *vertex_next(graph_t *g, vertex_t *v) { - if ( v == NULL || v->next == NULL) { - // Go to next index in hashtable - int i = v ? hash(v->ref)+1 : 0; - for ( ; i < HASHSIZE; i++) { - if ( g->hashtable[i] ) { - return g->hashtable[i]; - } - } - - // No next - return NULL; - } - - return v->next; + if (v == NULL || v->next == NULL) { + // Go to next index in hashtable + int i = v ? hash(v->ref) + 1 : 0; + for (; i < HASHSIZE; i++) { + if (g->hashtable[i]) { + return g->hashtable[i]; + } + } + + // No next + return NULL; + } + + return v->next; } void graph_edge(graph_t *g, char *from, char *to, int weight) { - vertex_t *fromv, *tov; - // Does a exists - if ( (fromv = table_lookup(g, from)) == NULL ) { - fromv = create_vertex(from); - table_insert(g, fromv, from); - } - // What about b - if ( (tov = table_lookup(g, to)) == NULL ) { - tov = create_vertex(to); - table_insert(g, tov, to); - } - - // Add edge - create_edge(fromv, tov, weight); + vertex_t *fromv, *tov; + // Does a exists + if ((fromv = table_lookup(g, from)) == NULL) { + fromv = create_vertex(from); + table_insert(g, fromv, from); + } + // What about b + if ((tov = table_lookup(g, to)) == NULL) { + tov = create_vertex(to); + table_insert(g, tov, to); + } + + // Add edge + create_edge(fromv, tov, weight); } int graph_print_adj(graph_t *g, char *ref) { - vertex_t *v = table_lookup(g, ref); - if ( v == NULL ) { - return 1; - } - - edge_t *e = v->adj; - printf("[ "); - while (e && e->from->ref == ref) { - printf("%s[%d] ", e->to->ref, e->weight); - e = e->next; - } - printf("]\n"); - - return 0; + vertex_t *v = table_lookup(g, ref); + if (v == NULL) { + return 1; + } + + edge_t *e = v->adj; + printf("[ "); + while (e && e->from->ref == ref) { + printf("%s[%d] ", e->to->ref, e->weight); + e = e->next; + } + printf("]\n"); + + return 0; } int graph_to_dot(FILE *f, graph_t *g) { - // print pre stuff - fprintf(f, "digraph coolgraph {\n"); - - // Label all nodes - vertex_t *v = vertex_next(g, NULL); - while ( v ) { - fprintf(f, "%s [label=\"%s(%d)\"];\n", v->ref, v->ref, v->dist); - v = vertex_next(g, v); - } - // Print all the edges - edge_t *e = edge_next(g, NULL); - while ( e ) { - fprintf(f, "%s -> %s [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : ""); - e = edge_next(g, e); - } - - // done - fprintf(f, "}\n"); + // print pre stuff + fprintf(f, "digraph coolgraph {\n"); + + // Label all nodes + vertex_t *v = vertex_next(g, NULL); + while (v) { + fprintf(f, "%s [label=\"%s(%d)\"];\n", v->ref, v->ref, v->dist); + v = vertex_next(g, v); + } + // Print all the edges + edge_t *e = edge_next(g, NULL); + while (e) { + fprintf(f, "%s -> %s [label = %d%s];\n", e->from->ref, e->to->ref, + e->weight, e->to->p == e->from ? " color=blue" : ""); + e = edge_next(g, e); + } + + // done + fprintf(f, "}\n"); } // This was created in a hurry sorry int graph_from_dot(FILE *f, graph_t *g) { - char from[100], to[100]; - int weight; - int count = 0; - // just fscanf it - for (;;) { - // Set first to zero - *from = 0; - *to = 0; - weight = 0; - int c = fscanf(f, "%s -> %s [label=%d];", from, to, &weight); - if ( c <= 0 ) { - break; - } - if ( *from == 0 || *to == 0 ) { - continue; - } - // Sorry i just want it to work - int tolen = strlen(to); - if ( to[tolen-1] == ';' ) { - to[tolen-1] = 0; - } - - weight = weight ? weight : 1; - //printf("Creating edge from %s to %s with w: %d\n", from, to, weight); - - graph_edge(g, from, to, weight); - count++; - } - - return count; + char from[100], to[100]; + int weight; + int count = 0; + // just fscanf it + for (;;) { + // Set first to zero + *from = 0; + *to = 0; + weight = 0; + int c = fscanf(f, "%s -> %s [label=%d];", from, to, &weight); + if (c <= 0) { + break; + } + if (*from == 0 || *to == 0) { + continue; + } + // Sorry i just want it to work + int tolen = strlen(to); + if (to[tolen - 1] == ';') { + to[tolen - 1] = 0; + } + + weight = weight ? weight : 1; + //printf("Creating edge from %s to %s with w: %d\n", from, to, weight); + + graph_edge(g, from, to, weight); + count++; + } + + return count; } vertex_t *graph_vertex(graph_t *g, char *ref) { - return table_lookup(g, ref); + return table_lookup(g, ref); } diff --git a/sem3/algo/workshop2/dijkstra/graph.h b/sem3/algo/workshop2/dijkstra/graph.h index 5c078b8..75b5eab 100644 --- a/sem3/algo/workshop2/dijkstra/graph.h +++ b/sem3/algo/workshop2/dijkstra/graph.h @@ -2,7 +2,7 @@ #define GRAPH_H_ #define COLOR_WHITE 0 -#define COLOR_GRAY 1 +#define COLOR_GRAY 1 #define COLOR_BLACK 2 #define HASHSIZE 128 @@ -11,29 +11,29 @@ struct vertex_struct; // Linked list typedef struct edge_struct { - int weight; - struct vertex_struct *from; - struct vertex_struct *to; - // Linked list stuff - struct edge_struct *next; - struct edge_struct *prev; + int weight; + struct vertex_struct *from; + struct vertex_struct *to; + // Linked list stuff + struct edge_struct *next; + struct edge_struct *prev; } edge_t; typedef struct vertex_struct { - char *ref; - int color; + char *ref; + int color; - int dist; - struct vertex_struct *p; + int dist; + struct vertex_struct *p; - edge_t *adj; + edge_t *adj; - // Hash table stuff - struct vertex_struct *next; + // Hash table stuff + struct vertex_struct *next; } vertex_t; typedef struct { - vertex_t *hashtable[128]; + vertex_t *hashtable[128]; } graph_t; int graph_to_dot(FILE *f, graph_t *g); diff --git a/sem3/module.c b/sem3/module.c index a4f4def..d29cd9f 100644 --- a/sem3/module.c +++ b/sem3/module.c @@ -4,11 +4,11 @@ module_init(void) { - printk(KERN_INFO "COOL_MODULE: Hej med dig\n"); - return 0; + printk(KERN_INFO "COOL_MODULE: Hej med dig\n"); + return 0; } module_exit(void) { - printk(KERN_INFO "COOL_MODULE: Nou moe\n"); + printk(KERN_INFO "COOL_MODULE: Nou moe\n"); } diff --git a/sem3/osc/miniproject/cnasm/ast.c b/sem3/osc/miniproject/cnasm/ast.c index badf090..cc53e24 100644 --- a/sem3/osc/miniproject/cnasm/ast.c +++ b/sem3/osc/miniproject/cnasm/ast.c @@ -4,101 +4,101 @@ #include <string.h> #include <stdio.h> -static ast_node_t *create_empty_node() { - ast_node_t *n = malloc(sizeof(ast_node_t)); - memset(n, 0, sizeof(ast_node_t)); +static ast_node_t *create_empty_node() +{ + ast_node_t *n = malloc(sizeof(ast_node_t)); + memset(n, 0, sizeof(ast_node_t)); } -ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, ast_node_t *iffalse) +ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, + ast_node_t *iffalse) { - ast_node_t *n = create_empty_node(); + ast_node_t *n = create_empty_node(); - n->t = t; - n->flowctrl.condition = c; - n->flowctrl.iftrue = iftrue; - n->flowctrl.iffalse = iffalse; + n->t = t; + n->flowctrl.condition = c; + n->flowctrl.iftrue = iftrue; + n->flowctrl.iffalse = iffalse; - return n; + return n; } ast_node_t *insert_for(char *pre, cond_t *c, char *inc, ast_node_t *stuff) { - ast_node_t *n = create_empty_node(); + ast_node_t *n = create_empty_node(); - n->t = TFOR; - n->forloop.condition = c; - n->forloop.pre = pre; - n->forloop.inc = inc; - n->forloop.stuff = stuff; + n->t = TFOR; + n->forloop.condition = c; + n->forloop.pre = pre; + n->forloop.inc = inc; + n->forloop.stuff = stuff; - return n; + return n; } ast_node_t *insert_stm(ast_node_t *stm, ast_node_t *stm_list) { - ast_node_t *n = create_empty_node(); + ast_node_t *n = create_empty_node(); - n->t = TSTM_LIST; - n->list.children[0] = stm_list; - n->list.children[1] = stm; + n->t = TSTM_LIST; + n->list.children[0] = stm_list; + n->list.children[1] = stm; - return n; + return n; } ast_node_t *insert_ident(char *ident) { - ast_node_t *n = create_empty_node(); + ast_node_t *n = create_empty_node(); - n->t = TIDENT; - n->ident = ident; + n->t = TIDENT; + n->ident = ident; - return n; + return n; } cond_t *insert_cond(uint8_t cmp, char *a, char *b) { - cond_t *c = malloc( sizeof(cond_t)); + cond_t *c = malloc(sizeof(cond_t)); - c->cmp = cmp; - c->a = a; - c->b = b; + c->cmp = cmp; + c->a = a; + c->b = b; } void node_print(ast_node_t *node) { - if ( !node ){ - printf("Nil"); - return; - } - switch (node->t) { - case TSTM_LIST: - printf("Stm_list("); - node_print(node->list.children[0]); - printf(","); - node_print(node->list.children[1]); - printf(")"); - break; - case TIF: - printf("If"); - printf("(%s %c %s) {", node->flowctrl.condition->a, - node->flowctrl.condition->cmp, - node->flowctrl.condition->b); - node_print(node->flowctrl.iftrue); - printf("}{"); - node_print(node->flowctrl.iffalse); - printf("}"); - break; - case TIDENT: - printf("%s", node->ident); - break; - case TWHILE: - printf("while"); - printf("(%s %c %s) {", node->flowctrl.condition->a, - node->flowctrl.condition->cmp, - node->flowctrl.condition->b); - node_print(node->flowctrl.iftrue); - printf("}"); - break; - default: - printf("invalid"); - } + if (!node) { + printf("Nil"); + return; + } + switch (node->t) { + case TSTM_LIST: + printf("Stm_list("); + node_print(node->list.children[0]); + printf(","); + node_print(node->list.children[1]); + printf(")"); + break; + case TIF: + printf("If"); + printf("(%s %c %s) {", node->flowctrl.condition->a, + node->flowctrl.condition->cmp, node->flowctrl.condition->b); + node_print(node->flowctrl.iftrue); + printf("}{"); + node_print(node->flowctrl.iffalse); + printf("}"); + break; + case TIDENT: + printf("%s", node->ident); + break; + case TWHILE: + printf("while"); + printf("(%s %c %s) {", node->flowctrl.condition->a, + node->flowctrl.condition->cmp, node->flowctrl.condition->b); + node_print(node->flowctrl.iftrue); + printf("}"); + break; + default: + printf("invalid"); + } } diff --git a/sem3/osc/miniproject/cnasm/ast.h b/sem3/osc/miniproject/cnasm/ast.h index 61a8f4f..4f37553 100644 --- a/sem3/osc/miniproject/cnasm/ast.h +++ b/sem3/osc/miniproject/cnasm/ast.h @@ -11,37 +11,38 @@ #define CLEQ CGT ^ 0x80 #define CGEQ CLT ^ 0x80 -enum ntype { TSTM_LIST, TIF, TFOR, TIDENT, TWHILE}; +enum ntype { TSTM_LIST, TIF, TFOR, TIDENT, TWHILE }; typedef struct cond { - uint8_t cmp; - char *a; - char *b; + uint8_t cmp; + char *a; + char *b; } cond_t; typedef struct ast_node { - enum ntype t; - // Dependent on type - union { - struct { - cond_t *condition; - struct ast_node *iftrue; - struct ast_node *iffalse; - } flowctrl; - struct { - cond_t *condition; - char *pre; - char *inc; - struct ast_node *stuff; - } forloop; - char *ident; - struct { - struct ast_node *children[2]; - } list; - }; + enum ntype t; + // Dependent on type + union { + struct { + cond_t *condition; + struct ast_node *iftrue; + struct ast_node *iffalse; + } flowctrl; + struct { + cond_t *condition; + char *pre; + char *inc; + struct ast_node *stuff; + } forloop; + char *ident; + struct { + struct ast_node *children[2]; + } list; + }; } ast_node_t; -ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, ast_node_t *iffalse); +ast_node_t *insert_ctrl(enum ntype t, cond_t *c, ast_node_t *iftrue, + ast_node_t *iffalse); ast_node_t *insert_stm(ast_node_t *stm, ast_node_t *stm_list); ast_node_t *insert_ident(char *ident); ast_node_t *insert_for(char *pre, cond_t *c, char *inc, ast_node_t *stuff); @@ -50,4 +51,4 @@ cond_t *insert_cond(uint8_t cmp, char *a, char *b); void node_print(ast_node_t *node); -#endif +#endif diff --git a/sem3/osc/miniproject/cnasm/codegen.c b/sem3/osc/miniproject/cnasm/codegen.c index 57584a4..6f32982 100644 --- a/sem3/osc/miniproject/cnasm/codegen.c +++ b/sem3/osc/miniproject/cnasm/codegen.c @@ -7,131 +7,131 @@ static void gencondjmp(FILE *f, cond_t *c, bool neg) { - uint8_t cmp = neg ? c->cmp^0x80 : c->cmp; - fprintf(f, "cmp %s %s\n", c->a, c->b); - switch (cmp) { - case CEQ: - fprintf(f, "je "); - break; - case CNEQ: - fprintf(f, "jne "); - break; - case CGT: - fprintf(f, "jg "); - break; - case CLT: - fprintf(f, "jl "); - break; - case CLEQ: - fprintf(f, "jle "); - break; - case CGEQ: - fprintf(f, "jge "); - break; - default: - fprintf(stderr, "Invalid cmp type %x", cmp); - fprintf(f, "jmp "); - } + uint8_t cmp = neg ? c->cmp ^ 0x80 : c->cmp; + fprintf(f, "cmp %s %s\n", c->a, c->b); + switch (cmp) { + case CEQ: + fprintf(f, "je "); + break; + case CNEQ: + fprintf(f, "jne "); + break; + case CGT: + fprintf(f, "jg "); + break; + case CLT: + fprintf(f, "jl "); + break; + case CLEQ: + fprintf(f, "jle "); + break; + case CGEQ: + fprintf(f, "jge "); + break; + default: + fprintf(stderr, "Invalid cmp type %x", cmp); + fprintf(f, "jmp "); + } } static void genif(FILE *f, struct genctx *ctx, ast_node_t *n) { - bool doElse = n->flowctrl.iffalse; - // Create conditional jump - gencondjmp(f, n->flowctrl.condition, true); - if ( doElse ) { - fprintf(f, "else_%d\n", ctx->nested); - } else { - fprintf(f, "end_%d\n", ctx->nested); - } - - struct genctx octx = { ctx->nested+1 }; - // Paste code - gentree(f, &octx, n->flowctrl.iftrue); - - // Do else - if ( doElse ) { - fprintf(f, "jmp end_%d\n", ctx->nested); - fprintf(f, "else_%d:\n", ctx->nested); - gentree(f, &octx, n->flowctrl.iffalse); - } - - // End block - fprintf(f, "end_%d:\n", ctx->nested); + bool doElse = n->flowctrl.iffalse; + // Create conditional jump + gencondjmp(f, n->flowctrl.condition, true); + if (doElse) { + fprintf(f, "else_%d\n", ctx->nested); + } else { + fprintf(f, "end_%d\n", ctx->nested); + } + + struct genctx octx = { ctx->nested + 1 }; + // Paste code + gentree(f, &octx, n->flowctrl.iftrue); + + // Do else + if (doElse) { + fprintf(f, "jmp end_%d\n", ctx->nested); + fprintf(f, "else_%d:\n", ctx->nested); + gentree(f, &octx, n->flowctrl.iffalse); + } + + // End block + fprintf(f, "end_%d:\n", ctx->nested); } static void genwhile(FILE *f, struct genctx *ctx, ast_node_t *n) { - // Create loop label - fprintf(f, "loop_%d:\n", ctx->nested); - - // Create conditional jump - gencondjmp(f, n->flowctrl.condition, true); - fprintf(f, "end_%d\n", ctx->nested); - - struct genctx octx = { ctx->nested+1 }; - // Paste code - gentree(f, &octx, n->flowctrl.iftrue); - - // Jump to start - fprintf(f, "jmp loop_%d\n", ctx->nested); - - // End block - fprintf(f, "end_%d:\n", ctx->nested); + // Create loop label + fprintf(f, "loop_%d:\n", ctx->nested); + + // Create conditional jump + gencondjmp(f, n->flowctrl.condition, true); + fprintf(f, "end_%d\n", ctx->nested); + + struct genctx octx = { ctx->nested + 1 }; + // Paste code + gentree(f, &octx, n->flowctrl.iftrue); + + // Jump to start + fprintf(f, "jmp loop_%d\n", ctx->nested); + + // End block + fprintf(f, "end_%d:\n", ctx->nested); } static void genfor(FILE *f, struct genctx *ctx, ast_node_t *n) { - // Do pre stuff - fprintf(f, "%s\n", n->forloop.pre); - - // Create loop label - fprintf(f, "loop_%d:\n", ctx->nested); - - // Create conditional jump - gencondjmp(f, n->flowctrl.condition, true); - fprintf(f, "end_%d\n", ctx->nested); - - struct genctx octx = { ctx->nested+1 }; - // Paste code - gentree(f, &octx, n->forloop.stuff); - - // Do inc stuff - fprintf(f, "%s\n", n->forloop.inc); - // Jump to start - fprintf(f, "jmp loop_%d\n", ctx->nested); - - // End block - fprintf(f, "end_%d:\n", ctx->nested); + // Do pre stuff + fprintf(f, "%s\n", n->forloop.pre); + + // Create loop label + fprintf(f, "loop_%d:\n", ctx->nested); + + // Create conditional jump + gencondjmp(f, n->flowctrl.condition, true); + fprintf(f, "end_%d\n", ctx->nested); + + struct genctx octx = { ctx->nested + 1 }; + // Paste code + gentree(f, &octx, n->forloop.stuff); + + // Do inc stuff + fprintf(f, "%s\n", n->forloop.inc); + // Jump to start + fprintf(f, "jmp loop_%d\n", ctx->nested); + + // End block + fprintf(f, "end_%d:\n", ctx->nested); } void gentree(FILE *f, struct genctx *ctx, ast_node_t *n) { - if ( !n ) { - return; - } - if ( ctx == NULL ) { - ctx = malloc(sizeof(struct genctx)); - ctx->nested = 0; - } - switch (n->t) { - case TSTM_LIST: - gentree(f, ctx, n->list.children[0]); - gentree(f, ctx, n->list.children[1]); - break; - case TIF: - genif(f, ctx, n); - break; - case TIDENT: - fprintf(f, "%s\n", n->ident); - break; - case TFOR: - genfor(f, ctx, n); - break; - case TWHILE: - genwhile(f, ctx, n); - break; - default: - return; - } + if (!n) { + return; + } + if (ctx == NULL) { + ctx = malloc(sizeof(struct genctx)); + ctx->nested = 0; + } + switch (n->t) { + case TSTM_LIST: + gentree(f, ctx, n->list.children[0]); + gentree(f, ctx, n->list.children[1]); + break; + case TIF: + genif(f, ctx, n); + break; + case TIDENT: + fprintf(f, "%s\n", n->ident); + break; + case TFOR: + genfor(f, ctx, n); + break; + case TWHILE: + genwhile(f, ctx, n); + break; + default: + return; + } } diff --git a/sem3/osc/miniproject/cnasm/codegen.h b/sem3/osc/miniproject/cnasm/codegen.h index 24ad6c4..14c68fe 100644 --- a/sem3/osc/miniproject/cnasm/codegen.h +++ b/sem3/osc/miniproject/cnasm/codegen.h @@ -6,9 +6,9 @@ #include "ast.h" struct genctx { - unsigned int nested; + unsigned int nested; }; void gentree(FILE *f, struct genctx *ctx, ast_node_t *n); -#endif +#endif diff --git a/sem3/osc/mm1/mm1/jmod.c b/sem3/osc/mm1/mm1/jmod.c index 472ad46..05eb7c1 100644 --- a/sem3/osc/mm1/mm1/jmod.c +++ b/sem3/osc/mm1/mm1/jmod.c @@ -7,67 +7,62 @@ static int major_num; static int busy; - static int cool_open(struct inode *inode, struct file *file) { - /* Check if we are already serving someone */ - if (busy) { - return -EBUSY; - } + /* Check if we are already serving someone */ + if (busy) { + return -EBUSY; + } - busy = 1; - return 0; + busy = 1; + return 0; } -static int cool_release (struct inode *inode, struct file *file) +static int cool_release(struct inode *inode, struct file *file) { - busy = 0; + busy = 0; - return 0; + return 0; } -static ssize_t cool_read (struct file *filp, char *buffer, size_t len, loff_t *offset) +static ssize_t cool_read(struct file *filp, char *buffer, size_t len, + loff_t *offset) { + char str[12] = "hej med dig"; + int i; - char str[12] = "hej med dig"; - int i; - - for (i = 0; i < len; i++) { - put_user(str[i % 12], buffer++); - } + for (i = 0; i < len; i++) { + put_user(str[i % 12], buffer++); + } - return i; + return i; } -static struct file_operations file_ops = { - .owner = THIS_MODULE, - .read = cool_read, - .open = cool_open, - .release = cool_release -}; +static struct file_operations file_ops = { .owner = THIS_MODULE, + .read = cool_read, + .open = cool_open, + .release = cool_release }; -static int __init jmod_init(void) +static int __init jmod_init(void) { - printk(KERN_INFO "COOL_MODULE: Registering cooldev\n"); - - major_num = register_chrdev(0, "cooldev", &file_ops); - if (major_num < 0) { - printk(KERN_ERR "COOL_MODULE: Could not register major\n"); - return 1; - } + printk(KERN_INFO "COOL_MODULE: Registering cooldev\n"); - printk(KERN_INFO "COOL_MODULE: Got major %d\n", major_num); + major_num = register_chrdev(0, "cooldev", &file_ops); + if (major_num < 0) { + printk(KERN_ERR "COOL_MODULE: Could not register major\n"); + return 1; + } - return 0; -} + printk(KERN_INFO "COOL_MODULE: Got major %d\n", major_num); + return 0; +} -static void __exit jmod_exit(void) +static void __exit jmod_exit(void) { - printk(KERN_INFO "COOL_MODULE: Nou moe\n"); - unregister_chrdev(major_num, "cooldev"); + printk(KERN_INFO "COOL_MODULE: Nou moe\n"); + unregister_chrdev(major_num, "cooldev"); } -module_init( jmod_init ); -module_exit( jmod_exit ); - +module_init(jmod_init); +module_exit(jmod_exit); diff --git a/sem3/osc/mm1/mm2/tprog.c b/sem3/osc/mm1/mm2/tprog.c index bb04778..82c9fb2 100644 --- a/sem3/osc/mm1/mm2/tprog.c +++ b/sem3/osc/mm1/mm2/tprog.c @@ -19,26 +19,26 @@ void timer_handler(int signum) /* Calculate new alarm */ tv->tv_sec *= SPEED; if (tv->tv_sec == 0) { - /* If tv_usec is 0 set i to 1 sec otherwise half it */ - if (tv->tv_usec == 0) { - tv->tv_usec = 999999; - } else if (tv->tv_usec > ENDUSEC) { - tv->tv_usec *= SPEED; - if (tv->tv_usec < ENDUSEC) { - tv->tv_usec = ENDUSEC; - } - } else { - /* Return letting the timer be set to ENDUSEC */ - return; - } + /* If tv_usec is 0 set i to 1 sec otherwise half it */ + if (tv->tv_usec == 0) { + tv->tv_usec = 999999; + } else if (tv->tv_usec > ENDUSEC) { + tv->tv_usec *= SPEED; + if (tv->tv_usec < ENDUSEC) { + tv->tv_usec = ENDUSEC; + } + } else { + /* Return letting the timer be set to ENDUSEC */ + return; + } } printf("Set to %d and %d\n", timer.it_value.tv_sec, timer.it_value.tv_usec); /* Set alarm */ int err = setitimer(ITIMER_REAL, &timer, NULL); if (err) { - printf("Hey we got an error guys\n"); - exit(1); + printf("Hey we got an error guys\n"); + exit(1); } } diff --git a/sem3/osc/mm11/regn/symtab.c b/sem3/osc/mm11/regn/symtab.c index 35799a5..9edcf72 100644 --- a/sem3/osc/mm11/regn/symtab.c +++ b/sem3/osc/mm11/regn/symtab.c @@ -4,50 +4,49 @@ unsigned int hash(char *s) { - uint32_t hv = 0; - for ( int i = 0; s[i] != '\0'; i++ ) { - // take MSB 6 bits of hv and xors with LSB of s[i] - uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f); - - // Push those back on hv - hv = (hv << 4) | v; - } - // Return appropriate size - return hv % HASHSIZE; + uint32_t hv = 0; + for (int i = 0; s[i] != '\0'; i++) { + // take MSB 6 bits of hv and xors with LSB of s[i] + uint32_t v = (hv >> 26) ^ (s[i] & 0x3f); + + // Push those back on hv + hv = (hv << 4) | v; + } + // Return appropriate size + return hv % HASHSIZE; } - symnode_t *sym_insert(char *var) { - unsigned int index = hash(var); + unsigned int index = hash(var); - // Save old value - symnode_t *oldSym = symbolarray[index]; + // Save old value + symnode_t *oldSym = symbolarray[index]; - // Make new - symbolarray[index] = malloc(sizeof(symnode_t)); - if ( symbolarray[index] == NULL ) { - // If malloc failed - symbolarray[index] = oldSym; - return NULL; - } + // Make new + symbolarray[index] = malloc(sizeof(symnode_t)); + if (symbolarray[index] == NULL) { + // If malloc failed + symbolarray[index] = oldSym; + return NULL; + } - // Link old one - symbolarray[index]->next = oldSym; - symbolarray[index]->name = var; + // Link old one + symbolarray[index]->next = oldSym; + symbolarray[index]->name = var; - return symbolarray[index]; + return symbolarray[index]; } symnode_t *sym_lookup(char *var) { - unsigned int index = hash(var); - symnode_t *n = symbolarray[index]; + unsigned int index = hash(var); + symnode_t *n = symbolarray[index]; - // Look trough list - while (n != NULL && strcmp(n->name, var) != 0) { - n = n->next; - } + // Look trough list + while (n != NULL && strcmp(n->name, var) != 0) { + n = n->next; + } - return n; + return n; } diff --git a/sem3/osc/mm11/regn/symtab.h b/sem3/osc/mm11/regn/symtab.h index c61f3a8..b7b93ec 100644 --- a/sem3/osc/mm11/regn/symtab.h +++ b/sem3/osc/mm11/regn/symtab.h @@ -2,19 +2,19 @@ #define HASHSIZE 100 typedef struct symnode_struct { - char *name; - struct symnode_struct *next; - double value; + char *name; + struct symnode_struct *next; + double value; } symnode_t; symnode_t *sym_insert(char *var); symnode_t *sym_lookup(char *var); struct symnode { - struct symnode *next; - char *name; - int type; - double value; + struct symnode *next; + char *name; + int type; + double value; }; symnode_t *symbolarray[HASHSIZE]; diff --git a/sem4/embedded/emb_m2/myfloat_red.h b/sem4/embedded/emb_m2/myfloat_red.h index b553233..142d0bc 100644 --- a/sem4/embedded/emb_m2/myfloat_red.h +++ b/sem4/embedded/emb_m2/myfloat_red.h @@ -4,54 +4,51 @@ */ //low precision floating pt type -typedef struct myfloat -{ - signed char mantissa; - signed char exponent; +typedef struct myfloat { + signed char mantissa; + signed char exponent; } myfloat_type; - //convert from double to low precision type void doub2mydouble(double arg, myfloat_type *res) { - int exponent; - double temp; - exponent = ceil(log(abs(arg))/log(2)); //base 2 logarithm - temp=arg*pow(2,7-exponent); - res->mantissa = (signed char)temp; - res->exponent = exponent-7; + int exponent; + double temp; + exponent = ceil(log(abs(arg)) / log(2)); //base 2 logarithm + temp = arg * pow(2, 7 - exponent); + res->mantissa = (signed char)temp; + res->exponent = exponent - 7; } //convert from low precision type to double double myfloat2double(myfloat_type *arg1) { - double res = (double)(arg1->mantissa) * pow(2,arg1->exponent); - return res; + double res = (double)(arg1->mantissa) * pow(2, arg1->exponent); + return res; } //multiply to low precision types -void mult_float(myfloat_type *arg1,myfloat_type *arg2,myfloat_type *result) +void mult_float(myfloat_type *arg1, myfloat_type *arg2, myfloat_type *result) { - int temp; - unsigned char sign; - - sign=0x80 & ((unsigned char)arg1-> mantissa ^ (unsigned char)arg2-> mantissa); //find sign of result - - char i=0; - temp = (int)(arg1-> mantissa) * (int)(arg2-> mantissa); - - temp = temp & 0x7f00; //take away sign from product - - while(abs(temp)>128) - { - i++; - temp=temp>>1; - } - - result->mantissa = (unsigned char) temp; - - result->mantissa = result->mantissa | sign; //add recorded sign - - result->exponent = arg1->exponent + arg2->exponent + i; - + int temp; + unsigned char sign; + + sign = 0x80 & ((unsigned char)arg1->mantissa ^ + (unsigned char)arg2->mantissa); //find sign of result + + char i = 0; + temp = (int)(arg1->mantissa) * (int)(arg2->mantissa); + + temp = temp & 0x7f00; //take away sign from product + + while (abs(temp) > 128) { + i++; + temp = temp >> 1; + } + + result->mantissa = (unsigned char)temp; + + result->mantissa = result->mantissa | sign; //add recorded sign + + result->exponent = arg1->exponent + arg2->exponent + i; } diff --git a/sem4/embedded/emb_m4/jrnl/regs.h b/sem4/embedded/emb_m4/jrnl/regs.h index 3f6ae03..cd475f5 100644 --- a/sem4/embedded/emb_m4/jrnl/regs.h +++ b/sem4/embedded/emb_m4/jrnl/regs.h @@ -2,80 +2,78 @@ #define REGS_H // Taken from Jens -#define PUSHREGS() __asm__ volatile ( \ - "push r1 \n" \ - "push r0 \n" \ - "in r0, __SREG__ \n" \ - "cli \n" \ - "push r0 \n" \ - "cli \n" \ - "push r2 \n" \ - "push r3 \n" \ - "push r4 \n" \ - "push r5 \n" \ - "push r6 \n" \ - "push r7 \n" \ - "push r8 \n" \ - "push r9 \n" \ - "push r10 \n" \ - "push r11 \n" \ - "push r12 \n" \ - "push r13 \n" \ - "push r14 \n" \ - "push r15 \n" \ - "push r16 \n" \ - "push r17 \n" \ - "push r18 \n" \ - "push r19 \n" \ - "push r20 \n" \ - "push r21 \n" \ - "push r22 \n" \ - "push r23 \n" \ - "push r24 \n" \ - "push r25 \n" \ - "push r26 \n" \ - "push r27 \n" \ - "push r28 \n" \ - "push r29 \n" \ - "push r30 \n" \ - "push r31 \n" \ - ) +#define PUSHREGS() \ + __asm__ volatile("push r1 \n" \ + "push r0 \n" \ + "in r0, __SREG__ \n" \ + "cli \n" \ + "push r0 \n" \ + "cli \n" \ + "push r2 \n" \ + "push r3 \n" \ + "push r4 \n" \ + "push r5 \n" \ + "push r6 \n" \ + "push r7 \n" \ + "push r8 \n" \ + "push r9 \n" \ + "push r10 \n" \ + "push r11 \n" \ + "push r12 \n" \ + "push r13 \n" \ + "push r14 \n" \ + "push r15 \n" \ + "push r16 \n" \ + "push r17 \n" \ + "push r18 \n" \ + "push r19 \n" \ + "push r20 \n" \ + "push r21 \n" \ + "push r22 \n" \ + "push r23 \n" \ + "push r24 \n" \ + "push r25 \n" \ + "push r26 \n" \ + "push r27 \n" \ + "push r28 \n" \ + "push r29 \n" \ + "push r30 \n" \ + "push r31 \n") -#define POPREGS() __asm__ volatile ( \ - "pop r31 \n" \ - "pop r30 \n" \ - "pop r29 \n" \ - "pop r28 \n" \ - "pop r27 \n" \ - "pop r26 \n" \ - "pop r25 \n" \ - "pop r24 \n" \ - "pop r23 \n" \ - "pop r22 \n" \ - "pop r21 \n" \ - "pop r20 \n" \ - "pop r19 \n" \ - "pop r18 \n" \ - "pop r17 \n" \ - "pop r16 \n" \ - "pop r15 \n" \ - "pop r14 \n" \ - "pop r13 \n" \ - "pop r12 \n" \ - "pop r11 \n" \ - "pop r10 \n" \ - "pop r9 \n" \ - "pop r8 \n" \ - "pop r7 \n" \ - "pop r6 \n" \ - "pop r5 \n" \ - "pop r4 \n" \ - "pop r3 \n" \ - "pop r2 \n" \ - "pop r0 \n" \ - "out __SREG__, r0 \n" \ - "pop r0 \n" \ - "pop r1 \n" \ - ) +#define POPREGS() \ + __asm__ volatile("pop r31 \n" \ + "pop r30 \n" \ + "pop r29 \n" \ + "pop r28 \n" \ + "pop r27 \n" \ + "pop r26 \n" \ + "pop r25 \n" \ + "pop r24 \n" \ + "pop r23 \n" \ + "pop r22 \n" \ + "pop r21 \n" \ + "pop r20 \n" \ + "pop r19 \n" \ + "pop r18 \n" \ + "pop r17 \n" \ + "pop r16 \n" \ + "pop r15 \n" \ + "pop r14 \n" \ + "pop r13 \n" \ + "pop r12 \n" \ + "pop r11 \n" \ + "pop r10 \n" \ + "pop r9 \n" \ + "pop r8 \n" \ + "pop r7 \n" \ + "pop r6 \n" \ + "pop r5 \n" \ + "pop r4 \n" \ + "pop r3 \n" \ + "pop r2 \n" \ + "pop r0 \n" \ + "out __SREG__, r0 \n" \ + "pop r0 \n" \ + "pop r1 \n") #endif |