vxcolor.c

vxworks官方下载的demo源代码

/* vxColor.c -  Graph coloring program to demo some vxWorks capabilities */

/* Copyright 1995 Wind River Systems, Inc. */

/*
modification history
--------------------
01d,14jun95,rhp fixed some typos in names and comments
01c,xxapr95,jco took care of colin's notes:

		1- use of a binary semaphore to suspend processNodes instead of
		   using taskDelay.
		2- use of a mutex semaphore to suspend the activities while 
		   adding new connection(s) or when asking for the net state.
		3- rewrite according to WRS Coding Conventions
		4- mods of the nodeJob interface to hide the database 
		   implementation (as an array) behind a pointer.

01b,xxapr95,jco ported to vxWorks. 
01a,xxapr95,jco written.
*/

/*
DESCRIPTION
Perform the following steps to run the graph-coloring demo:

(1) Call graphInit() to start up the package.

(2) Create and stabilize the graphs for a preconfigured scenario, as
in one of the following examples:

For a simple unconnected collection of map nodes:
.CS
colTest(1);
colTest(2);
.CE   

For a collection of nodes forming a wheel:
.CS
colTest(3);
colTest(4);
.CE

For a collection of nodes with the connectivity of a map of France:
.CS
colTest(5);
colTest(6);
.CE

(3) To display the current map (the argument 2 means to produce a full
display):
.CS
graphDisp(2);
.CE

(4) To change the color of any node (where the <mode> argument
specifies whether to use the <color> argument or generate a random
color):
.CS
colorChange(<nodeId>, <mode>, <color>);
.CE

If <mode> is 1, the new color is random; if <mode> is 2, the color is changed
to the value specified with the <color> argument.

(5) To extend the map, you can both create new nodes with
nodeCreate(), and make new connections between existing nodes with
connectionCreate():

.CS
nodeCreate(<nodeId>);
connectionCreate(<nodeId1>, <nodeId2>);
.CE

(6) To kill everything and end the demo:
.CS
graphStop();
.CE

INTERNAL
The following is the thread of execution of this test program.

The ":" trace stands for a given net (a set of node creation and connection 
creation). The "|" trace stands for modification of that net. New nodes
can be appended to the net, but only new connections or color changes
trigger the task resumes. The "#" tag stands for end of task.

       Stability   Node       Connection   Graph     Color    Graph       Graph
Node   Detection   Creation   Creation    Display   Change   Init        Stop
Task   Task	   Task	      Task	  Task	    Task     Task        Task
====   =========   ========   =========   =======   ======   =====       =====
                      :          :   |                |         |          |
                      :          :   |                |         |          |
                      :          :   |                |   spawn stability  |
                      :          :   |                |       /            |
                      :          :   |                |      /             |
           <------------------------------------------------/              |
           |          :          :   |                |         |          |
           |      spawn node     :   |                |         #          |
           |          /          :   |                |                    |
           |         /           :   |                |                    |
  <--------|--------/            :   |                |                    |
           |         #           :   |                |                    |
           |                     #   |                |                    |
      [stability]                    |                |                    |
           \                         |                |                    |
            \                        |                |                    |
             \ ----------------------------->         |                    |
   taskSuspend Node Tasks            |      |         |                    |
          /                          |      #         |                    |
         /                           |                |                    |
  <-----/                            |                |                    |
    taskSuspend itself               |                |                    |
                                     |                |                    |
                                     |                |                    |
                            taskResume Node Tasks     |                    |
                                     /                |                    |
                                    /                 |                    |
  <--------------------------------/          taskResume Node Tasks        |
  |                         taskResume Stability      #                    |
  |                                  /                                     |
  |                                 /                                      |
  |        <-----------------------/                                       |
  |        |                        |                                      |
  |        |                        #                                      |
  |        |                                                               |
  |        |                                       taskdelete Node + stability
  |        |                                                               /
  |        |                                                              /
  <--------<-------------------------------------------------------------/
  #        #                                                               |
                                                                           #


INCLUDE FILES:
*/

