#include <stddef.h>
#include <stdbool.h>
#include "list.h"

Data Structures
struct	avl_node

struct	avl_tree

Macros
#define	EXPORT(sym) sym

#define	AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr)

#define	AVL_TREE(_name, _comp, _allow_dups, _cmp_ptr)

#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)

#define	avl_for_element_range_reverse(first, last, element, node_member)

#define	avl_for_each_element(tree, element, node_member)

#define	avl_for_each_element_reverse(tree, 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)

#define	avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr)

#define	avl_for_each_element_safe(tree, element, node_member, ptr)

#define	avl_for_each_element_reverse_safe(tree, element, node_member, ptr)

#define	avl_remove_all_elements(tree, element, node_member, ptr)

Typedefs
typedef int(*	avl_tree_comp) (const void k1, const void k2, void *ptr)

Enumerations
enum	avl_find_mode { AVL_FIND_EQUAL , AVL_FIND_LESSEQUAL , AVL_FIND_GREATEREQUAL }

Functions
void	avl_init (struct avl_tree , avl_tree_comp, bool, void )

struct avl_node *	avl_find (const struct avl_tree , const void )

struct avl_node *	avl_find_greaterequal (const struct avl_tree tree, const void key)

struct avl_node *	avl_find_lessequal (const struct avl_tree tree, const void key)

int	avl_insert (struct avl_tree , struct avl_node )

void	avl_delete (struct avl_tree , struct avl_node )

static bool	avl_is_first (struct avl_tree tree, struct avl_node node)

static bool	avl_is_last (struct avl_tree tree, struct avl_node node)

static bool	avl_is_empty (struct avl_tree *tree)

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

Macro Definition Documentation

◆ avl_find_element

#define avl_find_element	(	tree,
		key,
		element,
		node_element
	)	((__typeof__((element)) )__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))

Parameters

tree	pointer to avl-tree
key	pointer to key
element	pointer to a node element (don't need to be initialized)
node_element	name of the avl_node element inside the larger struct

Returns: pointer to tree element with the specified key, NULL if no element was found

Definition at line 240 of file avl.h.

◆ avl_find_ge_element

#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))

Parameters

tree	pointer to avl-tree
key	pointer to specified key
element	pointer to a node element (don't need to be initialized)
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

Definition at line 266 of file avl.h.

◆ avl_find_le_element

#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))

Parameters

tree	pointer to avl-tree
key	pointer to specified key
element	pointer to a node element (don't need to be initialized)
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

Definition at line 253 of file avl.h.

◆ avl_first_element

#define avl_first_element	(	tree,
		element,
		node_member
	)	container_of((tree)->list_head.next, __typeof__(*(element)), node_member.list)

This function must not be called for an empty tree

Parameters

tree	pointer to avl-tree
element	pointer to a node element (don't need to be initialized)
node_member	name of the avl_node element inside the larger struct

Returns: pointer to the first element of the avl_tree (automatically converted to type 'element')

Definition at line 280 of file avl.h.

◆ avl_for_each_element

#define avl_for_each_element	(	tree,
		element,
		node_member
	)

Value:

  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, used similar to a for() command. This loop should not be used if elements are removed from the tree during the loop.

Parameters

tree	pointer to avl-tree
element	pointer to a node of the tree, this element will contain the current node of the tree during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 366 of file avl.h.

◆ avl_for_each_element_reverse

#define avl_for_each_element_reverse	(	tree,
		element,
		node_member
	)

Value:

  avl_for_element_range_reverse(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.

Parameters

tree	pointer to avl-tree
element	pointer to a node of the tree, this element will contain the current node of the tree during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 382 of file avl.h.

◆ avl_for_each_element_reverse_safe

#define avl_for_each_element_reverse_safe	(	tree,
		element,
		node_member,
		ptr
	)

Value:

  avl_for_element_range_reverse_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.

Parameters

tree	pointer to avl-tree
element	pointer to a node of the tree, this element will contain the current node of the tree during the loop
node_member	name of the avl_node element inside the larger struct
ptr	pointer to a tree element which is used to store the next node during the loop

Definition at line 522 of file avl.h.

◆ avl_for_each_element_safe

#define avl_for_each_element_safe	(	tree,
		element,
		node_member,
		ptr
	)

