X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fdaemon%2Futils_avltree.c;h=04e540327fcbae05542cb5da6661b8ca88f904f0;hb=master;hp=568d68c13d230d0d29f3b297edeffa768e62cf9d;hpb=24b87484c7fd2e0998682db6f77e54d8cdc459d4;p=collectd.git

diff --git a/src/daemon/utils_avltree.c b/src/daemon/utils_avltree.c
deleted file mode 100644
index 568d68c1..00000000
--- a/src/daemon/utils_avltree.c
+++ /dev/null
@@ -1,648 +0,0 @@
-/**
- * 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;
-
-  assert(t != NULL);
-
-  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->right)
-      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;
-}