4 files changed, 381 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..6db5985
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+.makeopts
+*.so
+*.o
+*.a
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..cc06e43
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,136 @@
+# Makefile for hax's table stuff
+#
+# Written by: Test_User <hax@andrewyu.org>
+#
+# This is free and unencumbered software released into the public
+# domain.
+#
+# Anyone is free to copy, modify, publish, use, compile, sell, or
+# distribute this software, either in source code form or as a compiled
+# binary, for any purpose, commercial or non-commercial, and by any
+# means.
+#
+# In jurisdictions that recognize copyright laws, the author or authors
+# of this software dedicate any and all copyright interest in the
+# software to the public domain. We make this dedication for the benefit
+# of the public at large and to the detriment of our heirs and
+# successors. We intend this dedication to be an overt act of
+# relinquishment in perpetuity of all present and future rights to this
+# software under copyright law.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+# OTHER DEALINGS IN THE SOFTWARE.
+
+ORIGINAL_CFLAGS := $(CFLAGS)
+ORIGINAL_LDFLAGS := $(LDFLAGS)
+
+INCLUDEFLAGS =
+
+LDFLAGS =
+
+.makeopts:
+	> .makeopts
+	printf '%s\n' 'LAST_SAFE_STACK = $(SAFE_STACK)' >> .makeopts
+	printf '%s\n' 'LAST_HAX_STRING_PATH = $(HAX_STRING_PATH)' >> .makeopts
+	printf '%s\n' 'LAST_CFLAGS = $(ORIGINAL_CFLAGS)' >> .makeopts
+	printf '%s\n' 'LAST_LDFLAGS = $(ORIGINAL_LDFLAGS)' >> .makeopts
+	printf '%s\n' 'LAST_CC = $(CC)' >> .makeopts
+
+$(shell [ -e .makeopts ] || > .makeopts)
+
+include .makeopts
+
+rebuild = 0
+
+# tabs not allowed :(
+ifneq ($(SAFE_STACK),)
+ifneq ($(SAFE_STACK),$(LAST_SAFE_STACK))
+rebuild = 1
+endif
+else
+SAFE_STACK := $(LAST_SAFE_STACK)
+endif
+
+ifneq ($(HAX_STRING_PATH),)
+ifneq ($(HAX_STRING_PATH),$(LAST_HAX_STRING_PATH))
+rebuild = 1
+endif
+else
+HAX_STRING_PATH := $(LAST_HAX_STRING_PATH)
+endif
+
+ifneq ($(ORIGINAL_CFLAGS),)
+ifneq ($(ORIGINAL_CFLAGS),$(LAST_CFLAGS))
+rebuild = 1
+endif
+else
+ORIGINAL_CFLAGS := $(LAST_CFLAGS)
+CFLAGS += $(LAST_CFLAGS)
+endif
+
+ifneq ($(ORIGINAL_LDFLAGS),)
+ifneq ($(ORIGINAL_LDFLAGS),$(LAST_LDFLAGS))
+rebuild = 1
+endif
+else
+ORIGINAL_LDFLAGS := $(LAST_LDFLAGS)
+LDFLAGS += $(LAST_LDFLAGS)
+endif
+
+ifneq ($(CC),)
+ifneq ($(CC),$(LAST_CC))
+rebuild = 1
+endif
+else
+CC := $(LAST_CC)
+endif
+
+ifeq ($(rebuild),1)
+.PHONY: .makeopts
+endif
+
+CFLAGS += $(INCLUDEFLAGS) -fPIC -fno-plt -D_REENTRANT -ggdb3 -Wall -Wextra -Wsign-conversion -Wno-unknown-warning-option -Wno-unused-parameter -Wno-implicit-fallthrough -Wno-alloc-size -std=gnu99
+
+ifneq ($(HAX_STRING_PATH),)
+CFLAGS += -I$(HAX_STRING_PATH)
+endif
+
+LDFLAGS += -lhax_string_utils
+
+ifneq ($(HAX_STRING_PATH),)
+LDFLAGS += -L$(HAX_STRING_PATH)
+endif
+
+
+ifeq ($(SAFE_STACK),1)
+CFLAGS += -fstack-check
+endif
+
+
+DEPS = $(shell $(CC) $(CFLAGS) -M -MT $(1).$(2) $(1).c | sed 's_\\$$__') .makeopts Makefile
+
+
+.PHONY: all clean
+# 'lib' prefix mandated bleh
+all: libhax_table.a libhax_table.so
+
+%.o: %.c
+	$(CC) $(CFLAGS) -c $< -o $@
+
+lib%.so: %.o
+	$(LD) $(LDFLAGS) -shared $< -o $@
+
+lib%.a: %.o
+	$(AR) rcs $@ $<
+
+$(call DEPS,hax_table,o)
+
+clean:
+	for file in `find . -name '*.so'`; do $(RM) $$file; done
+	for file in `find . -name '*.o'`; do $(RM) $$file; done
+	for file in `find . -name '*.a'`; do $(RM) $$file; done
diff --git a/hax_table.c b/hax_table.c
new file mode 100644
index 0000000..0b89a35
--- /dev/null
+++ b/hax_table.c
@@ -0,0 +1,190 @@
+// My table library thing
+//
+// Written by: Test_User <hax@andrewyu.org>
+//
+// This is free and unencumbered software released into the public
+// domain.
+//
+// Anyone is free to copy, modify, publish, use, compile, sell, or
+// distribute this software, either in source code form or as a compiled
+// binary, for any purpose, commercial or non-commercial, and by any
+// means.
+//
+// In jurisdictions that recognize copyright laws, the author or authors
+// of this software dedicate any and all copyright interest in the
+// software to the public domain. We make this dedication for the benefit
+// of the public at large and to the detriment of our heirs and
+// successors. We intend this dedication to be an overt act of
+// relinquishment in perpetuity of all present and future rights to this
+// software under copyright law.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+
+#include <string.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+
+#include "hax_string.h"
+#include "hax_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) {
+		if (a.len < b.len)
+			return -1;
+		else if (a.len > b.len)
+			return 1;
+	}
+
+	return val;
+}
+
+static inline size_t search(struct table tbl, struct string name, char *exists) {
+	if (tbl.len == 0) {
+		*exists = 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) {
+	char exists;
+	size_t index = search(*tbl, name, &exists);
+
+	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) {
+	char exists;
+	size_t index = search(tbl, name, &exists);
+	if (!exists)
+		return 0;
+
+	return tbl.array[index].ptr;
+}
+
+char has_table_index(struct table tbl, struct string name) {
+	char exists;
+	search(tbl, name, &exists);
+	return exists;
+}
+
+void * remove_table_index(struct table *tbl, struct string name) {
+	char exists;
+	size_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 - 1) * sizeof(*(tbl->array)));
+	tbl->len--;
+
+	void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * tbl->len);
+	if (tmp || (tbl->len == 0))
+		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;
+}
+
+void clear_table(struct table *tbl) {
+	for (size_t i = 0; i < tbl->len; i++)
+		free(tbl->array[i].name.data);
+
+	tbl->array = realloc(tbl->array, 0);
+	tbl->len = 0;
+}
+
+size_t get_table_offset(struct table tbl, struct string name, char *exists) {
+	return search(tbl, name, exists);
+}
+
+// TODO: Proper lookup
+void * get_table_prefix(struct table tbl, struct string name) {
+	for (size_t i = 0; i < tbl.len; i++)
+		if (tbl.array[i].name.len <= name.len && memcmp(tbl.array[i].name.data, name.data, tbl.array[i].name.len) == 0)
+			return tbl.array[i].ptr;
+
+	return 0;
+}
diff --git a/hax_table.h b/hax_table.h
new file mode 100644
index 0000000..90cbbdb
--- /dev/null
+++ b/hax_table.h
@@ -0,0 +1,51 @@
+// Header for my table library thing
+//
+// Written by: Test_User <hax@andrewyu.org>
+//
+// This is free and unencumbered software released into the public
+// domain.
+//
+// Anyone is free to copy, modify, publish, use, compile, sell, or
+// distribute this software, either in source code form or as a compiled
+// binary, for any purpose, commercial or non-commercial, and by any
+// means.
+//
+// In jurisdictions that recognize copyright laws, the author or authors
+// of this software dedicate any and all copyright interest in the
+// software to the public domain. We make this dedication for the benefit
+// of the public at large and to the detriment of our heirs and
+// successors. We intend this dedication to be an overt act of
+// relinquishment in perpetuity of all present and future rights to this
+// software under copyright law.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+// OTHER DEALINGS IN THE SOFTWARE.
+
+#pragma once
+
+#include "hax_string.h"
+
+struct table_index {
+	struct string name;
+	void *ptr;
+};
+
+struct table {
+	struct table_index *array;
+	size_t len;
+};
+
+extern int set_table_index(struct table *tbl, struct string name, void *ptr);
+extern void * get_table_index(struct table tbl, struct string name);
+extern char has_table_index(struct table tbl, struct string name);
+extern void * remove_table_index(struct table *tbl, struct string name); // returns same as get_table_index
+extern void clear_table(struct table *tbl);
+extern size_t get_table_offset(struct table tbl, struct string name, char *exists);
+
+// Longest index that <name> starts with
+extern void * get_table_prefix(struct table tbl, struct string name);