avl.c

本Linux网络应用程序采用客户-服务器模型,并发型交互。在OSI参考模型的传输层,通过调用TCP套接字(Socket)的各种函数,使服务器和各个客户端之间建立快速可靠的连接

	/* Have to remove node_to_delete = *nodeplace_to_delete. */
	if (node_to_delete->left == avl_empty) {
		*nodeplace_to_delete = node_to_delete->right;
		stack_ptr--;
		stack_count--;
	} else {
		struct avl_node ***stack_ptr_to_delete = stack_ptr;
		struct avl_node **nodeplace = &node_to_delete->left;
		struct avl_node *node;
		for (;;) {
			node = *nodeplace;
			if (node->right == avl_empty)
				break;
			*stack_ptr++ = nodeplace;
			stack_count++;
			nodeplace = &node->right;
		}
		*nodeplace = node->left;
		/* node replaces node_to_delete */
		node->left = node_to_delete->left;
		node->right = node_to_delete->right;
		node->height = node_to_delete->height;
		*nodeplace_to_delete = node;	/* replace node_to_delete */
		*stack_ptr_to_delete = &node->left;	/* replace &node_to_delete->avl_left */
	}
	avl_rebalance(stack_ptr, stack_count);
	return (0);
}

//#if (USER_SPACE)
#if (DEBUG_AVL)

/* print a tree */
static void printf_avl(struct avl_node *tree, short keylen)
{
	int i;

	if (tree != avl_empty) {
		printf("(%02x", tree->data[0]);
		for (i = 1; i < keylen; i++)
			printf(".%02x", tree->data[i]);
		if (tree->left != avl_empty) {
			printf_avl(tree->left, keylen);
			printf("<");
		}
		if (tree->right != avl_empty) {
			printf(">");
			printf_avl(tree->right, keylen);
		}
		printf(")\n");
	}
}

static char *avl_check_point = "somewhere";

/* check a tree's consistency and balancing */
static void avl_checkheights(struct avl_node *tree, short keylen)
{
	int h, hl, hr;

	if (tree == avl_empty)
		return;
	avl_checkheights(tree->left, keylen);
	avl_checkheights(tree->right, keylen);
	h = tree->height;
	hl = heightof(tree->left);
	hr = heightof(tree->right);
	if ((h == hl + 1) && (hr <= hl) && (hl <= hr + 1))
		return;
	if ((h == hr + 1) && (hl <= hr) && (hr <= hl + 1))
		return;
	printf("%s: avl_checkheights: heights inconsistent\n",
		   avl_check_point);
}

/* check that all values stored in a tree are < key */
static void avl_checkleft(struct avl_node *tree, unsigned char *key,
						  short keylen)
{
	if (tree == avl_empty)
		return;
	avl_checkleft(tree->left, key, keylen);
	avl_checkleft(tree->right, key, keylen);
	if (key_comp(tree->data, key, keylen) < 0)
		return;
	printf("%s: avl_checkleft: left key (0x%lx)>= top key\n",
		   avl_check_point, tree);
	print_avl_key("\tleft key:", tree->data, keylen);
	print_avl_key("\t top key:", key, keylen);
}

/* check that all values stored in a tree are > key */
static void avl_checkright(struct avl_node *tree, unsigned char *key,
						   short keylen)
{
	if (tree == avl_empty)
		return;
	avl_checkright(tree->left, key, keylen);
	avl_checkright(tree->right, key, keylen);
	if (key_comp(tree->data, key, keylen) > 0)
		return;
	printf("%s: avl_checkright: right key (0x%lx) <= top key\n",
		   avl_check_point, tree);
	print_avl_key("\tright key:", tree->data, keylen);
	print_avl_key("\t  top key:", key, keylen);
}

/* check that all values are properly increasing */
static void avl_checkorder(struct avl_node *tree, short keylen)
{
	if (tree == avl_empty)
		return;
	avl_checkorder(tree->left, keylen);
	avl_checkorder(tree->right, keylen);
	avl_checkleft(tree->left, tree->data, keylen);
	avl_checkright(tree->right, tree->data, keylen);
}

