Added hashtable for indexing vertexes

3 files changed, 90 insertions, 32 deletions

diff --git a/sem1/algo/workshop2/dfs/dfs b/sem1/algo/workshop2/dfs/dfs
new file mode 100755
index 0000000..f608d28
--- /dev/null
+++ b/sem1/algo/workshop2/dfs/dfs
diff --git a/sem1/algo/workshop2/dfs/graph.c b/sem1/algo/workshop2/dfs/graph.c
index 502b1a9..11ee07f 100644
--- a/sem1/algo/workshop2/dfs/graph.c
+++ b/sem1/algo/workshop2/dfs/graph.c
@@ -1,15 +1,58 @@
 #include <stdio.h>
+#include <stdint.h>
 #include <stdlib.h>
+#include <string.h>
+
 #include "graph.h"
 
-static vertex_t *create_vertex(char ref) {
+// 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;
+}
+
+
+static void table_insert(graph_t *g, vertex_t *v, char *var) {
+	unsigned int index = hash(var);
+
+	// Save old value
+	vertex_t *oldSym = g->hashtable[index];
+
+	// Make new
+	g->hashtable[index] = v;
+
+	// 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];
+
+	// Look trough list
+	while(n != NULL && strcmp(n->ref, var) != 0) {
+		n = n->next;
+	}
+
+	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 = ref;
 	v->color = COLOR_WHITE;
-	v->p = NULL;
+	v->next = NULL;
 	v->adj = NULL;
 	return v;
 }
@@ -43,14 +86,16 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
 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;
-			}
+		vertex_t *v = e ? e->from : NULL;
+
+		// Find next vertex
+		v = vertex_next(g, v);
+
+		// Check if found
+		if( v ) {
+			return v->adj;
 		}
+
 		// No next vertex
 		return NULL;
 	}
@@ -60,39 +105,49 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
 }
 
 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];
+	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 NULL;
+	return v->next;
 }
 
-void graph_edge(graph_t *g, char from, char to, int weight) {
+void graph_edge(graph_t *g, char *from, char *to, int weight) {
+	vertex_t *fromv, *tov;
 	// Does a exists
-	if( g->vertexes[from] == NULL ) {
-		g->vertexes[from] = create_vertex(from);
+	if( (fromv = table_lookup(g, from)) == NULL ) {
+		fromv = create_vertex(from);
+		table_insert(g, fromv, from);
 	}
 	// What about b
-	if( g->vertexes[to] == NULL ) {
-		g->vertexes[to] = create_vertex(to);
+	if( (tov = table_lookup(g, to)) == NULL ) {
+		tov = create_vertex(to);
+		table_insert(g, tov, to);
 	}
 
 	// Add edge
-	create_edge(g->vertexes[from], g->vertexes[to], weight);
+	create_edge(fromv, tov, weight);
 }
 
-int graph_print_adj(graph_t *g, char ref) {
-	if( g->vertexes[ref] == NULL ) {
+int graph_print_adj(graph_t *g, char *ref) {
+	vertex_t *v = table_lookup(g, ref);
+	if( v == NULL ) {
 		return 1;
 	}
 	
-	edge_t *e = g->vertexes[ref]->adj;
+	edge_t *e = v->adj;
 	printf("[ ");
 	while(e && e->from->ref == ref) {
-		printf("%c[%d] ", e->to->ref, e->weight);
+		printf("%s[%d] ", e->to->ref, e->weight);
 		e = e->next;
 	}
 	printf("]\n");
@@ -107,13 +162,13 @@ int graph_to_dot(FILE *f, graph_t *g) {
 	// Label all nodes
 	vertex_t *v = vertex_next(g, NULL);
 	while( v ) {
-		fprintf(f, "%c [label=\"%c\"];\n", v->ref, v->ref);
+		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, "%c -> %c [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : "");
+		fprintf(f, "%s -> %s [label = %d];\n", e->from->ref, e->to->ref, e->weight);
 		e = edge_next(g, e);
 	}
 
diff --git a/sem1/algo/workshop2/dfs/graph.h b/sem1/algo/workshop2/dfs/graph.h
index 67ac1dc..e169a8a 100644
--- a/sem1/algo/workshop2/dfs/graph.h
+++ b/sem1/algo/workshop2/dfs/graph.h
@@ -5,6 +5,8 @@
 #define COLOR_GRAY  1
 #define COLOR_BLACK 2
 
+#define HASHSIZE 128
+
 struct vertex_struct;
 
 // Linked list
@@ -18,24 +20,25 @@ typedef struct edge_struct {
 } edge_t;
 
 typedef struct vertex_struct {
-	char ref;
+	char *ref;
 	int color;
 
 	int dtime;
 	int ftime;
 
-	struct vertex_struct *p;
 	edge_t *adj;
+
+	// Hash table stuff
+	struct vertex_struct *next;
 } vertex_t;
 
 typedef struct {
-	vertex_t *vertexes[128];
-
+	vertex_t *hashtable[128];
 } graph_t;
 
 int graph_to_dot(FILE *f, graph_t *g);
-int graph_print_adj(graph_t *g, char ref);
-void graph_edge(graph_t *g, char from, char to, int weight);
+int graph_print_adj(graph_t *g, char *ref);
+void graph_edge(graph_t *g, char *from, char *to, int weight);
 edge_t *edge_next(graph_t *g, edge_t *e);
 vertex_t *vertex_next(graph_t *g, vertex_t *v);