Sensix Wireless Sensor Network Middleware    Home    Project Page    Download    CVS  Hosted by

/home/brennan/Software/sensix/source/avl.c Go to the documentation of this file. /* * Copyright 2007. Los Alamos National Security, LLC. This material * was produced under U.S. Government contract DE-AC52-06NA25396 for * Los Alamos National Laboratory (LANL), which is operated by Los * Alamos National Security, LLC, for the Department of Energy. The * U.S. Government has rights to use, reproduce, and distribute this * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY, * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to * produce derivative works, such modified software should be clearly * marked, so as not to confuse it with the version available from LANL. * * Additionally, this program is free software; you can redistribute it * and/or modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. Accordingly, this * program is distributed in the hope it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * for more details. */ #ifdef __KERNEL__ # include <linux/slab.h> # include <linux/errno.h> # define avl_malloc(size) kmalloc(size, GFP_KERNEL) # define avl_free(ptr) kfree(ptr) # define avl_error(...) printk(KERN_ERR __VA_ARGS__) # define avl_log(...) printk(KERN_INFO __VA_ARGS__) # define return_errno(num) return (num < 0 ? num : (0 - num)) #else // userspace # include <stdio.h> # include <stdlib.h> # include <errno.h> # include <syslog.h> # define avl_malloc(size) malloc(size) # define avl_free(ptr) free(ptr) # define avl_error(...) syslog(LOG_ERR, __VA_ARGS__) # define avl_log(...) syslog(LOG_INFO, __VA_ARGS__) # define return_errno(num) do { errno = num; return -1; } while (0) #endif // __KERNEL__ #include "avl.h" struct avlnode { void *element; unsigned long key; struct avlnode *left, *right; struct avlnode *next, *prev; unsigned int height; }; enum { LEFT = 0, RIGHT = 1 }; static inline int maximum(int a, int b) { return a > b ? a : b; } static inline int height(struct avlnode *tree) { if (tree == NULL) { return_errno(EINVAL); } return tree->height; } static struct avlnode *rotate(struct avlnode *node, int direction) { struct avlnode *child; if (node == NULL) return NULL; if (direction == LEFT) { child = node->right; node->right = child->left; child->left = node; } else { child = node->left; node->left = child->right; child->right = node; } node->height = 1 + maximum(height(node->left), height(node->right)); child->height = 1 + maximum(height(child->left), height(child->right)); return child; } static struct avlnode *double_rotate(struct avlnode *node, int direction) { struct avlnode *child, *parent; if (node == NULL) return NULL; if (direction == LEFT) { child = node->right; parent = child->left; child->left = parent->right; parent->right = child; node->right = parent->left; parent->left = node; } else { child = node->left; parent = child->right; child->right = parent->left; parent->left = child; node->left = parent->right; parent->right = node; } parent->height = 1 + maximum(height(parent->left), height(parent->right)); node->height = 1 + maximum(height(node->left), height(node->right)); child->height = 1 + maximum(height(child->left), height(child->right)); return parent; } static struct avlnode *__find_min_node(struct avltree *tree) { struct avlnode *node; if (tree == NULL) return NULL; node = tree->root; if (node == NULL) return NULL; while (node->left != NULL) node = node->left; return node; } unsigned long avl_size(struct avltree *tree) { unsigned long i = 0; struct avlnode *list; for (list = __find_min_node(tree); list != NULL; list = list->next) i++; return i; } static struct avlnode *__find(unsigned long key, struct avltree *tree) { int i = 0; struct avlnode *node; if (tree == NULL) return NULL; node = tree->root; while (node != NULL) { if (key == node->key) break; if (key < node->key) node = node->left; else if (key > node->key) node = node->right; i++; } return node; } void *avl_find(unsigned long key, struct avltree *tree) { struct avlnode *node = __find(key, tree); if (node == NULL) return NULL; return node->element; } void *avl_find_min(struct avltree *tree) { struct avlnode *min = __find_min_node(tree); if (min == NULL) return NULL; return min->element; } struct avlnode *__find_max_node(struct avltree *tree) { struct avlnode *node; if (tree == NULL) return NULL; node = tree->root; if (node == NULL) return NULL; while (node->right != NULL) node = node->right; return node; } void *avl_find_max(struct avltree *tree) { struct avlnode *max = __find_max_node(tree); if (max == NULL) return NULL; return max->element; } static struct avlnode *__avl_ins(void *elt, unsigned long key, struct avlnode *tree, struct avlnode *parent, int direction, int *error) { if (tree == NULL) { tree = avl_malloc(sizeof(struct avlnode)); if (tree == NULL) { *error = 1; return NULL; } tree->key = key; tree->element = elt; tree->left = tree->right = NULL; tree->next = tree->prev = NULL; if (direction == LEFT) { tree->next = parent; tree->prev = parent->prev; if (parent->prev != NULL) parent->prev->next = tree; parent->prev = tree; } else if (direction == RIGHT) { tree->next = parent->next; tree->prev = parent; if (parent->next != NULL) parent->next->prev = tree; parent->next = tree; } } else if (key < tree->key) { tree->left = __avl_ins(elt, key, tree->left, tree, LEFT, error); if (height(tree->left) - height(tree->right) >= 2) { if (height(tree->left->left) - height(tree->left->right) >= 1) tree = rotate(tree, RIGHT); else if (height(tree->left->right) - height(tree->left->left) >= 1) tree = double_rotate(tree, RIGHT); } } else if (key > tree->key) { tree->right = __avl_ins(elt, key, tree->right, tree, RIGHT, error); if (height(tree->right) - height(tree->left) >= 2) { if (height(tree->right->right) - height(tree->right->left) >= 1) tree = rotate(tree, LEFT); else if (height(tree->right->left) - height(tree->right->right) >= 1) tree = double_rotate(tree, LEFT); } } else if (key == tree->key) { *error = 1; } tree->height = 1 + maximum(height(tree->left), height(tree->right)); return tree; } int avl_insert(void *elt, unsigned long key, struct avltree *tree) { int error = 0; if (tree == NULL || elt == NULL) { return_errno(EINVAL); } tree->root = __avl_ins(elt, key, tree->root, NULL, -1, &error); return error; } static struct avlnode *__avl_del(void *elt, unsigned long key, struct avlnode *tree, struct avlnode *parent, int direction, int *error) { if (tree == NULL) { *error = 1; return NULL; } else if (key == tree->key) { elt = tree->element; if (tree->next != NULL) tree->next->prev = tree->prev; if (tree->prev != NULL) tree->prev->next = tree->next; if (direction == LEFT) parent->left = NULL; else if (direction == RIGHT) parent->right = NULL; avl_free(tree); return NULL; } else if (key < tree->key) { tree->left = __avl_del(elt, key, tree->right, tree, LEFT, error); if (height(tree->left) - height(tree->right) >= 2) { if (height(tree->left->left) - height(tree->left->right) >= 1) tree = rotate(tree, RIGHT); else if (height(tree->left->right) - height(tree->left->left) >= 1) tree = double_rotate(tree, RIGHT); } } else if (key > tree->key) { tree->right = __avl_del(elt, key, tree->right, tree, RIGHT, error); if (height(tree->right) - height(tree->left) >= 2) { if (height(tree->right->right) - height(tree->right->left) >= 1) tree = rotate(tree, LEFT); else if (height(tree->right->left) - height(tree->right->right) >= 1) tree = double_rotate(tree, LEFT); } } tree->height = 1 + maximum(height(tree->left), height(tree->right)); return tree; } int avl_delete(void *elt, unsigned long key, struct avltree *tree) { int error = 0; if (tree == NULL) { return_errno(EINVAL); } tree->root = __avl_del(elt, key, tree->root, NULL, -1, &error); return error; } static void __destroy_branch(struct avlnode *root) { if (root != NULL) { __destroy_branch(root->left); __destroy_branch(root->right); avl_free(root); } } void destroy_avltree(struct avltree *tree) { if (tree != NULL) __destroy_branch(tree->root); } static void __avl_print(struct avlnode *tree, int direction, int indent) { int i; if (tree != NULL) { __avl_print(tree->right, RIGHT, indent + 1); for (i = 0; i < indent - 1; i++) avl_log(" "); if (indent) { if (direction == LEFT) avl_log(" \\-- "); else avl_log(" /-- "); } avl_log("%ld\n", tree->key); __avl_print(tree->left, LEFT, indent + 1); } } void avl_print(struct avltree *tree) { if (tree == NULL) return; avl_log("AVL tree: \n"); __avl_print(tree->root, -1, 0); } void avl_print_list(struct avltree *tree) { int i; struct avlnode *list = __find_min_node(tree); if (list == NULL) return; avl_log("Linked list: %ld ", list->key); for (i = 1, list = list->next; list != NULL; list = list->next, i++) avl_log("-> %ld ", list->key); avl_log("\n\n"); }

© 2008, Los Alamos National Security, LLC.