Liuw's Thinkpad

GCC预处理器支持variadic macro，即是可变参数宏。定义方法和可变参数函数的定义很相似。

#define SCHED_OP(fn, ...) \
    (( ops.fn != NULL ) ? ops.fn(__VA_ARGS__) \
    : ( typeof(ops.fn(__VA_ARGS__)))0 )

在宏定义的时候用三个点来表示可变参数，后面用__VA_ARGS__来表示可变参数。

虽说两者“相似”，但是实际上可变参数宏和可变参数函数还是有区别的。如：

#define eprintf(format, ...) fprintf (stderr, format, __VA_ARGS__)

这个宏必须保证__VA_ARGS__至少含有一个参数，否则format之后会多一个逗号，语法错误。

不过这个问题还是有解决方法的，像下面的写法，即使__VA_ARGS__为空，预处理后也不会出现问题。预处理器会把前面的逗号一并删除。

#define eprintf(format, ...) fprintf (stderr, format, ##__VA_ARGS__)

参考：http://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html

最简单的两种排序方式，不多说。

选择排序的第i次循环中选取对应的第i小的数放在list[i]中。

插入排序第次循环把当前待排序的数插入到适当的位置中。

void selection_sort(int *l, int n)
{
	int i, j, tmp, min;

	for (i = 0; i < n-1; i++) {
		min = i;
		for (j = i+1; j < n; j++)
			if (l[j] < l[min])
				min = j;
		tmp = l[min], l[min] = l[i], l[i] = tmp;
	}
}

void insertion_sort(int *l, int n)
{
	int i, j, next;

	for (i = 1; i < n; i++) {
		next = l[i];
		for (j = i-1; j >= 0 && next < l[j]; j--)
			l[j+1] = l[j];
		l[j+1] = next;
	}
}

最大堆可以用一棵完全二叉树来实现，插入和删除都是O(lgn)的复杂度。

插入的时候先把待插入的元素设为树的最后一个叶子，然后由下往上递归处理，每次都比较子节点（初始为最后一个叶子节点）与父节点的键值大小。若父节点的键值较小，那么父节点下移，直到父节点的键值大于子节点，这就是合适的插入位置。这里可以很容易推导出插入位置前面所有的节点的键值都是大于待插入节点的键值的，而插入位置后面所有的节点的键值都是小于待插入节点的键值的。

删除的时候总是删除树的根。通常情况下删除之后堆还需要用最后一个叶子进行进一步的调整。这个调整是自上而下的。递归地扫描每一层，假如某层节点的子节点的键值小于最后一个叶子的键值，那么这个叶子就应该放在这一层；假如某层节点的子节点键值还大于最后一个叶子的键值，那么就进入下一层进行搜索。最后的结果也是符合最大堆的定义的。

下面给出一个数组树实现的最大堆。我原来在想的时候走入了一个误区，认为删除其实和插入所需要的操作是一样的，反正都会往里面插。但是实际上，插入的时候，节点是“下移”，删除的时候，节点是“上移”。所以这两个操作扫描的方向是不一样的。

typedef struct {
	int key;
	/* other fields */
} element;

#define MAX_ELEMENTS 100
element heap[MAX_ELEMENTS];
int n = 0; 			/* heap[0] is never used */

#define HEAP_FULL()  (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY() (!n)

void insert(element item)
{
	int i;

	if (HEAP_FULL()) {
		printf("Heap full\n");
		exit(-1);
	}

	i = ++n;
	while ((i != 1) && (heap[i].key > heap[i/2].key)) {
		heap[i] = heap[i/2]; /* move down */
		i /= 2;
	}

	heap[i] = item;
}

element delete()
{
	element item, temp;
	int child, parent;

	if (HEAP_EMPTY()) {
		printf("Heap empty\n");
		exit(-1);
	}

	item = heap[1];

	/* adjust heap with last element */
	temp = heap[n--];
	parent = 1, child = 2;	/* start from top level */

	while (child <= n) {
		/* find larger child */
		if ((child < n) && heap[child].key < heap[child+1].key)
			child++;
		if (heap[child].key < temp.key) /* found right position */
			break;
		/* move child up */
		heap[parent] = heap[child];
		/* move down to next level */
		parent = child;
		child  = parent * 2;
	}

	heap[parent] = temp;

	return item;
}

最小堆的实现和最大堆类似。

今天下午花了很久的时候做了一个走迷宫的题目。其实这个题目以前上数据结构课的时候都已经写过了，但是再写却又花了很多时间，虽然代码结构和以前写的不一样，但是这却不是最花时间的地方。大部分的时间都花在Debug一些很低级的bug上面，是我状态不好呢，还是写程序实在太烂了呢 Orz。

近来烦心事很多，确实很影响状态。不过就这次的练习来说，还是可以挖出自己很多不好的编程习惯的。总有来说，我要注意：

1. 训练对问题的抽象能力。看到一个问题时，要能够选择出合适的数据结构去把这个问题转化成计算机可以处理的形式。
2. 加强对数据结构的记忆，写逻辑已经先写出数据结构的定义及其上的操作，以后可以方便直接用。
3. 先把问题分析透，用纸笔或者伪代码先把流程写清楚再编码，急于求成只会引入更多的bug。

下面是代码，可以找出所有的路径，很简单哦。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Z 0
#define E 1
#define S 2
#define W 3
#define N 4
#define F 5

#define MAX_STACK_SIZE 1000

/* 0 means clear, 1 means blocked */
#define X 5
#define Y 4
int maze[X][Y] = {
	{0, 0, 1, 0},
	{1, 0, 0, 1},
	{1, 0, 1, 1},
	{0, 0, 0, 1},
	{1, 0, 0, 0}
};

typedef struct {
	int x, y;
	int direction;
} coord;

int   top = -1;
coord stack[MAX_STACK_SIZE];

#define PUSH(c)						\
	do {						\
		if (++top > MAX_STACK_SIZE) {		\
			printf("Stack overflowed\n");	\
			exit(-1);			\
		}					\
		stack[top] = c;				\
	} while (0)

#define POP(c)						\
	do {						\
		if (top == -1) {			\
			printf("Stack underflowed\n");	\
			exit(-1);			\
		}					\
		c = stack[--top];			\
	} while (0)

#define EMPTY() (top == -1)

#define EQUAL(c1, c2) (c1.x==c2.x && c1.y==c2.y)

#define EXISTS(c) exists(c)

#define IS_VALID_MOVE(c) \
	( !maze11 && c.x >= 0 && c.x < X && c.y >= 0 && c.y < Y )

int exists(coord c)
{
	int i, res = 0;
	for (i = 0; i <= top; ++i) {
		if (EQUAL(stack[i], c)) {
			res = 1;
			break;
		}
	}
	return res;
}

int main()
{
	coord fini_coord = { 4, 3, 0} , start_coord = { 0, 0, 0 };
	int found = 0;
	coord t, t1;
	int i;

	PUSH(start_coord);
	while (!EMPTY()) {
		t = stack[top];
		t1 = t;
		if ((EQUAL(t, fini_coord))) {
			found++;
			printf("Path %d:\n", found);
			for (i = 0; i <= top; i++)
				printf("(%d, %d)\n", stack[i].x, stack[i].y);
			printf("\n\n");
			POP(t1);
			continue;
		}

		switch (t.direction) {
		case Z:
			t.direction = E;
			stack[top] = t;
			t1 = t;
			t1.y += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);

			break;

		case E:
			t.direction = S;
			stack[top] = t;
			t1 = t;
			t1.x += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;

		case S:
			t.direction = W;
			stack[top] = t;
			t1 = t;
			t1.y -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case W:
			t.direction = N;
			stack[top] = t;
			t1 = t;
			t1.x -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case N:
			t.direction = 5;
			stack[top] = t;
			break;
		case F:
			POP(t1);
			break;
		default:
			printf("BUG: unknown direction\n");
			exit(-1);
		}
	}

	if (!found)
		printf("No path found\n");

	return 0;
}

算法这东西，真是常学常新，常学常有啊。今天花了一个下午去理解KMP算法的精髓所在，先写点感受。

定义等匹配的字符串为S长度为m，模式为P长度为n。双循环匹配算法的最坏时间复杂度是O(m*n)，而KMP算法的复杂度为O(m+n)。

分别设定：

S: abdabcabcd
P: abca

P首先要进行预处理，生成next数组的过程是一个P自匹配的过程。next数组的作用是告诉用户，在当前字符匹配失败的时候，P至少需要回退到哪一个位置，直观地理解，这个next数组表现了P自身的相似程度。其实生成next的过程和匹配过程是极其相似的。

让我们先不去管next是怎么生成的，我们先感性地认识一下S和P的匹配过程。

第一步：

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:  a b c a
j:  0 1 2 3

在i = 2，j = 2的时候失配。在最笨的办法下面，我们是直接把P右移一个位置，即是说i被设置为1，j又被设置为0，重新开始匹配。

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:    a b c a
j:    0 1 2 3

