N-sim
Emulation and simulation of
Wireless Sensor Networks



   Home


   Project Page


   Download


   CVS



   Installation


   Configuration


   Plug-ins




 Hosted by
SourceForge.net Logo

/home/brennan/n-sim/OrbisQuartus/server/xen/backend/avl.c

Go to the documentation of this file.
00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 
00036 #include "oq_alloc.h"
00037 #include "avl.h"
00038 
00039 
00040 #ifdef __KERNEL__
00041 # include <linux/kernel.h>
00042 # define OQ_PRINT(fmt, args...)   printk(KERN_INFO fmt, ## args)
00043 # define OQ_PRINTLN(fmt, args...) printk(KERN_INFO "orbisquartus: " fmt, ## args)
00044 #else
00045 # include <stdio.h>
00046 # define OQ_PRINT(fmt, args...)   fprintf(stderr, fmt, ## args)
00047 # define OQ_PRINTLN(fmt, args...) fprintf(stderr, fmt, ## args)
00048 #endif
00049 
00050 
00051 enum { LEFT = 0, RIGHT = 1 };
00052 
00053 
00054 static inline int maximum(int a, int b)
00055 {
00056         return a > b ? a :b;
00057 }
00058 
00059 static inline int height(struct avlnode *tree)
00060 {
00061         if (tree == NULL)
00062                 return -1;
00063         return tree->height;
00064 }
00065 
00066 
00067 static struct avlnode *rotate(struct avlnode *node, int direction)
00068 {
00069         struct avlnode *child;
00070         if (node == NULL)
00071                 return NULL;
00072 
00073         if (direction == LEFT) {
00074                 child = node->right;
00075                 node->right = child->left;
00076                 child->left = node;
00077         } else {
00078                 child = node->left;
00079                 node->left = child->right;
00080                 child->right = node;
00081         }
00082 
00083         node->height = 1 + maximum(height(node->left), height(node->right));
00084         child->height = 1 + maximum(height(child->left), height(child->right));
00085 
00086         return child;
00087 }
00088 
00089 
00090 static struct avlnode *double_rotate(struct avlnode *node, int direction)
00091 {
00092         struct avlnode *child, *parent;
00093         if (node == NULL)
00094                 return NULL;
00095 
00096         if (direction == LEFT) {
00097                 child = node->right;
00098                 parent = child->left;
00099                 child->left = parent->right;
00100                 parent->right = child;
00101                 node->right = parent->left;
00102                 parent->left = node;
00103         } else {
00104                 child = node->left;
00105                 parent = child->right;
00106                 child->right = parent->left;
00107                 parent->left = child;
00108                 node->left = parent->right;
00109                 parent->right = node;
00110         }
00111         parent->height = 1 + maximum(height(parent->left), 
00112                                      height(parent->right));
00113         node->height = 1 + maximum(height(node->left), height(node->right));
00114         child->height = 1 + maximum(height(child->left), height(child->right));
00115 
00116         return parent;
00117 }
00118 
00119 
00120 
00121 
00122 
00123 unsigned long avl_size(struct avltree *tree)
00124 {
00125         unsigned long i = 0;
00126         struct avlnode *list = avl_find_min(tree);
00127 
00128         if (list == NULL)
00129                 return i;
00130 
00131         for (; list != NULL; list = list->next)
00132                 i++;
00133 
00134         return i;
00135 }
00136 
00137 
00138 struct avlnode *avl_find(unsigned long key, struct avltree *tree)
00139 {
00140         int i = 0;
00141         struct avlnode *node;
00142 
00143         if (tree == NULL)
00144                 return NULL;
00145         node = tree->root;
00146 
00147         while (node != NULL) {
00148                 if (key == node->key)
00149                         break;
00150                 if (key < node->key)
00151                         node = node->left;
00152                 else if (key > node->key)
00153                         node = node->right;
00154                 i++;
00155         }
00156         return node;
00157 }
00158 
00159 
00160 void *avl_retrieve(unsigned long key, struct avltree *tree)
00161 {
00162         struct avlnode *node;
00163         if ((node = avl_find(key, tree)) == NULL)
00164                 return NULL;
00165         return node->element;
00166 }
00167 
00168 
00169 struct avlnode *avl_find_min(struct avltree *tree)
00170 {
00171         struct avlnode *node;
00172 
00173         if (tree == NULL)
00174                 return NULL;
00175 
00176         node = tree->root;
00177         if (node == NULL)
00178                 return NULL;
00179 
00180         while (node->left != NULL)
00181                 node = node->left;
00182 
00183         return node;
00184 }
00185 
00186 
00187 struct avlnode *avl_find_max(struct avltree *tree)
00188 {
00189         struct avlnode *node;
00190 
00191         if (tree == NULL)
00192                 return NULL;
00193 
00194         node = tree->root;
00195         if (node == NULL)
00196                 return NULL;
00197 
00198         while (node->right != NULL)
00199                 node = node->right;
00200 
00201         return node;
00202 }
00203 
00204 
00205 
00206 static struct avlnode *__avl_ins(void *elt, unsigned long key, 
00207                                  struct avlnode *tree, struct avlnode *parent, 
00208                                  int direction, int *error)
00209 {
00210         if (tree == NULL) {
00211                 tree = (struct avlnode *) OQ_ALLOCATE(sizeof(struct avlnode));
00212                 if (tree == NULL) {
00213                         *error = 1;
00214                         return NULL;
00215                 }
00216                 tree->key = key;
00217                 tree->element = elt;
00218                 tree->left = tree->right = NULL;
00219 
00220                 if (direction == LEFT) {
00221                         tree->next = parent;
00222                         tree->prev = parent->prev;
00223                         if (parent->prev != NULL)
00224                                 parent->prev->next = tree;
00225                         parent->prev = tree;
00226                 } else if (direction == RIGHT) {
00227                         tree->next = parent->next;
00228                         tree->prev = parent;
00229                         if (parent->next != NULL)
00230                                 parent->next->prev = tree;
00231                         parent->next = tree;
00232                 } else {
00233                         tree->next = tree->prev = NULL;
00234                 }
00235         } else if (key < tree->key) {
00236                 tree->left = __avl_ins(elt, key, tree->left, tree, 
00237                                        LEFT, error);
00238 
00239                 if (height(tree->left) - height(tree->right) >= 2) {
00240                         if (height(tree->left->left) - 
00241                             height(tree->left->right) >= 1)
00242                                 tree = rotate(tree, RIGHT);
00243                         else if (height(tree->left->right) - 
00244                                  height(tree->left->left) >= 1)
00245                                 tree = double_rotate(tree, RIGHT);
00246                 }
00247         } else if (key > tree->key) {
00248                 tree->right = __avl_ins(elt, key, tree->right, tree, 
00249                                         RIGHT, error);
00250 
00251                 if (height(tree->right) - height(tree->left) >= 2) {
00252                         if (height(tree->right->right) - 
00253                             height(tree->right->left) >= 1)
00254                                 tree = rotate(tree, LEFT);
00255                         else if (height(tree->right->left) - 
00256                                  height(tree->right->right) >= 1)
00257                                 tree = double_rotate(tree, LEFT);
00258                 }
00259         } else if (key == tree->key) {
00260                 *error = 1;
00261         }
00262 
00263         tree->height = 1 + maximum(height(tree->left), height(tree->right));
00264         return tree;
00265 }
00266 
00267 
00268 
00269 int avl_insert(void *elt, unsigned long key, struct avltree *tree)
00270 {
00271         int error = 0;
00272         if (tree == NULL || elt == NULL)
00273                 return -1;
00274 
00275         tree->root = __avl_ins(elt, key, tree->root, NULL, -1, &error);
00276         return error;
00277 }
00278 
00279 
00280 
00281 static struct avlnode *__avl_del(void *elt, unsigned long key, 
00282                                  struct avlnode *tree, struct avlnode *parent,
00283                                  int direction, int *error)
00284 {
00285         if (tree == NULL) {
00286                 *error = 1;
00287                 return NULL;
00288         } else if (key == tree->key) {
00289                 if (tree->next != NULL)
00290                         tree->next->prev = tree->prev;
00291                 if (tree->prev != NULL)
00292                         tree->prev->next = tree->next;
00293                 if (direction == LEFT)
00294                         parent->left = NULL;
00295                 else if (direction == RIGHT)
00296                         parent->right = NULL;
00297                 OQ_FREE(tree);
00298                 return NULL;
00299         } else if (key < tree->key) {
00300                 tree->left = __avl_del(elt, key, tree->right, tree, 
00301                                        LEFT, error);
00302 
00303                 if (height(tree->left) - height(tree->right) >= 2) {
00304                         if (height(tree->left->left) - 
00305                             height(tree->left->right) >= 1)
00306                                 tree = rotate(tree, RIGHT);
00307                         else if (height(tree->left->right) - 
00308                                  height(tree->left->left) >= 1)
00309                                 tree = double_rotate(tree, RIGHT);
00310                 }
00311         } else if (key > tree->key) {
00312                 tree->right = __avl_del(elt, key, tree->right, tree, 
00313                                         RIGHT, error);
00314 
00315                 if (height(tree->right) - height(tree->left) >= 2) {
00316                         if (height(tree->right->right) - 
00317                             height(tree->right->left) >= 1)
00318                                 tree = rotate(tree, LEFT);
00319                         else if (height(tree->right->left) - 
00320                                  height(tree->right->right) >= 1)
00321                                 tree = double_rotate(tree, LEFT);
00322                 }
00323         }
00324 
00325         tree->height = 1 + maximum(height(tree->left), height(tree->right));
00326         return tree;
00327 }
00328 
00329 
00330 int avl_delete(void *elt, unsigned long key, struct avltree *tree)
00331 {
00332         int error = 0;
00333         if (tree == NULL)
00334                 return -1;
00335 
00336         tree->root = __avl_del(elt, key, tree->root, NULL, -1, &error);
00337         return error;
00338 }
00339 
00340 
00341 
00342 void destroy_avltree(struct avlnode *root)
00343 {
00344         if (root != NULL) {
00345                 destroy_avltree(root->left);
00346                 destroy_avltree(root->right);
00347                 OQ_FREE(root);
00348         }
00349 }
00350 
00351 
00352 
00353 
00354 
00355 static void __avl_print(struct avlnode *tree, int direction, int indent)
00356 {
00357         int i;
00358         if (tree != NULL) {
00359                 __avl_print(tree->right, RIGHT, indent + 1);
00360 
00361                 for (i = 0; i < indent - 1; i++)
00362                         OQ_PRINT("    ");
00363                 if (indent) {
00364                         if (direction == LEFT)
00365                                 OQ_PRINT(" \\-- ");
00366                         else 
00367                                 OQ_PRINT(" /-- ");
00368                 }
00369                 OQ_PRINT("%ld\n", tree->key);
00370 
00371                 __avl_print(tree->left, LEFT, indent + 1);
00372         }
00373 }
00374 
00375 void avl_print(struct avltree *tree)
00376 {
00377         if (tree == NULL)
00378                 return;
00379 
00380         OQ_PRINTLN("AVL tree: \n");
00381         __avl_print(tree->root, -1, 0);
00382 }
00383 
00384 
00385 void avl_print_list(struct avltree *tree)
00386 {
00387         int i;
00388         struct avlnode *list = avl_find_min(tree);
00389 
00390         if (list == NULL)
00391                 return;
00392 
00393         OQ_PRINTLN("Linked list:  %ld ", list->key);
00394         for (i = 1, list = list->next; list != NULL; list = list->next, i++)
00395                 OQ_PRINT("-> %ld ", list->key);
00396         OQ_PRINT("\n\n");
00397 }


© 2007, Los Alamos National Security, LLC.