Replace string with another string in C

Question

I have written a program that replaces a given c-string with another c-string. My code works well with small files but takes too much time while working with large files (50 Megabytes and larger).

Also, there's a fast_strncat() function which is much much faster than strcat() function.

Please don't get offended for replacing benzene with phenol, it's just a test case.

Here's the code:

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

void fast_strncat(char *dest, const char *src, size_t *size)
{
    if (dest && src && size)
        while ((dest[*size] = *src++))
            *size += 1;
}

void strreplace(char **str, const char *old, const char *new_)
{
    size_t i, count_old = 0, len_o = strlen(old), len_n = strlen(new_);
    const char *temp = (const char *)(*str);
    for (i = 0; temp[i] != '\0'; ++i)
    {
        if (strstr((const char *)&temp[i], old) == &temp[i])
        {
            count_old++;
            i += len_o - 1;
        }
    }
    char *buff = calloc((i + count_old * (len_n - len_o) + 1), sizeof(char));
    if (!buff)
    {
        perror("bad allocation\n");
        exit(EXIT_FAILURE);
    }
    i = 0;
    while (*temp)
    {
        if (strstr(temp, old) == temp)
        {
            size_t x = 0;
            fast_strncat(&buff[i], new_, &x);
            i += len_n;
            temp += len_o;
        }
        else
            buff[i++] = *temp++;
    }
    free(*str);
    *str = calloc(i + 1, sizeof(char));
    if (!(*str))
    {
        perror("bad allocation\n");
        exit(EXIT_FAILURE);
    }
    i = 0;
    fast_strncat(*str, (const char *)buff, &i);
    free(buff);
}

int main(void)
{
    FILE *fptr = fopen("./benzene.txt", "rb");
    if (fptr)
    {
        fseek(fptr, 0, SEEK_END);
        size_t len = ftell(fptr);
        fseek(fptr, 0, SEEK_SET);

        char *data = calloc(len + 1, sizeof(char));
        if (!data)
        {
            perror("bad allocation\n");
            return EXIT_FAILURE;
        }
        fread(data, sizeof(char), len, fptr);
        fclose(fptr);

        strreplace(&data, "Benzene", "phenol");

        fptr = fopen("./phenol.txt", "wb");
        if (!fptr)
        {
            perror("file not saved.\n");
            free(data);
            return EXIT_FAILURE;
        }

        fwrite(data, sizeof(char), strlen((const char *)data), fptr);
        fclose(fptr);
        free(data);
        return EXIT_SUCCESS;
    }
    perror("file not opened.\n");
    return EXIT_FAILURE;
}

I compiled the above program using the command:

gcc -Wall -Wextra main.c -o main

I ran the program for a 50 Megabytes file on zsh on Intel i5-7200U:

./main  29.09s user 0.14s system 97% cpu 30.033 total

Answer 1

The fast_strncat() is a good idea. The actual copying isn't efficient (though a good optimiser might recognise the pattern), but letting the caller know how much was copied helps avoid a program being Schlemiel the painter.

I don't like the name; it sounds too much like strncat(), which has very different behaviour. Perhaps len_strcpy() or something better conveys the functionality?

And instead of passing a pointer to result, it's generally better to return the result (either as a number of characters as here - though size_t is probably a better choice of type - or perhaps as a pointer to the new string end).

It's possible we don't need it though - see our use of memcpy in the next section.

---

The way we're using strstr() is very inefficient. We're traversing input a character at a time, repeating the same search until our position reaches the search result. Imagine this in human terms:

• "Run down the road to the first red house, and tell me where it is."
• It's not this one, so walk ahead to the next house.
• "Run down the road to the first red house, and tell me where it is."

Doesn't this sound a lot like Shlemiel's algorithm, that we worked so hard to avoid earlier?

We could consider using strncmp() instead in the same loop, but we can do better. Once we have the result from strstr(), we know there are no matches up to that result. So we can measure the length change much more simply:

size_t count_old = 0;
for (const char *p = *str;  (p = strstr(p, old));  ++p) {
    ++count_old;
}

And we can copy each chunk in one go:

while (*temp) {
    const char *next_match = strstr(temp, old);
    if (next_match) {
        size_t match_len = next_match - temp;
        memcpy(buff+i, temp, match_len);
        i += match_len;
        temp += match_len;
        memcpy(buff+i, new, len_n);
        i += len_n;
        temp += len_o;
    } else {
        /* no match - copy the remainder */
        strcpy(buff+i, temp);
    }

---

The code is quite limited because it will only work with seekable files, it has to read the entire file into memory, and it needs space for the entire output file in memory before it starts writing.

We can make it more efficient (and avoid the need to seek) by reading a buffer of characters, replacing matches within the buffer, and then writing out the buffer, before repeating. There's a small complication that we need to deal with matches that might straddle two reads - we need to write out all but len_o - 1 characters, and then move those last few to the front of the buffer, before reading the next characters after them. If we know we're working with streams, then there's no need to write to a new string array - just fwrite() each chunk as we get there.

On the other hand, if we want a general function to work on in-memory strings, we can avoid needing separate input and output arrays. It's possible to perform replacement in situ, provided our buffer is big enough to hold the bigger of input and output. The code needs to have two branches - working from the end if the replacement string is bigger than the match string, or from the beginning otherwise. I'd definitely recommend using unit tests to guide implementation if you choose to attempt such in-place substitution.

---

We have no error checking for the fwrite() and fclose() in main(). These functions can and do fail (e.g. disk quota reached), and we mustn't mislead the user that we succeeded if we haven't written all the output.

---

Minor things:

• We don't need to include a newline at the end of the message we give to perror(). That function will append : and error description, then a newline of its own.
• temp isn't a great name for a variable. It only tells us that it's short-lived, but doesn't indicate what it's for.
• There are many redundant casts - I don't think any of the casts here are necessary (Any Type* converts automatically to Type const* - a cast just costs the reader's time, and makes it harder to spot the true problems).
• The if (ptr) test leaves us holding state in our heads for half a screenful - it's easier to read if we test if (!ptr), which has a much shorter block (and also exits the function).
• sizeof (char) is always 1 (because sizeof works in units of char), so those expressions can be simplified.

Answer 2

fast_strncat() fails to make a string.

Used within strreplace(), fast_strncat() may work as that code uses zero'd out buffers. But fast_strncat() is not a static function and subject to other's use.

Either make fast_strncat() static or append the null character.

Lack of error checking

Functions like ftell(), fread(), etc. deserve to have the return value checked for errors.

On memory allocation failure, don't die.

strreplace() should return a success/failure error indication. Just like malloc(), let the caller decide.

Minor: Unneeded cast

// strlen((const char *)data)
strlen(data)

---

Candidate alterative: For long strings, I expect the efficiencies of strlen(), memcpy() will win out.

void fast_strncat_alt(char *dest, const char *src, size_t *dest_len) {
  if (dest && src) {
    size_t src_len = strlen(src);
    memcpy(dest + *dest_len, src, src_len + 1u);
    *dest_len += src_len;
  }
}

For a single pass, could use the below. This is reasonable when the compiler is smart enough to analyze sprintf(des,t "%s", src) and emit efficient code.

void fast_strncat_alt2(char *dest, const char *src, size_t *dest_len) {
  if (dest && src) {
    int len = sprintf(dest + *dest_len, "%s", src);
    *dest_len += len;
  }
}

Answer 3

        char *data = calloc(len + 1, sizeof(char));

When allocating memory, it is often better to use the other form of sizeof:

        char *data = calloc(len + 1, sizeof *data);

Now, let's say you decide to change the type of data to int. You just need to make one change.

        int *data = calloc(len + 1, sizeof *data);

With the original, you would have needed to make two changes in parallel. That increases the riskiness of the change. Because it's easy to forget and say

        int *data = calloc(len + 1, sizeof(char));

That can segfault if someone tries to access the second half (or the last three quarters or even the last seven eighths of the array). Because an int is generally at least sixteen bits and may be as much as sixty-four (and someone is probably working on a system with larger words). But if you say sizeof *data then you don't need to care about any of that.

The primary argument that I've seen against it is that it looks weird. It looks like you are trying to dereference the array before it is allocated. But that's not how the compiler will treat it. And of course, this can be determined at compile time, so it will never appear in the assembly code.