/* includes */

#include "vxWorks.h"
#include "taskLib.h"
#include "msgQLib.h"
#include "stdarg.h"
#include "stdio.h"
#include "tickLib.h"
#include "kernelLib.h"

/* defines */

#define		GRAPHMAXNODE	100	/* graph max node number */
#define		NODEMAXCONNEX	10	/* node max connection number */
#define		MAX_MSG		50	/* max messg number in queue */
#define		MSG_SIZE	sizeof (NODE_ATTRIB) /* size of message */
#define		COLORMAX	6	/* maximum number of color */
#define		OUTDEGREEMAX	5	/* node max out degree */
#define		OUTDEGREEINIT	(OUTDEGREEMAX + 1)
#define		STEP_TICKS	6	/* inter node processing  ticks count */

/* typedefs */

typedef struct /* IDS */
    {
    int		tid;			/* task id */
    char	nid;			/* node id */
    } IDS;				/* task/node id	*/

typedef struct /* NODE_ATTRIB */
    {
    char	color;			/* node color */
    int		Xvalue;			/* node Xvalue */
    } NODE_ATTRIB;			/* node attributes */

typedef struct /* CONNECT_INFO */
    {
    char	dir;	/* direction: +=to connected -=from connected */
    IDS		tnid;			/* connected node tid & nid */
    NODE_ATTRIB	att;			/* connected node attributes */
    MSG_Q_ID	wMQId;		/* write (toNeighbor) mesg queue id */
    MSG_Q_ID	rMQId;		/* read  (toNeighbor) mesg queue id */
    } CONNECT_INFO;			/* connected node info */

typedef struct /* GNODE */
    {
    char	stable;			/* color stability flag	*/
    char	rev;			/* DAG reversing flag */
    IDS		tnid;			/* node tid & nid */
    NODE_ATTRIB	att;			/* node col & Xval */
    int		pc;			/* node Prog Counter */
    int		oD;			/* node outDegree */
    int		cNum;			/* node connections # */
    CONNECT_INFO cArray[NODEMAXCONNEX];	/* node connections array */
    } GNODE;				/* global node info */

typedef struct /* DATA_BASE */
    {
    char	nNum;			/* graph node #	*/
    GNODE	nArray[GRAPHMAXNODE];	/* graph node array */
    } DATA_BASE;			/* global graph info */	

/* globals */

DATA_BASE	dB;			/* global data base of nodes */
int		graphControlId;		/* graphControl task Id */
SEM_ID		nodeSyncSem;		/* node sync semaphore */
SEM_ID		graphSem;		/* graph mutex semaphore */

/* locals */


/* forward declarations */

int 		nodeChecks (int nodeId);
int 		nodeCreate (int nodeId);
void 		nodeInit (int nodeId, GNODE * pNode);
LOCAL void	nodeJob(int nodeId, GNODE * pNode);
int 		graphColoring (GNODE * pNode);
void 		graphControl (void);
void 		graphDisp (int mode);
void		graphInit (void);
void 		graphStop (void);
int 		colorChange (int nodeId, int mode, int newColor);
void 		colTest	(int opCode);
int 		connectionCreate (int nid1, int nid2);
BOOL 		consistencyTest	(void);

/*******************************************************************************
*
* neighborTalk - talking with the pc ranked neihgbor
*
* Note about the inter nodes communication phase:
* Trial: read a neighbor at a time for the color only
* actually, all processNodes write their color to all their neighbors
* and each process node read all its links to empty them
* (avoiding pipes to get full), but only one value is used.
*
*/

