/*
 * Push 'task' onto the ready_tasks queue.  If 'task' has the privilege
 * flag set, then also push it onto the ready_priority_tasks queue.
 *
 * Caller must hold the task manager lock.
 */
static inline void
push_readyq(isc__taskmgr_t *manager, isc__task_t *task) {
	ENQUEUE(manager->ready_tasks, task, ready_link);
	if ((task->flags & TASK_F_PRIVILEGED) != 0)
		ENQUEUE(manager->ready_priority_tasks, task,
			ready_priority_link);
}

void dijkstra(struct Graph *G, int s) {
    struct Queue* Q;
    Q = (struct Queue*)malloc(sizeof(struct Queue));
    Q->length = MAX_SIZE - 1;
    Q->head = Q->tail = 0;

    int i, j;
    G->costArray[s] = 0;

    ENQUEUE(Q, s);

    while(Q->head!=Q->tail) {      
        j = DEQUEUE(Q);
        G->colorArray[j] = BLACK;
        for (i=1; i<=G->V; i++) {
            if (G->adjMatrix[i][j]==0) {continue;} // Not j's neighbors
            else {
           //     if (G->colorArray[i]!=BLACK) { // Not j's parent
                    if (G->costArray[i]==INFINITE) { // New node
                        G->costArray[i] = G->costArray[j] + G->adjMatrix[i][j];
                        G->parentArray[i] = j;
                    }
                    else if (G->costArray[i] > G->costArray[j] + G->adjMatrix[i][j]) { // Updated node
                        G->costArray[i] = G->costArray[j] + G->adjMatrix[i][j];
                        G->parentArray[i] = j;
                    }
                    ENQUEUE(Q, i);
             //   }
            }
        }
    }
}

/* Perform menu command COMMAND.  */
Boolean
AppMenuDoCommand (UInt16 command)
{
    Boolean handled = false;
    FormDesc *fd;

    /* See if menu command is a form switch.  */
    for (fd = g_formList; fd; fd = fd->next) {
        if (fd->menuCommandID == command) {
            SwitchToForm (fd->formID);
            return true;
        }
    }

    /* Handle the rest of the items.  */
    switch (command) {
	case CommonOptionsPreferences:
	    PrefShowSetupForm();
	    return true;
	    
	case CommonOptionsAbout:
	    AboutShow();
	    return true;

#if 0
	case CommonOptionsSwitchclass:
	    SPREF (bluetoothClass) = (SPREF (bluetoothClass) + 1) % 5;
	    SPREF (bluetoothSDP) = (SPREF (bluetoothSDP) + 1) % 5;
	    return true;
#endif

	case CommonConnectionAddDevice:
	    BTSelectDevice();
	    return true;

	case CommonConnectionConnect:
	    ENQUEUE (CmdInitiateConnect);
	    return true;

	case CommonConnectionDisconnect:
	    ENQUEUE (CmdInitiateDisconnect);
	    return true;

	default:
	    break;
    }

    return handled;
}

void Topologicalsort( AdjGraph G, int aov[NumVertices] )
{  
	int v, w, nodes;
	EdgeNode *tmp;
	EdgeData indegree[NumVertices+1]={0};

	QUEUE Q ;
	MAKENULL( Q ) ;

	// 计算每个顶点的入度
	for( v=1; v<=G.n ; ++v )
	{
		tmp=G.vexlist[v].firstedge;
		while(tmp)
		{
			indegree[tmp->adjvex]++;
			tmp=tmp->next;
		}	
	}
	// 将入度为0的顶点加入队列
	for(v=1; v<=G.n; ++v)
		if ( indegree[v] ==0 ) 
			ENQUEUE( v, Q ) ;
	
	nodes = 0 ;
	while ( !EMPTY( Q ) )
	{  
		v = FRONT(Q)->element ;
		DEQUEUE( Q ) ;
		//cout << v <<' '; 
		aov[nodes]=v;
		nodes ++ ;		// 已考虑的节点个数加1
		// 如果(v, w)是一条边，将w的入度减1，如果w的入度为0，则将w入队
		for( w=1; w<=G.n; w++) 
		{
			if(connect(G, v, w))
			{
				--indegree[w];
				if( !(indegree[w])) 
					ENQUEUE(w,Q) ;
			}
		}
	}
	cout<<endl;
	if ( nodes < G.n ) 
		cout<<"图中有环路"<<endl;
	
}

