C program that splits the string based on a character

Question

I tried and made a program using my beginner knowledge of C to split a string into multiple sub strings. I just wondered how languages like Python and Javascript implemented the split() function. Thus, I gave it a try. It works and gives the desired output. Since I'm a beginner, I'd be really happy if someone reviewed my code and pointed out the errors.

I've given the code below. I guess there might me some memory issues. I am not quite sure however. What could I have done to make the code more efficient? What would be a better approach for this specific task ?

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

typedef struct fragments {
    char **words;
    size_t length;
}fragments;

char *slice(char *text, int start, int end);
fragments *split(char *text, char seperator);

int main(void) 
{
    char *text = "This is Stack Exchange";
    fragments *array  = split(text, ' ');

    for (int i = 0; i < array->length; i++)
    {
        printf("%s\n", array->words[i]);
    }

    return 0;
}

char *slice(char *text, int start, int end)
{
    // allocate memory 
    // loop from l_idx till c_idx
    // copy chars
    char *word = malloc(end - start + 1);     // 1 for '\0' 
    for (int i = start, j = 0; i < end; i++, j++)
        word[j] = text[i];
        
    int last_idx = end - start;
    word[last_idx] = '\0';

    return word;
}

fragments *split(char *text, char seperator)
{
    // loop through text
        // if seperator found
            // get index
            // slice from last index to curr index
            // append word to array

    int textlen = strlen(text);
    
    // find total_words
    size_t total_words = 0;
    for (int i = 0; i < textlen; i++) 
        if (text[i] == seperator)
            total_words++;
    total_words++;      // final word after seperator


    // declare array of words
    fragments *arr = malloc(sizeof(fragments));
    arr->words = malloc(total_words * sizeof(char*));
    arr->length = total_words;
    
    // Insert words
    int last_idx = 0, wordlen = 0, idx = -1;
    for (int i = 0; i < textlen; i++)
    {
        if (text[i] == seperator)
        {
            idx++; 
            char *word = slice(text, last_idx, i);
            arr->words[idx] = malloc(strlen(word) + 1);
            strcpy(arr->words[idx], word);
            last_idx = i + 1;
        }
    }
    // Insert last word
    char *last_word = slice(text, last_idx, textlen);
    arr->words[idx + 1] = malloc(strlen(last_word) + 1);
    strcpy(arr->words[idx + 1], last_word);

    return arr;
}

Answer 1

There are a lot of things that make this a difficult task in C.

I don't think your approach is totally broken, but there are some obvious improvements that can be made, and some points that you need to ponder.

First improvement - split the interface from the implementation. Put the structure definition and the declaration of the split function into a header file.

Second improvement - think about what you'd do if malloc failed...

Third improvement - don't leak memory quite so obviously. slice returned a suitable pointer to a word, so you don't need to malloc more space and copy the data.

Fourth improvement - use something like memcpy in slice rather than copy characters in a loop.

Fifth improvement - usual guidance is that you should try to make mallocing structures more robust using something like fragments *arr = malloc(sizeof(*arr));

Sixth improvement - make slice static.

To think about: you've malloced memory, how should that memory be freed? Do you document that the user should do so? Do you provide a convenience function like the one below?

void free_fragments(fragments *arr) {
  int i;
  for (i = 0; i < arr->length; i++) {
   free(arr->words[i]);
  }
  free(arr);
}

Answer 2

Use Efficient Data Structures

The current design uses pointers to pointers to pointers to null-terminated deep copies of strings. This is an extremely inefficient and error-prone data layout. It requires making a full copy of all data in the original string, with separate heap allocations that must each be manually freed, the resulting words have poor locality of reference (so they are likely to generate cache misses), and the resulting data must be triple-dereferenced to access it.

If—and this is a big if—you can guarantee that the list of words will not be used after the original string is destroyed, you can use a much more efficient data structure: views of the substrings. Simply store a non-owning reference to the the start of the substring, and its length. For example,

