Redisのデュアルチェーンテーブル構造の詳細

Redisにおける二重チェーンテーブル実現の基本構造:1.ノード構造

typedef struct listNode {
  struct listNode *prev; //    
  struct listNode *next; //    
  void *value;       //     
} listNode;

2.双方向チェーン構造

typedef struct list {
  listNode *head;       //   
  listNode *tail;        //   
  void *(*dup)(void *ptr); //    
  void (*free)(void *ptr);  //    
  int (*match)(void *ptr, void *key); //    ，      
  unsigned long len;     //             
} list;

3.双方向チェーンテーブル遍歴器

typedef struct listIter {
  listNode *next;  //     
  int direction;
} listIter;

     

  #define AL_START_HEAD 0 //    
  #define AL_START_TAIL 1  //    

4.マクロ定義関数

#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

5.関数の定義

list *listCreate(void); //        。       AlFree（）    。

               //   AlFree（）                 。

               //        ，  null；               。


void listRelease(list *list); //      ，         。  zfree(list *list)  ,   Zmalloc.c 。


list *listAddNodeHead(list *list, void *value); //            


list *listAddNodeTail(list *list, void *value);  //           


list *listInsertNode(list *list, listNode *old_node, void *value, int after);//            after   


void listDelNode(list *list, listNode *node);//          ，             。

                              //         
listIter *listGetIterator(list *list, int direction);//          。

                                 //    listNext（）            。direction   

                                //         。


listNode *listNext(listIter *iter);        


void listReleaseIterator(listIter *iter);      //        。


list *listDup(list *orig);                //      。        null，             

                                //           ，       。


listNode *listSearchKey(list *list, void *key); //        key。               

                                //      ，   null。


listNode *listIndex(list *list, long index);   //   0  ，        0.1         。    。

                            //              。-1        ，-2       

                             //         ，   null


void listRewind(list *list, listIter *li) {
  li->next = list->head;
  li->direction = AL_START_HEAD;
}

void listRewindTail(list *list, listIter *li) {
  li->next = list->tail;
  li->direction = AL_START_TAIL;
}


void listRotate(list *list);         //    ，          。

List構造とlistNode構造のAPI listとlistNodeにはそれぞれ独自のファミリーAPIがあります.ここではredisのソースコードを勉強します(ps:次のコードはすべて私がredisに倣って直接コンパイルできるコードを書き換えます)
list *listCreate(void)

  /** 
   *         
   * 
   * T = O(1)                                                               
   */ 
  list *listCreate(void) 
  { 
    struct list *list; 
   
    //           
    list = (struct list *)malloc(sizeof(struct list)); 
    if (list == NULL) 
      return NULL; 
   
    //       
    list->head = list->tail = NULL; 
    list->len = 0; 
    list->dup = NULL; 
    list->free = NULL; 
    list->match = NULL; 
   
    return list; 
  } 

void listRelease(list *list)
 

  /** 
   *        
   * 
   * T = O(N), N      
   */ 
  void listRelease(list *list) 
  { 
    unsigned long len; 
    listNode *current, *next; 
   
    current = list->head; 
    len = list->len; 
   
    while (len --) { 
      next = current->next; 
      //         free  ，           
      if (list->free) list->free(current->value); 
      //        
      free(current); 
      current = next; 
    } 
    free(list); 
  }  

list *listAddNodeHead(list *list, void *value)

  /** 
   *         value   ，            
   * 
   * T = O(1)                                                               
   */ 
  list *listAddNodeHead(list *list, void *value) 
  { 
    listNode *node; 
   
    node = (listNode *)malloc(sizeof(listNode)); 
    if (node == NULL) 
      return NULL; 
   
    node->value = value; 
   
    if (list->len == 0) { 
      //       
      list->head = list->tail = node; 
      node->prev = node->next = NULL; 
    } else { 
      //         
      node->prev = NULL; 
      node->next = list->head; 
      list->head->prev = node; 
      list->head = node; 
    } 
   
    list->len ++; 
   
    return list; 
  } 

list *listAddNodeTail(list *list, void *value)

  /** 
   *         value   ，            
   * 
   * T = O(1) 
   */ 
  list *listAddNodeTail(list *list, void *value) 
  { 
    listNode *node; 
     
    node = (listNode *)malloc(sizeof(listNode)); 
    if (node == NULL) 
      return NULL; 
   
    if (list->len == 0) { 
      //       
      list->head = list->tail = node; 
      node->prev = node->next = NULL; 
    } else { 
      //        
      node->prev = list->tail; 
      node->next = NULL; 
      list->tail->next = node; 
      list->tail = node; 
    } 
   
    list->len ++; 
   
    return list; 
  } 