ISC_TASKFUNC_SCOPE void
isc__task_setprivilege(isc_task_t *task0, isc_boolean_t priv) {
	isc__task_t *task = (isc__task_t *)task0;
	isc__taskmgr_t *manager = task->manager;
	isc_boolean_t oldpriv;

	LOCK(&task->lock);
	oldpriv = ISC_TF((task->flags & TASK_F_PRIVILEGED) != 0);
	if (priv)
		task->flags |= TASK_F_PRIVILEGED;
	else
		task->flags &= ~TASK_F_PRIVILEGED;
	UNLOCK(&task->lock);

	if (priv == oldpriv)
		return;

	LOCK(&manager->lock);
	if (priv && ISC_LINK_LINKED(task, ready_link))
		ENQUEUE(manager->ready_priority_tasks, task,
			ready_priority_link);
	else if (!priv && ISC_LINK_LINKED(task, ready_priority_link))
		DEQUEUE(manager->ready_priority_tasks, task,
			ready_priority_link);
	UNLOCK(&manager->lock);
}

/*
Normal event handler.

Take first character off queue and send to clock if not a null.

Shift characters down and put a null on the end.

We assume that there is no parallelism so no race condition, but even
if there is nothing bad will happen except that we might send some bad
data to the clock once in a while.
*/
static void
arc_event_handler(
	struct peer *peer
	)
{
	struct refclockproc *pp = peer->procptr;
	register struct arcunit *up = (struct arcunit *)pp->unitptr;
	int i;
	char c;
#ifdef DEBUG
	if(debug > 2) { printf("arc: arc_event_handler() called.\n"); }
#endif

	c = up->cmdqueue[0];       /* Next char to be sent. */
	/* Shift down characters, shifting trailing \0 in at end. */
	for(i = 0; i < CMDQUEUELEN; ++i)
	{ up->cmdqueue[i] = up->cmdqueue[i+1]; }

	/* Don't send '\0' characters. */
	if(c != '\0') {
		if(write(pp->io.fd, &c, 1) != 1) {
			msyslog(LOG_NOTICE, "ARCRON: write to fd %d failed", pp->io.fd);
		}
#ifdef DEBUG
		else if(debug) { printf("arc: sent `%2.2x', fd %d.\n", c, pp->io.fd); }
#endif
	}

	ENQUEUE(up);
}

static fsm_rt_t console_print(const uint8_t *pchBuf,uint8_t chNum)
{
    static uint8_t s_chPrintIndex ;
    static enum {
        CONSOLE_PRT_START = 0,
        CONSOLE_PRT_PRINT
    }s_tState = CONSOLE_PRT_START;
    
    if((NULL == pchBuf) || (!chNum)) {
        return fsm_rt_err;
    }
    
    switch(s_tState) {
        case CONSOLE_PRT_START:
            s_chPrintIndex = 0;
            s_tState = CONSOLE_PRT_PRINT;
            //break;
            
        case CONSOLE_PRT_PRINT:
            if(s_chPrintIndex < chNum) {
                if(ENQUEUE(InOutQueue,&g_tFIFOout,pchBuf[s_chPrintIndex])) {
                    s_chPrintIndex++;
                }
            } else {
                CONSOLE_PRT_RESET();
                return fsm_rt_cpl;
            }
            break;
    }
    
    return fsm_rt_on_going;
}

static inline isc_boolean_t
task_send(isc_task_t *task, isc_event_t **eventp) {
	isc_boolean_t was_idle = ISC_FALSE;
	isc_event_t *event;

	/*
	 * Caller must be holding the task lock.
	 */

	REQUIRE(eventp != NULL);
	event = *eventp;
	REQUIRE(event != NULL);
	REQUIRE(event->ev_type > 0);
	REQUIRE(task->state != task_state_done);

	XTRACE("task_send");

	if (task->state == task_state_idle) {
		was_idle = ISC_TRUE;
		INSIST(EMPTY(task->events));
		task->state = task_state_ready;
	}
	INSIST(task->state == task_state_ready ||
	       task->state == task_state_running);
	ENQUEUE(task->events, event, ev_link);
	*eventp = NULL;

	return (was_idle);
}

void TradeRouteData::SetRecip(TradeRoute route)
{

	Assert(FALSE);

	m_recip = route;
	ENQUEUE();
}

int TTY_WriteByte(int handle, byte data)
{
	ComPort	*p;

	p = handleToPort [handle];
	if (FULL(p->outputQueue))
		return -1;

	ENQUEUE (p->outputQueue, data);
	return 0;
}

