kusano 7d535a
kusano 7d535a
/*! @file dsnode_dfs.c
kusano 7d535a
 * \brief Determines the union of row structures of columns within the relaxed node
kusano 7d535a
 *
kusano 7d535a
 * 
kusano 7d535a
 * -- SuperLU routine (version 2.0) --
kusano 7d535a
 * Univ. of California Berkeley, Xerox Palo Alto Research Center,
kusano 7d535a
 * and Lawrence Berkeley National Lab.
kusano 7d535a
 * November 15, 1997
kusano 7d535a
 *
kusano 7d535a
 * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
kusano 7d535a
 *
kusano 7d535a
 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
kusano 7d535a
 * EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
kusano 7d535a
 * 
kusano 7d535a
 * Permission is hereby granted to use or copy this program for any
kusano 7d535a
 * purpose, provided the above notices are retained on all copies.
kusano 7d535a
 * Permission to modify the code and to distribute modified code is
kusano 7d535a
 * granted, provided the above notices are retained, and a notice that
kusano 7d535a
 * the code was modified is included with the above copyright notice.
kusano 7d535a
 * 
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
kusano 7d535a
#include "slu_ddefs.h"
kusano 7d535a
kusano 7d535a
/*! \brief
kusano 7d535a
 *
kusano 7d535a
 * 
kusano 7d535a
 * Purpose
kusano 7d535a
 * =======
kusano 7d535a
 *    dsnode_dfs() - Determine the union of the row structures of those 
kusano 7d535a
 *    columns within the relaxed snode.
kusano 7d535a
 *    Note: The relaxed snodes are leaves of the supernodal etree, therefore, 
kusano 7d535a
 *    the portion outside the rectangular supernode must be zero.
kusano 7d535a
 *
kusano 7d535a
 * Return value
kusano 7d535a
 * ============
kusano 7d535a
 *     0   success;
kusano 7d535a
 *    >0   number of bytes allocated when run out of memory.
kusano 7d535a
 * 
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
int
kusano 7d535a
dsnode_dfs (
kusano 7d535a
	   const int  jcol,	    /* in - start of the supernode */
kusano 7d535a
	   const int  kcol, 	    /* in - end of the supernode */
kusano 7d535a
	   const int  *asub,        /* in */
kusano 7d535a
	   const int  *xa_begin,    /* in */
kusano 7d535a
	   const int  *xa_end,      /* in */
kusano 7d535a
	   int        *xprune,      /* out */
kusano 7d535a
	   int        *marker,      /* modified */
kusano 7d535a
	   GlobalLU_t *Glu          /* modified */
kusano 7d535a
	   )
kusano 7d535a
{
kusano 7d535a
kusano 7d535a
    register int i, k, ifrom, ito, nextl, new_next;
kusano 7d535a
    int          nsuper, krow, kmark, mem_error;
kusano 7d535a
    int          *xsup, *supno;
kusano 7d535a
    int          *lsub, *xlsub;
kusano 7d535a
    int          nzlmax;
kusano 7d535a
    
kusano 7d535a
    xsup    = Glu->xsup;
kusano 7d535a
    supno   = Glu->supno;
kusano 7d535a
    lsub    = Glu->lsub;
kusano 7d535a
    xlsub   = Glu->xlsub;
kusano 7d535a
    nzlmax  = Glu->nzlmax;
kusano 7d535a
kusano 7d535a
    nsuper = ++supno[jcol];	/* Next available supernode number */
kusano 7d535a
    nextl = xlsub[jcol];
kusano 7d535a
kusano 7d535a
    for (i = jcol; i <= kcol; i++) {
kusano 7d535a
	/* For each nonzero in A[*,i] */
kusano 7d535a
	for (k = xa_begin[i]; k < xa_end[i]; k++) {	
kusano 7d535a
	    krow = asub[k];
kusano 7d535a
	    kmark = marker[krow];
kusano 7d535a
	    if ( kmark != kcol ) { /* First time visit krow */
kusano 7d535a
		marker[krow] = kcol;
kusano 7d535a
		lsub[nextl++] = krow;
kusano 7d535a
		if ( nextl >= nzlmax ) {
kusano 7d535a
		    if ( mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu) )
kusano 7d535a
			return (mem_error);
kusano 7d535a
		    lsub = Glu->lsub;
kusano 7d535a
		}
kusano 7d535a
	    }
kusano 7d535a
    	}
kusano 7d535a
	supno[i] = nsuper;
kusano 7d535a
    }
kusano 7d535a
kusano 7d535a
    /* Supernode > 1, then make a copy of the subscripts for pruning */
kusano 7d535a
    if ( jcol < kcol ) {
kusano 7d535a
	new_next = nextl + (nextl - xlsub[jcol]);
kusano 7d535a
	while ( new_next > nzlmax ) {
kusano 7d535a
	    if ( mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu) )
kusano 7d535a
		return (mem_error);
kusano 7d535a
	    lsub = Glu->lsub;
kusano 7d535a
	}
kusano 7d535a
	ito = nextl;
kusano 7d535a
	for (ifrom = xlsub[jcol]; ifrom < nextl; )
kusano 7d535a
	    lsub[ito++] = lsub[ifrom++];	
kusano 7d535a
        for (i = jcol+1; i <= kcol; i++) xlsub[i] = nextl;
kusano 7d535a
	nextl = ito;
kusano 7d535a
    }
kusano 7d535a
kusano 7d535a
    xsup[nsuper+1] = kcol + 1;
kusano 7d535a
    supno[kcol+1]  = nsuper;
kusano 7d535a
    xprune[kcol]   = nextl;
kusano 7d535a
    xlsub[kcol+1]  = nextl;
kusano 7d535a
kusano 7d535a
    return 0;
kusano 7d535a
}
kusano 7d535a