正如你所说,mpz_t
被 typedef'ed 作为数组类型的别名:
typedef __mpz_struct mpz_t[1];
结果,赋值给类型变量mpz_t
是非法的:
mpz_t a, b;
mpz_init(b);
a = b; /* Error: incompatible types when assigning to type ‘mpz_t’ */
/* from type ‘struct __mpz_struct *’ */
相反,有必要使用内置赋值函数之一:
mpz_t a, b;
mpz_inits(a, b, 0);
mpz_set(a, b); /* a is now a copy of b */
禁止直接分配给mpz_t
由于 gmp 管理内存的方式,这是必要的。请参阅下面的注释 1。
Bison 假设语义类型YYSTYPE
可以赋值给(见注2),这意味着它不能是数组类型。这通常不是问题,因为通常YYSTYPE
是联合体类型,可以对带有数组成员的联合体进行赋值。因此,只要将数组类型包含在 bison 中,使用数组类型就没有问题。%union
宣言。
但你不能对 gmp 这样做,因为虽然它可以编译,但它不会工作。您最终会出现大量内存泄漏,并且很可能会出现模糊的错误,其中 gmp 计算出错误的值(或者以更明显的方式失败,例如free
从下面的内存中取出mpz_t
).
Using mpz_t
直接将对象作为语义值是可能的,但这并不容易。您最终将花费大量时间思考哪些堆栈槽具有已初始化的语义值;哪些具有需要的值mpz_clear
ed,以及许多其他令人不安的细节。
一个更简单(但不简单)的解决方案是使语义值成为指向 an mpz_t
。如果您只是制作一个 bignum 计算器,您可以完全绕过语义值并维护自己的值堆栈。只要每个归约操作从值堆栈中弹出其所有参数并推送其结果,就可以解决这个问题。
这个值栈也将是一个向量mpz_t
值,但它在几个重要方面与解析器堆栈不同,因为它完全在您的控制之下:
-
您没有义务创造 bison 需要创造的临时价值(参见注释 2)。例如,如果您想做一个加法,从堆栈中弹出两个操作数并将结果推回,您可以这样做:
mpz_add(val_stack[top - 2], val_stack[top - 2], val_stack[top - 1]);
--top;
您可以在解析之前初始化值堆栈,并在解析完成后清除所有元素。这使得内存管理变得更加简单,并且可以让您重用分配的肢体向量。
诸如运算符和括号之类的标记没有关联的语义值,因此不占用值堆栈上的空间。这并没有节省太多空间,但它避免了初始化和清除堆栈槽的需要,因为堆栈槽中从来没有有用的数据。
Notes
1. 为什么 GMP 不鼓励直接分配
根据gmp手册,制作mpz_t
(和其他类似类型)大小为 1 的数组只是为了补偿 C 缺乏按引用传递。由于数组在用作函数参数时会衰减为指针,因此您无需显式标记参数即可实现引用传递。但肯定有人想到过,使用数组类型也会阻止直接分配给mpz_t
。由于 gmp 管理内存的方式,直接分配无法工作。
Gmp 值必须包含对分配存储的引用。 (必然的,因为bignum的大小没有限制,所以不同的bignum有不同的大小。)一般来说,有两种管理对象的方法:
使对象不可变。然后就可以任意共享,因为无法修改。
始终在分配时复制对象,从而使共享变得不可能。然后可以修改对象而不影响任何其他对象。
例如,Java 和 C++ 的字符串方法就是这两种策略的例证。不幸的是,这两种策略都依赖于语言中的一些基础设施:
上述两种策略都存在性能问题。
不可变对象在修改时需要复制,这可以将简单的线性复杂性变成二次复杂性。这是一个众所周知的重复附加到 Java 或 Python 字符串的问题; Java 的 StringBuilder 旨在弥补这个问题。不可变的整数会很烦人;累积总和是很常见的,例如(sum += value;
),并且必须复制sum
每次经过这样的循环都会大大减慢循环速度。
另一方面,强制复制赋值使得共享常量变得不可能,甚至无法重新排列向量。这可能会导致大量额外的复制,再次导致线性算法变成二次算法。
Gmp 选择了可变对象策略。大数must在赋值时被复制,并且由于 C 不允许覆盖赋值运算符,最简单的解决方案是禁止使用赋值运算符,强制使用库函数。
由于有时在不复制的情况下移动 bignum 是有用的——例如,洗牌 bignum 数组——gmp 还提供了一个交换函数。而且,如果您非常非常小心并且比我更了解 gmp 的内部结构,那么可能只使用union
上面提到的 hack,或者使用memcpy()
,为了对 gmp 对象进行更复杂的重新排列,前提是您保持重要的不变量:
每一个四肢向量必须精确地被一个且仅一个引用mpz_t
object.
重要的原因是 gmp 将在必要时使用 realloc 调整 bignum 的大小。假设a
and b
are mpz_t
,我们使用一些 hack 使它们都是相同的 bignum,共享内存:
memcpy(a, b, sizeof(a));
现在,我们使b
更大:
mpz_mul(b, b, b); /* Set b to b squared */
这会工作得很好,但在内部它会做类似的事情
tmp = realloc(b->_mp_d, 2 * b->_mp_size);
if (tmp) b->_mp_d = tmp;
为了要做b
足够大以容纳结果。这对于b
,但这可能会导致四肢被指向a
自从成功以来,就陷入了困境realloc
分配新存储将自动释放旧存储。
任何增加大小的操作都会发生同样的事情b
;将其摆正只是一个例子。a
在几乎任何增加大小的修改之后,最终都可能会出现悬空指针b
: mpz_add(b, tmp1, tmp2);
(假设tmp1
and/or tmp2
大于b
.)
2. 为什么 Bison 要求语义值是可分配的
Bison 创建了一个临时的YYSTYPE
每次减少的对象;这个临时变量是实际变量,表示为$$
在野牛行动中。在执行归约操作之前,解析器执行相当于$$ = $1;
。一旦行动完成,$1
通过$n
从堆栈中弹出,并且$$
被推到它上面。实际上,这会覆盖旧的$1
with $$
,这就是必须使用临时的原因。 (否则,设置$$
在一个行动中会令人惊讶地无效$1
.)