queue.c

介绍ROCK OS操作系统.一般用于汽车电子,类似OCVX.里面是个DEMO文档,内附说明.

/******************************************************************************
    Copyright (c) 2006 by RockOS.
    All rights reserved.

    This software is supported by the Rock Software Workroom only.

    Any bugs please contact the author with e-mail or QQ:
     E-mail : [e-mail]
         QQ : 59681888
*******************************************************************************
File name   : queue.c
Description : Implements for queue algrithm in RockOS. Including FIFO based
            : queue and priority based queue.
            : 
Auther      : sunxinqiu
History     :
  2006-3-15   first release.
******************************************************************************/

#include "os.h"

/******************************************************************************
Global var  : Q_BASIC_ELEMENT * g_basicElementPool;
Description : The basic queue(FIFO, LIFO queue)'s elment pool in RockOS.
            : 
******************************************************************************/
Q_BASIC_ELEMENT * g_basicElementPool;

/******************************************************************************
Global var  : Q_PRIO_ELEMENT * g_prioElementPool;
Description : The priority base queue's elment pool in RockOS.
            : 
******************************************************************************/
Q_PRIO_ELEMENT * g_prioElementPool;

/******************************************************************************
Global var  : QFREE g_basicFreeQ;
            : QFREE g_priorityFreeQ;
Description : The basic free elements pool and priority base elements pool.
            : 
******************************************************************************/
QFREE g_basicFreeQ;
QFREE g_priorityFreeQ;

/******************************************************************************
Global var  : QCB g_queueCB[];
Description : the queues control block in RockOS.
            : 
******************************************************************************/
QCB g_queueCB[MAX_QUEUE_NUM];

/******************************************************************************
Function    : STATUS queue_init(void)
Params      : N/A
            : 
            : 
            : 
Return      : NO_ERROR always
Description : This function is only used when system startup.
            : 
******************************************************************************/
STATUS queue_init()
{
    U32 i;
    HANDLE handle;
    U32 size;

    if (g_OSRunning != OS_PHASE_INIT)
    {
        return OS_FAIL;
    }

    /* init QCBs. */
    for (handle = 0; handle < MAX_QUEUE_NUM; handle++)
    {
        memset (&g_queueCB[handle], 0, sizeof(QCB));

        g_queueCB[handle].state = OS_QUEUE_FREE;
        g_queueCB[handle].owner = NULL_TASK;
        g_queueCB[handle].head = NULL_HANDLE;
    }

    /* alloc memory for basic elements' pool. */
    size = MAX_BASIC_QELEMENT * sizeof(Q_BASIC_ELEMENT);
    g_basicElementPool = (Q_BASIC_ELEMENT *)memAlloc(size, NULL_TASK,"basic Qelements");
    if (g_basicElementPool == NULL)
    {
        return OS_FAIL;
    }
    
    /* create free elements queue.*/
    g_basicFreeQ.total = MAX_BASIC_QELEMENT;
    g_basicFreeQ.current = MAX_BASIC_QELEMENT;
    g_basicFreeQ.head = 0;
    g_basicFreeQ.tail = MAX_BASIC_QELEMENT - 1;
    for (i = 0; i < MAX_BASIC_QELEMENT; i++)
    {
        g_basicElementPool[i].next = i+1;
    }
    g_basicElementPool[MAX_BASIC_QELEMENT - 1].next = (U32)(-1);

    /* alloc memory for priority based elements' pool. */
    size = MAX_PRIORITY_QELEMENT * sizeof(Q_PRIO_ELEMENT);
    g_prioElementPool = (Q_PRIO_ELEMENT *)memAlloc(size, NULL_TASK, "priority Qelements");
    if (g_prioElementPool == NULL)
    {
        memFree(g_basicElementPool);
        return OS_FAIL;
    }

    /* create free elements queue.*/
    g_priorityFreeQ.total = MAX_PRIORITY_QELEMENT;
    g_priorityFreeQ.current = MAX_PRIORITY_QELEMENT;
    g_priorityFreeQ.head = 0;
    g_priorityFreeQ.tail = MAX_PRIORITY_QELEMENT - 1;
    for (i = 0; i < MAX_PRIORITY_QELEMENT; i++)
    {
        g_prioElementPool[i].next = i+1;
    }
    g_prioElementPool[MAX_PRIORITY_QELEMENT - 1].next = (U32)(-1);

    return OS_SUCCESS;
}

