跳表（SkipList）

最近在看leveldb的源码，看到核心的skiplist时发现自己浑浑噩噩的，本来就不太懂，.h文件里还竟是模板迭代器啥的，于是决定还是先吧思路理清楚，都提倡不要重复发明轮子，但只有熟悉轮子的制作过程，用起来才可能得心应手啊。

这篇图文并茂的博文将跳表的基本操作描述的很不错：http://kenby.iteye.com/blog/1187303

为了便于忘了再看时能很快懂（源码真心不好看呀），下面的代码中很多地方都注释了一些我的理解

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define MAX_LEVEL	10
#define ALL_PART	4

struct SkipListNode{
	//data
	int key;
	//level count the node appears
	int height;
	//soft member
	SkipListNode* next[1];
};

int RandomLevel()
{
	int h = 1;
	while(rand() % ALL_PART == 0) ++h;
	return h;
}
SkipListNode* NewNode(int level)
{
	return reinterpret_cast<SkipListNode*>(malloc(sizeof(SkipListNode) + (level-1)*sizeof(SkipListNode*)
											));
}
void FreeNode(SkipListNode* p)
{
	free(p);
	p = NULL;
}

class SkipList
{
public:
	SkipList();
	~SkipList();

	bool Contain(int k)const;
	bool Insert(int k);
	bool Delete(int k);
	void Show()const;
private:
	void findLastLessThan(int k, SkipListNode* arr[MAX_LEVEL])const;
private:
	SkipListNode* head;
};

/*********************************** implementation *********************************/

SkipList::SkipList()
{
	head = NewNode(MAX_LEVEL);
	memset(head, 0, sizeof(SkipListNode) + (MAX_LEVEL-1)*sizeof(SkipListNode*));
	head->height = 1;
}
SkipList::~SkipList()
{
	int i = 0, m = head->height;
	for(; i < m; ++i){
		//delete nodes with height i
		SkipListNode *p = head, *q = head->next[i];
		for(; q; q = p->next[i]){
			if(q->height == i+1){
				p->next[i] = q->next[i];
				FreeNode(q);
			}
			else p = q;
		}
	}
	FreeNode(head);
}
void SkipList::Show()const
{
	puts("SkipList:");
	int m = head->height;
	for(; m; --m){
		printf("level %d: ", m-1);
		SkipListNode* p = head->next[m-1];
		bool first = true;
		for(; p; p = p->next[m-1]){
			if(first) first = false;
			else printf("-->");
			printf("%d", p->key);
		}
		puts("");
	}
}
void SkipList::findLastLessThan(int k, SkipListNode* arr[MAX_LEVEL])const
{
	// puts("enter SkipList::findLastLessThan");
	SkipListNode *p = head, *q;
	int m = p->height;
	//find each level's last node whose key is smaller than k
	for(int i = m-1; i >= 0; --i){
		//move horizontally for level i
		while((q = p->next[i]) && q->key < k) p = q;
		//p is last node in level i that has key smaller than k
		arr[i] = p;
		// printf("head = %p, arr[%d] = %p\n", head, i, p);
	}
	// puts("leave SkipList::findLastLessThan");
}
bool SkipList::Contain(int k)const
{
	SkipListNode* update[MAX_LEVEL], *q;
	findLastLessThan(k, update);
	q = update[0]->next[0];
	return q && q->key == k;
}
bool SkipList::Insert(int k)
{
	SkipListNode* update[MAX_LEVEL], *q;
	findLastLessThan(k, update);
	q = update[0]->next[0];
	// printf("head = %p, q = %p\n", head, q);

	//q is the first node in level 0, whose key is no lesser than k
	if(q && q->key == k) return false;

	//k is not in skiplist yet, find its highest appearing level
	int h = RandomLevel(), m = head->height;
	// printf("height for %d is  %d\n", k, h);
	if(h > m){
		//we need to redirect update[m, h) to head
		for(int i = m; i < h; ++i) update[i] = head;

		//need to change skiplist's whole height
		head->height = h;
	}

	//now insert k behind every update[0, h)
	SkipListNode* t = NewNode(h);
	t->key = k;
	t->height = h;
	for(int i = 0; i < h; ++i){
		t->next[i] = update[i]->next[i];
		update[i]->next[i] = t;
	}
	return true;
}
bool SkipList::Delete(int k)
{
	SkipListNode* update[MAX_LEVEL], *q;
	findLastLessThan(k, update);
	q = update[0]->next[0];

	//check k is in skip list or not, that is whether it appears in the lowest level
	if(!q || q->key != k) return false;

	//update[] are k's previous nodes, redirect them to k's next ones
	for(int i = q->height-1; i >= 0; --i){
		update[i]->next[i] = q->next[i];
	}
	FreeNode(q);

	//check if we need to change skiplist's whole height
	int h = head->height;
	for(; h; --h){
		if(head->next[h-1]) break;
	}
	head->height = h;
	return true;
}

void test()
{
	int cnt = 10, i;
	SkipList sl;

	puts("==== Insert ====");
	for(i = 0; i < cnt; ++i){
		if(sl.Insert(i)) printf("Insert %d into SkipList done\n", i);
		else printf("%d already in SkipList\n", i);

		if(sl.Insert(i)) printf("Insert %d into SkipList done\n", i);
		else printf("%d already in SkipList\n", i);
	}
	getchar();

	puts("==== Show ====");
	sl.Show();
	getchar();

	puts("==== Contain ====");
	for(i = 0; i < cnt; ++i){
		int v = rand() % (cnt + cnt / 2);
		if(sl.Contain(v)) printf("%d is in SkipList\n", v);
		else printf("%d is not in SkipList\n", v);
	}
	getchar();

	puts("==== Delete ====");
	for(i = cnt-1; i >= cnt/2; --i){
		if(sl.Delete(i)) printf("Delete %d from SkipList done\n", i);
		else printf("%d not in SkipList\n", i);

		if(sl.Delete(i)) printf("Delete %d from SkipList done\n", i);
		else printf("%d not in SkipList\n", i);
	}
	getchar();

	puts("==== Show ====");
	sl.Show();
	getchar();
}

int main()
{
	test();
	puts("done");
	getchar();
	return 0;
}