avl.c

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

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdarg.h>
#include <fcntl.h>
#include <time.h>
#include <sys/types.h>
#include <dirent.h>
#include <signal.h>
#include <errno.h>
#include <string.h>

//#include <log.h>

#include "avl.h"

#define DEBUG_AVL 0

#define	nodenext(node,len)	\
		((struct avl_node *)((unsigned char *)node + len))

/*
 * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search
 * from O(n) to O(log n), where n is the number of ULAs.
 * Written by Bruno Haible <[e-mail]>.
 * Taken from mmap.c, extensively modified by John Hayes 
 * <[e-mail]>
 * 98-02 Modified by Jean-Rene Peulve [e-mail]
 *		update port number when topology change
 *		return oldfdb when updating, for broadcast storm checking
 *		call addr_cmp once per node
 */


#define avl_empty	(struct avl_node *) NULL

/* Since the trees are balanced, their height will never be large. */
#define avl_maxheight	127
#define heightof(tree)	((tree) == avl_empty ? 0 : (tree)->height)
/*
 * Consistency and balancing rules:
 * 1. tree->avl_height == 1+max(heightof(tree->avl_left),heightof(tree->avl_right))
 * 2. abs( heightof(tree->avl_left) - heightof(tree->avl_right) ) <= 1
 * 3. foreach node in tree->avl_left: node->avl_key <= tree->avl_key,
 *    foreach node in tree->avl_right: node->avl_key >= tree->avl_key.
 */

void avl_init(struct avl_instance *tree, short keylen)
{
/*
	tree->head.height = 0;
	tree->head.left = (struct avl_node *)0;
	tree->head.right = (struct avl_node *)0;
*/
	tree->keylen = keylen;
	tree->fhp = avl_empty;
	tree->fhpp = &tree->fhp;
	return;
}


#if (DEBUG_AVL)
static void print_avl_key(char *info, unsigned char *key, short len)
{
	printf("%s %02x", info, *(key++));
	while (len > 1) {
		printf(".%02x", *(key++));
		len--;
	}
	printf("\n");
}
#endif


static inline int key_comp(unsigned char *key1, unsigned char *key2,
						   short len)
{
	while (len > 0) {
		if (*key1 > *key2)
			return (1);
		if (*key1 < *key2)
			return (-1);
		key1++;
		key2++;
		len--;
	}
	return 0;
}

struct avl_node *avl_find(struct avl_instance *fai,
								unsigned char *key)
{
	struct avl_node *result = NULL;
	struct avl_node *tree;
	int cmp;

#if (DEBUG_AVL)
	print_avl_key("avl searching for key", key, fai->keylen);
#endif							/* DEBUG_AVL */

	for (tree = fai->fhp;;) {
		if (tree == avl_empty) {

#if (DEBUG_AVL)
			printf("search failed, returning node 0x%x\n",
				   (unsigned int) result);
#endif							/* DEBUG_AVL */

			return result;
		}
#if (DEBUG_AVL)
		printf("node 0x%x: ", tree);
		print_avl_key("checking key", tree->data, fai->keylen);
#endif							/* DEBUG_AVL */

		cmp = key_comp(key, tree->data, fai->keylen);
		switch (cmp) {
		case 0:
#if (DEBUG_AVL)
			printf("found node 0x%x\n", (unsigned int) tree);
#endif							/* DEBUG_AVL */
			return tree;
		case -1:
			tree = tree->left;
			break;
		case 1:
			tree = tree->right;
			break;
		default:
			printf("avl_find error : unrecognized return code from key_comp() : %d\n", cmp);
			return NULL;
		}
	}
}


/*
 * Rebalance a tree.
 * After inserting or deleting a node of a tree we have a sequence of subtrees
 * nodes[0]..nodes[k-1] such that
 * nodes[0] is the root and nodes[i+1] = nodes[i]->{avl_left|avl_right}.
 */
