1 #ifndef __LIST_H__ 2 #define __LIST_H__ 3  4 typedef struct LIST LIST; 5 struct LIST 6 { 7   LIST *next; 8   LIST *prev; 9 };10 11 typedef struct LIST_HEAD12 {13   int count;14   LIST first;15 } LIST_HEAD;16 17 #define DO_LIST_INIT(name)     \18   { &(name),  &(name)}19 20 #define LIST_INIT(head)        \21   LIST head = DO_LIST_INIT(head)22 23 #define INIT_LIST(head)        \24   do { (head)->next = (head); (head)->prev = (head); } while (0)25 26 // list is first member of struct27 #define LIST_ITEM_PTR_CAST(list_ptr, item_type) ((item_type *)(list_ptr) )28 29 // list is not first member of struct30 #define LIST_ITEM_PTR(list_ptr, item_type, list_member) \31     ((item_type *)((char *)(list_ptr)-(unsigned int)(&((item_type *)0)->list_member)))32 33 LIST * list_get_prev(LIST *entry);34 LIST * list_get_next(LIST *entry);35 36 unsigned int list_is_empty(LIST *head);37 unsigned int list_is_empty_careful(LIST *head);38 unsigned int list_is_last(LIST *entry, LIST *head);39 40 void list_item_add(LIST_HEAD * head, LIST * item);41 void list_item_del(LIST_HEAD * head, LIST * item);42 43 void list_add_after_head(LIST *entry, LIST *head); // head entry ... tail44 void list_add_before_head(LIST *entry, LIST *head); // entry head ... tail45 46 void list_add_after(LIST *entry, LIST * where);47 void list_add_before(LIST *entry, LIST * where);48 49 void list_del_after_head(LIST *head);50 void list_del_before_head(LIST *head);51 void list_del(LIST *entry);52 53 void list_splice_after_head(LIST * list, LIST * head);54 void list_splice_before_head(LIST * list, LIST * head);55 56 void list_replace(LIST *old, LIST *new);57 58 void list_move_after_head(LIST *entry, LIST *head);59 void list_move_before_head(LIST *entry, LIST *head);60 61 void list_init(LIST *list); // INIT_LIST(list)62 63 #endif /* __LIST_H__ */

 

 

1 #include "list.h"  2   3 unsigned int list_is_empty(LIST *head)  4 {  5   return head->next == head;  6 }  7   8 unsigned int list_is_empty_careful(LIST *head)  9 { 10   LIST *next = head->next; 11   return ( next == head ) && ( next == head->prev ); 12 } 13  14 unsigned int list_is_last(LIST *entry, LIST *head) 15 { 16   return entry->next == head; 17 } 18  19 LIST * list_get_prev(LIST *entry) 20 { 21   return entry->prev; 22 } 23  24 LIST * list_get_next(LIST *entry) 25 { 26   return entry->next; 27 } 28  29 void __list_add(LIST *entry, LIST *prev, LIST *next) 30 { 31   next->prev = entry; 32   entry->next = next; 33   entry->prev = prev; 34   prev->next = entry; 35 } 36  37 // head entry ... tail 38 void list_add_after_head(LIST *entry, LIST *head) 39 { 40   __list_add( entry, head, head->next ); 41 } 42  43 // entry head ... tail 44 void list_add_before_head(LIST *entry, LIST *head) 45 { 46   __list_add( entry, head->prev, head ); 47 } 48  49 // ... where entry ... 50 void list_add_after(LIST *entry, LIST * where) 51 { 52   list_add_after_head( entry, where ); 53 } 54  55 // ... entry where ... 56 void list_add_before(LIST *entry, LIST * where) 57 { 58   list_add_before_head( entry, where ); 59 } 60  61 void __list_del(LIST *prev, LIST *next) 62 { 63   next->prev = prev; 64   prev->next = next; 65 } 66  67 // head [ **entry** ] ... tail 68 void list_del_after_head(LIST *head) 69 { 70   __list_del( head, head->next ); 71 } 72  73 // [ **entry** ] head ... tail 74 void list_del_before_head(LIST *head) 75 { 76   __list_del( head->prev, head ); 77 } 78  79 // ... [ **entry** ] ... 80 void list_del(LIST *entry) 81 { 82   __list_del( entry->prev, entry->next ); 83   INIT_LIST( entry ); 84 } 85  86 // prev : list->next list->prev : next 87 void __list_splice(const LIST *list, LIST *prev, LIST *next) 88 { 89   LIST *first = list->next; 90   LIST *last = list->prev; 91  92   first->prev = prev; 93   prev->next = first; 94  95   last->next = next; 96   next->prev = last; 97  98 } 99 100 // head list_tail ... list_head ... tail101 void list_splice_after_head(LIST * list, LIST * head)102 {103   if (!list_is_empty( list ))104   {105     __list_splice( list, head, head->next );106     INIT_LIST( list );107   }108 }109 110 // list_tail ... list_head --- head ... tail111 void list_splice_before_head(LIST * list, LIST * head)112 {113   if (!list_is_empty( list ))114   {115     __list_splice( list, head->prev, head );116     INIT_LIST( list );117   }118 }119 120 void list_replace(LIST *old, LIST *new)121 {122   new->next = old->next;123   new->next->prev = new;124   new->prev = old->prev;125   new->prev->next = new;126   INIT_LIST( old );127 }128 129 // head --- entry --- ... --- tail130 void list_move_after_head(LIST *entry, LIST *head)131 {132   __list_del( entry, head );133   list_add_after_head( entry, head );134 }135 136 // head --- ... --- tail --- entry137 void list_move_before_head(LIST *entry, LIST *head)138 {139   __list_del( entry, head );140   list_add_before_head( entry, head );141 }142 143 void list_init(LIST *list)144 {145   list->next = list;146   list->prev = list;147 }148 149 void list_item_add(LIST_HEAD * head, LIST * item)150 {151   // head --> 0 --> 1 --> 2 --> 3 --> head152   list_add_before_head( item, & ( head->first ) );153   head->count++;154 }155 156 void list_item_del(LIST_HEAD * head, LIST * item)157 {158   list_del( item );159   head->count--;160 }161 162 #define LIST_ITEM_COUNT ( 3 )163 void list_demo(void)164 {165   typedef struct ITEM166   {167     LIST list;168     int a;169   } ITEM;170 171   LIST_HEAD head;172   ITEM items [ LIST_ITEM_COUNT ];173 174   head.count = 0;175   INIT_LIST( &head.first );176 177   // head --> 0 --> 1 --> 2 --> 3 --> head178   for (unsigned int i = 0; i < LIST_ITEM_COUNT; i++)179   {180     list_item_add( &head, &items [ i ].list );181   }182 183   unsigned int i = 0;184   for (LIST * entry = head.first.next; entry != &head.first; entry =185     entry->next)186   {187     LIST_ITEM_PTR(entry, ITEM, list) ->a = i++;188     //LIST_ITEM_PTR_CAST(entry, ITEM) ->a = i++;189   }190 191   list_item_del( &head, &items [ LIST_ITEM_COUNT - 2 ].list );192   list_item_del( &head, &items [ LIST_ITEM_COUNT - 1 ].list );193   list_item_del( &head, &items [ 0 ].list );194 }