打印
[应用相关]

核心常用数据结构-【双向链表】

[复制链接]
757|2
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
Micachl|  楼主 | 2016-4-27 21:24 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
UCOSII中软件定时器的实现方法是,将定时器按定时时 间分组,使得每次时钟节拍到来时只对部分定时器进行比较操作,缩短了每次处理的时间。但这就需要动态地维护一个定时器组。定时器组的维护只是在每次定时器到时时才发生,而且定时器从组中移除和再插入操作不需要排序。这是一种比较高效的算法,减少了维护所需的操作时间。
【软件定时器数据结构】
//定时器基本结构
typedef  struct  os_tmr
{
    INT8U            OSTmrType;
    OS_TMR_CALLBACK  OSTmrCallback;
    void            *OSTmrCallbackArg;
    /*   */void            *OSTmrNext;/* Double link list pointers                                     */
    /*   */void            *OSTmrPrev;</b>
    INT32U           OSTmrMatch;
    INT32U           OSTmrDly;
    INT32U           OSTmrPeriod;
#if OS_TMR_CFG_NAME_EN > 0u
    INT8U           *OSTmrName;
#endif
    INT8U            OSTmrOpt;
    INT8U            OSTmrState;
} OS_TMR;


//定时器轮
typedef  struct  os_tmr_wheel
{
    /*   */OS_TMR          *OSTmrFirst;/* Pointer to first timer in linked list                         */
    INT16U           OSTmrEntries;</b>
} OS_TMR_WHEEL;
UCOSII软件定时器实现了3类链表的维护:
【三类链表实体数据】
/*   */OS_EXT  OS_TMR            OSTmrTbl[OS_TMR_CFG_MAX]; /* timer表-实体数据-用来被分配-不需要malloc                 */
/*   */OS_EXT  OS_TMR           *OSTmrFreeList;            /* 空闲时间块结构链表头                  */
/*   */OS_EXT  OS_TMR_WHEEL      OSTmrWheelTbl[OS_TMR_CFG_WHEEL_SIZE]; //timer 轮结构


沙发
Micachl|  楼主 | 2016-4-27 21:24 | 只看该作者
【当前时间】
/*   */OS_EXT  INT32U            OSTmrTime;                /* Current timer time                              */</b>

其中OS_TMR为定时器控制块,定时器控制块是软件定时器管理的基本单元,包含软件定时器的名称、定时时间、在链表中的位置、使用状态、使用方式,以及到时回调函数及其参数等基本信息。
OSTmrTbl[OS_TMR_CFG_MAX]:以数组的形式静态分配定时器控制块所需的RAM空间,并存储所有已建立的定时器控制块,OS_TMR_CFG_MAX为最大软件定时器的个数。
OSTmrFreeLiSt:为空闲定时器控制块链表头指针。空闲态的定时器控制块(OS_TMR)中,OSTmrnext和OSTmrPrev两个指针分别指向空闲控制块的前一个和后一个,组织了空闲控制块双向链表。建立定时器时,从这个链表中搜索空闲定时器控制块。
OSTmrWheelTbl[OS_TMR_CFG_WHEEL_SIZE]:该数组的每个元素都是已开启定时器的一个分组,元素中记录了指向该分组中第一个定时器控制块的指针,以及定时器控制块的个数。运行态的定时器控制块(OS_TMR)中,OSTmrnext和OSTmrPrev两个指针同样也组织了所在分组中定时器控制块的双向链表。软件定时器管理所需的数据结构示意图如图所示:

OS_TMR_CFG_WHEEL_SIZE定义了OSTmrWheelTbl的大小,同时这个值也是定时器分组的依据。按照定时器到时值与OS_TMR_CFG_WHEEL_SIZE相除的余数进行分组:不同余数的定时器放在不同分组中;相同余数的定时器处在同一组中,由双向链表连接。这样,余数值为0~OS_TMR_CFG_WHEEL_SIZE-1的不同定时器控制块,正好分别对应了数组元素OSTmr-WheelTbl[0]~OSTmrWheelTbl[OS_TMR_CFGWHEEL_SIZE-1]的不同分组。每次时钟节拍到来时,时钟数OSTmrTime值加1,然后也进行求余操作,只有余数相同的那组定时器才有可能到时,所以只对该组定时器进行判断。这种方法比循环判断所有定时器更高效。随着时钟数的累加,处理的分组也由0~OS_TMR_CFG_WHE EL_SIZE-1循环。这里,我们推荐OS_TMR_CFG_WHEEL_SIZE的取值为2的N次方,以便采用移位操作计算余数,缩短处理时间。
信号量唤醒定时器管理任务,计算出当前所要处理的分组后,程序遍历该分组中的所有控制块,将当前OSTmrTime值与定时器控制块中的到时值(OSTmrMatch)相比较。若相等(即到时),则调用该定时器到时回调函数;若不相等,则判断该组中下一个定时器控制块。如此操作,直到该分组链表的结尾。软件定时器管理任务的流程如图所示。
QQ图片20160405193319_看图王.jpg (39.15 KB, 下载次数: 0)
下载附件
软件定时器管理任务流程
2016-4-5 19:34 上传



