URL https://opencores.org/ocsvn/or1k_old/or1k_old/trunk

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [uclinux/] [uClinux-2.0.x/] [net/] [bridge/] [br_tree.c] - Blame information for rev 1782

Details | Compare with Previous | View Log


/*
 * this code is derived from the avl functions in mmap.c
 */
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/string.h>
#include <linux/malloc.h>
#include <linux/skbuff.h>
 
#include <net/br.h>
#define _DEBUG_AVL
 
/*
 * 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 <haible@ma2s2.mathematik.uni-karlsruhe.de>.
 * Taken from mmap.c, extensively modified by John Hayes
 * <hayes@netplumbing.com>
 */
 
struct fdb fdb_head;
struct fdb *fhp = &fdb_head;
struct fdb **fhpp = &fhp;
static int fdb_inited = 0;
 
int addr_cmp(unsigned char *a1, unsigned char *a2);
 
/*
 * fdb_head is the AVL tree corresponding to fdb
 * or, more exactly, its root.
 * A fdb has the following fields:
 *   fdb_avl_left     left son of a tree node
 *   fdb_avl_right    right son of a tree node
 *   fdb_avl_height   1+max(heightof(left),heightof(right))
 * The empty tree is represented as NULL.
 */
 
#ifndef avl_br_empty
#define avl_br_empty    (struct fdb *) NULL
#endif
 
/* Since the trees are balanced, their height will never be large. */
#define avl_maxheight   127
#define heightof(tree)  ((tree) == avl_br_empty ? 0 : (tree)->fdb_avl_height)
/*
 * Consistency and balancing rules:
 * 1. tree->fdb_avl_height == 1+max(heightof(tree->fdb_avl_left),heightof(tree->fdb_avl_right))
 * 2. abs( heightof(tree->fdb_avl_left) - heightof(tree->fdb_avl_right) ) <= 1
 * 3. foreach node in tree->fdb_avl_left: node->fdb_avl_key <= tree->fdb_avl_key,
 *    foreach node in tree->fdb_avl_right: node->fdb_avl_key >= tree->fdb_avl_key.
 */
 
int
fdb_init(void)
{
        fdb_head.fdb_avl_height = 0;
        fdb_head.fdb_avl_left = (struct fdb *)0;
        fdb_head.fdb_avl_right = (struct fdb *)0;
        fdb_inited = 1;
        return(0);
}
 
struct fdb *
br_avl_find_addr(unsigned char addr[6])
{
        struct fdb * result = NULL;
        struct fdb * tree;
 
        if (!fdb_inited)
                fdb_init();
#if (DEBUG_AVL)
        printk("searching for ula %02x:%02x:%02x:%02x:%02x:%02x\n",
                addr[0],
                addr[1],
                addr[2],
                addr[3],
                addr[4],
                addr[5]);
#endif /* DEBUG_AVL */
        for (tree = &fdb_head ; ; ) {
                if (tree == avl_br_empty) {
#if (DEBUG_AVL)
                        printk("search failed, returning node 0x%x\n", (unsigned int)result);
#endif /* DEBUG_AVL */
                        return result;
                }
 
#if (DEBUG_AVL)
                printk("node 0x%x: checking ula %02x:%02x:%02x:%02x:%02x:%02x\n",
                        (unsigned int)tree,
                        tree->ula[0],
                        tree->ula[1],
                        tree->ula[2],
                        tree->ula[3],
                        tree->ula[4],
                        tree->ula[5]);
#endif /* DEBUG_AVL */
                if (addr_cmp(addr, tree->ula) == 0) {
#if (DEBUG_AVL)
                        printk("found node 0x%x\n", (unsigned int)tree);
#endif /* DEBUG_AVL */
                        return tree;
                }
                if (addr_cmp(addr, tree->ula) < 0) {
                        tree = tree->fdb_avl_left;
                } else {
                        tree = tree->fdb_avl_right;
                }
        }
}
 
