#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)(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);
+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 *);
-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
return tree->count == 0;
}
+/**
+ * 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
+ */
+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);
+}
+
/**
* @param tree pointer to avl-tree
* @param key pointer to 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--)