vxcolor.c

vxworks官方下载的demo源代码

	    dB.nArray[i].att.color,
	    dB.nArray[i].att.Xvalue,
	    dB.nArray[i].stable,
	    dB.nArray[i].oD,
	    dB.nArray[i].rev,
	    dB.nArray[i].cNum);
	if (mode==2) /* full display */
	    {
	    for(j=0; j<dB.nArray[i].cNum; j++)
		printf(" * %2d%c %6d %d", dB.nArray[i].cArray[j].tnid.nid,
  		  dB.nArray[i].cArray[j].dir, dB.nArray[i].cArray[j].att.Xvalue,
		  dB.nArray[i].cArray[j].att.color);
	    }
	printf("\n");
        }
    }


/*******************************************************************************
*
* graphInit - coloring graph initialization
*
*/

void graphInit (void)
    {

    /* set initial node number to 0 */

    dB.nNum = 0;

    /*
     * enabling round robin: necessary to give each node of the
     * graph (which have all the same priority) some CPU access
     */

    kernelTimeSlice(2);

    /* spawn graphControl with low priority (199) to let tasks spawned from
     * the shell (100) able to run, but with higher priority than node's tasks
     * (200) to provides fast display 
     */

    graphControlId = taskSpawn ("tContrNet", 199, VX_SUPERVISOR_MODE,
	10000, (FUNCPTR) graphControl, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
    }


/*******************************************************************************
*
* graphControl - graph supervisor task
*
*/

void graphControl (void)
    {
    int		ix;	/* node index */

    /* sync binary semaphore to avoid nodes keep running */

    nodeSyncSem	= semBCreate (0, SEM_EMPTY);

    /* binary semaphore to provide graph mutex protection */

    graphSem	= semBCreate (0, SEM_FULL);

    FOREVER
	{

	/* access the dataBase critical resource */

	semTake (graphSem, -1);

	/* unblocks all the nodes in an atomic way */

	semFlush (nodeSyncSem);

	/* check stability */

	if (dB.nNum > 0)
	    {
	    ix=0;
	    while (ix<dB.nNum && dB.nArray[ix].stable == 1)
		ix++;
	    if (ix == dB.nNum) /* nodes are stable */
		{
		if (consistencyTest ()) /* dataBase is stable */
		    {
		    graphDisp (0);
		    semGive (graphSem);
    	            taskSuspend (0); /* suspend itself */
		    semTake (graphSem, -1);
		    }
		}
	    }

	/* hereunder delay should be enough for one step of coloring */

	taskDelay (STEP_TICKS);

	/* give back the dataBase access */

	semGive (graphSem);
	}
    }

/*******************************************************************************
*
* nodeCreate - node creation
*
*/

int nodeCreate
    (
    int nodeId
    )
    {

    char 	name[8];
    GNODE *	pNode;

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

    if ( nodeChecks (nodeId) != -1 )
	{
	printf("Node id %d already used in current graph.\n", nodeId);
	return -1;
	}

    /* check if the authorized maximum number of node is reached */

    if (dB.nNum == GRAPHMAXNODE-1)
	{
	printf("GRAPHMAXNODE reached!\n");
	return -1;
	}

    sprintf(name, "tNode%d", nodeId);
    pNode = &(dB.nArray[(unsigned int)dB.nNum]);
    dB.nNum++;

    /* spawn nodeJob with lower priority (200) than the default (100) */

    dB.nArray[dB.nNum-1].tnid.tid = 
	taskSpawn (name, 200, VX_SUPERVISOR_MODE, 10000, (FUNCPTR) nodeJob ,
		   nodeId, (int) pNode, 0, 0, 0, 0, 0, 0, 0, 0);
    return 0;
}



/*******************************************************************************
*
* nodeChecks - checks about a given node
*
* tests if a given node id is declared in the current database and if the
* connected node number (cNum) is under the limit
*
* RETURNS: -1 if bad node or bad cNum, rank in the database otherwise
*
*/

int nodeChecks
    (
    int 	nodeId /* node id */
    )
    {
    int		ix;	/* index */

    /* tests if the node exists */

    ix = 0;
    while (ix<dB.nNum && dB.nArray[ix].tnid.nid != nodeId)
	ix++;
    if (ix == dB.nNum)
	return -1;

    /* tests if the connected node number is under the limit */

    if (dB.nArray[ix].cNum == NODEMAXCONNEX)
	return -1;

    /* return the rank in the database */

    return ix;
    }

/*******************************************************************************
*
* connectionCreate - establish a connection between two nodes 
*
* the database is a critical resource that needs a mutex semaphore
*
*/

int connectionCreate
    (
    int nid1, 
    int nid2
    )
    {
    int		cNum1;
    int		cNum2;
    int		rank1;
    int		rank2;
    MSG_Q_ID	mqId;

    /* dataBase access request */

    semTake (graphSem, -1);

    /* check nodes id */

    if ( (rank1 = nodeChecks (nid1)) == -1 )
	{
	printf("No such node Id or NODEMAXCONNEX reached!\n");
	exit(2);
	}
    cNum1 = dB.nArray[rank1].cNum;
    if ( (rank2 = nodeChecks (nid2)) == -1 )
	{
	printf("No such node Id or NODEMAXCONNEX reached!\n");
	exit(2);
	}
    cNum2 = dB.nArray[rank2].cNum;

    dB.nArray[rank1].cArray[cNum1].tnid = dB.nArray[rank2].tnid;
    dB.nArray[rank1].cArray[cNum1].dir	= '0'; /* init with no direction */
    dB.nArray[rank1].cNum++;

    dB.nArray[rank2].cArray[cNum2].tnid = dB.nArray[rank1].tnid;
    dB.nArray[rank2].cArray[cNum2].dir	= '0'; /* init with no direction */
    dB.nArray[rank2].cNum++;

    /* create two Message Queues for node1 <-> node2 full duplex */

    if ( (mqId = msgQCreate(MAX_MSG, MSG_SIZE, MSG_Q_PRIORITY)) == NULL )
	return (ERROR);

    dB.nArray[rank1].cArray[cNum1].wMQId = mqId;
    dB.nArray[rank2].cArray[cNum2].rMQId = mqId;


    if ( (mqId = msgQCreate(MAX_MSG, MSG_SIZE, MSG_Q_PRIORITY)) == NULL )
	return (ERROR);

    dB.nArray[rank1].cArray[cNum1].rMQId = mqId;
    dB.nArray[rank2].cArray[cNum2].wMQId = mqId;

    /*printf("Link %d<->%d established.\n", nid1, nid2);*/

    /* free dataBase access */

    semGive (graphSem);

    /* resume the graphControl task (nop if graphControl already alive) */

    taskResume (graphControlId);
    return 0;
}

/*******************************************************************************
*
* nodeJob - task performed by each nodes in the graph
*
* More detailed description
*
*/

LOCAL void nodeJob 
    (
    int nodeId,		/* id of the node		*/
    GNODE * pNode	/* node processed by this task	*/
    )
    {

    /* node initialization		*/

    nodeInit(nodeId, pNode);

    /*printf("Node %d registered with random color=%d and random Xvlue = %d\n",
	    nodeId, pNode->att.color, pNode->att.Xvalue);*/

    FOREVER
	{

	/*
	 * each node block on the same semaphore (this avoid using here a
	 * taskDelay which leads, when used with many tasks, to sync problems)
	 */

	semTake (nodeSyncSem, -1);

	if (pNode->cNum > 0)
	    graphColoring (pNode);
	}
    }
    
/*******************************************************************************
*
* nodeInit - node initialization 
*
* More detailed description
*
*/

void nodeInit
    (
    int nodeId,		/* id of the node		*/
    GNODE * pNode	/* node processed by this task	*/
    )
    {

    /* random number generator init	*/
    srand (tickGet () + taskIdSelf ());

    /* node initialization		*/

    pNode->tnid.tid	= taskIdSelf ();
    pNode->tnid.nid	= nodeId;
    pNode->cNum 	= 0;
    pNode->rev 		= 0;
    pNode->pc 		= 0;
    pNode->stable 	= -1;
    pNode->oD 		= OUTDEGREEINIT;
    pNode->att.color	= rand()%6;
    pNode->att.Xvalue	= rand();

    }

/*******************************************************************************
*
* graphStop - collective Suicide
*
* kills task node's task, control task, mesgQs & semaphores
*
*/

void graphStop (void)
    {

    int	ix;	/* node index */
    int	jx;	/* connected node index */

    semDelete(graphSem);
    semDelete(nodeSyncSem);
    taskDelete(graphControlId);
    for(ix=0; ix< dB.nNum; ix++)
	taskDelete(dB.nArray[ix].tnid.tid);
    for(ix=0; ix< dB.nNum; ix++)
        {
	for(jx=0; jx< dB.nArray[ix].cNum; jx++)
	    {
	    msgQDelete(dB.nArray[ix].cArray[jx].rMQId);
	    msgQDelete(dB.nArray[ix].cArray[jx].wMQId);
	    }
        }
    printf("Graph coloring is finished.\n");
    }

/*******************************************************************************
*
* connectFullNode - performs full connections for a given node
*
*/

void connectFullNode
    (
    int nodId,		/* current node id */
    int nb_arg,		/* number of argument = connection # */
    ...			/* ellipse */
    )
    {
    int		ix;	/* index */
    va_list	p_list;	/* ellipse list */

    va_start(p_list, nb_arg);

    for (ix=0; ix<nb_arg; ix++)
	connectionCreate(nodId, va_arg(p_list, int));
    }

/*******************************************************************************
*
* entry point for colTest 
*
*/

void colTest 
    (
    int opCode
    )
    {
    int	ix;	/* index */

    if (opCode == 1)
	for(ix=1; ix<10; ix++)
	    nodeCreate(ix);

    if (opCode == 2) {
	connectFullNode(1, 7, 2, 4, 5, 6, 7, 8, 9);
	connectionCreate(2, 6);
	connectFullNode(3, 3, 4, 5, 8);
	connectFullNode(4, 2, 5, 8);
	connectionCreate(5, 8);
	connectFullNode(6, 2, 7, 8);
	connectFullNode(7, 2, 8, 9);
	connectionCreate(8, 9);
    }

    if (opCode == 3)
	for(ix=1; ix<10; ix++)
	    nodeCreate(ix);

    if (opCode == 4) {

	connectionCreate(1, 9);
	connectionCreate(9, 2);

	for(ix=2; ix<9; ix++) {
	    connectionCreate(1, ix);
	    connectionCreate(ix, ix+1);
	}
    }

    if (opCode == 5) { /* French counties */
	for(ix=1; ix<96; ix++)
	    nodeCreate(ix);
    }

    if (opCode == 6)
	{ 
        /* connections between counties of the french territory */
    
	connectFullNode(1, 6, 38, 39, 69, 71, 73, 74); /* Ain */
	connectFullNode(2, 6, 8, 51, 59, 60, 62, 77); /* Aisne */
	connectFullNode(3, 6, 18, 23, 42, 58, 63, 71); /* Allier */
	connectFullNode(4, 6, 5, 6, 13, 26, 83, 84); /* Alpes Haute Provence */
	connectFullNode(5, 4, 26, 38, 73, 84); /* Hautes Alpes */
	connectionCreate(6, 83); /* Alpes maritimes */
	connectFullNode(7, 5, 26, 30, 42, 43, 48); /* Ardeche */
	connectFullNode(8, 2, 51, 55); /* Ardennes */
	connectFullNode(9, 3, 11, 31, 66); /* Ariege */
	connectFullNode(10, 5, 21, 51, 52, 77, 89); /* Aube */
	connectFullNode(11, 4, 34, 66, 81, 82); /* Aude */
	connectFullNode(12, 7, 15, 30, 34, 46, 48, 81, 82); /* Aveyron */
	connectFullNode(13, 4, 20, 30, 83, 84); /* Bouches du Rhone */
	connectFullNode(14, 4, 27, 50, 61, 76); /* Calvados */
	connectFullNode(15, 5, 19, 43, 46, 48, 63); /* Cantal */
	connectFullNode(16, 6, 17, 24, 33, 79, 86, 87); /* Charente */
	connectFullNode(17, 3, 33, 79, 85); /* Charente maritime */
	connectFullNode(18, 5, 23, 36, 41, 45, 58); /* Cher */
	connectFullNode(19, 6, 23, 24, 46, 63, 87); /* Correze */
        /* Corse 20: no connection  */
	connectFullNode(21, 6, 39, 52, 58, 70, 71, 89); /* Cote d'or */
	connectFullNode(22, 3, 29, 35, 56); /* Cote d'armor */
	connectFullNode(23, 3, 36, 63, 87); /* Creuse */
	connectFullNode(24, 4, 33, 46, 47, 87); /* Dordogne */
	connectFullNode(25, 3, 39, 70, 90); /* Doubs */
	connectFullNode(26, 3, 30, 38, 84); /* Drome */
	connectFullNode(27, 7, 41, 45, 60, 61, 76, 78, 95); /* Eure */
	connectFullNode(28, 5, 41, 45, 61, 78, 91); /* Eure  et loir */
	connectionCreate(29, 56); /* Finistere */
	connectFullNode(30, 3, 34, 48, 84); /* Gard */
	connectFullNode(31, 4, 32, 65, 81, 82); /* Haute Garonne */
	connectFullNode(32, 5, 40, 47, 64, 65, 82); /* Gers */
	connectFullNode(33, 2, 40, 47); /* Gironde */
	connectionCreate(34, 81); /* Herault */
	connectFullNode(35, 4, 44, 50, 53, 56); /* Ile et vilaine */
	connectFullNode(36, 4, 37, 41, 86, 87); /* Indre */
	connectFullNode(37, 4, 41, 49, 72, 86); /* Indre et Loire */
	connectFullNode(38, 2, 69, 73); /* Isere */
	connectFullNode(39, 2, 70, 71); /* Jura */
	connectFullNode(40, 2, 47, 64); /* Landes */
	connectFullNode(41, 2, 45, 72); /* Loire et Cher */
	connectFullNode(42, 4, 43, 63, 69, 71); /* Loire */
	connectFullNode(43, 2, 48, 63); /* Haute Loire */
	connectFullNode(44, 3, 49, 56, 85); /* Loire Atlantique */
	connectFullNode(45, 4, 58, 77, 89, 91); /* Loiret */
	connectFullNode(46,  2, 47, 82); /* Lot */
	connectionCreate(47, 82); /* Lot et Garonne */
        /* Lozere 48 : no connection  */
	connectFullNode(49, 5, 53, 72, 79, 85, 86); /* Maine et Loire */
	connectionCreate(50, 53); /* Manche  */
	connectFullNode(51, 3, 52, 55, 77); /* Marne */
	connectFullNode(52, 3, 55, 70, 88); /* Haute Marne */
	connectFullNode(53, 2, 61, 72); /* Mayenne */
	connectFullNode(54, 4, 55, 57, 67, 88); /* Meurthe et Moselle */
	connectFullNode(55, 2, 57, 88); /* Meuse */
        /* Morbihan   56  */
	connectionCreate(57, 67); /* Moselle */
	connectionCreate(58, 71); /* Nievre */
	connectFullNode(59, 2, 62, 80); /* Nord */
	connectFullNode(60, 4, 76, 77, 80, 95); /* Oise */
	connectionCreate(61, 72); /* Orne */
	connectionCreate(62, 80); /* Pas de calais */
        /* Puy de Dome   63   */
	connectionCreate(64, 65); /* Pyrennees Atlantiques */
        /* Hautes Pyrennees  65 */
        /* Pyrennees Orientales 66 */
	connectFullNode(67, 2, 68, 88); /* Bas Rhin */
	connectFullNode(68, 2, 88, 90); /* Haut Rhin */
	connectionCreate(69, 71); /* Rhone */
	connectFullNode(70, 2, 88, 90); /* Haute Saone */
        /* Saone et Loire 71 */
        /* Sarthe 72*/
	connectionCreate(73, 74); /* Savoie */
        /* Haute Savoie 74 */
	connectFullNode(75, 3, 92, 93, 94); /* Paris */
	connectionCreate(76, 80); /* Seine Maritime */
	connectFullNode(77, 4, 89, 91, 93, 94); /* Seine et Marne */
	connectFullNode(78, 3, 91, 92, 95); /* Yvelines */
	connectFullNode(79, 2, 85, 86); /* Deux Sevres */
        /* Somme  80 */
	connectionCreate(81, 82); /* Tarn */
        /* Tarn  et garonne 82 */
        /* Var 83 */
        /* Vaucluse 84 */
        /* Vendee  85 */
	connectionCreate(86, 87); /* Vienne */
        /* Haute Vienne 87 */
        /* Vosges  88 */
        /* Yonne  89 */
        /* Territoire de Belfort  90 */
	connectFullNode(91, 2, 92, 94); /* Essonne */
	connectFullNode(92, 3, 93, 94, 95); /* Hauts de Seine */
	connectFullNode(93,  2, 94, 95); /* Seine St Denis */
        /* Val de Seine 94 */
        /* Val d'Oise 95 */
        }
    }