text: #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*);
  
  void
  main(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];
  
  void
  setup(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;
  	}
  }
  
  int
  llrbinserts(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;
  }
  
  int
  avlinserts(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;
  }
  
  int
  deletes(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;
  }
  
  int
  lookups(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;
  }
  
  int
  nodecmp(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;
  }
  