尾队列代码中的TAILQ_LAST怎么理解


尾队列实现中:
https://opensource.conformal.com/viewgit/?a=viewblob&p=adsuck&h=38130e0815288ca16ed277669e967c1327f6f7c6&f=linux/queue.h

TAILQ_LAST和TAILQ_PREV怎么理解?

   
  #define TAILQ_LAST(head, headname)                  \
  
(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

对TAILQ_LAST来说, (head)->tqh_last是最后一个元素的tqe_next指针的地址. 实在没看出为何能得到 队列最后一个元素的指针的.

c 数据结构

weichen 11 years, 1 month ago

自问自答吧.

http://blog.sina.com.cn/s/blog_603e7371010120ck.html

---引用---
"TAILQ_LAST的作用是计算出队列最后一个元素的地址,它的实现就有点难懂了,用到了TAILQ_ENTRY和TAILQ_HEAD内存布局一样的知识点:

   
  #define TAILQ_LAST(head,headname)  \
  
(*(((struct headname *)((head)->tqh_last))->tqh_last))


队列中的tqh_last字段的值是队列最后一个元素的tqe_next的地址,不是最后一个元素的地址。怎么计算出最后一个元素的地址呢?(struct headname *)(head)->tqh_last获得最后一个元素的tqe_next的地址,并强制转换成队列指针类型,再对其用->tqh_last就相当于获得了最后一个元素的tqe_prev地址(因为TAILQ_ENTRY和TAILQ_HEAD内存布局一样),然后解引用就得到了最后一个元素的地址。很巧妙!"

---引用结束---

补充一下:

   
  #define TAILQ_ENTRY(type)             \
  
struct { \
struct type *tqe_next; \
struct type **tqe_prev; \

}
#define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; \
struct type **tqh_last; \
}

其实这里我理解, 因为 TAILQ_ENTRY定义出来的结构 是没有名字的; 所以只好利用内存布局结构一样的 而又有名字的 TAILQ_HEAD 结构来做一个转换.

缝隙妖怪的式神 answered 11 years, 1 month ago

Your Answer