redis下的adlist

2216609207

1 //adlist.h
2 #ifndef __ADLIST__H__
3 #define __ADLIST__H__
4
5 typedef struct listNode_ {
6   struct listNode_ *prev;
7   struct listNode_ *next;
8   void *value;
9 } listNode;
10
11 typedef struct listIter_ {
12   listNode *next;
13   int      direction;
14 }listIter;
15
16 typedef struct List_ {
17   listNode *head;
18   listNode *tail;
19   void *(*dup)(void *ptr);
20   void (*free)(void *ptr);
21   int (*match)(void *ptr, void *key);
22   unsigned long len;
23 }List;
24
25 class ListM {
26   public:
27     enum {
28       AL_START_HEAD = 0,
29       AL_START_TAIL = 1,
30       AL_START_ERR  
31     };  
32
33     static List *ListCreate(void);
34     static void ListRelease(List *list);
35     
36     static List *ListAddNodeHead(List *list, void *value);
37     static List *ListAddNodeTail(List *list, void *value);
38     static List *ListInsertNode(List *list,
39                                 listNode *old_node,
40                                 void *value,
41                                 int after);
42         
43     static void ListDelNode(List *list, listNode *node);
44
45     static listIter *ListGetIterator(List *list, int direction);
46     static listNode *ListNext(listIter *iter);
47     static void ListReleaseIterator(listIter *iter);
48
49     static List *ListDup(List *orig);
50     static listNode *ListSearchKey(List *list, void *key);
51     static listNode *ListIndex(List *list, long index);
52
53     static void ListRewind(List *list, listIter *li);
54     static void ListRewindTail(List *list, listIter *li);
55     static void ListRotate(List *list);
56
57     static void Traversal(List *list);
58 };
59
60 #endif //__ADLIST__H__
　　
　　



  1 //adlist.cpp
  2 #include
  3 #include
  4 #include "adlist.h"
  5 #include "zmalloc.h"
  6
  7 List* ListM::ListCreate(void) {
  8    List *list;
  9    if((list = (List *)zmalloc(sizeof(List))) == NULL)
10      return NULL;
11
12    list->head = list->tail = NULL;
13    list->len = 0;
14    list->dup = NULL;
15    list->free = NULL;
16    list->match = NULL;
17    return list;
18 }
19
20 void ListM::ListRelease(List *list) {
21   unsigned long len = 0;
22   listNode *current, *next;
23
24   current = list->head;
25   len = list->len;
26   while(len--) {
27     next = current->next;
28     if(list->free) list->free(current->value);
29     zfree(current);
30     current = next;
31   }
32   zfree(list);
33 }
34
35 List *ListM::ListAddNodeHead(List *list, void *value) {
36   
37   listNode *node;
38
39   if((node = (listNode *)zmalloc(sizeof(*node))) == NULL) {
40     return NULL;
41   }
42   node->value = value;
43
44   if(list->len == 0) {
45     list->head = list->tail = node;
46     node->prev = node->next = NULL;
47   } else {
48     node->prev = NULL;
49     node->next = list->head;
50     list->head->prev = node;
51     list->head = node;
52   }
53   list->len++;
54
55   return list;
56 }
57
58 List *ListM::ListAddNodeTail(List *list, void *value) {
59
60   listNode *node;
61
62   if((node = (listNode *)zmalloc(sizeof(*node))) == NULL) {
63     return NULL;
64   }
65
66   node->value = value;
67   if(list->len == 0) {
68     list->head = list->tail = node;
69     node->prev = node->next = NULL;
70   } else {
71     node->prev = list->tail;
72     node->next = NULL;
73     list->tail->next = node;
74     list->tail = node;
75   }
76   list->len++;
77
78   return list;
79 }
80
81 List *ListM::ListInsertNode(List *list, listNode *old_node, void *value,int after) {
82    listNode *node;
83
84    if((node = (listNode *)zmalloc(sizeof(*node))) == NULL) {
85      return NULL;
86    }
87
88    node->value = value;
89    if(after) {
90     node->prev = old_node;
91     node->next = old_node->next;
92     if(list->tail == old_node) {
93       list->tail = node;
94     }
95    } else {
96     node->next = old_node;
97     node->prev = old_node->prev;
98     if(list->head == old_node) {
99       list->head = node;
100     }
101    }
102
103    if(node->prev != NULL) {
104     node->prev->next = node;
105    }
106
107    if(node->next != NULL) {
108     node->next->prev = node;
109    }
110    list->len++;
111
112    return list;
113 }
114
115
116 void ListM::ListDelNode(List *list, listNode *node) {
117   if(node->prev)
118     node->prev->next =  node->next;
119   else
120     list->head = node->next;
121
122   if(node->next)
123     node->next->prev = node->prev;
124   else
125     list->tail = node->prev;
126
127   if(list->free) list->free(node->value);
128   zfree(node);
129   list->len--;
130 }
131
132 listIter *ListM::ListGetIterator(List *list, int direction) {
133
134   listIter *iter;
135
136   if((iter = (listIter *)zmalloc(sizeof(*iter))) == NULL) return NULL;
137
138   if(direction == AL_START_HEAD)
139     iter->next = list->head;
140   else
141     iter->next = list->tail;
142   iter->direction = direction;
143
144   return iter;
145 }
146
147 listNode *ListM::ListNext(listIter *iter) {
148   listNode *current = iter->next;
149
150   if(current != NULL) {
151     if(iter->direction == AL_START_HEAD)
152       iter->next = current->next;
153     else
154       iter->next = current->prev;
155   }
156   return current;
157 }
158
159 void ListM::ListReleaseIterator(listIter *iter) {
160   zfree(iter);
161 }
162
163 listNode *ListM::ListSearchKey(List *list, void *key) {
164   listNode *node = NULL;
165   listIter *iter = NULL;
166
167   iter = ListGetIterator(list, AL_START_HEAD);
168   while((node = ListNext(iter)) !=  NULL) {
169     if(list->match) {
170       if(list->match(node->value, key)) {
171         ListReleaseIterator(iter);
172         return node;
173       }
174     } else {
175       if(key == node->value) {
176         ListReleaseIterator(iter);
177         return node;
178       }
179     }
180   }
181
182   ListReleaseIterator(iter);
183   return NULL;
184 }
185
186 listNode *ListM::ListIndex(List *list, long index) {
187   listNode *node = NULL;
188
189   if(index < 0 ) {
190     index = (-index) - 1;
191     node = list->tail;
192     while(index-- && node) node = node->prev;
193   } else {
194     node = list->head;
195     while(index-- && node) node = node->next;
196   }
197   return node;
198 }
199
200 void ListM::ListRewind(List *list, listIter *li) {
201   li->next = list->head;
202   li->direction = AL_START_HEAD;
203 }
204
205 void ListM::ListRewindTail(List *list, listIter *li) {
206   li->next = list->tail;
207   li->direction = AL_START_TAIL;
208 }
209
210 void ListM::ListRotate(List *list) {
211   listNode *tail = list->tail;
212
213   if(list->len tail = tail->prev;
216   list->tail->next = NULL;
217
218   list->head->prev = tail;
219   tail->prev = NULL;
220   tail->next = list->head;
221   list->head = tail;
222 }
223
224 void ListM::Traversal(List *list) {
225   if(list->head == list->tail ) return;
226
227   listNode *node = NULL;
228   listIter *iter = ListGetIterator(list, AL_START_HEAD);
229   std::cout