4
\$\begingroup\$

I'm a strtok_r() hater. I don't want to make a copy of my input string that it can destroy. After decades of struggle and strife I drafted a modern replacement that optimizes for the clarity of the caller. I call it tokstr, and it is written in C for callers in C. Example:

    tokstr_t ts = tokstr_string("this:is+-test");
    for (char *t; (t = tokstr_next(ts, "-:+")) != NULL; free(t))
            printf("\t\"%s\"\n", t);
    tokstr_last(&ts);

(will output "this", "is", and "test", as will this:)

    tokstr_t ts = tokstr_string("this:is+-test");
    for (char t[100]; tokstr_next_copy(ts, "-:+", t, sizeof t) > 0;)
            printf("\t\"%s\"\n", t);
    tokstr_last(&ts);

(and this:)

    tokstr_t ts = tokstr_string("this:is+-test");
    for (;;) {
            struct tokstr_reg t = tokstr_next_region(ts, "-:+");
            if (t.base == NULL)
                    break;
            printf("\t\"%*s\"\n", t.size, t.base);
    }
    tokstr_last(&ts);

For now I've simply added it to the repository where I needed it, but I hope eventually to publish it separately. I call your attention to the header file:

#ifndef __TOKSTR_H
#define __TOKSTR_H

// tokstr -- textual token iterator with some input independence
// 2022-01-29 [revised during code review, add regions]
// 2022-01-25 [initially released inside dnsdbq]

// tokstr_t -- opaque handle for one iterator
struct tokstr;
typedef struct tokstr *tokstr_t;

struct tokstr_reg {
        const char              *base;
        size_t                  size;
};

// tokstr_region -- create an iterator for a counted string
tokstr_t tokstr_region(struct tokstr_reg);

// tokstr_string -- create an iterator for a nul-terminated string
tokstr_t tokstr_string(const char *);

// tokstr_next -- return next token from an iterator (caller must free() this)
char *tokstr_next(tokstr_t, const char *);

// tokstr_next_copy -- copy next token from an iterator; return size, 0, or -1
ssize_t tokstr_next_copy(tokstr_t, const char *, char *, size_t);

// tokstr_next_region -- return region of next token
struct tokstr_reg tokstr_next_region(tokstr_t, const char *);

// tokstr_last -- destroy an iterator and release all of its internal resources
void tokstr_last(tokstr_t *);

#endif /*__TOKSTR_H*/

And here is the implementation:

// tokstr -- textual token iterator with some input independence
// 2022-01-29 [revised during code review, add regions]
// 2022-01-25 [initially released inside dnsdbq]

/* externals. */

#define _GNU_SOURCE

#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>

#include "tokstr.h"

/* private data types. */

enum tokstr_type { ts_buffer, ts_string };

struct tokstr_class {
        enum tokstr_type        type;
};

struct tokstr_region {
        struct tokstr_class     class;
        struct tokstr_reg       source;
};

struct tokstr_string {
        struct tokstr_class     class;
        const char              *source;
};

struct tokstr {
        union {
                struct tokstr_class     class;
                struct tokstr_region    region;
                struct tokstr_string    string;
        } data;
};

/* forward. */

static struct tokstr_reg next_region(struct tokstr_region *, const char *);
static struct tokstr_reg next_string(struct tokstr_string *, const char *);

/* public. */

// tokstr_buffer -- create an iterator for a counted string
tokstr_t
tokstr_region(struct tokstr_reg source) {
        tokstr_t ts = malloc(sizeof(struct tokstr_region));
        if (ts != NULL) {
                ts->data.region = (struct tokstr_region) {
                        .class = (struct tokstr_class) {
                                .type = ts_buffer,
                                },
                        .source = source,
                };
        }
        return ts;
}

// tokstr_string -- create an iterator for a nul-terminated string
tokstr_t
tokstr_string(const char *source) {
        tokstr_t ts = malloc(sizeof(struct tokstr_string));
        if (ts != NULL) {
                ts->data.string = (struct tokstr_string) {
                        .class = (struct tokstr_class) {
                                .type = ts_string,
                                },
                        .source = source,
                };
        }
        return ts;
}

// tokstr_next -- return next token from an iterator (caller must free() this)
char *
tokstr_next(tokstr_t ts, const char *delims) {
        struct tokstr_reg reg = tokstr_next_region(ts, delims);
        if (reg.base == NULL)
                return NULL;
        return strndup(reg.base, reg.size);
}

// tokstr_next_copy -- copy next token from an iterator; return size, 0, or -1
ssize_t
tokstr_next_copy(tokstr_t ts, const char *delims, char *buffer, size_t size) {
        struct tokstr_reg reg = tokstr_next_region(ts, delims);
        if (reg.base == NULL)
                return 0;
        if (reg.size >= size) {
                errno = EMSGSIZE;
                return -1;
        }
        memcpy(buffer, reg.base, reg.size);
        buffer[reg.size] = '\0';
        return (ssize_t) reg.size;
}

// tokstr_next_region -- return region of next token
struct tokstr_reg
tokstr_next_region(tokstr_t ts, const char *delims) {
        struct tokstr_reg reg = {};
        switch (ts->data.class.type) {
        case ts_buffer:
                reg = next_region(&ts->data.region, delims);
                break;
        case ts_string:
                reg = next_string(&ts->data.string, delims);
                break;
        default:
                abort();
        }
        assert((reg.base == NULL) == (reg.size == 0));
        return reg;
}

