c-在编译时连接一个链表

Question

考虑一个C结构，它表示单链表中的一个条目。它包含一个指向某些任意数据的指针、该数据的大小以及查找下一个条目的方法

typedef struct{
  unsigned char *data
  unsigned char dataSize
  unsigned char nextEntry
} Entry;

接下来，考虑以下条目集合及其表示的数据：

unsigned char dataA[3];
unsigned char dataB[16];
unsigned char dataC[17];
Entry entryA = {dataA, sizeof(dataA), 3}; //It's important for "3" to match up with the index of entryB once it's put into MasterList below.
Entry entryB = {dataB, sizeof(dataB), 4}; //Likewise
Entry entryC = {dataC, sizeof(dataC), 0}; //0 terminates the linked list
Entry emptyEntry = {(void*)0, 0, 0};
Entry MasterList[8] = {
entryA,     //Index 0 - Contains dataA and points to Index 3 as the next Entry in a linked list
emptyEntry, //Index 1 - Unused (or used for something else)
emptyEntry, //Index 2 - Unused
entryB,     //Index 3 - Contains dataB and points to Index 5 as the next Entry in a linked list
entryC,     //Index 4 - Contains dataC and terminates the linked list
emptyEntry, //Index 5 - Unused
emptyEntry, //Index 6 - Unused
emptyEntry};//Index 7 - Unused

我的问题：你能想出一种方法在编译时自动计算"nextEntry"的值吗？现在，如果有人打乱主列表中条目的顺序，或者添加一些其他数据并偏移一些条目，则存在巨大的漏洞潜力。我们在单元测试或集成测试中发现了所有的错误，但不可避免的是，对MasterList的任何更改都会被检查两次。一次是当有人编辑它时，第二次是当代码测试失败时修补链接列表。

我最初的本能是"不，那太愚蠢了"one_answers"你为什么要尝试这个？"但我过去见过一些令人印象深刻的C-Macro魔法。我也相信任何宏观魔法都会比上面的更难维持，但我认为这值得一试，对吧？

澄清-我一直使用MasterList数组（而不是一个正确的链表），因为信息的消费者希望它是这样的。事实上，还有其他不属于链表的信息需要在固定索引中。除此之外，还有这个链表数据。它之所以是一个链表，是为了在添加其他具有固定索引的元素时，使其在一定程度上不受推搡。例如，如果我们需要在索引3处插入一个特定的字符串，则条目B和条目C可能会被推掉，但仍然可以通过从链表头（固定在索引0处）开始并遍历列表来发现。

Answer 1

通过重置并使用行号：

#line 0 
#define NUM ( __LINE__ -2)
Entry MasterList[8] =
{ {dataA, sizeof(dataA), NUM }
, {(void*)0, 0, NUM }
, {(void*)0, 0, NUM }
, {dataB, sizeof(dataB), NUM }
, {dataC, sizeof(dataC), NUM }
, {(void*)0, 0, NUM }
, {(void*)0, 0, NUM }
, {(void*)0, 0, NUM }
};

gcc-E:的输出

# 28 "index.c"
#pragma #line 0 __FILE__
# 1 "index.c"
Entry MasterList[8] =
{ {dataA, sizeof(dataA), ( 2 -2) }
, {(void*)0, 0, ( 3 -2) }
, {(void*)0, 0, ( 4 -2) }
, {dataB, sizeof(dataB), ( 5 -2) }
, {dataC, sizeof(dataC), ( 6 -2) }
, {(void*)0, 0, ( 7 -2) }
, {(void*)0, 0, ( 8 -2) }
, {(void*)0, 0, ( 9 -2) }
};

应该可以在不重置行号的情况下执行此操作。

Answer 2

听起来应该只使用一个实际的链表，而不是让每个节点的数据猜测最后一个条目的索引。

您对预处理器的欺诈行为持开放态度，但您给运行时访问应该在编译时强制执行的数据带来了设计问题。首先，每个节点都必须对它甚至不知道自己所在的数组有全局知识。我知道C没有C++/Java/C#的魔力，更不用说Perl/Python/Ruby了，但这只是一个数据结构问题，而不是语言特性问题。

从评论编辑：

struct SpecialArray { 
    Entry* entries[10000]; //you'll have to write your own real memory management
    int lastIdx;
};
void addEntry(struct SpecialArray* arr, Entry* entry) {
    arr->entries[arr->lastIdx] = entry;
    entry->nextEntry = arr->lastIdx+1;
    lastIdx++;
}

听起来你实际上需要一个Entry[]，而不是评论中的*Entry[]，但这可以通过为Entry添加深度复制功能来实现。然后，只要客户端代码需要Entry数组，就可以传递(&arr.entries)。例程addEntry将为您管理索引问题并解决您原来的问题。

Answer 3

使用编译器或预处理器可用的工具似乎并没有一个好的方法来做到这一点。我认为最好的方法是使用代码生成工具来生成已经连接了链表的数组。

Answer 4

不要用指数来做这件事，它不值得尽可能少的收益。并且不要使用单独的对象，而是就地初始化。下面是另一个玩具示例，它甚至具有合格的next指针const，因此没有人可以乱用它：

#include <stddef.h>
typedef struct data data;
struct data {
  char const* D;
  size_t len;
  data*const next;
};
#define STR_INITIALIZER(STR) .D = STR, .len = (sizeof(STR) - 1)
#define DATA_INITIALIZER(NAME, STR, HERE) [HERE] = { STR_INITIALIZER(STR), &(NAME)[HERE+1], }
data table[] = {
  DATA_INITIALIZER(table, "something", 0),
  DATA_INITIALIZER(table, "something else", 1),
  { 0 }
};

这使用了C99的"指定初始值设定项"功能，但您可能会有一个没有的版本。

如果您真的希望所有操作都由宏完成，那么您可以使用P99来展开，下面的内容应该适用于"p99_for.h"（未测试）

#define TABLE_ENTRIES(NAME, ...) P99_FOR(NAME, P99_NARG(__VA_ARGS__), P00_SEQ, DATA_INITIALIZER, __VA_ARGS__)
data table[] = {
  TABLE_ENTRIES(table, "something", "something else"),
  { 0 }
};