merge an avl list implementation (imported from PacketBB)

diff --git a/Makefile b/Makefile
index ba25d1b..996d6a6 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -9,7 +9,7 @@ LIBDIR=$(PREFIX)/lib
 CPPFLAGS=
 
 OS=$(shell uname)
 CPPFLAGS=
 
 OS=$(shell uname)

-FILES=blob.c blobmsg.c hash.c uhtbl.c usock.c uloop.c
+FILES=blob.c blobmsg.c hash.c uhtbl.c usock.c uloop.c avl.c

 ifeq ($(OS),Linux)
   FILES += unl.c
   LIBS += $(LIBNL)
 ifeq ($(OS),Linux)
   FILES += unl.c
   LIBS += $(LIBNL)

diff --git a/avl.c b/avl.c
new file mode 100644 (file)
index 0000000..bde40b7
--- /dev/null
+++ b/avl.c
@@ -0,0 +1,760 @@
+/*
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org/git for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ */
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <time.h>
+#include <string.h>
+
+#include "avl.h"
+#include "list.h"
+
+#define list_merge(_head, _list) list_merge(_list, _head)
+#define list_is_last(_head, _list) list_is_last(_list, _head)
+#define list_is_first(_head, _list) list_is_first(_list, _head)
+
+/**
+ * internal type save inline function to calculate the maximum of
+ * to integers without macro implementation.
+ *
+ * @param x first parameter of maximum function
+ * @param y second parameter of maximum function
+ * @return largest integer of both parameters
+ */
+static inline int avl_max(int x, int y) {
+  return x > y ? x : y;
+}
+
+/**
+ * internal type save inline function to calculate the minimum of
+ * to integers without macro implementation.
+ *
+ * @param x first parameter of minimum function
+ * @param y second parameter of minimum function
+ * @return smallest integer of both parameters
+ */
+static inline int avl_min(int x, int y) {
+  return x < y ? x : y;
+}
+
+static struct avl_node *
+avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
+static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
+static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
+static void post_insert(struct avl_tree *tree, struct avl_node *node);
+static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
+static void avl_remove(struct avl_tree *tree, struct avl_node *node);
+
+/**
+ * Initialize a new avl_tree struct
+ * @param tree pointer to avl-tree
+ * @param comp pointer to comparator for the tree
+ * @param allow_dups true if the tree allows multiple
+ *   elements with the same
+ * @param ptr custom parameter for comparator
+ */
+void
+avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
+{
+  list_init_head(&tree->list_head);
+  tree->root = NULL;
+  tree->count = 0;
+  tree->comp = comp;
+  tree->allow_dups = allow_dups;
+  tree->cmp_ptr = ptr;
+}
+
+/**
+ * Internal function to support returning the element from a avl tree query
+ * @param tree pointer to avl tree
+ * @param key pointer to key
+ * @param offset offset of node inside the embedded struct
+ * @param mode mode of lookup operation (less equal, equal or greater equal)
+ * @param pointer to elemen, NULL if no fitting one was found
+ */
+void *
+__avl_find_element(struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
+  void *node = NULL;
+
+  switch (mode) {
+    case AVL_FIND_EQUAL:
+      node = avl_find(tree, key);
+      break;
+    case AVL_FIND_LESSEQUAL:
+      node = avl_find_lessequal(tree, key);
+      break;
+    case AVL_FIND_GREATEREQUAL:
+      node = avl_find_greaterequal(tree, key);
+      break;
+  }
+  return node == NULL ? NULL : (((char *)node) - offset);
+}
+
+/**
+ * Finds a node in an avl-tree with a certain key
+ * @param tree pointer to avl-tree
+ * @param key pointer to key
+ * @return pointer to avl-node with key, NULL if no node with
+ *    this key exists.
+ */
+struct avl_node *
+avl_find(struct avl_tree *tree, const void *key)
+{
+  struct avl_node *node;
+  int diff;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
+
+  return diff == 0 ? node : NULL;
+}
+
+/**
+ * Finds the last node in an avl-tree with a key less or equal
+ * than the specified key
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @return pointer to avl-node, NULL if no node with
+ *    key less or equal specified key exists.
+ */
+struct avl_node *
+avl_find_lessequal(struct avl_tree *tree, const void *key) {
+  struct avl_node *node, *next;
+  int diff;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
+
+  /* go left as long as key<node.key */
+  while (diff < 0) {
+    if (list_is_first(&tree->list_head, &node->list)) {
+      return NULL;
+    }
+
+    node = (struct avl_node *)node->list.prev;
+    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
+  }
+
+  /* go right as long as key>=next_node.key */
+  next = node;
+  while (diff >= 0) {
+    node = next;
+    if (list_is_last(&tree->list_head, &node->list)) {
+      break;
+    }
+
+    next = (struct avl_node *)node->list.next;
+    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
+  }
+  return node;
+}
+
+/**
+ * Finds the first node in an avl-tree with a key greater or equal
+ * than the specified key
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @return pointer to avl-node, NULL if no node with
+ *    key greater or equal specified key exists.
+ */
+struct avl_node *
+avl_find_greaterequal(struct avl_tree *tree, const void *key) {
+  struct avl_node *node, *next;
+  int diff;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
+
+  /* go right as long as key>node.key */
+  while (diff > 0) {
+    if (list_is_last(&tree->list_head, &node->list)) {
+      return NULL;
+    }
+
+    node = (struct avl_node *)node->list.next;
+    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
+  }
+
+  /* go left as long as key<=next_node.key */
+  next = node;
+  while (diff <= 0) {
+    node = next;
+    if (list_is_first(&tree->list_head, &node->list)) {
+      break;
+    }
+
+    next = (struct avl_node *)node->list.prev;
+    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
+  }
+  return node;
+}
+
+/**
+ * Inserts an avl_node into a tree
+ * @param tree pointer to tree
+ * @param new pointer to node
+ * @return 0 if node was inserted successfully, -1 if it was not inserted
+ *   because of a key collision
+ */
+int
+avl_insert(struct avl_tree *tree, struct avl_node *new)
+{
+  struct avl_node *node, *next, *last;
+  int diff;
+
+  new->parent = NULL;
+
+  new->left = NULL;
+  new->right = NULL;
+
+  new->balance = 0;
+  new->leader = true;
+
+  if (tree->root == NULL) {
+    list_add_head(&tree->list_head, &new->list);
+    tree->root = new;
+    tree->count = 1;
+    return 0;
+  }
+
+  node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
+
+  last = node;
+
+  while (!list_is_last(&tree->list_head, &last->list)) {
+    next = list_next_element(last, list);
+    if (next->leader) {
+      break;
+    }
+    last = next;
+  }
+
+  diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
+
+  if (diff == 0) {
+    if (!tree->allow_dups)
+      return -1;
+
+    new->leader = 0;
+
+    avl_insert_after(tree, last, new);
+    return 0;
+  }
+
+  if (node->balance == 1) {
+    avl_insert_before(tree, node, new);
+
+    node->balance = 0;
+    new->parent = node;
+    node->left = new;
+    return 0;
+  }
+
+  if (node->balance == -1) {
+    avl_insert_after(tree, last, new);
+
+    node->balance = 0;
+    new->parent = node;
+    node->right = new;
+    return 0;
+  }
+
+  if (diff < 0) {
+    avl_insert_before(tree, node, new);
+
+    node->balance = -1;
+    new->parent = node;
+    node->left = new;
+    post_insert(tree, node);
+    return 0;
+  }
+
+  avl_insert_after(tree, last, new);
+
+  node->balance = 1;
+  new->parent = node;
+  node->right = new;
+  post_insert(tree, node);
+  return 0;
+}
+
+/**
+ * Remove a node from an avl tree
+ * @param tree pointer to tree
+ * @param node pointer to node
+ */
+void
+avl_delete(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *next;
+  struct avl_node *parent;
+  struct avl_node *left;
+  struct avl_node *right;
+  if (node->leader) {
+    if (tree->allow_dups
+        && !list_is_last(&tree->list_head, &node->list)
+        && !(next = list_next_element(node, list))->leader) {
+      next->leader = true;
+      next->balance = node->balance;
+
+      parent = node->parent;
+      left = node->left;
+      right = node->right;
+
+      next->parent = parent;
+      next->left = left;
+      next->right = right;
+
+      if (parent == NULL)
+        tree->root = next;
+
+      else {
+        if (node == parent->left)
+          parent->left = next;
+
+        else
+          parent->right = next;
+      }
+
+      if (left != NULL)
+        left->parent = next;
+
+      if (right != NULL)
+        right->parent = next;
+    }
+
+    else
+      avl_delete_worker(tree, node);
+  }
+
+  avl_remove(tree, node);
+}
+
+static struct avl_node *
+avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
+{
+  int diff;
+
+  diff = (*comp) (key, node->key, cmp_ptr);
+  *cmp_result = diff;
+
+  if (diff < 0) {
+    if (node->left != NULL)
+      return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
+
+    return node;
+  }
+
+  if (diff > 0) {
+    if (node->right != NULL)
+      return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
+
+    return node;
+  }
+
+  return node;
+}
+
+static void
+avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *left, *parent;
+
+  left = node->left;
+  parent = node->parent;
+
+  left->parent = parent;
+  node->parent = left;
+
+  if (parent == NULL)
+    tree->root = left;
+
+  else {
+    if (parent->left == node)
+      parent->left = left;
+
+    else
+      parent->right = left;
+  }
+
+  node->left = left->right;
+  left->right = node;
+
+  if (node->left != NULL)
+    node->left->parent = node;
+
+  node->balance += 1 - avl_min(left->balance, 0);
+  left->balance += 1 + avl_max(node->balance, 0);
+}
+
+static void
+avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *right, *parent;
+
+  right = node->right;
+  parent = node->parent;
+
+  right->parent = parent;
+  node->parent = right;
+
+  if (parent == NULL)
+    tree->root = right;
+
+  else {
+    if (parent->left == node)
+      parent->left = right;
+
+    else
+      parent->right = right;
+  }
+
+  node->right = right->left;
+  right->left = node;
+
+  if (node->right != NULL)
+    node->right->parent = node;
+
+  node->balance -= 1 + avl_max(right->balance, 0);
+  right->balance -= 1 - avl_min(node->balance, 0);
+}
+
+static void
+post_insert(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *parent = node->parent;
+
+  if (parent == NULL)
+    return;
+
+  if (node == parent->left) {
+    parent->balance--;
+
+    if (parent->balance == 0)
+      return;
+
+    if (parent->balance == -1) {
+      post_insert(tree, parent);
+      return;
+    }
+
+    if (node->balance == -1) {
+      avl_rotate_right(tree, parent);
+      return;
+    }
+
+    avl_rotate_left(tree, node);
+    avl_rotate_right(tree, node->parent->parent);
+    return;
+  }
+
+  parent->balance++;
+
+  if (parent->balance == 0)
+    return;
+
+  if (parent->balance == 1) {
+    post_insert(tree, parent);
+    return;
+  }
+
+  if (node->balance == 1) {
+    avl_rotate_left(tree, parent);
+    return;
+  }
+
+  avl_rotate_right(tree, node);
+  avl_rotate_left(tree, node->parent->parent);
+}
+
+static void
+avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
+{
+  list_add_before(&pos_node->list, &node->list);
+  tree->count++;
+}
+
+static void
+avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
+{
+  list_add_after(&pos_node->list, &node->list);
+  tree->count++;
+}
+
+static void
+avl_remove(struct avl_tree *tree, struct avl_node *node)
+{
+  list_remove(&node->list);
+  tree->count--;
+}
+
+static void
+avl_post_delete(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *parent;
+
+  if ((parent = node->parent) == NULL)
+    return;
+
+  if (node == parent->left) {
+    parent->balance++;
+
+    if (parent->balance == 0) {
+      avl_post_delete(tree, parent);
+      return;
+    }
+
+    if (parent->balance == 1)
+      return;
+
+    if (parent->right->balance == 0) {
+      avl_rotate_left(tree, parent);
+      return;
+    }
+
+    if (parent->right->balance == 1) {
+      avl_rotate_left(tree, parent);
+      avl_post_delete(tree, parent->parent);
+      return;
+    }
+
+    avl_rotate_right(tree, parent->right);
+    avl_rotate_left(tree, parent);
+    avl_post_delete(tree, parent->parent);
+    return;
+  }
+
+  parent->balance--;
+
+  if (parent->balance == 0) {
+    avl_post_delete(tree, parent);
+    return;
+  }
+
+  if (parent->balance == -1)
+    return;
+
+  if (parent->left->balance == 0) {
+    avl_rotate_right(tree, parent);
+    return;
+  }
+
+  if (parent->left->balance == -1) {
+    avl_rotate_right(tree, parent);
+    avl_post_delete(tree, parent->parent);
+    return;
+  }
+
+  avl_rotate_left(tree, parent->left);
+  avl_rotate_right(tree, parent);
+  avl_post_delete(tree, parent->parent);
+}
+
+static struct avl_node *
+avl_local_min(struct avl_node *node)
+{
+  while (node->left != NULL)
+    node = node->left;
+
+  return node;
+}
+
+#if 0
+static struct avl_node *
+avl_local_max(struct avl_node *node)
+{
+  while (node->right != NULL)
+    node = node->right;
+
+  return node;
+}
+#endif
+
+static void
+avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *parent, *min;
+
+  parent = node->parent;
+
+  if (node->left == NULL && node->right == NULL) {
+    if (parent == NULL) {
+      tree->root = NULL;
+      return;
+    }
+
+    if (parent->left == node) {
+      parent->left = NULL;
+      parent->balance++;
+
+      if (parent->balance == 1)
+        return;
+
+      if (parent->balance == 0) {
+        avl_post_delete(tree, parent);
+        return;
+      }
+
+      if (parent->right->balance == 0) {
+        avl_rotate_left(tree, parent);
+        return;
+      }
+
+      if (parent->right->balance == 1) {
+        avl_rotate_left(tree, parent);
+        avl_post_delete(tree, parent->parent);
+        return;
+      }
+
+      avl_rotate_right(tree, parent->right);
+      avl_rotate_left(tree, parent);
+      avl_post_delete(tree, parent->parent);
+      return;
+    }
+
+    if (parent->right == node) {
+      parent->right = NULL;
+      parent->balance--;
+
+      if (parent->balance == -1)
+        return;
+
+      if (parent->balance == 0) {
+        avl_post_delete(tree, parent);
+        return;
+      }
+
+      if (parent->left->balance == 0) {
+        avl_rotate_right(tree, parent);
+        return;
+      }
+
+      if (parent->left->balance == -1) {
+        avl_rotate_right(tree, parent);
+        avl_post_delete(tree, parent->parent);
+        return;
+      }
+
+      avl_rotate_left(tree, parent->left);
+      avl_rotate_right(tree, parent);
+      avl_post_delete(tree, parent->parent);
+      return;
+    }
+  }
+
+  if (node->left == NULL) {
+    if (parent == NULL) {
+      tree->root = node->right;
+      node->right->parent = NULL;
+      return;
+    }
+
+    node->right->parent = parent;
+
+    if (parent->left == node)
+      parent->left = node->right;
+
+    else
+      parent->right = node->right;
+
+    avl_post_delete(tree, node->right);
+    return;
+  }
+
+  if (node->right == NULL) {
+    if (parent == NULL) {
+      tree->root = node->left;
+      node->left->parent = NULL;
+      return;
+    }
+
+    node->left->parent = parent;
+
+    if (parent->left == node)
+      parent->left = node->left;
+
+    else
+      parent->right = node->left;
+
+    avl_post_delete(tree, node->left);
+    return;
+  }
+
+  min = avl_local_min(node->right);
+  avl_delete_worker(tree, min);
+  parent = node->parent;
+
+  min->balance = node->balance;
+  min->parent = parent;
+  min->left = node->left;
+  min->right = node->right;
+
+  if (min->left != NULL)
+    min->left->parent = min;
+
+  if (min->right != NULL)
+    min->right->parent = min;
+
+  if (parent == NULL) {
+    tree->root = min;
+    return;
+  }
+
+  if (parent->left == node) {
+    parent->left = min;
+    return;
+  }
+
+  parent->right = min;
+}
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * indent-tabs-mode: nil
+ * End:
+ */

