GCC Middle and Back End API Reference
et_node Struct Reference

#include <et-forest.h>

Collaboration diagram for et_node:

Data Fields

int dfs_num_in
int dfs_num_out
struct et_nodefather
struct et_nodeson
struct et_nodeleft
struct et_noderight
struct et_occrightmost_occ
struct et_occparent_occ

Detailed Description

Et-forest data structure implementation.
Copyright (C) 2002-2024 Free Software Foundation, Inc.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; see the file COPYING3.  If not see
This package implements ET forest data structure. Each tree in
the structure maintains a tree structure and offers logarithmic time
for tree operations (insertion and removal of nodes and edges) and
poly-logarithmic time for nearest common ancestor.

ET tree stores its structure as a sequence of symbols obtained
by dfs(root)

dfs (node)
  s = node;
  for each child c of node do
    s = concat (s, c, node);
  return s;

For example for tree

       / | \
      2  3  4
    / |
   4  5

the sequence is 1 2 4 2 5 3 1 3 1 4 1.

The sequence is stored in a slightly modified splay tree.
In order to support various types of node values, a hashtable
is used to convert node values to the internal representation.   
The node representing the node in an et tree.   

Field Documentation

◆ data

◆ dfs_num_in

int et_node::dfs_num_in

◆ dfs_num_out

int et_node::dfs_num_out

◆ father

◆ left

struct et_node* et_node::left

Referenced by et_set_father(), and et_split().

◆ parent_occ

struct et_occ* et_node::parent_occ

◆ right

◆ rightmost_occ

◆ son

The documentation for this struct was generated from the following file: