projects / thirdparty / gcc.git / blame
| Commit | Line | Data |
|---|---|---|
| 502b8322 AJ |
1 | /* Et-forest data structure implementation. |
| 2 | Copyright (C) 2002, 2003 Free Software Foundation, Inc. | |
| f1cfb09f JH |
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 2 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; if not, write to the Free Software | |
| 16 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
| 17 | ||
| 502b8322 | 18 | /* This package implements ET forest data structure. Each tree in |
| f1cfb09f JH |
19 | the structure maintains a tree structure and offers logarithmic time |
| 20 | for tree operations (insertion and removal of nodes and edges) and | |
| fbe5a4a6 | 21 | poly-logarithmic time for nearest common ancestor. |
| 502b8322 | 22 | |
| 4d6922ee | 23 | ET tree stores its structue as a sequence of symbols obtained |
| f1cfb09f JH |
24 | by dfs(root) |
| 25 | ||
| 502b8322 | 26 | dfs (node) |
| f1cfb09f JH |
27 | { |
| 28 | s = node; | |
| 29 | for each child c of node do | |
| 30 | s = concat (s, c, node); | |
| 31 | return s; | |
| 32 | } | |
| 502b8322 | 33 | |
| f1cfb09f | 34 | For example for tree |
| 502b8322 | 35 | |
| f1cfb09f JH |
36 | 1 |
| 37 | / | \ | |
| 38 | 2 3 4 | |
| 39 | / | | |
| 40 | 4 5 | |
| 502b8322 | 41 | |
| f1cfb09f | 42 | the sequence is 1 2 4 2 5 3 1 3 1 4 1. |
| 502b8322 | 43 | |
| e0bb17a8 | 44 | The sequence is stored in a slightly modified splay tree. |
| f1cfb09f JH |
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 | #include <ansidecl.h> | |
| 52 | #include <stddef.h> | |
| 53 | ||
| 54 | #ifdef __cplusplus | |
| 55 | extern "C" { | |
| 56 | #endif /* __cplusplus */ | |
| 57 | ||
| 58 | typedef struct et_forest *et_forest_t; | |
| 59 | typedef struct et_forest_node *et_forest_node_t; | |
| 60 | ||
| 502b8322 AJ |
61 | extern et_forest_t et_forest_create (void); |
| 62 | ||
| 63 | extern void et_forest_delete (et_forest_t); | |
| 64 | ||
| 65 | extern et_forest_node_t et_forest_add_node (et_forest_t, void *); | |
| 66 | extern int et_forest_add_edge (et_forest_t, et_forest_node_t, | |
| 67 | et_forest_node_t); | |
| 68 | extern void et_forest_remove_node (et_forest_t, et_forest_node_t); | |
| 69 | extern int et_forest_remove_edge (et_forest_t, et_forest_node_t, | |
| 70 | et_forest_node_t); | |
| 71 | extern et_forest_node_t et_forest_parent (et_forest_t, et_forest_node_t); | |
| 72 | extern et_forest_node_t et_forest_common_ancestor (et_forest_t, | |
| 73 | et_forest_node_t, | |
| 74 | et_forest_node_t); | |
| 75 | extern void * et_forest_node_value (et_forest_t, et_forest_node_t); | |
| 76 | extern int et_forest_enumerate_sons (et_forest_t, et_forest_node_t, | |
| 77 | et_forest_node_t *); | |
| f1cfb09f JH |
78 | |
| 79 | #ifdef __cplusplus | |
| 80 | } | |
| 81 | #endif /* __cplusplus */ | |
| 82 | ||
| 83 | #endif /* _ET_TREE_H */ |