在堆中定义具有不同大小的结构

Question

我正在尝试实现一个bigInt库。我一直在检查其他库，如GMP，ttmaht或libtommath，但它们中的任何一个都满足项目的要求(因为许可证，因为它们只使用堆栈等(

我将遵循libtommath的方法(非常有据可查，全部用C编写(，但我希望全部存储在堆中。 libtommath 在这样的结构中实现了 bigInt：

typedef struct  {
int used, alloc, sign;
mp_digit *dp;
} mp_int;

如您所见，它具有用于访问值的间接寻址。(mp_digit是大整数的数字(。我想摆脱间接寻址，因此在堆中具有某种类似的结构，其中最后一个元素是 mp_digit[]，其中每个mp_int实例的大小可以不同。

我可以使用 void* 和 malloc(( 来做到这一点，知道前 X 位置是带有信息的 int(使用、分配、符号等(，然后访问知道偏移量的 mp_digit[]，但我不喜欢这个想法。我想知道哪个是更好的方法。

我发现了其他类似的问题，例如这个或这个，但它们不会将所有问题都存储在堆中，所以我的问题有点棘手/不同。

谢谢

Answer 1

在 C中，mp_digit dp[]表示一个灵活的数组成员。这出现在C99中：

typedef struct  {
int used, alloc;
signed char sign;
mp_digit dp[];
} mp_int;

您可以使用malloc(sizeof(mp_int) + alloc * sizeof(mp_digit));分配内存，也可以使用 realloc 分配内存。

然而，有一个晦涩的东西可以帮助你在这里保存一两个字节，这取决于mp_digit的类型 - 也就是说，dp的偏移量不一定是sizeof(mp_int)，但可能更少;有一个笨拙的宏黑客来计算要分配的实际最小大小(但这仍然是可移植的(。

该定义在C++中不起作用，但您可以在 C++ 中使用指向不完整类型的指针。

---

请注意，灵活数组成员与 1 字节数组不兼容，如下所示

Answer 2

在 C 中创建类似的东西

mp_int *LN_Create(int ndigits, int allocate)
{
mp_int *ln = calloc(1, sizeof mp_int);
if (ln != NULL)
{
ln->ndigits = ndigits;
if (allocate)
{
ln->dp = calloc(ndigits, sizeof mp_digit);
ln->alloc = 1;
if (ln->dp == NULL)
{
free(ln);
ln = NULL;
}
}
}
return ln;
}

或

mp_int *LN_Create1(int ndigits)
{
size_t allocsize = sizeof mp_int + (ndigits - 1) * sizeof mp_digit;
mp_int *ln = malloc(allocsize);
if (ln != NULL)
{
memset(ln, 0, allocsize);
ln->ndigits = ndigits;
}
return ln;
}