static int Modem_Command(ComPort *p, char *commandString)
{
	byte	b;

	if (CheckStatus (p))
		return -1;

	disable();
	p->outputQueue.head = p->outputQueue.tail = 0;
	p->inputQueue.head = p->inputQueue.tail = 0;
	enable();
	p->bufferUsed = 0;

	while (*commandString)
		ENQUEUE (p->outputQueue, *commandString++);
	ENQUEUE (p->outputQueue, '\r');

	// get the transmit rolling
	DEQUEUE (p->outputQueue, b);
	outportb(p->uart, b);

	return 0;
}

CARD32
processautorepeat(OsTimerPtr timer, CARD32 now, pointer arg)
{
    xEvent kevent;
    int    keycode;

    keycode = (long)arg;

    xf86Info.lastEventTime =
	kevent.u.keyButtonPointer.time =
	    GetTimeInMillis();

    /*
     * Repeat a key by faking a KeyRelease, and a KeyPress event in rapid
     * succession
     */

    ENQUEUE(&kevent, keycode,  KeyRelease, XE_KEYBOARD);
    ENQUEUE(&kevent, keycode,  KeyPress, XE_KEYBOARD);

    /* And return the appropriate value so we get rescheduled */
    return xf86Info.kbdRate;
}

//----------------------------------------------------------------------------
//
// Name       : CivilisationData::CivilisationData
//
// Description: Constructor
//
// Parameters : id      : unique civilisation id
//              owner   : player index
//              civ     : civilisation index
//              gender  : leader gender
//
// Globals    : -
//
// Returns    : -
//
// Remark(s)  : Notifies other (network) players of its existence.
//
//----------------------------------------------------------------------------
CivilisationData::CivilisationData(const ID &id, PLAYER_INDEX owner, sint32 civ, GENDER gender)
:	GameObj(id.m_id),
	m_owner(owner),
	m_civ(civ),
	m_gender(gender),
	m_cityStyle(CITY_STYLE_GENERIC)
{
	memset(m_cityname_count, 0, sizeof(m_cityname_count));
	memset(m_leader_name, 0, k_MAX_NAME_LEN);
	memset(m_personality_description, 0, k_MAX_NAME_LEN);
	memset(m_civilisation_name, 0, k_MAX_NAME_LEN);
	memset(m_country_name, 0, k_MAX_NAME_LEN);
	memset(m_singular_name, 0, k_MAX_NAME_LEN);

	ENQUEUE();
}

static void ISR_8250 (ComPort *p)
{
	byte	source = 0;
	byte	b;

	disable();

	while((source = inportb (p->uart + INTERRUPT_ID_REGISTER) & 0x07) != 1)
	{
		switch (source)
		{
			case IIR_RX_DATA_READY_INTERRUPT:
				b = inportb (p->uart + RECEIVE_BUFFER_REGISTER);
				if (! FULL(p->inputQueue))
				{
					ENQUEUE (p->inputQueue, b);
				}
				else
				{
					p->lineStatus |= LSR_OVERRUN_ERROR;
					p->statusUpdated = true;
				}
				break;

			case IIR_TX_HOLDING_REGISTER_INTERRUPT:
				if (! EMPTY(p->outputQueue))
				{
					DEQUEUE (p->outputQueue, b);
					outportb (p->uart + TRANSMIT_HOLDING_REGISTER, b);
				}
				break;

			case IIR_MODEM_STATUS_INTERRUPT:
				p->modemStatus = (inportb (p->uart + MODEM_STATUS_REGISTER) & MODEM_STATUS_MASK) | p->modemStatusIgnore;
				p->statusUpdated = true;
				break;

			case IIR_LINE_STATUS_INTERRUPT:
				p->lineStatus = inportb (p->uart + LINE_STATUS_REGISTER);
				p->statusUpdated = true;
				break;
		}
		source = inportb (p->uart + INTERRUPT_ID_REGISTER) & 0x07;
	}
	outportb (0x20, 0x20);
}

static inline void
task_ready(isc_task_t *task) {
	isc_taskmgr_t *manager = task->manager;

	REQUIRE(VALID_MANAGER(manager));
	REQUIRE(task->state == task_state_ready);

	XTRACE("task_ready");

	LOCK(&manager->lock);

	ENQUEUE(manager->ready_tasks, task, ready_link);
#ifdef ISC_PLATFORM_USETHREADS
	SIGNAL(&manager->work_available);
#endif /* ISC_PLATFORM_USETHREADS */

	UNLOCK(&manager->lock);
}