/* An non-owning view of a substring.  This is a reference within some other
 * string, and MUST NOT OUTLIVE the string it references.
 */
typedef struct substring {
  const char* sv; // Pointer to the substring.
  size_t length;  // Length of the substting.
} substring;

The const qualifier on the substring pointer is partly because it’s a non-owning alias, but mainly so I can take a substring of a constant string without the compiler complaining.

In a language like Rust, the lifetime constraint would be enforced by the borrow checker, but in C, that’s your responsibility to keep straight.

Now, you want a list of these substrings. The most efficient data structure to use for this is a vector: a dynamic array that expands as needed.

typedef struct substring_vector {
  substring* data;  // Pointer to a contiguous array of size allocated, OR
                    // to NULL if zero elements are allocated..
  size_t length;    // The numbeer of elements currently used.
  size_t allocated; // The number of elements currently allocated.
} substring_vector;

There is now only one array of words, which is stored contiguously in memory, which all reference the same contiguous string, with no unnecessary copying of data, and needs to be dereferenced twice instead of three times. Freeing or expanding it is a single heap operation, not a loop over each word in the array.

Note that almost all languages newer than C have generic versions of these data structures in their standard libraries. In C++, for example, this is std::vector<std::string_view>. Since C does not, I’m going to re-invent a crude wheel here.

You Can Return Structures from Functions.

You don’t need to return pointers to heap-allocated object, although you can. If your structure is a struct fragment, you could write something like struct fragment words = split( string, delim );. You could also have the caller allocate the result object and pass in its address to be filled in.

Check for Errors

Actually, this program doesn’t receive any possible error values other than out-of-memory and output errors. I’m also going to ignore I/O errors for this purpose, since they’re unrelated to the code you were asking about, and because there’s no meaningful handling we can do here. (If we can’t print, we can’t very well print an error message.)

on most modern systems, virtual memory means that the system would thrash to a halt long before we ever got an out-of-memory error, but it’s a good idea to handle those anyway. I also go ahead and check that data pointers are valid. In this MWE, I check with assert(). This is mainly so I get more useful runtime errors than SIGSEGV, which tell me what went wrong where.

Manage Your Memory

You acknowledged that you need to do this, and you were right! You can make this easier if you:

Write Functions to Manipulate Your Data Structures

The very minimal API we need to implement and test split() is: initialize a substring_vector, clean it up, add a substring to it, and print out the contents.

Given the structures we defined above, the interfaces of these would be:

void substring_vector_init( substring_vector* const v );
void substring_vector_cleanup( substring_vector* const v );
substring* substring_vector_insert( substring_vector* const v,
                                    const substring sv );
void substring_vector_print( const substring_vector* const v );

Writing the function parameters (and as many other values as possible) as static single assignments protects us from bugs where a variable is used before it is initialized, or contains something other than we thought. Hence declaring all of them const.

A substring is passed by value because it is small enough to do so efficiently, and a substring_vector is always passed by address.

Note that, if you really do need to make deep copies of the data, this lets you change your data structure without rewriting the client code. Your code will be much more maintainable this way.

Write Contracts for Your Functions

This is particularly important if you are asking the user of your library to manage the memory properly. This is impossible if you do not tell them what they need to do. A comment block at the start of the function should also succinctly explain what each parameter does, what the return value is, how it handles any edge cases that are not obvious, and what side-effects the function has.

Here is the contract for my version:

substring_vector split( const char* const s, const char c )
/* This creates a substring_vector of substrings of s, delimited by c.
 * There are no empty words in the substring_vector.  Leading and
 * consecutive delimiters are ignored.  The returned object is owned by the
 * caller and MUST BE FREED with substring_vector_cleanup().
 */

A Finite State Machine Would be Suitable

