diff options
Diffstat (limited to 'util.c')
| -rw-r--r-- | util.c | 170 |
1 files changed, 157 insertions, 13 deletions
@@ -142,9 +142,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 +162,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 +249,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 +377,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)); +} |