et-forest.c File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "et-forest.h"
#include "alloc-pool.h"

Include dependency graph for et-forest.c:

Data Structures
struct	et_occ

Functions
static void	set_depth ()
static void	set_depth_add ()
static void	set_prev ()
static void	set_next ()
static void	et_recomp_min ()
static void	et_splay ()
static struct et_occ *	et_new_occ ()
struct et_node *	et_new_tree ()
void	et_free_tree ()
void	et_free_tree_force ()
void	et_free_pools ()
void	et_set_father ()
void	et_split ()
struct et_node *	et_nca ()
bool	et_below ()
struct et_node *	et_root ()

Variables
static alloc_pool	et_nodes
static alloc_pool	et_occurrences

---

Function Documentation

bool et_below

(

)

Checks whether the node UP is an ancestor of the node DOWN.

In case O1 and O2 are in two different trees, we must just restore the original state.

Referenced by nearest_common_dominator_for_set().

void et_free_pools

(

void

)

Release the alloc pools, if they are empty.

void et_free_tree

(

)

Releases et tree T.

References free_alloc_pool_if_empty().

void et_free_tree_force

(

)

Releases et tree T without maintaining other nodes.

struct et_node* et_nca ( )

read

Finds the nearest common ancestor of the nodes N1 and N2.

O1 and O2 are in different components of the forest.

Referenced by get_dominated_to_depth().

static struct et_occ* et_new_occ ( )

staticread

Create a new et tree occurrence of NODE.

struct et_node* et_new_tree ( )

read

Create a new et tree containing DATA.

Referenced by assign_dfs_numbers().

static void et_recomp_min ( )

inlinestatic

Recompute minimum for occurrence OCC.

References et_occ::depth, et_occ::min, and et_occ::min_occ.

Referenced by et_splay().

struct et_node* et_root ( )

read

Returns the root of the tree that contains NODE.

The root of the tree corresponds to the rightmost occurrence in the represented path.

void et_set_father

(

)

Sets father of et tree T to FATHER.

Update the path represented in the splay tree.

 Update the tree.   

Referenced by get_dominated_by_region().

static void et_splay ( )

static

Splay the occurrence OCC to the root of the tree.

             zig  

             zag  

             zig zig  

             zag zig  

             zig zag  

             zag zag  

References et_recomp_min(), et_occ::min, et_occ::min_occ, et_occ::next, NULL, et_occ::parent, et_occ::prev, set_depth(), set_depth_add(), set_next(), and set_prev().

void et_split

(

)

Splits the edge from T to its father.

Update the path represented by the splay tree.

 Update the tree.   

References et_node::left, and et_node::right.

Referenced by get_dominated_by_region().

static void set_depth ( )

inlinestatic

Changes depth of OCC to D.

Referenced by et_splay().

static void set_depth_add ( )

inlinestatic

Adds D to the depth of OCC.

Referenced by et_splay().

static void set_next ( )

inlinestatic

Sets next field of OCC to P.

Referenced by et_splay().

static void set_prev ( )

inlinestatic

Sets prev field of OCC to P.

Referenced by et_splay().

---

Variable Documentation

alloc_pool et_nodes

static

alloc_pool et_occurrences

static