c - 有效地将可变长度数组存储到静态内存中

Question

我正在开发一个嵌入式系统，该系统需要将一些预先确定的数据存储在内存中以供运行时使用。数据本质上是一个很大的状态转换表。

例子:{1,2},{1,3},{2,3},{2,4},{2,5},{3,1}

其中:状态 1 可以转到状态 2 或 3。状态 2 可以转到状态 3、4 或 5。状态 3 只能转到状态 1。

我目前正在使用“N”x 2 数组 - 其中“N”是最大转换量(在本例中为 3)。

这不是节省空间的，有很多未使用的内存。从上面的示例中，状态 1 有 2 个未使用的分配，状态 3 有 4 个未使用的分配。如果一个状态比其余状态有更多的转换，问题会变得更加明显。

我当前的实现将信息存储为结构数组，其中结构的形式为:

#define max_transitions 9
...
const struct state_table{
    uint16_t number;
    char len;
    uint16_t stt[max_transitions][2];
};

然后我继续定义一堆数据:

#define MAX_STATES 619
const static struct state_table SUPERVISOR[MAX_STATES] = {
{1,6,{{301,2},{410,3},{411,4},{500,5},{501,6},{604,7}}},
...
{619,5,{{301,611},{401,297},{500,619},{501,619},{602,514}}}
};

第一个元素是当前状态，第二个是长度，第三个是 STT 的数组。

在 619 个状态中，大约有 10 个状态有 9 个转换。平均过渡长度为 5，因此这对我当前的实现造成了巨大的内存浪费。

问题:我正在寻找有关如何提高空间效率的指导。

提前致谢

Answer 1

如评论中所述，这不使用 VLA。您需要的是一个结构，其中最后一个元素是一个未知长度的数组。一种简单的方法是使用指针，但它会强制您拆分初始化:

const struct state_table{
    uint16_t number;
    char len;
    const uint16_t (*stt)[2]; // pointer to arrays of size 2
};

const uint16_t tst1[][2] = {{301,2},{410,3},{411,4},{500,5},{501,6},{604,7}};
...
const uint16_t tst619[][2] = {{301,611},{401,297},{500,619},{501,619},{602,514}};

const static struct state_table SUPERVISOR[MAX_STATES] = {
{1,6,tst1,
...
{619,5,tst619}
};

事实上，这就像用指向数组的指针数组替换二维数组，因为结构的最后一个元素仅指向其他数组。