The split() function traverses the string from front to back, tracking the length of the current word. If it reaches a delimiter or the end of the string, and there was any word before it, the function inserts that word into the vector of substrings.

The conventional way to write this in C would be with a loop. I, personally, like a more quasi-functional style, with a lot of static single assignments and tail-recursive calls. They are particularly well-suited to implementing finite state machines. So I’ll give an example of that.

The state machine used internally to implement the algorithm needs two pieces of state that are not part of the interface of split(): a count of the length of the current word, and a substring_vector to add words to. Therefore, it will be defined as a helper function, static since it is not intended to be used anywhere else in the program, and split() will set up its parameters and hand control over to it.

substring_vector split( const char* const s, const char c )
/* This creates a substring_vector of substrings of s, delimited by c.
 * There are no empty words in the substring_vector.  Leading and
 * consecutive delimiters are ignored.  The returned object is owned by the
 * caller and MUST BE FREED with substring_vector_cleanup().
 */
{
  substring_vector v;
  substring_vector_init(&v);
  // v is not cleaned up here because the helper takes ownership.
  return split_helper( s, c, 0, &v );
}

At this point, I’ll mention an important extension, modern C compilers are generally good at recognizing when to optimize tail calls (unless you tell them not to optimize at all), but clang (and its fork ICX) has an extension that makes this explicit. So nearly all of my programs have the following boilerplate:

#if __clang__
#  define MUSTTAIL __attribute__((musttail))
#else
#  define MUSTTAIL /**/
#endif

This lets me write a tail-recursive call as MUSTTAIL return, which expands to __attribute__((musttail)) return on compilers that support it, but a bare return on those that do not.

With that in place, one possible implementation of split_helper() would be this.

static substring_vector split_helper( const char* const s,
                                      const char c,
                                      size_t substring_len,
                                      substring_vector* restrict const vp
                                    )
/* Internal tail-recursive helper function.
 */
{
  if (!*s) { // We are at the end of the input string.
    if (substring_len) { // There is one word left to add to the vector..
      const substring word = { s - substring_len, substring_len };
      substring_vector_insert( vp, word );
    }
    return *vp;
  } else if (*s == c) { // We are at the separator.
    if (substring_len) { // This is not an empty word.
      const substring word = { s - substring_len, substring_len };
      substring_vector_insert( vp, word );
    }
    MUSTTAIL return split_helper( s+1, c, 0, vp );
  } else { // We are in the middle of a word.
    MUSTTAIL return split_helper( s+1, c, substring_len+1, vp );
  }
}

Most C code you’ll run into doesn’t look like this, and I usually get a comment or two saying this coding style isn’t very C-like. However, C can handle it just fine. It’s just as efficient as a while or for loop. In my opinion, it has several big advantages. One is, the program state can only be updated all at once, once per branch, and the compiler will warn me if there is any branch where I forgot to update it. It is much harder to verify whether each branch within my while loop has updated all the local variables it should, and only those it should, once and only once.

Turning this into an equivalent while loop (and comparing the code the compiler generates for both) would be a nice exercise, though.

Is a One-Character Delimiter Sufficient?

For UTF-8 strings, certainly not! A single Unicode code-point or grapheme can be multiple char long today. I don’t implement this, but you might try modifying this function to accept multi-byte delimiters.

You Had a Good Idea to do Two Passes

You’ll notice I did only one pass through the string—but that one pass might need to resize the substring_vector multiple times, copying the array of substrings each time. The way you did it, making a pass to count the words first and then allocating that many elements, has a lot to be said for it.

The main reason I left that out was that the code I wrote to skip zero-length words (such as between two consecutive spaces) was much simpler for a one-pass approach.

If you want to add that capability to my approach, you would want to extend the vector API with a substring_vector_reserve() function that reserves the amount of memory requested. It would internally call realloc(). Or use a language that provides this functionality in its standard library.

Putting it All Together

