11
\$\begingroup\$

In Pascal/Delphi, there's a built-in function for inserting a substring into a main string.

procedure Insert ( const InsertStr : string; var TargetStr : string; Position : Integer ) ;

I'm used to this function, so I'd like to simulate it in C.

Because the main string will generally become longer after an insertion, the way to proceed is:

  • To have some extra space in a char array allocated in stack, or
  • To use dynamically allocated strings.

I've chosen the second option. At the moment my code looks like this. It uses the standard C string.h library.

#include "stdlib.h"
#include "string.h"

void myStrInsert(const char *pWord, char **pStr, int pos)
{
    // Only dynamically allocated strings are allowed.
    if (pos < 0)
        return;
    int lenStr = strlen(*pStr);
    if (pos > lenStr)
        pos = lenStr;
    int lenWord = strlen(pWord);

    char *pResult = (char *)malloc(lenStr + lenWord + 1);
    if (pResult != NULL) {
        memcpy(pResult, *pStr, pos);
        memcpy(pResult + pos, pWord, lenWord);
        memcpy(pResult + pos + lenWord, *pStr + pos, lenStr - pos + 1);
        free(*pStr);
        *pStr = pResult;
    }
}

Can this function be simplified/optimized?

\$\endgroup\$
  • \$\begingroup\$ You have to ensure somehow that *pStr is a valid, dynamically allocated pointer. \$\endgroup\$ – πάντα ῥεῖ Apr 1 '18 at 13:19
11
\$\begingroup\$

There are a number of things that I see that may help you improve your code.

Use the appropriate form for #includes

The code has the appropriate #include files but they should be in angle brackets and not quotes. When you write #include "math.h" it is different from #include <math.h>. For standard headers, you should use the <> form. If you're not sure about the difference, see this question for more detail.

Don't use Hungarian notation

Prefixing every variable with an abbreviation of its type (e.g. pStr) is usually called "Hungarian notation" and it was once popular. Even then it was a bad idea. Don't clutter up your source code with that; instead, concentrate on defining meaningful names for each variable and choose types appropriately.

Return an error code

The myStrInsert function can detect errors, but gives no indication to the calling program that anything went wrong. A more robust design would return an error code.

Avoid memory fragmentation

The code allocates new space even if the original space would have had room. This is somewhat wasteful and can lead to memory fragmentation. Better would be to use realloc.

Do more error checking

It's good that pos is checked for a negative number, but it might be good to also check to assure that the pointers are not NULL before dereferencing them.

A possible rewrite

Using all of these suggestions, one might rewrite to something like this:

int myStrInsert(const char *inserted, char **target, int pos)
{
    if (inserted == NULL || target == NULL || *target == NULL || pos < 0) {
        return -2;
    }
    size_t wordlen = strlen(inserted);
    size_t origlen = strlen(*target);
    char *orig = realloc(*target, origlen+wordlen+1);
    if (orig == NULL) {
        return -1;
    }
    if (pos > origlen) {
        pos = origlen;
    } else {
        memmove(&orig[pos+wordlen], &orig[pos], origlen-pos);
    }
    memmove(&orig[pos], inserted, wordlen);
    orig[origlen+wordlen] = '\0';
    *target = orig;
    return 0;
}

Limitations

One thing I think I should mention is that, unlike the original code, this code is not robust if we attempt to splice a string into itself. That is, if we try to insert "fox" into the string "the fox" by passing in the first parameter as a pointer into the same string we're modifying, it's not necessarily well-behaved. It's something that isn't hard to fix, but I wanted to make sure that readers were aware of the limitation before attempting to use this code.

\$\endgroup\$
  • 1
    \$\begingroup\$ Joel Spolsky wrote a nice essay some years ago about how Hungarian notation made sense when it denoted the different meanings of variables that had the same type, to make it easier to notice that you were passing in an area instead of a length as a double or a hash value instead of an index as a size_t. But then Microsoft interpreted it as annotating all variables with their type, which the compiler already checks automatically. So, give your variables meaningful names? \$\endgroup\$ – Davislor Apr 2 '18 at 0:13
6
\$\begingroup\$

Yes, this is roughly how one might implement Pascal-style insert on C-style NUL-terminated strings. I would point out, however, that in the Pascal world, strings were normally counted rather than NUL-terminated, and if you're thinking in Pascal, you might be inclined to subtly make assumptions that do not hold on terminated strings, either relatively benign — such as the matter of forgetting that strlen() is not an O(1) but O(n) operation — or potentially dangerous — such as accidentally shoving terminators into your not-8-bit-clean strings. I would also point out that in Pascal, it was customary to number chars of a string from 1 onwards; you're interpreting pos in C style, so this being an inconsistency with the concept of a 'Pascal-style' insert, it would definitely merit a brief mention in documentation, such as a helpful comment above the function.

Edward is right about #insert <string.h> et al over #insert "string.h". I would disagree with him regarding "error checking"; in the context of Pascal-style string processing, these are boundary conditions, not errors, and if you're seeking to have a Pascal-style insert, you probably don't care about getting error codes for these conditions from your function, so it would be a waste of brain power to invent and remember encoding system for them. HOWEVER, you're treating the case of pos lying far left or far right of *pStr in two different ways: in the first case, you're not inserting anything, and in the second case, you're inserting pWord at the right end of *pStr. It is likely that consistency would be preferable here, either inserting in both cases or not inserting in either cases, unless you desire bug-compatibility with some particular pre-existing implementation.

As for Edward's recommendation of realloc() over malloc() — I would advise against it unless you find your system is running too slowly in practice. Premature optimisation is the root of all evil. Memory fragmentation of the kind you might get by calling malloc() is not a real issue in modern computer systems with paged virtual memory.

Besides the Hungarian notation, which I also recommend against, unless you're labouring under a code style guide that mandates it — it's bad but probably not worth a revolt —, there's another stylistic quirk in your code that slightly bothers me: you're typecasting the result of malloc() explicitly to (char *). This idea comes from a bunch of old — as in nineties — compilers for a weird language called "C/C++", which mixed ideas from C and C++. Real C does not need this typecast because in C, void * and char * are compatible; C++ needed it and so did the straddling "C/C++" compilers, but you would be using new char[...] (or quite possibly, new std::string(...)) if you were programming in real C++. So, I'm inclined to suggest you take out the typecast.

And finally, if you're using malloc() and free(), you'll need #include <stdlib.h>. You might get by the compiler without making it explicit, but it's generally considered a good practice to explicitly include headers for all the functions and types you directly refer in your code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.