From 8308d6fc53ee339a0b5cac4b9b837179c61efbaa Mon Sep 17 00:00:00 2001
From: pommicket <pommicket@gmail.com>
Date: Sun, 1 Jan 2023 12:05:48 -0500
Subject: more reorganizing

---
 ds.c              | 346 -----------------------------------------
 ds.h              | 458 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ide-definitions.c |   2 +-
 lsp.h             |   3 +
 main.c            |  22 +--
 menu.c            |   2 +-
 ted.c             |  16 ++
 ted.h             |   5 +-
 ui.c              |   2 +-
 util.c            | 295 +++++++++--------------------------
 util.h            |  92 +++++++++++
 11 files changed, 650 insertions(+), 593 deletions(-)
 delete mode 100644 ds.c
 create mode 100644 ds.h
 create mode 100644 util.h

diff --git a/ds.c b/ds.c
deleted file mode 100644
index b599f36..0000000
--- a/ds.c
+++ /dev/null
@@ -1,346 +0,0 @@
-/* VARIOUS DATA STRUCTURES
-- dynamic array
-- string builder
-- string hash table
-*/
-
-
-// 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.)
-
-#include <stddef.h>
-typedef union {
-	long num;
-	void *ptr;
-	void (*fnptr)(void);
-#ifdef ARR_LONG_DOUBLE
-	long
-#endif
-	double flt;
-} ArrMaxAlign;
-#if __STDC_VERSION__ < 199901L && !defined inline
-#define inline
-#endif
-
-
-typedef struct {
-	u32 len;
-	u32 cap;
-	ArrMaxAlign data[];
-} ArrHeader;
-
-// watch out! do not call this function if arr is NULL.
-static inline ArrHeader *arr_hdr_(void *arr) {
-	return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
-}
-
-static inline u32 arr_len(const void *arr) {
-	return arr ? arr_hdr_((void*)arr)->len : 0;
-}
-
-static inline u32 arr_cap(void *arr) {
-	return arr ? arr_hdr_(arr)->cap : 0;
-}
-
-static inline unsigned arr_lenu(void *arr) {
-	return (unsigned)arr_len(arr);
-}
-
-// grow array to fit one more member
-static void *arr_grow1_(void *arr, size_t member_size) {
-	if (arr) {
-		ArrHeader *hdr = arr_hdr_(arr);
-		if (hdr->len >= hdr->cap) {
-			u32 new_capacity = hdr->cap * 2;
-			ArrHeader *old_hdr = hdr;
-			hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size);
-			if (hdr) {
-				hdr->cap = new_capacity;
-			} else {
-				free(old_hdr);
-				return NULL;
-			}
-		}
-		return hdr->data;
-	} else {
-		// create a new array
-		u32 initial_capacity = 2; // allocate enough space for two members
-		ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size);
-		if (ret) {
-			ret->cap = initial_capacity;
-			return ret->data;
-		} else {
-			return NULL;
-		}
-	}
-}
-
-static inline void *arr_add_ptr_(void **arr, size_t member_size) {
-	u8 *ret;
-	*arr = arr_grow1_(*arr, member_size);
-	if (*arr) {
-		ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++);
-		memset(ret, 0, member_size);
-	} else {
-		ret = NULL;
-	}
-	return ret;
-}
-
-static void arr_reserve_(void **arr, size_t member_size, size_t n) {
-	if (n >= U32_MAX-1) { 
-		// too big; free arr.
-		if (*arr) free(arr_hdr_(*arr));
-		*arr = NULL;
-	}
-	
-	if (n == 0) return;
-
-	if (!*arr) {
-		// create a new array with capacity n+1
-		// why n+1? i dont know i wrote this a while ago
-		ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size);
-		if (hdr) {
-			hdr->cap = (u32)n+1;
-			*arr = hdr->data;
-		}
-	} else {
-		// increase capacity of array
-		ArrHeader *hdr = arr_hdr_(*arr);
-		u32 curr_cap = hdr->cap;
-		if (n > curr_cap) {
-			ArrHeader *old_hdr = hdr;
-			while (n > curr_cap) {
-				if (curr_cap < U32_MAX/2)
-					curr_cap *= 2;
-				else
-					curr_cap = U32_MAX;
-			}
-			hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size);
-			if (hdr) {
-				hdr->cap = curr_cap;
-			} else {
-				// growing failed
-				free(old_hdr);
-				*arr = NULL;
-				return;
-			}
-		}
-		*arr = hdr->data;
-	}
-}
-
-static void arr_set_len_(void **arr, size_t member_size, size_t n) {
-	arr_reserve_(arr, member_size, n);
-	if (*arr) {
-		ArrHeader *hdr = arr_hdr_(*arr);
-		if (n > hdr->len) {
-			// zero new elements
-			memset((char *)hdr->data + hdr->len * member_size, 0, (n - hdr->len) * member_size);
-		}
-		hdr->len = (u32)n;
-	}
-}
-
-static void *arr_remove_(void *arr, size_t member_size, size_t index) {
-	ArrHeader *hdr = arr_hdr_(arr);
-	assert(index < hdr->len);
-	memmove((char *)arr + index * member_size, (char *)arr + (index+1) * member_size, (hdr->len - (index+1)) * member_size);
-	if (--hdr->len == 0) {
-		free(hdr);
-		return NULL;
-	} else {
-		return arr;
-	}
-}
-
-#ifdef __cplusplus
-#define arr_cast_typeof(a) (decltype(a))
-#elif defined __GNUC__
-#define arr_cast_typeof(a) (__typeof__(a))
-#else
-#define arr_cast_typeof(a)
-#endif
-
-#define arr__join2(a,b) a##b
-#define arr__join(a,b) arr__join2(a,b) // macro used internally
-// if the array is not NULL, free it and set it to NULL
-#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0)
-// a nice alias
-#define arr_clear(a) arr_free(a)
-// add an item to the array - if allocation fails, the array will be freed and set to NULL.
-// (how this works: if we can successfully grow the array, increase the length and add the item.)
-#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0)
-// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed.
-// the added item will be zero-initialized.
-#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a))
-// set the length of `a` to `n`, increasing the capacity if necessary.
-// the newly-added elements are zero-initialized.
-#define arr_qsort(a, cmp) qsort((a), arr_len(a), sizeof *(a), (cmp))
-#define arr_remove_last(a) do { assert(a); if (--arr_hdr_(a)->len == 0) arr_free(a); } while (0)
-#define arr_remove(a, i) (void)((a) = arr_remove_((a), sizeof *(a), (i)))
-#define arr_insert(a, i, x) do { u32 _index = (i); (a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)); \
-	if (a) { memmove((a) + _index + 1, (a) + _index, (arr_len(a) - _index) * sizeof *(a));\
-	(a)[_index] = x; \
-	++arr_hdr_(a)->len; } } while (0)
-#define arr_pop_last(a) ((a)[--arr_hdr_(a)->len])
-#define arr_size_in_bytes(a) (arr_len(a) * sizeof *(a))
-#define arr_lastp(a) ((a) ? &(a)[arr_len(a)-1] : NULL)
-#define arr_foreach_ptr_end(a, type, var, end) type *end = (a) + arr_len(a); \
-	for (type *var = (a); var != end; ++var)
-// Iterate through each element of the array, setting var to a pointer to the element.
-// You can't use this like, e.g.:
-// if (something)
-//   arr_foreach_ptr(a, int, i);
-// You'll get an error. You will need to use braces because it expands to multiple statements.
-// (we need to name the end pointer something unique, which is why there's that arr__join thing
-// we can't just declare it inside the for loop, because type could be something like char *.)
-#define arr_foreach_ptr(a, type, var) arr_foreach_ptr_end(a, type, var, arr__join(_foreach_end,__LINE__))
-
-#define arr_reverse(a, type) do { \
-	u64 _i, _len = arr_len(a); \
-	for (_i = 0; 2*_i < _len; ++_i) { \
-		type *_x = &(a)[_i]; \
-		type *_y = &(a)[_len-1-_i]; \
-		type _tmp; \
-		_tmp = *_x; \
-		*_x = *_y; \
-		*_y = _tmp; \
-	} \
-	} while (0)
-
-// Ensure that enough space is allocated for n elements.
-#define arr_reserve(a, n) arr_reserve_((void **)&(a), sizeof *(a), (n)) 
-// 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;
-	u32 i;
-	assert(arr_len(arr) == 0);
-	for (i = 0; i < 10000; ++i) {
-		arr_add(arr, i*i);
-	}
-	assert(arr_len(arr) == 10000);
-	arr_remove_last(arr);
-	assert(arr_len(arr) == 9999);
-	for (i = 0; i < arr_len(arr); ++i)
-		assert(arr[i] == i*i);
-	while (arr_len(arr))
-		arr_remove_last(arr);
-	assert(arr_len(arr) == 0);
-}
-#endif
-
-typedef struct {
-	// dynamic array, including a null byte.
-	char *str;
-} StrBuilder;
-
-void str_builder_create(StrBuilder *builder) {
-	memset(builder, 0, sizeof *builder);
-	arr_add(builder->str, 0);
-}
-
-StrBuilder str_builder_new(void) {
-	StrBuilder ret = {0};
-	str_builder_create(&ret);
-	return ret;
-}
-
-void str_builder_free(StrBuilder *builder) {
-	arr_free(builder->str);
-}
-
-void str_builder_clear(StrBuilder *builder) {
-	str_builder_free(builder);
-	str_builder_create(builder);
-}
-
-void str_builder_append(StrBuilder *builder, const char *s) {
-	assert(builder->str);
-	
-	size_t s_len = strlen(s);
-	size_t prev_size = arr_len(builder->str);
-	size_t prev_len = prev_size - 1; // null terminator
-	// note: this zeroes the newly created elements, so we have a new null terminator
-	arr_set_len(builder->str, prev_size + s_len);
-	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, ...) {
-	// idk if you can always just pass NULL to vsnprintf
-	va_list args;
-	char fakebuf[2] = {0};
-	va_start(args, fmt);
-	int ret = vsnprintf(fakebuf, 1, fmt, args);
-	va_end(args);
-	
-	if (ret < 0) return; // bad format or something
-	u32 n = (u32)ret;
-	
-	size_t prev_size = arr_len(builder->str);
-	size_t prev_len = prev_size - 1; // null terminator
-	arr_set_len(builder->str, prev_size + n);
-	va_start(args, fmt);
-	vsnprintf(builder->str + prev_len, n + 1, fmt, args);
-	va_end(args);
-}
-
-// append n null bytes.
-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) {
-	assert(builder->str);
-	return arr_len(builder->str) - 1;
-}
-
-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) {
-	if (new_len > str_builder_len(builder)) {
-		assert(0);
-		return;
-	}
-	arr_set_len(builder->str, new_len + 1);
-}
-
diff --git a/ds.h b/ds.h
new file mode 100644
index 0000000..a447e4c
--- /dev/null
+++ b/ds.h
@@ -0,0 +1,458 @@
+#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
+
+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;
+	void (*fnptr)(void);
+#ifdef ARR_LONG_DOUBLE
+	long
+#endif
+	double flt;
+} ArrMaxAlign;
+#if __STDC_VERSION__ < 199901L && !defined inline
+#define inline
+#endif
+
+
+typedef struct {
+	u32 len;
+	u32 cap;
+	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 ArrHeader *arr_hdr_(void *arr) {
+	return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data));
+}
+
+static u32 arr_len(const void *arr) {
+	return arr ? arr_hdr_((void*)arr)->len : 0;
+}
+
+static u32 arr_cap(void *arr) {
+	return arr ? arr_hdr_(arr)->cap : 0;
+}
+
+static unsigned arr_lenu(void *arr) {
+	return (unsigned)arr_len(arr);
+}
+
+// grow array to fit one more member
+static void *arr_grow1_(void *arr, size_t member_size) {
+	if (arr) {
+		ArrHeader *hdr = arr_hdr_(arr);
+		if (hdr->len >= hdr->cap) {
+			u32 new_capacity = hdr->cap * 2;
+			ArrHeader *old_hdr = hdr;
+			hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size);
+			if (hdr) {
+				hdr->cap = new_capacity;
+			} else {
+				free(old_hdr);
+				return NULL;
+			}
+		}
+		return hdr->data;
+	} else {
+		// create a new array
+		u32 initial_capacity = 2; // allocate enough space for two members
+		ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size);
+		if (ret) {
+			ret->cap = initial_capacity;
+			return ret->data;
+		} else {
+			return NULL;
+		}
+	}
+}
+
+static void *arr_add_ptr_(void **arr, size_t member_size) {
+	u8 *ret;
+	*arr = arr_grow1_(*arr, member_size);
+	if (*arr) {
+		ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++);
+		memset(ret, 0, member_size);
+	} else {
+		ret = NULL;
+	}
+	return ret;
+}
+
+static void arr_reserve_(void **arr, size_t member_size, size_t n) {
+	if (n >= U32_MAX-1) { 
+		// too big; free arr.
+		if (*arr) free(arr_hdr_(*arr));
+		*arr = NULL;
+		return;
+	}
+	
+	if (n == 0) return;
+
+	if (!*arr) {
+		// create a new array with capacity n+1
+		// why n+1? i dont know i wrote this a while ago
+		ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size);
+		if (hdr) {
+			hdr->cap = (u32)n+1;
+			*arr = hdr->data;
+		}
+	} else {
+		// increase capacity of array
+		ArrHeader *hdr = arr_hdr_(*arr);
+		u32 curr_cap = hdr->cap;
+		if (n > curr_cap) {
+			ArrHeader *old_hdr = hdr;
+			while (n > curr_cap) {
+				if (curr_cap < U32_MAX/2)
+					curr_cap *= 2;
+				else
+					curr_cap = U32_MAX;
+			}
+			hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size);
+			if (hdr) {
+				hdr->cap = curr_cap;
+			} else {
+				// growing failed
+				free(old_hdr);
+				*arr = NULL;
+				return;
+			}
+		}
+		*arr = hdr->data;
+	}
+}
+
+static void arr_set_len_(void **arr, size_t member_size, size_t n) {
+	arr_reserve_(arr, member_size, n);
+	if (*arr) {
+		ArrHeader *hdr = arr_hdr_(*arr);
+		if (n > hdr->len) {
+			// zero new elements
+			memset((char *)hdr->data + hdr->len * member_size, 0, (n - hdr->len) * member_size);
+		}
+		hdr->len = (u32)n;
+	}
+}
+
+static void *arr_remove_(void *arr, size_t member_size, size_t index) {
+	ArrHeader *hdr = arr_hdr_(arr);
+	assert(index < hdr->len);
+	memmove((char *)arr + index * member_size, (char *)arr + (index+1) * member_size, (hdr->len - (index+1)) * member_size);
+	if (--hdr->len == 0) {
+		free(hdr);
+		return NULL;
+	} else {
+		return arr;
+	}
+}
+
+#ifdef __cplusplus
+#define arr_cast_typeof(a) (decltype(a))
+#elif defined __GNUC__
+#define arr_cast_typeof(a) (__typeof__(a))
+#else
+#define arr_cast_typeof(a)
+#endif
+
+#define arr__join2(a,b) a##b
+#define arr__join(a,b) arr__join2(a,b) // macro used internally
+// if the array is not NULL, free it and set it to NULL
+#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0)
+// a nice alias
+#define arr_clear(a) arr_free(a)
+// add an item to the array - if allocation fails, the array will be freed and set to NULL.
+// (how this works: if we can successfully grow the array, increase the length and add the item.)
+#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0)
+// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed.
+// the added item will be zero-initialized.
+#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a))
+// set the length of `a` to `n`, increasing the capacity if necessary.
+// the newly-added elements are zero-initialized.
+#define arr_qsort(a, cmp) qsort((a), arr_len(a), sizeof *(a), (cmp))
+#define arr_remove_last(a) do { assert(a); if (--arr_hdr_(a)->len == 0) arr_free(a); } while (0)
+#define arr_remove(a, i) (void)((a) = arr_remove_((a), sizeof *(a), (i)))
+#define arr_insert(a, i, x) do { u32 _index = (i); (a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)); \
+	if (a) { memmove((a) + _index + 1, (a) + _index, (arr_len(a) - _index) * sizeof *(a));\
+	(a)[_index] = x; \
+	++arr_hdr_(a)->len; } } while (0)
+#define arr_pop_last(a) ((a)[--arr_hdr_(a)->len])
+#define arr_size_in_bytes(a) (arr_len(a) * sizeof *(a))
+#define arr_lastp(a) ((a) ? &(a)[arr_len(a)-1] : NULL)
+#define arr_foreach_ptr_end(a, type, var, end) type *end = (a) + arr_len(a); \
+	for (type *var = (a); var != end; ++var)
+// Iterate through each element of the array, setting var to a pointer to the element.
+// You can't use this like, e.g.:
+// if (something)
+//   arr_foreach_ptr(a, int, i);
+// You'll get an error. You will need to use braces because it expands to multiple statements.
+// (we need to name the end pointer something unique, which is why there's that arr__join thing
+// we can't just declare it inside the for loop, because type could be something like char *.)
+#define arr_foreach_ptr(a, type, var) arr_foreach_ptr_end(a, type, var, arr__join(_foreach_end,__LINE__))
+
+#define arr_reverse(a, type) do { \
+	u64 _i, _len = arr_len(a); \
+	for (_i = 0; 2*_i < _len; ++_i) { \
+		type *_x = &(a)[_i]; \
+		type *_y = &(a)[_len-1-_i]; \
+		type _tmp; \
+		_tmp = *_x; \
+		*_x = *_y; \
+		*_y = _tmp; \
+	} \
+	} while (0)
+
+// Ensure that enough space is allocated for n elements.
+#define arr_reserve(a, n) arr_reserve_((void **)&(a), sizeof *(a), (n)) 
+// 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))
+
+#ifndef NDEBUG
+static void arr_test(void) {
+	u32 *arr = NULL;
+	u32 i;
+	assert(arr_len(arr) == 0);
+	for (i = 0; i < 10000; ++i) {
+		arr_add(arr, i*i);
+	}
+	assert(arr_len(arr) == 10000);
+	arr_remove_last(arr);
+	assert(arr_len(arr) == 9999);
+	for (i = 0; i < arr_len(arr); ++i)
+		assert(arr[i] == i*i);
+	while (arr_len(arr))
+		arr_remove_last(arr);
+	assert(arr_len(arr) == 0);
+}
+#endif
+
+static void str_builder_create(StrBuilder *builder) {
+	memset(builder, 0, sizeof *builder);
+	arr_add(builder->str, 0);
+}
+
+static StrBuilder str_builder_new(void) {
+	StrBuilder ret = {0};
+	str_builder_create(&ret);
+	return ret;
+}
+
+static void str_builder_free(StrBuilder *builder) {
+	arr_free(builder->str);
+}
+
+static void str_builder_clear(StrBuilder *builder) {
+	str_builder_free(builder);
+	str_builder_create(builder);
+}
+
+static void str_builder_append(StrBuilder *builder, const char *s) {
+	assert(builder->str);
+	
+	size_t s_len = strlen(s);
+	size_t prev_size = arr_len(builder->str);
+	size_t prev_len = prev_size - 1; // null terminator
+	// note: this zeroes the newly created elements, so we have a new null terminator
+	arr_set_len(builder->str, prev_size + s_len);
+	memcpy(builder->str + prev_len, s, s_len);
+}
+
+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};
+	va_start(args, fmt);
+	int ret = vsnprintf(fakebuf, 1, fmt, args);
+	va_end(args);
+	
+	if (ret < 0) return; // bad format or something
+	u32 n = (u32)ret;
+	
+	size_t prev_size = arr_len(builder->str);
+	size_t prev_len = prev_size - 1; // null terminator
+	arr_set_len(builder->str, prev_size + n);
+	va_start(args, fmt);
+	vsnprintf(builder->str + prev_len, n + 1, fmt, args);
+	va_end(args);
+}
+
+// append n null bytes.
+static void str_builder_append_null(StrBuilder *builder, size_t n) {
+	arr_set_len(builder->str, arr_len(builder->str) + n);
+}
+
+static u32 str_builder_len(StrBuilder *builder) {
+	assert(builder->str);
+	return arr_len(builder->str) - 1;
+}
+
+static char *str_builder_get_ptr(StrBuilder *builder, size_t index) {
+	assert(index <= str_builder_len(builder));
+	return &builder->str[index];
+}
+
+static void str_builder_shrink(StrBuilder *builder, size_t new_len) {
+	if (new_len > str_builder_len(builder)) {
+		assert(0);
+		return;
+	}
+	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_
-- 
cgit v1.2.3