// tokstr_last -- destroy an iterator and release all of its internal resources
void
tokstr_last(tokstr_t *pts) {
        free(*pts);
        *pts = NULL;
}

/* private functions. */

// next_buffer -- implement tokstr_next for counted string iterators
static struct tokstr_reg
next_region(struct tokstr_region *reg, const char *delims) {
        if (reg->source.size != 0) {
                while (reg->source.size != 0 &&
                       strchr(delims, *reg->source.base) != 0)
                        reg->source.size--, reg->source.base++;
                const char *prev = reg->source.base;
                while (reg->source.size != 0 &&
                       strchr(delims, *reg->source.base) == 0)
                        reg->source.size--, reg->source.base++;
                size_t size = (size_t) (reg->source.base - prev);
                if (size != 0)
                        return (struct tokstr_reg) {prev, size};
        }
        return (struct tokstr_reg) {};
}

// next_string -- implement tokstr_next for nul-terminated string iterators
static struct tokstr_reg
next_string(struct tokstr_string *str, const char *delims) {
        int ch = *str->source;
        if (ch != '\0') {
                while (ch != '\0' && strchr(delims, ch) != NULL)
                        ch = *++str->source;
                const char *prev = str->source;
                while (ch != '\0' && strchr(delims, ch) == NULL)
                        ch = *++str->source;
                size_t size = (size_t) (str->source - prev);
                if (size != 0)
                        return (struct tokstr_reg) {prev, size};
        }
        return (struct tokstr_reg) {};
}

It is called from dnsdbq.c and pdns.c in the same repository. I won't reproduce those source code files here since they are large and merely reflect the example given at the outset (above).

I am very interested in feedback on the abstraction level, and on the hoped-for clarity of the caller compared to using strtok_r(), and on the quality of the implementation.

In response to an answer posted below, I thought to better document my goals:

I know that there's extra complexity in having two kinds of iterators, but since I know I will some day want three, I chose to depend upon that extra layer of indirection from day 1. So even if I were willing to require an extra scan of the input string by making the caller first call strlen(), that wouldn't future proof it against something coming later such as tokstr_wstring() or tokstr_utf8() or tokstr_stdio(). I apologize for not justifying this complexity in the comments. It's the kind of thing I learned by doing inet_ntop() and inet_pton() and res_ninit() wrong back in the day.

There's an unavoidable malloc() happening here for the opaque handle (tokstr_t), whose size the caller will not know. In Cron and BIND I fought hard against the heap because in 1990 malloc() and free() were terrible. However, even on the tiniest of 2020's modern processors, allocations which are freed quickly aren't much more expensive than alloca(). We can afford to err on the side of clarity, especially for the callers. If someone doesn't want tokstr because of its heap use, they're not going to like strtok_r() for the same reason. My challenge is: how can the caller be given maximum clarity?

Based on comments here I have revised the interface to include a new data type struct tokstr_reg, renaming tokstr_buffer() to tokstr_region(), and adding an output function tokstr_next_region() for callers who prefer a zero-copy work flow. I also added tokstr_next_copy() which has a copy (memcpy()) but not a heap allocation (strndup()).

The indentation, declaration, and expression styles are as close as possible to KNF, except where we departed from KNF at ISC. So, int and char and pointers are not used as a booleans, and are instead compared to something in order to create a first class boolean. GCC and CLang can be made to help with this in the Makefile:

-W -Wall -Wextra -Wcast-qual -Wpointer-arith -Wwrite-strings \
-Wmissing-prototypes  -Wbad-function-cast -Wnested-externs \
-Wunused -Wshadow -Wmissing-noreturn -Wswitch-enum -Wconversion
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$
  1. Unify.

    Just call strlen() to convert from null-terminated to counted string, so you only need one implementation.
    The reduction in code and complexity should easily pay for that one extra call.

    (Admittedly, if you actually implement the extra-sources you allude to in the edit, this will not apply to the new one, diminishing the benefit some.)

  2. Don't allocate needlessly.

    While hiding the context behind an opaque handle allows you to change the implementation without impacting users, that extra allocation is not free.

    (New ideas for radical extension might make this change impractical.)

  3. Minimize allocation.

    Currently, for every iteration you allocate the token on the stack, and then free it in the caller. While that allows the caller to keep hold of it at without having to duplicate it, most of the time most of the allocations will be needless additional work.

    Allow the caller to take ownership, but don't force it. If they don't, re-use if possible.

  4. The suffix _t is reserved under POSIX. Whether you should care...?

  5. value != NULL, value != 0, value != '\0', !!value and value all have the same truth value.

    Ditto value == NULL, value == 0, value == '\0', and !value.

    I suggest using the simplest which fits.

\$\endgroup\$
3
  • \$\begingroup\$ Deduplicator, thank you for your review. I think I should document my goals better but I can't do it in ~500 characters. Not sure how to proceed. \$\endgroup\$
    – Paul Vixie
    Jan 29, 2022 at 8:39
  • \$\begingroup\$ Deduplicator, I have extensively edited my question based on your review. Thanks again for your attention. \$\endgroup\$
    – Paul Vixie
    Jan 29, 2022 at 9:21
  • \$\begingroup\$ Deduplicator, after thinking about your comments, I saw an opportunity to add a zero copy output function, and also a string copy output function, in addition to the heap allocating output function. I'd appreciate any comments you can offer on these changes. Thanks again for giving your perspective on the initial proposal. \$\endgroup\$
    – Paul Vixie
    Jan 29, 2022 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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