AVL木（mallocなし版）

C言語でmapが必要になったときのためのライブラリ。
mallocが遅いだろうと思って、
spaghetti sourceのAVL木をmallocを使わずに書き換えたもの。

ソースコード

#include<stdio.h>
#include<string.h>
/*
	AVL木によるmapの実装
	spaghetti sourceの移植だけど、mallocなし版
*/

#define S int
#define T int
#define MAX_SIZE 2000000

typedef struct{
	S key;
	T value;
	int size, height;
	int child[2];
} node;
node list[MAX_SIZE];
int size;

int balance(int);
int cmp(const void *a, const void *b){
	return *((int*)a) - *((int*)b);
}

#define max(a, b) (a > b ? a : b)
#define sz(t) (t ? list[t].size : 0)
#define ht(t) (t ? list[t].height : 0)
int rotate(int t, int l,int r){
	int s = list[t].child[r];
	list[t].child[r] = list[s].child[l];
	list[s].child[l] = balance(t);
	
	if(t)list[t].size = sz(list[t].child[0]) + sz(list[t].child[1]) + 1;
	if(s)list[s].size = sz(list[s].child[0]) + sz(list[s].child[1]) + 1;
	return balance(s);
}
int balance(int t){
	int i;
	for(i = 0; i < 2; i++){
		if(ht(list[t].child[!i]) - ht(list[t].child[i]) < -1){
			if(ht(list[list[t].child[i]].child[!i]) - ht(list[list[t].child[i]].child[i]) > 0)
				list[t].child[i] = rotate(list[t].child[i], i, !i);
			return rotate(t, !i, i);
		}
	}
	if(t)list[t].height = max(ht(list[t].child[0]), ht(list[t].child[1])) + 1;
	if(t)list[t].size = sz(list[t].child[0]) + sz(list[t].child[1]) + 1;
	return t;
}
int move_down(int t,int rhs){
	if(t == 0)return rhs;
	list[t].child[1] = move_down(list[t].child[1], rhs);
	return balance(t);
}

int find(int t, const S* key){
	if(t == 0)return 0;
	int res = cmp(key, &list[t].key);
	if(res == 0)return t;
	if(res < 0) return find(list[t].child[0], key);
	return find(list[t].child[1], key);
}

int erase(int t, const S* key){
	if(t == 0)return 0;
	int res = cmp(key, &list[t].key);
	if(res == 0)return move_down(list[t].child[0], list[t].child[1]);
	if(res < 0)list[t].child[0] = erase(list[t].child[0], key);
	else list[t].child[1] = erase(list[t].child[1], key);
	list[t].size--;
	return balance(t);
}
int insert2(int t, int x){
	if(t == 0)return x;
	if(cmp(&list[x].key, &list[t].key) <= 0)list[t].child[0] = insert2(list[t].child[0], x);
	else list[t].child[1] = insert2(list[t].child[1], x);
	list[t].size++;
	return balance(t);
}
int insert(int root, const S* key, const T* value){
	++size;
	list[size].size = list[size].height = 1;
	memcpy(&list[size].key, key, sizeof(S));
	memcpy(&list[size].value, value, sizeof(T));
	return insert2(root, size);
}
int rank(int t, int k){
	if(!t)return 0;
	int m = sz(list[t].child[0]);
	if(k < m)return rank(list[t].child[0], k);
	if(k == m)return t;
	return rank(list[t].child[1], k-m-1);
}

速度

5〜10%くらい遅くなった。なんでやねん！！

verify

TopCode SRM 310 Div1 Medium