more reorganizing

10 files changed, 360 insertions, 303 deletions

diff --git a/ds.c b/ds.h
index b599f36..a447e4c 100644
--- a/ds.c
+++ b/ds.h
@@ -1,21 +1,31 @@
-/* VARIOUS DATA STRUCTURES
+#ifndef DS_H_
+#define DS_H_
+
+/*
+VARIOUS DATA STRUCTURES
 - dynamic array
 - string builder
 - string hash table
-*/
 
+This file is self-contained and should not use anything from any project it's contained in.
+You can just #include it -- it's not huge, the functions are all static, and
+any reasonable compiler will ignore the unused code.
 
-// functions in this file suffixed with _ are not meant to be used outside here, unless you
-// know what you're doing
+functions in this file suffixed with _ are not meant to be used outside here, unless you
+know what you're doing
 
-// IMPORTANT NOTE: If you are using this with structures containing `long double`s, do
-//  #define ARR_LONG_DOUBLE
-// before including this file
-// ( otherwise the long doubles will not be aligned.
-//   this does mean that arrays waste 8 bytes of memory.
-//    which isnt important unless you're making a lot of arrays.)
+NOTE: even on 64-bit platforms, dynamic arrays can only hold ~2^32 elements.
+
+IMPORTANT NOTE: If you are using this with structures containing `long double`s, do
+       #define ARR_LONG_DOUBLE
+ before including this file
+ (otherwise the long doubles will not be aligned.
+  this does mean that arrays waste 8 bytes of memory.
+  which isnt important unless you're making a lot of arrays.)
+*/
 
 #include <stddef.h>
+
 typedef union {
 	long num;
 	void *ptr;
@@ -36,20 +46,40 @@ typedef struct {
 	ArrMaxAlign data[];
 } ArrHeader;
 
+typedef struct {
+	char *str;
+	size_t len;
+	uint64_t data[];
+} StrHashTableSlot;
+
+typedef StrHashTableSlot *StrHashTableSlotPtr;
+
+typedef struct {
+	StrHashTableSlot **slots;
+	size_t data_size;
+	size_t nentries; /* # of filled slots */
+} StrHashTable;
+
+typedef struct {
+	// dynamic array, including a null byte.
+	char *str;
+} StrBuilder;
+
+
 // watch out! do not call this function if arr is NULL.
-static inline ArrHeader *arr_hdr_(void *arr) {
+static ArrHeader *arr_hdr_(void *arr) {
 	return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
 }
 
-static inline u32 arr_len(const void *arr) {
+static u32 arr_len(const void *arr) {
 	return arr ? arr_hdr_((void*)arr)->len : 0;
 }
 
-static inline u32 arr_cap(void *arr) {
+static u32 arr_cap(void *arr) {
 	return arr ? arr_hdr_(arr)->cap : 0;
 }
 
-static inline unsigned arr_lenu(void *arr) {
+static unsigned arr_lenu(void *arr) {
 	return (unsigned)arr_len(arr);
 }
 
@@ -82,7 +112,7 @@ static void *arr_grow1_(void *arr, size_t member_size) {
 	}
 }
 
-static inline void *arr_add_ptr_(void **arr, size_t member_size) {
+static void *arr_add_ptr_(void **arr, size_t member_size) {
 	u8 *ret;
 	*arr = arr_grow1_(*arr, member_size);
 	if (*arr) {
@@ -99,6 +129,7 @@ static void arr_reserve_(void **arr, size_t member_size, size_t n) {
 		// too big; free arr.
 		if (*arr) free(arr_hdr_(*arr));
 		*arr = NULL;
+		return;
 	}
 	
 	if (n == 0) return;
@@ -221,31 +252,6 @@ static void *arr_remove_(void *arr, size_t member_size, size_t index) {
 // Similar to arr_reserve, but also sets the length of the array to n.
 #define arr_set_len(a, n) arr_set_len_((void **)&(a), sizeof *(a), (n))
 
-#if 0
-static void arrcstr_append_strn_(char **a, char const *s, size_t s_len) {
-	size_t curr_len = arr_len(*a);
-	size_t new_len = curr_len + s_len;
-	arr_reserve(*a, new_len + 1);
-	arr_set_len(*a, new_len);
-	memcpy(*a + curr_len, s, s_len);
-	(*a)[curr_len + s_len] = '\0';
-}
-
-static void arrcstr_shrink_(char **a, u32 new_len) {
-	ArrHeader *hdr = arr_hdr_(*a);
-	assert(hdr->cap > new_len);
-	hdr->len = new_len;
-	(*a)[new_len] = '\0';
-}
-
-// append to a C-string array
-#define arrcstr_append_str(a, s) arrcstr_append_strn_(&(a), (s), strlen(s))
-// take at most n bytes from s
-#define arrcstr_append_strn(a, s, n) arrcstr_append_strn_(&(a), (s), (n))
-// make the string smaller
-#define arrcstr_shrink(a, n) arrcstr_shrink_(&(a), (n))
-#endif
-
 #ifndef NDEBUG
 static void arr_test(void) {
 	u32 *arr = NULL;
@@ -265,32 +271,27 @@ static void arr_test(void) {
 }
 #endif
 
-typedef struct {
-	// dynamic array, including a null byte.
-	char *str;
-} StrBuilder;
-
-void str_builder_create(StrBuilder *builder) {
+static void str_builder_create(StrBuilder *builder) {
 	memset(builder, 0, sizeof *builder);
 	arr_add(builder->str, 0);
 }
 
-StrBuilder str_builder_new(void) {
+static StrBuilder str_builder_new(void) {
 	StrBuilder ret = {0};
 	str_builder_create(&ret);
 	return ret;
 }
 
-void str_builder_free(StrBuilder *builder) {
+static void str_builder_free(StrBuilder *builder) {
 	arr_free(builder->str);
 }
 
-void str_builder_clear(StrBuilder *builder) {
+static void str_builder_clear(StrBuilder *builder) {
 	str_builder_free(builder);
 	str_builder_create(builder);
 }
 
-void str_builder_append(StrBuilder *builder, const char *s) {
+static void str_builder_append(StrBuilder *builder, const char *s) {
 	assert(builder->str);
 	
 	size_t s_len = strlen(s);
@@ -301,8 +302,8 @@ void str_builder_append(StrBuilder *builder, const char *s) {
 	memcpy(builder->str + prev_len, s, s_len);
 }
 
-void str_builder_appendf(StrBuilder *builder, PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(2, 3);
-void str_builder_appendf(StrBuilder *builder, const char *fmt, ...) {
+static void str_builder_appendf(StrBuilder *builder, PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(2, 3);
+static void str_builder_appendf(StrBuilder *builder, const char *fmt, ...) {
 	// idk if you can always just pass NULL to vsnprintf
 	va_list args;
 	char fakebuf[2] = {0};
@@ -322,21 +323,21 @@ void str_builder_appendf(StrBuilder *builder, const char *fmt, ...) {
 }
 
 // append n null bytes.
-void str_builder_append_null(StrBuilder *builder, size_t n) {
+static void str_builder_append_null(StrBuilder *builder, size_t n) {
 	arr_set_len(builder->str, arr_len(builder->str) + n);
 }
 
-u32 str_builder_len(StrBuilder *builder) {
+static u32 str_builder_len(StrBuilder *builder) {
 	assert(builder->str);
 	return arr_len(builder->str) - 1;
 }
 
-char *str_builder_get_ptr(StrBuilder *builder, size_t index) {
+static char *str_builder_get_ptr(StrBuilder *builder, size_t index) {
 	assert(index <= str_builder_len(builder));
 	return &builder->str[index];
 }
 
-void str_builder_shrink(StrBuilder *builder, size_t new_len) {
+static void str_builder_shrink(StrBuilder *builder, size_t new_len) {
 	if (new_len > str_builder_len(builder)) {
 		assert(0);
 		return;
@@ -344,3 +345,114 @@ void str_builder_shrink(StrBuilder *builder, size_t new_len) {
 	arr_set_len(builder->str, new_len + 1);
 }
 
+
+static uint64_t str_hash(const char *str, size_t len) {
+	uint64_t hash = 0;
+	const char *p = str, *end = str + len;
+	for (; p < end; ++p) {
+		hash = ((hash * 1664737020647550361 + 123843) << 8) + 2918635993572506131*(uint64_t)*p;
+	}
+	return hash;
+}
+
+static void str_hash_table_create(StrHashTable *t, size_t data_size) {
+	t->slots = NULL;
+	t->data_size = data_size;
+	t->nentries = 0;
+}
+
+static StrHashTableSlot **str_hash_table_slot_get(StrHashTableSlot **slots, const char *s, size_t s_len, size_t i) {
+	StrHashTableSlot **slot;
+	size_t slots_cap = arr_len(slots);
+	while (1) {
+		assert(i < slots_cap);
+		slot = &slots[i];
+		if (!*slot) break;
+		if (s && (*slot)->str &&
+			s_len == (*slot)->len && memcmp(s, (*slot)->str, s_len) == 0)
+			break;
+		i = (i+1) % slots_cap;
+	}
+	return slot;
+}
+
+static void str_hash_table_grow(StrHashTable *t) {
+	size_t slots_cap = arr_len(t->slots);
+	if (slots_cap <= 2 * t->nentries) {
+		StrHashTableSlot **new_slots = NULL;
+		size_t new_slots_cap = slots_cap * 2 + 10;
+		arr_set_len(new_slots, new_slots_cap);
+		memset(new_slots, 0, new_slots_cap * sizeof *new_slots);
+		arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) {
+			StrHashTableSlot *slot = *slotp;
+			if (slot) {
+				uint64_t new_hash = str_hash(slot->str, slot->len);
+				StrHashTableSlot **new_slot = str_hash_table_slot_get(new_slots, slot->str, slot->len, new_hash % new_slots_cap);
+				*new_slot = slot;
+			}
+		}
+		arr_clear(t->slots);
+		t->slots = new_slots;
+	}
+}
+
+static size_t str_hash_table_slot_size(StrHashTable *t) {
+	return sizeof(StrHashTableSlot) + ((t->data_size + sizeof(uint64_t) - 1) / sizeof(uint64_t)) * sizeof(uint64_t);
+}
+
+static StrHashTableSlot *str_hash_table_insert_(StrHashTable *t, const char *str, size_t len) {
+	size_t slots_cap;
+	uint64_t hash;
+	StrHashTableSlot **slot;
+	str_hash_table_grow(t);
+	slots_cap = arr_len(t->slots);
+	hash = str_hash(str, len);
+	slot = str_hash_table_slot_get(t->slots, str, len, hash % slots_cap);
+	if (!*slot) {
+		*slot = calloc(1, str_hash_table_slot_size(t));
+		char *s = (*slot)->str = calloc(1, len + 1);
+		memcpy(s, str, len);
+		(*slot)->len = len;
+		++t->nentries;
+	}
+	return *slot;
+}
+
+// does NOT check for a null byte.
+static void *str_hash_table_insert_with_len(StrHashTable *t, const char *str, size_t len) {
+	return str_hash_table_insert_(t, str, len)->data;
+}
+
+static void *str_hash_table_insert(StrHashTable *t, const char *str) {
+	return str_hash_table_insert_(t, str, strlen(str))->data;
+}
+
+static void str_hash_table_clear(StrHashTable *t) {
+	arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) {
+		if (*slotp) {
+			free((*slotp)->str);
+		}
+		free(*slotp);
+	}
+	arr_clear(t->slots);
+	t->nentries = 0;
+}
+
+static StrHashTableSlot *str_hash_table_get_(StrHashTable *t, const char *str, size_t len) {
+	size_t nslots = arr_len(t->slots), slot_index;
+	if (!nslots) return NULL;
+	slot_index = str_hash(str, len) % arr_len(t->slots);
+	return *str_hash_table_slot_get(t->slots, str, len, slot_index);
+}
+
+static void *str_hash_table_get_with_len(StrHashTable *t, const char *str, size_t len) {
+	StrHashTableSlot *slot = str_hash_table_get_(t, str, len);
+	if (!slot) return NULL;
+	return slot->data;
+}
+
+static void *str_hash_table_get(StrHashTable *t, const char *str) {
+	return str_hash_table_get_with_len(t, str, strlen(str));
+}
+
+#endif
diff --git a/ide-definitions.c b/ide-definitions.c
index 6ea0547..cd7f3f2 100644
--- a/ide-definitions.c
+++ b/ide-definitions.c
@@ -105,7 +105,7 @@ static void definitions_selector_filter_entries(Ted *ted) {
 	arr_clear(sel->entries);
 
 	arr_foreach_ptr(defs->selector_all_definitions, SymbolInfo, info) {
-		if (!search_term || stristr(info->name, search_term)) {
+		if (!search_term || strstr_case_insensitive(info->name, search_term)) {
 			SelectorEntry *entry = arr_addp(sel->entries);
 			entry->name = info->name;
 			entry->color = info->color;
diff --git a/lsp.h b/lsp.h
index 15b517b..3948329 100644
--- a/lsp.h
+++ b/lsp.h
@@ -1,6 +1,9 @@
 #ifndef LSP_H_
 #define LSP_H_
 
+#include "base.h"
+#include "ds.h"
+
 typedef u32 LSPDocumentID;
 typedef u32 LSPID;
 typedef u32 LSPRequestID;
diff --git a/main.c b/main.c
index c4b995f..ec70abf 100644
--- a/main.c
+++ b/main.c
@@ -74,7 +74,7 @@ no_warn_end
 #include <pcre2.h>
 
 #if DEBUG
-extern unsigned char *stbi_load(char const *filename, int *x, int *y, int *comp, int req_comp);
+extern unsigned char *stbi_load(const char *filename, int *x, int *y, int *comp, int req_comp);
 #else
 #define STB_IMAGE_STATIC
 no_warn_start
@@ -82,7 +82,6 @@ no_warn_start
 no_warn_end
 #endif
 
-#include "ds.c"
 #include "util.c"
 
 #if _WIN32
@@ -102,33 +101,14 @@ no_warn_end
 #error "Unrecognized operating system."
 #endif
 
-static void die(char const *fmt, ...) {
-	char buf[256] = {0};
-	
-	va_list args;
-	va_start(args, fmt);
-	vsnprintf(buf, sizeof buf - 1, fmt, args);
-	va_end(args);
-	
-	// show a message box, and if that fails, print it
-	if (SDL_ShowSimpleMessageBox(SDL_MESSAGEBOX_ERROR, "Error", buf, NULL) < 0) {
-		debug_println("%s\n", buf);
-	}
-	
-	exit(EXIT_FAILURE);
-}
-
 #include "io.c"
-
 #include "time.c"
 #include "ted.h"
 #include "gl.c"
 #include "text.c"
-
 #include "string32.c"
 #include "colors.c"
 #include "syntax.c"
-bool tag_goto(Ted *ted, char const *tag);
 #include "buffer.c"
 #include "ted.c"
 #include "ui.c"
diff --git a/menu.c b/menu.c
index 07801a6..2d55e0b 100644
--- a/menu.c
+++ b/menu.c
@@ -271,7 +271,7 @@ static void menu_update(Ted *ted) {
 			SelectorEntry *entry = entries;
 			for (Command c = 0; c < CMD_COUNT; ++c) {
 				char const *name = command_to_str(c);
-				if (c != CMD_UNKNOWN && *name && stristr(name, search_term)) {
+				if (c != CMD_UNKNOWN && *name && strstr_case_insensitive(name, search_term)) {
 					entry->name = name;
 					entry->color = colors[COLOR_TEXT];
 					++entry;
diff --git a/ted.c b/ted.c
index 611dae2..4580f9a 100644
--- a/ted.c
+++ b/ted.c
@@ -2,6 +2,22 @@
 #define ted_seterr(ted, ...) \
 	snprintf((ted)->error, sizeof (ted)->error - 1, __VA_ARGS__)
 
+static void die(char const *fmt, ...) {
+	char buf[256] = {0};
+	
+	va_list args;
+	va_start(args, fmt);
+	vsnprintf(buf, sizeof buf - 1, fmt, args);
+	va_end(args);
+	
+	// show a message box, and if that fails, print it
+	if (SDL_ShowSimpleMessageBox(SDL_MESSAGEBOX_ERROR, "Error", buf, NULL) < 0) {
+		debug_println("%s\n", buf);
+	}
+	
+	exit(EXIT_FAILURE);
+}
+
 void ted_seterr_to_buferr(Ted *ted, TextBuffer *buffer) {
 	size_t size = sizeof ted->error;
 	if (sizeof buffer->error < size) size = sizeof buffer->error;
diff --git a/ted.h b/ted.h
index 29f2a15..f80ae45 100644
--- a/ted.h
+++ b/ted.h
@@ -1,6 +1,8 @@
 #ifndef TED_H_
 #define TED_H_
 
+#include "util.h"
+#include "ds.h"
 #include "lsp.h"
 #include "base.h"
 #include "text.h"
@@ -585,8 +587,9 @@ typedef struct Ted {
 	char error[512];
 	char error_shown[512]; // error display in box on screen
 } Ted;
+
 char *buffer_contents_utf8_alloc(TextBuffer *buffer);
-Command command_from_str(char const *str);
+Command command_from_str(const char *str);
 const char *command_to_str(Command command);
 // Returns string representation of command
 const char *command_to_str(Command c);
diff --git a/ui.c b/ui.c
index ebaa0ef..a187d26 100644
--- a/ui.c
+++ b/ui.c
@@ -447,7 +447,7 @@ static char *file_selector_update(Ted *ted, FileSelector *fs) {
 		bool increment = true;
 		for (u32 i = 0; i < nfiles; i += increment, increment = true) {
 			// remove if the file name does not contain the search term,
-			bool remove = search_term && *search_term && !stristr(files[i]->name, search_term);
+			bool remove = search_term && *search_term && !strstr_case_insensitive(files[i]->name, search_term);
 			// or if this is just the current directory
 			remove |= streq(files[i]->name, ".");
 			if (remove) {
diff --git a/util.c b/util.c
index 49e2a20..3da5f30 100644
--- a/util.c
+++ b/util.c
@@ -8,48 +8,52 @@
 #endif
 
 #include "base.h"
+#include "util.h"
 
-// Is this character a "word" character?
-static bool is_word(char32_t c) {
+// on 16-bit systems, this is 16383. on 32/64-bit systems, this is 1073741823
+// it is unusual to have a string that long.
+#define STRLEN_SAFE_MAX (UINT_MAX >> 2)
+
+bool is_word(char32_t c) {
 	return c > WCHAR_MAX || c == '_' || iswalnum((wint_t)c);
 }
 
-static bool is_digit(char32_t c) {
+bool is_digit(char32_t c) {
 	return c < WCHAR_MAX && iswdigit((wint_t)c);
 }
 
-static bool is_space(char32_t c) {
+bool is_space(char32_t c) {
 	return c < WCHAR_MAX && iswspace((wint_t)c);
 }
 
-static bool is_a_tty(FILE *out) {
-	return
-	#if __unix__
-		isatty(fileno(out))
+bool is_a_tty(FILE *out) {
+	#if _WIN32
+	int fd = _fileno(out);
+	return fd >= 0 && _isatty(fd);
 	#else
-		false
+	int fd = fileno(out);
+	return fd >= 0 && isatty(fd);
 	#endif
-		;
 }
 
-static const char *term_italics(FILE *out) {
+const char *term_italics(FILE *out) {
 	return is_a_tty(out) ? "\x1b[3m" : "";
 }
 
-static const char *term_bold(FILE *out) {
+const char *term_bold(FILE *out) {
 	return is_a_tty(out) ? "\x1b[1m" : "";
 }
 
-static const char *term_yellow(FILE *out) {
+const char *term_yellow(FILE *out) {
 	return is_a_tty(out) ? "\x1b[93m" : "";
 }
 
-static const char *term_clear(FILE *out) {
+const char *term_clear(FILE *out) {
 	return is_a_tty(out) ? "\x1b[0m" : "";
 }
 
 
-static u8 util_popcount(u64 x) {
+u8 util_popcount(u64 x) {
 #ifdef __GNUC__
 	return (u8)__builtin_popcountll(x);
 #else
@@ -62,7 +66,7 @@ static u8 util_popcount(u64 x) {
 #endif
 }
 
-static u8 util_count_leading_zeroes32(u32 x) {
+u8 util_count_leading_zeroes32(u32 x) {
 	if (x == 0) return 32; // GCC's __builtin_clz is undefined for x = 0
 #if __GNUC__ && UINT_MAX == 4294967295
 	return (u8)__builtin_clz(x);
@@ -80,12 +84,12 @@ static u8 util_count_leading_zeroes32(u32 x) {
 #endif
 }
 
-static bool util_is_power_of_2(u64 x) {
+bool util_is_power_of_2(u64 x) {
 	return util_popcount(x) == 1;
 }
 
 // for finding a character in a char32 string
-static char32_t *util_mem32chr(char32_t *s, char32_t c, size_t n) {
+char32_t *util_mem32chr(char32_t *s, char32_t c, size_t n) {
 	for (size_t i = 0; i < n; ++i) {
 		if (s[i] == c) {
 			return &s[i];
@@ -94,7 +98,7 @@ static char32_t *util_mem32chr(char32_t *s, char32_t c, size_t n) {
 	return NULL;
 }
 
-static char32_t const *util_mem32chr_const(char32_t const *s, char32_t c, size_t n) {
+const char32_t *util_mem32chr_const(const char32_t *s, char32_t c, size_t n) {
 	for (size_t i = 0; i < n; ++i) {
 		if (s[i] == c) {
 			return &s[i];
@@ -103,23 +107,23 @@ static char32_t const *util_mem32chr_const(char32_t const *s, char32_t c, size_t
 	return NULL;
 }
 
-static bool str_has_prefix(char const *str, char const *prefix) {
+bool str_has_prefix(const char *str, const char *prefix) {
 	return strncmp(str, prefix, strlen(prefix)) == 0;
 }
 
 // e.g. "/usr/share/bla" has the path prefix "/usr/share" but not "/usr/sha"
-static bool str_has_path_prefix(const char *path, const char *prefix) {
+bool str_has_path_prefix(const char *path, const char *prefix) {
 	size_t prefix_len = strlen(prefix);
 	if (strncmp(path, prefix, prefix_len) != 0)
 		return false;
 	return path[prefix_len] == '\0' || strchr(ALL_PATH_SEPARATORS, path[prefix_len]);
 }
 
-static bool streq(char const *a, char const *b) {
+bool streq(const char *a, const char *b) {
 	return strcmp(a, b) == 0;
 }
 
-static size_t strn_len(const char *src, size_t n) {
+size_t strn_len(const char *src, size_t n) {
 	const char *p = src;
 	// in C99 and C++11/14, calling memchr with a size larger than
 	// the size of the object is undefined behaviour.
@@ -131,7 +135,7 @@ static size_t strn_len(const char *src, size_t n) {
 }
 
 // duplicates at most n characters from src
-static char *strn_dup(char const *src, size_t n) {
+char *strn_dup(const char *src, size_t n) {
 	size_t len = strn_len(src, n);
 	if (n > len)
 		n = len;
@@ -144,26 +148,12 @@ static char *strn_dup(char const *src, size_t n) {
 }
 
 // duplicates a null-terminated string. the returned string should be passed to free()
-static char *str_dup(char const *src) {
+char *str_dup(const char *src) {
 	return strn_dup(src, SIZE_MAX);
 }
 
-// like snprintf, but not screwed up on windows
-#define str_printf(str, size, ...) (str)[(size) - 1] = '\0', snprintf((str), (size) - 1, __VA_ARGS__)
-// like snprintf, but the size is taken to be the length of the array str.
-//                              first, check that str is actually an array
-#define strbuf_printf(str, ...) assert(sizeof str != 4 && sizeof str != 8), \
-	str_printf(str, sizeof str, __VA_ARGS__)
-#define str_catf(str, size, ...) str_printf((str) + strlen(str), (size) - strlen(str), __VA_ARGS__)
-#define strbuf_catf(str, ...) assert(sizeof str != 4 && sizeof str != 8), \
-	str_catf(str, sizeof str, __VA_ARGS__)
-
-// on 16-bit systems, this is 16383. on 32/64-bit systems, this is 1073741823
-// it is unusual to have a string that long.
-#define STRLEN_SAFE_MAX (UINT_MAX >> 2)
-
 // safer version of strncat. dst_sz includes a null terminator.
-static void strn_cat(char *dst, size_t dst_sz, char const *src, size_t src_len) {
+void strn_cat(char *dst, size_t dst_sz, const char *src, size_t src_len) {
 	size_t dst_len = strlen(dst);
 
 	// make sure dst_len + src_len + 1 doesn't overflow
@@ -190,12 +180,12 @@ static void strn_cat(char *dst, size_t dst_sz, char const *src, size_t src_len)
 }
 
 // safer version of strcat. dst_sz includes a null terminator.
-static void str_cat(char *dst, size_t dst_sz, char const *src) {
+void str_cat(char *dst, size_t dst_sz, const char *src) {
 	strn_cat(dst, dst_sz, src, strlen(src));
 }
 
 // safer version of strncpy. dst_sz includes a null terminator.
-static void strn_cpy(char *dst, size_t dst_sz, char const *src, size_t src_len) {
+void strn_cpy(char *dst, size_t dst_sz, const char *src, size_t src_len) {
 	size_t n = src_len; // number of bytes to copy
 	for (size_t i = 0; i < n; ++i) {
 		if (src[i] == '\0') {
@@ -216,14 +206,10 @@ static void strn_cpy(char *dst, size_t dst_sz, char const *src, size_t src_len)
 }
 
 // safer version of strcpy. dst_sz includes a null terminator.
-static void str_cpy(char *dst, size_t dst_sz, char const *src) {
+void str_cpy(char *dst, size_t dst_sz, const char *src) {
 	strn_cpy(dst, dst_sz, src, SIZE_MAX);
 }
 
-#define strbuf_cpy(dst, src) str_cpy(dst, sizeof dst, src)
-#define strbuf_cat(dst, src) str_cat(dst, sizeof dst, src)
-
-
 char *a_sprintf(PRINTF_FORMAT_STRING const char *fmt, ...) ATTRIBUTE_PRINTF(1, 2);
 char *a_sprintf(const char *fmt, ...) {
 	// idk if you can always just pass NULL to vsnprintf
@@ -244,7 +230,7 @@ char *a_sprintf(const char *fmt, ...) {
 
 
 // advances str to the start of the next UTF8 character
-static void utf8_next_char_const(char const **str) {
+static void utf8_next_char_const(const char **str) {
 	if (**str) {
 		do {
 			++*str;
@@ -252,21 +238,16 @@ static void utf8_next_char_const(char const **str) {
 	}
 }
 
-/* 
-returns the first instance of needle in haystack, where both are UTF-8 strings, ignoring the case of the characters,
-or NULL if the haystack does not contain needle
-WARNING: O(strlen(haystack) * strlen(needle))
-*/
-static char *stristr(char const *haystack, char const *needle) {
+char *strstr_case_insensitive(const char *haystack, const char *needle) {
 	size_t needle_bytes = strlen(needle), haystack_bytes = strlen(haystack);
 
 	if (needle_bytes > haystack_bytes) return NULL;
 	
-	char const *haystack_end = haystack + haystack_bytes;
-	char const *needle_end = needle + needle_bytes;
+	const char *haystack_end = haystack + haystack_bytes;
+	const char *needle_end = needle + needle_bytes;
 
-	for (char const *haystack_start = haystack; haystack_start + needle_bytes <= haystack_end; utf8_next_char_const(&haystack_start)) {
-		char const *p = haystack_start, *q = needle;
+	for (const char *haystack_start = haystack; haystack_start + needle_bytes <= haystack_end; utf8_next_char_const(&haystack_start)) {
+		const char *p = haystack_start, *q = needle;
 		bool match = true;
 
 		// check if p matches q
@@ -288,27 +269,14 @@ static char *stristr(char const *haystack, char const *needle) {
 	return NULL;
 }
 
-static void print_bytes(u8 *bytes, size_t n) {
-	u8 *b, *end;
+void print_bytes(const u8 *bytes, size_t n) {
+	const u8 *b, *end;
 	for (b = bytes, end = bytes + n; b != end; ++b)
-		printf("%x ", *b);
+		printf("%02x ", *b);
 	printf("\n");
 }
 
-/*
-does this predicate hold for all the characters of s. predicate is int (*)(int) instead
-of bool (*)(char) so that you can pass isprint, etc. to it.
-*/
-static bool str_satisfies(char const *s, int (*predicate)(int)) {
-	char const *p;
-	for (p = s; *p; ++p)
-		if (!predicate(*p))
-			return false;
-	return true;
-}
-
-
-static int strcmp_case_insensitive(char const *a, char const *b) {
+int strcmp_case_insensitive(const char *a, const char *b) {
 #if _WIN32
 	return _stricmp(a, b);
 #else
@@ -316,25 +284,27 @@ static int strcmp_case_insensitive(char const *a, char const *b) {
 #endif
 }
 
-// function to be passed into qsort for case insensitive sorting
-static int str_qsort_case_insensitive_cmp(const void *av, const void *bv) {
-	char const *const *a = av, *const *b = bv;
+int str_qsort_case_insensitive_cmp(const void *av, const void *bv) {
+	const char *const *a = av, *const *b = bv;
 	return strcmp_case_insensitive(*a, *b);
 }
 
-// imo windows has the argument order right here
 #if _WIN32
-#define qsort_with_context qsort_s
+void qsort_with_context(void *base, size_t nmemb, size_t size,
+	int (*compar)(void *, const void *, const void *),
+	void *arg) {
+	qsort_s(base, nmemb, size, compar, arg);
+}
 #else
 typedef struct {
 	int (*compar)(void *, const void *, const void *);
 	void *context;
 } QSortWithContext;
-static int qsort_with_context_cmp(const void *a, const void *b, void *context) {
+int qsort_with_context_cmp(const void *a, const void *b, void *context) {
 	QSortWithContext *c = context;
 	return c->compar(c->context, a, b);
 }
-static void qsort_with_context(void *base, size_t nmemb, size_t size,
+void qsort_with_context(void *base, size_t nmemb, size_t size,
 	int (*compar)(void *, const void *, const void *),
 	void *arg) {
 	QSortWithContext ctx = {
@@ -345,17 +315,15 @@ static void qsort_with_context(void *base, size_t nmemb, size_t size,
 }
 #endif
 
-// the actual file name part of the path; get rid of the containing directory.
-// NOTE: the returned string is part of path, so you don't need to free it or anything.
-static char const *path_filename(char const *path) {
-	char const *last_path_sep = strrchr(path, PATH_SEPARATOR);
+const char *path_filename(const char *path) {
+	const char *last_path_sep = strrchr(path, PATH_SEPARATOR);
 	if (last_path_sep)
 		return last_path_sep + 1;
 	// (a relative path with no path separators)
 	return path;
 }
 
-static bool path_is_absolute(char const *path) {
+bool path_is_absolute(const char *path) {
 	return path[0] == PATH_SEPARATOR
 	#if _WIN32
 		|| path[1] == ':'
@@ -363,8 +331,7 @@ static bool path_is_absolute(char const *path) {
 		;
 }
 
-// assuming `dir` is an absolute path, returns the absolute path of `relpath`, relative to `dir`.
-static void path_full(char const *dir, char const *relpath, char *abspath, size_t abspath_size) {
+void path_full(const char *dir, const char *relpath, char *abspath, size_t abspath_size) {
 	assert(abspath_size);
 	assert(dir[0]);
 	abspath[0] = '\0';
@@ -386,7 +353,7 @@ static void path_full(char const *dir, char const *relpath, char *abspath, size_
 	
 	while (*relpath) {
 		size_t component_len = strcspn(relpath, ALL_PATH_SEPARATORS);
-		char const *component_end = relpath + component_len;
+		const char *component_end = relpath + component_len;
 
 		size_t len = strlen(abspath);
 		if (component_len == 1 && relpath[0] == '.') {
@@ -411,18 +378,25 @@ static void path_full(char const *dir, char const *relpath, char *abspath, size_
 	}
 }
 
-// returns true if the paths are the same.
-// handles the fact that paths are case insensitive on windows.
-// treats links as different from the files they point to.
-static bool paths_eq(char const *path1, char const *path2) {
-#if _WIN32
-	return _stricmp(path1, path2) == 0;
-#else
+bool paths_eq(const char *path1, const char *path2) {
+#if __unix__
 	return streq(path1, path2);
+#else
+	char fixed_path1[8192];
+	char fixed_path2[8192];
+	strbuf_cpy(fixed_path1, path1);
+	strbuf_cpy(fixed_path2, path2);
+	for (size_t i = 0; fixed_path1[i]; ++i)
+		if (fixed_path1[i] == '/')
+			fixed_path1[i] = '\\';
+	for (size_t i = 0; fixed_path2[i]; ++i)
+		if (fixed_path2[i] == '/')
+			fixed_path2[i] = '\\';
+	return _stricmp(fixed_path1, fixed_path2) == 0;
 #endif
 }
 
-static void change_directory(char const *path) {
+void change_directory(const char *path) {
 #if _WIN32
 	_chdir(path);
 #else
@@ -430,8 +404,7 @@ static void change_directory(char const *path) {
 #endif
 }
 
-// returns true on success
-static bool copy_file(char const *src, char const *dst) {
+bool copy_file(const char *src, const char *dst) {
 	bool success = false;
 	FILE *src_file = fopen(src, "rb");
 	if (src_file) {
@@ -452,125 +425,3 @@ static bool copy_file(char const *src, char const *dst) {
 }
 
 
-static uint64_t str_hash(char const *str, size_t len) {
-	uint64_t hash = 0;
-	char const *p = str, *end = str + len;
-	for (; p < end; ++p) {
-		hash = ((hash * 1664737020647550361 + 123843) << 8) + 2918635993572506131*(uint64_t)*p;
-	}
-	return hash;
-}
-
-typedef struct {
-	char *str;
-	size_t len;
-	uint64_t data[];
-} StrHashTableSlot;
-
-typedef StrHashTableSlot *StrHashTableSlotPtr;
-
-typedef struct {
-	StrHashTableSlot **slots;
-	size_t data_size;
-	size_t nentries; /* # of filled slots */
-} StrHashTable;
-
-static inline void str_hash_table_create(StrHashTable *t, size_t data_size) {
-	t->slots = NULL;
-	t->data_size = data_size;
-	t->nentries = 0;
-}
-
-static StrHashTableSlot **str_hash_table_slot_get(StrHashTableSlot **slots, char const *s, size_t s_len, size_t i) {
-	StrHashTableSlot **slot;
-	size_t slots_cap = arr_len(slots);
-	while (1) {
-		assert(i < slots_cap);
-		slot = &slots[i];
-		if (!*slot) break;
-		if (s && (*slot)->str &&
-			s_len == (*slot)->len && memcmp(s, (*slot)->str, s_len) == 0)
-			break;
-		i = (i+1) % slots_cap;
-	}
-	return slot;
-}
-
-static void str_hash_table_grow(StrHashTable *t) {
-	size_t slots_cap = arr_len(t->slots);
-	if (slots_cap <= 2 * t->nentries) {
-		StrHashTableSlot **new_slots = NULL;
-		size_t new_slots_cap = slots_cap * 2 + 10;
-		arr_set_len(new_slots, new_slots_cap);
-		memset(new_slots, 0, new_slots_cap * sizeof *new_slots);
-		arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) {
-			StrHashTableSlot *slot = *slotp;
-			if (slot) {
-				uint64_t new_hash = str_hash(slot->str, slot->len);
-				StrHashTableSlot **new_slot = str_hash_table_slot_get(new_slots, slot->str, slot->len, new_hash % new_slots_cap);
-				*new_slot = slot;
-			}
-		}
-		arr_clear(t->slots);
-		t->slots = new_slots;
-	}
-}
-
-static inline size_t str_hash_table_slot_size(StrHashTable *t) {
-	return sizeof(StrHashTableSlot) + ((t->data_size + sizeof(uint64_t) - 1) / sizeof(uint64_t)) * sizeof(uint64_t);
-}
-
-static StrHashTableSlot *str_hash_table_insert_(StrHashTable *t, char const *str, size_t len) {
-	size_t slots_cap;
-	uint64_t hash;
-	StrHashTableSlot **slot;
-	str_hash_table_grow(t);
-	slots_cap = arr_len(t->slots);
-	hash = str_hash(str, len);
-	slot = str_hash_table_slot_get(t->slots, str, len, hash % slots_cap);
-	if (!*slot) {
-		*slot = calloc(1, str_hash_table_slot_size(t));
-		char *s = (*slot)->str = calloc(1, len + 1);
-		memcpy(s, str, len);
-		(*slot)->len = len;
-		++t->nentries;
-	}
-	return *slot;
-}
-
-// does NOT check for a null byte.
-static inline void *str_hash_table_insert_with_len(StrHashTable *t, char const *str, size_t len) {
-	return str_hash_table_insert_(t, str, len)->data;
-}
-
-static inline void *str_hash_table_insert(StrHashTable *t, char const *str) {
-	return str_hash_table_insert_(t, str, strlen(str))->data;
-}
-
-static void str_hash_table_clear(StrHashTable *t) {
-	arr_foreach_ptr(t->slots, StrHashTableSlotPtr, slotp) {
-		if (*slotp) {
-			free((*slotp)->str);
-		}
-		free(*slotp);
-	}
-	arr_clear(t->slots);
-	t->nentries = 0;
-}
-
-static StrHashTableSlot *str_hash_table_get_(StrHashTable *t, char const *str, size_t len) {
-	size_t nslots = arr_len(t->slots), slot_index;
-	if (!nslots) return NULL;
-	slot_index = str_hash(str, len) % arr_len(t->slots);
-	return *str_hash_table_slot_get(t->slots, str, len, slot_index);
-}
-
-static inline void *str_hash_table_get_with_len(StrHashTable *t, char const *str, size_t len) {
-	StrHashTableSlot *slot = str_hash_table_get_(t, str, len);
-	if (!slot) return NULL;
-	return slot->data;
-}
-
-static inline void *str_hash_table_get(StrHashTable *t, char const *str) {
-	return str_hash_table_get_with_len(t, str, strlen(str));
-}
diff --git a/util.h b/util.h
new file mode 100644
index 0000000..8d5aeef
--- /dev/null
+++ b/util.h
@@ -0,0 +1,92 @@
+#ifndef UTIL_H_
+#define UTIL_H_
+
+
+// like snprintf, but not screwed up on windows
+#define str_printf(str, size, ...) (str)[(size) - 1] = '\0', snprintf((str), (size) - 1, __VA_ARGS__)
+// like snprintf, but the size is taken to be the length of the array str.
+//                              first, check that str is actually an array
+#define strbuf_printf(str, ...) assert(sizeof str != 4 && sizeof str != 8), \
+	str_printf(str, sizeof str, __VA_ARGS__)
+#define str_catf(str, size, ...) str_printf((str) + strlen(str), (size) - strlen(str), __VA_ARGS__)
+#define strbuf_catf(str, ...) assert(sizeof str != 4 && sizeof str != 8), \
+	str_catf(str, sizeof str, __VA_ARGS__)
+#define strbuf_cpy(dst, src) str_cpy(dst, sizeof dst, src)
+#define strbuf_cat(dst, src) str_cat(dst, sizeof dst, src)
+
+// ctype functions for 32-bit chars.
+bool is_word(char32_t c);
+bool is_digit(char32_t c);
+bool is_space(char32_t c);
+bool is_a_tty(FILE *out);
+// terminal colors. if `out` is a TTY, these will return the appropriate escape sequences.
+// if `out` is not a TTY, these will return "".
+const char *term_italics(FILE *out);
+const char *term_bold(FILE *out);
+const char *term_yellow(FILE *out);
+const char *term_clear(FILE *out);
+// number of 1 bits in x.
+u8 util_popcount(u64 x);
+// count leading zeroes. if x == 0, this always returns 32 (not undefined behavior).
+u8 util_count_leading_zeroes32(u32 x);
+// is x a power of 2?
+bool util_is_power_of_2(u64 x);
+// like memchr, but 32-bit.
+char32_t *util_mem32chr(char32_t *s, char32_t c, size_t n);
+// like memchr, but 32-bit, and constant.
+const char32_t *util_mem32chr_const(const char32_t *s, char32_t c, size_t n);
+// does `str` have this prefix?
+bool str_has_prefix(const char *str, const char *prefix);
+// like str_has_prefix, but for paths. "ab/cd" is a path-prefix of "ab/cd/ef", but not "ab/cde".
+bool str_has_path_prefix(const char *path, const char *prefix);
+// are these two strings equal?
+bool streq(const char *a, const char *b);
+// equivalent to the POSIX function strnlen
+size_t strn_len(const char *src, size_t n);
+// equivalent to the POSIX function strndup
+char *strn_dup(const char *src, size_t n);
+// equivalent to the POSIX function strdup
+char *str_dup(const char *src);
+// a safer version of strncat. `dst_sz` includes a null-terminator.
+void strn_cat(char *dst, size_t dst_sz, const char *src, size_t src_len);
+// a safer version of strcat. `dst_sz` includes a null-terminator.
+void str_cat(char *dst, size_t dst_sz, const char *src);
+// a safer version of strncpy. `dst_sz` includes a null-terminator.
+void strn_cpy(char *dst, size_t dst_sz, const char *src, size_t src_len);
+// a safer version of strcpy. `dst_sz` includes a null-terminator.
+void str_cpy(char *dst, size_t dst_sz, const char *src);
+// equivalent to GNU function asprintf (like sprintf, but allocates the string with malloc).
+char *a_sprintf(const char *fmt, ...);
+// print some bytes. useful for debugging.
+void print_bytes(const u8 *bytes, size_t n);
+// like strstr, but case-insensitive
+// currently this uses a "naive" string searching algorithm so
+// it may be O(len(haystack) * len(needle)) for certain strings.
+char *strstr_case_insensitive(const char *haystack, const char *needle);
+// like strcmp, but case-insensitive
+int strcmp_case_insensitive(const char *a, const char *b);
+// function to be passed into qsort for case insensitive sorting
+int str_qsort_case_insensitive_cmp(const void *av, const void *bv);
+// the actual file name part of the path; get rid of the containing directory.
+// NOTE: the returned string is part of path, so you don't need to free it or anything.
+const char *path_filename(const char *path);
+// is this an absolute path?
+bool path_is_absolute(const char *path);
+// assuming `dir` is an absolute path, returns the absolute path of `relpath`, relative to `dir`.
+void path_full(const char *dir, const char *relpath, char *abspath, size_t abspath_size);
+// returns true if the paths are the same.
+// handles the fact that paths are case insensitive on windows and that \ is the same as /.
+// a symbolic link is considered different from the file it points to, as are two hard
+// links to the same file.
+bool paths_eq(const char *path1, const char *path2);
+// equivalent to POSIX function chdir.
+void change_directory(const char *path);
+// copy file from src to dest
+// returns true on success
+bool copy_file(const char *src, const char *dst);
+// like qsort, but with a context object which gets passed to the comparison function
+void qsort_with_context(void *base, size_t nmemb, size_t size,
+	int (*compar)(void *, const void *, const void *),
+	void *arg);
+
+#endif // UTIL_H_