how to replace substring in c ?

Question

This example works but I think that the memory leaks. Function used in the simple web server module and thus shared memory grows if you use this function.

    char *str_replace ( const char *string, const char *substr, const char *replacement ){
      char *tok = NULL;
      char *newstr = NULL;
      char *oldstr = NULL;
      if ( substr == NULL || replacement == NULL ) return strdup (string);
      newstr = strdup (string);
      while ( (tok = strstr ( newstr, substr ))){
        oldstr = newstr;
        newstr = malloc ( strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) + 1 );
        memset(newstr,0,strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) + 1);
        if ( newstr == NULL ){
          free (oldstr);
          return NULL;
        }
        memcpy ( newstr, oldstr, tok - oldstr );
        memcpy ( newstr + (tok - oldstr), replacement, strlen ( replacement ) );
        memcpy ( newstr + (tok - oldstr) + strlen( replacement ), tok + strlen ( substr ), strlen ( oldstr ) - strlen ( substr ) - ( tok - oldstr ) );
        memset ( newstr + strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) , 0, 1 );
        free (oldstr);
      }
      return newstr;
    }

Answer 1

Explain this part:

if ( substr == NULL || replacement == NULL ) return strdup (string);

Why do you return a copy of the existing string? This will leak memory, and it's unnecessary.

You also never free the duplicate if the while loop is skipped (i.e. the condition is never met).

Answer 2

One problem I can see is that if the replacement string contains the search string, you'll loop forever (until you run out of memory).

For example:

char *result = str_replace("abc", "a", "aa");

Also, doing another malloc/free every time you replace one instance is pretty expensive.

A better approach would be to do exactly 2 passes over the input string:

• the first pass, count how many instances of the search string are present

• now that you know how many matches, compute the length of your result & malloc once:

  strlen(string) + matches*(strlen(replacement)-strlen(substr)) + 1

• make a second pass through the source string, copying/replacing

Answer 3

• strdup is not C89/C99, therefore your code => no ANSI C
• better make the NULL-test direct after malloc

here an example, only with one new memoryblock:

/* precondition: s!=0, old!=0, new!=0 */
char *str_replace(const char *s, const char *old, const char *new)
{
  size_t slen = strlen(s)+1;
  char *cout = malloc(slen), *p=cout;
  if( !p )
    return 0;
  while( *s )
    if( !strncmp(s, old, strlen(old)) )
    {
      p  -= cout;
      cout= realloc(cout, slen += strlen(new)-strlen(old) );
      p  += strlen( strcpy(p=cout+(int)p, new) );
      s  += strlen(old);
    }
    else
     *p++=*s++;

  *p=0;
  return cout;
}