很明显，这样一次移动一个位置太慢，i回溯了，效率太低。观察一下S，由于S[2] = P[0]，S[3] = P[1]，我们完全可以把P直接右移两个位置，即是从i = 4，j = 2开始比较。

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:      a b c a
j:      0 1 2 3

可是计算机不是人，不懂怎么去“观察”。所以我们必须生成next数组，告诉计算机在失配的时候应该把j设置为什么，而i不必回溯。

个人觉得这个生成next的过程是整个算法最精彩的部分。我原来在考虑搜索问题时也想到了i的不回溯，但是j该如何设置还没有很好的想法。看到KMP的next生成方法也没能很好地理解，笨啊。

前面我提到过，生成的next数组其实表示的是P自身的相似程度。形式化地定义一个失配函数f：

记模式P=p0p1...p(n-1)
f(j) = i，i为满足i<j且p0p1...pi=p(j-i)p(j-i+1)...pj的最大整数，i>=0
f(j) = -1，其他情况

这个失配函数还有另外一个表达形式：

f(j) = -1，j=0
f(j) = f^m(j-1) + 1，其中m是满足p(f^k(j-1)+1)=pj的最小整数k
f(j) = -1，其他情况

根据这个表达形式，我们可以得到如下的生成next数组的算法：

int lenp = strlen(p);

next[0] = -1; // 这个很好理解。
for (j = 1; j < lenp; j++) {

    i = next[j-1]; // 首先把前一个next值取出来
    /* 在i=-1时，说明前面一元素并非相似模式一部分。但是这个时候j指向的元素也
     * 可能是模式的开始，所以后面还要再作判断。
     * i>=0，若j指向的元素和i+1指向的元素不同，说明自身的相似性已经结束了。
     * 我们需要回溯到前一个模式去。
     */
    while ((p[j] != p[i+1]) && (i >= 0))
        i = next[i];

    if (p[j] == p[i+1])
        next[j] = i + 1;
    else
        next[j] = -1;
}

其中while循环一部分有点绕，还是举个例子实在：

j:     0  1  2  3  4  5  6  7  8  9
P:     a  b  c  d  a  b  c  a  b  d
next: -1 -1 -1 -1  0  1  2  0  1 -1

next的前面4个元素都是-1这自不必多说。在j = 7时，i = next[7] = 2，p[i+1] = ‘d’，发生失配，所以设置i = next[i] = -1，退出循环。

综合起来，整个KMP算法代码如下：

int kmp(const char *s, const char *p)
{
	int i, j, lens=strlen(s), lenp=strlen(p);
	int *next = (int *)malloc(sizeof(int)*lenp);

	next[0] = -1;
	for (j = 1; j < lenp; j++) {
		i = next[j-1];
		while ((p[j] != p[i+1]) && (i >= 0))
			i = next[i];
		if (p[j] == p[i+1])
			next[j] = i + 1;
		else
			next[j] = -1;
	}

	i = j = 0;
	while (i < lens && j < lenp) {
		if (s[i] == p[j])
			i++, j++;
		else if (j == 0)
			i++;
		else
			j = next[j-1] + 1;
	}

	free(next);

	return ( j == lenp ? (i-lenp) : -1 );
}

在匹配过程中，i只会单向增加。

对很多人来说，这样的算法自然是not a big deal。但是我是个算法白痴，好记性不如烂笔头。

其实想法很简单，以排列为例，假如要生成abcd的全排列的话，其实就是：

• 先选出a，然后排列bcd。
• 先选出b，然后排列acd。
• ……

即是说，要生成n个元素的全排列，必须先解决n-1个元素的全排列；要生成n-1个元素的全排列，必须先生成n-2个元素的全排列……

幸运的是，1个元素的全排列实在是太“明显”了。

/* Permutaion and combination in C */

#include <stdio.h>

void swap(char *a, char *b)
{
	char tmp;
	tmp = *a, *a = *b, *b = tmp;
}

/* s: start index
   n: last index, NOTE, not total element number of list!
*/
void perm_aux(char *list, int s, int n)
{
	int i;
	if (s == n) { // 此时已经全部扫描完数组
		for (i = 0; i <= n; ++i)
			printf("%c", list[i]);
		printf("\n");
	}else{
		for (i = s; i <= n; ++i) { // 依次选取从s到n的元素作为此子全排列的第一个元素，然后生成s+1到n子序列的全排列
			swap(&list[s], &list[i]);
			perm_aux(list, s+1, n);
			swap(&list[s], &list[i]);
		}
	}
}