static void avl_rebalance(struct avl_node ***nodeplaces_ptr,
							 int count)
{
	for (; count > 0; count--) {
		struct avl_node **nodeplace = *--nodeplaces_ptr;
		struct avl_node *node = *nodeplace;
		struct avl_node *nodeleft = node->left;
		struct avl_node *noderight = node->right;
		int heightleft = heightof(nodeleft);
		int heightright = heightof(noderight);
		if (heightright + 1 < heightleft) {
			/*                                                      */
			/*                            *                         */
			/*                          /   \                       */
			/*                       n+2      n                     */
			/*                                                      */
			struct avl_node *nodeleftleft = nodeleft->left;
			struct avl_node *nodeleftright = nodeleft->right;
			int heightleftright = heightof(nodeleftright);
			if (heightof(nodeleftleft) >= heightleftright) {
				/*                                                        */
				/*                *                    n+2|n+3            */
				/*              /   \                  /    \             */
				/*           n+2      n      -->      /   n+1|n+2         */
				/*           / \                      |    /    \         */
				/*         n+1 n|n+1                 n+1  n|n+1  n        */
				/*                                                        */
				node->left = nodeleftright;
				nodeleft->right = node;
				nodeleft->height = 1 + (node->height =
										1 + heightleftright);
				*nodeplace = nodeleft;
			} else {
				/*                                                        */
				/*                *                     n+2               */
				/*              /   \                 /     \             */
				/*           n+2      n      -->    n+1     n+1           */
				/*           / \                    / \     / \           */
				/*          n  n+1                 n   L   R   n          */
				/*             / \                                        */
				/*            L   R                                       */
				/*                                                        */
				nodeleft->right = nodeleftright->left;
				node->left = nodeleftright->right;
				nodeleftright->left = nodeleft;
				nodeleftright->right = node;
				nodeleft->height = node->height = heightleftright;
				nodeleftright->height = heightleft;
				*nodeplace = nodeleftright;
			}
		} else if (heightleft + 1 < heightright) {
			/* similar to the above, just interchange 'left' <--> 'right' */
			struct avl_node *noderightright = noderight->right;
			struct avl_node *noderightleft = noderight->left;
			int heightrightleft = heightof(noderightleft);
			if (heightof(noderightright) >= heightrightleft) {
				node->right = noderightleft;
				noderight->left = node;
				noderight->height = 1 + (node->height =
										 1 + heightrightleft);
				*nodeplace = noderight;
			} else {
				noderight->left = noderightleft->right;
				node->right = noderightleft->left;
				noderightleft->right = noderight;
				noderightleft->left = node;
				noderight->height = node->height = heightrightleft;
				noderightleft->height = heightright;
				*nodeplace = noderightleft;
			}
		} else {
			int height =
				(heightleft < heightright ? heightright : heightleft) + 1;
			if (height == node->height)
				break;
			node->height = height;
		}
	}
}

/* Insert a node into a tree.
 * Performance improvement:
 *	 call addr_cmp() only once per node and use result in a switch.
 * Return old node address if we knew that MAC address already
 * Return NULL if we insert the new node
 */
struct avl_node *avl_insert(struct avl_instance *fai,
								  struct avl_node *new_node)
{
	struct avl_node **nodeplace = fai->fhpp;
	struct avl_node **stack[avl_maxheight];
	int stack_count = 0;
	struct avl_node ***stack_ptr = &stack[0];	/* = &stack[stackcount] */
	for (;;) {
		struct avl_node *node;

		node = *nodeplace;
		if (node == avl_empty)
			break;
		*stack_ptr++ = nodeplace;
		stack_count++;
		switch (key_comp(new_node->data, node->data, fai->keylen)) {
		case 0:				/* node with the same key exist */
			return node;		/* return the node in tree to caller */
		case 1:				/* new_node->key > node->key */
			nodeplace = &node->right;
			break;
		default:				/* -1 => new_node->key < node->key */
			nodeplace = &node->left;
		}
	}

#if (DEBUG_AVL)
	printf("node 0x%x: ", (unsigned int) new_node);
	print_avl_key("adding key", new_node->data, fai->keylen);
#endif							/* (DEBUG_AVL) */

	new_node->left = avl_empty;
	new_node->right = avl_empty;
	new_node->height = 1;
	*nodeplace = new_node;
	avl_rebalance(stack_ptr, stack_count);

	return NULL;				/* this is a new node */
}


/* Removes a node out of a tree. */
int avl_remove(struct avl_instance *fai,
				  struct avl_node *node_to_delete)
{
	struct avl_node **nodeplace = fai->fhpp;
	struct avl_node **stack[avl_maxheight];
	int stack_count = 0;
	struct avl_node ***stack_ptr = &stack[0];	/* = &stack[stackcount] */
	struct avl_node **nodeplace_to_delete;
	int cmp;

	for (;;) {
		struct avl_node *node = *nodeplace;
		if (node == avl_empty) {
			/* what? node_to_delete not found in tree? */
			printf
				("avl: avl_remove: node to delete not found in tree\n");
			return (-1);
		}
		*stack_ptr++ = nodeplace;
		stack_count++;
		cmp = key_comp(node_to_delete->data, node->data, fai->keylen);

		if (cmp == 0)
			break;
		if (cmp < 0)
			nodeplace = &node->left;
		else
			nodeplace = &node->right;
	}
	nodeplace_to_delete = nodeplace;