net/bridge/br

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

DEFINITIONS
