dRonin  adbada4
dRonin firmware
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
utlist.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2007-2009, Troy D. Hanson
3 All rights reserved.
4 
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7 
8  * Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 
11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 */
23 
24 #ifndef UTLIST_H
25 #define UTLIST_H
26 
27 #define UTLIST_VERSION 1.8
28 
29 /*
30  * This file contains macros to manipulate singly and doubly-linked lists.
31  *
32  * 1. LL_ macros: singly-linked lists.
33  * 2. DL_ macros: doubly-linked lists.
34  * 3. CDL_ macros: circular doubly-linked lists.
35  *
36  * To use singly-linked lists, your structure must have a "next" pointer.
37  * To use doubly-linked lists, your structure must "prev" and "next" pointers.
38  * Either way, the pointer to the head of the list must be initialized to NULL.
39  *
40  * ----------------.EXAMPLE -------------------------
41  * struct item {
42  * int id;
43  * struct item *prev, *next;
44  * }
45  *
46  * struct item *list = NULL:
47  *
48  * int main() {
49  * struct item *item;
50  * ... allocate and populate item ...
51  * DL_APPEND(list, item);
52  * }
53  * --------------------------------------------------
54  *
55  * For doubly-linked lists, the append and delete macros are O(1)
56  * For singly-linked lists, append and delete are O(n) but prepend is O(1)
57  * The sort macro is O(n log(n)) for all types of single/double/circular lists.
58  */
59 
60 /******************************************************************************
61  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
62  * Unwieldy variable names used here to avoid shadowing passed-in variables. *
63  *****************************************************************************/
64 #define LL_SORT(list, cmp) \
65 do { \
66  __typeof__(list) _ls_p, _ls_q, _ls_e, _ls_tail, _ls_oldhead; \
67  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
68  if (list) { \
69  _ls_insize = 1; \
70  _ls_looping = 1; \
71  while (_ls_looping) { \
72  _ls_p = list; \
73  _ls_oldhead = list; \
74  list = NULL; \
75  _ls_tail = NULL; \
76  _ls_nmerges = 0; \
77  while (_ls_p) { \
78  _ls_nmerges++; \
79  _ls_q = _ls_p; \
80  _ls_psize = 0; \
81  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
82  _ls_psize++; \
83  _ls_q = _ls_q->next; \
84  if (!_ls_q) break; \
85  } \
86  _ls_qsize = _ls_insize; \
87  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
88  if (_ls_psize == 0) { \
89  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
90  } else if (_ls_qsize == 0 || !_ls_q) { \
91  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
92  } else if (cmp(_ls_p,_ls_q) <= 0) { \
93  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
94  } else { \
95  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
96  } \
97  if (_ls_tail) { \
98  _ls_tail->next = _ls_e; \
99  } else { \
100  list = _ls_e; \
101  } \
102  _ls_tail = _ls_e; \
103  } \
104  _ls_p = _ls_q; \
105  } \
106  _ls_tail->next = NULL; \
107  if (_ls_nmerges <= 1) { \
108  _ls_looping=0; \
109  } \
110  _ls_insize *= 2; \
111  } \
112  } \
113 } while (0)
114 
115 #define DL_SORT(list, cmp) \
116 do { \
117  __typeof__(list) _ls_p, _ls_q, _ls_e, _ls_tail, _ls_oldhead; \
118  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
119  if (list) { \
120  _ls_insize = 1; \
121  _ls_looping = 1; \
122  while (_ls_looping) { \
123  _ls_p = list; \
124  _ls_oldhead = list; \
125  list = NULL; \
126  _ls_tail = NULL; \
127  _ls_nmerges = 0; \
128  while (_ls_p) { \
129  _ls_nmerges++; \
130  _ls_q = _ls_p; \
131  _ls_psize = 0; \
132  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
133  _ls_psize++; \
134  _ls_q = _ls_q->next; \
135  if (!_ls_q) break; \
136  } \
137  _ls_qsize = _ls_insize; \
138  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
139  if (_ls_psize == 0) { \
140  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
141  } else if (_ls_qsize == 0 || !_ls_q) { \
142  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
143  } else if (cmp(_ls_p,_ls_q) <= 0) { \
144  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
145  } else { \
146  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
147  } \
148  if (_ls_tail) { \
149  _ls_tail->next = _ls_e; \
150  } else { \
151  list = _ls_e; \
152  } \
153  _ls_e->prev = _ls_tail; \
154  _ls_tail = _ls_e; \
155  } \
156  _ls_p = _ls_q; \
157  } \
158  list->prev = _ls_tail; \
159  _ls_tail->next = NULL; \
160  if (_ls_nmerges <= 1) { \
161  _ls_looping=0; \
162  } \
163  _ls_insize *= 2; \
164  } \
165  } \
166 } while (0)
167 
168 #define CDL_SORT(list, cmp) \
169 do { \
170  __typeof__(list) _ls_p, _ls_q, _ls_e, _ls_tail, _ls_oldhead; \
171  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
172  if (list) { \
173  _ls_insize = 1; \
174  _ls_looping = 1; \
175  while (_ls_looping) { \
176  _ls_p = list; \
177  _ls_oldhead = list; \
178  list = NULL; \
179  _ls_tail = NULL; \
180  _ls_nmerges = 0; \
181  while (_ls_p) { \
182  _ls_nmerges++; \
183  _ls_q = _ls_p; \
184  _ls_psize = 0; \
185  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
186  _ls_psize++; \
187  _ls_q = ((_ls_q->next == _ls_oldhead) ? NULL : _ls_q->next); \
188  if (!_ls_q) break; \
189  } \
190  _ls_qsize = _ls_insize; \
191  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
192  if (_ls_psize == 0) { \
193  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
194  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
195  } else if (_ls_qsize == 0 || !_ls_q) { \
196  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
197  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
198  } else if (cmp(_ls_p,_ls_q) <= 0) { \
199  _ls_e = _ls_p; _ls_p = _ls_p->next; _ls_psize--; \
200  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
201  } else { \
202  _ls_e = _ls_q; _ls_q = _ls_q->next; _ls_qsize--; \
203  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
204  } \
205  if (_ls_tail) { \
206  _ls_tail->next = _ls_e; \
207  } else { \
208  list = _ls_e; \
209  } \
210  _ls_e->prev = _ls_tail; \
211  _ls_tail = _ls_e; \
212  } \
213  _ls_p = _ls_q; \
214  } \
215  list->prev = _ls_tail; \
216  _ls_tail->next = list; \
217  if (_ls_nmerges <= 1) { \
218  _ls_looping=0; \
219  } \
220  _ls_insize *= 2; \
221  } \
222  } \
223 } while (0)
224 
225 /******************************************************************************
226  * singly linked list macros (non-circular) *
227  *****************************************************************************/
228 #define LL_PREPEND(head,add) \
229 do { \
230  (add)->next = head; \
231  head = add; \
232 } while (0)
233 
234 #define LL_APPEND(head,add) \
235 do { \
236  __typeof__(head) _tmp; \
237  (add)->next=NULL; \
238  if (head) { \
239  _tmp = head; \
240  while (_tmp->next) { _tmp = _tmp->next; } \
241  _tmp->next=(add); \
242  } else { \
243  (head)=(add); \
244  } \
245 } while (0)
246 
247 #define LL_DELETE(head,del) \
248 do { \
249  __typeof__(head) _tmp; \
250  if ((head) == (del)) { \
251  (head)=(head)->next; \
252  } else { \
253  _tmp = head; \
254  while (_tmp->next && (_tmp->next != (del))) { \
255  _tmp = _tmp->next; \
256  } \
257  if (_tmp->next) { \
258  _tmp->next = ((del)->next); \
259  } \
260  } \
261 } while (0)
262 
263 #define LL_FOREACH(head,el) \
264  for(el=head;el;el=el->next)
265 
266 /******************************************************************************
267  * doubly linked list macros (non-circular) *
268  *****************************************************************************/
269 #define DL_PREPEND(head,add) \
270 do { \
271  (add)->next = head; \
272  if (head) { \
273  (add)->prev = (head)->prev; \
274  (head)->prev = (add); \
275  } else { \
276  (add)->prev = (add); \
277  } \
278  (head) = (add); \
279 } while (0)
280 
281 #define DL_APPEND(head,add) \
282 do { \
283  if (head) { \
284  (add)->prev = (head)->prev; \
285  (head)->prev->next = (add); \
286  (head)->prev = (add); \
287  (add)->next = NULL; \
288  } else { \
289  (head)=(add); \
290  (head)->prev = (head); \
291  (head)->next = NULL; \
292  } \
293 } while (0);
294 
295 #define DL_DELETE(head,del) \
296 do { \
297  if ((del)->prev == (del)) { \
298  (head)=NULL; \
299  } else if ((del)==(head)) { \
300  (del)->next->prev = (del)->prev; \
301  (head) = (del)->next; \
302  } else { \
303  (del)->prev->next = (del)->next; \
304  if ((del)->next) { \
305  (del)->next->prev = (del)->prev; \
306  } else { \
307  (head)->prev = (del)->prev; \
308  } \
309  } \
310 } while (0);
311 
312 
313 #define DL_FOREACH(head,el) \
314  for(el=head;el;el=el->next)
315 
316 /******************************************************************************
317  * circular doubly linked list macros *
318  *****************************************************************************/
319 #define CDL_PREPEND(head,add) \
320 do { \
321  if (head) { \
322  (add)->prev = (head)->prev; \
323  (add)->next = (head); \
324  (head)->prev = (add); \
325  (add)->prev->next = (add); \
326  } else { \
327  (add)->prev = (add); \
328  (add)->next = (add); \
329  } \
330 (head)=(add); \
331 } while (0)
332 
333 #define CDL_DELETE(head,del) \
334 do { \
335  if ( ((head)==(del)) && ((head)->next == (head))) { \
336  (head) = 0L; \
337  } else { \
338  (del)->next->prev = (del)->prev; \
339  (del)->prev->next = (del)->next; \
340  if ((del) == (head)) (head)=(del)->next; \
341  } \
342 } while (0);
343 
344 #define CDL_FOREACH(head,el) \
345  for(el=head;el;el= (el->next==head ? 0L : el->next))
346 
347 
348 #endif /* UTLIST_H */
349