added random stuff which hasn't beend added because yeah

10 files changed, 393 insertions, 0 deletions

diff --git a/lib/util/a.out b/lib/util/a.out
new file mode 100755
index 0000000..2457844
--- /dev/null
+++ b/lib/util/a.out
diff --git a/lib/util/circulardoublelinkedlist.h b/lib/util/circulardoublelinkedlist.h
new file mode 100644
index 0000000..3e5c524
--- /dev/null
+++ b/lib/util/circulardoublelinkedlist.h
@@ -0,0 +1,54 @@
+#ifndef __CIRCULARLIST__
+#define __CIRCULARLIST__
+
+/**
+  * ciruclar double linked list implementation
+  *
+  **/
+#include "util.h"
+#include<stdio.h>
+
+struct circular_list {
+	struct circular_list *next;
+	struct circular_list *prev;
+};
+
+#define CIRCULARLIST_INIT(name)	do { (name)->next = (name); (name)->prev = (name); } while(0);
+
+static int inline __circular_list_insert(struct circular_list *prev, struct circular_list *new, struct circular_list *next)
+{
+	prev->next = new;
+	new->prev = prev;
+	new->next = next;
+	next->prev = new;
+}
+
+static int inline circular_list_insert_after(struct circular_list *list, struct circular_list *new_elem)
+{
+	return __circular_list_insert(list, new_elem, list->next);
+}
+
+static int inline circular_list_insert_before(struct circular_list *list, struct circular_list *new_elem)
+{
+	return __circular_list_insert(list->prev, new_elem, list);
+}
+
+static void inline __circular_list_delete(struct circular_list *prev, struct circular_list *elem, struct circular_list *next)
+{
+	prev->next = next;
+	next->prev = prev;
+	elem->next = elem;
+	elem->prev = elem;
+}
+static void inline circular_list_delete(struct circular_list *elem)
+{
+	__circular_list_delete(elem->prev, elem, elem->next);
+}
+
+#define circular_list_get_prev(elem)	(elem)->prev
+#define circular_list_get_next(elem)	(elem)->next
+
+#define CIRCULARLIST_FOR_EACH(pos, head)	for(pos = head->next; pos != head; pos = pos->next)
+#define CONTAINER_OF(ptr, type, member)	((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
+
+#endif
diff --git a/lib/util/doublelinkedlist.h b/lib/util/doublelinkedlist.h
new file mode 100644
index 0000000..460d799
--- /dev/null
+++ b/lib/util/doublelinkedlist.h
@@ -0,0 +1,58 @@
+#ifndef __LIST__
+#define __LIST__
+
+/**
+  * double linked list implementation
+  *
+  **/
+
+#include<stdio.h>
+
+struct list {
+	struct list *next;
+	struct list *prev;
+};
+
+#define LIST_INIT(name)	do { (name)->next = NULL; (name)->prev = NULL; } while(0);
+
+static int inline __list_insert(struct list *prev, struct list *new, struct list *next)
+{
+	if(prev != NULL)
+		prev->next = new;
+	new->prev = prev;
+	new->next = next;
+	if(next != NULL)
+		next->prev = new;
+}
+
+static int inline list_insert_after(struct list *list, struct list *new_elem)
+{
+	return __list_insert(list, new_elem, list->next);
+}
+
+static int inline list_insert_before(struct list *list, struct list *new_elem)
+{
+	return __list_insert(list->prev, new_elem, list);
+}
+
+static void inline __list_delete(struct list *prev, struct list *elem, struct list *next)
+{
+	if(prev != NULL)
+		prev->next = next;
+	if(next != NULL)
+		next->prev = prev;
+	elem->next = elem;
+	elem->prev = elem;
+}
+static void inline list_delete(struct list *elem)
+{
+	__list_delete(elem->prev, elem, elem->next);
+}
+
+#define list_get_prev(elem)	(elem)->prev
+#define list_get_next(elem)	(elem)->next
+
+#define LIST_TO_END(pos, head)	for(pos = head; pos != NULL; pos = pos->next)
+#define CONTAINER_OF(ptr, type, member)	((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
+
+#endif
diff --git a/lib/util/hashtable.h b/lib/util/hashtable.h
new file mode 100644
index 0000000..57ac495
--- /dev/null
+++ b/lib/util/hashtable.h
@@ -0,0 +1,159 @@
+#ifndef __HASHMAP__
+#define __HASHMAP__
+
+#include <openssl/sha.h>
+#include <string.h>
+#include "circulardoublelinkedlist.h"
+#include "util.h"
+
+struct ht_item {
+	char *hash;
+	void *data;
+	unsigned int data_length;
+	struct list list;
+};
+
+struct hashtable {
+	struct ht_item **begin;
+	unsigned int length;
+	unsigned int hash_length;
+	void (*hash_function)(void *data, unsigned int data_length, char *res);
+};
+
+
+int __ht_init(struct hashtable *ht, unsigned int number_elem,
+		unsigned int hash_length, void (*func)(void *data,
+		unsigned int data_length, char *res))
+{
+	ht->begin = xmalloc(sizeof(struct ht_item)*number_elem);
+	ht->length = number_elem;
+	ht->hash_length = hash_length;
+	ht->hash_function = func;
+}
+
+int ht_destroy(struct hashtable *ht)
+{
+	free(ht->begin);
+}
+
+void compute_hash_sha1(void *data, unsigned int data_length, char *res)
+{
+	SHA_CTX sha1;
+
+	SHA1_Init(&sha1);
+	SHA1_Update(&sha1, data, data_length);
+	SHA1_Final(res, &sha1);
+
+}
+
+int ht_init_sha1(struct hashtable *ht)
+{
+	__ht_init(ht, 300, 20, compute_hash_sha1);
+}
+
+void *ht_is_in_list(struct list *list, char *hash, int hash_length)
+{
+	struct list *head, *iter;
+	struct ht_item *res = NULL;
+
+	head = list;
+	res = CONTAINER_OF(head, struct ht_item, list);
+	if(memcmp(res->hash, hash, hash_length) == 0)
+		return res->data;
+
+	CIRCULARLIST_FOR_EACH(iter,head) {
+		res = CONTAINER_OF(iter, struct ht_item, list);
+		if(memcmp(res->hash, hash, hash_length) == 0)
+			return res->data;
+	}
+
+	return NULL;
+}
+
+void ht_add(struct hashtable *ht, void *data, unsigned int data_length,
+		void *key, unsigned int key_length)
+{
+	unsigned long index;
+	struct ht_item *new_elem = xmalloc(sizeof(struct ht_item));
+	new_elem->hash =  xmalloc(ht->hash_length);
+	new_elem->data = xmalloc(data_length);
+
+	memcpy(new_elem->data, data, data_length);
+	new_elem->data_length = data_length;
+	CIRCULARLIST_INIT(&new_elem->list);
+
+	ht->hash_function(key, key_length, new_elem->hash);
+	memcpy(&index, new_elem->hash, sizeof(unsigned long));
+	index = index % ht->length;
+
+	if(ht->begin[index] == NULL) {
+		ht->begin[index] = new_elem;
+		return;
+	}
+
+	if(ht_is_in_list(&(ht->begin[index]->list), new_elem->hash,
+			ht->hash_length) == NULL) {
+		list_insert_after(&(ht->begin[index]->list), &new_elem->list);
+		return;
+	}
+}
+
+void *ht_get(struct hashtable *ht, void *key, unsigned int key_length)
+{
+	char *hash = xmalloc(ht->hash_length);
+	unsigned long index;
+
+	ht->hash_function(key, key_length, hash);
+	memcpy(&index, hash, sizeof(unsigned long));
+	index = index % ht->length;
+
+	struct ht_item *res = ht_is_in_list(&(ht->begin[index]->list), hash, ht->hash_length);
+	free(hash);
+	return res;
+}
+
+void __ht_delete_item(struct ht_item *delete)
+{
+	free(delete->hash);
+	free(delete->data);
+	free(delete);
+}
+
+void ht_list_delete(struct list *list, unsigned long index, char *hash,
+		unsigned int hash_length)
+{
+	struct list *head, *iter;
+	struct ht_item *res;
+
+	head = list;
+	res = CONTAINER_OF(head, struct ht_item, list);
+	if (memcmp(res->hash, hash, hash_length) == 0) {
+		list_delete(head);
+		__ht_delete_item(res);
+		return;
+	}
+
+	CIRCULARLIST_FOR_EACH(iter, head) {
+		res = CONTAINER_OF(iter, struct ht_item, list);
+		if (memcmp(res->hash, hash, hash_length) == 0) {
+			list_delete(iter);
+			__ht_delete_item(res);
+			return;
+		}
+	}
+}
+
+void ht_delete(struct hashtable *ht, void *key, unsigned int key_length)
+{
+	char *hash = xmalloc(ht->hash_length);
+	unsigned long index;
+
+	ht->hash_function(key, key_length, hash);
+	memcpy(&index, hash, sizeof(unsigned long));
+	index = index % ht->length;
+
+	ht_list_delete(&ht->begin[index]->list, index, hash, ht->hash_length);
+	free(hash);
+}
+
+#endif
diff --git a/lib/util/hashtable.h.gch b/lib/util/hashtable.h.gch
new file mode 100644
index 0000000..cf2b3d2
--- /dev/null
+++ b/lib/util/hashtable.h.gch
diff --git a/lib/util/set.h b/lib/util/set.h
new file mode 100644
index 0000000..bd05351
--- /dev/null
+++ b/lib/util/set.h
@@ -0,0 +1,39 @@
+#ifndef __SET_H__
+#define __SET_H__
+#include <stdlib.h>
+#include "hashtable.h"
+
+/**
+  * implementation of a set based on a hashtable implementation
+  *
+  **/
+
+typedef struct hashtable set_t;
+
+void set_init(set_t *set)
+{
+	ht_init_sha1(set);
+}
+
+
+void set_insert(set_t *set, void *data, unsigned int data_length)
+{
+	ht_add(set, data, data_length, data, data_length);
+}
+
+unsigned int set_is_in_set(set_t *set, void *data, unsigned int data_length)
+{
+	if(ht_get(set, data, data_length) == NULL)
+		return 0;
+	else
+		return 1;
+}
+
+void set_delete(set_t *set, void *data, unsigned int data_length)
+{
+	ht_delete(set, data, data_length);
+}
+
+#define SET_FOR_EACH
+
+#endif
diff --git a/lib/util/set.h.gch b/lib/util/set.h.gch
new file mode 100644
index 0000000..2c1b1fe
--- /dev/null
+++ b/lib/util/set.h.gch
diff --git a/lib/util/test_hash.c b/lib/util/test_hash.c
new file mode 100644
index 0000000..19d2aae
--- /dev/null
+++ b/lib/util/test_hash.c
@@ -0,0 +1,48 @@
+#include "hashtable.h"
+#include "set.h"
+
+
+int main()
+{
+	int i;
+	struct hashtable ht;
+
+	char *msg = malloc(100);
+	memcpy(msg, "Hallo dies ist meine Message\n", 20);
+	char *key = malloc(20);
+
+	ht_init_sha1(&ht);
+	key[1] = '\n';
+	for(i=0;i<156;i++) {
+		key[0] = i;
+		msg[0] = i;
+		ht_add(&ht, msg, strlen(msg), key, strlen(key));
+	}
+
+
+	ht_delete(&ht, key, strlen(key));
+	char *ret = ht_get(&ht, key, strlen(key));
+	if(ret != NULL)
+		printf("uuh das sollte eigtl nicht mehr da sein\n");
+
+	key[0] = 'a' + 3;
+	ret = ht_get(&ht, key, strlen(key));
+	if(ret == NULL)
+		printf("did not found data\n");
+
+	printf("message is: %s\n", msg);
+	printf("got data from ht: %s\n", ret);
+
+
+	set_t t;
+
+	set_init(&t);
+	set_insert(&t, msg, strlen(msg));
+	if(set_is_in_set(&t, msg, strlen(msg)) == 1)
+		printf("im set, alles gut\n");
+
+	set_delete(&t, msg, strlen(msg));
+	if(set_is_in_set(&t, msg, strlen(msg)) == 0)
+		printf("nicht merg im set, alles gut\n");
+
+}
diff --git a/lib/util/util.c b/lib/util/util.c
new file mode 100644
index 0000000..dd06869
--- /dev/null
+++ b/lib/util/util.c
@@ -0,0 +1,25 @@
+#include "util.h"
+
+void *die(char *text)
+{
+	printf("dieing: %s\n", text);
+	exit(1);
+}
+
+void *xmalloc(unsigned int size)
+{
+	void *mem = malloc(size);
+	if(mem == NULL)
+		die("out of memory");
+	else
+		return mem;
+}
+
+void *xrealloc(void *data, unsigned int size)
+{
+	void *mem = realloc(data, size);
+	if(mem == NULL)
+		die("out of memory");
+	else
+		return mem;
+}
diff --git a/lib/util/util.h b/lib/util/util.h
new file mode 100644
index 0000000..b998ef8
--- /dev/null
+++ b/lib/util/util.h
@@ -0,0 +1,10 @@
+#ifndef __UTIL_H__
+#define __UTIL_H__
+
+#include <stdlib.h>
+#include <stdio.h>
+
+void *die(char *text);
+void *xmalloc(unsigned int size);
+void *xrealloc(void *data, unsigned int size);
+#endif