libubox: Plug a small memory leak.

[project/libubox.git] / avl.h

diff --git a/avl.h b/avl.h
index 80a29b7..c468597 100644 (file)
--- a/avl.h
+++ b/avl.h
@@ -45,7 +45,6 @@
 #include <stdbool.h>
 
 #include "list.h"
 #include <stdbool.h>
 
 #include "list.h"

-#include "list_compat.h"

 
 /* Support for OLSR.org linker symbol export */
 #define EXPORT(sym) sym
 
 /* Support for OLSR.org linker symbol export */
 #define EXPORT(sym) sym


@@ -62,7 +61,7 @@ struct avl_node {
    * this must be the first element of an avl_node to
    * make casting for lists easier
    */
    * 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 parent node in tree, NULL if root node


@@ -82,7 +81,7 @@ struct avl_node {
   /**
    * pointer to key of node
    */
   /**
    * pointer to key of node
    */

-  void *key;
+  const void *key;

 
   /**
    * balance state of AVL tree (0,-1,+1)
 
   /**
    * balance state of AVL tree (0,-1,+1)


@@ -113,7 +112,7 @@ struct avl_tree {
    * Head of linked list node for supporting easy iteration
    * and multiple elments with the same key.
    */
    * 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
 
   /**
    * pointer to the root node of the avl tree, NULL if tree is empty


@@ -154,14 +153,24 @@ enum avl_find_mode {
   AVL_FIND_GREATEREQUAL
 };
 
   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 *);
 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 *);

-void *EXPORT(__avl_find_element)(const struct avl_tree *tree, const void *key,
-    size_t offset, enum avl_find_mode mode);

 
 /**
  * @param tree pointer to avl-tree
 
 /**
  * @param tree pointer to avl-tree


@@ -193,6 +202,32 @@ avl_is_empty(struct avl_tree *tree) {
 }
 
 /**
 }
 
 /**

+ * 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
  * @param element pointer to a node element
  * @param tree pointer to avl-tree
  * @param key pointer to key
  * @param element pointer to a node element


@@ -243,7 +278,7 @@ avl_is_empty(struct avl_tree *tree) {
  *    (automatically converted to type 'element')
  */
 #define avl_first_element(tree, element, node_member) \
  *    (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
 
 /**
  * @param tree pointer to tree


@@ -255,7 +290,7 @@ avl_is_empty(struct avl_tree *tree) {
  *    (automatically converted to type 'element')
  */
 #define avl_last_element(tree, element, node_member) \
  *    (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
 
 /**
  * This function must not be called for the last element of


@@ -268,7 +303,7 @@ avl_is_empty(struct avl_tree *tree) {
  *    (automatically converted to type 'element')
  */
 #define avl_next_element(element, node_member) \
  *    (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
 
 /**
  * This function must not be called for the first element of


@@ -281,7 +316,7 @@ avl_is_empty(struct avl_tree *tree) {
  *    (automatically converted to type 'element')
  */
 #define avl_prev_element(element, node_member) \
  *    (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.
 
 /**
  * Loop over a block of elements of a tree, used similar to a for() command.


@@ -510,7 +545,7 @@ avl_is_empty(struct avl_tree *tree) {
 #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), \
 #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--)
        (tree)->root = NULL; \
        (tree)->count > 0; \
        element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--)