Skip to content

Instantly share code, notes, and snippets.

@nilium
Created September 24, 2010 21:54
Show Gist options
  • Save nilium/596119 to your computer and use it in GitHub Desktop.
Save nilium/596119 to your computer and use it in GitHub Desktop.
char *string_replace(const char *haystack, const char *needle, const char *replace) {
char *out_str, *out_ptr; // output string, pointer used for modifying output
int out_len, replace_len; // output length, replacement length
const char *replace_iter, *haystack_iter; // replacement iterater, haystack iterator
const char *needle_iter = NULL; // needle iterator
const char *haystack_last; // last known position in the haystack, used for backtracking
char haystack_val = 0; // last known value in the haystack (used to cut down on derefs)
char needle_val = 0; // current value in the needle search
if (!(haystack && needle && *haystack && *needle)) {
// no usable haystack or needle = gtfo
return NULL;
}
out_len = 0;
out_str = out_ptr = NULL;
replace_len = (replace ? strlen(replace) : 0);
haystack_iter = haystack;
// iterate through haystack string
while ((haystack_val = *haystack_iter)) {
// if there is no ongoing search and the first char of the needle matches
// the current haystack value, begin a search
if (!needle_iter && haystack_val == *needle) {
// increment length/iterators since we already know about the first character
needle_iter = needle+1;
haystack_last = ++haystack_iter;
++out_len;
continue;
}
// if there's an ongoing search
if (needle_iter) {
needle_val = *needle_iter;
if (!needle_val) {
// search complete, string matches the needle
--out_len; // decrement length to account for the needle's length
out_len += replace_len; // add the length of the replacement string to the output length
needle_iter = NULL; // end the search
} else if (needle_val == haystack_val) {
// search is ongoing and still matching
++needle_iter;
--out_len; // decrement length to account for the needle's length
} else {
// there was a non-matching character, terminate the search
needle_iter = NULL;
// backtrack to the last match
haystack_iter = haystack_last;
}
}
++out_len;
++haystack_iter;
}
haystack_iter = haystack;
out_ptr = out_str = (char*)malloc(out_len + 1 * sizeof(char));
while ((haystack_val = *haystack_iter)) {
if (!needle_iter && *haystack_iter == *needle) {
needle_iter = needle+1;
// we're now assigning characters to the output
*out_ptr = haystack_val;
haystack_last = ++haystack_iter;
continue;
}
if (needle_iter) {
if (!(needle_val = *needle_iter)) {
// replacement matched
replace_iter = replace;
// iterate over the replacement, inserting its characters
// into the output string
while (*replace_iter)
*(out_ptr++) = *(replace_iter++);
// end search
needle_iter = NULL;
} else if (needle_val == haystack_val) {
// incrmeent needle search
++needle_iter;
} else {
// something didn't match, end the search
needle_iter = NULL;
++out_ptr;
}
}
if (!needle_iter) {
// if no search is ongoing, add characters to the output string
*(out_ptr++) = haystack_val;
}
// continue iterating through the haystack
++haystack_iter;
}
*out_ptr = '\0'; // null term
return out_str;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment