#include <stdbool.h>
#include "list.h"
-#include "list_compat.h"
/* Support for OLSR.org linker symbol export */
#define EXPORT(sym) sym
* this must be the first element of an avl_node to
* make casting for lists easier
*/
- struct list_entity list;
+ struct list_head list;
/**
* Pointer to parent node in tree, NULL if root node
/**
* pointer to key of node
*/
- void *key;
+ const void *key;
/**
* balance state of AVL tree (0,-1,+1)
* Head of linked list node for supporting easy iteration
* and multiple elments with the same key.
*/
- struct list_entity list_head;
+ struct list_head list_head;
/**
* pointer to the root node of the avl tree, NULL if tree is empty
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);
* 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))
+ ((__typeof__(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
/**
* @param tree pointer to avl-tree
* 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))
+ ((__typeof__(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
/**
* @param tree pointer to avl-tree
* 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))
+ ((__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
* (automatically converted to type 'element')
*/
#define avl_first_element(tree, element, node_member) \
- container_of((tree)->list_head.next, typeof(*(element)), node_member)
+ container_of((tree)->list_head.next, __typeof__(*(element)), node_member.list)
/**
* @param tree pointer to tree
* (automatically converted to type 'element')
*/
#define avl_last_element(tree, element, node_member) \
- container_of((tree)->list_head.prev, typeof(*(element)), node_member)
+ container_of((tree)->list_head.prev, __typeof__(*(element)), node_member.list)
/**
* This function must not be called for the last element of
* (automatically converted to type 'element')
*/
#define avl_next_element(element, node_member) \
- container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
+ container_of((&(element)->node_member.list)->next, __typeof__(*(element)), node_member.list)
/**
* This function must not be called for the first element of
* (automatically converted to type 'element')
*/
#define avl_prev_element(element, node_member) \
- container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
+ container_of((&(element)->node_member.list)->prev, __typeof__(*(element)), node_member.list)
/**
* Loop over a block of elements of a tree, used similar to a for() command.
#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), \
+ INIT_LIST_HEAD(&(tree)->list_head), \
(tree)->root = NULL; \
(tree)->count > 0; \
element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)