? ? ? ??adlist是redis實現(xiàn)的雙端鏈表，這個雙端鏈表和數(shù)據(jù)結構中的雙鏈表類似。雙端鏈表list有一個指向鏈表和一個指向鏈表尾的指針，list還包括一些函數(shù)指針。

如：void *(*dup)(void *ptr);? ? ? ? ? dup是一個函數(shù)指針，它指向的這個函數(shù)返回值是void *，參數(shù)是void *ptr

adlist.h

/* adlist.h - A generic doubly linked list implementation** Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>* All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions are met:** * Redistributions of source code must retain the above copyright notice,* this list of conditions and the following disclaimer.* * Redistributions in binary form must reproduce the above copyright* notice, this list of conditions and the following disclaimer in the* documentation and/or other materials provided with the distribution.* * Neither the name of Redis nor the names of its contributors may be used* to endorse or promote products derived from this software without* specific prior written permission.** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE* POSSIBILITY OF SUCH DAMAGE.*/#ifndef __ADLIST_H__ #define __ADLIST_H__//雙端鏈表實現(xiàn):有一個指向表頭的節(jié)點，有一個指向表尾的節(jié)點/* Node, List, and Iterator are the only data structures used currently. */typedef struct listNode { //雙端鏈表節(jié)點struct listNode *prev; // 前置節(jié)點struct listNode *next; // 后置節(jié)點void *value; // 節(jié)點的值 } listNode;typedef struct listIter { //雙端鏈表迭代器listNode *next; // 當前迭代到的節(jié)點int direction; // 迭代的方向 } listIter;typedef struct list { //雙端鏈表結構listNode *head; // 表頭節(jié)點listNode *tail; // 表尾節(jié)點void *(*dup)(void *ptr); // 節(jié)點值復制函數(shù)void (*free)(void *ptr); // 節(jié)點值釋放函數(shù)int (*match)(void *ptr, void *key); // 節(jié)點值對比函數(shù)unsigned long len; // 鏈表所包含的節(jié)點數(shù)量 } list; /* Functions implemented as macros */ #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)/* Prototypes */ list *listCreate(void); void listRelease(list *list); void listEmpty(list *list); list *listAddNodeHead(list *list, void *value); list *listAddNodeTail(list *list, void *value); list *listInsertNode(list *list, listNode *old_node, void *value, int after); void listDelNode(list *list, listNode *node); listIter *listGetIterator(list *list, int direction); listNode *listNext(listIter *iter); 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);/* Directions for iterators */ #define AL_START_HEAD 0 #define AL_START_TAIL 1#endif /* __ADLIST_H__ */

adlist.c

