/* ET-trees datastructure implementation. | |

Contributed by Pavel Nejedly | |

Copyright (C) 2002 Free Software Foundation, Inc. | |

This file is part of the libiberty library. | |

Libiberty is free software; you can redistribute it and/or | |

modify it under the terms of the GNU Library General Public | |

License as published by the Free Software Foundation; either | |

version 2 of the License, or (at your option) any later version. | |

Libiberty 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 | |

Library General Public License for more details. | |

You should have received a copy of the GNU Library General Public | |

License along with libiberty; see the file COPYING.LIB. If | |

not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |

Boston, MA 02111-1307, USA. | |

The ET-forest structure is described in: | |

D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. | |

J. G'omput. System Sci., 26(3):362 381, 1983. | |

*/ | |

#include "config.h" | |

#include "system.h" | |

#include "et-forest.h" | |

struct et_forest_occurrence; | |

typedef struct et_forest_occurrence* et_forest_occurrence_t; | |

/* The ET-forest type. */ | |

struct et_forest | |

{ | |

/* Linked list of nodes is used to destroy the structure. */ | |

int nnodes; | |

}; | |

/* Single occurrence of node in ET-forest. | |

A single node may have multiple occurrences. | |

*/ | |

struct et_forest_occurrence | |

{ | |

/* Parent in the splay-tree. */ | |

et_forest_occurrence_t parent; | |

/* Children in the splay-tree. */ | |

et_forest_occurrence_t left, right; | |

/* Counts of vertices in the two splay-subtrees. */ | |

int count_left, count_right; | |

/* Next occurrence of this node in the sequence. */ | |

et_forest_occurrence_t next; | |

/* The node, which this occurrence is of. */ | |

et_forest_node_t node; | |

}; | |

/* ET-forest node. */ | |

struct et_forest_node | |

{ | |

et_forest_t forest; | |

void *value; | |

/* First and last occurrence of this node in the sequence. */ | |

et_forest_occurrence_t first, last; | |

}; | |

static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t)); | |

static void remove_all_occurrences PARAMS ((et_forest_node_t)); | |

static inline et_forest_occurrence_t find_leftmost_node | |

PARAMS ((et_forest_occurrence_t)); | |

static inline et_forest_occurrence_t find_rightmost_node | |

PARAMS ((et_forest_occurrence_t)); | |

static int calculate_value PARAMS ((et_forest_occurrence_t)); | |

/* Return leftmost node present in the tree roted by OCC. */ | |

static inline et_forest_occurrence_t | |

find_leftmost_node (occ) | |

et_forest_occurrence_t occ; | |

{ | |

while (occ->left) | |

occ = occ->left; | |

return occ; | |

} | |

/* Return rightmost node present in the tree roted by OCC. */ | |

static inline et_forest_occurrence_t | |

find_rightmost_node (occ) | |

et_forest_occurrence_t occ; | |

{ | |

while (occ->right) | |

occ = occ->right; | |

return occ; | |

} | |

/* Operation splay for splay tree structure representing ocuurences. */ | |

static et_forest_occurrence_t | |

splay (node) | |

et_forest_occurrence_t node; | |

