?
Solved

Substring replacement within a string

Posted on 2003-03-09
14
Medium Priority
?
1,209 Views
Last Modified: 2010-04-15
Hello all:

I currently have a replace substring function that I implemented to do just that replace all occurences of a substring in a given string. I am making use of this function in a c Library I am writing as part of an API I am developing. In any event the replace string function I am using is used extensively, and frequently (i.e might be a memory hog), thus I am wondering if someone might be able to provide me with an example of an EXTREMELY memory friendly replace substring function.... I thought mine was friendly, but lately I am wondering if it really is due to recent crashes I have been experiencing the more I make use of it.

One last thought is that under normal circumstances I would post the replace substring function that I am using, however, i developed it at work and since I work at a secure sight (i.e. no access from our internal network to the world, no floppy drives etc..). It makes it slightly difficult to share my code with you, without me rehashing and redevloping it on this internet machine, which by the way has no compiler for me to test it on anyway...

Anyway, could someone please provide me with an example of an extremely memory friendly replace substring function... Any suggestions, examples, code are greatly welcomed...

By the way this will be used on a Solaris machine, but should be pretty easy to implement using ANSI standard libraries... right???

Thanks in advance...

rechard
0
Comment
Question by:rechard
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
14 Comments
 
LVL 6

Expert Comment

by:gj62
ID: 8098906
Hmmm, I don't know why a string replace function would be memory intensive -

Can you at least post your function definition, (so we can pattern ours after yours)?

Also, is it replacing an identical number of characters, or must it grow/shrink the string within the function?

If you are crashing, have you allocated memory (perhaps via malloc, etc) that you are not freeing?  

A basic replace function would be to use strstr() to find the location of the replacement string, and if you are replacing with the same number of characters, simply memcpy them over...

Something tells me you want more than this...
0
 

Author Comment

by:rechard
ID: 8098965
gj62.. I agree... In any event I have no other thoughts here... my api does string repalcement on lines that it reads in from a translated XML file, to make it understandable to the application I am interfacing with.. Thus for evey line I read in from a file I first passit through this replaceSubString function that I wrote... It is so hard to trap, exactly where the problem is occuring.. This is what makes me think it might be memory related... In other words, it crashes all over the place... not in the smae place twice... sometimes I can run it numerous times w/o crash,other times it fails on first "package" I send through the API... SInce everything I do in my API uses this replaceSubstring function I thought it would be a starting place for figuring out whats up...

Answers to your questions... my declartation looks something like
char *replaceSubstring(char *string, char *oldstring, char *newstring)

In most cases oldstring is smaller than the string that is used to replace it.. Thus I need to make extensive use of realloc/malloc functions.. I have attempted to be very careful with my memory allocation/deallocation and freeing it, but perhaps there is a problem here.. Like I said this is a starting place for figuring this out... may not even be the problem... but worth a shot since this is "the most intensive memory " piece of my library used by the API....

Also after reading another question posted in this forum (I think from rdest5) I am wondering if I can do something like he is suggesting.. That is perhaps display some sort of memory usage at various points in my library.. i.e. memory being consumed, memory free, etc... then I could call this function at various points in this library to display the current state of memory... perhaps a way to debug it??

thoughts?

thanks for getting back to me so soon..

rechard
0
 
LVL 5

Expert Comment

by:Kocil
ID: 8098972
No code from him, because its extremely important and top secret.
But he ask code from us ... and with only 20 points !
Please be fair man.

0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:rechard
ID: 8098993
Kocil

come on man thats all the point I have right now.. In any event... I asked for suggestions, examples, code etc.. whatever you want to share (code was never my only request or requirement)...

I didn't say it was extremely important or top secret but that I work at a secure sight and can't get my code out the door (here)..

Sorry

rechard
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8099062

Hi Rechard,

Try this:


/*  Replace all occurences of a string with another

  OldString  - The original string
  src        - The target string (search item)
  dst        - The destination string (replacement item)
  NewString  - The modified string
*/