看到这里,大家肯定会问,楼主你扯了ucos的软件定时器出来,和你的题目{核心常用数据结构-【双向链表】}有啥关系。其实,整片内容讲的核心就在下面这两个定义的变量。

使用特权

评论回复
板凳
Micachl|  楼主 | 2016-4-27 21:26 | 只看该作者
/*   */OS_EXT OS_TMR OSTmrTbl[OS_TMR_CFG_MAX]; /* timer表-实体数据-用来被分配-不需要malloc */
/*   */OS_EXT OS_TMR *OSTmrFreeList; /* 空闲时间块结构链表头 */

大家再联想上面的软件定时器的解释,这个地方是不需要malloc的。换句话说OSTmrTbl链表结构的实体数据。你要申请就去OSTmrTbl拿,用完了,就放到OSTmrFreeList里面。这个时候,如果你要申请一个节点,直接从OSTmrFreeList里面拿一个就行。
大家可能会再问,我用数组一样可以解决链表问题啊,干嘛要用链表。
这也是我今天写这篇帖子的目的,先说说楼主,楼主也排斥链表,因为这东西老是和malloc搞在一起,楼主胆子小,怕malloc不好使,而且链表和malloc搞在一起的时候代码尤其复杂而且难看。如果用上面的方法:
1、不用malloc
2、不用malloc
3、不用malloc
看看这个时候操作链表多方便,还特么是双向链表
static  OS_TMR  *OSTmr_Alloc         (void);
/*   */static  void     OSTmr_Free          (OS_TMR *ptmr);
/*   */static  void     OSTmr_InitTask      (void);
/*   */static  void     OSTmr_Link          (OS_TMR *ptmr, INT8U type);
/*   */static  void     OSTmr_Unlink        (OS_TMR *ptmr);</b>
static  void     OSTmr_Task          (void   *p_arg);
看完了也就这六个方法。(卧槽,好像是4个)

那链表适用于何处呢,讲个例子
楼主到现在没用过os,暂时也不想用os。但是发现有个东西特别好使,就是软件定时器。这玩意就是把一个(其实是很多个)counter和callbackFun放在定时器中断里面,counter减完了就执行回调函数(上面有ucos软件定时器的例子)。
如果我用数组,数据结构是这样的,是这样处理的。

typedef void (*callbackfun)(void);
typedef struct
{
      unsigend char flag;//空闲标志
      callbackfun*cbfunc;//回调
      unsigned int counter;//计数器
}timerObj;
static timerObj  usTimerObjTab[20]={0,NULL,0};//表

void initTimer(void){ memset(...) ;}
//初始化
void addtask(unsigned int counter ,callbackfun*cbfunc)
{
    for(int i=0;i<20;i++)
    {
        if(usTimerObjTab[i].flag==0)
        {
        //分配一个定时器
            usTimerObjTab[i].flag=1;
        }
    }
}

//我们还要把它放到定时器中断里轮询啊

void timerTaskPoll(void)
{
    for(int i=0;i<20;i++)
    {
        if(usTimerObjTab[i].flag=1)
        {
            if(usTimerObjTab[i].counter>0)//如果计数器不为0
            {
                usTimerObjTab[i].counter--;//减减
            }
            else//计数器为0
            {
                usTimerObjTab[i].cbfunc();//执行回调
                usTimerObjTab[i].flag=0;//释放
            }
        }
    }
}

咋一看觉得好像都差不多,那我们来简单比较一下用链表的情况(没有代码了,ucos有)
1、如果最大需要支持200个或者500个定时器的时候。
△  timerTaskPoll无法判断哪个是结尾,因为可能下面这这种情况(【一代表有效,|代表无效】)
    一 一 一 一 | 一 一 一 一 | 一 ....
原因很简单,你不知道哪个定时器长哪个短,所以必须轮询所有数据
△   如果498个是没用的,用了两个,这个时候,呵呵,我只想说,链表好使。
△   没有malloc
当然,其他和这个相类似的数据结构都可以使用这个方法,比如异步发送队列,比如zigbee节点管理等等(原谅楼主,楼主刚好要做这些,就只想到这些了)
最后,谢谢ucos作者的伟大,也谢谢原子的帖子 。

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

43

主题

300

帖子

1

粉丝