Here is a MWE with test driver as a single flat file. In a real-world situation, you would factor it out into modules, with separate source and header files.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // For memcpy()

/* An non-owning view of a substring.  This is a reference within some other
 * string, and MUST NOT OUTLIVE the string it references.
 */
typedef struct substring {
  const char* sv; // Pointer to the substring.
  size_t length;  // Length of the substting.
} substring;

/* A vector of substrings. This should be initialized and destroyed by the
 * functions below.
 */
typedef struct substring_vector {
  substring* data;  // Pointer to a contiguous array of size allocated, OR
                    // to NULL if zero elements are allocated..
  size_t length;    // The numbeer of elements currently used.
  size_t allocated; // The number of elements currently allocated.
} substring_vector;

void substring_vector_init( substring_vector* const v )
/* Initializes an empty substring_vector.
 */
{
  assert(v);
  v->data = NULL;
  v->length = 0;
  v->allocated = 0;
}

void substring_vector_cleanup( const substring_vector* const v )
/* Frees the memory owned by a substring_vector The substring-vector
 * BECOMES INVALID and must not be re-used.  Must be called once and only
 * once on any non-empty vector.
 */
{
  assert(v);
  free(v->data);
}

substring* substring_vector_insert( substring_vector* const v,
                                    const substring sv )
/* Inserts the given substring at the end of the substring_vector, resizing
 * the latter as necessary.  Returns a pointer to the inserted element.
 */
{
  assert(v);
  if ( !v->allocated ) {
    assert( !v->data && !v->length );
    static const size_t initial_alloc = 256U;
    v->data = calloc( initial_alloc, sizeof(substring) );
    assert(v->data);
    v->allocated = initial_alloc;
  }
  
  if ( v->allocated <= v->length ) {
    // The current size of the memory block.
    const size_t old_size = v->allocated * sizeof(v->data[0]);
    // Enlarge the memory block by 50%.
    const size_t new_size = old_size + (old_size+1)/2;
    // Bheck for arithmetic overflow on the buffer size.
    assert( new_size > old_size );
    v->allocated = new_size;
    v->data = realloc( v->data, new_size );
    assert(v->data);
  }
  // At this point, v->data is large enough to hold the new element.

  substring* const new_element = &v->data[v->length];
  v->length += 1;
  memcpy( new_element, &sv, sizeof(sv) );
  
  return new_element;
}

void substring_vector_print( const substring_vector* const v )
{
  assert(v);
  for ( size_t i = 0; i < v->length; ++i ) {
    assert(v->data[i].sv);
    fwrite( v->data[i].sv, 1, v->data[i].length, stdout );
    fputs( "\n", stdout );
  }
  
  fputs( "\n", stdout );
}

/* Interfaces to make a deep copy of a substring vector, etc., would go here,
 * but they are not needed for this project.
 */


#if __clang__
#  define MUSTTAIL __attribute__((musttail))
#else
#  define MUSTTAIL /**/
#endif

static substring_vector split_helper( const char* const s,
                                      const char c,
                                      size_t substring_len,
                                      substring_vector* restrict const vp
                                    )
/* Internal tail-recursive helper function.
 */
{
  if (!*s) { // We are at the end of the input string.
    if (substring_len) { // There is one word left to add to the vector..
      const substring word = { s - substring_len, substring_len };
      substring_vector_insert( vp, word );
    }
    return *vp;
  } else if (*s == c) { // We are at the separator.
    if (substring_len) { // This is not an empty word.
      const substring word = { s - substring_len, substring_len };
      substring_vector_insert( vp, word );
    }
    MUSTTAIL return split_helper( s+1, c, 0, vp );
  } else { // We are in the middle of a word.
    MUSTTAIL return split_helper( s+1, c, substring_len+1, vp );
  }
}