char *ReplaceAll (char *OldString, char *src, char *dst)
{
  int NewLength;
  int ReplaceCount;
  char *NewString;
  char *sp, *op;

/*  Count the number of items to replace.  */

  for (ReplaceCount = 0, sp = OldString; *OldString;)
  {
    sp = strstr (sp, src);
    if (sp)
    {
      ReplaceCount++;
      sp += strlen (src);
    }
  }

/*  Allocate a new string of sufficient proportions  */

  NewLength = strlen (OldString) + (ReplaceCount * (strlen (dst) - strlen (src))) + 2;
  NewString = (char *)malloc (NewLength);
  memset (NewString, 0, NewLength);

/*  Copy the original string replacing "src" with "dst"  */

  op = OldString;
  while (op)
  {
    sp = strstr (op, src);  /*  find next replacement object  */
    if (sp)
    { /*  copy the intervening text  */
      memcpy (NewString+strlen(NewString), op, sp-op);
      strcat (NewString, dst);  /*  replace src with dst  */
      op = sp + strlen (src);   /*  advance old pointer  */
    }
    else
    {
      strcat (NewString, op);
      break;  /*  the entire string has been copied  */
    }
  }
  return (NewString);
}


Good Luck,
Kdo
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8099073

Apologies for taking so long.  The phone rang 1/2 way through typing the routine.  It was the boss -- and he insisted on a priority status.

Then work became an issue.  A couple of UDB instances were fighting back.  :)


The routine that I provided should handle any length string and properly allocates a correctly sized buffer.

BTW, if strlen(src) == 0, I'm sure you won't like the results.  ;)


Again, Good Luck,
Kdo
0
 

Author Comment

by:rechard
ID: 8099139
Kdo...

Am I being retarded or is there a problem with the first for loop???

just checking

thanks for the suggestion I will try it as soon as I have finished downloading/installing my compiler...

rechard
0
 

Author Comment

by:rechard
ID: 8099148
Kdo...

Am I being retarded or is there a problem with the first for loop???

just checking

thanks for the suggestion I will try it as soon as I have finished downloading/installing my compiler...

rechard
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8099184

Yeah -- Lysdexia (or lunacy) on my part.  It should be:

for (ReplaceCount = 0, sp = OldString; *sp;)


Apologies,

Kdo
0
 

Author Comment

by:rechard
ID: 8099214
Kdo

No apologies neccessary... In any event... I will try it out thanks...

In general is memset/memcpy safer than malloc/realloc/free? etc? or are the equivalent.. i am new to the concepts of memset and memcpy... does anything need to "be freed" in this function.. what are the basic ideas/rules when using memset and memcpy?

Thanks much...

rechard

0
 

Author Comment

by:rechard
ID: 8099233
Also why when using malloc in function are you adding 2 and not just 1... I understand that you have to add1 for \0 terminator... but why the other byte...?

thanks again...

PS please do not think I am trying to be critical at all.. i am not (in fact I appreciate your quick response) just trying to get an understanding...

thanks again

rechard
0
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 80 total points
ID: 8099318

memset() and memcpy() manipulate existing data/buffers.  You should become very familiar with them as they are your friends -- you'll use them a LOT!

No good reason on the "+2".  It's a (bad) habit that I got into years ago when I was trying to track down my own memory leak.  I try to type "+1" but sometimes my fingers just won't let me do it when I'm calculating a buffer length.  :)


This function should be fast enough, but it may not be the most efficient.  It scans the string twice with strstr().

Having a huge buffer that you're SURE won't be overrun as the destination buffer will allow you to scan it only once, but this is pretty wasteful.

And a recursive function might actually be more efficient, but if you're not accustomed to recursion, trying to decypher the code can be pretty daunting.

Kdo
0
 
LVL 20

Expert Comment

by:jmcg
ID: 10089671
Nothing has happened on this question in more than 10 months. It's time for cleanup!

My recommendation, which I will post in the Cleanup topic area, is to
accept answer by Kdo.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

jmcg
EE Cleanup Volunteer
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
Suggested Courses
Course of the Month9 days, 19 hours left to enroll

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question