void neighborTalk 
    (
    GNODE * pNode	/* current node */
    )
    {
    NODE_ATTRIB	att;		/* attributes */
    int		ix;		/* connected node index */
    int		retVal;		/* msgQ operation result */

    att = pNode->att;

    /* writing connected nodes */

    for (ix=0; ix< pNode->cNum; ix++)
	retVal = msgQSend (pNode->cArray[ix].wMQId, (char *) &att, MSG_SIZE,
			   WAIT_FOREVER, MSG_PRI_NORMAL);

    /* reading connected nodes, especially rank=pc one */

    for (ix=0; ix< pNode->cNum; ix++)
	{
	retVal = msgQReceive (pNode->cArray[ix].rMQId, (char *) &att,
			      MSG_SIZE, NO_WAIT);
	if (ix == pNode->pc)
	    pNode->cArray[ix].att =  att;
	}
    }

/*******************************************************************************
*
* graphColoring - DAG & Coloring processing
*
*
*/

int graphColoring 
    (
    GNODE * pNode	/* current node */
    )
    {
    int		ix;		/* index */
    int		outDegree;	/* outdegree of this node */
    int		colConf;	/* if color conflict */
    int		col[COLORMAX];	/* color check array */
    long	XvalueMax;	/* max Xvalue of node */
#if 0
    /* not used */
    NODE_ATTRIB	att;		/* attributes */
#endif

    if (pNode->pc < pNode->cNum) /* connected neighbors scaning uncompleted */
        {

	/* talking with pc ranked neighbor */

	neighborTalk (pNode);


	/* program counter incrementation */

	pNode->pc++;
        }
    else /* connected neighbors scaning completed */
        {

	/* DAG conversion: computes links directions and outDegree */

	XvalueMax = 0;
        outDegree = 0;
    	for (ix=0; ix < pNode->cNum; ix++)
	    {
	    if ( (pNode->att.Xvalue < pNode->cArray[ix].att.Xvalue ) || 
		 ( (pNode->att.Xvalue == pNode->cArray[ix].att.Xvalue) &&
		   (pNode->tnid.nid < pNode->cArray[ix].tnid.nid) ) )
		{

		pNode->cArray[ix].dir = '+';
		outDegree++;
		if (pNode->cArray[ix].att.Xvalue > XvalueMax)
		    XvalueMax = pNode->cArray[ix].att.Xvalue;
	        }
	    else
		{
		pNode->cArray[ix].dir = '-';
	        }
	    }
	pNode->oD = outDegree;

        if (outDegree > OUTDEGREEMAX)
	    {

	    /* DAG conversion: reversing current node */

	    printf("reversing %d: Xvalue from %d to Xvalue = %ld.\n",
		   pNode->tnid.nid, pNode->att.Xvalue, XvalueMax + 1);
            pNode->att.Xvalue = XvalueMax + 1;
	    pNode->rev++;
            }
	else /* outDegree <= OUTDEGREEMAX : this enables coloring algo */
	    {	

	    /* COL : detecting color conflict and 'n' tagging used color */

            colConf = 0;
    	    for (ix=0; ix<6; ix++)
		col[ix] = 'y';

    	    for (ix=0; ix < pNode->cNum; ix++)
		{
	        if (pNode->cArray[ix].dir == '+')
		    {
	            if (pNode->att.color == pNode->cArray[ix].att.color)
			colConf = 1;
	            col[(unsigned int)(pNode->cArray[ix].att.color)] = 'n';
	            }
	        }

	    /* COL: update color in case of coloring conflict */

	    if ( colConf == 1 )
		{
		ix=0; /* looks for the first free color	*/

		while( ix<6 && col[ix]=='n')
		    ix++;
		if (ix==6)
		    {
		    printf("End of node %d: col error.\n", pNode->tnid.nid);
		    exit(2);
		    }
		else
		    {
		    printf("Node %d: color update %d --> %d\n",
			pNode->tnid.nid, pNode->att.color, ix);
		    pNode->att.color = ix;
		    }
		pNode->stable = 0;
	        }
	    else
		{
		pNode->stable = 1;
	        }
	    }

   	/* reset program counter		*/

	pNode->pc 	= 0;
        }
    return 0;
    }