Value:

  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, 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.

Parameters

tree	pointer to avl-tree
element	pointer to a node of the tree, this element will contain the current node of the tree during the loop
node_member	name of the avl_node element inside the larger struct
ptr	pointer to a tree element which is used to store the next node during the loop

Definition at line 503 of file avl.h.

◆ avl_for_element_range

#define avl_for_element_range	(	first,
		last,
		element,
		node_member
	)

Value:

  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, used similar to a for() command. This loop should not be used if elements are removed from the tree during the loop.

Parameters

first	pointer to first element of loop
last	pointer to last element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 333 of file avl.h.

◆ avl_for_element_range_reverse

#define avl_for_element_range_reverse	(	first,
		last,
		element,
		node_member
	)

Value:

  for (element = (last); \
       element->node_member.list.next != &(first)->node_member.list; \
       element = avl_prev_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.

Parameters

first	pointer to first element of loop
last	pointer to last element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 350 of file avl.h.

◆ avl_for_element_range_reverse_safe

#define avl_for_element_range_reverse_safe	(	first_element,
		last_element,
		element,
		node_member,
		ptr
	)

Value:

  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 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.

Parameters

first_element	first element of range (will be last returned by the loop)
last_element	last element of range (will be first returned by the loop)
element	iterator pointer to node element struct
node_member	name of avl_node within node element struct
ptr	pointer to node element struct which is used to store the previous node during the loop

Definition at line 484 of file avl.h.

◆ avl_for_element_range_safe

#define avl_for_element_range_safe	(	first_element,
		last_element,
		element,
		node_member,
		ptr
	)

Value:

  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 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.

Parameters

first_element	first element of loop
last_element	last element of loop
element	iterator pointer to tree element struct
node_member	name of avl_node within tree element struct
ptr	pointer to tree element struct which is used to store the next node during the loop

Definition at line 466 of file avl.h.

◆ avl_for_element_to_last

#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, 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.

Parameters

tree	pointer to avl-tree
first	pointer to first element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 400 of file avl.h.

◆ avl_for_element_to_last_reverse

#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 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.

Parameters

tree	pointer to avl-tree
first	pointer to first element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 417 of file avl.h.

◆ avl_for_first_to_element

#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, 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'.

Parameters

tree	pointer to avl-tree
last	pointer to last element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 433 of file avl.h.

◆ avl_for_first_to_element_reverse

#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 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'.

Parameters

tree	pointer to avl-tree
last	pointer to last element of loop
element	pointer to a node of the tree, this element will contain the current node of the list during the loop
node_member	name of the avl_node element inside the larger struct

Definition at line 450 of file avl.h.

◆ avl_last_element

#define avl_last_element	(	tree,
		element,
		node_member
	)	container_of((tree)->list_head.prev, __typeof__(*(element)), node_member.list)

Parameters

tree	pointer to tree
element	pointer to a node struct that contains the avl_node (don't need to be initialized)
node_member	name of the avl_node element inside the larger struct

Returns: pointer to the last element of the avl_tree (automatically converted to type 'element')

Definition at line 292 of file avl.h.

◆ avl_next_element

#define avl_next_element	(	element,
		node_member
	)	container_of((&(element)->node_member.list)->next, __typeof__(*(element)), node_member.list)

This function must not be called for the last element of an avl tree

Parameters

element	pointer to a node of the tree
node_member	name of the avl_node element inside the larger struct

Returns: pointer to the node after 'element' (automatically converted to type 'element')

Definition at line 305 of file avl.h.

◆ avl_prev_element

#define avl_prev_element	(	element,
		node_member
	)	container_of((&(element)->node_member.list)->prev, __typeof__(*(element)), node_member.list)

This function must not be called for the first element of an avl tree

Parameters

