Functions to manage thread lists. More...

Collaboration diagram for Lists functions:

Functions
void	__thlAddPrioList (__PTHREAD th, __PTHREAD *thb)
	Adds the thread in a priority ordered list.
void	__thlRemovePrioList (__PTHREAD *thb)
	Removes the first thread from a priority ordered list.
void	__thlAddSuspList (__PTHREAD th, __PTHREAD *thl)
	Adds the thread to the end of the suspended threads list.
void	__thlRemoveSuspList (__PTHREAD th, __PTHREAD thb, __PTHREAD thl)
	Removes the thread from the suspended threads list.
void	__thlAddEvtPrio (__PTHREAD th, __PTHREAD *the)
	Add the thread to the event's thread list, ordered by priority.
void	__thlRemoveEvtPrio (__PTHREAD th, __PTHREAD *the)
	Removes the thread from the event's thread list, ordered by priority.

Detailed Description

Functions to manage thread lists.

The following functions should be used exclusively by the Core module in order to manage the thread linked lists.

Milos scheduler manages three lists by now:

A list representing the threads ready to run, ordered by priority. That is the __threadReady list, defined in thread.c
A list of suspended threads, ordered by time of arrival (threads are appended at the end of the list).
For each event in the system, a list containing the threads that are waiting for that particular event, ordered by priority.

The first two methods (__thlAddPrioList() and __thlRemovePrioList()) are used to keep track of the ready threads ordered by priority. __thlAddSuspList() and __thlRemoveSuspList() manages those threads in suspended (sleeping or waiting) state.

Note that the four methods described above use the same linked pointers (th_qnext and thq_prev). That is because a ready thread cannot be in the suspended list and vice-versa.

__thlAddEvtPrio() and __thlRemoveEvtPrio() sort the threads by priority, to be used by __eventSet() and __eventWait().

Function Documentation

void __thlAddPrioList	(	__PTHREAD	th,
		__PTHREAD *	thb
	)

Adds the thread in a priority ordered list.

Even this function can be called from outside Core module, it should not.

Since we are always removing only the head of the priority ordered list do not use th_qprev value when ordering by priority.

Parameters:

th	Pointer to a thread pointer.
thb	Pointer to the thread at the head of the list.

Returns:: Nothing.

Definition at line 73 of file thlist.c.

{
    __PTHREAD tl = __NULL;
    __PTHREAD p = *thb;

    /* Set null here, we are doing it anyway ahead in the code
     * whenever the exit condition.
     */
    th->th_qnext = th->th_qprev = __NULL;

    if (p == __NULL)
    {
        *thb = th;
        return;
    }

    /*
     * The worst case here is when N threads equals ALL threads - 1,
     * and we are adding a thread with the lowest priority
     */
    while (p && p->th_priority <= th->th_priority)
    {
        tl = p;
        p = p->th_qnext;
    }

    /* Exit conditions:
     * -    p is null and is equal to *thb, so
     *      th becomes the head of the list (*thb = th).
     *      This condition is already checked at the beginning
     *      of the function.
     *
     * -    p is null means we reached the end of the list.
     *
     * -    p is not null and is equal to *thb so
     *      th replaces p as the head of the list (*thb = th).
     *
     * -    p is not null and is not equal to *thb so th is
     *      inserted somewhere in the list.
     */

    if (p == __NULL)
    {
        tl->th_qnext = th;
    } else
    {
        if (p == *thb)
        {
            th->th_qnext = p;
            *thb = th;
        } else
        {
            th->th_qnext = tl->th_qnext;
            tl->th_qnext = th;
        }
    }
}

void __thlRemovePrioList ( __PTHREAD * thb )

Removes the first thread from a priority ordered list.

Even this function can be called from outside Core module, it should not.

It's a priority ordered list, and this function is called when we are about to execute the thread with highest priority (among those that are ready to run). So is enough to remove only the first thread pointer.

Parameters:

thb	Pointer to a thread pointer.

Returns:: Nothing.

Definition at line 146 of file thlist.c.

{
    __PTHREAD th = *thb;

    *thb = th->th_qnext;
    th->th_qnext = th->th_qprev = __NULL;
}

void __thlAddSuspList	(	__PTHREAD	th,
		__PTHREAD *	thl
	)

Adds the thread to the end of the suspended threads list.

Even this function can be called from outside Core module, it should not.

