avl.h

Go to the documentation of this file.

/*
 * 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"
 
/* Support for OLSR.org linker symbol export */
#define EXPORT(sym) sym
 
struct avl_node {
  struct list_head list;
 
  struct avl_node *parent;
 
  struct avl_node *left;
 
  struct avl_node *right;
 
  const void *key;
 
  signed char balance;
 
  bool leader;
};
 
typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
 
struct avl_tree {
  struct list_head list_head;
 
  struct avl_node *root;
 
  unsigned int count;
 
  bool allow_dups;
 
  avl_tree_comp comp;
 
  void *cmp_ptr;
};
 
enum avl_find_mode {
  AVL_FIND_EQUAL,
  AVL_FIND_LESSEQUAL,
  AVL_FIND_GREATEREQUAL
};
 
#define AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr)      \
        {                                                       \
                .list_head = LIST_HEAD_INIT(_name.list_head),   \
                .comp = _comp,                                  \
                .allow_dups = _allow_dups,                      \
                .cmp_ptr = _cmp_ptr                             \
        }
 
#define AVL_TREE(_name, _comp, _allow_dups, _cmp_ptr)           \
        struct avl_tree _name =                                 \
                AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr)
 
void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
struct avl_node *EXPORT(avl_find)(const struct avl_tree *, const void *);
struct avl_node *EXPORT(avl_find_greaterequal)(const struct avl_tree *tree, const void *key);
struct avl_node *EXPORT(avl_find_lessequal)(const 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 *);
 
static inline bool
avl_is_first(struct avl_tree *tree, struct avl_node *node) {
  return tree->list_head.next == &node->list;
}
 
static inline bool
avl_is_last(struct avl_tree *tree, struct avl_node *node) {
  return tree->list_head.prev == &node->list;
}
 
static inline bool
avl_is_empty(struct avl_tree *tree) {
  return tree->count == 0;
}
 
static inline void *
__avl_find_element(const 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);
}
 
#define avl_find_element(tree, key, element, node_element) \
  ((__typeof__(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
 
#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))
 
#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))
 
#define avl_first_element(tree, element, node_member) \
  container_of((tree)->list_head.next, __typeof__(*(element)), node_member.list)
 
#define avl_last_element(tree, element, node_member) \
  container_of((tree)->list_head.prev, __typeof__(*(element)), node_member.list)
 
#define avl_next_element(element, node_member) \
  container_of((&(element)->node_member.list)->next, __typeof__(*(element)), node_member.list)
 
#define avl_prev_element(element, node_member) \
  container_of((&(element)->node_member.list)->prev, __typeof__(*(element)), node_member.list)
 
#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))
 
#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))
 
#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)
 
#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)
 
#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)
 
 
#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)
 
#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)
 
 
#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)
 
#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))
 
#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))
 
#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)
 
#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)
 
#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), \
       INIT_LIST_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:
 */