main()
{
	struct avl_instance test_avl;
	unsigned char check[0x0fffff];
	unsigned char *p;
	struct avl_node *free = NULL, *node, *node2, *nodetofree;
	int ops = 0, n_nodes = 0, n_mem = 0;
	int nodesize = AVL_NODE_LEN + 8;
	int key, key2;
	unsigned int i;
	unsigned char data[8];
	unsigned long t1, t2;

	memset(check, 0, 0x0fffff);
	avl_init(&test_avl, 20);
	free =
		(struct avl_node *) malloc((AVL_NODE_LEN + 20) *
									  (unsigned int) 0x0fffff);
	node = free;
	while (1) {
		key = rand() & 0x0fffff;
		if (check[key])
			continue;
		n_nodes++;

		p = node->data;
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		node =
			(struct avl_node *) ((unsigned char *) node +
									(AVL_NODE_LEN + 20));

		if (n_nodes >= 900000)
			break;
	}
	printf("key prepare phase 1 ok\n");

	node = free;
	for (i = 0; i < (unsigned int) 0x0fffff; i++) {
		if (check[i])
			continue;
		p = node->data;
		memcpy(p, &i, sizeof(int));

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;

		key = rand();
		memcpy(p, &key, sizeof(int));
		p += 4;
		node =
			(struct avl_node *) ((unsigned char *) node +
									(AVL_NODE_LEN + 20));
	}

	printf("key prepare phase 2 ok\n");

	t1 = time(NULL);
	node = free;
	for (i = 0; i < (unsigned int) 0x0fffff; i++) {
		if ((node2 = avl_insert(&test_avl, node)) != NULL) {
			fprintf(stderr, "insert error, key exist\n");
			print_avl_key("\t key1:", node->data, 20);
			print_avl_key("\t key1:", node->data, 20);
			abort();
		}
		node =
			(struct avl_node *) ((unsigned char *) node +
									(AVL_NODE_LEN + 20));
	}
	t2 = time(NULL);
	printf("Insert %ud nodes, use %d s, %d nodes per second\n",
		   (unsigned int) 0x0fffff, t2 - t1,
		   (unsigned int) 0x0fffff / (t2 - t1));

	t1 = time(NULL);
	node = free;
	for (i = 0; i < (unsigned int) 0x0fffff; i++) {
		if ((node2 = avl_find(&test_avl, node->data)) != node) {
			fprintf(stderr, "find error, different node\n");
			print_avl_key("\t key1:", node->data, 20);
			print_avl_key("\t key1:", node->data, 20);
			abort();
		}
		node =
			(struct avl_node *) ((unsigned char *) node +
									(AVL_NODE_LEN + 20));
	}
	t2 = time(NULL);
	printf("Find %ud nodes, use %d s, %d nodes per second\n",
		   (unsigned int) 0x0fffff, t2 - t1,
		   (unsigned int) 0x0fffff / (t2 - t1));

	t1 = time(NULL);
	node = free;
	for (i = 0; i < (unsigned int) 0x0fffff; i++) {
		avl_remove(&test_avl, node);
		if ((node2 = avl_insert(&test_avl, node)) != NULL) {
			fprintf(stderr, "insert error, key exist\n");
			print_avl_key("\t key1:", node->data, 20);
			print_avl_key("\t key1:", node->data, 20);
			abort();
		}
		node =
			(struct avl_node *) ((unsigned char *) node +
									(AVL_NODE_LEN + 20));
	}
	t2 = time(NULL);
	printf("RM/IN %ud nodes, use %d s, %d nodes per second\n",
		   (unsigned int) 0x0fffff, t2 - t1,
		   (unsigned int) 0x0fffff / (t2 - t1));

	return;
}

#endif							/* USER_SPACE */

/*
_Initialize avl tree;
*/
int init_avl_tree(struct avl_instance *avltr, int *p_trnodenum,
				  struct avl_node **p_freenode, int nodelen,
				  int cntnum, int nodekeylen)
{
	int mlctime;				/* malloc memory time */
	int mlcnum;					/* per malloc node record num */
	struct avl_node * node;
	int iloop, jloop;

	mlcnum = MAX_BLOCK_LEN / nodelen;
	if (cntnum % mlcnum)
		mlctime = (cntnum / mlcnum) + 1;
	else
		mlctime = (cntnum / mlcnum);

	*p_freenode = NULL;
	for (iloop = 0; iloop < mlctime; iloop++) {
		node = (struct avl_node *) malloc(MAX_BLOCK_LEN);
		if (!node) {
			fprintf(stderr,"malloc failed init tree,but malloced "
							"%d nodes.\n", *p_trnodenum);
			return -1;
		}
		memset(node, 0, MAX_BLOCK_LEN);
		for (jloop = 0; jloop < mlcnum; jloop++) {
			node->next = *p_freenode;
			*p_freenode = node;
			node = nodenext(node, nodelen);
			(* p_trnodenum)++;
		}
	}

	avl_init(avltr, nodekeylen);
	return 0;
}