/*
 * 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]->{fdb_avl_left|fdb_avl_right}.
 */
static void
br_avl_rebalance (struct fdb *** nodeplaces_ptr, int count)
{
        if (!fdb_inited)
                fdb_init();
        for ( ; count > 0 ; count--) {
                struct fdb ** nodeplace = *--nodeplaces_ptr;
                struct fdb * node = *nodeplace;
                struct fdb * nodeleft = node->fdb_avl_left;
                struct fdb * noderight = node->fdb_avl_right;
                int heightleft = heightof(nodeleft);
                int heightright = heightof(noderight);
                if (heightright + 1 < heightleft) {
                        /*                                                      */
                        /*                            *                         */
                        /*                          /   \                       */
                        /*                       n+2      n                     */
                        /*                                                      */
                        struct fdb * nodeleftleft = nodeleft->fdb_avl_left;
                        struct fdb * nodeleftright = nodeleft->fdb_avl_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->fdb_avl_left = nodeleftright;
                                nodeleft->fdb_avl_right = node;
                                nodeleft->fdb_avl_height = 1 + (node->fdb_avl_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->fdb_avl_right = nodeleftright->fdb_avl_left;
                                node->fdb_avl_left = nodeleftright->fdb_avl_right;
                                nodeleftright->fdb_avl_left = nodeleft;
                                nodeleftright->fdb_avl_right = node;
                                nodeleft->fdb_avl_height = node->fdb_avl_height = heightleftright;
                                nodeleftright->fdb_avl_height = heightleft;
                                *nodeplace = nodeleftright;
                        }
                } else if (heightleft + 1 < heightright) {
                        /* similar to the above, just interchange 'left' <--> 'right' */
                        struct fdb * noderightright = noderight->fdb_avl_right;
                        struct fdb * noderightleft = noderight->fdb_avl_left;
                        int heightrightleft = heightof(noderightleft);
                        if (heightof(noderightright) >= heightrightleft) {
                                node->fdb_avl_right = noderightleft;
                                noderight->fdb_avl_left = node;
                                noderight->fdb_avl_height = 1 + (node->fdb_avl_height = 1 + heightrightleft);
                                *nodeplace = noderight;
                        } else {
                                noderight->fdb_avl_left = noderightleft->fdb_avl_right;
                                node->fdb_avl_right = noderightleft->fdb_avl_left;
                                noderightleft->fdb_avl_right = noderight;
                                noderightleft->fdb_avl_left = node;
                                noderight->fdb_avl_height = node->fdb_avl_height = heightrightleft;
                                noderightleft->fdb_avl_height = heightright;
                                *nodeplace = noderightleft;
                        }
                } else {
                        int height = (heightleft<heightright ? heightright : heightleft) + 1;
                        if (height == node->fdb_avl_height)
                                break;
                        node->fdb_avl_height = height;
                }
        }
#ifdef DEBUG_AVL
        printk_avl(&fdb_head);
#endif /* DEBUG_AVL */
}
 
/* Insert a node into a tree. */
int
br_avl_insert (struct fdb * new_node)
{
        struct fdb ** nodeplace = fhpp;
        struct fdb ** stack[avl_maxheight];
        int stack_count = 0;
        struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
        if (!fdb_inited)
                fdb_init();
        for (;;) {
                struct fdb *node;
 
                node = *nodeplace;
                if (node == avl_br_empty)
                        break;
                *stack_ptr++ = nodeplace; stack_count++;
                if (addr_cmp(new_node->ula, node->ula) == 0) { /* update */
                /*
                 * Vova Oksman: There was the BUG, in case that port
                 * was changed we must to update it.
                 */
                        node->port = new_node->port;
                        node->flags = new_node->flags;
                        node->timer = new_node->timer;
                        return(0);
                }
                if (addr_cmp(new_node->ula, node->ula) < 0) {
                        nodeplace = &node->fdb_avl_left;
                } else {
                        nodeplace = &node->fdb_avl_right;
                }
        }
#if (DEBUG_AVL)
        printk("node 0x%x: adding ula %02x:%02x:%02x:%02x:%02x:%02x\n",
                (unsigned int)new_node,
                new_node->ula[0],
                new_node->ula[1],
                new_node->ula[2],
                new_node->ula[3],
                new_node->ula[4],
                new_node->ula[5]);
#endif /* (DEBUG_AVL) */
        new_node->fdb_avl_left = avl_br_empty;
        new_node->fdb_avl_right = avl_br_empty;
        new_node->fdb_avl_height = 1;
        *nodeplace = new_node;
#if (0) 
        br_avl_rebalance(stack_ptr,stack_count);
#endif /* (0) */
#ifdef DEBUG_AVL
        printk_avl(&fdb_head);
#endif /* DEBUG_AVL */
        return(1);
}
 