element	pointer to a node of the tree
node_member	name of the avl_node element inside the larger struct

Returns: pointer to the node before 'element' (automatically converted to type 'element')

Definition at line 318 of file avl.h.

◆ avl_remove_all_elements

#define avl_remove_all_elements	(	tree,
		element,
		node_member,
		ptr
	)

Value:

  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--)

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,

Parameters

tree	pointer to avl-tree
element	pointer to a node of the tree, this element will contain the current node of the tree during the loop
node_member	name of the avl_node element inside the larger struct
ptr	pointer to a tree element which is used to store the next node during the loop

Definition at line 545 of file avl.h.

◆ AVL_TREE

#define AVL_TREE	(	_name,
		_comp,
		_allow_dups,
		_cmp_ptr
	)

Value:

struct avl_tree _name = \

AVL_TREE_INIT(_name, _comp, _allow_dups, _cmp_ptr)

avl_tree

Definition: avl.h:110

Definition at line 164 of file avl.h.

◆ AVL_TREE_INIT

#define AVL_TREE_INIT	(	_name,
		_comp,
		_allow_dups,
		_cmp_ptr
	)

Value:

        {                                                       \
                .list_head = LIST_HEAD_INIT(_name.list_head),   \
                .comp = _comp,                                  \
                .allow_dups = _allow_dups,                      \
                .cmp_ptr = _cmp_ptr                             \
        }

Definition at line 156 of file avl.h.

◆ EXPORT

#define EXPORT ( sym ) sym

Definition at line 50 of file avl.h.

Typedef Documentation

◆ avl_tree_comp

typedef int(* avl_tree_comp) (const void *k1, const void *k2, void *ptr)

Prototype for avl comparators

Parameters

k1	first key
k2	second key
ptr	custom data for tree comparator

Returns: +1 if k1>k2, -1 if k1<k2, 0 if k1==k2

Definition at line 104 of file avl.h.

Enumeration Type Documentation

◆ avl_find_mode

enum avl_find_mode

internal enum for avl_find_... macros

Enumerator
AVL_FIND_EQUAL
AVL_FIND_LESSEQUAL
AVL_FIND_GREATEREQUAL

Definition at line 150 of file avl.h.

                    {
   AVL_FIND_EQUAL,
   AVL_FIND_LESSEQUAL,
   AVL_FIND_GREATEREQUAL
 };

Function Documentation

◆ __avl_find_element()

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

inlinestatic

Internal function to support returning the element from a avl tree query

Parameters

tree	pointer to avl tree
key	pointer to key
offset	offset of node inside the embedded struct
mode	mode of lookup operation (less equal, equal or greater equal)
pointer	to elemen, NULL if no fitting one was found

Definition at line 213 of file avl.h.

                                                                                                          {
   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);
 }

◆ avl_delete()

void avl_delete	(	struct avl_tree *	tree,
		struct avl_node *	node
	)

Remove a node from an avl tree

Parameters

tree	pointer to tree
node	pointer to node

Definition at line 307 of file avl.c.

 {
   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(&node->list, &tree->list_head)
         && !(next = avl_next(node))->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);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ avl_find()

struct avl_node* avl_find	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds a node in an avl-tree with a certain key

Parameters

tree	pointer to avl-tree
key	pointer to key

Returns: pointer to avl-node with key, NULL if no node with this key exists.

Definition at line 115 of file avl.c.

 {
   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;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ avl_find_greaterequal()

struct avl_node* avl_find_greaterequal	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds the first node in an avl-tree with a key greater or equal than the specified key

Parameters

tree	pointer to avl-tree
key	pointer to specified key

Returns: pointer to avl-node, NULL if no node with key greater or equal specified key exists.

Definition at line 179 of file avl.c.

                                                                     {
   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(&node->list, &tree->list_head)) {
       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(&node->list, &tree->list_head)) {
       break;
     }
  
     next = (struct avl_node *)node->list.prev;
     diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
   }
   return node;
 }

Here is the call graph for this function:

◆ avl_find_lessequal()

struct avl_node* avl_find_lessequal	(	const struct avl_tree *	tree,
		const void *	key
	)

Finds the last node in an avl-tree with a key less or equal than the specified key

Parameters

tree	pointer to avl-tree
key	pointer to specified key

Returns: pointer to avl-node, NULL if no node with key less or equal specified key exists.

Definition at line 137 of file avl.c.

                                                                  {
   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(&node->list, &tree->list_head)) {
       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(&node->list, &tree->list_head)) {
       break;
     }
  
     next = (struct avl_node *)node->list.next;
     diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
   }
   return node;
 }

Here is the call graph for this function:

◆ avl_init()

void avl_init	(	struct avl_tree *	tree,
		avl_tree_comp	comp,
		bool	allow_dups,
		void *	ptr
	)

Initialize a new avl_tree struct

Parameters

tree	pointer to avl-tree
comp	pointer to comparator for the tree
allow_dups	true if the tree allows multiple elements with the same
ptr	custom parameter for comparator

Definition at line 92 of file avl.c.

 {
   INIT_LIST_HEAD(&tree->list_head);
   tree->root = NULL;
   tree->count = 0;
   tree->comp = comp;
   tree->allow_dups = allow_dups;
   tree->cmp_ptr = ptr;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ avl_insert()

int avl_insert	(	struct avl_tree *	tree,
		struct avl_node *	new
	)

Inserts an avl_node into a tree

Parameters

tree	pointer to tree
new	pointer to node

Returns: 0 if node was inserted successfully, -1 if it was not inserted because of a key collision

Definition at line 220 of file avl.c.

 {
   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(&new->list, &tree->list_head);
     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(&last->list, &tree->list_head)) {
     next = avl_next(last);
     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;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ avl_is_empty()

static bool avl_is_empty ( struct avl_tree * tree )

inlinestatic

Parameters

tree	pointer to avl-tree

Returns: true if the tree is empty, false otherwise

Definition at line 200 of file avl.h.

                                     {
   return tree->count == 0;
 }

◆ avl_is_first()

static bool avl_is_first	(	struct avl_tree *	tree,
		struct avl_node *	node
	)

inlinestatic

Parameters

tree	pointer to avl-tree
node	pointer to node of the tree

Returns: true if node is the first one of the tree, false otherwise

Definition at line 181 of file avl.h.

                                                            {
   return tree->list_head.next == &node->list;
 }

◆ avl_is_last()

static bool avl_is_last	(	struct avl_tree *	tree,
		struct avl_node *	node
	)

inlinestatic

Parameters

tree	pointer to avl-tree
node	pointer to node of the tree

Returns: true if node is the last one of the tree, false otherwise

Definition at line 191 of file avl.h.

                                                           {
   return tree->list_head.prev == &node->list;
 }

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ avl_find_element

◆ avl_find_ge_element

◆ avl_find_le_element

◆ avl_first_element

◆ avl_for_each_element

◆ avl_for_each_element_reverse

◆ avl_for_each_element_reverse_safe

◆ avl_for_each_element_safe

◆ avl_for_element_range

◆ avl_for_element_range_reverse

◆ avl_for_element_range_reverse_safe

◆ avl_for_element_range_safe

◆ avl_for_element_to_last

◆ avl_for_element_to_last_reverse

◆ avl_for_first_to_element

◆ avl_for_first_to_element_reverse

◆ avl_last_element

◆ avl_next_element

◆ avl_prev_element

◆ avl_remove_all_elements

◆ AVL_TREE

◆ AVL_TREE_INIT

◆ EXPORT

Typedef Documentation

◆ avl_tree_comp

Enumeration Type Documentation

◆ avl_find_mode

Function Documentation

◆ __avl_find_element()

◆ avl_delete()

◆ avl_find()

◆ avl_find_greaterequal()

◆ avl_find_lessequal()

◆ avl_init()

◆ avl_insert()

◆ avl_is_empty()

◆ avl_is_first()

◆ avl_is_last()