CTaskHeap Class Reference

#include <externs.h>

Collaboration diagram for CTaskHeap:

[legend]

Public Member Functions
	CTaskHeap ()
	~CTaskHeap ()
bool	Insert (PTASK_RECORD, SCHCMP *)
PTASK_RECORD	PeekAtTopmost (void)
PTASK_RECORD	RemoveTopmost (SCHCMP *)
void	CancelTask (FTASK *fpTask, void *arg_voidptr, int arg_Integer)
int	TraverseUnordered (SCHLOOK *pfLook, SCHCMP *pfCompare)
int	TraverseOrdered (SCHLOOK *pfLook, SCHCMP *pfCompare)
Private Member Functions
bool	Grow (void)
void	SiftDown (int, SCHCMP *)
void	SiftUp (int, SCHCMP *)
PTASK_RECORD	Remove (int, SCHCMP *)
void	Update (int iNode, SCHCMP *pfCompare)
void	Sort (SCHCMP *pfCompare)
void	Remake (SCHCMP *pfCompare)
Private Attributes
int	m_nAllocated
int	m_nCurrent
PTASK_RECORD *	m_pHeap
int	m_iVisitedMark

---

Detailed Description

Definition at line 894 of file externs.h.

---

Constructor & Destructor Documentation

CTaskHeap::CTaskHeap

(

)

Definition at line 326 of file timer.cpp.

References INITIAL_TASKS, m_iVisitedMark, m_nAllocated, m_nCurrent, and m_pHeap.

{
    m_nCurrent = 0;
    m_iVisitedMark = 0;
    m_nAllocated = INITIAL_TASKS;
    m_pHeap = new PTASK_RECORD[m_nAllocated];
    if (!m_pHeap)
    {
        m_nAllocated = 0;
    }
}

CTaskHeap::~CTaskHeap

(

)

Definition at line 338 of file timer.cpp.

References m_nCurrent, and m_pHeap.

{
    while (m_nCurrent--)
    {
        PTASK_RECORD pTask = m_pHeap[m_nCurrent];
        if (pTask)
        {
            delete pTask;
        }
        m_pHeap[m_nCurrent] = NULL;
    }
    if (m_pHeap)
    {
        delete [] m_pHeap;
    }
}

---

Member Function Documentation

void CTaskHeap::CancelTask	(	FTASK *	fpTask,
		void *	arg_voidptr,
		int	arg_Integer
	)

Definition at line 405 of file timer.cpp.

References TASK_RECORD::fpTask, m_nCurrent, and m_pHeap.

Referenced by CScheduler::CancelTask().

{
    for (int i = 0; i < m_nCurrent; i++)
    {
        PTASK_RECORD p = m_pHeap[i];
        if (  p->fpTask == fpTask
           && p->arg_voidptr == arg_voidptr
           && p->arg_Integer == arg_Integer)
        {
            p->fpTask = NULL;
        }
    }
}

bool CTaskHeap::Grow

(

void

)

[private]

Definition at line 372 of file timer.cpp.

References EXTRA_TASKS, m_nAllocated, and m_pHeap.

Referenced by Insert().

{
    // Grow the heap.
    //
    int n = m_nAllocated + EXTRA_TASKS;
    PTASK_RECORD *p = new PTASK_RECORD[n];
    if (!p)
    {
        return false;
    }

    memcpy(p, m_pHeap, sizeof(PTASK_RECORD)*m_nAllocated);
    m_nAllocated = n;
    delete [] m_pHeap;
    m_pHeap = p;

    return true;
}

bool CTaskHeap::Insert	(	PTASK_RECORD	,
		SCHCMP *
	)

Definition at line 355 of file timer.cpp.

References Grow(), m_iVisitedMark, TASK_RECORD::m_iVisitedMark, m_nAllocated, m_nCurrent, m_pHeap, and SiftUp().

Referenced by CScheduler::DeferImmediateTask(), CScheduler::DeferTask(), and CScheduler::ReadyTasks().