ISC_TASKFUNC_SCOPE isc_result_t
isc__task_onshutdown(isc_task_t *task0, isc_taskaction_t action,
		     const void *arg)
{
	isc__task_t *task = (isc__task_t *)task0;
	isc_boolean_t disallowed = ISC_FALSE;
	isc_result_t result = ISC_R_SUCCESS;
	isc_event_t *event;

	/*
	 * Send a shutdown event with action 'action' and argument 'arg' when
	 * 'task' is shutdown.
	 */

	REQUIRE(VALID_TASK(task));
	REQUIRE(action != NULL);

	event = isc_event_allocate(task->manager->mctx,
				   NULL,
				   ISC_TASKEVENT_SHUTDOWN,
				   action,
				   arg,
				   sizeof(*event));
	if (event == NULL)
		return (ISC_R_NOMEMORY);

	LOCK(&task->lock);
	if (TASK_SHUTTINGDOWN(task)) {
		disallowed = ISC_TRUE;
		result = ISC_R_SHUTTINGDOWN;
	} else
		ENQUEUE(task->on_shutdown, event, ev_link);
	UNLOCK(&task->lock);

	if (disallowed)
		isc_mem_put(task->manager->mctx, event, sizeof(*event));

	return (result);
}

static unsigned int
dequeue_events(isc_task_t *task, void *sender, isc_eventtype_t first,
	       isc_eventtype_t last, void *tag,
	       isc_eventlist_t *events, isc_boolean_t purging)
{
	isc_event_t *event, *next_event;
	unsigned int count = 0;

	REQUIRE(VALID_TASK(task));
	REQUIRE(last >= first);

	XTRACE("dequeue_events");

	/*
	 * Events matching 'sender', whose type is >= first and <= last, and
	 * whose tag is 'tag' will be dequeued.  If 'purging', matching events
	 * which are marked as unpurgable will not be dequeued.
	 *
	 * sender == NULL means "any sender", and tag == NULL means "any tag".
	 */

	LOCK(&task->lock);

	for (event = HEAD(task->events); event != NULL; event = next_event) {
		next_event = NEXT(event, ev_link);
		if (event->ev_type >= first && event->ev_type <= last &&
		    (sender == NULL || event->ev_sender == sender) &&
		    (tag == NULL || event->ev_tag == tag) &&
		    (!purging || PURGE_OK(event))) {
			DEQUEUE(task->events, event, ev_link);
			ENQUEUE(*events, event, ev_link);
			count++;
		}
	}

	UNLOCK(&task->lock);

	return (count);
}

static inline isc_boolean_t
task_shutdown(isc__task_t *task) {
	isc_boolean_t was_idle = ISC_FALSE;
	isc_event_t *event, *prev;

	/*
	 * Caller must be holding the task's lock.
	 */

	XTRACE("task_shutdown");

	if (! TASK_SHUTTINGDOWN(task)) {
		XTRACE(isc_msgcat_get(isc_msgcat, ISC_MSGSET_GENERAL,
				      ISC_MSG_SHUTTINGDOWN, "shutting down"));
		task->flags |= TASK_F_SHUTTINGDOWN;
		if (task->state == task_state_idle) {
			INSIST(EMPTY(task->events));
			task->state = task_state_ready;
			was_idle = ISC_TRUE;
		}
		INSIST(task->state == task_state_ready ||
		       task->state == task_state_running);

		/*
		 * Note that we post shutdown events LIFO.
		 */
		for (event = TAIL(task->on_shutdown);
		     event != NULL;
		     event = prev) {
			prev = PREV(event, ev_link);
			DEQUEUE(task->on_shutdown, event, ev_link);
			ENQUEUE(task->events, event, ev_link);
		}
	}

	return (was_idle);
}

/*
 * Supply Strategy 1 Large Buffers to CP
 *
 * May be called in interrupt state.
 * Must be called with interrupts locked out.
 *
 * Arguments:
 *	fup		pointer to device unit structure
 *
 * Returns:
 *	none
 */
