双向循环链表的实现

• 目标

  • 使用Linux内核链表实现KylinLib中的双向循环链表
  • template<typename T>class DualCircleList;

  

• KylinLib中双向循环链表的设计思路

  数据结点之间在逻辑上构成双向循环链表，头结点仅用于结点的定位。

  

• 实现思路

  • 通过模板定义DualCircleList类，继承自DualLinkList类
  • 在DualCircleList内部使用Linux内核链表进行实现
  • 使用struct list_head定义DualCircleList的头结点
  • 特殊处理：循环遍历时忽略头结点

• 实现要点

  • 通过list_head进行目标结点定位( position(i) )
  • 通过list_entry将list_head指针转换为目标结点指针
  • 通过list_for_each实现int find(const T &e)函数
  • 遍历函数中的next()和pre()需要考虑跳过头结点

编程实验

• 基于Linux内核链表的双向循环链表

  #ifndef DUALCIRCULARLIST_H
  #define DUALCIRCULARLIST_H
  
  #include "DualLinkedList.h"
  #include "LinuxList.h"
  
  namespace KylinLib {
  template< typename T>
  class DualCircularList : public DualLinkedList<T>{
  public:
      DualCircularList(){
          INIT_LIST_HEAD(&m_header);
      }
  
      bool insert(size_t index,const T &value){
          auto node = new Node();
          index = index%(this->m_size+1);
          if(node!=nullptr){
              node->value = value;
              list_add_tail(&node->head,position(index)->next);
              this->m_size++;
          } else {
              THROW_EXCEPTION(NoEnoughMemoryException,"No momery to insert new element...");
          }
          return true;
      }
  
      bool append(const T &value){
          return insert(this->m_size,value);
      }
  
      bool remove(size_t index){
          index = mod(index);
          auto toDel = position(index)->next;
          if(m_current==toDel)m_current=toDel->next;
          list_del(toDel);
          this->m_size--;
          delete list_entry(toDel,Node,head);
          return true;
      }
  
      virtual bool set(size_t index,const T &value) {
          index = mod(index);
          list_entry(position(index)->next,Node,head)->value = value;
          return true;
      }
  
      virtual bool get(size_t index,T &value) const {
          index = mod(index);
          value = list_entry(position(index)->next,Node,head)->value;
          return true;
      }
  
      virtual const T& at(size_t index) const {
          index = mod(index);
          return list_entry(position(index)->next,Node,head)->value;
      }
  
      virtual int find(const T &value) const {
          int ret = -1;
          int i = 0;
          list_head *slider = nullptr;
          list_for_each(slider,&m_header){
              if(list_entry(slider,Node,head)->value == value){
                  ret = i;
                  break;
              }
              i++;
          }
          return ret;
      }
  
      void clear(){
          while (this->m_size>0) {
              remove(0);
          }
      }
  
      bool begin(size_t index,size_t step = 1){
          index = mod(index);
          m_current = position(index)->next;
          this->m_step = step;
          return true;
      }
  
      bool end(){
          return (m_current==nullptr)||(this->m_size==0);
      }
  
      T& current(){
          if(!end())
              return list_entry(m_current,Node,head)->value;
          else {
              THROW_EXCEPTION(InvalidOperationException,"No value at current position...");
          }
      }
  
      bool next(){
          size_t i = 0;
          while ((i<this->m_step)&&!end()) {
              if(m_current!=&m_header){
                  m_current = m_current->next;
                  i++;
              } else {
                  m_current=m_current->next;
              }
          }
          if(m_current==&m_header)
              m_current = m_current->next;
          return (i==this->m_step);
      }
  
      bool prev(){
          size_t i = 0;
          while ((i<this->m_step)&&!end()) {
              if(m_current!=&m_header){
                  m_current = m_current->prev;
                  i++;
              } else {
                  m_current=m_current->prev;
              }
          }
          if(m_current==&m_header)
              m_current = m_current->prev;
          return (i==this->m_step);
      }
  
      ~DualCircularList(){
          clear();
      }
  protected:
      list_head* position(size_t index)const{
          auto ret = const_cast<list_head*>(&m_header);
          for (size_t i=0;i<index;i++) {
              ret = ret->next;
          }
          return ret;
      }
  
      size_t mod(size_t index) const{
          return (this->m_size==0)?0:(index%this->m_size);
      }
  
      struct Node : public Object{
          list_head head;
          T value;
      };
      list_head m_header;
      list_head *m_current = nullptr;
  };
  }
  #endif // DUALCIRCULARLIST_H
  

小结

• Linux内核链表是带头结点的双向循环链表
• DualCircleList使用Linux内核链表进行内部实现
• DualCircleList在循环遍历时需要跳过头结点
• 将list_head指针转换为目标结点指针时，使用list_entry宏

思考题

• 下面代码中的pn1和pn2是否相等？为什么？

  struct Node : public Object{
      list_head head;
      T value;
  };
  
  Node node;
  list_head *ld = &node.head;
  Node *pn1 = reinterpret_cast<Node*>(ld);
  Node *pn2 = list_entry(ld,Node,head);