insert a char in the middle of a string

[tano]

Hello,
I have to insert a char in the middle of a string, I have written two functions
but I don't know what is the better? The problem is: if I use malloc() I copy
all the string with the new char in the middle every time, with realloc() the
part of the string before the position where the char has to be inserted is not
changed if realloc returns the same pointer is passed, but if not the
string is copied at all the first time, and then the part after the char has to
be shifted to right.. Perhaps it could be possible to make another function
using the system call of the os (brk, sbrk)?
Can anybody give me suggestions or clarify my ideas?
Thanks,
tano

/* Code: the len is in memory, incremented after every insertion, so it
doesn't need to compute it using strlen() */

#include <stdio.h>
#include <stdlib.h>

char* insert_char_malloc (char *str, int len, char c, int pos)
{
char *p;
int i;

p = malloc(len + 2);
for (i = 0 ; i < pos ; ++i)
p[i] = str[i];
p[i++] = c;
for ( ; i < len + 2 ; ++i)
p[i] = str[i - 1];
free(str);
return p;
}

char* insert_char_realloc (char *str, int len, char c, int pos)
{
int i;

str = realloc(str, len + 2);
for (i = len + 1 ; i > pos ; --i)
str[i] = str[i - 1];
str[i] = c;
return str;
}

[Nick Patavalis]

On 2004-08-09, tano <ta*****@yahoo.it> wrote:

I have to insert a char in the middle of a string, I have written
two functions but I don't know what is the better?

Both have their pros and cons, as you said yourself. I would
personally choose the "malloc" version, because it has a more
"constant" behavior. In any case it all depends on how often you have
to perform the operation: If not very often then you functions are
ok. If, though, you have to do it every once in a while (e.g. you 're
writing an editor), then you should probably choose a whole different
*representation* for your strings: Instead of having them be arrays of
chars you could implement them as lists of characters, or as lists of
arrays (substrings) that are broken and re-combined, and so on. The
possibilities are endless.

/npat

P.S. The system calls you mentioned cannot help you with this (they
are irrelevant).

[Christopher Benson-Manica]

tano <ta*****@yahoo.it> spoke thus:

char* insert_char_malloc (char *str, int len, char c, int pos)
{
char *p;
int i; p = malloc(len + 2);
You should check whether malloc() succeeded, if you were not aware of
that.
for (i = 0 ; i < pos ; ++i)
p[i] = str[i];
p[i++] = c;
for ( ; i < len + 2 ; ++i)
p[i] = str[i - 1];
free(str);
The caller has to be aware that str was freed, which IMHO is an
unnecessary burden.
return p;
}

I suggest (untested):

char *insert_char_realloc( char **str, int len, char c, int pos )
{
char *tmp=realloc( *str, len+2 );
if( !tmp ) { /* failed */
return NULL;
}
sprintf( tmp, "%.*s%c%s", pos, *str, c, *str+pos );
*str=tmp;
return *str;
}

I don't remember whether realloc( ptr, n ) == ptr; the double pointer
may be unnecessary. Of course, pos must be less than len or things
will break.

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

[Malcolm]

"tano" <ta*****@yahoo.it> wrote

I have to insert a char in the middle of a string, I have written two functions but I don't know what is the better?

/* Code: the len is in memory, incremented after every insertion, so it
doesn't need to compute it using strlen() */

#include <stdio.h>
#include <stdlib.h>

char* insert_char_malloc (char *str, int len, char c, int pos)
{
char *p;
int i;

p = malloc(len + 2);
You need to check p is non-null.
for (i = 0 ; i < pos ; ++i)
p[i] = str[i];
p[i++] = c;
for ( ; i < len + 2 ; ++i)
p[i] = str[i - 1];
free(str);
return p;
}
Consider carefully whether you want to free str, and whether you want to
insist that the length is passed in. Both these things may give you a speed
advantage, but make the function less generally useful.

char* insert_char_realloc (char *str, int len, char c, int pos)
{
int i;

str = realloc(str, len + 2);
You need to assign to a temporary and test str for null.
for (i = len + 1 ; i > pos ; --i)
str[i] = str[i - 1];
str[i] = c;
return str;
}

The realloc() version may well be faster, since realloc() doesn't always
perform a copy. Howver it suffers from the same problem that the interface
isn't clean - you must pass a pointer allocated with malloc and then
remember that it is invalidated by the call.

[SM Ryan]

# all the string with the new char in the middle every time, with realloc() the
# part of the string before the position where the char has to be inserted is not
# changed if realloc returns the same pointer is passed, but if not the
# string is copied at all the first time, and then the part after the char has to

realloc has a potential performance problem that you may not be aware of.
realloc can copy the string everytime; if the string is length n, that
is O(n) time. If you insert every character starting from an empty
string, that is n inserts or a total time of O(n^2).