/* adlist.c - A generic doubly linked list implementation** Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>* All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions are met:** * Redistributions of source code must retain the above copyright notice,* this list of conditions and the following disclaimer.* * Redistributions in binary form must reproduce the above copyright* notice, this list of conditions and the following disclaimer in the* documentation and/or other materials provided with the distribution.* * Neither the name of Redis nor the names of its contributors may be used* to endorse or promote products derived from this software without* specific prior written permission.** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE* POSSIBILITY OF SUCH DAMAGE.*/#include <stdlib.h> #include "adlist.h" #include "zmalloc.h"/* Create a new list. The created list can be freed with* AlFreeList(), but private value of every node need to be freed* by the user before to call AlFreeList().** On error, NULL is returned. Otherwise the pointer to the new list. */ list *listCreate(void) //創(chuàng)建一個新的鏈表 {struct list *list;if ((list = zmalloc(sizeof(*list))) == NULL)return NULL;list->head = list->tail = NULL;list->len = 0;list->dup = NULL;list->free = NULL;list->match = NULL;return list; }/* Remove all the elements from the list without destroying the list itself. */ void listEmpty(list *list) {unsigned long len;listNode *current, *next;current = list->head;//表頭節(jié)點 len = list->len;while(len--) {next = current->next;if (list->free) list->free(current->value); //釋放節(jié)點對應的值zfree(current); //釋放節(jié)點current = next;}list->head = list->tail = NULL;list->len = 0; }/* Free the whole list.** This function can't fail. */ void listRelease(list *list) {listEmpty(list);zfree(list); }/* Add a new node to the list, to head, containing the specified 'value'* pointer as value.** On error, NULL is returned and no operation is performed (i.e. the* list remains unaltered).* On success the 'list' pointer you pass to the function is returned. */ list *listAddNodeHead(list *list, void *value) //頭部增加 {listNode *node;if ((node = zmalloc(sizeof(*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; }/* Add a new node to the list, to tail, containing the specified 'value'* pointer as value.** On error, NULL is returned and no operation is performed (i.e. the* list remains unaltered).* On success the 'list' pointer you pass to the function is returned. */ list *listAddNodeTail(list *list, void *value) {listNode *node;if ((node = zmalloc(sizeof(*node))) == NULL)return NULL;node->value = value;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; }/*創(chuàng)建一個包含值value的新節(jié)點，并將它插入到old_node的之前或之后 如果after為 0 ，將新節(jié)點插入到old_node之前。 如果after為 1 ，將新節(jié)點插入到old_node之后*/ list *listInsertNode(list *list, listNode *old_node, void *value, int after) {listNode *node;if ((node = zmalloc(sizeof(*node))) == NULL)return NULL;node->value = value;if (after) { //節(jié)點插入到old_node之前node->prev = old_node;node->next = old_node->next;if (list->tail == old_node) {list->tail = node;}} else { //新節(jié)點插入到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; }/* Remove the specified node from the specified list.* It's up to the caller to free the private value of the node.** This function can't fail. */ void listDelNode(list *list, listNode *node) {if (node->prev)node->prev->next = node->next;elselist->head = node->next;if (node->next)node->next->prev = node->prev;elselist->tail = node->prev;if (list->free) list->free(node->value);zfree(node);list->len--; }/* Returns a list iterator 'iter'. After the initialization every* call to listNext() will return the next element of the list.** This function can't fail. */ //為給定鏈表創(chuàng)建一個迭代器，之后每次對這個迭代器調用 listNext 都返回被迭代到的鏈表節(jié)點 listIter *listGetIterator(list *list, int direction)//direction 參數(shù)決定了迭代器的迭代方向 {listIter *iter;if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;if (direction == AL_START_HEAD)iter->next = list->head;elseiter->next = list->tail;iter->direction = direction;return iter; }/* Release the iterator memory */ void listReleaseIterator(listIter *iter) {zfree(iter); }/* Create an iterator in the list private iterator structure */ 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; }/* Return the next element of an iterator.* It's valid to remove the currently returned element using* listDelNode(), but not to remove other elements.** The function returns a pointer to the next element of the list,* or NULL if there are no more elements, so the classical usage patter* is:** iter = listGetIterator(list,<direction>);* while ((node = listNext(iter)) != NULL) {* doSomethingWith(listNodeValue(node));* }* */ listNode *listNext(listIter *iter)//返回迭代器當前所指向的節(jié)點 {listNode *current = iter->next;if (current != NULL) {if (iter->direction == AL_START_HEAD)iter->next = current->next;elseiter->next = current->prev;}return current; }/* Duplicate the whole list. On out of memory NULL is returned.* On success a copy of the original list is returned.** The 'Dup' method set with listSetDupMethod() function is used* to copy the node value. Otherwise the same pointer value of* the original node is used as value of the copied node.** The original list both on success or error is never modified. */ list *listDup(list *orig) //復制整個鏈表 {list *copy;listIter iter;listNode *node;if ((copy = listCreate()) == NULL) //創(chuàng)建一個新的鏈表return NULL;copy->dup = orig->dup;copy->free = orig->free;copy->match = orig->match;listRewind(orig, &iter); //使iter指向list->headwhile((node = listNext(&iter)) != NULL) {void *value;if (copy->dup) {value = copy->dup(node->value);if (value == NULL) {listRelease(copy);return NULL;}} elsevalue = node->value;if (listAddNodeTail(copy, value) == NULL) {listRelease(copy);return NULL;}}return copy; }/* Search the list for a node matching a given key.* The match is performed using the 'match' method* set with listSetMatchMethod(). If no 'match' method* is set, the 'value' pointer of every node is directly* compared with the 'key' pointer.** On success the first matching node pointer is returned* (search starts from head). If no matching node exists* NULL is returned. */ listNode *listSearchKey(list *list, void *key)//查找鏈表 list 中值和 key 匹配的節(jié)點 {listIter iter;listNode *node;listRewind(list, &iter);while((node = listNext(&iter)) != NULL) {if (list->match) {if (list->match(node->value, key)) {return node;}} else {if (key == node->value) {return node;}}}return NULL; }/* Return the element at the specified zero-based index* where 0 is the head, 1 is the element next to head* and so on. Negative integers are used in order to count* from the tail, -1 is the last element, -2 the penultimate* and so on. If the index is out of range NULL is returned. */ listNode *listIndex(list *list, long index) {//返回鏈表在給定索引上的值;-1是最后一個元素，-2是倒數(shù)第二個listNode *n;if (index < 0) {index = (-index)-1;n = list->tail;while(index-- && n) n = n->prev;} else {n = list->head;while(index-- && n) n = n->next;}return n; }/* Rotate the list removing the tail node and inserting it to the head. */ void listRotate(list *list) { /*旋轉列表，刪除尾節(jié)點并將其插入到頭部*/listNode *tail = list->tail;if (listLength(list) <= 1) return;/* Detach current tail */list->tail = tail->prev;list->tail->next = NULL;/* Move it as head */list->head->prev = tail;tail->prev = NULL;tail->next = list->head;list->head = tail; }/* Add all the elements of the list 'o' at the end of the* list 'l'. The list 'other' remains empty but otherwise valid. */ void listJoin(list *l, list *o) { //將 o 連到 l 后面，然后釋放 oif (o->head)o->head->prev = l->tail;if (l->tail)l->tail->next = o->head;elsel->head = o->head;if (o->tail) l->tail = o->tail;l->len += o->len;/* Setup other as an empty list. */o->head = o->tail = NULL;o->len = 0; }

?

總結

以上是生活随笔為你收集整理的redis之adlist.c的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。