C: implementing str_replace to replace all occurrences of substring

Articles may may have files attached at the end of the post

Last time, I showed how to replace PHP's str_replace in C.

The previous code was only replacing one occurrence of substr which might be sufficient in most cases... but will not do the job when the pattern appears more than once within the original string.

This new piece of code will replace ALL occurrences of substring by the replacement pattern.

The following bit of code might miss some optimization, for instance we could first check how many times the pattern is found and then do only one big allocation and enter another loop to replace all patterns, but for now, this is what I came with.

Maybe at a later stage I will come with another version a bit more optimized.

  1. /**
  2.  * vim: tabstop=2:shiftwidth=2:softtabstop=2:expandtab
  3.  *
  4.  * str_replace.c implements a str_replace PHP like function
  5.  * Copyright (C) 2010  chantra <chantra__A__debuntu__D__org>
  6.  *
  7.  * This program is free software; you can redistribute it and/or
  8.  * modify it under the terms of the GNU General Public License
  9.  * as published by the Free Software Foundation; either version 2
  10.  * of the License, or (at your option) any later version.
  11.  *
  12.  * This program is distributed in the hope that it will be useful,
  13.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.  * GNU General Public License for more details.
  16.  *
  17.  * You should have received a copy of the GNU General Public License
  18.  * along with this program; if not, write to the Free Software
  19.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  20.  *
  21.  * gcc -o str_replace_all str_replace_all.c
  22.  */
  23.  
  24. #include <stdio.h>
  25. #include <string.h>
  26. #include <stdlib.h>
  27.  
  28. void usage(char *p){
  29.   fprintf(stderr, "USAGE: %s string tok replacement\n", p );
  30. }
  31.  
  32. char *
  33. str_replace ( const char *string, const char *substr, const char *replacement ){
  34.   char *tok = NULL;
  35.   char *newstr = NULL;
  36.   char *oldstr = NULL;
  37.   /* if either substr or replacement is NULL, duplicate string a let caller handle it */
  38.   if ( substr == NULL || replacement == NULL ) return strdup (string);
  39.   newstr = strdup (string);
  40.   while ( (tok = strstr ( newstr, substr ))){
  41.     oldstr = newstr;
  42.     newstr = malloc ( strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) + 1 );
  43.     /*failed to alloc mem, free old string and return NULL */
  44.     if ( newstr == NULL ){
  45.       free (oldstr);
  46.       return NULL;
  47.     }
  48.     memcpy ( newstr, oldstr, tok - oldstr );
  49.     memcpy ( newstr + (tok - oldstr), replacement, strlen ( replacement ) );
  50.     memcpy ( newstr + (tok - oldstr) + strlen( replacement ), tok + strlen ( substr ), strlen ( oldstr ) - strlen ( substr ) - ( tok - oldstr ) );
  51.     memset ( newstr + strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) , 0, 1 );
  52.     free (oldstr);
  53.   }
  54.   return newstr;
  55. }
  56.  
  57. int main( int argc, char **argv ){
  58.   char *ns = NULL;
  59.   if( argc != 4 ) {
  60.     usage(argv[0]);
  61.     return 1;
  62.   }
  63.   ns = str_replace( argv[1], argv[2], argv[3] );
  64.   fprintf( stdout, "Old string: %s\nTok: %s\nReplacement: %s\nNew string: %s\n", argv[1], argv[2], argv[3], ns );
  65.   free(ns);
  66.   return 0;
  67. }

Will output:

$ gcc -o str_replace_all str_replace_all.c
$ ./str_replace_all "(uid=%u/%u)" "%u" chantra
Old string: (uid=%u/%u)
Tok: %u
Replacement: chantra
New string: (uid=chantra/chantra)

AttachmentSize
str_replace_all.c2.39 KB

update on your code

FYI, your code works well as long as the thing you're replacement string doesn't include the needle value, otherwise the code is trapped in an infinite loop.

ie:

./str_replace_all foobar bar bar2

*should* have returned foobar2 but instead it gets stuck in an infinite loop building foobar2222222222222222222222222...... because the strstr() check in the while() condition starts looking at the beginning of the haystack string (or new haystack) every time, so 'bar' would get replaced with 'bar2' over and over again.

A few simple changes fixes the problem:

  1.  32 char *
  2.  33 str_replace ( const char *string, const char *substr, const char *replacement ){
  3.  34   char *tok = NULL;
  4.  35   char *newstr = NULL;
  5.  36   char *oldstr = NULL;
  6. *37   char *strhead = NULL;
  7.  38   /* if either substr or replacement is NULL, duplicate string a let caller handle it */
  8.  39   if ( substr == NULL || replacement == NULL ) return strdup (string);
  9.  40   newstr = strdup (string);
  10.  41  
  11. *42   strhead = newstr ;
  12. *43   while ( (tok = strstr ( strhead, substr )) ) {
  13. *44     strhead = tok ;

Line 37 adds a new pointer
Line 42 points strhead to the beginning of your new haystack string
Line 43 changes your strstr() call to use strhead
Line 44 points strhead to the token found from strstr()

Thanks for the code!

yet another version

Tks Landouglas,

Yeah, I forgot this case :s which is really bad.

Your solution is also missing something and will only replace 1 occurrence within the string.

Here is a revised solution:

  1. char *
  2. str_replace ( const char *string, const char *substr, const char *replacement ){
  3.   char *tok = NULL;
  4.   char *newstr = NULL;
  5.   char *oldstr = NULL;
  6.   char *head = NULL;
  7.  
  8.   /* if either substr or replacement is NULL, duplicate string a let caller handle it */
  9.   if ( substr == NULL || replacement == NULL ) return strdup (string);
  10.   newstr = strdup (string);
  11.   head = newstr;
  12.   while ( (tok = strstr ( head, substr ))){
  13.     oldstr = newstr;
  14.     newstr = malloc ( strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) + 1 );
  15.     /*failed to alloc mem, free old string and return NULL */
  16.     if ( newstr == NULL ){
  17.       free (oldstr);
  18.       return NULL;
  19.     }
  20.     memcpy ( newstr, oldstr, tok - oldstr );
  21.     memcpy ( newstr + (tok - oldstr), replacement, strlen ( replacement ) );
  22.     memcpy ( newstr + (tok - oldstr) + strlen( replacement ), tok + strlen ( substr ), strlen ( oldstr ) - strlen ( substr ) - ( tok - oldstr ) );
  23.     memset ( newstr + strlen ( oldstr ) - strlen ( substr ) + strlen ( replacement ) , 0, 1 );
  24.     /* move back head right after the last replacement */
  25.     head = newstr + (tok - oldstr) + strlen( replacement );
  26.     free (oldstr);
  27.   }
  28.   return newstr;
  29. }