diff --git a/avl.h b/avl.h
new file mode 100644 (file)
index 0000000..1c57604
--- /dev/null
+++ b/avl.h
@@ -0,0 +1,525 @@
+/*
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org/git for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ */
+
+#ifndef _AVL_H
+#define _AVL_H
+
+#include <stddef.h>
+#include <stdbool.h>
+
+#include "list.h"
+#include "list_compat.h"
+
+/* Support for OLSR.org linker symbol export */
+#define EXPORT(sym) sym
+
+/**
+ * This element is a member of a avl-tree. It must be contained in all
+ * larger structs that should be put into a tree.
+ */
+struct avl_node {
+  /**
+   * Linked list node for supporting easy iteration and multiple
+   * elments with the same key.
+   *
+   * this must be the first element of an avl_node to
+   * make casting for lists easier
+   */
+  struct list_entity list;
+
+  /**
+   * Pointer to parent node in tree, NULL if root node
+   */
+  struct avl_node *parent;
+
+  /**
+   * Pointer to left child
+   */
+  struct avl_node *left;
+
+  /**
+   * Pointer to right child
+   */
+  struct avl_node *right;
+
+  /**
+   * pointer to key of node
+   */
+  void *key;
+
+  /**
+   * balance state of AVL tree (0,-1,+1)
+   */
+  signed char balance;
+
+  /**
+   * true if first of a series of nodes with same key
+   */
+  bool leader;
+};
+
+/**
+ * Prototype for avl comparators
+ * @param k1 first key
+ * @param k2 second key
+ * @param ptr custom data for tree comparator
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
+
+/**
+ * This struct is the central management part of an avl tree.
+ * One of them is necessary for each avl_tree.
+ */
+struct avl_tree {
+  /**
+   * Head of linked list node for supporting easy iteration
+   * and multiple elments with the same key.
+   */
+  struct list_entity list_head;
+
+  /**
+   * pointer to the root node of the avl tree, NULL if tree is empty
+   */
+  struct avl_node *root;
+
+  /**
+   * number of nodes in the avl tree
+   */
+  unsigned int count;
+
+  /**
+   * true if multiple nodes with the same key are
+   * allowed in the tree, false otherwise
+   */
+  bool allow_dups;
+
+  /**
+   * pointer to the tree comparator
+   *
+   * First two parameters are keys to compare,
+   * third parameter is a copy of cmp_ptr
+   */
+  avl_tree_comp comp;
+
+  /**
+   * custom pointer delivered to the tree comparator
+   */
+  void *cmp_ptr;
+};
+
+/**
+ * internal enum for avl_find_... macros
+ */
+enum avl_find_mode {
+  AVL_FIND_EQUAL,
+  AVL_FIND_LESSEQUAL,
+  AVL_FIND_GREATEREQUAL
+};
+
+void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
+struct avl_node *EXPORT(avl_find)(struct avl_tree *, const void *);
+struct avl_node *EXPORT(avl_find_greaterequal)(struct avl_tree *tree, const void *key);
+struct avl_node *EXPORT(avl_find_lessequal)(struct avl_tree *tree, const void *key);
+int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
+void EXPORT(avl_delete)(struct avl_tree *, struct avl_node *);
+void *EXPORT(__avl_find_element)(struct avl_tree *tree, const void *key,
+    size_t offset, enum avl_find_mode mode);
+
+/**
+ * @param tree pointer to avl-tree
+ * @param node pointer to node of the tree
+ * @return true if node is the first one of the tree, false otherwise
+ */
+static inline bool
+avl_is_first(struct avl_tree *tree, struct avl_node *node) {
+  return tree->list_head.next == &node->list;
+}
+
+/**
+ * @param tree pointer to avl-tree
+ * @param node pointer to node of the tree
+ * @return true if node is the last one of the tree, false otherwise
+ */
+static inline bool
+avl_is_last(struct avl_tree *tree, struct avl_node *node) {
+  return tree->list_head.prev == &node->list;
+}
+
+/**
+ * @param tree pointer to avl-tree
+ * @return true if the tree is empty, false otherwise
+ */
+static inline bool
+avl_is_empty(struct avl_tree *tree) {
+  return tree->count == 0;
+}
+
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to tree element with the specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
+
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * return pointer to last tree element with less or equal key than specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_le_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
+
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * return pointer to first tree element with greater or equal key than specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_ge_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
+
+/**
+ * This function must not be called for an empty tree
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the first element of the avl_tree
+ *    (automatically converted to type 'element')
+ */
+#define avl_first_element(tree, element, node_member) \
+  container_of((tree)->list_head.next, typeof(*(element)), node_member)
+
+/**
+ * @param tree pointer to tree
+ * @param element pointer to a node struct that contains the avl_node
+ *    (don't need to be initialized)
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the last element of the avl_tree
+ *    (automatically converted to type 'element')
+ */
+#define avl_last_element(tree, element, node_member) \
+  container_of((tree)->list_head.prev, typeof(*(element)), node_member)
+
+/**
+ * This function must not be called for the last element of
+ * an avl tree
+ *
+ * @param element pointer to a node of the tree
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the node after 'element'
+ *    (automatically converted to type 'element')
+ */
+#define avl_next_element(element, node_member) \
+  container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
+
+/**
+ * This function must not be called for the first element of
+ * an avl tree
+ *
+ * @param element pointer to a node of the tree
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the node before 'element'
+ *    (automatically converted to type 'element')
+ */
+#define avl_prev_element(element, node_member) \
+  container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param first pointer to first element of loop
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_element_range(first, last, element, node_member) \
+  for (element = (first); \
+       element->node_member.list.prev != &(last)->node_member.list; \
+       element = avl_next_element(element, node_member))
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param first pointer to first element of loop
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_element_range_reverse(first, last, element, node_member) \
+  for (element = (last); \
+       element->node_member.list.next != &(first)->node_member.list; \
+       element = avl_prev_element(element, node_member))
+
+/**
+ * Loop over all elements of an avl_tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_each_element(tree, element, node_member) \
+  avl_for_element_range(avl_first_element(tree, element, node_member), \
+                        avl_last_element(tree, element,  node_member), \
+                        element, node_member)
+
+/**
+ * Loop over all elements of an avl_tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_each_element_reverse(tree, element, node_member) \
+  avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \
+                                avl_last_element(tree, element,  node_member), \
+                                element, node_member)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the element 'first' to the end of the tree.
+ *
+ * @param tree pointer to avl-tree
+ * @param first pointer to first element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_element_to_last(tree, first, element, node_member) \
+  avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member)
+
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the element 'first' to the end of the tree.
+ *
+ * @param tree pointer to avl-tree
+ * @param first pointer to first element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_element_to_last_reverse(tree, first, element, node_member) \
+  avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the start of the tree to the element 'last'.
+ *
+ * @param tree pointer to avl-tree
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_first_to_element(tree, last, element, node_member) \
+  avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member)
+
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the start of the tree to the element 'last'.
+ *
+ * @param tree pointer to avl-tree
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ */
+#define avl_for_first_to_element_reverse(tree, last, element, node_member) \
+  avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member)
+
+/**
+ * Loop over a block of nodes of a tree, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param first_element first element of loop
+ * @param last_element last element of loop
+ * @param element iterator pointer to tree element struct
+ * @param node_member name of avl_node within tree element struct
+ * @param ptr pointer to tree element struct which is used to store
+ *    the next node during the loop
+ */
+#define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \
+  for (element = (first_element), ptr = avl_next_element(first_element, node_member); \
+       element->node_member.list.prev != &(last_element)->node_member.list; \
+       element = ptr, ptr = avl_next_element(ptr, node_member))
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param first_element first element of range (will be last returned by the loop)
+ * @param last_element last element of range (will be first returned by the loop)
+ * @param element iterator pointer to node element struct
+ * @param node_member name of avl_node within node element struct
+ * @param ptr pointer to node element struct which is used to store
+ *    the previous node during the loop
+ */
+#define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \
+  for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \
+       element->node_member.list.next != &(first_element)->node_member.list; \
+       element = ptr, ptr = avl_prev_element(ptr, node_member))
+
+/**
+ * Loop over all elements of an avl_tree, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param ptr pointer to a tree element which is used to store
+ *    the next node during the loop
+ */
+#define avl_for_each_element_safe(tree, element, node_member, ptr) \
+  avl_for_element_range_safe(avl_first_element(tree, element, node_member), \
+                             avl_last_element(tree, element, node_member), \
+                             element, node_member, ptr)
+
+/**
+ * Loop over all elements of an avl_tree backwards, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param ptr pointer to a tree element which is used to store
+ *    the next node during the loop
+ */
+#define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \
+  avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \
+                                     avl_last_element(tree, element, node_member), \
+                                     element, node_member, ptr)
+
+/**
+ * A special loop that removes all elements of the tree and cleans up the tree
+ * root. The loop body is responsible to free the node elements of the tree.
+ *
+ * This loop is much faster than a normal one for clearing the tree because it
+ * does not rebalance the tree after each removal. Do NOT use a break command
+ * inside.
+ * You can free the memory of the elements within the loop.
+ * Do NOT call avl_delete() on the elements within the loop,
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param ptr pointer to a tree element which is used to store
+ *    the next node during the loop
+ */
+#define avl_remove_all_elements(tree, element, node_member, ptr) \
+  for (element = avl_first_element(tree, element, node_member), \
+       ptr = avl_next_element(element, node_member), \
+       list_init_head(&(tree)->list_head), \
+       (tree)->root = NULL; \
+       (tree)->count > 0; \
+       element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)
+
+#endif /* _AVL_H */
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * indent-tabs-mode: nil
+ * End:
+ */

