rsc.c

新一代基于事件的嵌入式操作系统dyos在三星的s3c44b0的arm芯片上的完整移植代码

//----------------------------------------------------
//Copyright (C), 2004-2009,  lst.
//版权所有 (C), 2004-2009,   lst.
//所属模块: 资源管理
//作者：lst
//版本：V1.0.0
//文件描述: 创建、添加、移动、删除、搜索资源结点的服务
//其他说明:
//修订历史:
//    2. 日期:20090131
//       作者:lst
//       新版本号：v1.1.0
//       修改说明:
//          1.加了个总根节点，添加了模块初始化函数
//          2.用信号量保护并发访问安全
//          3.改进了遍历函数，允许用NULL代表遍历整个队列
//          4.修正了一些bug
//    1. 日期:20090104
//       作者:lst
//       新版本号：v1.0.0
//       修改说明:原始版本
//------------------------------------------------------
#include "inc_os.h"
#include <string.h>

//-------------资源链算法说明----------------------
//各同级结点连成双向循环链表
//每个结点的child指针直接指向的结点称为该结点的长子结点.又称为该下级结点的
//长兄结点,长兄结点的前一个结点称为小弟结点,也称父结点的满子结点.
//所有结点的Parent指针均指向父结点

//特别提示，资源队列的并发访问安全由资源管理模块负责，资源结点自身的并发访问
//          保护由使用者负责。

static struct rsc_node tg_rsc_root;
static struct semaphore_LCB tg_semp_rsc_root;
static struct rsc_node *pg_rsc_root;

//----初始化资源管理模块-------------------------------------------------------
//功能: 创建总根结点，本函数被分裂成两个，第二个函数必须在执行完锁初始化后才能
//      调用，第一个则必须在锁初始化执行前调用
//参数: 无
//返回: 新加入的结点
//------------------------------------------------------------------------------
bool_t module_init_rsc1(void)
{
    tg_rsc_root.child = NULL;
    tg_rsc_root.name = "resouce queue";
    tg_rsc_root.next =&tg_rsc_root;
    tg_rsc_root.previous =&tg_rsc_root;
    tg_rsc_root.parent = NULL;
    tg_rsc_root.node_size = sizeof(tg_rsc_root);
    pg_rsc_root = &tg_rsc_root;
    return true;
}
bool_t module_init_rsc2(void)
{
    __semp_create_knl(&tg_semp_rsc_root,1,1,"semaphore for resouce queue");
    return true;
}
//----添加根结点----------------------------------------------------------------
//功能: 在资源链中添加一个根结点(特供锁模块，因此时锁尚未初始化，)
//参数: node,新添加的结点指针
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_add_lock_root_node(struct  rsc_node *node,
                                uint32_t size,char *name)
{
    struct  rsc_node *root_node;
    if(node == NULL)
        return NULL;
    node->parent = pg_rsc_root; 
    node->child=NULL;
    node->node_size = size;
    node->name = name;
    if(pg_rsc_root->child == NULL)
    {
        pg_rsc_root->child = node;
        node->next = node;
        node->previous = node;
    }else
    {
        root_node = pg_rsc_root->child;
        node->next = root_node;
        node->previous = root_node->previous;
        root_node->previous->next = node;
        root_node->previous = node;
    }
    return node;
}

//----添加根结点----------------------------------------------------------------
//功能: 在资源链中添加一个根结点
//参数: node,新添加的结点指针
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_add_root_node(struct  rsc_node *node,
                                uint32_t size,char *name)
{
    struct  rsc_node *root_node;
    if(node == NULL)
        return NULL;
    node->parent = pg_rsc_root; 
    node->child=NULL;
    node->node_size = size;
    node->name = name;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return NULL;
    //资源队列中至少存在一个信号量结点，无须判断是否空
    root_node = pg_rsc_root->child;
    node->next = root_node;
    node->previous = root_node->previous;
    root_node->previous->next = node;
    root_node->previous = node;
    semp_post(&tg_semp_rsc_root);
    return node;
}

