OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [et-forest.h] - Diff between revs 154 and 816

Go to most recent revision | Only display areas with differences | Details | Blame | View Log

Rev 154 Rev 816
/* Et-forest data structure implementation.
/* Et-forest data structure implementation.
   Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
   Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
 
 
   This program is free software; you can redistribute it and/or modify
   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
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.
   (at your option) any later version.
 
 
   This program is distributed in the hope that it will be useful,
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   GNU General Public License for more details.
 
 
   You should have received a copy of the GNU General Public License
   You should have received a copy of the GNU General Public License
   along with this program; see the file COPYING3.  If not see
   along with this program; see the file COPYING3.  If not see
   <http://www.gnu.org/licenses/>.  */
   <http://www.gnu.org/licenses/>.  */
 
 
/* This package implements ET forest data structure. Each tree in
/* This package implements ET forest data structure. Each tree in
   the structure maintains a tree structure and offers logarithmic time
   the structure maintains a tree structure and offers logarithmic time
   for tree operations (insertion and removal of nodes and edges) and
   for tree operations (insertion and removal of nodes and edges) and
   poly-logarithmic time for nearest common ancestor.
   poly-logarithmic time for nearest common ancestor.
 
 
   ET tree stores its structure as a sequence of symbols obtained
   ET tree stores its structure as a sequence of symbols obtained
   by dfs(root)
   by dfs(root)
 
 
   dfs (node)
   dfs (node)
   {
   {
     s = node;
     s = node;
     for each child c of node do
     for each child c of node do
       s = concat (s, c, node);
       s = concat (s, c, node);
     return s;
     return s;
   }
   }
 
 
   For example for tree
   For example for tree
 
 
            1
            1
          / | \
          / | \
         2  3  4
         2  3  4
       / |
       / |
      4  5
      4  5
 
 
   the sequence is 1 2 4 2 5 3 1 3 1 4 1.
   the sequence is 1 2 4 2 5 3 1 3 1 4 1.
 
 
   The sequence is stored in a slightly modified splay tree.
   The sequence is stored in a slightly modified splay tree.
   In order to support various types of node values, a hashtable
   In order to support various types of node values, a hashtable
   is used to convert node values to the internal representation.  */
   is used to convert node values to the internal representation.  */
 
 
#ifndef _ET_TREE_H
#ifndef _ET_TREE_H
#define _ET_TREE_H
#define _ET_TREE_H
 
 
#include <ansidecl.h>
#include <ansidecl.h>
#include <stddef.h>
#include <stddef.h>
 
 
#ifdef __cplusplus
#ifdef __cplusplus
extern "C" {
extern "C" {
#endif /* __cplusplus */
#endif /* __cplusplus */
 
 
/* The node representing the node in an et tree.  */
/* The node representing the node in an et tree.  */
struct et_node
struct et_node
{
{
  void *data;                   /* The data represented by the node.  */
  void *data;                   /* The data represented by the node.  */
 
 
  int dfs_num_in, dfs_num_out;  /* Number of the node in the dfs ordering.  */
  int dfs_num_in, dfs_num_out;  /* Number of the node in the dfs ordering.  */
 
 
  struct et_node *father;       /* Father of the node.  */
  struct et_node *father;       /* Father of the node.  */
  struct et_node *son;          /* The first of the sons of the node.  */
  struct et_node *son;          /* The first of the sons of the node.  */
  struct et_node *left;
  struct et_node *left;
  struct et_node *right;        /* The brothers of the node.  */
  struct et_node *right;        /* The brothers of the node.  */
 
 
  struct et_occ *rightmost_occ; /* The rightmost occurrence.  */
  struct et_occ *rightmost_occ; /* The rightmost occurrence.  */
  struct et_occ *parent_occ;    /* The occurrence of the parent node.  */
  struct et_occ *parent_occ;    /* The occurrence of the parent node.  */
};
};
 
 
struct et_node *et_new_tree (void *data);
struct et_node *et_new_tree (void *data);
void et_free_tree (struct et_node *);
void et_free_tree (struct et_node *);
void et_free_tree_force (struct et_node *);
void et_free_tree_force (struct et_node *);
void et_free_pools (void);
void et_free_pools (void);
void et_set_father (struct et_node *, struct et_node *);
void et_set_father (struct et_node *, struct et_node *);
void et_split (struct et_node *);
void et_split (struct et_node *);
struct et_node *et_nca (struct et_node *, struct et_node *);
struct et_node *et_nca (struct et_node *, struct et_node *);
bool et_below (struct et_node *, struct et_node *);
bool et_below (struct et_node *, struct et_node *);
 
 
#ifdef __cplusplus
#ifdef __cplusplus
}
}
#endif /* __cplusplus */
#endif /* __cplusplus */
 
 
#endif /* _ET_TREE_H */
#endif /* _ET_TREE_H */
 
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.