C HaxServ

1 files changed, 163 insertions, 0 deletions

diff --git a/table.c b/table.c
new file mode 100644
index 0000000..f663139
--- /dev/null
+++ b/table.c
@@ -0,0 +1,163 @@
+#include <string.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+
+#include "types.h"
+#include "table.h"
+
+// currently going with a binary lookup...
+
+static inline int compare(struct string a, struct string b) {
+	size_t len;
+	if (a.len > b.len)
+		len = b.len;
+	else
+		len = a.len;
+
+	int val = memcmp(a.data, b.data, len);
+
+	if (val == 0 && a.len != b.len)
+		return 1;
+	else
+		return val;
+}
+
+static inline uint64_t search(struct table tbl, struct string name, uint8_t *exists) {
+	if (tbl.len == 0)
+		return 0;
+
+	size_t low = 0, high = tbl.len - 1;
+
+	size_t mid = high/2;
+
+	while (low != high) {
+		int val = compare(tbl.array[mid].name, name);
+
+		if (val == 0) {
+			*exists = 1;
+			return mid;
+		} else if (val > 0) {
+			low = mid + 1;
+			if (mid > low)
+				break;
+			if (low > high)
+				low = high;
+		} else {
+			high = mid - 1;
+			if (mid < high)
+				break;
+			if (high < low)
+				high = low;
+		}
+
+		mid = low + ((high-low)/2);
+	}
+
+	int val = compare(tbl.array[mid].name, name);
+	if (val > 0) {
+		*exists = 0;
+		return mid+1;
+	} else if (val == 0) {
+		*exists = 1;
+		return mid;
+	} else {
+		*exists = 0;
+		return mid;
+	}
+}
+
+int set_table_index(struct table *tbl, struct string name, void *ptr) {
+	uint8_t exists, err;
+	uint64_t index = search(*tbl, name, &exists);
+
+	if (index == tbl->len) {
+		void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
+		if (tmp == 0)
+			return 1;
+
+		tbl->array = tmp;
+
+		tbl->len++;
+	} else if (!exists) {
+		void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
+		if (tmp == 0)
+			return 1;
+
+		tbl->array = tmp;
+
+		memmove(&(tbl->array[index+1]), &(tbl->array[index]), (tbl->len - index) * sizeof(*(tbl->array)));
+		tbl->len++;
+	} else {
+		tbl->array[index].ptr = ptr;
+
+		return 0; // don't overwrite old allocated name
+	}
+
+	char *data = malloc(name.len);
+	if (data == 0)
+		return 1;
+
+	memcpy(data, name.data, name.len);
+
+	tbl->array[index] = (struct table_index){{data, name.len}, ptr};
+
+	return 0;
+}
+
+void * get_table_index(struct table tbl, struct string name) {
+	if (tbl.len == 0)
+		return 0;
+
+	size_t low = 0, high = tbl.len - 1;
+
+	size_t mid = high/2;
+
+	while (low != high) {
+		int val = compare(tbl.array[mid].name, name);
+		if (val == 0) {
+			return tbl.array[mid].ptr;
+		} else if (val > 0) {
+			low = mid + 1;
+			if (mid > low)
+				return 0;
+			if (low > high)
+				low = high;
+		} else {
+			high = mid - 1;
+			if (mid < high)
+				return 0;
+			if (high < low)
+				high = low;
+		}
+
+		mid = low + ((high-low)/2);
+	}
+
+	if (compare(tbl.array[mid].name, name) == 0)
+		return tbl.array[mid].ptr;
+	else
+		return 0;
+}
+
+void * remove_table_index(struct table *tbl, struct string name) {
+	uint8_t exists, err;
+	uint64_t index = search(*tbl, name, &exists);
+
+	if (!exists)
+		return 0;
+
+	void *ptr = tbl->array[index].ptr;
+	free(tbl->array[index].name.data);
+
+	memmove(&(tbl->array[index]), &(tbl->array[index+1]), (tbl->len - index) * sizeof(*(tbl->array)));
+	tbl->len--;
+
+	void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * tbl->len);
+	if (tmp)
+		tbl->array = tmp;
+	// else: realloc failed on shrinking... so now we have a table that's allocated a bit too big, not much of an issue
+
+	return ptr;
+}