/* Removes a node out of a tree. */
int
br_avl_remove (struct fdb * node_to_delete)
{
        struct fdb ** nodeplace = fhpp;
        struct fdb ** stack[avl_maxheight];
        int stack_count = 0;
        struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
        struct fdb ** nodeplace_to_delete;
        if (!fdb_inited)
                fdb_init();
        for (;;) {
                struct fdb * node = *nodeplace;
                if (node == avl_br_empty) {
                        /* what? node_to_delete not found in tree? */
                        printk(KERN_ERR "br: avl_remove: node to delete not found in tree\n");
                        return(-1);
                }
                *stack_ptr++ = nodeplace; stack_count++;
                if (addr_cmp(node_to_delete->ula, node->ula) == 0)
                                break;
                if (addr_cmp(node_to_delete->ula, node->ula) < 0)
                        nodeplace = &node->fdb_avl_left;
                else
                        nodeplace = &node->fdb_avl_right;
        }
        nodeplace_to_delete = nodeplace;
        /* Have to remove node_to_delete = *nodeplace_to_delete. */
        if (node_to_delete->fdb_avl_left == avl_br_empty) {
                *nodeplace_to_delete = node_to_delete->fdb_avl_right;
                stack_ptr--; stack_count--;
        } else {
                struct fdb *** stack_ptr_to_delete = stack_ptr;
                struct fdb ** nodeplace = &node_to_delete->fdb_avl_left;
                struct fdb * node;
                for (;;) {
                        node = *nodeplace;
                        if (node->fdb_avl_right == avl_br_empty)
                                break;
                        *stack_ptr++ = nodeplace; stack_count++;
                        nodeplace = &node->fdb_avl_right;
                }
                *nodeplace = node->fdb_avl_left;
                /* node replaces node_to_delete */
                node->fdb_avl_left = node_to_delete->fdb_avl_left;
                node->fdb_avl_right = node_to_delete->fdb_avl_right;
                node->fdb_avl_height = node_to_delete->fdb_avl_height;
                *nodeplace_to_delete = node; /* replace node_to_delete */
                *stack_ptr_to_delete = &node->fdb_avl_left; /* replace &node_to_delete->fdb_avl_left */
        }
        br_avl_rebalance(stack_ptr,stack_count);
        return(0);
}
 
#ifdef DEBUG_AVL
 
/* print a tree */
static void printk_avl (struct fdb * tree)
{
        if (tree != avl_br_empty) {
                printk("(");
                printk("%02x:%02x:%02x:%02x:%02x:%02x",
                        tree->ula[0],
                        tree->ula[1],
                        tree->ula[2],
                        tree->ula[3],
                        tree->ula[4],
                        tree->ula[5]);
                if (tree->fdb_avl_left != avl_br_empty) {
                        printk_avl(tree->fdb_avl_left);
                        printk("<");
                }
                if (tree->fdb_avl_right != avl_br_empty) {
                        printk(">");
                        printk_avl(tree->fdb_avl_right);
                }
                printk(")\n");
        }
}
 
#if (0)
static char *avl_check_point = "somewhere";
 
