基于异或实现的单方向双链表

背景

在某些应用中需要使用分配在栈上的不定长内存数组。而我常用的泛型双链表是弱定义的，在开发专用模块时使用很方便；但在上述使用情景时，使用会变得很繁杂，另外储存一个单位需要额外的两个单位。
空间利用率实在有些难以恭维，于是便有了这个小模块的诞生。在简单应用中，一般是对某不定长的单位组进行保存，即压栈/出栈，入列/出列。

双向链表与异或

链表需要进行保存自身的入口，即链表元素的地址。
另外，每个元素都会保存前驱(Before)和后继(After)节点。这就是上文提到的额外的两个存储单位。

为了压缩空间，很容易想到对 B 和 A 进行融合，显然与和或都会造成信息的损失，于是使用异或(总之就是取反，懒得解释了)。

  • 异或的性质 a ⊙ a ⊙ b = b 。

于是，我们有一个链表，首结点 B = NULL 、尾结点 A = NULL 。以从头至尾举例：

  1. 首结点的 A ⊙ B = A ，故获得了后继结点。
  2. 对于后继结点，首结点是已知的，换言之，前驱 A 已知。于是 B ⊙ A ⊙ B = A 。
  3. 循环上述步骤。

这种链表既可以从头至尾也可以从尾至头，但是任意一次遍历只能保持一个方向。这种特性对于灵活性较强的应用是很不好用的，但是对于简单应用足够了，譬如栈上的不定长队列与栈。

API

一共包含三个 API 。

  1. 初始化：
1
2
3
#define STACK_INIT(num)                              \
	void* first_node_##num[2]		 = {NULL, NULL}; \
	void** __stack_pointer_##num##__ = first_node_##num
  1. PUSH:
1
2
3
4
5
6
7
#define __STACK_PUSH__(num, value, count)                                                                             \
	void* node_##num##_##count[2] = {__stack_pointer_##num##__, NULL};                                                \
	__stack_pointer_##num##__[0]  = (void*)((intptr_t)__stack_pointer_##num##__[0] ^ (intptr_t)node_##num##_##count); \
	__stack_pointer_##num##__[1]  = (void*)value;                                                                     \
	__stack_pointer_##num##__	  = node_##num##_##count
#define __STACK_PUSH(num, value, count) __STACK_PUSH__(num, value, count)
#define STACK_PUSH(num, value)			__STACK_PUSH(num, value, __COUNTER__)
  1. POP:
1
2
3
4
5
6
7
8
9
10
11
12
#define STACK_POP(num, element_pointer, res_pointer)                                               \
	do {                                                                                           \
		intptr_t temp			  = (intptr_t)__stack_pointer_##num##__;                           \
		__stack_pointer_##num##__ = __stack_pointer_##num##__[0];                                  \
		if (*__stack_pointer_##num##__ == first_node_##num[0]) {                                   \
			*res_pointer = 0;                                                                      \
		} else {                                                                                   \
			*res_pointer				 = 1;                                                      \
			__stack_pointer_##num##__[0] = (void*)((intptr_t)__stack_pointer_##num##__[0] ^ temp); \
		}                                                                                          \
		*element_pointer = (intptr_t)__stack_pointer_##num##__[1];                                 \
	} while (0)

注意事项

  1. 该组 API 只使用栈内存，这既是最大的优点也是最大缺点。如果读者自己找不出该组 API 的优缺点，那就不应该使用。
  2. 笔者的主要使用场景为 STM32 某个函数内的已知短不定长数组。 既不想产生内存碎片，又没办法方便的确定数组长度。

附录：测试样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	STACK_INIT(1);
	STACK_PUSH(1, 0);
	STACK_PUSH(1, 1);
	STACK_PUSH(1, 2);
	STACK_PUSH(1, 3);
	STACK_PUSH(1, 4);
	STACK_PUSH(1, INT_MAX);

	intptr_t res		= 1;
	intptr_t element = 0;
	do {
		STACK_POP(1, &element, &res);
		printf("Popped element: %ld\n", element);
	} while (res);

	return EXIT_SUCCESS;
}