/*                                                                      tab:8
 *
 * find_comp.sc - find connected components given local stars
 *
 * "Copyright (c) 1993 by Steve Lumetta and The Regents of the University 
 * of California.  All rights reserved."
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice and the following
 * two paragraphs appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Author:          Steve Lumetta
 * Version:         201
 * Creation Date:   Thu May 12 17:22:27 1994
 * Filename:        find_comp.sc
 * History:
 */

#include <stdio.h>
#include <split-c/split-c.h>
#include "connect.h"

static volatile int merge_flag;
#ifndef GAM_COMPLIANT
static void merge_list_handler (int proc, node_t *comp, int addr_p,
				void *addr_a);
static void merge_list_reply_handler (int addr_p, void *addr_a);
#else
static void merge_list_handler (int proc, node_t *comp, int addr_p,
				void *addr_a);
static void merge_list_reply_handler (int ignore, int addr_p, void *addr_a);
#endif


static edge_t *global remainder;

double timer, local_time, update_time, global_time, max_conn_time;

extern int percent;

node_t *all_find_components (int n_vertices, node_t *comp_list)
{
    node_t *comp, **c_ptr, *global parent, *global gparent;
    node_t *done_list, *no_jump;
    edge_t *global edge, *global *global e_ptr, l_edge;
    int other_val, i, j, iteration, complete;
    unsigned mp = MYPROC;

#ifndef FAST
    double phase1, phase2, phase3, phase4, phase5;
    double phase6, phase7, phase8, elapsed;
    int num_hooks = 0, not_hooked;
    double it_timer;
    
    phase1 = phase2 = phase3 = phase4 = phase5 = phase6 = phase7 = phase8 = 0;
    global_time = get_seconds();
#endif
    
    /* Stars with no edges coming out are kept in done_list. */
    done_list = NULL;
    
    for (iteration = 0; ; iteration++) {

#ifndef FAST
	it_timer = get_seconds ();
	elapsed = get_seconds();
#endif
	
	/* Check for completion--this is done before marking stars so that
	   an extra iteration will be done to ensure value propagation to
	   all children. */
	complete = all_reduce_to_all_add (comp_list == NULL);
	if (complete == PROCS) break;

	/* Move stars to done list if they have no links. */
	c_ptr = &comp_list;
	while (*c_ptr != NULL) {
	    comp = *c_ptr;
	    if (comp->parent->edges == NULL) {
		*c_ptr = comp->queue;
		comp->queue = done_list;
		done_list = comp;
	    }
	    else
		c_ptr = &(comp->queue);
	}
	barrier ();  /* FIXME: Needed? */

#ifndef FAST
	phase1 += get_seconds() - elapsed;

	elapsed = get_seconds();

	not_hooked = 0;
#endif
	/* Try to attach all of our stars to other components
	   with higher component number. */
	for (comp = comp_list; comp != NULL; comp = comp->queue) {
	    e_ptr = toglobal (mp, &comp->edges);
	    edge = comp->edges;
	    while (edge != NULL) {
		l_edge = *edge;
		other_val = l_edge.node->value;
		if (comp->value > other_val) break;
		e_ptr = &edge->next;
		edge = l_edge.next;
	    }
	    if (edge != NULL) {
		*e_ptr = l_edge.next;
		comp->parent = l_edge.node;
		l_edge.node->parent->stagnant :- 0;
		comp->value = other_val;
		comp->stagnant = 0;
#ifndef FAST
		num_hooks++;
#endif
	    }
#ifndef FAST
	    else if (comp->edges)
		not_hooked++;
#endif
	}
	all_store_sync();
#ifndef FAST
	phase2 += get_seconds() - elapsed;

	elapsed = get_seconds();
#endif
	for (comp = comp_list; comp != NULL; comp = comp->queue) {
	    if (!comp->stagnant || comp->edges == NULL)
		continue;
	    edge = comp->edges;
	    if (toproc (edge) == mp) {
		comp->edges = edge->next;
		comp->parent = edge->node;
		comp->value = edge->node->value;
	    } else {
		l_edge = *edge;
		comp->edges = l_edge.next;
		comp->parent = l_edge.node;
		comp->value = l_edge.node->value;
	    }
#ifndef FAST
	    num_hooks++;
#endif
	}		    
	barrier ();
#ifndef FAST
	phase8 += get_seconds() - elapsed;

	elapsed = get_seconds();
#endif
	/* Now double the parent pointers one or more times. */
	no_jump = NULL;
	while (1) {
	    c_ptr = &comp_list;
	    comp = *c_ptr;
	    while (comp != NULL) {
		node_t *global p, *global gp;

		p = comp->parent;
		gp = p->parent;
		if (p == gp) {
		    comp->value := p->value;
		    *c_ptr = comp->queue;
		    comp->queue = no_jump;
		    no_jump = comp;
		    comp = *c_ptr;
		    continue;
		}
		comp->parent = gp;
		c_ptr = &comp->queue;
		comp = comp->queue;
	    }
	    sync ();
	    complete = all_reduce_to_all_add (comp_list == NULL);
	    if (complete == PROCS) break;
	}
	comp_list = no_jump;
#ifndef FAST
	phase3 += get_seconds() - elapsed;

	elapsed = get_seconds();
#endif
	for (comp = comp_list; comp; comp = comp->queue) {
	    comp->stagnant = 1;
	    e_ptr = toglobal (mp, &comp->edges);
	    edge = comp->edges;
	    while (edge != NULL) {
		l_edge = *edge;
		if (l_edge.node->value == comp->value)
		    *e_ptr = l_edge.next;
		else
		    e_ptr = &edge->next;
		edge = l_edge.next;
	    }
	}
	barrier ();
#ifndef FAST
	phase5 += get_seconds() - elapsed;

	elapsed = get_seconds();
#endif
	/* Now append the edge-list to your parent's edge list
	   only if you are a star.  Note that only stars use edges
	   to contract components. */
	for (comp = comp_list; comp; comp = comp->queue) {
	    if (comp->parent != toglobal (mp, comp)) {
		/* Append edges to the parent list. */
		if (comp->edges != NULL) {
		    e_ptr = toglobal (mp, &comp->edges);
		    while (*e_ptr != NULL)
			e_ptr = &(*e_ptr)->next;
		    merge_flag = 0;
#ifndef GAM_COMPLIANT
		    am_request4 (toproc (comp->parent), merge_list_handler,
				  mp, (int)tolocal (comp->parent),
				  toproc (comp->edges),
				  (int)tolocal (comp->edges));
#else
		    am_request_3 (toproc (comp->parent), merge_list_handler,
				  (int)tolocal (comp->parent),
				  toproc (comp->edges),
				  (int)tolocal (comp->edges));
#endif
		    while (merge_flag != 1) am_poll ();
		    *e_ptr = remainder;
		    comp->edges = NULL;
		}
	    }
	}
	barrier ();

#ifndef FAST
	phase6 += get_seconds() - elapsed;

	it_timer = get_seconds () - it_timer;

	not_hooked = all_reduce_to_one_add (not_hooked);

#if 0	
	on_one {
	    fprintf (fp,
     "End of iteration %d (time = %.6lf). Completed: %d, Didnt hook: %d\n",
		     iteration, it_timer, complete, not_hooked);
	    fprintf(fp, "Donep: %8.6f, Hook:   %8.6f, Jumping: %8.6f secs\n",
		    phase1, phase2, phase3);
	    fprintf(fp, "Starp: %8.6f, Dups:   %8.6f, Append:  %8.6f secs\n",
		    phase4, phase5, phase6);
	}
#endif
	
#endif
    }

    /* Note that the way we construct the connected components,
       we double only on the roots of the trees found by local dfs.
       Do a doubling operation for the children of these trees also. */
#ifndef FAST
    elapsed = get_seconds ();
#endif
    {
	node_t* comp;
	node_t* stop;

	for (comp = tolocal (node_list), stop = comp + n_vertices;
	     comp != stop; comp++) {
	    node_t* global parent = comp->parent;
	    if (toproc (parent) == mp) {
		node_t* lpar = tolocal (parent);
		
		comp->parent = lpar->parent;
		comp->value = lpar->value;
	    }
	}
    }
#ifndef FAST
    phase7 = get_seconds () - elapsed;
    global_time = get_seconds() - global_time;
#endif
    timer = get_seconds() - timer;
    
#ifndef FAST
    on_one {
	if (PROCS > 1)
	    fprintf (fp,
		     "Finding components took %d iterations in %7.4f secs.\n",
		     iteration, timer);
	else
	    fprintf (fp, "Finding components took %7.4f secs.\n", local_time);
    }
    /* Find the resulting number of components.  Useful for debugging. */
    {
	int num_comp = 0;
	
	/* Count the number of connected components. */
	for (comp = done_list; comp; comp = comp->queue)
	    if (comp->parent == toglobal (mp, comp))
		num_comp++;
	num_comp = all_reduce_to_all_add(num_comp);
	num_hooks = all_reduce_to_all_add(num_hooks);
	on_one {
	    fprintf(fp, "Number of components: %d (%d hooked)\n", num_comp,
		    num_hooks);
	    fprintf(fp, "Donep: %8.6f, Hook:   %8.6f, Jumping: %8.6f secs ",
		    phase1, phase2, phase3);
	    fprintf(fp, "Starp: %8.6f, Dups:   %8.6f, Append:  %8.6f secs ",
		    phase4, phase5, phase6);
	    fprintf(fp, "Final: %8.6f  UHook:  %8.6f, Conn:    %8.6f secs\n", phase7, phase8, max_conn_time);
	    fprintf (fp, "%d %7.4f, Local: %7.4f Update: %7.4f Global: %7.4f\n",
		     n_vertices, timer, local_time, update_time, global_time);
	}	
    }
#else
    on_one {
	if (PROCS > 1)
	    fprintf (fp, "%7.4f\n", timer);
	else
	    fprintf (fp, "%7.4f\n", local_time);
    }
#endif
#if 0
    on_one
	fprintf(fp, "complete\n");
#endif
}

#ifndef GAM_COMPLIANT
static void merge_list_handler (int proc, node_t *comp, int addr_p,
				void *addr_a)
{
    edge_t *global old_edges;

    old_edges = comp->edges;
    comp->edges = toglobal (addr_p, addr_a);
    am_reply2 (proc, merge_list_reply_handler, toproc (old_edges),
	       (int)tolocal (old_edges));
}
#else
static void merge_list_handler (int proc, node_t *comp, int addr_p,
				void *addr_a)
{
    edge_t *global old_edges;

    old_edges = comp->edges;
    comp->edges = toglobal (addr_p, addr_a);
    am_reply_2 (proc, merge_list_reply_handler, toproc (old_edges),
	       (int)tolocal (old_edges));
}
#endif

#ifndef GAM_COMPLIANT
static void merge_list_reply_handler (int addr_p, void *addr_a)
{
    remainder = toglobal (addr_p, addr_a);
    merge_flag = 1;
}
#else
static void merge_list_reply_handler (int ignore, int addr_p, void *addr_a)
{
    remainder = toglobal (addr_p, addr_a);
    merge_flag = 1;
}
#endif