{ | |

et_forest_occurrence_t parent; | |

et_forest_occurrence_t grandparent; | |

while (1) | |

{ | |

parent = node->parent; | |

if (! parent) | |

return node; /* node == root. */ | |

grandparent = parent->parent; | |

if (! grandparent) | |

break; | |

/* Now there are four possible combinations: */ | |

if (node == parent->left) | |

{ | |

if (parent == grandparent->left) | |

{ | |

et_forest_occurrence_t node1, node2; | |

int count1, count2; | |

node1 = node->right; | |

count1 = node->count_right; | |

node2 = parent->right; | |

count2 = parent->count_right; | |

grandparent->left = node2; | |

grandparent->count_left = count2; | |

if (node2) | |

node2->parent = grandparent; | |

parent->left = node1; | |

parent->count_left = count1; | |

if (node1) | |

node1->parent = parent; | |

parent->right = grandparent; | |

parent->count_right = count2 + grandparent->count_right + 1; | |

node->right = parent; | |

node->count_right = count1 + parent->count_right + 1; | |

node->parent = grandparent->parent; | |

parent->parent = node; | |

grandparent->parent = parent; | |

if (node->parent) | |

{ | |

if (node->parent->left == grandparent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

else | |

{ | |

/* parent == grandparent->right && node == parent->left*/ | |

et_forest_occurrence_t node1, node2; | |

int count1, count2; | |

node1 = node->left; | |

count1 = node->count_left; | |

node2 = node->right; | |

count2 = node->count_right; | |

grandparent->right = node1; | |

grandparent->count_right = count1; | |

if (node1) | |

node1->parent = grandparent; | |

parent->left = node2; | |

parent->count_left = count2; | |

if (node2) | |

node2->parent = parent; | |

node->left = grandparent; | |

node->count_left = grandparent->count_left + count1 + 1; | |

node->right = parent; | |

node->count_right = parent->count_right + count2 + 1; | |

node->parent = grandparent->parent; | |

parent->parent = node; | |

grandparent->parent = node; | |

if (node->parent) | |

{ | |

if (node->parent->left == grandparent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

} | |

else | |

{ | |

/* node == parent->right. */ | |

if (parent == grandparent->left) | |

{ | |

et_forest_occurrence_t node1, node2; | |

int count1, count2; | |

node1 = node->left; | |

count1 = node->count_left; | |

node2 = node->right; | |

count2 = node->count_right; | |

parent->right = node1; | |

parent->count_right = count1; | |

if (node1) | |

node1->parent = parent; | |

grandparent->left = node2; | |

grandparent->count_left = count2; | |

if (node2) | |

node2->parent = grandparent; | |

node->left = parent; | |

node->count_left = parent->count_left + count1 + 1; | |

node->right = grandparent; | |

node->count_right = grandparent->count_right + count2 + 1; | |

node->parent = grandparent->parent; | |

parent->parent = node; | |

grandparent->parent = node; | |

if (node->parent) | |

{ | |

if (node->parent->left == grandparent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

else | |

{ | |

/* parent == grandparent->right && node == parent->right*/ | |

et_forest_occurrence_t node1, node2; | |

int count1, count2; | |

node1 = node->left; | |

count1 = node->count_left; | |

node2 = parent->left; | |

count2 = parent->count_left; | |

grandparent->right = node2; | |

grandparent->count_right = count2; | |

if (node2) | |

node2->parent = grandparent; | |

parent->right = node1; | |

parent->count_right = count1; | |

if (node1) | |

node1->parent = parent; | |

parent->left = grandparent; | |

parent->count_left = count2 + grandparent->count_left + 1; | |

node->left = parent; | |

node->count_left = count1 + parent->count_left + 1; | |

node->parent = grandparent->parent; | |

parent->parent = node; | |

grandparent->parent = parent; | |

if (node->parent) | |

{ | |

if (node->parent->left == grandparent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

} | |

} | |

/* parent == root. */ | |

/* There are two possible combinations: */ | |

if (node == parent->left) | |

{ | |

et_forest_occurrence_t node1; | |

int count1; | |

node1 = node->right; | |

count1 = node->count_right; | |

parent->left = node1; | |

parent->count_left = count1; | |

if (node1) | |

node1->parent = parent; | |

node->right = parent; | |

node->count_right = parent->count_right + 1 + count1; | |

node->parent = parent->parent; /* the same as = 0; */ | |

parent->parent = node; | |

if (node->parent) | |

{ | |

if (node->parent->left == parent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

else | |

{ | |

/* node == parent->right. */ | |

et_forest_occurrence_t node1; | |

int count1; | |

node1 = node->left; | |

count1 = node->count_left; | |

parent->right = node1; | |

parent->count_right = count1; | |

if (node1) | |

node1->parent = parent; | |

node->left = parent; | |

node->count_left = parent->count_left + 1 + count1; | |

node->parent = parent->parent; /* the same as = 0; */ | |

parent->parent = node; | |

if (node->parent) | |

{ | |

if (node->parent->left == parent) | |

node->parent->left = node; | |

else | |

node->parent->right = node; | |

} | |

} | |

return node; | |

} | |

/* Remove all occurences of the given node before destroying the node. */ | |

static void | |

remove_all_occurrences (forest_node) | |

et_forest_node_t forest_node; | |

{ | |

et_forest_occurrence_t first = forest_node->first; | |

et_forest_occurrence_t last = forest_node->last; | |

et_forest_occurrence_t node; | |

splay (first); | |

if (first->left) | |

first->left->parent = 0; | |

if (first->right) | |

first->right->parent = 0; | |

if (last != first) | |

{ | |

splay (last); | |

if (last->left) | |

last->left->parent = 0; | |

if (last->right) | |

last->right->parent = 0; | |

} | |

if (last->right && first->left) /* actually, first->left would suffice. */ | |

{ | |

/* Need to join them. */ | |

et_forest_occurrence_t prev_node, next_node; | |

prev_node = splay (find_rightmost_node (first->left)); | |

next_node = splay (find_leftmost_node (last->right)); | |

/* prev_node and next_node are consecutive occurencies | |

of the same node. */ | |

if (prev_node->next != next_node) | |

abort (); | |

prev_node->right = next_node->right; | |

prev_node->count_right = next_node->count_right; | |

prev_node->next = next_node->next; | |

if (prev_node->right) | |

prev_node->right->parent = prev_node; | |

if (prev_node->node->last == next_node) | |

prev_node->node->last = prev_node; | |

free (next_node); | |

} | |

if (first != last) | |

{ | |

node = first->next; | |

while (node != last) | |

{ | |

et_forest_occurrence_t next_node; | |

splay (node); | |

if (node->left) | |

node->left->parent = 0; | |

if (node->right) | |

node->right->parent = 0; | |

next_node = node->next; | |

free (node); | |

node = next_node; | |

} | |

} | |

free (first); | |

if (first != last) | |

free (last); | |

} | |

/* Calculate ET value of the given node. */ | |

static inline int | |

calculate_value (node) | |

et_forest_occurrence_t node; | |

{ | |

int value = node->count_left; | |

while (node->parent) | |

{ | |

if (node == node->parent->right) | |

value += node->parent->count_left + 1; | |

node = node->parent; | |

} | |

return value; | |

} | |

/* Create ET-forest structure. */ | |

et_forest_t | |

et_forest_create () | |

{ | |

et_forest_t forest = xmalloc (sizeof (struct et_forest)); | |

forest->nnodes = 0; | |

return forest; | |

} | |

/* Deallocate the structure. */ | |

void | |

et_forest_delete (forest) | |

et_forest_t forest; | |

{ | |

if (forest->nnodes) | |

abort (); | |

free (forest); | |

} | |

/* Create new node with VALUE and return the edge. | |

Return NULL when memory allocation failed. */ | |

et_forest_node_t | |

et_forest_add_node (forest, value) | |

et_forest_t forest; | |

void *value; | |

{ | |

/* Create node with one occurrence. */ | |

et_forest_node_t node; | |

et_forest_occurrence_t occ; | |

node = xmalloc (sizeof (struct et_forest_node)); | |

occ = xmalloc (sizeof (struct et_forest_occurrence)); | |

node->first = node->last = occ; | |

node->value = value; | |

forest->nnodes++; | |

occ->node = node; | |

occ->left = occ->right = occ->parent = 0; | |

occ->next = 0; | |

occ->count_left = occ->count_right = 0; | |

return node; | |

} | |

/* Add new edge to the tree, return 1 if succesfull. | |

0 indicates that creation of the edge will close the cycle in graph. */ | |

int | |

et_forest_add_edge (forest, parent_node, child_node) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t parent_node; | |

et_forest_node_t child_node; | |

{ | |

et_forest_occurrence_t new_occ, parent_occ, child_occ; | |

if (! parent_node || ! child_node) | |

abort (); | |

parent_occ = parent_node->first; | |

child_occ = child_node->first; | |

splay (parent_occ); | |

splay (child_occ); | |

if (parent_occ->parent) | |

return 0; /* Both child and parent are in the same tree. */ | |

if (child_occ->left) | |

abort (); /* child must be root of its containing tree. */ | |

new_occ = xmalloc (sizeof (struct et_forest_occurrence)); | |

new_occ->node = parent_node; | |

new_occ->left = child_occ; | |

new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */ | |

new_occ->right = parent_occ->right; | |

new_occ->count_right = parent_occ->count_right; | |

new_occ->parent = parent_occ; | |

new_occ->next = parent_occ->next; | |

child_occ->parent = new_occ; | |

parent_occ->right = new_occ; | |

parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1; | |

parent_occ->next = new_occ; | |

if (new_occ->right) | |

new_occ->right->parent = new_occ; | |

if (parent_node->last == parent_occ) | |

parent_node->last = new_occ; | |

return 1; | |

} | |

/* Remove NODE from the tree and all connected edges. */ | |

void | |

et_forest_remove_node (forest, node) | |

et_forest_t forest; | |

et_forest_node_t node; | |

{ | |

remove_all_occurrences (node); | |

forest->nnodes--; | |

free (node); | |

} | |

/* Remove edge from the tree, return 1 if sucesfull, | |

0 indicates nonexisting edge. */ | |

int | |

et_forest_remove_edge (forest, parent_node, child_node) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t parent_node; | |

et_forest_node_t child_node; | |

{ | |

et_forest_occurrence_t parent_pre_occ, parent_post_occ; | |

splay (child_node->first); | |

if (! child_node->first->left) | |

return 0; | |

parent_pre_occ = find_rightmost_node (child_node->first->left); | |

if (parent_pre_occ->node != parent_node) | |

abort (); | |

splay (parent_pre_occ); | |

parent_pre_occ->right->parent = 0; | |

parent_post_occ = parent_pre_occ->next; | |

splay (parent_post_occ); | |

parent_post_occ->left->parent = 0; | |

parent_pre_occ->right = parent_post_occ->right; | |

parent_pre_occ->count_right = parent_post_occ->count_right; | |

if (parent_post_occ->right) | |

parent_post_occ->right->parent = parent_pre_occ; | |

parent_pre_occ->next = parent_post_occ->next; | |

if (parent_post_occ == parent_node->last) | |

parent_node->last = parent_pre_occ; | |

free (parent_post_occ); | |

return 1; | |

} | |

/* Return the parent of the NODE if any, NULL otherwise. */ | |

et_forest_node_t | |

et_forest_parent (forest, node) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t node; | |

{ | |

splay (node->first); | |

if (node->first->left) | |

return find_rightmost_node (node->first->left)->node; | |

else | |

return 0; | |

} | |

/* Return nearest common ancestor of NODE1 and NODE2. | |

Return NULL of they are in different trees. */ | |

et_forest_node_t | |

et_forest_common_ancestor (forest, node1, node2) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t node1; | |

et_forest_node_t node2; | |

{ | |

int value1, value2, max_value; | |

et_forest_node_t ancestor; | |

if (node1 == node2) | |

return node1; | |

if (! node1 || ! node2) | |

abort (); | |

splay (node1->first); | |

splay (node2->first); | |

if (! node1->first->parent) /* The two vertices are in different trees. */ | |

return 0; | |

value2 = calculate_value (node2->first); | |

value1 = calculate_value (node1->first); | |

if (value1 < value2) | |

{ | |

ancestor = node1; | |

max_value = value2; | |

} | |

else | |

{ | |

ancestor = node2; | |

max_value = value1; | |

} | |

while (calculate_value (ancestor->last) < max_value) | |

{ | |

/* Find parent node. */ | |

splay (ancestor->first); | |

ancestor = find_rightmost_node (ancestor->first->left) ->node; | |

} | |

return ancestor; | |

} | |

/* Return the value pointer of node set during it's creation. */ | |

void * | |

et_forest_node_value (forest, node) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t node; | |

{ | |

/* Alloc threading NULL as a special node of the forest. */ | |

if (!node) | |

return NULL; | |

return node->value; | |

} | |

/* Find all sons of NODE and store them into ARRAY allocated by the caller. | |

Return number of nodes found. */ | |

int | |

et_forest_enumerate_sons (forest, node, array) | |

et_forest_t forest ATTRIBUTE_UNUSED; | |

et_forest_node_t node; | |

et_forest_node_t *array; | |

{ | |

int n = 0; | |

et_forest_occurrence_t occ = node->first, stop = node->last, occ1; | |

/* Parent is the rightmost node of the left successor. | |

Look for all occurences having no right succesor | |

and lookup the sons. */ | |

while (occ != stop) | |

{ | |

splay (occ); | |

if (occ->right) | |

{ | |

occ1 = find_leftmost_node (occ->right); | |

if (occ1->node->first == occ1) | |

array[n++] = occ1->node; | |

} | |

occ = occ->next; | |

} | |

return n; | |

} |