C语言实现的list

[cpp] view plain copy

1. #ifndef __WINE_SERVER_LIST_H  
2. #define __WINE_SERVER_LIST_H  
3.   
4. #include <stddef.h>  
5.   
6. struct list  
7. {  
8.     struct list *next;  
9.     struct list *prev;  
10. };  
11.   
12. /* add an element after the specified one */  
13. static inline void list_add_after( struct list *elem, struct list *to_add )  
14. {  
15.     to_add->next = elem->next;  
16.     to_add->prev = elem;  
17.     elem->next->prev = to_add;  
18.     elem->next = to_add;  
19. }  
20.   
21. /* add an element before the specified one */  
22. static inline void list_add_before( struct list *elem, struct list *to_add )  
23. {  
24.     to_add->next = elem;  
25.     to_add->prev = elem->prev;  
26.     elem->prev->next = to_add;  
27.     elem->prev = to_add;  
28. }  
29.   
30. /* add element at the head of the list */  
31. static inline void list_add_head( struct list *list, struct list *elem )  
32. {  
33.     list_add_after( list, elem );  
34. }  
35.   
36. /* add element at the tail of the list */  
37. static inline void list_add_tail( struct list *list, struct list *elem )  
38. {  
39.     list_add_before( list, elem );  
40. }  
41.   
42. /* remove an element from its list */  
43. static inline void list_remove( struct list *elem )  
44. {  
45.     elem->next->prev = elem->prev;  
46.     elem->prev->next = elem->next;  
47. }  
48.   
49. /* get the next element */  
50. static inline struct list *list_next( const struct list *list, const struct list *elem )  
51. {  
52.     struct list *ret = elem->next;  
53.     if (elem->next == list) ret = NULL;  
54.     return ret;  
55. }  
56.   
57. /* get the previous element */  
58. static inline struct list *list_prev( const struct list *list, const struct list *elem )  
59. {  
60.     struct list *ret = elem->prev;  
61.     if (elem->prev == list) ret = NULL;  
62.     return ret;  
63. }  
64.   
65. /* get the first element */  
66. static inline struct list *list_head( const struct list *list )  
67. {  
68.     return list_next( list, list );  
69. }  
70.   
71. /* get the last element */  
72. static inline struct list *list_tail( const struct list *list )  
73. {  
74.     return list_prev( list, list );  
75. }  
76.   
77. /* check if a list is empty */  
78. static inline int list_empty( const struct list *list )  
79. {  
80.     return list->next == list;  
81. }  
82.   
83. /* initialize a list */  
84. static inline void list_init( struct list *list )  
85. {  
86.     list->next = list->prev = list;  
87. }  
88.   
89. /* count the elements of a list */  
90. static inline unsigned int list_count( const struct list *list )  
91. {  
92.     unsigned count = 0;  
93.     const struct list *ptr;  
94.     for (ptr = list->next; ptr != list; ptr = ptr->next) count++;  
95.     return count;  
96. }  
97.   
98. /* move all elements from src to the tail of dst */  
99. static inline void list_move_tail( struct list *dst, struct list *src )  
100. {  
101.     if (list_empty(src)) return;  
102.   
103.     dst->prev->next = src->next;  
104.     src->next->prev = dst->prev;  
105.     dst->prev = src->prev;  
106.     src->prev->next = dst;  
107.     list_init(src);  
108. }  
109.   
110. /* move all elements from src to the head of dst */  
111. static inline void list_move_head( struct list *dst, struct list *src )  
112. {  
113.     if (list_empty(src)) return;  
114.   
115.     dst->next->prev = src->prev;  
116.     src->prev->next = dst->next;  
117.     dst->next = src->next;  
118.     src->next->prev = dst;  
119.     list_init(src);  
120. }  
121.   
122. /* iterate through the list */  
123. #define LIST_FOR_EACH(cursor,list) \  
124.     for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next)  
125.   
126. /* iterate through the list, with safety against removal */  
127. #define LIST_FOR_EACH_SAFE(cursor, cursor2, list) \  
128.     for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \  
129.          (cursor) != (list); \  
130.          (cursor) = (cursor2), (cursor2) = (cursor)->next)  
131.   
132. /* iterate through the list using a list entry */  
133. #define LIST_FOR_EACH_ENTRY(elem, list, type, field) \  
134.     for ((elem) = LIST_ENTRY((list)->next, type, field); \  
135.          &(elem)->field != (list); \  
136.          (elem) = LIST_ENTRY((elem)->field.next, type, field))  
137.   
138. /* iterate through the list using a list entry, with safety against removal */  
139. #define LIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field) \  
140.     for ((cursor) = LIST_ENTRY((list)->next, type, field), \  
141.          (cursor2) = LIST_ENTRY((cursor)->field.next, type, field); \  
142.          &(cursor)->field != (list); \  
143.          (cursor) = (cursor2), \  
144.          (cursor2) = LIST_ENTRY((cursor)->field.next, type, field))  
145.   
146. /* iterate through the list in reverse order */  
147. #define LIST_FOR_EACH_REV(cursor,list) \  
148.     for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev)  
149.   
150. /* iterate through the list in reverse order, with safety against removal */  
151. #define LIST_FOR_EACH_SAFE_REV(cursor, cursor2, list) \  
152.     for ((cursor) = (list)->prev, (cursor2) = (cursor)->prev; \  
153.          (cursor) != (list); \  
154.          (cursor) = (cursor2), (cursor2) = (cursor)->prev)  
155.   
156. /* iterate through the list in reverse order using a list entry */  
157. #define LIST_FOR_EACH_ENTRY_REV(elem, list, type, field) \  
158.     for ((elem) = LIST_ENTRY((list)->prev, type, field); \  
159.          &(elem)->field != (list); \  
160.          (elem) = LIST_ENTRY((elem)->field.prev, type, field))  
161.   
162. /* iterate through the list in reverse order using a list entry, with safety against removal */  
163. #define LIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field) \  
164.     for ((cursor) = LIST_ENTRY((list)->prev, type, field), \  
165.          (cursor2) = LIST_ENTRY((cursor)->field.prev, type, field); \  
166.          &(cursor)->field != (list); \  
167.          (cursor) = (cursor2), \  
168.          (cursor2) = LIST_ENTRY((cursor)->field.prev, type, field))  
169.   
170. /* macros for statically initialized lists */  
171. #undef LIST_INIT  
172. #define LIST_INIT(list)  { &(list), &(list) }  
173.   
174. /* get pointer to object containing list element */  
175. #undef LIST_ENTRY  
176. #define LIST_ENTRY(elem, type, field) \  
177.     ((type *)((char *)(elem) - offsetof(type, field)))  
178.   
179. #endif  /* __WINE_SERVER_LIST_H */  

用法简介：

[cpp] view plain copy

1. /* Define a list like so: 
2.  * 
3.  *   struct gadget 
4.  *   { 
5.  *       struct list  entry;   <-- doesn't have to be the first item in the struct 
6.  *       int          a, b; 
7.  *   }; 
8.  * 
9.  *   static struct list global_gadgets = LIST_INIT( global_gadgets ); 
10.  * 
11.  * or 
12.  * 
13.  *   struct some_global_thing 
14.  *   { 
15.  *       struct list gadgets; 
16.  *   }; 
17.  * 
18.  *   list_init( &some_global_thing->gadgets ); 
19.  * 
20.  * Manipulate it like this: 
21.  * 
22.  *   list_add_head( &global_gadgets, &new_gadget->entry ); 
23.  *   list_remove( &new_gadget->entry ); 
24.  *   list_add_after( &some_random_gadget->entry, &new_gadget->entry ); 
25.  * 
26.  * And to iterate over it: 
27.  * 
28.  *   struct gadget *gadget; 
29.  *   LIST_FOR_EACH_ENTRY( gadget, &global_gadgets, struct gadget, entry ) 
30.  *   { 
31.  *       ... 
32.  *   } 
33.  * 
34.  */