3

I am writing a program that tokenizes a text and transforms it based on the tokenization. The tokens are represented by a struct:

struct token {
    enum token_type type;
    size_t length;        /* as returned by strlen(token.text); */
    char text[];          /* 0-terminated */
};

The tokenizer provides an iterator interface that allocates and yields the next token when called. The caller of this function then processes the token, passes it to several functions (some of which might store the token on their own) and might store it somewhere.

At a certain point of time, token processing is finished and all tokens can be freed.

How should I go on about tracing the tokens' allocations?

I had three ideas for this:

  • Each token contains a pointer to the previous token; at the end, I can simply traverse the linked list to free all tokens. This gets complicated once I create tokens in more than one place.

  • Each token contains a reference counter. This is complicated because I need to pay close attention to where I keep a reference to a token.

  • Each function duplicates tokens instead of keeping references to them. If a function gets passed a token as an argument, it must not keep them. This might lead to a lot of unneccessary memory allocation.

It would be nice to have some information from more experienced programmers.

4
  • I'm pretty sure smart pointers should do the trick for you with the least amount of hassle, you don't have to worry about the reference count once its hiding inside that. Alternatively, you can register all your tokens in some global list and just traverse it to deallocate them all
    – Leeor
    Sep 24, 2013 at 7:44
  • @Leenor smart pointers? What's that?
    – fuz
    Sep 24, 2013 at 7:49
  • 1
    I don't think you'll find a clean implementation of smart pointers in C.
    – tangrs
    Sep 24, 2013 at 7:50
  • Hmm. Never though of that, I guess it would be difficult without destructors. I was somehow assuming that c gurus came up with something :), still - reference counting should work
    – Leeor
    Sep 24, 2013 at 8:10

3 Answers 3

2

Since you say that at some point in time all tokens need to be freed at the same time, you can go with a memory pool. Write a token allocator that will malloc tokens and store the allocated pointer in some array, linked list or however you want to solve it. When you're done with all the processing, call a function that will free all the tokens at the same time.

Something like this (not tested, but you should get the idea):

struct token {
    struct token *token_next;
    enum token_type type;
    size_t length;
    char *text;
};

struct token_pool {
    struct token *token_list;
};

struct token *
token_alloc(struct token_pool *pool, size_t len, enum token_type type)
{
    struct token *t;

    if ((t = malloc(sizeof(*t) + len)) == NULL)
        return NULL;
    t->length = len;
    t->text = (char *)(t + 1);
    t->type = type;
    t->token_next = pool->token_list;
    pool->token_list = t;

    return t;
}

void
token_free_pool(struct token_pool *pool)
{
     struct token *t;

     while ((t = pool->token_list) != NULL) {
         pool->token_list = t->token_next;
         free(t);
     }
}

The advanced level here is to allocate the memory in larger slabs so that you don't need to call malloc that many times, but since you're going with dynamic sizes it's probably just overkill.

This is something that's used by apache with their apr_pool API. Many of the things that are allocated in apache have a very specific life time (per-server or per-call) so it's quite easy and efficient to avoid leaks and optimize allocations and freeing.

1

It depends a bit on the life span of the tokens and how much extra memory you have. Things that are doing something distinctly different with the token (creating a new string for example, or storing it for later) should probably create a copy.

For the rest I'd go with the reference counter -- but create a function (or macro) that creates the reference and updates the counter (and a counterpart that releases the reference and decrements the counter).

Then it's easier to find bad references as any time you keep a reference you must use the function -- if you don't it's unsafe. You could even put debugging logic in there to check when a reference was / created freed and have some way of tracking if a reference is safe. In debug mode you could implement reference generation as a copy to allow you to add the tracking information.

0

Maybe simple master list is good enough.

When you allocate token, add token pointer to master list. When you are done processing, go through the list and deallocate everything.

Edit:

This could be achieved by having a Tokenizer object (a struct), which has a bunch of functions, that manage the token life time automatically.

typedef struct {
    /* list for tokens */
} Tokenizer;

void Tokenizer_Init(Tokenizer * this); // Must be called first
void Tokenizer_DeInit(Tokenizer * this); // Must be called last
void Tokenizer_DoStuff(Tokenizer * this);
6
  • Where should I store a pointer to the master list? I dislike having global variables as they make it difficult to turn the program into a library.
    – fuz
    Sep 24, 2013 at 8:40
  • @FUZxxl Not exatly sure what your program structure is, but I would probably pass the list as a pointer argument to the function/object that creates the tokens.
    – user694733
    Sep 24, 2013 at 8:56
  • The problem (as stated above) is, that there are multiple functions that could create tokens.
    – fuz
    Sep 24, 2013 at 9:04
  • @FUZxxl Then list would have to be passed to each function when calling, if using this approach.
    – user694733
    Sep 24, 2013 at 9:10
  • I don't see why having a library precludes global memory. If all your functions are within that library then that would be good encapsulation. Memory management is, by and large, a global thing! If you need to have separate instances of a bunch of allocated memory just pass back a handle (Like HeapAlloc).
    – noelicus
    Sep 24, 2013 at 9:27

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.