/******************************************************************************
Function    : HQUEUE q_create();
Params      : type  - FIFO queue or priority based queue.
            : qsize - the queue's size, max elements in this queue.
            : owner - the owner task.
            : name  - the queue's name.
Return      : the queue's handle.
Description : create a FIFO, LIFO or priority based queue.
            : 
******************************************************************************/
HQUEUE q_create(U16 type, U32 qsize, HTASK owner, const char * name)
{
    HQUEUE i;
    HQUEUE qid;

    /* params check. */
    if ((type != OS_QUEUE_FIFO)
        &&(type != OS_QUEUE_LIFO)
        &&(type != OS_QUEUE_PRIO)
        &&(type != OS_QUEUE_SET))
    {
        OS_error("q_create(): unknown queue type [%d], owner [%d], name [%s]!!!\n",
                    type, owner, name);
        return NULL_QUEUE;
    }

    if (qsize == 0)
    {
        return NULL_QUEUE;
    }

    /* find a free QCB. */
    qid = NULL_QUEUE;
    OS_ENTER_CRITICAL();
    for (i = 0; i < MAX_QUEUE_NUM; i++)
    {
        if (g_queueCB[i].state == OS_QUEUE_FREE)
        {
            g_queueCB[i].state = type;
            qid = i;
            break;
        }
    }
    OS_LEAVE_CRITICAL();

    /* init the QCB. */
    g_queueCB[qid].owner = owner;
    strncpy (&g_queueCB[qid].name[0], name, MAX_NAME_LEN);

    g_queueCB[qid].total = qsize;
    g_queueCB[qid].current = 0;

    g_queueCB[qid].head = (U32)(-1);
    g_queueCB[qid].tail = (U32)(-1);

    return qid;
}