//----插入结点------------------------------------------------------------------
//功能: 在资源链表中指定项前面插入一个结点,若指定结点是长子,则成为新的长子
//参数  node,在此结点前面插入结点
//      new_node,待插入的新结点
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_insert_node(struct  rsc_node *node,
                                   struct rsc_node *new_node,
                                   uint32_t size,char *name)
{
    if((node==NULL)||(new_node==NULL))
        return NULL;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return NULL;
    new_node->next=node;
    new_node->previous=node->previous;
    new_node->parent=node->parent;
    new_node->child=NULL;
    new_node->node_size = size;
    new_node->name = name;
    node->previous->next=new_node;
    node->previous=new_node;
    if(node->parent != pg_rsc_root) //根结点无需处理父结点的子指针
    {
        if(node->parent->child==node)//node是长子结点,new_node成为新长子
        {   
            node->parent->child=new_node;
        }
    }
    semp_post(&tg_semp_rsc_root);
    return new_node;
}

//----增加结点------------------------------------------------------------------
//功能: 在资源链表中指定项后面增加一个结点,若指定结点是满子,则成为新的满子
//参数  node,在此结点后面插入结点
//      new_node,待插入的新结点
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_add_node(struct  rsc_node *node,
                                struct  rsc_node *new_node,
                                uint32_t size,char *name)
{
    if((node==NULL)||(new_node==NULL))
        return NULL;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return NULL;
    new_node->previous=node;
    new_node->next=node->next;
    new_node->parent=node->parent;
    new_node->child=NULL;
    new_node->node_size = size;
    new_node->name = name;
    node->next->previous=new_node;
    node->next=new_node;
    semp_post(&tg_semp_rsc_root);
    return new_node;
}

//----插入子结点----------------------------------------------------------------
//功能: 给指定结点增加一个子结点,该结点将加入到所有子结点的最后面,即满子结点,
//参数  parent_node,新结点的父亲结点
//      new_node,待插入的新结点
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_add_son(struct  rsc_node *parent_node,
                               struct  rsc_node *new_node,
                               uint32_t size,char *name)
{
    struct  rsc_node *p;
    if((parent_node==NULL)||(new_node==NULL))
        return NULL;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return NULL;
    new_node->node_size = size;
    new_node->name = name;
    new_node->child=NULL;
    if(parent_node->child==NULL)
    {
        parent_node->child=new_node;
        new_node->parent=parent_node;
        new_node->next=new_node;
        new_node->previous=new_node;
    }else
    {
        p=parent_node->child;
        new_node->next=p;
        new_node->previous=p->previous;
        new_node->parent=parent_node;
        p->previous->next=new_node;
        p->previous=new_node;
    }
    semp_post(&tg_semp_rsc_root);
    return new_node;
}

//----插入一个长子结点---------------------------------------------------------
//功能: 给指定结点增加一个子结点,并且使该结点成为长子结点,
//参数  parent_node,新结点的父亲结点
//      new_node,待插入的新结点
//返回: 新加入的结点
//------------------------------------------------------------------------------
struct  rsc_node * rsc_add_eldest_son(struct  rsc_node *parent_node,
                                    struct  rsc_node *new_node,
                                    uint32_t size,char *name)
{
    struct  rsc_node *p;
    if((parent_node==NULL)||(new_node==NULL))
        return NULL;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return NULL;
    new_node->node_size = size;
    new_node->name = name;
    new_node->child=NULL;
    if(parent_node->child==NULL)
    {
        parent_node->child=new_node;
        new_node->parent=parent_node;
        new_node->next=new_node;
        new_node->previous=new_node;
    }else
    {
        p=parent_node->child;
        new_node->next=p;
        new_node->previous=p->previous;
        new_node->parent=parent_node;
        p->previous->next=new_node;
        p->previous=new_node;
        parent_node->child = parent_node->child->previous;
    }
    semp_post(&tg_semp_rsc_root);
    return new_node;
}

