ucx/string.c

branch
newapi
changeset 174
0358f1d9c506
child 253
087cc9216f28
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/string.c	Mon May 22 16:17:26 2023 +0200
@@ -0,0 +1,785 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *   1. Redistributions of source code must retain the above copyright
+ *      notice, this list of conditions and the following disclaimer.
+ *
+ *   2. Redistributions in binary form must reproduce the above copyright
+ *      notice, this list of conditions and the following disclaimer in the
+ *      documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "cx/string.h"
+#include "cx/utils.h"
+
+#include <string.h>
+#include <stdarg.h>
+#include <ctype.h>
+
+#ifndef _WIN32
+
+#include <strings.h> // for strncasecmp()
+
+#endif // _WIN32
+
+cxmutstr cx_mutstr(char *cstring) {
+    return (cxmutstr) {cstring, strlen(cstring)};
+}
+
+cxmutstr cx_mutstrn(
+        char *cstring,
+        size_t length
+) {
+    return (cxmutstr) {cstring, length};
+}
+
+cxstring cx_str(const char *cstring) {
+    return (cxstring) {cstring, strlen(cstring)};
+}
+
+cxstring cx_strn(
+        const char *cstring,
+        size_t length
+) {
+    return (cxstring) {cstring, length};
+}
+
+cxstring cx_strcast(cxmutstr str) {
+    return (cxstring) {str.ptr, str.length};
+}
+
+void cx_strfree(cxmutstr *str) {
+    free(str->ptr);
+    str->ptr = NULL;
+    str->length = 0;
+}
+
+void cx_strfree_a(
+        CxAllocator const *alloc,
+        cxmutstr *str
+) {
+    cxFree(alloc, str->ptr);
+    str->ptr = NULL;
+    str->length = 0;
+}
+
+size_t cx_strlen(
+        size_t count,
+        ...
+) {
+    if (count == 0) return 0;
+
+    va_list ap;
+    va_start(ap, count);
+    size_t size = 0;
+    cx_for_n(i, count) {
+        cxstring str = va_arg(ap, cxstring);
+        size += str.length;
+    }
+    va_end(ap);
+
+    return size;
+}
+
+cxmutstr cx_strcat_ma(
+        CxAllocator const *alloc,
+        cxmutstr str,
+        size_t count,
+        ...
+) {
+    if (count == 0) return str;
+
+    cxstring *strings = calloc(count, sizeof(cxstring));
+    if (!strings) abort();
+
+    va_list ap;
+    va_start(ap, count);
+
+    // get all args and overall length
+    size_t slen = str.length;
+    cx_for_n(i, count) {
+        cxstring s = va_arg (ap, cxstring);
+        strings[i] = s;
+        slen += s.length;
+    }
+    va_end(ap);
+
+    // reallocate or create new string
+    if (str.ptr == NULL) {
+        str.ptr = cxMalloc(alloc, slen + 1);
+    } else {
+        str.ptr = cxRealloc(alloc, str.ptr, slen + 1);
+    }
+    if (str.ptr == NULL) abort();
+
+    // concatenate strings
+    size_t pos = str.length;
+    str.length = slen;
+    cx_for_n(i, count) {
+        cxstring s = strings[i];
+        memcpy(str.ptr + pos, s.ptr, s.length);
+        pos += s.length;
+    }
+
+    // terminate string
+    str.ptr[str.length] = '\0';
+
+    // free temporary array
+    free(strings);
+
+    return str;
+}
+
+cxstring cx_strsubs(
+        cxstring string,
+        size_t start
+) {
+    return cx_strsubsl(string, start, string.length - start);
+}
+
+cxmutstr cx_strsubs_m(
+        cxmutstr string,
+        size_t start
+) {
+    return cx_strsubsl_m(string, start, string.length - start);
+}
+
+cxstring cx_strsubsl(
+        cxstring string,
+        size_t start,
+        size_t length
+) {
+    if (start > string.length) {
+        return (cxstring) {NULL, 0};
+    }
+
+    size_t rem_len = string.length - start;
+    if (length > rem_len) {
+        length = rem_len;
+    }
+
+    return (cxstring) {string.ptr + start, length};
+}
+
+cxmutstr cx_strsubsl_m(
+        cxmutstr string,
+        size_t start,
+        size_t length
+) {
+    cxstring result = cx_strsubsl(cx_strcast(string), start, length);
+    return (cxmutstr) {(char *) result.ptr, result.length};
+}
+
+cxstring cx_strchr(
+        cxstring string,
+        int chr
+) {
+    chr = 0xFF & chr;
+    // TODO: improve by comparing multiple bytes at once
+    cx_for_n(i, string.length) {
+        if (string.ptr[i] == chr) {
+            return cx_strsubs(string, i);
+        }
+    }
+    return (cxstring) {NULL, 0};
+}
+
+cxmutstr cx_strchr_m(
+        cxmutstr string,
+        int chr
+) {
+    cxstring result = cx_strchr(cx_strcast(string), chr);
+    return (cxmutstr) {(char *) result.ptr, result.length};
+}
+
+cxstring cx_strrchr(
+        cxstring string,
+        int chr
+) {
+    chr = 0xFF & chr;
+    size_t i = string.length;
+    while (i > 0) {
+        i--;
+        // TODO: improve by comparing multiple bytes at once
+        if (string.ptr[i] == chr) {
+            return cx_strsubs(string, i);
+        }
+    }
+    return (cxstring) {NULL, 0};
+}
+
+cxmutstr cx_strrchr_m(
+        cxmutstr string,
+        int chr
+) {
+    cxstring result = cx_strrchr(cx_strcast(string), chr);
+    return (cxmutstr) {(char *) result.ptr, result.length};
+}
+
+#ifndef CX_STRSTR_SBO_SIZE
+#define CX_STRSTR_SBO_SIZE 512
+#endif
+
+cxstring cx_strstr(
+        cxstring haystack,
+        cxstring needle
+) {
+    if (needle.length == 0) {
+        return haystack;
+    }
+
+    // optimize for single-char needles
+    if (needle.length == 1) {
+        return cx_strchr(haystack, *needle.ptr);
+    }
+
+    /*
+     * IMPORTANT:
+     * Our prefix table contains the prefix length PLUS ONE
+     * this is our decision, because we want to use the full range of size_t.
+     * The original algorithm needs a (-1) at one single place,
+     * and we want to avoid that.
+     */
+
+    // local prefix table
+    size_t s_prefix_table[CX_STRSTR_SBO_SIZE];
+
+    // check needle length and use appropriate prefix table
+    // if the pattern exceeds static prefix table, allocate on the heap
+    bool useheap = needle.length >= CX_STRSTR_SBO_SIZE;
+    register size_t *ptable = useheap ? calloc(needle.length + 1,
+                                               sizeof(size_t)) : s_prefix_table;
+
+    // keep counter in registers
+    register size_t i, j;
+
+    // fill prefix table
+    i = 0;
+    j = 0;
+    ptable[i] = j;
+    while (i < needle.length) {
+        while (j >= 1 && needle.ptr[j - 1] != needle.ptr[i]) {
+            j = ptable[j - 1];
+        }
+        i++;
+        j++;
+        ptable[i] = j;
+    }
+
+    // search
+    cxstring result = {NULL, 0};
+    i = 0;
+    j = 1;
+    while (i < haystack.length) {
+        while (j >= 1 && haystack.ptr[i] != needle.ptr[j - 1]) {
+            j = ptable[j - 1];
+        }
+        i++;
+        j++;
+        if (j - 1 == needle.length) {
+            size_t start = i - needle.length;
+            result.ptr = haystack.ptr + start;
+            result.length = haystack.length - start;
+            break;
+        }
+    }
+
+    // if prefix table was allocated on the heap, free it
+    if (ptable != s_prefix_table) {
+        free(ptable);
+    }
+
+    return result;
+}
+
+cxmutstr cx_strstr_m(
+        cxmutstr haystack,
+        cxstring needle
+) {
+    cxstring result = cx_strstr(cx_strcast(haystack), needle);
+    return (cxmutstr) {(char *) result.ptr, result.length};
+}
+
+size_t cx_strsplit(
+        cxstring string,
+        cxstring delim,
+        size_t limit,
+        cxstring *output
+) {
+    // special case: output limit is zero
+    if (limit == 0) return 0;
+
+    // special case: delimiter is empty
+    if (delim.length == 0) {
+        output[0] = string;
+        return 1;
+    }
+
+    // special cases: delimiter is at least as large as the string
+    if (delim.length >= string.length) {
+        // exact match
+        if (cx_strcmp(string, delim) == 0) {
+            output[0] = cx_strn(string.ptr, 0);
+            output[1] = cx_strn(string.ptr + string.length, 0);
+            return 2;
+        } else {
+            // no match possible
+            output[0] = string;
+            return 1;
+        }
+    }
+
+    size_t n = 0;
+    cxstring curpos = string;
+    while (1) {
+        ++n;
+        cxstring match = cx_strstr(curpos, delim);
+        if (match.length > 0) {
+            // is the limit reached?
+            if (n < limit) {
+                // copy the current string to the array
+                cxstring item = cx_strn(curpos.ptr, match.ptr - curpos.ptr);
+                output[n - 1] = item;
+                size_t processed = item.length + delim.length;
+                curpos.ptr += processed;
+                curpos.length -= processed;
+            } else {
+                // limit reached, copy the _full_ remaining string
+                output[n - 1] = curpos;
+                break;
+            }
+        } else {
+            // no more matches, copy last string
+            output[n - 1] = curpos;
+            break;
+        }
+    }
+
+    return n;
+}
+
+size_t cx_strsplit_a(
+        CxAllocator const *allocator,
+        cxstring string,
+        cxstring delim,
+        size_t limit,
+        cxstring **output
+) {
+    // find out how many splits we're going to make and allocate memory
+    size_t n = 0;
+    cxstring curpos = string;
+    while (1) {
+        ++n;
+        cxstring match = cx_strstr(curpos, delim);
+        if (match.length > 0) {
+            // is the limit reached?
+            if (n < limit) {
+                size_t processed = match.ptr - curpos.ptr + delim.length;
+                curpos.ptr += processed;
+                curpos.length -= processed;
+            } else {
+                // limit reached
+                break;
+            }
+        } else {
+            // no more matches
+            break;
+        }
+    }
+    *output = cxCalloc(allocator, n, sizeof(cxstring));
+    return cx_strsplit(string, delim, n, *output);
+}
+
+size_t cx_strsplit_m(
+        cxmutstr string,
+        cxstring delim,
+        size_t limit,
+        cxmutstr *output
+) {
+    return cx_strsplit(cx_strcast(string),
+                       delim, limit, (cxstring *) output);
+}
+
+size_t cx_strsplit_ma(
+        CxAllocator const *allocator,
+        cxmutstr string,
+        cxstring delim,
+        size_t limit,
+        cxmutstr **output
+) {
+    return cx_strsplit_a(allocator, cx_strcast(string),
+                         delim, limit, (cxstring **) output);
+}
+
+int cx_strcmp(
+        cxstring s1,
+        cxstring s2
+) {
+    if (s1.length == s2.length) {
+        return memcmp(s1.ptr, s2.ptr, s1.length);
+    } else if (s1.length > s2.length) {
+        return 1;
+    } else {
+        return -1;
+    }
+}
+
+int cx_strcasecmp(
+        cxstring s1,
+        cxstring s2
+) {
+    if (s1.length == s2.length) {
+#ifdef _WIN32
+        return _strnicmp(s1.ptr, s2.ptr, s1.length);
+#else
+        return strncasecmp(s1.ptr, s2.ptr, s1.length);
+#endif
+    } else if (s1.length > s2.length) {
+        return 1;
+    } else {
+        return -1;
+    }
+}
+
+int cx_strcmp_p(
+        void const *s1,
+        void const *s2
+) {
+    cxstring const *left = s1;
+    cxstring const *right = s2;
+    return cx_strcmp(*left, *right);
+}
+
+int cx_strcasecmp_p(
+        void const *s1,
+        void const *s2
+) {
+    cxstring const *left = s1;
+    cxstring const *right = s2;
+    return cx_strcasecmp(*left, *right);
+}
+
+cxmutstr cx_strdup_a(
+        CxAllocator const *allocator,
+        cxstring string
+) {
+    cxmutstr result = {
+            cxMalloc(allocator, string.length + 1),
+            string.length
+    };
+    if (result.ptr == NULL) {
+        result.length = 0;
+        return result;
+    }
+    memcpy(result.ptr, string.ptr, string.length);
+    result.ptr[string.length] = '\0';
+    return result;
+}
+
+cxstring cx_strtrim(cxstring string) {
+    cxstring result = string;
+    // TODO: optimize by comparing multiple bytes at once
+    while (result.length > 0 && isspace(*result.ptr)) {
+        result.ptr++;
+        result.length--;
+    }
+    while (result.length > 0 && isspace(result.ptr[result.length - 1])) {
+        result.length--;
+    }
+    return result;
+}
+
+cxmutstr cx_strtrim_m(cxmutstr string) {
+    cxstring result = cx_strtrim(cx_strcast(string));
+    return (cxmutstr) {(char *) result.ptr, result.length};
+}
+
+bool cx_strprefix(
+        cxstring string,
+        cxstring prefix
+) {
+    if (string.length < prefix.length) return false;
+    return memcmp(string.ptr, prefix.ptr, prefix.length) == 0;
+}
+
+bool cx_strsuffix(
+        cxstring string,
+        cxstring suffix
+) {
+    if (string.length < suffix.length) return false;
+    return memcmp(string.ptr + string.length - suffix.length,
+                  suffix.ptr, suffix.length) == 0;
+}
+
+bool cx_strcaseprefix(
+        cxstring string,
+        cxstring prefix
+) {
+    if (string.length < prefix.length) return false;
+#ifdef _WIN32
+    return _strnicmp(string.ptr, prefix.ptr, prefix.length) == 0;
+#else
+    return strncasecmp(string.ptr, prefix.ptr, prefix.length) == 0;
+#endif
+}
+
+bool cx_strcasesuffix(
+        cxstring string,
+        cxstring suffix
+) {
+    if (string.length < suffix.length) return false;
+#ifdef _WIN32
+    return _strnicmp(string.ptr+string.length-suffix.length,
+                  suffix.ptr, suffix.length) == 0;
+#else
+    return strncasecmp(string.ptr + string.length - suffix.length,
+                       suffix.ptr, suffix.length) == 0;
+#endif
+}
+
+void cx_strlower(cxmutstr string) {
+    cx_for_n(i, string.length) {
+        string.ptr[i] = (char) tolower(string.ptr[i]);
+    }
+}
+
+void cx_strupper(cxmutstr string) {
+    cx_for_n(i, string.length) {
+        string.ptr[i] = (char) toupper(string.ptr[i]);
+    }
+}
+
+#ifndef CX_STRREPLACE_INDEX_BUFFER_SIZE
+#define CX_STRREPLACE_INDEX_BUFFER_SIZE 64
+#endif
+
+struct cx_strreplace_ibuf {
+    size_t *buf;
+    struct cx_strreplace_ibuf *next;
+    unsigned int len;
+};
+
+static void cx_strrepl_free_ibuf(struct cx_strreplace_ibuf *buf) {
+    while (buf) {
+        struct cx_strreplace_ibuf *next = buf->next;
+        free(buf->buf);
+        free(buf);
+        buf = next;
+    }
+}
+
+cxmutstr cx_strreplacen_a(
+        CxAllocator const *allocator,
+        cxstring str,
+        cxstring pattern,
+        cxstring replacement,
+        size_t replmax
+) {
+
+    if (pattern.length == 0 || pattern.length > str.length || replmax == 0)
+        return cx_strdup_a(allocator, str);
+
+    // Compute expected buffer length
+    size_t ibufmax = str.length / pattern.length;
+    size_t ibuflen = replmax < ibufmax ? replmax : ibufmax;
+    if (ibuflen > CX_STRREPLACE_INDEX_BUFFER_SIZE) {
+        ibuflen = CX_STRREPLACE_INDEX_BUFFER_SIZE;
+    }
+
+    // Allocate first index buffer
+    struct cx_strreplace_ibuf *firstbuf, *curbuf;
+    firstbuf = curbuf = calloc(1, sizeof(struct cx_strreplace_ibuf));
+    if (!firstbuf) return cx_mutstrn(NULL, 0);
+    firstbuf->buf = calloc(ibuflen, sizeof(size_t));
+    if (!firstbuf->buf) {
+        free(firstbuf);
+        return cx_mutstrn(NULL, 0);
+    }
+
+    // Search occurrences
+    cxstring searchstr = str;
+    size_t found = 0;
+    do {
+        cxstring match = cx_strstr(searchstr, pattern);
+        if (match.length > 0) {
+            // Allocate next buffer in chain, if required
+            if (curbuf->len == ibuflen) {
+                struct cx_strreplace_ibuf *nextbuf =
+                        calloc(1, sizeof(struct cx_strreplace_ibuf));
+                if (!nextbuf) {
+                    cx_strrepl_free_ibuf(firstbuf);
+                    return cx_mutstrn(NULL, 0);
+                }
+                nextbuf->buf = calloc(ibuflen, sizeof(size_t));
+                if (!nextbuf->buf) {
+                    free(nextbuf);
+                    cx_strrepl_free_ibuf(firstbuf);
+                    return cx_mutstrn(NULL, 0);
+                }
+                curbuf->next = nextbuf;
+                curbuf = nextbuf;
+            }
+
+            // Record match index
+            found++;
+            size_t idx = match.ptr - str.ptr;
+            curbuf->buf[curbuf->len++] = idx;
+            searchstr.ptr = match.ptr + pattern.length;
+            searchstr.length = str.length - idx - pattern.length;
+        } else {
+            break;
+        }
+    } while (searchstr.length > 0 && found < replmax);
+
+    // Allocate result string
+    cxmutstr result;
+    {
+        ssize_t adjlen = (ssize_t) replacement.length - (ssize_t) pattern.length;
+        size_t rcount = 0;
+        curbuf = firstbuf;
+        do {
+            rcount += curbuf->len;
+            curbuf = curbuf->next;
+        } while (curbuf);
+        result.length = str.length + rcount * adjlen;
+        result.ptr = cxMalloc(allocator, result.length + 1);
+        if (!result.ptr) {
+            cx_strrepl_free_ibuf(firstbuf);
+            return cx_mutstrn(NULL, 0);
+        }
+    }
+
+    // Build result string
+    curbuf = firstbuf;
+    size_t srcidx = 0;
+    char *destptr = result.ptr;
+    do {
+        for (size_t i = 0; i < curbuf->len; i++) {
+            // Copy source part up to next match
+            size_t idx = curbuf->buf[i];
+            size_t srclen = idx - srcidx;
+            if (srclen > 0) {
+                memcpy(destptr, str.ptr + srcidx, srclen);
+                destptr += srclen;
+                srcidx += srclen;
+            }
+
+            // Copy the replacement and skip the source pattern
+            srcidx += pattern.length;
+            memcpy(destptr, replacement.ptr, replacement.length);
+            destptr += replacement.length;
+        }
+        curbuf = curbuf->next;
+    } while (curbuf);
+    memcpy(destptr, str.ptr + srcidx, str.length - srcidx);
+
+    // Result is guaranteed to be zero-terminated
+    result.ptr[result.length] = '\0';
+
+    // Free index buffer
+    cx_strrepl_free_ibuf(firstbuf);
+
+    return result;
+}
+
+CxStrtokCtx cx_strtok(
+        cxstring str,
+        cxstring delim,
+        size_t limit
+) {
+    CxStrtokCtx ctx;
+    ctx.str = str;
+    ctx.delim = delim;
+    ctx.limit = limit;
+    ctx.pos = 0;
+    ctx.next_pos = 0;
+    ctx.delim_pos = 0;
+    ctx.found = 0;
+    ctx.delim_more = NULL;
+    ctx.delim_more_count = 0;
+    return ctx;
+}
+
+CxStrtokCtx cx_strtok_m(
+        cxmutstr str,
+        cxstring delim,
+        size_t limit
+) {
+    return cx_strtok(cx_strcast(str), delim, limit);
+}
+
+bool cx_strtok_next(
+        CxStrtokCtx *ctx,
+        cxstring *token
+) {
+    // abortion criteria
+    if (ctx->found >= ctx->limit || ctx->delim_pos >= ctx->str.length) {
+        return false;
+    }
+
+    // determine the search start
+    cxstring haystack = cx_strsubs(ctx->str, ctx->next_pos);
+
+    // search the next delimiter
+    cxstring delim = cx_strstr(haystack, ctx->delim);
+
+    // if found, make delim capture exactly the delimiter
+    if (delim.length > 0) {
+        delim.length = ctx->delim.length;
+    }
+
+    // if more delimiters are specified, check them now
+    if (ctx->delim_more_count > 0) {
+        cx_for_n(i, ctx->delim_more_count) {
+            cxstring d = cx_strstr(haystack, ctx->delim_more[i]);
+            if (d.length > 0 && (delim.length == 0 || d.ptr < delim.ptr)) {
+                delim.ptr = d.ptr;
+                delim.length = ctx->delim_more[i].length;
+            }
+        }
+    }
+
+    // store the token information and adjust the context
+    ctx->found++;
+    ctx->pos = ctx->next_pos;
+    token->ptr = &ctx->str.ptr[ctx->pos];
+    ctx->delim_pos = delim.length == 0 ?
+                     ctx->str.length : (size_t) (delim.ptr - ctx->str.ptr);
+    token->length = ctx->delim_pos - ctx->pos;
+    ctx->next_pos = ctx->delim_pos + delim.length;
+
+    return true;
+}
+
+bool cx_strtok_next_m(
+        CxStrtokCtx *ctx,
+        cxmutstr *token
+) {
+    return cx_strtok_next(ctx, (cxstring *) token);
+}
+
+void cx_strtok_delim(
+        CxStrtokCtx *ctx,
+        cxstring const *delim,
+        size_t count
+) {
+    ctx->delim_more = delim;
+    ctx->delim_more_count = count;
+}

mercurial