Skip to content

Instantly share code, notes, and snippets.

@dhess
Created May 17, 2011 00:10
Show Gist options
  • Save dhess/975639 to your computer and use it in GitHub Desktop.
Save dhess/975639 to your computer and use it in GitHub Desktop.
strrep - substring replacement in 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;
}
@VNovytskyi
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment