+++ /dev/null
-/**
- * collectd - src/utils_avltree.c
- * Copyright (C) 2006,2007 Florian octo Forster
- *
- * Permission is hereby granted, free of charge, to any person obtaining a
- * copy of this software and associated documentation files (the "Software"),
- * to deal in the Software without restriction, including without limitation
- * the rights to use, copy, modify, merge, publish, distribute, sublicense,
- * and/or sell copies of the Software, and to permit persons to whom the
- * Software is furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
- * DEALINGS IN THE SOFTWARE.
- *
- * Authors:
- * Florian octo Forster <octo at collectd.org>
- **/
-
-#include <assert.h>
-#include <stdlib.h>
-
-#include "utils_avltree.h"
-
-#define BALANCE(n) \
- ((((n)->left == NULL) ? 0 : (n)->left->height) - \
- (((n)->right == NULL) ? 0 : (n)->right->height))
-
-/*
- * private data types
- */
-struct c_avl_node_s {
- void *key;
- void *value;
-
- int height;
- struct c_avl_node_s *left;
- struct c_avl_node_s *right;
- struct c_avl_node_s *parent;
-};
-typedef struct c_avl_node_s c_avl_node_t;
-
-struct c_avl_tree_s {
- c_avl_node_t *root;
- int (*compare)(const void *, const void *);
- int size;
-};
-
-struct c_avl_iterator_s {
- c_avl_tree_t *tree;
- c_avl_node_t *node;
-};
-
-/*
- * private functions
- */
-#if 0
-static void verify_tree (c_avl_node_t *n)
-{
- if (n == NULL)
- return;
-
- verify_tree (n->left);
- verify_tree (n->right);
-
- assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
- assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
-} /* void verify_tree */
-#else
-#define verify_tree(n) /**/
-#endif
-
-static void free_node(c_avl_node_t *n) {
- if (n == NULL)
- return;
-
- if (n->left != NULL)
- free_node(n->left);
- if (n->right != NULL)
- free_node(n->right);
-
- free(n);
-}
-
-static int calc_height(c_avl_node_t *n) {
- int height_left;
- int height_right;
-
- if (n == NULL)
- return (0);
-
- height_left = (n->left == NULL) ? 0 : n->left->height;
- height_right = (n->right == NULL) ? 0 : n->right->height;
-
- return (((height_left > height_right) ? height_left : height_right) + 1);
-} /* int calc_height */
-
-static c_avl_node_t *search(c_avl_tree_t *t, const void *key) {
- c_avl_node_t *n;
- int cmp;
-
- n = t->root;
- while (n != NULL) {
- cmp = t->compare(key, n->key);
- if (cmp == 0)
- return (n);
- else if (cmp < 0)
- n = n->left;
- else
- n = n->right;
- }
-
- return (NULL);
-}
-
-/* (x) (y)
- * / \ / \
- * (y) /\ /\ (x)
- * / \ /_c\ ==> / a\ / \
- * /\ /\ /____\/\ /\
- * / a\ /_b\ /_b\ /_c\
- * /____\
- */
-static c_avl_node_t *rotate_right(c_avl_tree_t *t, c_avl_node_t *x) {
- c_avl_node_t *p;
- c_avl_node_t *y;
- c_avl_node_t *b;
-
- assert(x != NULL);
- assert(x->left != NULL);
-
- p = x->parent;
- y = x->left;
- b = y->right;
-
- x->left = b;
- if (b != NULL)
- b->parent = x;
-
- x->parent = y;
- y->right = x;
-
- y->parent = p;
- assert((p == NULL) || (p->left == x) || (p->right == x));
- if (p == NULL)
- t->root = y;
- else if (p->left == x)
- p->left = y;
- else
- p->right = y;
-
- x->height = calc_height(x);
- y->height = calc_height(y);
-
- return (y);
-} /* void rotate_right */
-
-/*
- * (x) (y)
- * / \ / \
- * /\ (y) (x) /\
- * /_a\ / \ ==> / \ / c\
- * /\ /\ /\ /\/____\
- * /_b\ / c\ /_a\ /_b\
- * /____\
- */
-static c_avl_node_t *rotate_left(c_avl_tree_t *t, c_avl_node_t *x) {
- c_avl_node_t *p;
- c_avl_node_t *y;
- c_avl_node_t *b;
-
- assert(x != NULL);
- assert(x->right != NULL);
-
- p = x->parent;
- y = x->right;
- b = y->left;
-
- x->right = b;
- if (b != NULL)
- b->parent = x;
-
- x->parent = y;
- y->left = x;
-
- y->parent = p;
- assert((p == NULL) || (p->left == x) || (p->right == x));
- if (p == NULL)
- t->root = y;
- else if (p->left == x)
- p->left = y;
- else
- p->right = y;
-
- x->height = calc_height(x);
- y->height = calc_height(y);
-
- return (y);
-} /* void rotate_left */
-
-static c_avl_node_t *rotate_left_right(c_avl_tree_t *t, c_avl_node_t *x) {
- rotate_left(t, x->left);
- return (rotate_right(t, x));
-} /* void rotate_left_right */
-
-static c_avl_node_t *rotate_right_left(c_avl_tree_t *t, c_avl_node_t *x) {
- rotate_right(t, x->right);
- return (rotate_left(t, x));
-} /* void rotate_right_left */
-
-static void rebalance(c_avl_tree_t *t, c_avl_node_t *n) {
- int b_top;
- int b_bottom;
-
- while (n != NULL) {
- b_top = BALANCE(n);
- assert((b_top >= -2) && (b_top <= 2));
-
- if (b_top == -2) {
- assert(n->right != NULL);
- b_bottom = BALANCE(n->right);
- assert((b_bottom >= -1) && (b_bottom <= 1));
- if (b_bottom == 1)
- n = rotate_right_left(t, n);
- else
- n = rotate_left(t, n);
- } else if (b_top == 2) {
- assert(n->left != NULL);
- b_bottom = BALANCE(n->left);
- assert((b_bottom >= -1) && (b_bottom <= 1));
- if (b_bottom == -1)
- n = rotate_left_right(t, n);
- else
- n = rotate_right(t, n);
- } else {
- int height = calc_height(n);
- if (height == n->height)
- break;
- n->height = height;
- }
-
- assert(n->height == calc_height(n));
-
- n = n->parent;
- } /* while (n != NULL) */
-} /* void rebalance */
-
-static c_avl_node_t *c_avl_node_next(c_avl_node_t *n) {
- c_avl_node_t *r; /* return node */
-
- if (n == NULL) {
- return (NULL);
- }
-
- /* If we can't descent any further, we have to backtrack to the first
- * parent that's bigger than we, i. e. who's _left_ child we are. */
- if (n->right == NULL) {
- r = n->parent;
- while ((r != NULL) && (r->parent != NULL)) {
- if (r->left == n)
- break;
- n = r;
- r = n->parent;
- }
-
- /* n->right == NULL && r == NULL => t is root and has no next
- * r->left != n => r->right = n => r->parent == NULL */
- if ((r == NULL) || (r->left != n)) {
- assert((r == NULL) || (r->parent == NULL));
- return (NULL);
- } else {
- assert(r->left == n);
- return (r);
- }
- } else {
- r = n->right;
- while (r->left != NULL)
- r = r->left;
- }
-
- return (r);
-} /* c_avl_node_t *c_avl_node_next */
-
-static c_avl_node_t *c_avl_node_prev(c_avl_node_t *n) {
- c_avl_node_t *r; /* return node */
-
- if (n == NULL) {
- return (NULL);
- }
-
- /* If we can't descent any further, we have to backtrack to the first
- * parent that's smaller than we, i. e. who's _right_ child we are. */
- if (n->left == NULL) {
- r = n->parent;
- while ((r != NULL) && (r->parent != NULL)) {
- if (r->right == n)
- break;
- n = r;
- r = n->parent;
- }
-
- /* n->left == NULL && r == NULL => t is root and has no next
- * r->right != n => r->left = n => r->parent == NULL */
- if ((r == NULL) || (r->right != n)) {
- assert((r == NULL) || (r->parent == NULL));
- return (NULL);
- } else {
- assert(r->right == n);
- return (r);
- }
- } else {
- r = n->left;
- while (r->right != NULL)
- r = r->right;
- }
-
- return (r);
-} /* c_avl_node_t *c_avl_node_prev */
-
-static int _remove(c_avl_tree_t *t, c_avl_node_t *n) {
- assert((t != NULL) && (n != NULL));
-
- if ((n->left != NULL) && (n->right != NULL)) {
- c_avl_node_t *r; /* replacement node */
- if (BALANCE(n) > 0) /* left subtree is higher */
- {
- assert(n->left != NULL);
- r = c_avl_node_prev(n);
-
- } else /* right subtree is higher */
- {
- assert(n->right != NULL);
- r = c_avl_node_next(n);
- }
-
- assert((r->left == NULL) || (r->right == NULL));
-
- /* copy content */
- n->key = r->key;
- n->value = r->value;
-
- n = r;
- }
-
- assert((n->left == NULL) || (n->right == NULL));
-
- if ((n->left == NULL) && (n->right == NULL)) {
- /* Deleting a leave is easy */
- if (n->parent == NULL) {
- assert(t->root == n);
- t->root = NULL;
- } else {
- assert((n->parent->left == n) || (n->parent->right == n));
- if (n->parent->left == n)
- n->parent->left = NULL;
- else
- n->parent->right = NULL;
-
- rebalance(t, n->parent);
- }
-
- free_node(n);
- } else if (n->left == NULL) {
- assert(BALANCE(n) == -1);
- assert((n->parent == NULL) || (n->parent->left == n) ||
- (n->parent->right == n));
- if (n->parent == NULL) {
- assert(t->root == n);
- t->root = n->right;
- } else if (n->parent->left == n) {
- n->parent->left = n->right;
- } else {
- n->parent->right = n->right;
- }
- n->right->parent = n->parent;
-
- if (n->parent != NULL)
- rebalance(t, n->parent);
-
- n->right = NULL;
- free_node(n);
- } else if (n->right == NULL) {
- assert(BALANCE(n) == 1);
- assert((n->parent == NULL) || (n->parent->left == n) ||
- (n->parent->right == n));
- if (n->parent == NULL) {
- assert(t->root == n);
- t->root = n->left;
- } else if (n->parent->left == n) {
- n->parent->left = n->left;
- } else {
- n->parent->right = n->left;
- }
- n->left->parent = n->parent;
-
- if (n->parent != NULL)
- rebalance(t, n->parent);
-
- n->left = NULL;
- free_node(n);
- } else {
- assert(0);
- }
-
- return (0);
-} /* void *_remove */
-
-/*
- * public functions
- */
-c_avl_tree_t *c_avl_create(int (*compare)(const void *, const void *)) {
- c_avl_tree_t *t;
-
- if (compare == NULL)
- return (NULL);
-
- if ((t = malloc(sizeof(*t))) == NULL)
- return (NULL);
-
- t->root = NULL;
- t->compare = compare;
- t->size = 0;
-
- return (t);
-}
-
-void c_avl_destroy(c_avl_tree_t *t) {
- if (t == NULL)
- return;
- free_node(t->root);
- free(t);
-}
-
-int c_avl_insert(c_avl_tree_t *t, void *key, void *value) {
- c_avl_node_t *new;
- c_avl_node_t *nptr;
- int cmp;
-
- if ((new = malloc(sizeof(*new))) == NULL)
- return (-1);
-
- new->key = key;
- new->value = value;
- new->height = 1;
- new->left = NULL;
- new->right = NULL;
-
- if (t->root == NULL) {
- new->parent = NULL;
- t->root = new;
- t->size = 1;
- return (0);
- }
-
- nptr = t->root;
- while (42) {
- cmp = t->compare(nptr->key, new->key);
- if (cmp == 0) {
- free_node(new);
- return (1);
- } else if (cmp < 0) {
- /* nptr < new */
- if (nptr->right == NULL) {
- nptr->right = new;
- new->parent = nptr;
- rebalance(t, nptr);
- break;
- } else {
- nptr = nptr->right;
- }
- } else /* if (cmp > 0) */
- {
- /* nptr > new */
- if (nptr->left == NULL) {
- nptr->left = new;
- new->parent = nptr;
- rebalance(t, nptr);
- break;
- } else {
- nptr = nptr->left;
- }
- }
- } /* while (42) */
-
- verify_tree(t->root);
- ++t->size;
- return (0);
-} /* int c_avl_insert */
-
-int c_avl_remove(c_avl_tree_t *t, const void *key, void **rkey, void **rvalue) {
- c_avl_node_t *n;
- int status;
-
- assert(t != NULL);
-
- n = search(t, key);
- if (n == NULL)
- return (-1);
-
- if (rkey != NULL)
- *rkey = n->key;
- if (rvalue != NULL)
- *rvalue = n->value;
-
- status = _remove(t, n);
- verify_tree(t->root);
- --t->size;
- return (status);
-} /* void *c_avl_remove */
-
-int c_avl_get(c_avl_tree_t *t, const void *key, void **value) {
- c_avl_node_t *n;
-
- assert(t != NULL);
-
- n = search(t, key);
- if (n == NULL)
- return (-1);
-
- if (value != NULL)
- *value = n->value;
-
- return (0);
-}
-
-int c_avl_pick(c_avl_tree_t *t, void **key, void **value) {
- c_avl_node_t *n;
- c_avl_node_t *p;
-
- if ((key == NULL) || (value == NULL))
- return (-1);
- if (t->root == NULL)
- return (-1);
-
- n = t->root;
- while ((n->left != NULL) || (n->right != NULL)) {
- if (n->left == NULL) {
- n = n->right;
- continue;
- } else if (n->right == NULL) {
- n = n->left;
- continue;
- }
-
- if (n->left->height > n->right->height)
- n = n->left;
- else
- n = n->right;
- }
-
- p = n->parent;
- if (p == NULL)
- t->root = NULL;
- else if (p->left == n)
- p->left = NULL;
- else
- p->right = NULL;
-
- *key = n->key;
- *value = n->value;
-
- free_node(n);
- --t->size;
- rebalance(t, p);
-
- return (0);
-} /* int c_avl_pick */
-
-c_avl_iterator_t *c_avl_get_iterator(c_avl_tree_t *t) {
- c_avl_iterator_t *iter;
-
- if (t == NULL)
- return (NULL);
-
- iter = calloc(1, sizeof(*iter));
- if (iter == NULL)
- return (NULL);
- iter->tree = t;
-
- return (iter);
-} /* c_avl_iterator_t *c_avl_get_iterator */
-
-int c_avl_iterator_next(c_avl_iterator_t *iter, void **key, void **value) {
- c_avl_node_t *n;
-
- if ((iter == NULL) || (key == NULL) || (value == NULL))
- return (-1);
-
- if (iter->node == NULL) {
- for (n = iter->tree->root; n != NULL; n = n->left)
- if (n->left == NULL)
- break;
- iter->node = n;
- } else {
- n = c_avl_node_next(iter->node);
- }
-
- if (n == NULL)
- return (-1);
-
- iter->node = n;
- *key = n->key;
- *value = n->value;
-
- return (0);
-} /* int c_avl_iterator_next */
-
-int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) {
- c_avl_node_t *n;
-
- if ((iter == NULL) || (key == NULL) || (value == NULL))
- return (-1);
-
- if (iter->node == NULL) {
- for (n = iter->tree->root; n != NULL; n = n->left)
- if (n->right == NULL)
- break;
- iter->node = n;
- } else {
- n = c_avl_node_prev(iter->node);
- }
-
- if (n == NULL)
- return (-1);
-
- iter->node = n;
- *key = n->key;
- *value = n->value;
-
- return (0);
-} /* int c_avl_iterator_prev */
-
-void c_avl_iterator_destroy(c_avl_iterator_t *iter) { free(iter); }
-
-int c_avl_size(c_avl_tree_t *t) {
- if (t == NULL)
- return (0);
- return (t->size);
-}
projects / collectd.git / blobdiff