substring_vector split( const char* const s, const char c )
/* This creates a substring_vector of substrings of s, delimited by c.
 * There are no empty words in the substring_vector.  Leading and
 * consecutive delimiters are ignored.  The returned object is owned by the
 * caller and MUST BE FREED with substring_vector_cleanup().
 */
{
  assert(s);
  substring_vector v;
  substring_vector_init(&v);
  // v is not cleaned up here because the helper takes ownership.
  return split_helper( s, c, 0, &v );
}


// A very minimal test driver, not nearly sufficient to cover all cases.
#include <stdlib.h>

int main(void)
{
  const substring_vector words1 =
    split( "hello, world, hola, mundo, bonjour, le monde", ' ' );
   
  substring_vector_print(&words1);
  assert( words1.length == 7 );

  substring_vector_cleanup(&words1); // words1 is now invalid to use.
  
  const substring_vector words2 = split( "|abc|||def|123|xyz|ijk|", '|' );

  substring_vector_print(&words2);
  assert( words2.length == 5 );
  
  /* All memory will be freed when the program terminates anyway, but if
   * this function were not main(), you would need to do this:
   */
  substring_vector_cleanup(&words2);

  return EXIT_SUCCESS;
}

For reference, Clang 14.0.0 with the flags -std=c17 -march=x86-64-v3 -Os inlines the tail-recursive helper function and compiles it to:

.LBB4_3: # =>This Inner Loop Header: Depth=1
  cmp al, bpl
  jne .LBB4_10
  test rdx, rdx
  je .LBB4_6
  mov rsi, rbx
  sub rsi, rdx
  mov rdi, r15
  call substring_vector_insert
.LBB4_6: # in Loop: Header=BB4_3 Depth=1
  xor edx, edx
  jmp .LBB4_11
.LBB4_10: # in Loop: Header=BB4_3 Depth=1
  inc rdx
.LBB4_11: # in Loop: Header=BB4_3 Depth=1
  mov al, byte ptr [rbx + 1]
  inc rbx
  test al, al
  jne .LBB4_3
  test rdx, rdx
  je .LBB4_9
  sub rbx, rdx
  mov rdi, rsp
  mov rsi, rbx
  call substring_vector_insert
.LBB4_9:

As you can see, there’s no penalty to code size or to speed.

Answer 3

int vs. size_t

Interesting that OP used int textlen and size_t total_words = 0; when size_t makes sense for both.

size_t is the type to used for array sizing, indexing and string lengths - being not too narrow nor too wide. Take care as it is an unsigned type.

Consider 2 passes

Perhaps one pass down the string to find word count and a 2nd to populate. Could use a common function:

// Untested, illustrative code

static size_t split_parse(char **word, const char *s, char sep) {
  size_t word_count = 0;
  while (*s) {
    while (*s == sep)
      s++;
    if (*s == 0) {
      break;
    }
    const char *begin = s;
    while (*s != sep && *s != '\0') {
      s++;
    }
    if (word) {
      size_t length = (size_t) (s - begin);
      word[word_count] = malloc(length + 1u);
      if (word[word_count] == NULL) { // Out of memory
        return word_count;
      }
      memcpy(word[word_count], begin, length);
      word[word_count][length] = '\0';
    }
    word_count++;
  }
  return word_count;
}

char** split_string(const char *s, char sep) {
  size_t count = split_parse(NULL, s, sep);
  char **words = malloc(sizeof words[0] * (count + 1));
  if (words) {
    size_t count2 = split_parse(words, s, sep);
    if (count2 != count) {
      // TBD - ran out of memory on 2nd pass
      // Perhaps free all and return NULL.
      // For now, let us return a shorten list
    }
    words[count2] = NULL;
  }
  return words;
}

Mindful of sep == 0

Review code that it behaves when the separator is a null character. That might be a pathological case, yet code should not exhibit undefined behavior nor an infinite loop if it was.

I think OP's code is OK on the matter.

Use const

As the source string should remain unchanged, use const char *text. This also allows the split function to be call on const strings.