10
\$\begingroup\$

I'm new to the C programming language and I just made a basic version of Python's split() function using C.

Note: A major functionality I chose not to implement is the usage of optional delimiters.

Official documentation of split() can be found here.

#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define DEFAULT_BUFSIZE 512


static inline int isDelimiter(char s) {
    return s == ' ' || s == '\t';
}


// Splits a string with elements delimited by spaces or tabs into an array
// of strings. It works very similarly to Python's split() function.
int parser(char *source, char ***destination) {
    // The auxiliar variable `aux` will save the array contents, rather than
    // using *destination. Its elements length is initially DEFAULT_BUFSIZE
    // so that realloc() doesn't have to be called everytime a character
    // is copied. The memory used by each element will be reduced to the
    // minimum possible afterwards.
    // The most efficient solution would actually be having two buffer
    // variables: one for the element size and another for the array itself.
    // But currently this isn't neccessary.
    size_t bufsize = DEFAULT_BUFSIZE;
    char **aux = malloc(sizeof(char *));

    // The source string is iterated and its contents are copied to the aux
    // array, so we need 3 counters:
    //     * `len` is the array length
    //     * `iArr` is the array's current element index.
    //     * `iStr` is the source array's index.
    size_t len = 1;
    int iStr = 0;
    int iArr = 0;
    // If there's more than 1 delimiter in a row, a new element shouldn't be
    // created. This is why `newEl` has to be created. It acts as a boolean
    // that indicates when a new element should start.
    int newEl = TRUE;
    // The first element of the array is created. The rest will be allocated
    // inside the loop.
    aux[0] = malloc(bufsize * sizeof(char));
    while (source[iStr] != '\0') {
        if (isDelimiter(source[iStr]) && !newEl) {
            // The used memory is reduced to what's actually being used.
            aux[len-1] = realloc(aux[len-1], (iArr+1) * sizeof(char));
            // The current element ends.
            aux[len-1][iArr] = '\0';
            iArr = 0;
            ++len;
            // Don't come back here until a character other than a delimiter
            // is found.
            newEl = TRUE;

            // The new element is allocated.
            aux = realloc(aux, len * sizeof(char *));
            aux[len-1] = malloc(bufsize * sizeof(char));
        } else if (!isDelimiter(source[iStr])) {
            // The source character is copied to the destination.
            aux[len-1][iArr] = source[iStr];
            ++iArr;
            // From now on, a new element can be started.
            newEl = FALSE;

            // The buffer is enlargened if neccessary.
            if (iArr >= bufsize) {
                bufsize += DEFAULT_BUFSIZE;
                aux[len-1] = realloc(aux[len-1], bufsize * sizeof(char *));
            }
        }
        ++iStr;
    }

    // The last element's size has to be reduced outside of the loop, and a
    // '\0' is added to finish it. If newEl is true, it means the last element
    // is filled with delimiters and it shouldn't be included in the array.
    if (newEl) {
        --len;
    } else {
        aux[len-1] = realloc(aux[len-1], (iArr+1) * sizeof(char));
        aux[len-1][iArr] = '\0';
    }
    // Finally, the last element is NULL.
    aux[len] = NULL;

    // Saving the destination variable and returning its length.
    *destination = aux;
    return len;
}

I also made a small test file:

#include <stdio.h>  // fgets()...
#include <string.h>  // strlen()
#include <stdlib.h>  // size_t, atoi...
#include "parser.h"
#define MAX 1024


int main() {
    char str[MAX];
    printf("Introduce numbers delimited by spaces or tabs: ");
    fgets(str, MAX, stdin);
    // Removing the '\n' from fgets()
    str[strlen(str)-1] = '\0';

    char **nums;
    size_t len = parser(str, &nums);
    if (len == 0) {
        fprintf(stderr, "No input.\n");
        exit(1);
    }

    int sum = 0;
    for (int i = 0; i < len; ++i)
        sum += atoi(nums[i]);

    printf("Sum: %d\n", sum);

    free(nums);
    return 0;
}

Also, here's a GodBolt snippet.

\$\endgroup\$
13
\$\begingroup\$

Minor stuff ...

Allocate to the object, not type

The below is easier to maintain.

// char **aux = malloc(sizeof(char *))
char **aux = malloc(sizeof *aux)

