strrep - substring replacement in C

strrep.c

/*
 * strrep.c - C substring replacement.
 *
 * Written in 2011 by Drew Hess <dhess-src@bothan.net>.
 *
 * To the extent possible under law, the author(s) have dedicated all
 * copyright and related and neighboring rights to this software to
 * the public domain worldwide. This software is distributed without
 * any warranty.
 *
 * For the full statement of the dedication, see the Creative Commons
 * CC0 Public Domain Dedication at
 * <http://creativecommons.org/publicdomain/zero/1.0/>.
 */

#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
 * This file includes a main() function so that the file can be
 * compiled into an executable, in order to run some simple test cases
 * on the included strrep() function. If you want to use strrep in
 * your own project, make sure you cut or comment out the main()
 * function below.
 */
 
/*
 * This function returns string s1 if string s2 is an empty string, or
 * if s2 is not found in s1. If s2 is found in s1, the function
 * returns a new null-terminated string whose contents are identical
 * to s1, except that all occurrences of s2 in the original string s1
 * are, in the new string, replaced by the string s3. The caller owns
 * the new string.
 *
 * Strings s1, s2, and s3 must all be null-terminated strings. If any
 * of s1, s2, or s3 are NULL, the function returns NULL, indicating an
 * error condition. If any other error occurs, the function returns
 * NULL.
 *
 * This code is written pedantically, primarily so that asserts can be
 * used liberally. The code could certainly be optimized and/or made
 * less verbose, and I encourage you to do that if you use strstr in
 * your production code, once you're comfortable that it functions as
 * intended. Each assert makes plain an invariant condition that is
 * assumed to be true by the statement(s) that immediately follow the
 * assert.  Some of the asserts are trivially true, as written, but
 * they're included, nonetheless, in case you, in the process of
 * optimizing or adapting the code for your own purposes, make a
 * change that breaks an assumption made downstream by the original
 * code.
 */

char *
strrep(const char *s1, const char *s2, const char *s3)
{
    if (!s1 || !s2 || !s3)
        return 0;
    size_t s1_len = strlen(s1);
    if (!s1_len)
        return (char *)s1;
    size_t s2_len = strlen(s2);
    if (!s2_len)
        return (char *)s1;

    /*
     * Two-pass approach: figure out how much space to allocate for
     * the new string, pre-allocate it, then perform replacement(s).
     */

    size_t count = 0;
    const char *p = s1;
    assert(s2_len); /* otherwise, strstr(s1,s2) will return s1. */
    do {
        p = strstr(p, s2);
        if (p) {
            p += s2_len;
            ++count;
        }
    } while (p);

    if (!count)
        return (char *)s1;

    /*
     * The following size arithmetic is extremely cautious, to guard
     * against size_t overflows.
     */
    assert(s1_len >= count * s2_len);
    assert(count);
    size_t s1_without_s2_len = s1_len - count * s2_len;
    size_t s3_len = strlen(s3);
    size_t newstr_len = s1_without_s2_len + count * s3_len;
    if (s3_len &&
        ((newstr_len <= s1_without_s2_len) || (newstr_len + 1 == 0)))
        /* Overflow. */
        return 0;
    
    char *newstr = (char *)malloc(newstr_len + 1); /* w/ terminator */
    if (!newstr)
        /* ENOMEM, but no good way to signal it. */
        return 0;
    
    char *dst = newstr;
    const char *start_substr = s1;
    size_t i;
    for (i = 0; i != count; ++i) {
        const char *end_substr = strstr(start_substr, s2);
        assert(end_substr);
        size_t substr_len = end_substr - start_substr;
        memcpy(dst, start_substr, substr_len);
        dst += substr_len;
        memcpy(dst, s3, s3_len);
        dst += s3_len;
        start_substr = end_substr + s2_len;
    }

    /* copy remainder of s1, including trailing '\0' */
    size_t remains = s1_len - (start_substr - s1) + 1;
    assert(dst + remains == newstr + newstr_len + 1);
    memcpy(dst, start_substr, remains);
    assert(strlen(newstr) == newstr_len);
    return newstr;
}

