Thread: insertstr

  1. #16
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Well thank you for at least explaining that, however I see 2 problems with your version for performance and memory, first the memory, your version creates a new string forcing the programmer to free up more memory after each call, 2nd is the performance I see at least 6 calls not including the aforementioned free which would cause significant overhead when doing it on hundreds or even thousands of calls (which my app may very well have to make), my version you will notice makes no attempt to allocate memory aside from the variables it needs, and for performance it is better to skip the overhead of calling functions which will check the parameters anyway adding yet more cycles. I do realise I can probably squeeze more cycles out of this and will do at another time but for now my current version is sufficient for my needs and anyone who wishes to copy it. While I'm on the topic I will mention this now, any code I post on these forums I don't mind being copied for programmes so long as a comment is added in the destination mentioning the source.

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I agree that it would be better to avoid dynamic memory allocation here. Such a decision could be left to the caller, and if necessary one could write a wrapper. That said, I also agree that your code seems overly complicated, including the version from post #9. Trying my hand, I came up with:
    Code:
    char *insertstr(char *haystack, char const *needle, size_t size, size_t pos)
    {
        const size_t haystack_len = strlen(haystack);
        const size_t needle_len = strlen(needle);
        const size_t total_len = haystack_len + needle_len;
        if (total_len >= size)
        {
            return NULL;
        }
        else if (needle_len == 0)
        {
            return haystack;
        }
    
        if (pos > haystack_len)
        {
            pos = haystack_len;
        }
    
        memmove(haystack + pos + needle_len, haystack + pos, haystack_len - pos);
        strncpy(haystack + pos, needle, needle_len);
        haystack[total_len] = '\0';
    
        return haystack;
    }
    If you fear that memmove might be relatively expensive, then you can replace it with a loop that starts from the back to avoid overwriting across an overlap:
    Code:
    char *insertstr(char *haystack, char const *needle, size_t size, size_t pos)
    {
        const size_t haystack_len = strlen(haystack);
        const size_t needle_len = strlen(needle);
        const size_t total_len = haystack_len + needle_len;
        size_t i;
        if (total_len >= size)
        {
            return NULL;
        }
        else if (needle_len == 0)
        {
            return haystack;
        }
    
        if (pos > haystack_len)
        {
            pos = haystack_len;
        }
    
        i = haystack_len;
        while (i-- > pos)
        {
            haystack[i + needle_len] = haystack[i];
        }
        strncpy(haystack + pos, needle, needle_len);
        haystack[total_len] = '\0';
    
        return haystack;
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Thank you, I'll consider those when I get back to re-examining insertstr, for now though I will be continuing with the app I was developing, I code by the motto "first make it work, then make it fast"

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, it probably isn't significantly more (or less) efficient. And yes, assuming that you have formulated a reasonable algorithm, making it work would be a better idea to start with than making it fast. The point though is to reinforce the idea behind Jimmy's post #7: look for tools that can make things work for you before you write from scratch. In this case I replaced the memmove with a loop with the consideration of efficiency, but even then it might be unnecessary. Consider that these three lines:
    Code:
    memmove(haystack + pos + needle_len, haystack + pos, haystack_len - pos);
    strncpy(haystack + pos, needle, needle_len);
    haystack[total_len] = '\0';
    do the bulk of the actual work of string insertion that was done with your two for loops and the if/else statement, and yet is easier to understand (memmove to move the substring after the insertion point to its destination; strncpy to copy the string to be inserted to its destination - admittedly these would be suitable comments), so it becomes a matter of checking that the arguments specify the correct ranges to move or copy to/from.

    You probably should replace strncpy with memcpy though: in retrospect, you don't need to bother with null characters, so memcpy would be better than strncpy.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Quote Originally Posted by awsdert View Post
    I've got a strong feeling something is wrong with this code but as I presently cannot see it
    But I thought your code is perfection! Your understanding is second only to God's! How could anyone here, as an inferior programmer of little understand help you?

  6. #21
    Lurker
    Join Date
    Dec 2004
    Posts
    296
    Something similar to what Laserlight suggested is what I would expect any decent programmer would come up with.

    But I have to ask, Laserlight, why did you have to put the needle back in the haystack? I went through all the trouble of finding it, now I have to do it all over again! :-)

  7. #22
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Quote Originally Posted by Yarin View Post
    But I thought your code is perfection! Your understanding is second only to God's! How could anyone here, as an inferior programmer of little understand help you?
    When did I ever say my code was perfect, I said in the thread you're referencing that only God could provide a better structure (assuming such a thing is possible for that particular scenario),
    App loads most data, then loads a library selected by user to load a file in the format the library supports, using a library keeps the app small as there are many formats out there (most of which I do not even know about), it also avoids recompiling the app every time a new format is supported, tell me how do you think that structure is bad?

  8. #23
    Registered User
    Join Date
    Jan 2014
    Posts
    45
    Hmm ...

    Code:
    #include <stdio.h>
    #include <string.h>
    
    char *insert(char *to, const char *s, int split, const char *in)
    {
    	sprintf(to, "%.*s%s%s", split, s, in, s + split);
    	return to;
    }
    
    int main(void)
    {
    	const char *s = "I robots";
    	char t[64];
    
    	puts(insert(t, s, strcspn(s, " "), " like"));
    	return 0;
    }

  9. #24
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    nice idea but still needs an extra buffer to print to, show me one without the extra buffer that is safe like laserlight's version or my version (haven't actually tried laserlight's version yet)

  10. #25
    Registered User
    Join Date
    Jan 2014
    Posts
    45
    It is not unsafe for the caller to know what they're giving a function, it is simply unappealing to the lowest common denominator.
    Code:
    #include <stdlib.h>
    
    char *insertstr(char *s, int split, const char *in)
    {
    	char *r;
    
    	if ((r = malloc(strlen(s) + strlen(in) + 1)) == NULL)
    		return NULL;
    	strcpy(s, insert(r, s, split, in));
    	free(r);
    	return s;
    }

  11. #26
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by zyxwvuts
    It is not unsafe for the caller to know what they're giving a function, it is simply unappealing to the lowest common denominator.
    Although that is true, e.g., if the caller really did allocate enough space, then the use of sprintf or strcpy is fine, in practice I would say that the bad reputation that C has for buffer overflows has much to do with null terminated strings and string facilities that do not require maximum lengths to be passed as arguments.

    The issue about the extra buffer seems to me to be a matter of efficiency: if you already know that there is enough space to insert the string in-place, it is unnecessary to require an additional buffer altogether. Writing a wrapper to abstract this away is good, but the malloc/free and strcpy could well be unnecessary work. With an in-place solution on the other hand, one could abstract away the need to pass the maximum length by say, writing a wrapper to use malloc and return the result.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #27
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    well there is that however for my instance the destination buffer is used in strtoul straight away afterwords:
    Code:
    char *tok = *line ? insertstr( line, " ", 80, 8 ) : NULL
    ulong p1 = *line ? strtoul( line, &tok, 16 ) : 0;
    ulong p2 = *line ? strtoul( tok, NULL, 16 ) : 0;
    The analysis has worked fine thus far, however writing that has just triggered a thought for a debugging error I was having.

    Edit: Also line is a buffer passed to several functions (depending on what stage the analysis is at)
    Last edited by awsdert; 02-05-2015 at 03:11 AM.

  13. #28
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Quote Originally Posted by laserlight View Post
    I agree that it would be better to avoid dynamic memory allocation here. Such a decision could be left to the caller, and if necessary one could write a wrapper. That said, I also agree that your code seems overly complicated, including the version from post #9. Trying my hand, I came up with:

    If you fear that memmove might be relatively expensive, then you can replace it with a loop that starts from the back to avoid overwriting across an overlap:
    Having taken your examples into account I saw a way to simplify my function as far as I can possibly get:
    Code:
    char* insertstr( char *dst, size_t const size, char const *src )
    {
      size_t srcLen = strlen( src );
      size_t dstLen = strlen( dst );
      size_t length = srcLen + dstLen;
      if ( length >= size )
        return NULL;
      if ( !srcLen )
        return dst;
      dst[length] = '\0';
      while ( length > srcLen )
      {
        dst[--length] = dst[--dstLen];
      }
      while ( length > 0 )
      {
        dst[--length] = src[--srcLen];
      }
      return dst;
    }
    Tested with:
    Code:
    char test[100] = "01234ABCDEF";
    insertstr( &test[5], 100 - 5, "56789" );
    to get the expected "0123456789ABCDEF"

  14. #29
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Ah, instead of specifying the position to insert, you require the caller to do pointer arithmetic (if applicable), then prepend src to dst. Looks workable, though then I suggest that you rename your function to prependstr.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #30
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Quote Originally Posted by laserlight View Post
    I suggest that you rename your function to prependstr.
    Don't be glib, laserlight. Only God could design it better.

Popular pages Recent additions subscribe to a feed