If instead of copying each time 1, 2, 3, 4, 5, 6, 7, 8, ... , n = n(n+1)/2,
or O(n^2), you double the length only when necessary, 1, 2, 4, 4, 8, 8, 8,
8, ... , 2n, the number of copies is 1 + 2 + 4 + 8 +...
approx= 2^(log n) - 1, or O(n).

Bad news is that with C strings, you cannot deduce the allocated block
size from string length, and it is not portably available from the block
address, so you need to pass the allocated block size in and out.

If you do n mallocs of size 1, 2, 3, ..., n, you get this same quadratic
worst case performance.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
I think that's kinda of personal; I don't think I should answer that.

[Stan Milam]

tano wrote:

Hello,
I have to insert a char in the middle of a string, I have written two functions
but I don't know what is the better? The problem is: if I use malloc() I copy
all the string with the new char in the middle every time, with realloc() the
part of the string before the position where the char has to be inserted is not
changed if realloc returns the same pointer is passed, but if not the
string is copied at all the first time, and then the part after the char has to
be shifted to right.. Perhaps it could be possible to make another function
using the system call of the os (brk, sbrk)?
Can anybody give me suggestions or clarify my ideas?
Thanks,

This is some code I have saved away. It inserts one string of
characters into another, so I can be used to insert a single character too.

/**FILE******************************************** ********************/
/* File Id: STRINS.C. */
/* Author: William Smith. */
/* Date Written: 23 Dec. 92. */
/* */
/* This function inserts a string (ins) into a target string */
/* (str) at a specified position (pos) in the target string. */
/* The position for the insert must fall within the boundries */
/* of the target string. */
/* */
/* The inspiration of this code came from an article that ap- */
/* peared in the Jan. 93 issue of "The C Users Journal" called */
/* an "Essential String Library". I wrote this code without the */
/* benefit of the code listing in the magazine. */
/* */
/* Arguments: */
/* char *str - The address of the string to insert into. */
/* char *pos - Position in the string where the insert will */
/* be done. */
/* char *ins - The address of a string to insert into the */
/* target string. */
/* */
/* Returns: The address of the target string after the */
/* insert. */
/* */
/* NOTE: It is the programmer's responsiblity to ensure there */
/* is enough space in the target string to insert. */
/* */
/************************************************** **************FILE**/

#include <stddef.h>
#include <string.h>

char *str_insert(char *str, char *pos, char *ins) {

size_t inslen, poslen, lenstr;

lenstr = strlen(str); /* Get lengths */
inslen = strlen(ins);
if (inslen && pos >= str && pos <= &str[lenstr]) { /* Minimum edits */
poslen = strlen(pos); /* Adjusted
length */
memmove(pos + inslen, pos, poslen); /* Make room in
str */
memmove(pos, ins, inslen); /* Now copy in
ins */
}
return str; /* Return entire
str */
}

--
Regards,
Stan Milam.
-------------------------------------------------------
Spiritual people inspire me. Religeous people scare me.
-------------------------------------------------------

[Chris Torek]

Since no one else has pointed this out yet, I will:

In article <news:cf**********@chessie.cirr.com>
Christopher Benson-Manica <at***@nospam.cyberspace.org> wrote:

char *insert_char_realloc( char **str, int len, char c, int pos )
{
char *tmp=realloc( *str, len+2 );
if( !tmp ) { /* failed */
return NULL;
}
sprintf( tmp, "%.*s%c%s", pos, *str, c, *str+pos );
*str=tmp;
return *str;
}

I don't remember whether realloc( ptr, n ) == ptr; the double pointer
may be unnecessary. Of course, pos must be less than len or things
will break.

There are two problems here: (A) realloc() may move the data, and
in the process invalidate the old data, so that the call to sprintf()
passes the wrong values. This can be fixed, and in some cases
realloc() does not actually move the data, but then: (B) The
behavior of sprintf() is undefined if the output region (tmp)
overlaps the input (*str, or after fixing the bug, tmp again).

The memmove()-and-insert solution is probably the best to the
problem as stated, but in general, inserting one character at a
time into a potentially-long string is not a great strategy.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Christopher Benson-Manica]

Chris Torek <no****@torek.net> spoke thus:

There are two problems here: (A) realloc() may move the data, and
in the process invalidate the old data, so that the call to sprintf()
passes the wrong values. This can be fixed, and in some cases
realloc() does not actually move the data, but then: (B) The
behavior of sprintf() is undefined if the output region (tmp)
overlaps the input (*str, or after fixing the bug, tmp again).

I wasn't sure I remembered A, but it figures. B, however, is an
embarassing gaffe on my part, and I'm grateful that you didn't let me
get away with it :)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.