/*
 * A set of simple self-tests. To use strrep() in your own project,
 * cut or comment out the lines that follow.
 *
 * Otherwise, to compile this file into a test program, do this:
 *
 * cc -o strrep strrep.c
 */

#include <stdio.h>

int
main(int argc, char **argv)
{
    fprintf(stderr, "Test 1... ");
    const char *s1 = 0;
    const char *s2 = 0;
    const char *s3 = 0;
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");
    
    fprintf(stderr, "Test 2... ");
    s1 = "";
    s2 = 0;
    s3 = 0;
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 3... ");
    s1 = 0;
    s2 = "";
    s3 = 0;
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 4... ");
    s1 = "";
    s2 = "";
    s3 = 0;
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 5... ");
    s1 = 0;
    s2 = 0;
    s3 = "";
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 6... ");
    s1 = "";
    s2 = 0;
    s3 = "";
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 7... ");
    s1 = 0;
    s2 = "";
    s3 = "";
    assert(strrep(s1, s2, s3) == 0);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 8... ");
    s1 = "";
    s2 = "";
    s3 = "";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 9... ");
    s1 = "abc";
    s2 = "";
    s3 = "xyz";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 10... ");
    s1 = "";
    s2 = "abc";
    s3 = "xyz";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 11... ");
    s1 = "abc";
    s2 = "def";
    s3 = "xyz";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 12... ");
    s1 = "ab";
    s2 = "abc";
    s3 = "xyz";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 13... ");
    s1 = "abc";
    s2 = "abc";
    s3 = "xyz";
    char *s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyz") == 0);
    assert(s4 != s1);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 14... ");
    s1 = "abc";
    s2 = "a";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyzbc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 15... ");
    s1 = "abc";
    s2 = "b";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "axyzc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 15... ");
    s1 = "abc";
    s2 = "c";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abxyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 16... ");
    s1 = "aba";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyza") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 17... ");
    s1 = "bbc";
    s2 = "bc";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "bxyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 18... ");
    s1 = "a";
    s2 = "a";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 19... ");
    s1 = "ab";
    s2 = "a";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyzb") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 20... ");
    s1 = "ab";
    s2 = "b";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "axyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 21... ");
    s1 = "abbc";
    s2 = "ab";
    s3 = "x";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xbc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 22... ");
    s1 = "abcc";
    s2 = "bc";
    s3 = "x";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "axc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 23... ");
    s1 = "dccd";
    s2 = "cd";
    s3 = "x";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "dcx") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 24... ");
    s1 = "abab";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyzxyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 25... ");
    s1 = "abcab";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyzcxyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 26... ");
    s1 = "abcabc";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "xyzcxyzc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 27... ");
    s1 = "cabcab";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "cxyzcxyz") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 28... ");
    s1 = "cabcabc";
    s2 = "ab";
    s3 = "xyz";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "cxyzcxyzc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 29... ");
    s1 = "abc";
    s2 = "ab";
    s3 = "ab";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 30... ");
    s1 = "abc";
    s2 = "bc";
    s3 = "bc";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 31... ");
    s1 = "abcc";
    s2 = "abc";
    s3 = "ab";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 32... ");
    s1 = "abccc";
    s2 = "bc";
    s3 = "b";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abcc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 33... ");
    s1 = "abccc";
    s2 = "cc";
    s3 = "c";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abcc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 34... ");
    s1 = "abcd";
    s2 = "a";
    s3 = "";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "bcd") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 35... ");
    s1 = "abcd";
    s2 = "bc";
    s3 = "";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "ad") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 36... ");
    s1 = "abcd";
    s2 = "d";
    s3 = "";
    s4 = strrep(s1, s2, s3);
    assert(strcmp(s4, "abc") == 0);
    free(s4);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "Test 37... ");
    s1 = "";
    s2 = "";
    s3 = "abc";
    assert(strrep(s1, s2, s3) == s1);
    fprintf(stderr, "pass.\n");

    fprintf(stderr, "All tests pass.\n");

    return 0;
}

It was good to have the same implemented function without dynamic memory allocation.