list *listInsertNode(list *list, listNode *old_node, void *value, int after)
 

  /** 
   *        value    
   *    after     ，       old_node        
   * 
   * T = O(1) 
   */ 
  list *listInsertNode(list *list, listNode *old_node, void *value, int after) 
  { 
    listNode *node; 
   
    node = (listNode *)malloc(sizeof(listNode)); 
    if (node == NULL) 
      return NULL; 
   
    if (after) { 
      //    old_node   
      node->prev = old_node; 
      node->next = old_node->next; 
      //        
      if (list->tail == old_node) { 
        list->tail = node; 
      } 
    } else { 
      //    old_node   
      node->next = old_node; 
      node->prev = old_node->prev; 
      //        
      if (list->head == old_node) { 
        list->head = node; 
      } 
    } 
   
    //               (       ，    ) 
    if (node->prev != NULL) { 
      node->prev->next = node; 
    } 
    if (node->next != NULL) { 
      node->next->prev = node; 
    } 
   
    //        
    list->len ++; 
   
    return list; 
  } 

void listDelNode(list *list, listNode *node)
  

 /** 
   *            
   * 
   * T = O(1) 
   */ 
  void listDelNode(list *list, listNode *node) 
  { 
    //          
    if (node->prev) { 
      node->prev->next = node->next; 
    } else { 
      list->head = node->next; 
    } 
   
    //        
    if (node->next) { 
      node->next->prev = node->prev; 
    } else { 
      list->tail = node->prev; 
    } 
   
    //       
    if (list->free) list->free(node->value); 
   
    //      
    free(node); 
   
    //          
    list->len --; 
  } 

反復器は実は私は反復器の概念に対してとてもよく知らないで、私が純粋なcプログラマーなため、c++ができなくて、ここは直接勉強しました!
Redisはリスト構造に対して反復器を実現し,チェーンテーブルを遍歴する.
反復器の構造は次のように定義されます.

  /** 
   *       
   */ 
  typedef struct listIter { 
    //      
    listNode *next; 
   
    //      
    int direction; 
  } listIter; 

Directionは、反復器がnextポインタに沿って後方に反復するか、prevポインタに沿って前方に反復するかを決定し、この値はadlist.h中のAL_START_HEAD定数またはAL_START_TAIL定数:

  #define AL_START_HEAD 0 
  #define AL_START_TAIL 1 

反復器のapi実装を学習します.
listIter *listGetIterator(list *list, int direction)

  /** 
   *     list      ，       direction   
   * 
   *       listNext(),              
   * 
   * T = O(1) 
   */ 
  listIter *listGetIterator(list *list, int direction) 
  { 
    listIter *iter; 
   
    iter = (listIter *)malloc(sizeof(listIter)); 
    if (iter == NULL) 
      return NULL; 
   
    //         ，                
    if (direction == AL_START_HEAD) { 
      iter->next = list->head; 
    } else { 
      iter->next = list->tail; 
    } 
   
    //      
    iter->direction = direction; 
   
    return iter; 
  } 

void listRewind(list *list, listIter *li)

  /** 
   *     iter       list    
   * 
   * T = O(1) 
   */ 
  void listRewind(list *list, listIter *li) 
  { 
    li->next = list->head; 
    li->direction = AL_START_HEAD; 
  } 

void listRewindTail(list *list, listIter *li)

  /** 
   *     iter       list    
   * 
   * T = O(1) 
   */ 
  void listRewindTail(list *list, listIter *li) 
  { 
    li->next = list->tail; 
    li->direction = AL_START_TAIL; 
  } 

listNode *listNext(listIter *iter)

  /** 
   *           ，    NULL，  ，      ： 
   * iter = listGetIterator(list, ); 
   * while ((node = listNext(iter)) != NULL) { 
   *   doSomethingWith(listNodeValue(node)); 
   * } 
   * 
   * T = O(1) 
   */ 
  listNode *listNext(listIter *iter) 
  { 
    listNode *current = iter->next; 
   
    if (current != NULL) { 
      //       ，     
      if (iter->direction == AL_START_HEAD) 
        iter->next = current->next; 
      else 
        iter->next = current->prev; 
    } 
   
    return current; 
  }