/* permutation for a list with m elements */
void perm(char *list, int m)
{
	perm_aux(list, 0, m-1);
}

void comb_aux(char *list, int d, int n, int m)
{
	int i;
	if (d == n) {
		for (i = 0; i <= n; ++i)
			printf ("%c", list[i]);
		printf("\n");
	}else{
		for (i = d; i <= m; ++i) {
			swap(&list[d], &list[i]);
			comb_aux(list, d+1, n, m);
			swap(&list[d], &list[i]);
		}
	}
}

/* Take n numbers from a set of m numbers */
void comb(char *list, int n, int m)
{
	comb_aux(list, 0, n-1, m-1);
}

int main(int argc, char *argv[])
{
	char l[3] = {'a', 'b', 'c' };
	perm(l, 3);
	comb(l, 2, 3);
	return 0;
}

我个人理解的计算机科学中的Continuation，即是把一个计算过程具体化（reifier），得到一组可以用来重构这个计算过程的结构。通常情况下，它包含了处理器的栈，还包含了当前的执行点（具体化一点，就是所有寄存器的值），这样处理器就可以在任何时候重构这个计算过程。

一些高级语言，如Python、Ruby、Haskell、LISP等，在VM中对Continuation提供了支持。目前使用的计算机，还是必须手工编写代码才能支持Continuation。

Xen提供了一个hypercall_create_continuation函数，用来resume当前的hypercall。具体做的事情无非就是为客户虚拟机准备好上下文（栈及寄存器），然后重新执行陷入指令。要让虚拟重新执行陷入指令的处理又分为再种情况：假如是PV的虚拟机，把EIP减2，重新执行int 0×82或者syscall指令；假如是HVM，那么不需要对EIP作处理，因为vmcall产生的是fault，指令会重新自动执行。

Xen中的Continuation仅仅用于重新执行hypercall，对栈和寄存器的操作比较少，速度是有保证的。

那么，Xen在什么时候需要创建Continuation呢？常见的代码形式是：

if ( hypercall_preempt_check() )
    hypercall_create_continuation(...)

hypercall_preempt_check又是干什么的呢？假如当前物理CPU有等待处理的softirq，或者PV中的VCPU中有可投递的upcall（pending且!masked），那么它的返回值就为真。（HVM这里先不讨论）

即是说，Xen在执行某些Hypercall的时候，有可能处于一种不能抢占CPU的状态，所以必须让客户虚拟机重新再执行一次Hypercall。

受影响的Hypercall有：

__HYPERVISOR_hvm_op
__HYPERVISOR_mmuext_op
__HYPERVISOR_mmu_update
__HYPERVISOR_domctl
__HYPERVISOR_set_trap_table
__HYPERVISOR_memory_op
__HYPERVISOR_multicall
__HYPERVISOR_console_io

本人目前的看法是，这些Hypercall在有upcall或者softirq处于pending的状态时候执行的话，都会有影响虚拟机状态一致性的可能。以console io为例，虚拟机和consoled之间的事件通知，就是用的event channel机制。处于pending状态的event很可能就是IO通信产生的。假如虚拟机在调用__HYPERVISOR_console_io之前没有先把所有的event都处理完，那么就会造成数据的丢失。

但是其他的Hypercall为什么不会有这样的问题呢？那自然是因为其他的Hypercall在执行的时候可以保证当时所处的状态是“干净”的。

草草看了一下代码，写下了上面的文字。水平所限，错误在所难免，欢迎指正。

又蛋疼了，从一道招聘用的C题改一下得来的。

原题是“不使用if，while，do while，for等结构输出数组中不大于k的所有元素”。不用循环，第一的反应自然是递归；不使用if，但是又要做分支（比较大小、递归终止），那么可以用三目运算符 ?: 。

那么原题再加强一下条件，三目运算符?:也不能用了，那么只有用点奇技淫巧来解决了。还好玩C也玩了这么多年，那么就在机器层面上解决这个问题吧。

#include <stdlib.h>
#include <stdio.h>

int arr[8] = { 10, 4, 2, 5, 8, 1, 9, 3 };

void rec(int *array, int n, int k);

void f1(int *array, int n, int k)
{
	printf("%d\n", array[n]);
	rec(array, n-1, k);
}

void f2(int *array, int n, int k)
{
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	rec(array, n-1, k);
}

void e1(int *array, int n, int k)
{
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
	asm volatile ("nop");
}