diff --git a/list.h b/list.h
index 2959a06..e8271d0 100644 (file)
--- a/list.h
+++ b/list.h
@@ -167,6 +167,17 @@ static inline void list_move_tail(struct list_head *list,
 }
 
 /**
 }
 
 /**

+ * list_is_first - tests whether @list is the first entry in list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_is_first(const struct list_head *list,
+                               const struct list_head *head)
+{
+       return list->prev == head;
+}
+
+/**

  * list_is_last - tests whether @list is the last entry in list @head
  * @list: the entry to test
  * @head: the head of the list
  * list_is_last - tests whether @list is the last entry in list @head
  * @list: the entry to test
  * @head: the head of the list

diff --git a/list_compat.h b/list_compat.h
new file mode 100644 (file)
index 0000000..2b7b1f4
--- /dev/null
+++ b/list_compat.h
@@ -0,0 +1,15 @@
+#ifndef __LIST_COMPAT_H
+#define __LIST_COMPAT_H
+
+#define list_entity                            list_head
+
+#define list_init_head(_list)                  INIT_LIST_HEAD(_list)
+#define list_add_head(_head, _list)            list_add(_list, _head)
+#define list_add_after(_after, _list)          list_add(_list, _after)
+#define list_add_before(_before, _list)                list_add_tail(_list, _before)
+#define list_remove(_list)                     list_del(_list)
+#define list_is_empty(_list)                   list_empty(_list)
+#define list_next_element(_element, _member)   list_entry((_element)->_member.next, typeof(*(_element)), _member)
+
+
+#endif