OPAL (Object Oriented Parallel Accelerator Library) 2024.2
OPAL
avl.cpp File Reference
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "avl.h"
Include dependency graph for avl.cpp:

Go to the source code of this file.

Macros

#define NODE_COUNT(n)
#define L_COUNT(n)
#define R_COUNT(n)
#define CALC_COUNT(n)
#define NODE_DEPTH(n)
#define L_DEPTH(n)
#define R_DEPTH(n)
#define CALC_DEPTH(n)

Functions

unsigned int avl_count (const avl_tree_t *avltree)
avl_node_t * avl_at (const avl_tree_t *avltree, unsigned int index)
unsigned int avl_index (const avl_node_t *avlnode)
int avl_search_closest (const avl_tree_t *avltree, const void *item, avl_node_t **avlnode)
avl_node_t * avl_search (const avl_tree_t *avltree, const void *item)
avl_tree_t * avl_init_tree (avl_tree_t *rc, avl_compare_t cmp, avl_freeitem_t freeitem)
avl_tree_t * avl_alloc_tree (avl_compare_t cmp, avl_freeitem_t freeitem)
void avl_clear_tree (avl_tree_t *avltree)
void avl_free_nodes (avl_tree_t *avltree)
void avl_free_tree (avl_tree_t *avltree)
avl_node_t * avl_init_node (avl_node_t *newnode, void *item)
avl_node_t * avl_insert_top (avl_tree_t *avltree, avl_node_t *newnode)
avl_node_t * avl_insert_before (avl_tree_t *avltree, avl_node_t *node, avl_node_t *newnode)
avl_node_t * avl_insert_after (avl_tree_t *avltree, avl_node_t *node, avl_node_t *newnode)
avl_node_t * avl_insert_node (avl_tree_t *avltree, avl_node_t *newnode)
avl_node_t * avl_insert (avl_tree_t *avltree, void *item)
void avl_unlink_node (avl_tree_t *avltree, avl_node_t *avlnode)
void * avl_delete_node (avl_tree_t *avltree, avl_node_t *avlnode)
void * avl_delete (avl_tree_t *avltree, const void *item)
avl_node_t * avl_fixup_node (avl_tree_t *avltree, avl_node_t *newnode)

Macro Definition Documentation

◆ CALC_COUNT

#define CALC_COUNT ( n)
Value:
(L_COUNT(n) + R_COUNT(n) + 1)
R_COUNT
#define R_COUNT(n)
Definition avl.cpp:40
L_COUNT
#define L_COUNT(n)
Definition avl.cpp:39

Definition at line 41 of file avl.cpp.

◆ CALC_DEPTH

#define CALC_DEPTH ( n)
Value:
((L_DEPTH(n)>R_DEPTH(n)?L_DEPTH(n):R_DEPTH(n)) + 1)
L_DEPTH
#define L_DEPTH(n)
Definition avl.cpp:46
R_DEPTH
#define R_DEPTH(n)
Definition avl.cpp:47

Definition at line 48 of file avl.cpp.

◆ L_COUNT

#define L_COUNT ( n)
Value:
(NODE_COUNT((n)->left))
NODE_COUNT
#define NODE_COUNT(n)
Definition avl.cpp:38

Definition at line 39 of file avl.cpp.

Referenced by avl_at(), and avl_index().

◆ L_DEPTH

#define L_DEPTH ( n)
Value:
(NODE_DEPTH((n)->left))
NODE_DEPTH
#define NODE_DEPTH(n)
Definition avl.cpp:45

Definition at line 46 of file avl.cpp.

◆ NODE_COUNT

#define NODE_COUNT ( n)
Value:
((n) ? (n)->count : 0)

Definition at line 38 of file avl.cpp.

Referenced by avl_count().

◆ NODE_DEPTH

#define NODE_DEPTH ( n)
Value:
((n) ? (n)->depth : 0)

Definition at line 45 of file avl.cpp.

◆ R_COUNT

#define R_COUNT ( n)
Value:
(NODE_COUNT((n)->right))

Definition at line 40 of file avl.cpp.

◆ R_DEPTH

#define R_DEPTH ( n)
Value:
(NODE_DEPTH((n)->right))

Definition at line 47 of file avl.cpp.

Function Documentation

◆ avl_alloc_tree()

avl_tree_t * avl_alloc_tree ( avl_compare_t cmp,
avl_freeitem_t freeitem )

Definition at line 189 of file avl.cpp.

References avl_init_tree().

Referenced by Hypervolume::FromFile().

Here is the call graph for this function:

◆ avl_at()

avl_node_t * avl_at ( const avl_tree_t * avltree,
unsigned int index )

Definition at line 97 of file avl.cpp.

References c, L_COUNT, avl_node_t::left, avl_node_t::right, and avl_tree_t::top.

◆ avl_clear_tree()

void avl_clear_tree ( avl_tree_t * avltree)

Definition at line 193 of file avl.cpp.

References avl_tree_t::head, avl_tree_t::tail, and avl_tree_t::top.

Referenced by avl_free_nodes(), and Hypervolume::hv3_AVL().

◆ avl_count()

unsigned int avl_count ( const avl_tree_t * avltree)

Definition at line 93 of file avl.cpp.

References NODE_COUNT, and avl_tree_t::top.

◆ avl_delete()

void * avl_delete ( avl_tree_t * avltree,
const void * item )

