新项目启动，几个模块的数据结构一直没有想到比较科学的解决办法。分别是：软件定时器、节点网络管理、数据发送队列。
      多番查资料，看到了原子的ucos软件定时器的帖子，死活没看懂。遂决定扒开Ucos的代码好好瞅瞅。
      先解释一下软件定时器的结构【引用部分原子帖子内容】：

可参考【http://www.openedv.com/posts/list/15061.htm】

UCOSII中软件定时器的实现方法是，将定时器按定时时 间分组，使得每次时钟节拍到来时只对部分定时器进行比较操作，缩短了每次处理的时间。但这就需要动态地维护一个定时器组。定时器组的维护只是在每次定时器到时时才发生，而且定时器从组中移除和再插入操作不需要排序。这是一种比较高效的算法，减少了维护所需的操作时间。

【软件定时器数据结构】

1. //定时器基本结构
   
2. typedef  struct  os_tmr
   
3. {
   
4.     INT8U            OSTmrType;
   
5.     OS_TMR_CALLBACK  OSTmrCallback;
   
6.     void            *OSTmrCallbackArg;
   
7.     /*   */void            *OSTmrNext;/* Double link list pointers                                     */
   
8.     /*   */void            *OSTmrPrev;</b>
   
9.     INT32U           OSTmrMatch;
   
10.     INT32U           OSTmrDly;
    
11.     INT32U           OSTmrPeriod;
    
12. #if OS_TMR_CFG_NAME_EN > 0u
    
13.     INT8U           *OSTmrName;
    
14. #endif
    
15.     INT8U            OSTmrOpt;
    
16.     INT8U            OSTmrState;
    
17. } OS_TMR;
    
18. 
    
19. 
    
20. //定时器轮
    
21. typedef  struct  os_tmr_wheel
    
22. {
    
23.     /*   */OS_TMR          *OSTmrFirst;/* Pointer to first timer in linked list                         */
    
24.     INT16U           OSTmrEntries;</b>
    
25. } OS_TMR_WHEEL;

复制代码

       UCOSII软件定时器实现了3类链表的维护：

【三类链表实体数据】

1. /*   */OS_EXT  OS_TMR            OSTmrTbl[OS_TMR_CFG_MAX]; /* timer表-实体数据-用来被分配-不需要malloc                 */
   
2. /*   */OS_EXT  OS_TMR           *OSTmrFreeList;            /* 空闲时间块结构链表头                  */
   
3. /*   */OS_EXT  OS_TMR_WHEEL      OSTmrWheelTbl[OS_TMR_CFG_WHEEL_SIZE]; //timer 轮结构
   

复制代码

       【当前时间】

1. /*   */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）相比较。若相等(即到时)，则调用该定时器到时回调函数；若不相等，则判断该组中下一个定时器控制块。如此操作，直到该分组链表的结尾。软件定时器管理任务的流程如图所示。

软件定时器管理任务流程

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

1. /*   */OS_EXT OS_TMR OSTmrTbl[OS_TMR_CFG_MAX]; /* timer表-实体数据-用来被分配-不需要malloc */
   
2. /*   */OS_EXT OS_TMR *OSTmrFreeList; /* 空闲时间块结构链表头 */

复制代码

大家再联想上面的软件定时器的解释，这个地方是不需要malloc的。换句话说OSTmrTbl链表结构的实体数据。你要申请就去OSTmrTbl拿，用完了，就放到OSTmrFreeList里面。这个时候，如果你要申请一个节点，直接从OSTmrFreeList里面拿一个就行。

大家可能会再问，我用数组一样可以解决链表问题啊，干嘛要用链表。

这也是我今天写这篇帖子的目的，先说说楼主，楼主也排斥链表，因为这东西老是和malloc搞在一起，楼主胆子小，怕malloc不好使，而且链表和malloc搞在一起的时候代码尤其复杂而且难看。如果用上面的方法：

1、不用malloc

2、不用malloc

3、不用malloc

看看这个时候操作链表多方便，还特么是双向链表

1. static  OS_TMR  *OSTmr_Alloc         (void);
   
2. /*   */static  void     OSTmr_Free          (OS_TMR *ptmr);
   
3. /*   */static  void     OSTmr_InitTask      (void);
   
4. /*   */static  void     OSTmr_Link          (OS_TMR *ptmr, INT8U type);
   
5. /*   */static  void     OSTmr_Unlink        (OS_TMR *ptmr);</b>
   
6. static  void     OSTmr_Task          (void   *p_arg);

复制代码

      看完了也就这六个方法。（卧槽，好像是4个）

那链表适用于何处呢，讲个例子

楼主到现在没用过os，暂时也不想用os。但是发现有个东西特别好使，就是软件定时器。这玩意就是把一个（其实是很多个）counter和callbackFun放在定时器中断里面，counter减完了就执行回调函数(上面有ucos软件定时器的例子)。

如果我用数组，数据结构是这样的，是这样处理的。

1. 
   
2. typedef void (*callbackfun)(void);
   
3. typedef struct
   
4. {
   
5.       unsigend char flag;//空闲标志
   
6.       callbackfun*cbfunc;//回调
   
7.       unsigned int counter;//计数器
   
8. }timerObj;
   
9. static timerObj  usTimerObjTab[20]={0,NULL,0};//表
   
10. 
    
11. void initTimer(void){ memset(...) ;}
    
12. //初始化
    
13. void addtask(unsigned int counter ,callbackfun*cbfunc)
    
14. {
    
15.     for(int i=0;i<20;i++)
    
16.     {
    
17.         if(usTimerObjTab[i].flag==0)
    
18.         {
    
19.         //分配一个定时器
    
20.             usTimerObjTab[i].flag=1;
    
21.         }
    
22.     }
    
23. }
    
24. 
    
25. //我们还要把它放到定时器中断里轮询啊
    
26. 
    
27. void timerTaskPoll(void)
    
28. {
    
29.     for(int i=0;i<20;i++)
    
30.     {
    
31.         if(usTimerObjTab[i].flag=1)
    
32.         {
    
33.             if(usTimerObjTab[i].counter>0)//如果计数器不为0
    
34.             {
    
35.                 usTimerObjTab[i].counter--;//减减
    
36.             }
    
37.             else//计数器为0
    
38.             {
    
39.                 usTimerObjTab[i].cbfunc();//执行回调
    
40.                 usTimerObjTab[i].flag=0;//释放
    
41.             }
    
42.         }
    
43.     }
    
44. }
    

复制代码

咋一看觉得好像都差不多，那我们来简单比较一下用链表的情况（没有代码了,ucos有）

1、如果最大需要支持200个或者500个定时器的时候。

△  timerTaskPoll无法判断哪个是结尾，因为可能下面这这种情况（【一代表有效，|代表无效】）

    一 一 一 一 | 一 一 一 一 | 一 ....

原因很简单，你不知道哪个定时器长哪个短，所以必须轮询所有数据

△   如果498个是没用的，用了两个，这个时候，呵呵，我只想说，链表好使。

△   没有malloc

当然，其他和这个相类似的数据结构都可以使用这个方法，比如异步发送队列，比如zigbee节点管理等等（原谅楼主，楼主刚好要做这些，就只想到这些了）

最后，谢谢ucos作者的伟大，也谢谢原子的帖子 。

代码貌似不能加粗 <b>开头是加粗的代码，看的时候稍微费神一点了。对，我放成了/*   */开头

使劲顶一下

V3.0.4版本已经取消了OSTmrWheelTbl

高手，学习下