This is not a priority ordered list. The thl parameter points the last thread in the list.

Parameters:

th	Pointer to a thread.
thl	Pointer to the last thread pointer in the list.

Returns:: Nothing.

Definition at line 170 of file thlist.c.

{
    th->th_qnext = __NULL;
    th->th_qprev = *thl;
    if (*thl) (*thl)->th_qnext = th;
    *thl = th;
}

void __thlRemoveSuspList	(	__PTHREAD	th,
		__PTHREAD *	thb,
		__PTHREAD *	thl
	)

Removes the thread from the suspended threads list.

Even this function can be called from outside Core module, it should not.

This is not a priority ordered list. The thl parameter points the last thread in the list.

Parameters:

th	Pointer to a thread.
thb	Pointer to the first thread pointer.
thl	Pointer to the last thread pointer.

Returns:: Nothing.

Definition at line 194 of file thlist.c.

{
    /* If the previous in list is not null assign the next in list */
    if (th->th_qprev)
    {
        th->th_qprev->th_qnext = th->th_qnext;
    }

    /* If the next in list is not null assign the previous in list */
    if (th->th_qnext)
    {
        th->th_qnext->th_qprev = th->th_qprev;
    }

    /* If we are removing the head of the list, assign it the next thread */
    if (*thb == th)
    {
        *thb = th->th_qnext;
    }

    /* If the thread we are removing is the last one, assign the previous to thl */
    if (*thl == th)
    {
        *thl = th->th_qprev;
    }

    /* If the head is null, the tail should be null */
    if (*thb == __NULL) *thl = __NULL;

    /* Clean */
    th->th_qnext = th->th_qprev = __NULL;

}

void __thlAddEvtPrio	(	__PTHREAD	th,
		__PTHREAD *	the
	)

Add the thread to the event's thread list, ordered by priority.

Even this function can be called from outside Core module, it should not.

Because a thread that waits for an event can be removed from the event's list at any time, we should use th_evprev value to save time, instead of cycling the list in a loop.

Parameters:

th	Pointer to a thread.
the	Pointer to the head of the list pointer.

Returns:: Nothing.

Definition at line 244 of file thlist.c.

{
    __PTHREAD tl = __NULL;
    __PTHREAD p = *the;

    /* Set null here, we are doing it anyway ahead in the code
     * whenever the exit condition.
     */
    th->th_evnext = th->th_evprev = __NULL;

    if (p == __NULL)
    {
        *the = th;
        return;
    }

    /*
     * The worst case here is when N threads equals ALL threads - 1,
     * and we are adding a thread with the lowest priority
     */
    while (p && p->th_priority <= th->th_priority)
    {
        tl = p;
        p = p->th_evnext;
    }

    /* Exit conditions:
     * -    p is null and is equal to *the, so
     *      th becomes the head of the list (*the = th).
     *      This condition is already checked at the beginning
     *      of the function.
     *
     * -    p is null means we reached the end of the list.
     *
     * -    p is not null and is equal to *the so
     *      th replaces p as the head of the list (*the = th).
     *
     * -    p is not null and is not equal to *the so th is
     *      inserted somewhere in the list.
     */

    if (p == __NULL)
    {
        tl->th_evnext = th;
        th->th_evprev = tl;
    } else
    {
        if (p == *the)
        {
            p->th_evprev = th;
            th->th_evnext = p;
            *the = th;
        } else
        {
            th->th_evnext = p;
            tl->th_evnext = p->th_evprev = th;
            th->th_evprev = tl;
        }
    }
}

void __thlRemoveEvtPrio	(	__PTHREAD	th,
		__PTHREAD *	the
	)

Removes the thread from the event's thread list, ordered by priority.

Even this function can be called from outside Core module, it should not.

Because a thread that waits for an event can be removed from the event's list at any time, we should use th_evprev value to save time, instead of cycling the list in a loop.

Parameters:

th	Pointer to a thread.
the	Pointer to the head of the list pointer.

Returns:: Nothing.

Definition at line 321 of file thlist.c.

{
    if (th->th_evprev) th->th_evprev->th_evnext = th->th_evnext;
    if (th->th_evnext) th->th_evnext->th_evprev = th->th_evprev;
    if (*the == th) *the = th->th_evnext;
    th->th_evnext = th->th_evprev = __NULL;
}