3

我正在编写一个对文本进行标记并基于标记化对其进行转换的程序。标记由结构表示：

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

标记器提供了一个迭代器接口，该接口在调用时分配并产生下一个标记。然后，该函数的调用者处理该令牌，将其传递给几个函数（其中一些可能自行存储该令牌）并可能将其存储在某处。

在某个时间点，令牌处理完成并且可以释放所有令牌。

我应该如何继续跟踪代币的分配？

我对此有三个想法：

  • 每个令牌都包含一个指向前一个令牌的指针；最后，我可以简单地遍历链表来释放所有令牌。一旦我在多个地方创建令牌，这就会变得复杂。

  • 每个令牌都包含一个引用计数器。这很复杂，因为我需要密切注意我保留对令牌的引用的位置。

  • 每个函数都复制标记而不是保留对它们的引用。如果一个函数作为参数传递了一个标记，它不能保留它们。这可能会导致大量不必要的内存分配。

如果能从更有经验的程序员那里得到一些信息，那就太好了。

4

3 回答 3

2

由于您说在某个时间点需要同时释放所有令牌，因此您可以使用内存池。编写一个令牌分配器，该分配器将malloc令牌并将分配的指针存储在某个数组、链表或任何您想解决的问题中。完成所有处理后，调用将同时释放所有令牌的函数。

像这样的东西（未经测试，但你应该明白）：

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);
     }
}

这里的高级级别是在更大的平板中分配内存，这样您就不需要多次调用 malloc ，但是由于您使用的是动态大小，所以它可能只是矫枉过正。

这是 apache 与他们的 apr_pool API 一起使用的东西。在 apache 中分配的许多东西都有一个非常特定的生命周期（每个服务器或每个调用），因此避免泄漏和优化分配和释放非常容易和有效。

于 2013-09-24T09:32:59.887 回答
1

这在一定程度上取决于令牌的使用寿命以及您拥有多少额外内存。与令牌做一些明显不同的事情（例如创建一个新字符串，或将其存储以供以后使用）可能应该创建一个副本。

对于其余部分，我将使用引用计数器——但创建一个函数（或宏）来创建引用并更新计数器（以及释放引用并减少计数器的对应项）。

然后更容易找到错误的引用，因为任何时候保留引用都必须使用该函数——如果不这样做是不安全的。您甚至可以在其中放置调试逻辑以检查何时释放/创建引用，并通过某种方式跟踪引用是否安全。在调试模式下，您可以将参考生成实现为副本，以允许您添加跟踪信息。

于 2013-09-24T07:49:52.723 回答
0

也许简单的主列表就足够了。

分配令牌时，将令牌指针添加到主列表。完成处理后，浏览列表并取消分配所有内容。

编辑：

这可以通过拥有一个Tokenizer对象（一个结构）来实现，该对象具有一堆函数，可以自动管理令牌的生命周期。

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);
于 2013-09-24T08:34:43.740 回答