/*******************************************************************************
*
* consistencyTest - tests whether arcs are well oriented throughout the graph
*
* RETURNS: TRUE if graph is consistent, FALSE otherwise
*/

BOOL consistencyTest (void)
    {
    int		i;	/* node index */
    int		j;	/* connected node index */
    int		k;	/* node index */
    int		l;	/* connected node index */
    char	dir1;	/* link direction */
    char	dir2;	/* link direction */

    for(i=0; i<dB.nNum; i++)
	{
	for(j=0; j<dB.nArray[i].cNum; j++)
	    {
	    if (dB.nArray[i].att.color == dB.nArray[i].cArray[j].att.color)
		{
		printf("(i,j)=(%d,%d) direct color conflict.\n", i, j);
		return FALSE;
    	        }
    	    if ( (k = nodeChecks (dB.nArray[i].cArray[j].tnid.nid)) == -1 )
		{
		printf("Bad link definition.\n");
		return FALSE;
		}
	    /* is that node at rank k has correct connected info */
    	    l = 0;
    	    while ( l<dB.nArray[k].cNum && 
		    dB.nArray[k].cArray[l].tnid.nid != dB.nArray[i].tnid.nid )
		l++;
    	    if (l == dB.nNum)
		{
		printf("Symetric link violation.\n");
		return FALSE;
    	        }
	    /* is that node at rank k has correct color */
	    if ( dB.nArray[i].cArray[j].att.color != dB.nArray[k].att.color )
		{
		printf("(i,j,k)=(%d,%d,%d) connection color inconsistency.\n", i, j, k);
		return FALSE;
    	        }

	    dir1 = dB.nArray[i].cArray[j].dir;
	    dir2 = dB.nArray[k].cArray[l].dir;

	    if ( (dir1 != '+' && dir1 != '-') || (dir2 != '+' && dir2 != '-')
		 || (dir1==dir2) )
		{
		printf("Asymetric direction inconsistency.\n");
		return FALSE;
	        }
	    }
        }
    return TRUE;
    }

/*******************************************************************************
*
* colorChange - randomly change a node color
*
* note: database is a critical resource that needs a mutex semaphore
*/

int colorChange
    (
    int nodeId,		/* node id */
    int mode,		/* colorChange mode: 1 = random, 2 = specified color */
    int newColor	/* specified color of the colorChange mode # 2 */
    )
    {
    int		rank;	/* node rank in the database */
    char	color;	/* temporary color */

    /* checks if that node id is already in use in the graph */

    if ( (rank = nodeChecks (nodeId)) == -1 )
	{
	printf("No such node id %d in current graph.\n", nodeId);
	return -1;
	}

    switch (mode)
	{
	case 1: /* randomly picks out a color among 6 values */
    	    srand (tickGet ());
    	    color = dB.nArray[rank].att.color;
    	    while ( color == dB.nArray[rank].att.color)
	        color = rand()%6;
	    break;

	case 2:
	    color = newColor;
	    break;

	default: 
	    printf("Unknown colorChange mode.\n");
	    exit(0);
	}

    printf("Node %d: color change %d --> %d.\n", nodeId,
	   dB.nArray[rank].att.color, color);

    /* access the dataBase critical resource */

    semTake (graphSem, -1);

    dB.nArray[rank].att.color = color;
    dB.nArray[rank].stable	   = 0;

    /* give back the dataBase critical resource */

    semGive (graphSem);

    /* resume the graphControl task */

    taskResume (graphControlId);
    return 0;
}

/*******************************************************************************
*
*  graphDisp - display current graph state
*
* note: database access should be frozzen during the display
*
*/

void graphDisp
    (
    int mode	/* display mode 2 = full !2 = regular */
    )
    {

    int	i, j;

    printf("******\n* dataBase graph info:\n*\n");
    printf("nid color Xvalue sb oD Rev cNum connected nodes\n");
    for(i=0; i<dB.nNum; i++)
	{
	printf("%3d %5d %6d %2d %2d %3d %4d", 
	    dB.nArray[i].tnid.nid,