//---删除一个结点---------------------------------------------------------------
//功能: 把一个结点从资源链表中断开结点,该结点不能有子结点
//参数: node,被删除的结点,如该结点有子结点则不删除
//返回: 如果被删结点有子结点则返回false,否则返回true
//备注1，资源结点没有信号量保护，删除结点需谨慎。
//备注2，不提供删除一棵树的功能，这是诱导犯罪。因为rsc模块无法不知道结点用途，
//      也就不知道如何处理结点负载，故删除树可能会导致节点负载不释放类的内存错误
//------------------------------------------------------------------------------
bool_t rsc_del_node(struct  rsc_node *node)
{

    bool_t result;
    if(node == NULL)
        return false;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return false;
    if(node->child != NULL) //子结点非空,不操作
        result = false;
    else
    {
        if(node->parent == pg_rsc_root)    //是个根结点
        {
            //总有信号量结点在，无须判断是否唯一根结点
            node->previous->next = node->next;
            node->next->previous = node->previous;
        }else
        {
            if(node->next == node)   //说明该结点没有兄弟结点.
            {
                node->parent->child = NULL;
            }else
            {
                if(node->parent->child == node)
                {   //说明该结点是长子结点,需要改变长子结点
                    node->parent->child = node->next;
                }
                node->previous->next = node->next;
                node->next->previous = node->previous;
            }
        }
        result = true;
    }
    semp_post(&tg_semp_rsc_root);
    return true;
}

//---移动一棵树---------------------------------------------------------------
//功能: 移动一棵树到别的结点下面成为其子树
//参数: node,被移动的结点指针
//返回: 无
//-----------------------------------------------------------------------------
bool_t rsc_moveto_tree(struct rsc_node *parent,struct  rsc_node *node)
{
    return true;
}

//----移动结点成为小弟---------------------------------------------------------
//功能: 移动一个结点,使该结点成为小弟结点,该结点本来应在链表中
//参数: node,被移动的结点指针
//返回: 无
//-----------------------------------------------------------------------------
bool_t rsc_moveto_least(struct  rsc_node *node)
{
    struct  rsc_node *eldest;
    if(node == NULL)
        return false;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return false;
    if(node->parent == pg_rsc_root)    //根结点不分兄弟
        ;
    else
    {
        eldest = node->parent->child;
        if(eldest == node)
        //如果node是长兄结点,则直接移动父结点的子指针到下一个结点就可以了.
            node->parent->child = node->next;
        //以下从链表中取出结点
        node->next->previous = node->previous;
        node->previous->next = node->next;
        //以下把node插入小弟位置,由于是循环链表,长兄结点的前面就是小弟结点.
        node->next = eldest;
        node->previous = eldest->previous;
        eldest->previous->next = node;
        eldest->previous = node;
    }
    semp_post(&tg_semp_rsc_root);
    return true;
}

//----移动结点成为长兄----------------------------------------------------------
//功能: 移动一个结点,使该结点成为长兄结点,该结点本来应在链表中
//参数: node,被移动的结点指针
//返回: 无
//------------------------------------------------------------------------------
bool_t rsc_movto_eldest(struct  rsc_node *node)
{
    if(node == NULL)
        return false;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return false;
    if(node->parent == NULL)    //根结点不分兄弟
        ;
    else
    {
        rsc_moveto_least(node);
        node->parent->child = node;
    }
    semp_post(&tg_semp_rsc_root);
    return false;
}

//----移动结点到某结点后面------------------------------------------------------
//功能: 移动一个结点到某结点后面成为弟结点,该结点本来应在链表中
//参数: node,被移动的结点指针
//      elder,目标结点,node移动到本结点后面
//返回: 无
//------------------------------------------------------------------------------
bool_t rsc_movto_lesser(struct  rsc_node *elder,struct  rsc_node *node)
{
    if((elder==NULL)||(node==NULL))
        return false;
    if(semp_pend(&tg_semp_rsc_root,cn_timeout_forever) ==false)
        return false;
    if(node->parent == pg_rsc_root)    //根结点不分兄弟
        ;
    else
    {
        if(node->parent->child == node)
            node->parent->child = node->next;
        //以下从链表中取出结点
        node->next->previous = node->previous;
        node->previous->next = node->next;
        //以下把node插入小弟位置,由于是循环链表,长兄结点的前面就是小弟结点.
        node->previous = elder;
        node->next = elder->next;
        elder->next->previous = node;
        elder->next = node;
    }
    semp_post(&tg_semp_rsc_root);
    return false;
}

//----移动结点到某结点前面------------------------------------------------------
//功能: 移动一个结点到某结点前边成为兄结点,该结点本来在链表中
//参数: node,被移动的结点指针
//      lesser,目标结点,node移动到本结点前面