summaryrefslogtreecommitdiffstats
path: root/src/dstring.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2024-05-07 15:42:46 -0400
committerTavian Barnes <tavianator@tavianator.com>2024-05-07 15:42:46 -0400
commit452d6697e0f92326ab139eed4eadd9c2fd8b55ca (patch)
tree0feeb3722dcf6debb6c33c5175342bf1d70a1dba /src/dstring.c
parenta4299f9bc1d3e60a7e628561e8d650c2a241e1c2 (diff)
parentc5cf2cf90834f2f56b2940d2a499a1a614ebfd21 (diff)
downloadbfs-find2fd.tar.xz
Merge branch 'main' into find2fdfind2fd
Diffstat (limited to 'src/dstring.c')
-rw-r--r--src/dstring.c231
1 files changed, 145 insertions, 86 deletions
diff --git a/src/dstring.c b/src/dstring.c
index f344d09..b5bf3d3 100644
--- a/src/dstring.c
+++ b/src/dstring.c
@@ -1,147 +1,184 @@
-/****************************************************************************
- * bfs *
- * Copyright (C) 2016-2022 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * Permission to use, copy, modify, and/or distribute this software for any *
- * purpose with or without fee is hereby granted. *
- * *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
- ****************************************************************************/
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+#include "prelude.h"
#include "dstring.h"
-#include <assert.h>
+#include "alloc.h"
+#include "bit.h"
+#include "diag.h"
#include <stdarg.h>
+#include <stddef.h>
+#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
- * The memory representation of a dynamic string. Users get a pointer to data.
+ * The memory representation of a dynamic string. Users get a pointer to str.
*/
struct dstring {
- size_t capacity;
- size_t length;
- char data[];
+ /** Capacity of the string, *including* the terminating NUL. */
+ size_t cap;
+ /** Length of the string, *excluding* the terminating NUL. */
+ size_t len;
+ /** The string itself. */
+ alignas(dchar) char str[];
};
-/** Get the string header from the string data pointer. */
-static struct dstring *dstrheader(const char *dstr) {
- return (struct dstring *)(dstr - offsetof(struct dstring, data));
+#define DSTR_OFFSET offsetof(struct dstring, str)
+
+/** Back up to the header from a pointer to dstring::str. */
+static struct dstring *dstrheader(const dchar *dstr) {
+ return (struct dstring *)(dstr - DSTR_OFFSET);
}
-/** Get the correct size for a dstring with the given capacity. */
-static size_t dstrsize(size_t capacity) {
- return BFS_FLEX_SIZEOF(struct dstring, data, capacity + 1);
+/**
+ * In some provenance models, the expression `header->str` has its provenance
+ * restricted to just the `str` field itself, making a future dstrheader()
+ * illegal. This alternative is guaranteed to preserve provenance for the entire
+ * allocation.
+ *
+ * - https://stackoverflow.com/q/25296019
+ * - https://mastodon.social/@void_friend@tech.lgbt/111144859908104311
+ */
+static dchar *dstrdata(struct dstring *header) {
+ return (char *)header + DSTR_OFFSET;
}
/** Allocate a dstring with the given contents. */
-static char *dstralloc_impl(size_t capacity, size_t length, const char *data) {
+static dchar *dstralloc_impl(size_t cap, size_t len, const char *str) {
// Avoid reallocations for small strings
- if (capacity < 7) {
- capacity = 7;
+ if (cap < DSTR_OFFSET) {
+ cap = DSTR_OFFSET;
}
- struct dstring *header = malloc(dstrsize(capacity));
+ struct dstring *header = ALLOC_FLEX(struct dstring, str, cap);
if (!header) {
return NULL;
}
- header->capacity = capacity;
- header->length = length;
+ header->cap = cap;
+ header->len = len;
- memcpy(header->data, data, length);
- header->data[length] = '\0';
- return header->data;
+ char *ret = dstrdata(header);
+ memcpy(ret, str, len);
+ ret[len] = '\0';
+ return ret;
}
-char *dstralloc(size_t capacity) {
- return dstralloc_impl(capacity, 0, "");
+dchar *dstralloc(size_t cap) {
+ return dstralloc_impl(cap + 1, 0, "");
}
-char *dstrdup(const char *str) {
- size_t len = strlen(str);
- return dstralloc_impl(len, len, str);
+dchar *dstrdup(const char *str) {
+ return dstrxdup(str, strlen(str));
}
-char *dstrndup(const char *str, size_t n) {
- size_t len = strnlen(str, n);
- return dstralloc_impl(len, len, str);
+dchar *dstrndup(const char *str, size_t n) {
+ return dstrxdup(str, strnlen(str, n));
}
-size_t dstrlen(const char *dstr) {
- return dstrheader(dstr)->length;
+dchar *dstrddup(const dchar *dstr) {
+ return dstrxdup(dstr, dstrlen(dstr));
}
-int dstreserve(char **dstr, size_t capacity) {
- struct dstring *header = dstrheader(*dstr);
+dchar *dstrxdup(const char *str, size_t len) {
+ return dstralloc_impl(len + 1, len, str);
+}
- if (capacity > header->capacity) {
- capacity *= 2;
+size_t dstrlen(const dchar *dstr) {
+ return dstrheader(dstr)->len;
+}
- header = realloc(header, dstrsize(capacity));
- if (!header) {
- return -1;
- }
- header->capacity = capacity;
+int dstreserve(dchar **dstr, size_t cap) {
+ if (!*dstr) {
+ *dstr = dstralloc(cap);
+ return *dstr ? 0 : -1;
+ }
- *dstr = header->data;
+ struct dstring *header = dstrheader(*dstr);
+ size_t old_cap = header->cap;
+ size_t new_cap = cap + 1; // Terminating NUL
+ if (old_cap >= new_cap) {
+ return 0;
}
+ new_cap = bit_ceil(new_cap);
+ header = REALLOC_FLEX(struct dstring, str, header, old_cap, new_cap);
+ if (!header) {
+ return -1;
+ }
+
+ header->cap = new_cap;
+ *dstr = dstrdata(header);
return 0;
}
-int dstresize(char **dstr, size_t length) {
- if (dstreserve(dstr, length) != 0) {
+int dstresize(dchar **dstr, size_t len) {
+ if (dstreserve(dstr, len) != 0) {
return -1;
}
struct dstring *header = dstrheader(*dstr);
- header->length = length;
- header->data[length] = '\0';
-
+ header->len = len;
+ header->str[len] = '\0';
return 0;
}
-/** Common implementation of dstr{cat,ncat,app}. */
-static int dstrcat_impl(char **dest, const char *src, size_t srclen) {
+int dstrcat(dchar **dest, const char *src) {
+ return dstrxcat(dest, src, strlen(src));
+}
+
+int dstrncat(dchar **dest, const char *src, size_t n) {
+ return dstrxcat(dest, src, strnlen(src, n));
+}
+
+int dstrdcat(dchar **dest, const dchar *src) {
+ return dstrxcat(dest, src, dstrlen(src));
+}
+
+int dstrxcat(dchar **dest, const char *src, size_t len) {
size_t oldlen = dstrlen(*dest);
- size_t newlen = oldlen + srclen;
+ size_t newlen = oldlen + len;
if (dstresize(dest, newlen) != 0) {
return -1;
}
- memcpy(*dest + oldlen, src, srclen);
+ memcpy(*dest + oldlen, src, len);
return 0;
}
-int dstrcat(char **dest, const char *src) {
- return dstrcat_impl(dest, src, strlen(src));
+int dstrapp(dchar **str, char c) {
+ return dstrxcat(str, &c, 1);
}
-int dstrncat(char **dest, const char *src, size_t n) {
- return dstrcat_impl(dest, src, strnlen(src, n));
+int dstrcpy(dchar **dest, const char *src) {
+ return dstrxcpy(dest, src, strlen(src));
}
-int dstrdcat(char **dest, const char *src) {
- return dstrcat_impl(dest, src, dstrlen(src));
+int dstrncpy(dchar **dest, const char *src, size_t n) {
+ return dstrxcpy(dest, src, strnlen(src, n));
}
-int dstrapp(char **str, char c) {
- return dstrcat_impl(str, &c, 1);
+int dstrdcpy(dchar **dest, const dchar *src) {
+ return dstrxcpy(dest, src, dstrlen(src));
+}
+
+int dstrxcpy(dchar **dest, const char *src, size_t len) {
+ if (dstresize(dest, len) != 0) {
+ return -1;
+ }
+
+ memcpy(*dest, src, len);
+ return 0;
}
char *dstrprintf(const char *format, ...) {
va_list args;
va_start(args, format);
- char *str = dstrvprintf(format, args);
+ dchar *str = dstrvprintf(format, args);
va_end(args);
return str;
@@ -149,7 +186,7 @@ char *dstrprintf(const char *format, ...) {
char *dstrvprintf(const char *format, va_list args) {
// Guess a capacity to try to avoid reallocating
- char *str = dstralloc(2*strlen(format));
+ dchar *str = dstralloc(2 * strlen(format));
if (!str) {
return NULL;
}
@@ -162,7 +199,7 @@ char *dstrvprintf(const char *format, va_list args) {
return str;
}
-int dstrcatf(char **str, const char *format, ...) {
+int dstrcatf(dchar **str, const char *format, ...) {
va_list args;
va_start(args, format);
@@ -172,48 +209,70 @@ int dstrcatf(char **str, const char *format, ...) {
return ret;
}
-int dstrvcatf(char **str, const char *format, va_list args) {
+int dstrvcatf(dchar **str, const char *format, va_list args) {
// Guess a capacity to try to avoid calling vsnprintf() twice
size_t len = dstrlen(*str);
- dstreserve(str, len + 2*strlen(format));
- size_t cap = dstrheader(*str)->capacity;
+ dstreserve(str, len + 2 * strlen(format));
+ size_t cap = dstrheader(*str)->cap;
va_list copy;
va_copy(copy, args);
char *tail = *str + len;
- int ret = vsnprintf(tail, cap - len + 1, format, args);
+ size_t tail_cap = cap - len;
+ int ret = vsnprintf(tail, tail_cap, format, args);
if (ret < 0) {
goto fail;
}
size_t tail_len = ret;
- if (tail_len > cap - len) {
- cap = len + tail_len;
- if (dstreserve(str, cap) != 0) {
+ if (tail_len >= tail_cap) {
+ if (dstreserve(str, len + tail_len) != 0) {
goto fail;
}
tail = *str + len;
ret = vsnprintf(tail, tail_len + 1, format, copy);
if (ret < 0 || (size_t)ret != tail_len) {
- assert(!"Length of formatted string changed");
+ bfs_bug("Length of formatted string changed");
goto fail;
}
}
va_end(copy);
- struct dstring *header = dstrheader(*str);
- header->length += tail_len;
+ dstrheader(*str)->len += tail_len;
return 0;
fail:
+ va_end(copy);
*tail = '\0';
return -1;
}
-void dstrfree(char *dstr) {
+int dstrescat(dchar **dest, const char *str, enum wesc_flags flags) {
+ return dstrnescat(dest, str, SIZE_MAX, flags);
+}
+
+int dstrnescat(dchar **dest, const char *str, size_t n, enum wesc_flags flags) {
+ size_t len = *dest ? dstrlen(*dest) : 0;
+
+ // Worst case growth is `ccc...` => $'\xCC\xCC\xCC...'
+ n = strnlen(str, n);
+ size_t cap = len + 4 * n + 3;
+ if (dstreserve(dest, cap) != 0) {
+ return -1;
+ }
+
+ char *cur = *dest + len;
+ char *end = *dest + cap + 1;
+ cur = wordnesc(cur, end, str, n, flags);
+ bfs_assert(cur != end, "wordesc() result truncated");
+
+ return dstresize(dest, cur - *dest);
+}
+
+void dstrfree(dchar *dstr) {
if (dstr) {
free(dstrheader(dstr));
}