国产片侵犯亲女视频播放_亚洲精品二区_在线免费国产视频_欧美精品一区二区三区在线_少妇久久久_在线观看av不卡

服務器之家：專注于服務器技術及軟件下載分享
分類導航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|數據庫技術|

服務器之家 - 數據庫 - Redis - 詳解Redis中的雙鏈表結構

詳解Redis中的雙鏈表結構

2019-10-26 19:55zinss26914 Redis

這篇文章主要介紹了Redis中的雙鏈表結構,包括listNode結構的API,需要的朋友可以參考下

Redis中雙鏈表實現的基本結構：
1.節點結構

?
1
2
3
4
5
typedef struct listNode {
  struct listNode *prev; //前向節點
  struct listNode *next; //后向節點
  void *value;       //該節點的值
} listNode;

2.雙向鏈表結構

?
1
2
3
4
5
6
7
8
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.雙向鏈表遍歷器

?
1
2
3
4
5
6
7
8
9
typedef struct listIter {
  listNode *next;  //下一個節點
  int direction;
} listIter;
 
 方向定義
 
  #define AL_START_HEAD 0 //向前查找
  #define AL_START_TAIL 1  //向后查找

4.宏定義函數

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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.定義函數

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 創建一個新列表
 *
 * 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)

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 釋放整個列表
 *
 * 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)
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 新建一個包含給定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)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 新建一個包含給定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)

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 創建一個包含值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)

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
  * 釋放列表中給定的節點
  *
  * 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針對list結構實現了一個迭代器，用于對鏈表進行遍歷

迭代器的結構定義如下：

?
1
2
3
4
5
6
7
8
9
10
/**
 * 鏈表迭代器
 */
typedef struct listIter {
  // 下一節點
  listNode *next;
 
  // 迭代方向
  int direction;
} listIter;


direction決定了迭代器是沿著next指針向后迭代，還是沿著prev指針向前迭代，這個值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：

?
1
2
#define AL_START_HEAD 0
#define AL_START_TAIL 1


學習一下迭代器的api實現：

listIter *listGetIterator(list *list, int direction)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 創建列表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)

?
1
2
3
4
5
6
7
8
9
10
/**
 * 將迭代器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)

?
1
2
3
4
5
6
7
8
9
10
/**
 * 將迭代器iter的迭代指針倒回list的表尾
 *
 * T = O(1)
 */
void listRewindTail(list *list, listIter *li)
{
  li->next = list->tail;
  li->direction = AL_START_TAIL;
}


listNode *listNext(listIter *iter)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 函數要么返回當前節點，要么返回NULL，因此，常見的用法是：
 * iter = listGetIterator(list, <direction>);
 * 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;
}

延伸 · 閱讀

精彩推薦
  • Redisredis 交集、并集、差集的具體使用

    redis 交集、并集、差集的具體使用

    這篇文章主要介紹了redis 交集、并集、差集的具體使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友...

    xiaojin21cen10152021-07-27
  • RedisRedis全量復制與部分復制示例詳解

    Redis全量復制與部分復制示例詳解

    這篇文章主要給大家介紹了關于Redis全量復制與部分復制的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用Redis爬蟲具有一定的參考學習...

    豆子先生5052019-11-27
  • RedisRedis如何實現數據庫讀寫分離詳解

    Redis如何實現數據庫讀寫分離詳解

    Redis的主從架構，能幫助我們實現讀多，寫少的情況，下面這篇文章主要給大家介紹了關于Redis如何實現數據庫讀寫分離的相關資料，文中通過示例代碼介紹...

    羅兵漂流記6092019-11-11
  • RedisRedis的配置、啟動、操作和關閉方法

    Redis的配置、啟動、操作和關閉方法

    今天小編就為大家分享一篇Redis的配置、啟動、操作和關閉方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧 ...

    大道化簡5312019-11-14
  • Redisredis中如何使用lua腳本讓你的靈活性提高5個逼格詳解

    redis中如何使用lua腳本讓你的靈活性提高5個逼格詳解

    這篇文章主要給大家介紹了關于redis中如何使用lua腳本讓你的靈活性提高5個逼格的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具...

    一線碼農5812019-11-18
  • Redisredis實現排行榜功能

    redis實現排行榜功能

    排行榜在很多地方都能使用到，redis的zset可以很方便地用來實現排行榜功能，本文就來簡單的介紹一下如何使用，具有一定的參考價值，感興趣的小伙伴們...

    乘月歸5022021-08-05
  • Redis詳解Redis復制原理

    詳解Redis復制原理

    與大多數db一樣，Redis也提供了復制機制，以滿足故障恢復和負載均衡等需求。復制也是Redis高可用的基礎，哨兵和集群都是建立在復制基礎上實現高可用的...

    李留廣10222021-08-09
  • RedisRedis 事務知識點相關總結

    Redis 事務知識點相關總結

    這篇文章主要介紹了Redis 事務相關總結，幫助大家更好的理解和學習使用Redis，感興趣的朋友可以了解下...

    AsiaYe8232021-07-28
主站蜘蛛池模板： 久久久久在线 | 久久精品电影 | 欧美一级淫片007 | 精品国产乱码久久久久久影片 | 中文字幕av一区二区三区免费看 | 99视频在线 | 中文字幕亚洲二区 | 五月激情综合网 | 国产一区二区三区四区二区 | 欧美在线高清 | 亚洲成年人影院 | 久久久久久久久久久久国产精品 | 日韩欧美二区 | 成人在线一区二区 | 亚洲精品久久久久久久久久久久久 | 国产日韩欧美精品 | 免费观看一区二区三区毛片软件 | 久久精品综合 | 欧美一区二区三区电影 | 国产中文字幕一区 | 成人高清视频在线观看 | 天天爽天天干 | 黄版视频在线观看 | 午夜激情视频在线观看 | 播放欧美一级片 | 欧美日本韩国一区二区 | 少妇精品久久久久久久久久 | 成人免费一区二区三区视频网站 | 黄色小网站免费观看 | 欧美亚洲综合久久 | 一级片黄 | 久久九九免费 | 国产欧美日韩一区二区三区四区 | 国产精品久久精品 | 有码一区 | 亚洲三区在线观看 | 精品黑人一区二区三区久久 | 久久成人国产精品 | 亚洲九九| 日韩精品一 | 午夜寂寞少妇aaa片毛片 |