// why don't we put e2 before e1?
// because e2 is 0x4f bytes long, padding would be 0x80-0x4f bytes long,
// i don't want to see such a long annoying function.
void e2(int *array, int n, int k)
{
	unsigned int mask = 0x80000000;
	void (*pf)(int*, int, int);

	int t = array[n];
	pf = f1;

	// t-k yields ">=", t-1-k yields ">"
	pf += (((t-1 - k) & mask) >> 25);
	pf(array, n, k);
}

void rec(int *array, int n, int k)
{
	unsigned int mask = 0x80000000;
	void (*pf)(int*, int, int);

	pf = e1;
	// notice that -1
	pf += ((-1 - n) & mask) >> 26;
	pf(array, n, k);
}

int main()
{
#if 0
	printf("%p %p %p %p\n%x\n%x\n%x\n",
	       f1, f2, e1, e2, f2-f1, e1-f2, e2-e1);
#endif
	// second argument should be array's max index, not size
	rec(arr, 8-1, 0);
	return 0;
}

其实思路很简单，各函数之间的间距是2^n且不为0，比较时用减法溢出再移位得到偏移，然后把该偏移加到函数指针之上。若有溢出，加完偏移之后函数指针就会指向另外一个函数，从而实现分支的选择。在32位的Linux上用gcc编译运行通过，Windows不行，还得再调整。

当然，MAX_INT减去一个负数时的结果是错误的。这个程序还可以再进一步的改进。可以用函数指针数组，然后用形似如下的代码

pf[a>b] = f1;
pf[a<=b] = f2;
pf[1];

来实现分支。

再来一个在语言层面上解决问题的版本，基本不依赖于具体的机器和编译器，而且没有减法溢出的问题。

#include <stdio.h>

int array[] = { 1 , 3 , 8 };
int k = 4;
int n;

int f1(int a) { printf("%d\n", a); }

int f2(int a) { }

void solve2(int a, int b)
{
	int ff[2];
	ff[ a >= b ] = a;
	ff[ b >= a ] = b;

	int (*f[2])(int);
	f[ a >= b ] = f1;
	f[ b >= a ] = f2;

	f[1](ff[1]);
}

void solve1(int a[], int n, int k) {}

void solve(int a[] ,int n ,int k)
{
	solve2(a[n], k);

	void (*f[2])(int a[], int n, int k);
	f[ n > -1 ] = solve;
	f[ -1 >= n] = solve1;

	f[1](a, n - 1, k);
}

int main(int argc, char **argv)
{
	n = sizeof(array) / sizeof(array[0]);
	solve(array, n-1, k);
	return 0;
}

UPDATE：加上小呆给的版本

int lk(int *array, int n, int k)
{
    /*
     * when there is no menber in array
     * n ==0 returns true
     * the whole expression is true
     * stop
     */
    return (n == 0)
        ||
        /*
         * print the member if it is larger than k
         * the whole expression is always false and never blocks
         */
        ((*array > k) && printf("%d ", *array) && 0)
        ||
        lk(++array, --n, k);
}

看到类似这样的代码。

char **arr;
int len;
arr = produce_array(&len);
/* 此时生成了有len个元素的含有内容的数组。用一次free来释放？ */
free(arr);

原来看到free()那里，觉得会有问题，我的想法是要为每一个char *分别malloc内存，所以需要有len次free。其实不然，C语言太灵活了，不要被自己原来固有的想法束缚了才好。完全可以通过一次malloc申请到所有的空间，再活用这些空间。

/* 设有 n 个以 NULL 结尾的字符串放在 data 中，它们的总长为 dlen */
char **produce_array(int *len)
{
  char **ret;
  int i;

  *len = n;
  ret = malloc(sizeof(char *) * n + dlen);
  ret[0] = (char *)(ret + n);
  memcpy(ret[0], data, dlen);
  for (i = 1; i < n; i++)
    ret[i] = ret[i-1] + strlen(ret[i-1]) + 1;

  return ret;
}

前几天收到猎头的 PM 之后，我就一直在思考“C/C++”中间有这个“/”应该怎么理解，到底是“与”的关系还是“或”的关系。想来想去，虽然一般“/”都表示是“或”，但是现在的公司都希望是“与”。没法，看来只有 C 还是不够的，还是开始学一下 C++ 吧。

随之而来的第二个纠结就是我发现 C++ Primer 似乎不合适做入门书，至少是不合我的习惯的。还以为这本没怎么翻过的书终于可以发挥一下余热，汗。看来还是找一本比较薄一点的，轻松看看算了。