GCC Middle and Back End API Reference
|
#include <et-forest.h>
Data Fields | |
void * | data |
int | dfs_num_in |
int | dfs_num_out |
struct et_node * | father |
struct et_node * | son |
struct et_node * | left |
struct et_node * | right |
struct et_occ * | rightmost_occ |
struct et_occ * | parent_occ |
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 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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 <http://www.gnu.org/licenses/>.
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 1 / | \ 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.
void* et_node::data |
int et_node::dfs_num_in |
Referenced by assign_dfs_numbers(), bb_dom_dfs_in(), and dominated_by_p().
int et_node::dfs_num_out |
Referenced by assign_dfs_numbers(), bb_dom_dfs_out(), and dominated_by_p().
Referenced by et_set_father(), and et_split().
Referenced by et_free_tree_force(), et_set_father(), and et_split().
Referenced by assign_dfs_numbers(), et_set_father(), et_split(), and next_dom_son().
Referenced by et_below(), et_free_tree(), et_free_tree_force(), et_nca(), et_root(), et_set_father(), and et_split().
Referenced by assign_dfs_numbers(), et_free_tree(), et_set_father(), et_split(), first_dom_son(), get_dominated_by(), and next_dom_son().