Home | History | Annotate | Line # | Download | only in gcc 
      1 /* Et-forest data structure implementation.
      2    Copyright (C) 2002-2022 Free Software Foundation, Inc.
      3 
      4    This program is free software; you can redistribute it and/or modify
      5    it under the terms of the GNU General Public License as published by
      6    the Free Software Foundation; either version 3 of the License, or
      7    (at your option) any later version.
      8 
      9    This program is distributed in the hope that it will be useful,
     10    but WITHOUT ANY WARRANTY; without even the implied warranty of
     11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     12    GNU General Public License for more details.
     13 
     14    You should have received a copy of the GNU General Public License
     15    along with this program; see the file COPYING3.  If not see
     16    <http://www.gnu.org/licenses/>.  */
     17 
     18 /* This package implements ET forest data structure. Each tree in
     19    the structure maintains a tree structure and offers logarithmic time
     20    for tree operations (insertion and removal of nodes and edges) and
     21    poly-logarithmic time for nearest common ancestor.
     22 
     23    ET tree stores its structure as a sequence of symbols obtained
     24    by dfs(root)
     25 
     26    dfs (node)
     27    {
     28      s = node;
     29      for each child c of node do
     30        s = concat (s, c, node);
     31      return s;
     32    }
     33 
     34    For example for tree
     35 
     36             1
     37           / | \
     38          2  3  4
     39        / |
     40       4  5
     41 
     42    the sequence is 1 2 4 2 5 3 1 3 1 4 1.
     43 
     44    The sequence is stored in a slightly modified splay tree.
     45    In order to support various types of node values, a hashtable
     46    is used to convert node values to the internal representation.  */
     47 
     48 #ifndef _ET_TREE_H
     49 #define _ET_TREE_H
     50 
     51 #ifdef __cplusplus
     52 extern "C" {
     53 #endif /* __cplusplus */
     54 
     55 /* The node representing the node in an et tree.  */
     56 struct et_node
     57 {
     58   void *data;			/* The data represented by the node.  */
     59 
     60   int dfs_num_in, dfs_num_out;	/* Number of the node in the dfs ordering.  */
     61 
     62   struct et_node *father;	/* Father of the node.  */
     63   struct et_node *son;		/* The first of the sons of the node.  */
     64   struct et_node *left;
     65   struct et_node *right;	/* The brothers of the node.  */
     66 
     67   struct et_occ *rightmost_occ;	/* The rightmost occurrence.  */
     68   struct et_occ *parent_occ;	/* The occurrence of the parent node.  */
     69 };
     70 
     71 struct et_node *et_new_tree (void *data);
     72 void et_free_tree (struct et_node *);
     73 void et_free_tree_force (struct et_node *);
     74 void et_free_pools (void);
     75 void et_set_father (struct et_node *, struct et_node *);
     76 void et_split (struct et_node *);
     77 struct et_node *et_nca (struct et_node *, struct et_node *);
     78 bool et_below (struct et_node *, struct et_node *);
     79 struct et_node *et_root (struct et_node *);
     80 
     81 #ifdef __cplusplus
     82 }
     83 #endif /* __cplusplus */
     84 
     85 #endif /* _ET_TREE_H */
     86