diff options
-rw-r--r-- | .gitignore | 4 | ||||
-rw-r--r-- | Makefile | 136 | ||||
-rw-r--r-- | hax_table.c | 190 | ||||
-rw-r--r-- | hax_table.h | 51 |
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); |