{
    if (m_nCurrent == m_nAllocated)
    {
        if (!Grow())
        {
            return false;
        }
    }
    pTask->m_iVisitedMark = m_iVisitedMark-1;

    m_pHeap[m_nCurrent] = pTask;
    m_nCurrent++;
    SiftUp(m_nCurrent-1, pfCompare);
    return true;
}

PTASK_RECORD CTaskHeap::PeekAtTopmost

(

void

)

Definition at line 391 of file timer.cpp.

References m_nCurrent, and m_pHeap.

Referenced by CScheduler::ReadyTasks(), CScheduler::RunTasks(), and CScheduler::WhenNext().

{
    if (m_nCurrent <= 0)
    {
        return NULL;
    }
    return m_pHeap[0];
}

void CTaskHeap::Remake

(

SCHCMP *

pfCompare

)

[private]

Definition at line 776 of file timer.cpp.

References m_nCurrent, and SiftUp().

Referenced by TraverseOrdered().

{
    int s_nCurrent = m_nCurrent;
    m_nCurrent = 0;
    while (s_nCurrent--)
    {
        m_nCurrent++;
        SiftUp(m_nCurrent-1, pfCompare);
    }
}

PTASK_RECORD CTaskHeap::Remove	(	int	,
		SCHCMP *
	)			[private]

Definition at line 644 of file timer.cpp.

References m_nCurrent, m_pHeap, SiftDown(), and SiftUp().

Referenced by RemoveTopmost(), and TraverseUnordered().

{
    if (iNode < 0 || m_nCurrent <= iNode) return NULL;

    PTASK_RECORD pTask = m_pHeap[iNode];

    m_nCurrent--;
    m_pHeap[iNode] = m_pHeap[m_nCurrent];
    SiftDown(iNode, pfCompare);
    SiftUp(iNode, pfCompare);

    return pTask;
}

PTASK_RECORD CTaskHeap::RemoveTopmost

(

SCHCMP *

)

Definition at line 400 of file timer.cpp.

References Remove().

Referenced by CScheduler::ReadyTasks(), and CScheduler::RunTasks().

{
    return Remove(0, pfCompare);
}

void CTaskHeap::SiftDown	(	int	,
		SCHCMP *
	)			[private]

Definition at line 600 of file timer.cpp.

References HEAP_LEFT_CHILD, HEAP_RIGHT_CHILD, m_nCurrent, and m_pHeap.

Referenced by Remove(), Sort(), and Update().

{
    int parent = iSubRoot;
    int child = HEAP_LEFT_CHILD(parent);

    PTASK_RECORD Ref = m_pHeap[parent];

    while (child < m_nCurrent)
    {
        int rightchild = HEAP_RIGHT_CHILD(parent);
        if (rightchild < m_nCurrent)
        {
            if (pfCompare(m_pHeap[rightchild], m_pHeap[child]) < 0)
            {
                child = rightchild;
            }
        }
        if (pfCompare(Ref, m_pHeap[child]) <= 0)
            break;

        m_pHeap[parent] = m_pHeap[child];
        parent = child;
        child = HEAP_LEFT_CHILD(parent);
    }
    m_pHeap[parent] = Ref;
}

void CTaskHeap::SiftUp	(	int	,
		SCHCMP *
	)			[private]

Definition at line 627 of file timer.cpp.

References HEAP_PARENT, and m_pHeap.

Referenced by Insert(), Remake(), Remove(), and Update().

{
    while (child)
    {
        int parent = HEAP_PARENT(child);
        if (pfCompare(m_pHeap[parent], m_pHeap[child]) <= 0)
            break;

        PTASK_RECORD Tmp;
        Tmp = m_pHeap[child];
        m_pHeap[child] = m_pHeap[parent];
        m_pHeap[parent] = Tmp;

        child = parent;
    }
}

void CTaskHeap::Sort

(

SCHCMP *

pfCompare

)

[private]

Definition at line 763 of file timer.cpp.

References m_nCurrent, m_pHeap, and SiftDown().

Referenced by TraverseOrdered().

{
    int s_nCurrent = m_nCurrent;
    while (m_nCurrent--)
    {
        PTASK_RECORD p = m_pHeap[m_nCurrent];
        m_pHeap[m_nCurrent] = m_pHeap[0];
        m_pHeap[0] = p;
        SiftDown(0, pfCompare);
    }
    m_nCurrent = s_nCurrent;
}