/******************************************************************************
Function    : STATUS q_destroy(HQUEUE qid)
Params      : qid - the queue to be destroyed.
            : 
            : 
            : 
Return      : OS_SUCCESS or OS_FAIL
Description : destroy a queue created by q_create().
            : 
******************************************************************************/
STATUS q_destroy(HQUEUE qid)
{
    HANDLE handle;

    /* params check. */
    if (qid > MAX_QUEUE_NUM)
    {
        OS_error("q_add(): qid [%d] out of range!!!\n", qid);
        return OS_FAIL;
    }

    if (g_queueCB[qid].state == OS_QUEUE_FREE)
    {
        OS_error("q_add(): qid [%d] is free!!!\n", qid);
        return OS_FAIL;
    }

    while(q_enum(qid, &handle) == OS_SUCCESS)
    {
        // do nothing here.
    }

    OS_ENTER_CRITICAL();
    memset(&g_queueCB[qid], 0, sizeof(QCB));
    g_queueCB[qid].state = OS_QUEUE_FREE;
    OS_LEAVE_CRITICAL();

    return OS_SUCCESS;
}
/******************************************************************************
Function    : STATUS q_add(HQUEUE qid, void * pData, U16 priority)
Params      : qid   - the queue
            : pData - the data
            : priority - the data's priority (if available)
Return      : OS_SUCCESS or OS_FAIL if the queue is full.
Description : add a element to queue.
            : 
******************************************************************************/
STATUS q_add(HQUEUE qid, HANDLE handle, U16 priority)
{
    STATUS nret;

    U32 element;
    U32 head, tail;

    U32 prev, current;

    /* params check. */
    if (qid > MAX_QUEUE_NUM)
    {
        OS_error("q_add(): qid [%d] out of range!!!\n", qid);
        return OS_FAIL;
    }

    if (g_queueCB[qid].state == OS_QUEUE_FREE)
    {
        OS_error("q_add(): qid [%d] is free!!!\n", qid);
        return OS_FAIL;
    }

    switch(g_queueCB[qid].state)
    {
    case OS_QUEUE_FIFO:
    case OS_QUEUE_SET:
        if (g_queueCB[qid].current == g_queueCB[qid].total)
        {
            OS_error("q_add(): queue [%d] is full!!!\n", qid);
            q_showSingle(qid);
            nret = OS_FAIL;
        }
        else
        {
            if (g_basicFreeQ.current == 0)
            {
                OS_error("q_add(): basic queue elements are all used, pool exhausted!!!\n");
                nret = OS_FAIL;
                break;
            }

            /* get a element from element pool. */
            element = g_basicFreeQ.head;
            g_basicFreeQ.head = g_basicElementPool[element].next;

            g_basicFreeQ.current--;

            /* fill data. */
            g_basicElementPool[element].handle = handle;

            /* check if the queue is empty or not. */
            if (g_queueCB[qid].current == 0)
            {
                /* this is the first element. */
                g_basicElementPool[element].next = (U32)(-1);

                g_queueCB[qid].head = element;
                g_queueCB[qid].tail = element;
                g_queueCB[qid].current++;
            }
            else
            {
                /* add it to queue. */
                tail = g_queueCB[qid].tail;
                g_basicElementPool[tail].next = element;
                g_basicElementPool[element].next = (U32)(-1);

                g_queueCB[qid].tail = element;
                g_queueCB[qid].current++;
            }

            nret = OS_SUCCESS;
        }
        break;

    case OS_QUEUE_LIFO:
        if (g_queueCB[qid].current == g_queueCB[qid].total)
        {
            OS_error("q_add(): queue [%d] is full!!!\n", qid);
            q_showSingle(qid);
            nret = OS_FAIL;
        }
        else
        {
            if (g_basicFreeQ.current == 0)
            {
                OS_error("q_add(): basic queue elements are all used, pool exhausted!!!\n");
                nret = OS_FAIL;
                break;
            }

            /* get a element from element pool. */
            element = g_basicFreeQ.head;
            g_basicFreeQ.head = g_basicElementPool[element].next;
            g_basicFreeQ.current--;

            /* fill data. */
            g_basicElementPool[element].handle = handle;

            /* add it to queue. */
            head = g_queueCB[qid].head;
            g_basicElementPool[element].next = head;
            g_queueCB[qid].head = element;
            g_queueCB[qid].current++;
        }
        break;

    case OS_QUEUE_PRIO:
        if (g_queueCB[qid].current == g_queueCB[qid].total)
        {
            OS_error("q_add(): queue [%d] is full!!!\n", qid);
            q_showSingle(qid);
            nret = OS_FAIL;
        }
        else
        {
            if (g_priorityFreeQ.current == 0)
            {
                OS_error("q_add(): priority base queue elements are all used, pool exhausted!!!\n");
                nret = OS_FAIL;
                break;
            }

            /* get a element from element pool. */
            element = g_priorityFreeQ.head;
            g_priorityFreeQ.head = g_prioElementPool[element].next;
            g_priorityFreeQ.current--;

            /* fill data. */
            g_prioElementPool[element].priority = priority;
            g_prioElementPool[element].handle = handle;

            /* find the proper position and add it to queue. */
            prev = (U32)(-1);
            current = g_queueCB[qid].head;
            while((current != (U32)(-1))&&(priority >= g_prioElementPool[current].priority))
            {
                prev = current;
                current = g_prioElementPool[current].next;
            }

            if (prev != (U32)(-1))
            {
                /* insert to the chain. */
                g_prioElementPool[prev].next = element;
                g_prioElementPool[element].next = current;
            }
            else
            {
                /* insert to the head. */
                g_prioElementPool[element].next = g_queueCB[qid].head;
                g_queueCB[qid].head = element;
            }
            g_queueCB[qid].current++;
        }
        break;

    default:
        OS_error("q_add(): qid [%d] state is [%d]!!!\n", qid, g_queueCB[qid].state);
        nret = OS_FAIL;
        break;
    }

    return nret;
}

/******************************************************************************
Function    : STATUS q_enum (HQUEUE qid, void ** pData)
Params      : qid   - the queue which to be enumed.
            : pData - to save the element's data from queue.
            : 
            : 
Return      : OS_SUCCESS or OS_FAIL if the queue is empty.
Description : enumerate the first element from a specified queue.
******************************************************************************/
STATUS q_enum (HQUEUE qid, HANDLE * phandle)
{
    STATUS nret;

    U32 element;
    U32 tail;

    /* params check. */
    if (qid > MAX_QUEUE_NUM)
    {
        OS_error("q_enum(): qid [%d] out of range!!!\n", qid);
        return OS_FAIL;
    }

    if (g_queueCB[qid].state == OS_QUEUE_FREE)
    {
        OS_error("q_enum(): qid [%d] is free!!!\n", qid);
        return OS_FAIL;
    }

    /* if queue is empty. */
    if (g_queueCB[qid].current == 0)
    {
        return OS_FAIL;
    }

    switch(g_queueCB[qid].state)
    {
    case OS_QUEUE_FIFO:
    case OS_QUEUE_LIFO:
        /* get the data and clear it. */
        element = g_queueCB[qid].head;
        if (phandle != NULL)
        {
            * phandle = g_basicElementPool[element].handle;
        }
        g_basicElementPool[element].handle = NULL_HANDLE;

        /* remove it from queue. */
        g_queueCB[qid].current--;
        if (g_queueCB[qid].current == 0)
        {
            g_queueCB[qid].head = (U32)(-1);
        }
        else
        {