summaryrefslogtreecommitdiff
path: root/util.c
diff options
context:
space:
mode:
Diffstat (limited to 'util.c')
-rw-r--r--util.c185
1 files changed, 172 insertions, 13 deletions
diff --git a/util.c b/util.c
index 07cd8ea..32115cf 100644
--- a/util.c
+++ b/util.c
@@ -7,6 +7,21 @@
#error "Unrecognized operating system."
#endif
+
+// Is this character a "word" character?
+static bool is_word(char32_t c) {
+ return c > WCHAR_MAX || c == '_' || iswalnum((wint_t)c);
+}
+
+static bool is_digit(char32_t c) {
+ return c < WCHAR_MAX && iswdigit((wint_t)c);
+}
+
+static bool is_space(char32_t c) {
+ return c < WCHAR_MAX && iswspace((wint_t)c);
+}
+
+
static u8 util_popcount(u64 x) {
#ifdef __GNUC__
return (u8)__builtin_popcountll(x);
@@ -142,9 +157,14 @@ static void str_cat(char *dst, size_t dst_sz, char const *src) {
}
// safer version of strncpy. dst_sz includes a null terminator.
-static void str_cpy(char *dst, size_t dst_sz, char const *src) {
- size_t srclen = strlen(src);
- size_t n = srclen; // number of bytes to copy
+static void strn_cpy(char *dst, size_t dst_sz, char const *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') {
+ n = i;
+ break;
+ }
+ }
if (dst_sz == 0) {
assert(0);
@@ -157,6 +177,11 @@ static void str_cpy(char *dst, size_t dst_sz, char const *src) {
dst[n] = 0;
}
+// safer version of strcpy. dst_sz includes a null terminator.
+static void str_cpy(char *dst, size_t dst_sz, char const *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)
@@ -239,18 +264,28 @@ static int str_qsort_case_insensitive_cmp(const void *av, const void *bv) {
return strcmp_case_insensitive(*a, *b);
}
-static void *qsort_ctx_arg;
-static int (*qsort_ctx_cmp)(void *, const void *, const void *);
-static int qsort_with_context_cmp(const void *a, const void *b) {
- return qsort_ctx_cmp(qsort_ctx_arg, a, b);
+// imo windows has the argument order right here
+#if _WIN32
+#define qsort_with_context qsort_s
+#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) {
+ QSortWithContext *c = context;
+ return c->compar(c->context, a, b);
}
-
-static void qsort_with_context(void *base, size_t nmemb, size_t size, int (*compar)(void *, const void *, const void *), void *arg) {
- // just use global variables. hopefully we don't try to run this in something multithreaded!
- qsort_ctx_arg = arg;
- qsort_ctx_cmp = compar;
- qsort(base, nmemb, size, qsort_with_context_cmp);
+static void qsort_with_context(void *base, size_t nmemb, size_t size,
+ int (*compar)(void *, const void *, const void *),
+ void *arg) {
+ QSortWithContext ctx = {
+ .compar = compar,
+ .context = arg
+ };
+ qsort_r(base, nmemb, size, qsort_with_context_cmp, &ctx);
}
+#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.
@@ -357,3 +392,127 @@ static bool copy_file(char const *src, char const *dst) {
}
return success;
}
+
+
+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));
+}