Definition at line 406 of file avl.cpp.

References avl_delete_node(), and avl_search().

Here is the call graph for this function:

◆ avl_delete_node()

void * avl_delete_node ( avl_tree_t * avltree,
avl_node_t * avlnode )

Definition at line 394 of file avl.cpp.

References avl_unlink_node(), avl_tree_t::freeitem, and avl_node_t::item.

Referenced by avl_delete().

Here is the call graph for this function:

◆ avl_fixup_node()

avl_node_t * avl_fixup_node ( avl_tree_t * avltree,
avl_node_t * newnode )

Definition at line 410 of file avl.cpp.

References avl_tree_t::head, avl_node_t::next, avl_node_t::parent, avl_node_t::prev, avl_node_t::right, avl_tree_t::tail, and avl_tree_t::top.

◆ avl_free_nodes()

void avl_free_nodes ( avl_tree_t * avltree)

Definition at line 197 of file avl.cpp.

References avl_clear_tree(), avl_tree_t::freeitem, avl_tree_t::head, avl_node_t::item, and avl_node_t::next.

Referenced by avl_free_tree().

Here is the call graph for this function:

◆ avl_free_tree()

void avl_free_tree ( avl_tree_t * avltree)

Definition at line 218 of file avl.cpp.

References avl_free_nodes().

Here is the call graph for this function:

◆ avl_index()

unsigned int avl_index ( const avl_node_t * avlnode)

Definition at line 118 of file avl.cpp.

References c, L_COUNT, avl_node_t::parent, and avl_node_t::right.

◆ avl_init_node()

avl_node_t * avl_init_node ( avl_node_t * newnode,
void * item )

Definition at line 233 of file avl.cpp.

References avl_node_t::item.

Referenced by avl_insert(), and Hypervolume::hv3_AVL().

◆ avl_init_tree()

avl_tree_t * avl_init_tree ( avl_tree_t * rc,
avl_compare_t cmp,
avl_freeitem_t freeitem )

Definition at line 178 of file avl.cpp.

References avl_tree_t::cmp, avl_tree_t::freeitem, avl_tree_t::head, avl_tree_t::tail, and avl_tree_t::top.

Referenced by avl_alloc_tree().

◆ avl_insert()

avl_node_t * avl_insert ( avl_tree_t * avltree,
void * item )

Definition at line 321 of file avl.cpp.

References avl_init_node(), and avl_insert_node().

Here is the call graph for this function:

◆ avl_insert_after()

avl_node_t * avl_insert_after ( avl_tree_t * avltree,
avl_node_t * node,
avl_node_t * newnode )

Definition at line 274 of file avl.cpp.

References avl_insert_before(), avl_insert_top(), avl_tree_t::head, avl_node_t::next, avl_node_t::parent, avl_node_t::prev, avl_node_t::right, and avl_tree_t::tail.

Referenced by avl_insert_before(), avl_insert_node(), and Hypervolume::hv3_AVL().

Here is the call graph for this function:

◆ avl_insert_before()

avl_node_t * avl_insert_before ( avl_tree_t * avltree,
avl_node_t * node,
avl_node_t * newnode )

Definition at line 248 of file avl.cpp.

References avl_insert_after(), avl_insert_top(), avl_tree_t::head, avl_node_t::left, avl_node_t::next, avl_node_t::parent, avl_node_t::prev, and avl_tree_t::tail.

Referenced by avl_insert_after(), and avl_insert_node().

Here is the call graph for this function:

◆ avl_insert_node()

avl_node_t * avl_insert_node ( avl_tree_t * avltree,
avl_node_t * newnode )

Definition at line 300 of file avl.cpp.

References avl_insert_after(), avl_insert_before(), avl_insert_top(), avl_search_closest(), avl_node_t::item, and avl_tree_t::top.

Referenced by avl_insert().

Here is the call graph for this function:

◆ avl_insert_top()

avl_node_t * avl_insert_top ( avl_tree_t * avltree,
avl_node_t * newnode )

Definition at line 241 of file avl.cpp.

References avl_tree_t::head, avl_node_t::next, avl_node_t::parent, avl_node_t::prev, avl_tree_t::tail, and avl_tree_t::top.

Referenced by avl_insert_after(), avl_insert_before(), avl_insert_node(), and Hypervolume::hv3_AVL().

◆ avl_search()

avl_node_t * avl_search ( const avl_tree_t * avltree,
const void * item )

Definition at line 173 of file avl.cpp.

References avl_search_closest().

Referenced by avl_delete().

Here is the call graph for this function:

◆ avl_search_closest()

int avl_search_closest ( const avl_tree_t * avltree,
const void * item,
avl_node_t ** avlnode )

Definition at line 134 of file avl.cpp.

References c, avl_tree_t::cmp, avl_node_t::item, avl_node_t::left, avl_node_t::right, and avl_tree_t::top.

Referenced by avl_insert_node(), avl_search(), and Hypervolume::hv3_AVL().

◆ avl_unlink_node()

void avl_unlink_node ( avl_tree_t * avltree,
avl_node_t * avlnode )

Definition at line 340 of file avl.cpp.

References avl_tree_t::head, avl_node_t::left, avl_node_t::next, avl_node_t::parent, avl_node_t::prev, avl_node_t::right, avl_tree_t::tail, and avl_tree_t::top.

Referenced by avl_delete_node(), and Hypervolume::hv3_AVL().