// aux[0] = malloc(bufsize * sizeof(char));
aux[0] = malloc(sizeof *(aux[0]) * bufsize);

Avoid Exploit

Below code is undefined behavior is the first character of user input is the null character. It is also incorrect if a '\n' was never read. (long line, or EOF before a '\n'.)

// Removing the '\n' from fgets()
str[strlen(str)-1] = '\0';

A better approach is

str[strcspn(str, "\n")] = '\0';

Avoid mixing types

I recommend to use the same type.

size_t len = ...
...
// for (int i = 0; i < len; ++i)
for (size_t i = 0; i < len; ++i)
\$\endgroup\$
  • \$\begingroup\$ Thanks for the tips! The only one I don't understand that much is the first. Why would that be better than what I did? It seems more confusing to me. \$\endgroup\$ – Dewamuval Nov 19 at 21:49
  • \$\begingroup\$ @Dewamuval Which code is certainly correct pointer = malloc(sizeof *pointer * n) vs. pointer = malloc(sizeof(long) * n)? \$\endgroup\$ – chux - Reinstate Monica Nov 19 at 22:20
  • 1
    \$\begingroup\$ Yeah the first one makes more sense, thanks. \$\endgroup\$ – Dewamuval Nov 20 at 13:23
10
\$\begingroup\$

So, you basically rewrote the strtok function in ANSI C. The difference is that you allocate memory for each substring while TOK modifies the original string by adding \0 characters in the place of delimiters. This means that you keep allocating more and more memory, while you can just make a copy of the whole string and use strtok to modify the copy you just made, keeping the original string untouched. When you write more advanced C code, try to avoid the need to allocate more memory. You know the amount of memory required is just the length of the string so make a copy of it. Then replace the tokens you want to replace with the \0 character, walking through the string just once and returning pointers to each start of a substring. And decide if "\0" is a string that you want to return or not... Nice attempt, but it can be improved by not using realloc() in the first place... That method will slow down this function considerably...

\$\endgroup\$
  • 2
    \$\begingroup\$ It's closer to Python's split() than to C's strtok(). Because if one of the elements had more than 1 space between them, replacing them with '\0' wouldn't be a good idea. \$\endgroup\$ – Dewamuval Nov 17 at 18:12
  • 1
    \$\begingroup\$ But after finding the first delimiter, you can just keep skipping characters in the string until you find a non-delimiter. The next string would start at that location and continue until the next delimiter. But all I'm saying is that you keep reallocating memory instead of using the memory that you've already allocated. There's a good chance that your code will leak memory, as you do free nums in your example, but you're not freeing all the strings allocated inside nums. I haven't tested your code but it seems leaky at first glance. \$\endgroup\$ – Wim ten Brink Nov 17 at 18:40
  • 1
    \$\begingroup\$ Hmmm that makes more sense yeah. Also, I didn't realize the free(nums), thanks for pointing it out. \$\endgroup\$ – Dewamuval Nov 17 at 18:48
3
\$\begingroup\$

Your usage of realloc is wrong:

aux = realloc(aux, len * sizeof(char *));

The trouble is that if realloc() fails (i.e. it can not find a bigger block) it does not release aux but returns NULL. So the correct usage is:

char** tmp = realloc(aux, len * sizeof(char *));
if (tmp == NULL) {
    /* SOME ERROR HANDLING */
    // free(aux);
    exit(0); // or something approipriate
}
aux = tmp; // Now we have handled errors we can assign to aux.
\$\endgroup\$
  • \$\begingroup\$ Yes, I should take care of errors with malloc and realloc. Thanks! \$\endgroup\$ – Dewamuval Nov 19 at 21:50
2
\$\begingroup\$

Major issue

You allocate memory that can take a single pointer for aux, then start accessing off the end of it with aux[len-1].

These sort of issues create exploitable security vulnerabilities.

For an array of pointers I would have expected to see use of calloc().

Try re-running using something like Clang's address sanitizer (for example, with cc split.c -fsanitize=undefined,address -o split).

\$\endgroup\$
  • \$\begingroup\$ I didn't even know about calloc! And clang's addess sanitizer sounds really helpful too, thanks. \$\endgroup\$ – Dewamuval Nov 19 at 21:51

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.