int CTaskHeap::TraverseOrdered	(	SCHLOOK *	pfLook,
		SCHCMP *	pfCompare
	)

Definition at line 745 of file timer.cpp.

References IU_DONE, m_nCurrent, m_pHeap, Remake(), and Sort().

Referenced by CScheduler::TraverseOrdered().

{
    Sort(pfCompare);

    for (int i = m_nCurrent-1; i >= 0; i--)
    {
        PTASK_RECORD p = m_pHeap[i];
        int cmd = pfLook(p);
        if (IU_DONE == cmd)
        {
            break;
        }
    }

    Remake(pfCompare);
    return true;
}

int CTaskHeap::TraverseUnordered	(	SCHLOOK *	pfLook,
		SCHCMP *	pfCompare
	)

Definition at line 687 of file timer.cpp.

References IU_DONE, IU_REMOVE_TASK, IU_UPDATE_TASK, TASK_RECORD::m_iVisitedMark, m_iVisitedMark, m_nCurrent, m_pHeap, Remove(), and Update().

Referenced by CScheduler::TraverseUnordered().

{
    // Indicate that everything has not been visited.
    //
    m_iVisitedMark++;
    if (m_iVisitedMark == 0)
    {
        // We rolled over. Yeah, this code will probably never run, but
        // let's go ahead and mark all the records as visited anyway.
        //
        for (int i = 0; i < m_nCurrent; i++)
        {
            PTASK_RECORD p = m_pHeap[i];
            p->m_iVisitedMark = m_iVisitedMark;
        }
        m_iVisitedMark++;
    }

    int bUnvisitedRecords;
    do
    {
        bUnvisitedRecords = false;
        for (int i = 0; i < m_nCurrent; i++)
        {
            PTASK_RECORD p = m_pHeap[i];

            if (p->m_iVisitedMark == m_iVisitedMark)
            {
                // We have already seen this one.
                //
                continue;
            }
            bUnvisitedRecords = true;
            p->m_iVisitedMark = m_iVisitedMark;

            int cmd = pfLook(p);
            switch (cmd)
            {
            case IU_REMOVE_TASK:
                Remove(i, pfCompare);
                break;

            case IU_DONE:
                return false;

            case IU_UPDATE_TASK:
                Update(i, pfCompare);
                break;
            }
        }
    } while (bUnvisitedRecords);
    return true;
}

void CTaskHeap::Update	(	int	iNode,
		SCHCMP *	pfCompare
	)			[private]

Definition at line 658 of file timer.cpp.

References m_nCurrent, SiftDown(), and SiftUp().

Referenced by TraverseUnordered().

{
    if (iNode < 0 || m_nCurrent <= iNode)
    {
        return;
    }

    SiftDown(iNode, pfCompare);
    SiftUp(iNode, pfCompare);
}

---

Field Documentation

int CTaskHeap::m_iVisitedMark [private]

Definition at line 901 of file externs.h.

Referenced by CTaskHeap(), Insert(), and TraverseUnordered().

int CTaskHeap::m_nAllocated [private]

Definition at line 897 of file externs.h.

Referenced by CTaskHeap(), Grow(), and Insert().

int CTaskHeap::m_nCurrent [private]

Definition at line 898 of file externs.h.

Referenced by CancelTask(), CTaskHeap(), Insert(), PeekAtTopmost(), Remake(), Remove(), SiftDown(), Sort(), TraverseOrdered(), TraverseUnordered(), Update(), and ~CTaskHeap().

PTASK_RECORD* CTaskHeap::m_pHeap [private]

Definition at line 899 of file externs.h.

Referenced by CancelTask(), CTaskHeap(), Grow(), Insert(), PeekAtTopmost(), Remove(), SiftDown(), SiftUp(), Sort(), TraverseOrdered(), TraverseUnordered(), and ~CTaskHeap().

---

The documentation for this class was generated from the following files:

• mux/src/externs.h
• mux/src/timer.cpp

---