#include <u.h>#include <libc.h>#include <bst.h> enum {	NODES =    500000,	MAX =    10000000}; typedef struct Inode Inode; struct Inode {	Bst;	int v;}; void setup(int); int llrbinserts(Bsttree*);int avlinserts(Bsttree*);int nodecmp(Bst*, Bst*);int deletes(Bsttree*);int lookups(Bsttree*); voidmain(int argc, char **argv){	Bsttree *llrb, *avl;	int c, seq;	long start[4], stop[4]; 	seq = 0;	ARGBEGIN {	case 's':		seq = 1;		break;	} ARGEND 	setup(seq); 	avl = bstcreateavl(nodecmp);	llrb = bstcreatellrb(nodecmp); 	times(start);	c = llrbinserts(llrb);	times(stop);	print("LLRB:\nTime for %d insertions, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = avlinserts(avl);	times(stop);	print("AVL:\nTime for %d insertions, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = lookups(llrb);	times(stop);	print("LLRB:\nTime for %d lookups, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = lookups(avl);	times(stop);	print("AVL:\nTime for %d lookups, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = deletes(llrb);	times(stop);	print("LLRB:\nTime for %d deletions, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = deletes(avl);	times(stop);	print("AVL:\nTime for %d deletions, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = lookups(llrb);	times(stop);	print("LLRB:\nTime for %d lookups, %d successful: %ld\n", NODES, c, stop[0] - start[0]); 	times(start);	c = lookups(avl);	times(stop);	print("AVL:\nTime for %d lookups, %d successful: %ld\n", NODES, c, stop[0] - start[0]);} int rands[NODES];Inode llrbpool[NODES], avlpool[NODES]; voidsetup(int s){	int i; 	srand(time(nil));	for(i = 0; i < NODES; i++) {		if(s) {			rands[i] = i;			avlpool[i].v = i;		} else {			rands[i] = nrand(MAX);			avlpool[i].v = nrand(MAX);		}		llrbpool[i].v = avlpool[i].v;	}} intllrbinserts(Bsttree *t){	Inode *n, *ni;	int r; 	r = 0;	for(ni = llrbpool; ni < llrbpool+nelem(llrbpool); ni++) {		n = (Inode*)bstinsert(t, ni);		if(n == nil)			r++;	}	return r;} intavlinserts(Bsttree *t){	Inode *n, *ni;	int r; 	r = 0;	for(ni = avlpool; ni < avlpool+nelem(avlpool); ni++) {		n = (Inode*)bstinsert(t, ni);		if(n == nil)			r++;	}	return r;} intdeletes(Bsttree *t){	Inode n, *m;	int *i, r; 	r = 0;	for(i = rands; i < rands+nelem(rands); i++) {		n.v = *i;		m = (Inode*)bstdelete(t, &n);		if(m != nil)			r++;	}	return r;} intlookups(Bsttree *t){	Inode n, *m;	int *i, r; 	r = 0;	for(i = rands; i < rands+nelem(rands); i++) {		n.v = *i;		m = (Inode*)bstlookup(t, &n);		if(m != nil)			r++;	}	return r;} intnodecmp(Bst *a, Bst *b){	Inode *na, *nb; 	na = (Inode*)a;	nb = (Inode*)b; 	if(na->v < nb->v)		return -1;	if(na->v > nb->v)		return 1;	return 0;}