static void
fore_buf_supply_1l(Fore_unit *fup)
{
	H_buf_queue	*hbp;
	Buf_queue	*cqp;
	Buf_descr	*bdp;
	Buf_handle	*bhp;
	KBuffer		*m;
	int		nvcc, nbuf, i;

	/*
	 * Figure out how many buffers we should be giving to the CP.
	 * We're basing this calculation on the current number of open
	 * VCCs thru this device, with certain minimum and maximum values
	 * enforced.  This will then allow us to figure out how many more 
	 * buffers we need to supply to the CP.  This will be rounded up 
	 * to fill a supply queue entry.
	 */
	nvcc = MAX(fup->fu_open_vcc, BUF_MIN_VCC);
	nbuf = nvcc * 4 * RECV_MAX_SEGS;
	nbuf = MIN(nbuf, BUF1_LG_CPPOOL);
	nbuf -= fup->fu_buf1l_cnt;
	nbuf = roundup(nbuf, BUF1_LG_ENTSIZE);

	/*
	 * OK, now supply the buffers to the CP
	 */
	while (nbuf > 0) {

		/*
		 * Acquire a supply queue entry
		 */
		hbp = fup->fu_buf1l_tail;
		if (!((*hbp->hbq_status) & QSTAT_FREE))
			break;
		bdp = hbp->hbq_descr;

		/*
		 * Get a buffer for each descriptor in the queue entry
		 */
		for (i = 0; i < BUF1_LG_ENTSIZE; i++, bdp++) {
			caddr_t		cp;

			/*
			 * Get a cluster buffer
			 */
			KB_ALLOCEXT(m, BUF1_LG_SIZE, KB_F_NOWAIT, KB_T_DATA);
			if (m == NULL) {
				break;
			}
			KB_HEADSET(m, BUF1_LG_DOFF);

			/*
			 * Point to buffer handle structure
			 */
			bhp = (Buf_handle *)((caddr_t)m + BUF1_LG_HOFF);
			bhp->bh_type = BHT_S1_LARGE;

			/*
			 * Setup buffer descriptor
			 */
			bdp->bsd_handle = bhp;
			KB_DATASTART(m, cp, caddr_t);
			bhp->bh_dma = bdp->bsd_buffer = (H_dma) DMA_GET_ADDR(
				cp, BUF1_LG_SIZE, BUF_DATA_ALIGN, 0);
			if (bdp->bsd_buffer == 0) {
				/*
				 * Unable to assign dma address - free up
				 * this descriptor's buffer
				 */
				fup->fu_stats->st_drv.drv_bf_segdma++;
				KB_FREEALL(m);
				break;
			}

			/*
			 * All set, so queue buffer (handle)
			 */
			ENQUEUE(bhp, Buf_handle, bh_qelem, fup->fu_buf1l_bq);
		}

		/*
		 * If we we're not able to fill all the descriptors for
		 * an entry, free up what's been partially built
		 */
		if (i != BUF1_LG_ENTSIZE) {
			caddr_t		cp;

//.........这里部分代码省略.........

static void ISR_16550 (ComPort *p)
{
	int		count;
	byte	source;
	byte	b;

	disable();
	while((source = inportb (p->uart + INTERRUPT_ID_REGISTER) & 0x07) != 1)
	{
		switch (source)
		{
			case IIR_RX_DATA_READY_INTERRUPT:
				do
				{
					b = inportb (p->uart + RECEIVE_BUFFER_REGISTER);
					if (!FULL(p->inputQueue))
					{
						ENQUEUE (p->inputQueue, b);
					}
					else
					{
						p->lineStatus |= LSR_OVERRUN_ERROR;
						p->statusUpdated = true;
					}
				} while (inportb (p->uart + LINE_STATUS_REGISTER) & LSR_DATA_READY);
				break;

			case IIR_TX_HOLDING_REGISTER_INTERRUPT:
				count = 16;
				while ((! EMPTY(p->outputQueue)) && count--)
				{
					DEQUEUE (p->outputQueue, b);
					outportb (p->uart + TRANSMIT_HOLDING_REGISTER, b);
				}
				break;

			case IIR_MODEM_STATUS_INTERRUPT:
				p->modemStatus = (inportb (p->uart + MODEM_STATUS_REGISTER) & MODEM_STATUS_MASK) | p->modemStatusIgnore;
				p->statusUpdated = true;
				break;

			case IIR_LINE_STATUS_INTERRUPT:
				p->lineStatus = inportb (p->uart + LINE_STATUS_REGISTER);
				p->statusUpdated = true;
				break;
		}
		source = inportb (p->uart + INTERRUPT_ID_REGISTER) & 0x07;
	}

	// check for lost IIR_TX_HOLDING_REGISTER_INTERRUPT on 16550a!
	if (inportb (p->uart + LINE_STATUS_REGISTER ) & LSR_TRANSMITTER_EMPTY)
	{
		count = 16;
		while ((! EMPTY(p->outputQueue)) && count--)
		{
			DEQUEUE (p->outputQueue, b);
			outportb (p->uart + TRANSMIT_HOLDING_REGISTER, b);
		}
	}

	outportb (0x20, 0x20);
}