1
\$\begingroup\$

The first time I used strtok, it felt, well, weird. But after a while, I became quite used to it. In a way it was simple. Soon after reading a bunch of Stack Overflow comments and posts about this function, I came to realize that this isn't what I should use in the long run.

Personally, my biggest problem with strtok was that it was a destructive function. So today I just wanted to make a version of it that non-destructive.

So the way this new version is going to be used, is just the same as strtok.

token = get_token
while token is valid
    (do something with the token)
    token = get_token

The only change I made (to make my job somewhat easier) is instead of a char * delimiter, I'm taking an int. So the function signature is now

char *tokenize(const char *__src, int delim);

Before looking at the source code, let me show you how much identical this function is in regard to the strtok function using a snippet.

char string[] =
      "The exec() functions return only if an error has occurred. The return "
      "value is - 1, and errno is set to indicate the error.";
char *token = tokenize(string, ' ');
while (token)
  {
    printf("'%s'\n", token);
    token = tokenize(NULL, ' ');
  }

This solution is made from an educational perspective, nothing more. I'm not claiming this to be a viable alternative to strtok.


To briefly explain how I've written this function

The function returns a malloc'd char * that contains the token. Instead of allocating just the amount of memory required to store the substring, it allocates 8 more bytes to store the index address from the source char * that will be used in the next iteration to look for the next token.

It also frees the previous malloc'd block upon each iteration. Yes, if you don't go through the whole string, you'll have a memory leak (or you'll have to add a weird call to free yourself with the correct address, - sizeof(char *) being the offset).

I'm using assert to handle the errors, as it's faster and simple enough for this situation, and most importantly gets the job done.


The source

char *tokenize(const char *__src, int delim)
{
  static const char *src;
  static char *token;
  const char *start_pos_loc;

  if (__src)
    {
      src = __src;
    }

  if (!token)
    {
      start_pos_loc = src;
    }
  else
    {
      memcpy(&start_pos_loc, token - sizeof(char *), sizeof(char *));
      free((void *)token - sizeof(char *));
    }

  size_t substring_length = 0;
  const char *ptr;

  for (ptr = start_pos_loc; *ptr != 0 && *ptr != delim; ptr++)
    {
      substring_length++;
    }

  if (!substring_length)
    {
      return NULL;
    }

  // Skipping the final delimiter.
  ptr++;

  token = malloc(substring_length + 1 + sizeof(char *));
  assert(token);

  memcpy(token, &ptr, sizeof(char *));
  token += sizeof(char *);
  memcpy(token, start_pos_loc, substring_length);

  token[substring_length] = 0;

  return token;
}

One of the things that I'm mostly looking forward to, is knowing if I'm using const correctly or not.

Apart from that, take the following main function for example:-

int main()
{
  char string[] = "Hello World! How is life now?";
  char *token = tokenize(string, ' ');
  while (token)
    {
      printf("'%s'\n", token);
      token = tokenize(NULL, ' ');
    }
  return 0;
}

After running it under valgrind, I'm getting this error:-

==42519== Conditional jump or move depends on uninitialised value(s)
==42519==    at 0x109287: tokenize (in /home/debdut/Documents/cpp/a.out)
==42519==    by 0x1093F9: main (in /home/debdut/Documents/cpp/a.out)

Any idea where might this be coming from?

Thank you : )

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

Your code is too complicated.

No wonder you try to simplify by using debugging-constructs for release error-detection.

  1. Don't try to shoehorn a third variable somewhere into the dynamic allocation. The awkwardness is unneeded. Especially as you only need two static pointers: the returned token, and the resume position.

  2. You have the choice: free()+malloc() or realloc()/free(). The former potentially wastes time.

char* tokenize(const char* restrict s, int c) {
    static const char *p
    static char *r;
    s = p = s ? s : p;
    assert(s);
    if (!*s) {
        free(r);
        r = 0;
        return 0;
    }
    while (*p && *p != c)
        ++p;
    r = realloc(r, p - s + 1);
    if (!r) {
        fprintf(stderr, "Could not allocate memory for a token.\n");
        abort();
    }
    memcpy(r, s, p - s);
    r[p - s] = 0;
    if (*p) ++p;
    return r;
}

That was done under the assumption that you really want tokenize() to manage the token. There are other arguably better designs:

  1. Simply handing it off to the caller and letting him free it when its time. Probably not significantly less efficient, often better as a copy is needed anyway.

  2. Simply return start- and end-pointer, and let the caller do whatever he wants. Simpler and more flexible, though often more cumbersome to use.

Possible alternative reentrant design:

typedef struct tokenize_context {
    const char *input;
    char *token;
} tokenize_context;

char* tokenize(tokenize_context* restrict p, int c) {
    assert(p && p->input);
    if (!*p->input) {
        free(p->token);
        p->token = 0;
        return 0;
    }
    const char* const begin = p->input;
    while (*p->input && *p->input != c)
        ++p->input;
    p->token = realloc(p->token, p->input - begin + 1);
    if (!p->token) {
        fprintf(stderr, "Could not allocate memory for a token.\n");
        abort();
    }
    memcpy(p->token, begin, p->input - begin);
    p->token[p->input - begin] = 0;
    if (*p->input) ++p->input;
    return p->token;
}

Used like:

tokenize_context ctx{"The quick brown fox jumps over the lazy dog."};
while (tokenize(&ctx, ' ')) {
    // Use ctx.token, or return-value from the above call
    // May steel ctx.token by setting to 0
    // May free ctx.token for early stop
}
\$\endgroup\$
0
\$\begingroup\$
  token = malloc(substring_length + 1 + sizeof(char *));
  assert(token);

This assert() is wrong. You're claiming that malloc() can't return a null pointer - but it can, and does.

You'll need to examine token and return a failure indicator if it's null, before the assert().

\$\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.