/* check a tree's consistency and balancing */
static void avl_checkheights (struct fdb * tree)
{
        int h, hl, hr;
 
        if (tree == avl_br_empty)
                return;
        avl_checkheights(tree->fdb_avl_left);
        avl_checkheights(tree->fdb_avl_right);
        h = tree->fdb_avl_height;
        hl = heightof(tree->fdb_avl_left);
        hr = heightof(tree->fdb_avl_right);
        if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
                return;
        if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
                return;
        printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);
}
 
/* check that all values stored in a tree are < key */
static void avl_checkleft (struct fdb * tree, fdb_avl_key_t key)
{
        if (tree == avl_br_empty)
                return;
        avl_checkleft(tree->fdb_avl_left,key);
        avl_checkleft(tree->fdb_avl_right,key);
        if (tree->fdb_avl_key < key)
                return;
        printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);
}
 
/* check that all values stored in a tree are > key */
static void avl_checkright (struct fdb * tree, fdb_avl_key_t key)
{
        if (tree == avl_br_empty)
                return;
        avl_checkright(tree->fdb_avl_left,key);
        avl_checkright(tree->fdb_avl_right,key);
        if (tree->fdb_avl_key > key)
                return;
        printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);
}
 
/* check that all values are properly increasing */
static void avl_checkorder (struct fdb * tree)
{
        if (tree == avl_br_empty)
                return;
        avl_checkorder(tree->fdb_avl_left);
        avl_checkorder(tree->fdb_avl_right);
        avl_checkleft(tree->fdb_avl_left,tree->fdb_avl_key);
        avl_checkright(tree->fdb_avl_right,tree->fdb_avl_key);
}
 
#endif /* (0) */
#endif /* DEBUG_AVL */
 
int
addr_cmp(unsigned char a1[], unsigned char a2[])
{
        int i;
 
        for (i=0; i<6; i++) {
                if (a1[i] > a2[i]) return(1);
                if (a1[i] < a2[i]) return(-1);
        }
        return(0);
}
 

Browse

Tools

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [uclinux/] [uClinux-2.0.x/] [net/] [bridge/] [br_tree.c] - Blame information for rev 1782

