双向链表~~ 代码比较容易懂，小弟只是做了简单的注释，没啥特别的，不多说了，上代码~~
Adlist.h
1 #ifndef __ADLIST_H__ 2 #define __ADLIST_H__ 3 4 /* Node, List, and Iterator are the only data structures used currently. */ 5 6 typedef struct listNode { 7 struct listNode *prev; 8 struct listNode *next; 9 void *value;10 } listNode;11 12 typedef struct listIter {13 listNode *next;14 int direction;15 } listIter;16 17 typedef struct list {18 listNode *head;19 listNode *tail;20 void *(*dup)(void *ptr);21 void (*free)(void *ptr);22 int (*match)(void *ptr, void *key);23 unsigned int len;24 } list;25 26 /* Functions implemented as macros */27 #define listLength(l) ((l)->len)28 #define listFirst(l) ((l)->head)29 #define listLast(l) ((l)->tail)30 #define listPrevNode(n) ((n)->prev)31 #define listNextNode(n) ((n)->next)32 #define listNodeValue(n) ((n)->value)33 34 #define listSetDupMethod(l,m) ((l)->dup = (m))35 #define listSetFreeMethod(l,m) ((l)->free = (m))36 #define listSetMatchMethod(l,m) ((l)->match = (m))37 38 #define listGetDupMethod(l) ((l)->dup)39 #define listGetFree(l) ((l)->free)40 #define listGetMatchMethod(l) ((l)->match)41 42 /* Prototypes */43 list *listCreate(void);44 void listRelease(list *list);45 list *listAddNodeHead(list *list, void *value);46 list *listAddNodeTail(list *list, void *value);47 list *listInsertNode(list *list, listNode *old_node, void *value, int after);48 void listDelNode(list *list, listNode *node);49 listIter *listGetIterator(list *list, int direction);50 listNode *listNext(listIter *iter);51 void listReleaseIterator(listIter *iter);52 list *listDup(list *orig);53 listNode *listSearchKey(list *list, void *key);54 listNode *listIndex(list *list, int index);55 void listRewind(list *list, listIter *li);56 void listRewindTail(list *list, listIter *li);57 58 /* Directions for iterators */59 #define AL_START_HEAD 060 #define AL_START_TAIL 161 62 #endif /* __ADLIST_H__ */
Adlist.c
1 #include2 #include "adlist.h" 3 #include "zmalloc.h" 4 5 /* Create a new list. The created list can be freed with 6 * AlFreeList(), but private value of every node need to be freed 7 * by the user before to call AlFreeList(). 8 * 9 * On error, NULL is returned. Otherwise the pointer to the new list. */ 10 11 //创建一个新的list，返回list指针 12 //如果创建失败，返回NULL指针 13 list *listCreate(void) 14 { 15 struct list *list; 16 17 if ((list = zmalloc(sizeof(*list))) == NULL) 18 return NULL; 19 list->head = list->tail = NULL; 20 list->len = 0; 21 list->dup = NULL; 22 list->free = NULL; 23 list->match = NULL; 24 return list; 25 } 26 27 /* Free the whole list. 28 * 29 * This function can't fail. */ 30 //释放列表 31 void listRelease(list *list) 32 { 33 unsigned int len; 34 listNode *current, *next; 35 36 current = list->head; 37 len = list->len; 38 while(len--) { 39 next = current->next; 40 if (list->free) list->free(current->value); 41 zfree(current); 42 current = next; 43 } 44 zfree(list); 45 } 46 47 //在list头部添加一个新节点，并返回新的list指针 48 //如果失败，返回NULL【申请内存失败】 49 /* Add a new node to the list, to head, contaning the specified 'value' 50 * pointer as value. 51 * 52 * On error, NULL is returned and no operation is performed (i.e. the 53 * list remains unaltered). 54 * On success the 'list' pointer you pass to the function is returned. */ 55 list *listAddNodeHead(list *list, void *value) 56 { 57 listNode *node; 58 59 if ((node = zmalloc(sizeof(*node))) == NULL) 60 return NULL; 61 node->value = value; 62 if (list->len == 0) { 63 list->head = list->tail = node; 64 node->prev = node->next = NULL; 65 } else { 66 node->prev = NULL; 67 node->next = list->head; 68 list->head->prev = node; 69 list->head = node; 70 } 71 list->len++; 72 return list; 73 } 74 75 76 //在list尾部增加添加node，返回list指针 77 /* Add a new node to the list, to tail, contaning the specified 'value' 78 * pointer as value. 79 * 80 * On error, NULL is returned and no operation is performed (i.e. the 81 * list remains unaltered). 82 * On success the 'list' pointer you pass to the function is returned. */ 83 list *listAddNodeTail(list *list, void *value) 84 { 85 listNode *node; 86 87 if ((node = zmalloc(sizeof(*node))) == NULL) 88 return NULL; 89 node->value = value; 90 if (list->len == 0) { 91 list->head = list->tail = node; 92 node->prev = node->next = NULL; 93 } else { 94 node->prev = list->tail; 95 node->next = NULL; 96 list->tail->next = node; 97 list->tail = node; 98 } 99 list->len++;100 return list;101 }102 103 //在list中插入一个新节点，如果after为非零，插在old_node后，否则，插在old_node之前104 list *listInsertNode(list *list, listNode *old_node, void *value, int after) {105 listNode *node;106 107 if ((node = zmalloc(sizeof(*node))) == NULL)108 return NULL;109 node->value = value;110 if (after) {111 node->prev = old_node;112 node->next = old_node->next;113 if (list->tail == old_node) {114 list->tail = node;115 }116 } else {117 node->next = old_node;118 node->prev = old_node->prev;119 if (list->head == old_node) {120 list->head = node;121 }122 }123 if (node->prev != NULL) {124 node->prev->next = node;125 }126 if (node->next != NULL) {127 node->next->prev = node;128 }129 list->len++;130 return list;131 }132 133 //删除某节点134 /* Remove the specified node from the specified list.135 * It's up to the caller to free the private value of the node.136 *137 * This function can't fail. */138 void listDelNode(list *list, listNode *node)139 {140 if (node->prev)141 node->prev->next = node->next;142 else143 list->head = node->next;144 if (node->next)145 node->next->prev = node->prev;146 else147 list->tail = node->prev;148 if (list->free) list->free(node->value);149 zfree(node);150 list->len--;151 }152 153 //得到一个listIter，用来遍历列表list用154 /* Returns a list iterator 'iter'. After the initialization every155 * call to listNext() will return the next element of the list.156 *157 * This function can't fail. */158 listIter *listGetIterator(list *list, int direction)159 {160 listIter *iter;161 162 if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;163 if (direction == AL_START_HEAD)164 iter->next = list->head;165 else166 iter->next = list->tail;167 iter->direction = direction;168 return iter;169 }170 171 //释放listIter172 /* Release the iterator memory */173 void listReleaseIterator(listIter *iter) {174 zfree(iter);175 }176 177 //把一个listIter强制搞成指向头指针的iter178 /* Create an iterator in the list private iterator structure */179 void listRewind(list *list, listIter *li) {180 li->next = list->head;181 li->direction = AL_START_HEAD;182 }183 184 //把一个listIter强制搞成指向尾指针的iter185 void listRewindTail(list *list, listIter *li) {186 li->next = list->tail;187 li->direction = AL_START_TAIL;188 }189 190 /* Return the next element of an iterator.191 * It's valid to remove the currently returned element using192 * listDelNode(), but not to remove other elements.193 *194 * The function returns a pointer to the next element of the list,195 * or NULL if there are no more elements, so the classical usage patter196 * is:197 *198 * iter = listGetIterator(list, );199 * while ((node = listNext(iter)) != NULL) {200 * doSomethingWith(listNodeValue(node));201 * }202 *203 * */204 //得到iter的下一个iter205 listNode *listNext(listIter *iter)206 {207 listNode *current = iter->next;208 209 if (current != NULL) {210 if (iter->direction == AL_START_HEAD)211 iter->next = current->next;212 else213 iter->next = current->prev;214 }215 return current;216 }217 /* Duplicate the whole list. On out of memory NULL is returned.218 * On success a copy of the original list is returned.219 *220 * The 'Dup' method set with listSetDupMethod() function is used221 * to copy the node value. Otherwise the same pointer value of222 * the original node is used as value of the copied node.223 *224 * The original list both on success or error is never modified. */225 //复制整个list，并返回新list的指针，如果dup失败，返回NULL226 //227 list *listDup(list *orig)228 {229 list *copy;230 listIter *iter;231 listNode *node;232 233 if ((copy = listCreate()) == NULL)234 return NULL;235 copy->dup = orig->dup;236 copy->free = orig->free;237 copy->match = orig->match;238 iter = listGetIterator(orig, AL_START_HEAD);239 while((node = listNext(iter)) != NULL) {240 void *value;241 //如果预定义了copy函数【clone?】则使用其来复制value242 if (copy->dup) {243 value = copy->dup(node->value);244 //如果复制失败【一般是内存alloc失败】245 if (value == NULL) {246 listRelease(copy);247 listReleaseIterator(iter);248 return NULL;249 }250 } else251 value = node->value;252 if (listAddNodeTail(copy, value) == NULL) {253 listRelease(copy);254 listReleaseIterator(iter);255 return NULL;256 }257 }258 listReleaseIterator(iter);259 return copy;260 }261 262 /* Search the list for a node matching a given key.263 * The match is performed using the 'match' method264 * set with listSetMatchMethod(). If no 'match' method265 * is set, the 'value' pointer of every node is directly266 * compared with the 'key' pointer.267 *268 * On success the first matching node pointer is returned269 * (search starts from head). If no matching node exists270 * NULL is returned. */271 //在list中查找*key指针指向的value272 listNode *listSearchKey(list *list, void *key)273 {274 listIter *iter;275 listNode *node;276 277 iter = listGetIterator(list, AL_START_HEAD);278 while((node = listNext(iter)) != NULL) {279 //如果自定义了match方法，则使用自定义match方法280 if (list->match) {281 if (list->match(node->value, key)) {282 listReleaseIterator(iter);283 return node;284 }285 } else {286 if (key == node->value) {287 listReleaseIterator(iter);288 return node;289 }290 }291 }292 listReleaseIterator(iter);293 return NULL;294 }295 296 /* Return the element at the specified zero-based index297 * where 0 is the head, 1 is the element next to head298 * and so on. Negative integers are used in order to count299 * from the tail, -1 is the last element, -2 the penultimante300 * and so on. If the index is out of range NULL is returned. */301 //找到第index个元素，如果没找到，返回NULL【如果index为什么没有和list->len 做一次比较呢?】302 listNode *listIndex(list *list, int index) {303 listNode *n;304 305 if (index < 0) {306 index = (-index)-1;307 n = list->tail;308 while(index-- && n) n = n->prev;309 } else {310 n = list->head;311 while(index-- && n) n = n->next;312 }313 return n;314 }