引言 - 導航欄目 有些朋友可能對 redis 充滿著數不盡的求知欲, 也許是 redis 屬於工作, 交流(面試)的大頭戲, 不得不 ... 而自己當下對於 redis 只是停留在會用層面, 細節層面幾乎沒有涉獵. 為了更快的融於大 家, 這裡嘗試拋磚引玉. 先帶大家手寫個 redis 中最簡單的 ...
引言 - 導航欄目
有些朋友可能對 redis 充滿著數不盡的求知欲, 也許是 redis 屬於工作, 交流(面試)的大頭戲,
不得不 ... 而自己當下對於 redis 只是停留在會用層面, 細節層面幾乎沒有涉獵. 為了更快的融於大
家, 這裡嘗試拋磚引玉. 先帶大家手寫個 redis 中最簡單的數據結構, adlist 雙向鏈表. 讓我們一
起對 redis 有個初步的認知. 本文會從下麵幾個標題展開解讀(吐槽), 歡迎交流和指正.
1. redis adlist 解析
2. redis config.h 分析
3. redis setproctitle.c 分析
4. redis atomicvar.h 分析
5. redis zmalloc 分析
6. redis Makefile 解析
redis 大頭是 C 寫的, 而 C 啥也不缺, 就缺手寫, OK 開始廢話手寫之旅吧 :)
前言 - redis adlist
全篇示例代碼都有手寫過, 不過為了素材正規, 這裡直接原封不動的引用
github.com/antirez/redis 中相關代碼.
1. redis adlist 解析
1 /* adlist.h - A generic doubly linked list implementation
2 *
3 * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of Redis nor the names of its contributors may be used
15 * to endorse or promote products derived from this software without
16 * specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #ifndef __ADLIST_H__
32 #define __ADLIST_H__
33
34 /* Node, List, and Iterator are the only data structures used currently. */
35
36 typedef struct listNode {
37 struct listNode *prev;
38 struct listNode *next;
39 void *value;
40 } listNode;
41
42 typedef struct listIter {
43 listNode *next;
44 int direction;
45 } listIter;
46
47 typedef struct list {
48 listNode *head;
49 listNode *tail;
50 void *(*dup)(void *ptr);
51 void (*free)(void *ptr);
52 int (*match)(void *ptr, void *key);
53 unsigned long len;
54 } list;
55
56 /* Functions implemented as macros */
57 #define listLength(l) ((l)->len)
58 #define listFirst(l) ((l)->head)
59 #define listLast(l) ((l)->tail)
60 #define listPrevNode(n) ((n)->prev)
61 #define listNextNode(n) ((n)->next)
62 #define listNodeValue(n) ((n)->value)
63
64 #define listSetDupMethod(l,m) ((l)->dup = (m))
65 #define listSetFreeMethod(l,m) ((l)->free = (m))
66 #define listSetMatchMethod(l,m) ((l)->match = (m))
67
68 #define listGetDupMethod(l) ((l)->dup)
69 #define listGetFreeMethod(l) ((l)->free)
70 #define listGetMatchMethod(l) ((l)->match)
71
72 /* Prototypes */
73 list *listCreate(void);
74 void listRelease(list *list);
75 void listEmpty(list *list);
76 list *listAddNodeHead(list *list, void *value);
77 list *listAddNodeTail(list *list, void *value);
78 list *listInsertNode(list *list, listNode *old_node, void *value, int after);
79 void listDelNode(list *list, listNode *node);
80 listIter *listGetIterator(list *list, int direction);
81 listNode *listNext(listIter *iter);
82 void listReleaseIterator(listIter *iter);
83 list *listDup(list *orig);
84 listNode *listSearchKey(list *list, void *key);
85 listNode *listIndex(list *list, long index);
86 void listRewind(list *list, listIter *li);
87 void listRewindTail(list *list, listIter *li);
88 void listRotate(list *list);
89 void listJoin(list *l, list *o);
90
91 /* Directions for iterators */
92 #define AL_START_HEAD 0
93 #define AL_START_TAIL 1
94
95 #endif /* __ADLIST_H__ */
首先手寫的是 adlist.h 雙向鏈表的頭文件, 對於這個頭文件有幾點要聊一聊的.
1.1' redis 中頭文件格式目前沒有統一
#ifndef __ADLIST_H__ #endif
#ifndef __REDIS_HELP_H #endif
#ifndef __ZMALLOC_H #endif
可能也是, redis 這個項目維護和開發都十年多了. 代碼風格在變(千奇百怪)也是正常.
這裡推薦第三種寫法 -> __{不帶尾碼文件名}_H
1.2' adlist.h 中函數命名隨意
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);
命名隨意不是個好習慣, 推薦參數名強區分. 例如下麵這樣固定格式
extern void listReleaseIterator(listIter * iter);
extern list * listDup(list * l);
extern listNode * listSearchKey(list * l, void * key);
extern listNode * listIndex(list * l, long index);
extern void listRewind(list * l, listIter * iter);
extern void listRewindTail(list * l, listIter * iter);
extern void listRotate(list * l);
extern void listJoin(list * l, list * o);
寫完 adlist.h 介面定義部分, 相信有些人對待實現的 adlist.c 也有了大致輪廓了吧 :)
1 /* adlist.c - A generic doubly linked list implementation
2 *
3 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of Redis nor the names of its contributors may be used
15 * to endorse or promote products derived from this software without
16 * specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
31
32 #include <stdlib.h>
33 #include "adlist.h"
34 #include "zmalloc.h"
35
36 /* Create a new list. The created list can be freed with
37 * AlFreeList(), but private value of every node need to be freed
38 * by the user before to call AlFreeList().
39 *
40 * On error, NULL is returned. Otherwise the pointer to the new list. */
41 list *listCreate(void)
42 {
43 struct list *list;
44
45 if ((list = zmalloc(sizeof(*list))) == NULL)
46 return NULL;
47 list->head = list->tail = NULL;
48 list->len = 0;
49 list->dup = NULL;
50 list->free = NULL;
51 list->match = NULL;
52 return list;
53 }
54
55 /* Remove all the elements from the list without destroying the list itself. */
56 void listEmpty(list *list)
57 {
58 unsigned long len;
59 listNode *current, *next;
60
61 current = list->head;
62 len = list->len;
63 while(len--) {
64 next = current->next;
65 if (list->free) list->free(current->value);
66 zfree(current);
67 current = next;
68 }
69 list->head = list->tail = NULL;
70 list->len = 0;
71 }
72
73 /* Free the whole list.
74 *
75 * This function can't fail. */
76 void listRelease(list *list)
77 {
78 listEmpty(list);
79 zfree(list);
80 }
81
82 /* Add a new node to the list, to head, containing the specified 'value'
83 * pointer as value.
84 *
85 * On error, NULL is returned and no operation is performed (i.e. the
86 * list remains unaltered).
87 * On success the 'list' pointer you pass to the function is returned. */
88 list *listAddNodeHead(list *list, void *value)
89 {
90 listNode *node;
91
92 if ((node = zmalloc(sizeof(*node))) == NULL)
93 return NULL;
94 node->value = value;
95 if (list->len == 0) {
96 list->head = list->tail = node;
97 node->prev = node->next = NULL;
98 } else {
99 node->prev = NULL;
100 node->next = list->head;
101 list->head->prev = node;
102 list->head = node;
103 }
104 list->len++;
105 return list;
106 }
107
108 /* Add a new node to the list, to tail, containing the specified 'value'
109 * pointer as value.
110 *
111 * On error, NULL is returned and no operation is performed (i.e. the
112 * list remains unaltered).
113 * On success the 'list' pointer you pass to the function is returned. */
114 list *listAddNodeTail(list *list, void *value)
115 {
116 listNode *node;
117
118 if ((node = zmalloc(sizeof(*node))) == NULL)
119 return NULL;
120 node->value = value;
121 if (list->len == 0) {
122 list->head = list->tail = node;
123 node->prev = node->next = NULL;
124 } else {
125 node->prev = list->tail;
126 node->next = NULL;
127 list->tail->next = node;
128 list->tail = node;
129 }
130 list->len++;
131 return list;
132 }
133
134 list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
135 listNode *node;
136
137 if ((node = zmalloc(sizeof(*node))) == NULL)
138 return NULL;
139 node->value = value;
140 if (after) {
141 node->prev = old_node;
142 node->next = old_node->next;
143 if (list->tail == old_node) {
144 list->tail = node;
145 }
146 } else {
147 node->next = old_node;
148 node->prev = old_node->prev;
149 if (list->head == old_node) {
150 list->head = node;
151 }
152 }
153 if (node->prev != NULL) {
154 node->prev->next = node;
155 }
156 if (node->next != NULL) {
157 node->next->prev = node;
158 }
159 list->len++;
160 return list;
161 }
162
163 /* Remove the specified node from the specified list.
164 * It's up to the caller to free the private value of the node.
165 *
166 * This function can't fail. */
167 void listDelNode(list *list, listNode *node)
168 {
169 if (node->prev)
170 node->prev->next = node->next;
171 else
172 list->head = node->next;
173 if (node->next)
174 node->next->prev = node->prev;
175 else
176 list->tail = node->prev;
177 if (list->free) list->free(node->value);
178 zfree(node);
179 list->len--;
180 }
181
182 /* Returns a list iterator 'iter'. After the initialization every
183 * call to listNext() will return the next element of the list.
184 *
185 * This function can't fail. */
186 listIter *listGetIterator(list *list, int direction)
187 {
188 listIter *iter;
189
190 if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
191 if (direction == AL_START_HEAD)
192 iter->next = list->head;
193 else
194 iter->next = list->tail;
195 iter->direction = direction;
196 return iter;
197 }
198
199 /* Release the iterator memory */
200 void listReleaseIterator(listIter *iter) {
201 zfree(iter);
202 }
203
204 /* Create an iterator in the list private iterator structure */
205 void listRewind(list *list, listIter *li) {
206 li->next = list->head;
207 li->direction = AL_START_HEAD;
208 }
209
210 void listRewindTail(list *list, listIter *li) {
211 li->next = list->tail;
212 li->direction = AL_START_TAIL;
213 }
214
215 /* Return the next element of an iterator.
216 * It's valid to remove the currently returned element using
217 * listDelNode(), but not to remove other elements.
218 *
219 * The function returns a pointer to the next element of the list,
220 * or NULL if there are no more elements, so the classical usage patter
221 * is:
222 *
223 * iter = listGetIterator(list,<direction>);
224 * while ((node = listNext(iter)) != NULL) {
225 * doSomethingWith(listNodeValue(node));
226 * }
227 *
228 * */
229 listNode *listNext(listIter *iter)
230 {
231 listNode *current = iter->next;
232
233 if (current != NULL) {
234 if (iter->direction == AL_START_HEAD)
235 iter->next = current->next;
236 else
237 iter->next = current->prev;
238 }
239 return current;
240 }
241
242 /* Duplicate the whole list. On out of memory NULL is returned.
243 * On success a copy of the original list is returned.
244 *
245 * The 'Dup' method set with listSetDupMethod() function is used
246 * to copy the node value. Otherwise the same pointer value of
247 * the original node is used as value of the copied node.
248 *
249 * The original list both on success or error is never modified. */
250 list *listDup(list *orig)
251 {
252 list *copy;
253 listIter iter;
254 listNode *node;
255
256 if ((copy = listCreate()) == NULL)
257 return NULL;
258 copy->dup = orig->dup;
259 copy->free = orig->free;
260 copy->match = orig->match;
261 listRewind(orig, &iter);
262 while((node = listNext(&iter)) != NULL) {
263 void *value;
264
265 if (copy->dup) {
266 value = copy->dup(node->value);
267 if (value == NULL) {
268 listRelease(copy);
269 return NULL;
270 }
271 } else
272 value = node->value;
273 if (listAddNodeTail(copy, value) == NULL) {
274 listRelease(copy);
275 return NULL;
276 }
277 }
278 return copy;
279 }
280
281 /* Search the list for a node matching a given key.
282 * The match is performed using the 'match' method
283 * set with listSetMatchMethod(). If no 'match' method
284 * is set, the 'value' pointer of every node is directly
285 * compared with the 'key' pointer.
286 *
287 * On success the first matching node pointer is returned
288 * (search starts from head). If no matching node exists
289 * NULL is returned. */
290 listNode *listSearchKey(list *list, void *key)
291 {
292 listIter iter;
293 listNode *node;
294
295 listRewind(list, &iter);
296 while((node = listNext(&iter)) != NULL) {
297 if (list->match) {
298 if (list->match(node->value, key)) {
299 return node;
300 }
301 } else {
302 if (key == node->value) {
303 return node;
304 }
305 }
306 }
307 return NULL;
308 }
309
310 /* Return the element at the specified zero-based index
311 * where 0 is the head, 1 is the element next to head
312 * and so on. Negative integers are used in order to count
313 * from the tail, -1 is the last element, -2 the penultimate
314 * and so on. If the index is out of range NULL is returned. */
315 listNode *listIndex(list *list, long index) {
316 listNode *n;
317
318 if (index < 0) {
319 index = (-index)-1;
320 n = list->tail;
321 while(index-- && n) n = n->prev;
322 } else {
323 n = list->head;
324 while(index-- && n) n = n->next;
325 }
326 return n;
327 }
328
329 /* Rotate the list removing the tail node and inserting it to the head. */
330 void listRotate(list *list) {
331 listNode *tail = list->tail;
332
333 if (listLength(list) <= 1) return;
334
335 /* Detach current tail */
336 list->tail = tail->prev;
337 list->tail->next = NULL;
338 /* Move it as head */
339 list->head->prev = tail;
340 tail->prev = NULL;
341 tail->next = list->head;
342 list->head = tail;
343 }
344
345 /* Add all the elements of the list 'o' at the end of the
346 * list 'l'. The list 'other' remains empty but otherwise valid. */
347 void listJoin(list *l, list *o) {
348 if (o->head)
349 o->head->prev = l->tail;
350
351 if (l->tail)
352 l->tail->next = o->head;
353 else
354 l->head = o->head;
355
356 if (o->tail) l->tail = o->tail;
357 l->len += o->len;
358
359 /* Setup other as an empty list. */
360 o->head = o->tail = NULL;
361 o->len = 0;
362 }
是的, 就是這樣, 就是這樣簡單.
我們稍微多講點, 其實對於 listCreate 可以寫的更加簡約, 不是嗎?
struct list * listCreate(void) {
return zcalloc(sizeof(struct list));
}
好了, 那我們繼續交流(吐槽)吧.
1.3' 代碼括弧 { } 位置隨意
這不是個好習慣, 畢竟誰也不喜歡兩面派. 大項目還是得需要在大方向上統一風格和約束.
1.4' struct listIter::direction 不一定是個很好的設計
direction 通過與 AL_START_HEAD or AL_START_TAIL 巨集進行運行時比對, 來區分遍歷的方向. 覺得
有點浪費. 內心更傾向於幹掉運行時比對, 從一開始用戶就應該知道該怎麼遍歷更好, 畢竟這是所有數據結構
的標桿.
❤ 恭喜大家, 到這我們關於 redis adlist 最基礎最簡單的數據結構已經手寫分析完畢, 後面可以不用看了.
謝謝大家捧場 ~
正文 - adlist 周邊
簡單愉快的背後總會有些更深的不可捉摸. 離開了奶頭樂, 我們將從 adlist.c 中一行代碼, 正式開啟
我們此次探險之旅.
#include "zmalloc.h"
2. redis config.h 分析
同樣在 zmallo.c 中我們發現瞭如下兩行代碼, 這就是我們要說的一個主體之一 config.h
#include "config.h"
#include "atomicvar.h"
config.h 主要作用是用於確定程式的運行環境, 例如是什麼操作系統, 是什麼位元組序, 要不要啟用某些功能
/*
* Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
*