Line No.	Rev	Author	Line
1	199	simons	`/*`
2			`* this code is derived from the avl functions in mmap.c`
3			`*/`
4			`#include <linux/kernel.h>`
5			`#include <linux/errno.h>`
6			`#include <linux/string.h>`
7			`#include <linux/malloc.h>`
8			`#include <linux/skbuff.h>`
9
10			`#include <net/br.h>`
11			`#define _DEBUG_AVL`
12
13			`/*`
14			`* Use an AVL (Adelson-Velskii and Landis) tree to speed up this search`
15			`* from O(n) to O(log n), where n is the number of ULAs.`
16			`* Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>.`
17			`* Taken from mmap.c, extensively modified by John Hayes`
18			`* <hayes@netplumbing.com>`
19			`*/`
20
21			`struct fdb fdb_head;`
22			`struct fdb *fhp = &fdb_head;`
23			`struct fdb **fhpp = &fhp;`
24			`static int fdb_inited = 0;`
25
26			`int addr_cmp(unsigned char a1, unsigned char a2);`
27
28			`/*`
29			`* fdb_head is the AVL tree corresponding to fdb`
30			`* or, more exactly, its root.`
31			`* A fdb has the following fields:`
32			`* fdb_avl_left left son of a tree node`
33			`* fdb_avl_right right son of a tree node`
34			`* fdb_avl_height 1+max(heightof(left),heightof(right))`
35			`* The empty tree is represented as NULL.`
36			`*/`
37
38			`#ifndef avl_br_empty`
39			`#define avl_br_empty (struct fdb *) NULL`
40			`#endif`
41
42			`/* Since the trees are balanced, their height will never be large. */`
43			`#define avl_maxheight 127`
44			`#define heightof(tree) ((tree) == avl_br_empty ? 0 : (tree)->fdb_avl_height)`
45			`/*`
46			`* Consistency and balancing rules:`
47			`* 1. tree->fdb_avl_height == 1+max(heightof(tree->fdb_avl_left),heightof(tree->fdb_avl_right))`
48			`* 2. abs( heightof(tree->fdb_avl_left) - heightof(tree->fdb_avl_right) ) <= 1`
49			`* 3. foreach node in tree->fdb_avl_left: node->fdb_avl_key <= tree->fdb_avl_key,`
50			`* foreach node in tree->fdb_avl_right: node->fdb_avl_key >= tree->fdb_avl_key.`
51			`*/`
52
53			`int`
54			`fdb_init(void)`
55			`{`
56			`fdb_head.fdb_avl_height = 0;`
57			`fdb_head.fdb_avl_left = (struct fdb *)0;`
58			`fdb_head.fdb_avl_right = (struct fdb *)0;`
59			`fdb_inited = 1;`
60			`return(0);`
61			`}`
62
63			`struct fdb *`
64			`br_avl_find_addr(unsigned char addr[6])`
65			`{`
66			`struct fdb * result = NULL;`
67			`struct fdb * tree;`
68
69			`if (!fdb_inited)`
70			`fdb_init();`
71			`#if (DEBUG_AVL)`
72			`printk("searching for ula %02x:%02x:%02x:%02x:%02x:%02x\n",`
73			`addr[0],`
74			`addr[1],`
75			`addr[2],`
76			`addr[3],`
77			`addr[4],`
78			`addr[5]);`
79			`#endif /* DEBUG_AVL */`
80			`for (tree = &fdb_head ; ; ) {`
81			`if (tree == avl_br_empty) {`
82			`#if (DEBUG_AVL)`
83			`printk("search failed, returning node 0x%x\n", (unsigned int)result);`
84			`#endif /* DEBUG_AVL */`
85			`return result;`
86			`}`
87
88			`#if (DEBUG_AVL)`
89			`printk("node 0x%x: checking ula %02x:%02x:%02x:%02x:%02x:%02x\n",`
90			`(unsigned int)tree,`
91			`tree->ula[0],`
92			`tree->ula[1],`
93			`tree->ula[2],`
94			`tree->ula[3],`
95			`tree->ula[4],`
96			`tree->ula[5]);`
97			`#endif /* DEBUG_AVL */`
98			`if (addr_cmp(addr, tree->ula) == 0) {`
99			`#if (DEBUG_AVL)`
100			`printk("found node 0x%x\n", (unsigned int)tree);`
101			`#endif /* DEBUG_AVL */`
102			`return tree;`
103			`}`
104			`if (addr_cmp(addr, tree->ula) < 0) {`
105			`tree = tree->fdb_avl_left;`
106			`} else {`
107			`tree = tree->fdb_avl_right;`
108			`}`
109			`}`
110			`}`
111
112			`/*`
113			`* Rebalance a tree.`
114			`* After inserting or deleting a node of a tree we have a sequence of subtrees`
115			`* nodes[0]..nodes[k-1] such that`
116			`* nodes[0] is the root and nodes[i+1] = nodes[i]->{fdb_avl_left\|fdb_avl_right}.`
117			`*/`
118			`static void`
119			`br_avl_rebalance (struct fdb *** nodeplaces_ptr, int count)`
120			`{`
121			`if (!fdb_inited)`
122			`fdb_init();`
123			`for ( ; count > 0 ; count--) {`
124			`struct fdb ** nodeplace = *--nodeplaces_ptr;`
125			`struct fdb * node = *nodeplace;`
126			`struct fdb * nodeleft = node->fdb_avl_left;`
127			`struct fdb * noderight = node->fdb_avl_right;`
128			`int heightleft = heightof(nodeleft);`
129			`int heightright = heightof(noderight);`
130			`if (heightright + 1 < heightleft) {`
131			`/* */`
132			`/* * */`
133			`/* / \ */`
134			`/* n+2 n */`
135			`/* */`
136			`struct fdb * nodeleftleft = nodeleft->fdb_avl_left;`
137			`struct fdb * nodeleftright = nodeleft->fdb_avl_right;`
138			`int heightleftright = heightof(nodeleftright);`
139			`if (heightof(nodeleftleft) >= heightleftright) {`
140			`/* */`
141			`/* * n+2\|n+3 */`
142			`/* / \ / \ */`
143			`/* n+2 n --> / n+1\|n+2 */`
144			`/* / \ \| / \ */`
145			`/* n+1 n\|n+1 n+1 n\|n+1 n */`
146			`/* */`
147			`node->fdb_avl_left = nodeleftright;`
148			`nodeleft->fdb_avl_right = node;`
149			`nodeleft->fdb_avl_height = 1 + (node->fdb_avl_height = 1 + heightleftright);`
150			`*nodeplace = nodeleft;`
151			`} else {`
152			`/* */`
153			`/* * n+2 */`
154			`/* / \ / \ */`
155			`/* n+2 n --> n+1 n+1 */`
156			`/* / \ / \ / \ */`
157			`/* n n+1 n L R n */`
158			`/* / \ */`
159			`/* L R */`
160			`/* */`
161			`nodeleft->fdb_avl_right = nodeleftright->fdb_avl_left;`
162			`node->fdb_avl_left = nodeleftright->fdb_avl_right;`
163			`nodeleftright->fdb_avl_left = nodeleft;`
164			`nodeleftright->fdb_avl_right = node;`
165			`nodeleft->fdb_avl_height = node->fdb_avl_height = heightleftright;`
166			`nodeleftright->fdb_avl_height = heightleft;`
167			`*nodeplace = nodeleftright;`
168			`}`
169			`} else if (heightleft + 1 < heightright) {`
170			`/* similar to the above, just interchange 'left' <--> 'right' */`
171			`struct fdb * noderightright = noderight->fdb_avl_right;`
172			`struct fdb * noderightleft = noderight->fdb_avl_left;`
173			`int heightrightleft = heightof(noderightleft);`
174			`if (heightof(noderightright) >= heightrightleft) {`
175			`node->fdb_avl_right = noderightleft;`
176			`noderight->fdb_avl_left = node;`
177			`noderight->fdb_avl_height = 1 + (node->fdb_avl_height = 1 + heightrightleft);`
178			`*nodeplace = noderight;`
179			`} else {`
180			`noderight->fdb_avl_left = noderightleft->fdb_avl_right;`
181			`node->fdb_avl_right = noderightleft->fdb_avl_left;`
182			`noderightleft->fdb_avl_right = noderight;`
183			`noderightleft->fdb_avl_left = node;`
184			`noderight->fdb_avl_height = node->fdb_avl_height = heightrightleft;`
185			`noderightleft->fdb_avl_height = heightright;`
186			`*nodeplace = noderightleft;`
187			`}`
188			`} else {`
189			`int height = (heightleft<heightright ? heightright : heightleft) + 1;`
190			`if (height == node->fdb_avl_height)`
191			`break;`
192			`node->fdb_avl_height = height;`
193			`}`
194			`}`
195			`#ifdef DEBUG_AVL`
196			`printk_avl(&fdb_head);`
197			`#endif /* DEBUG_AVL */`
198			`}`
199
200			`/* Insert a node into a tree. */`
201			`int`
202			`br_avl_insert (struct fdb * new_node)`
203			`{`
204			`struct fdb ** nodeplace = fhpp;`
205			`struct fdb ** stack[avl_maxheight];`
206			`int stack_count = 0;`
207			`struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */`
208			`if (!fdb_inited)`
209			`fdb_init();`
210			`for (;;) {`
211			`struct fdb *node;`
212
213			`node = *nodeplace;`
214			`if (node == avl_br_empty)`
215			`break;`
216			`*stack_ptr++ = nodeplace; stack_count++;`
217			`if (addr_cmp(new_node->ula, node->ula) == 0) { /* update */`
218			`/*`
219			`* Vova Oksman: There was the BUG, in case that port`
220			`* was changed we must to update it.`
221			`*/`
222			`node->port = new_node->port;`
223			`node->flags = new_node->flags;`
224			`node->timer = new_node->timer;`
225			`return(0);`
226			`}`
227			`if (addr_cmp(new_node->ula, node->ula) < 0) {`
228			`nodeplace = &node->fdb_avl_left;`
229			`} else {`
230			`nodeplace = &node->fdb_avl_right;`
231			`}`
232			`}`
233			`#if (DEBUG_AVL)`
234			`printk("node 0x%x: adding ula %02x:%02x:%02x:%02x:%02x:%02x\n",`
235			`(unsigned int)new_node,`
236			`new_node->ula[0],`
237			`new_node->ula[1],`
238			`new_node->ula[2],`
239			`new_node->ula[3],`
240			`new_node->ula[4],`
241			`new_node->ula[5]);`
242			`#endif /* (DEBUG_AVL) */`
243			`new_node->fdb_avl_left = avl_br_empty;`
244			`new_node->fdb_avl_right = avl_br_empty;`
245			`new_node->fdb_avl_height = 1;`
246			`*nodeplace = new_node;`
247			`#if (0)`
248			`br_avl_rebalance(stack_ptr,stack_count);`
249			`#endif /* (0) */`
250			`#ifdef DEBUG_AVL`
251			`printk_avl(&fdb_head);`
252			`#endif /* DEBUG_AVL */`
253			`return(1);`
254			`}`
255
256			`/* Removes a node out of a tree. */`
257			`int`
258			`br_avl_remove (struct fdb * node_to_delete)`
259			`{`
260			`struct fdb ** nodeplace = fhpp;`
261			`struct fdb ** stack[avl_maxheight];`
262			`int stack_count = 0;`
263			`struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */`
264			`struct fdb ** nodeplace_to_delete;`
265			`if (!fdb_inited)`
266			`fdb_init();`
267			`for (;;) {`
268			`struct fdb * node = *nodeplace;`
269			`if (node == avl_br_empty) {`
270			`/* what? node_to_delete not found in tree? */`
271			`printk(KERN_ERR "br: avl_remove: node to delete not found in tree\n");`
272			`return(-1);`
273			`}`
274			`*stack_ptr++ = nodeplace; stack_count++;`
275			`if (addr_cmp(node_to_delete->ula, node->ula) == 0)`
276			`break;`
277			`if (addr_cmp(node_to_delete->ula, node->ula) < 0)`
278			`nodeplace = &node->fdb_avl_left;`
279			`else`
280			`nodeplace = &node->fdb_avl_right;`
281			`}`
282			`nodeplace_to_delete = nodeplace;`
283			`/* Have to remove node_to_delete = nodeplace_to_delete. /`
284			`if (node_to_delete->fdb_avl_left == avl_br_empty) {`
285			`*nodeplace_to_delete = node_to_delete->fdb_avl_right;`
286			`stack_ptr--; stack_count--;`
287			`} else {`
288			`struct fdb *** stack_ptr_to_delete = stack_ptr;`
289			`struct fdb ** nodeplace = &node_to_delete->fdb_avl_left;`
290			`struct fdb * node;`
291			`for (;;) {`
292			`node = *nodeplace;`
293			`if (node->fdb_avl_right == avl_br_empty)`
294			`break;`
295			`*stack_ptr++ = nodeplace; stack_count++;`
296			`nodeplace = &node->fdb_avl_right;`
297			`}`
298			`*nodeplace = node->fdb_avl_left;`
299			`/* node replaces node_to_delete */`
300			`node->fdb_avl_left = node_to_delete->fdb_avl_left;`
301			`node->fdb_avl_right = node_to_delete->fdb_avl_right;`
302			`node->fdb_avl_height = node_to_delete->fdb_avl_height;`
303			`nodeplace_to_delete = node; / replace node_to_delete */`
304			`stack_ptr_to_delete = &node->fdb_avl_left; / replace &node_to_delete->fdb_avl_left */`
305			`}`
306			`br_avl_rebalance(stack_ptr,stack_count);`
307			`return(0);`
308			`}`
309
310			`#ifdef DEBUG_AVL`
311
312			`/* print a tree */`
313			`static void printk_avl (struct fdb * tree)`
314			`{`
315			`if (tree != avl_br_empty) {`
316			`printk("(");`
317			`printk("%02x:%02x:%02x:%02x:%02x:%02x",`
318			`tree->ula[0],`
319			`tree->ula[1],`
320			`tree->ula[2],`
321			`tree->ula[3],`
322			`tree->ula[4],`
323			`tree->ula[5]);`
324			`if (tree->fdb_avl_left != avl_br_empty) {`
325			`printk_avl(tree->fdb_avl_left);`
326			`printk("<");`
327			`}`
328			`if (tree->fdb_avl_right != avl_br_empty) {`
329			`printk(">");`
330			`printk_avl(tree->fdb_avl_right);`
331			`}`
332			`printk(")\n");`
333			`}`
334			`}`
335
336			`#if (0)`
337			`static char *avl_check_point = "somewhere";`
338
339			`/* check a tree's consistency and balancing */`
340			`static void avl_checkheights (struct fdb * tree)`
341			`{`
342			`int h, hl, hr;`
343
344			`if (tree == avl_br_empty)`
345			`return;`
346			`avl_checkheights(tree->fdb_avl_left);`
347			`avl_checkheights(tree->fdb_avl_right);`
348			`h = tree->fdb_avl_height;`
349			`hl = heightof(tree->fdb_avl_left);`
350			`hr = heightof(tree->fdb_avl_right);`
351			`if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))`
352			`return;`
353			`if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))`
354			`return;`
355			`printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);`
356			`}`
357
358			`/* check that all values stored in a tree are < key */`
359			`static void avl_checkleft (struct fdb * tree, fdb_avl_key_t key)`
360			`{`
361			`if (tree == avl_br_empty)`
362			`return;`
363			`avl_checkleft(tree->fdb_avl_left,key);`
364			`avl_checkleft(tree->fdb_avl_right,key);`
365			`if (tree->fdb_avl_key < key)`
366			`return;`
367			`printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);`
368			`}`
369
370			`/* check that all values stored in a tree are > key */`
371			`static void avl_checkright (struct fdb * tree, fdb_avl_key_t key)`
372			`{`
373			`if (tree == avl_br_empty)`
374			`return;`
375			`avl_checkright(tree->fdb_avl_left,key);`
376			`avl_checkright(tree->fdb_avl_right,key);`
377			`if (tree->fdb_avl_key > key)`
378			`return;`
379			`printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);`
380			`}`
381
382			`/* check that all values are properly increasing */`
383			`static void avl_checkorder (struct fdb * tree)`
384			`{`
385			`if (tree == avl_br_empty)`
386			`return;`
387			`avl_checkorder(tree->fdb_avl_left);`
388			`avl_checkorder(tree->fdb_avl_right);`
389			`avl_checkleft(tree->fdb_avl_left,tree->fdb_avl_key);`
390			`avl_checkright(tree->fdb_avl_right,tree->fdb_avl_key);`
391			`}`
392
393			`#endif /* (0) */`
394			`#endif /* DEBUG_AVL */`
395
396			`int`
397			`addr_cmp(unsigned char a1[], unsigned char a2[])`
398			`{`
399			`int i;`
400
401			`for (i=0; i<6; i++) {`
402			`if (a1[i] > a2[i]) return(1);`
403			`if (a1[i] < a2[i]) return(-1);`
404			`}`
405			`return(0);`
406			`}`
407