_DESIGNING COMPLEX DATACENTRIC APPLICATIONS_
by Paul Bonneau


[LISTING ONE]

/**************************************************************************
 MARK.C -- determines the molecules in an array of atoms
***************************************************************************/
#define catmMax        6        /* Maximum number of neighbors. */
#define NULL           0

typedef struct atm
{
    struct atm *    patmParent;         /* Parent atom during walk. */
    struct atm *    patmRoot;           /* Root atom. */
    int             catm;               /* Number of of neighbors. */
    struct atm *    rgpatm[catmMax];    /* Neighbor list. */
} ATM;                                  /* AToM. */
/*  Prototypes */
void    Mark(ATM *, int);
ATM *   PatmNextChild(ATM * rgatm, ATM * patm);
void    Walk(ATM *, ATM *);

/***************************************************************************/
/* void Mark(ATM * rgatm, int catm)                                        */
/*    Mark each atom in the array with its parent molecule.                */
/*    Upon return, each atom will point to the root atom of the molecule   */
/*    containing it via the patmRoot field.                                */
/*        rgatm    : The array of atoms to mark.                           */
/*        catm    : The number of atoms in the array.                      */
/***************************************************************************/

void Mark(ATM * rgatm, int catm)
{   ATM *    patmLim  = rgatm + catm;    /* The limit of the array. */
    ATM *    patm;                       /* An array iterator. */

    /* First, make sure the mark fields are zeroed out. */
    for (patm = rgatm; patm < patmLim; patm++)
        patm->patmParent = patm->patmRoot = NULL;

    /* Now mark the atoms.  If an atom has already been marked, skip it. */
    /* If an atom has not been marked, then start a new molecule, and */
    /* grow a spanning tree and mark each atom in the tree with the new */
    /* molecule.  We conveniently use the first atom as the root to mark */
    /* all atoms in the tree with. */
    for (patm = rgatm; patm < patmLim; patm++)
        if (patm->patmRoot)
            Walk(rgatm, patm);
}
/**********************************************************************/
/* void Walk(ATM * rgatm, ATM * patm)                                 */
/*    Mark all atoms in this molecule with the root atom.             */
/*    Depth first non-recursive marking.                              */
/*    rgatm    : Array of all atoms.                                  */
/*    patm    : First atom in molecule.                               */
/**********************************************************************/
void Walk(ATM * rgatm, ATM * patm)
{   ATM *    patmRoot;

    patmRoot = patm->patmRoot = patm;    /* Remember root atom. */

    /* Mark the parent of the root atom with a special value, so we can */
    /* detect it is the root atom when encountered during the walk. */
    patm->patmParent = (ATM *)-1;

    for (;;)    /* Walk the tree. */
    {
        ATM *    patmNext;
        /* Given the current atom, get the next one to visit. */
        if (!(patmNext = PatmNextChild(rgatm, patm)))
        {
            /* No more kids, move back to parent.  If parent is */
            /* the root, stop. */
            if ((patm = patm->patmParent) == (ATM *)-1)
                break;                     /* We're done. */
        }
        else
        {
            patm = patmNext;               /* Move to "child". */
            patm->patmRoot = patmRoot;     /* Mark child.      */
        }
    }
}
/**********************************************************************/
/* ATM * PatmNextChild(ATM * rgatm, ATM * patm)                       */
/*    Return the next unvisited neighbor.                             */
/*    Return null if all neighbors have been visited.                 */
/*        rgatm    : Array of all atoms.                              */
/*        patm    : Atom to find an unvisited neighbor of.            */
/**********************************************************************/
ATM * PatmNextChild(ATM * rgatm, ATM * patm)
{   ATM **    ppatmLim;    /* Limit of atom's neighbor list. */
    ATM **    ppatm;        /* Neighbor list iterator. */

    /* Loop over all neighbors of this atom, looking for an unmarked one. */
    ppatmLim = patm->rgpatm + patm->catm;
    for (ppatm = patm->rgpatm; ppatm < ppatmLim; ppatm++)
        if (!(*ppatm)->patmParent)
        {
            (*ppatm)->patmParent = patm;
            return *ppatm;
         }
    return NULL;
}