Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/util/utlist.h

1/*␊
2Copyright (c) 2007-2012, Troy D. Hanson http://uthash.sourceforge.net␊
3All rights reserved.␊
4␊
5Redistribution and use in source and binary forms, with or without␊
6modification, 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␊
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS␊
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED␊
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A␊
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER␊
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,␊
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,␊
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR␊
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF␊
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING␊
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS␊
21SOFTWARE, 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.9.6␊
28␊
29#include <assert.h>␊
30␊
31/* ␊
32 * This file contains macros to manipulate singly and doubly-linked lists.␊
33 *␊
34 * 1. LL_ macros: singly-linked lists.␊
35 * 2. DL_ macros: doubly-linked lists.␊
36 * 3. CDL_ macros: circular doubly-linked lists.␊
37 *␊
38 * To use singly-linked lists, your structure must have a "next" pointer.␊
39 * To use doubly-linked lists, your structure must "prev" and "next" pointers.␊
40 * Either way, the pointer to the head of the list must be initialized to NULL.␊
41 * ␊
42 * ----------------.EXAMPLE -------------------------␊
43 * struct item {␊
44 * int id;␊
45 * struct item *prev, *next;␊
46 * }␊
47 *␊
48 * struct item *list = NULL:␊
49 *␊
50 * int main() {␊
51 * struct item *item;␊
52 * ... allocate and populate item ...␊
53 * DL_APPEND(list, item);␊
54 * }␊
55 * --------------------------------------------------␊
56 *␊
57 * For doubly-linked lists, the append and delete macros are O(1)␊
58 * For singly-linked lists, append and delete are O(n) but prepend is O(1)␊
59 * The sort macro is O(n log(n)) for all types of single/double/circular lists.␊
60 */␊
61␊
62/* These macros use decltype or the earlier __typeof GNU extension.␊
63 As decltype is only available in newer compilers (VS2010 or gcc 4.3+␊
64 when compiling c++ code), this code uses whatever method is needed␊
65 or, for VS2008 where neither is available, uses casting workarounds. */␊
66#ifdef _MSC_VER /* MS compiler */␊
67#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */␊
68#define LDECLTYPE(x) decltype(x)␊
69#else /* VS2008 or older (or VS2010 in C mode) */␊
70#define NO_DECLTYPE␊
71#define LDECLTYPE(x) char*␊
72#endif␊
73#else /* GNU, Sun and other compilers */␊
74#define LDECLTYPE(x) __typeof(x)␊
75#endif␊
76␊
77/* for VS2008 we use some workarounds to get around the lack of decltype,␊
78 * namely, we always reassign our tmp variable to the list head if we need␊
79 * to dereference its prev/next pointers, and save/restore the real head.*/␊
80#ifdef NO_DECLTYPE␊
81#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }␊
82#define _NEXT(elt,list) ((char*)((list)->next))␊
83#define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }␊
84#define _PREV(elt,list) ((char*)((list)->prev))␊
85#define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }␊
86#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }␊
87#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }␊
88#else ␊
89#define _SV(elt,list)␊
90#define _NEXT(elt,list) ((elt)->next)␊
91#define _NEXTASGN(elt,list,to) ((elt)->next)=(to)␊
92#define _PREV(elt,list) ((elt)->prev)␊
93#define _PREVASGN(elt,list,to) ((elt)->prev)=(to)␊
94#define _RS(list)␊
95#define _CASTASGN(a,b) (a)=(b)␊
96#endif␊
97␊
98/******************************************************************************␊
99 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *␊
100 * Unwieldy variable names used here to avoid shadowing passed-in variables. *␊
101 *****************************************************************************/␊
102#define LL_SORT(list, cmp) \␊
103do { \␊
104 LDECLTYPE(list) _ls_p; \␊
105 LDECLTYPE(list) _ls_q; \␊
106 LDECLTYPE(list) _ls_e; \␊
107 LDECLTYPE(list) _ls_tail; \␊
108 LDECLTYPE(list) _ls_oldhead; \␊
109 LDECLTYPE(list) _tmp; \␊
110 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
111 if (list) { \␊
112 _ls_insize = 1; \␊
113 _ls_looping = 1; \␊
114 while (_ls_looping) { \␊
115 _CASTASGN(_ls_p,list); \␊
116 _CASTASGN(_ls_oldhead,list); \␊
117 list = NULL; \␊
118 _ls_tail = NULL; \␊
119 _ls_nmerges = 0; \␊
120 while (_ls_p) { \␊
121 _ls_nmerges++; \␊
122 _ls_q = _ls_p; \␊
123 _ls_psize = 0; \␊
124 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊
125 _ls_psize++; \␊
126 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \␊
127 if (!_ls_q) break; \␊
128 } \␊
129 _ls_qsize = _ls_insize; \␊
130 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
131 if (_ls_psize == 0) { \␊
132 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
133 } else if (_ls_qsize == 0 || !_ls_q) { \␊
134 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
135 } else if (cmp(_ls_p,_ls_q) <= 0) { \␊
136 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
137 } else { \␊
138 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
139 } \␊
140 if (_ls_tail) { \␊
141 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊
142 } else { \␊
143 _CASTASGN(list,_ls_e); \␊
144 } \␊
145 _ls_tail = _ls_e; \␊
146 } \␊
147 _ls_p = _ls_q; \␊
148 } \␊
149 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \␊
150 if (_ls_nmerges <= 1) { \␊
151 _ls_looping=0; \␊
152 } \␊
153 _ls_insize *= 2; \␊
154 } \␊
155 } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊
156} while (0)␊
157␊
158#define DL_SORT(list, cmp) \␊
159do { \␊
160 LDECLTYPE(list) _ls_p; \␊
161 LDECLTYPE(list) _ls_q; \␊
162 LDECLTYPE(list) _ls_e; \␊
163 LDECLTYPE(list) _ls_tail; \␊
164 LDECLTYPE(list) _ls_oldhead; \␊
165 LDECLTYPE(list) _tmp; \␊
166 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
167 if (list) { \␊
168 _ls_insize = 1; \␊
169 _ls_looping = 1; \␊
170 while (_ls_looping) { \␊
171 _CASTASGN(_ls_p,list); \␊
172 _CASTASGN(_ls_oldhead,list); \␊
173 list = NULL; \␊
174 _ls_tail = NULL; \␊
175 _ls_nmerges = 0; \␊
176 while (_ls_p) { \␊
177 _ls_nmerges++; \␊
178 _ls_q = _ls_p; \␊
179 _ls_psize = 0; \␊
180 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊
181 _ls_psize++; \␊
182 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \␊
183 if (!_ls_q) break; \␊
184 } \␊
185 _ls_qsize = _ls_insize; \␊
186 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
187 if (_ls_psize == 0) { \␊
188 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
189 } else if (_ls_qsize == 0 || !_ls_q) { \␊
190 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
191 } else if (cmp(_ls_p,_ls_q) <= 0) { \␊
192 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
193 } else { \␊
194 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
195 } \␊
196 if (_ls_tail) { \␊
197 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊
198 } else { \␊
199 _CASTASGN(list,_ls_e); \␊
200 } \␊
201 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \␊
202 _ls_tail = _ls_e; \␊
203 } \␊
204 _ls_p = _ls_q; \␊
205 } \␊
206 _CASTASGN(list->prev, _ls_tail); \␊
207 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \␊
208 if (_ls_nmerges <= 1) { \␊
209 _ls_looping=0; \␊
210 } \␊
211 _ls_insize *= 2; \␊
212 } \␊
213 } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊
214} while (0)␊
215␊
216#define CDL_SORT(list, cmp) \␊
217do { \␊
218 LDECLTYPE(list) _ls_p; \␊
219 LDECLTYPE(list) _ls_q; \␊
220 LDECLTYPE(list) _ls_e; \␊
221 LDECLTYPE(list) _ls_tail; \␊
222 LDECLTYPE(list) _ls_oldhead; \␊
223 LDECLTYPE(list) _tmp; \␊
224 LDECLTYPE(list) _tmp2; \␊
225 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
226 if (list) { \␊
227 _ls_insize = 1; \␊
228 _ls_looping = 1; \␊
229 while (_ls_looping) { \␊
230 _CASTASGN(_ls_p,list); \␊
231 _CASTASGN(_ls_oldhead,list); \␊
232 list = NULL; \␊
233 _ls_tail = NULL; \␊
234 _ls_nmerges = 0; \␊
235 while (_ls_p) { \␊
236 _ls_nmerges++; \␊
237 _ls_q = _ls_p; \␊
238 _ls_psize = 0; \␊
239 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊
240 _ls_psize++; \␊
241 _SV(_ls_q,list); \␊
242 if (_NEXT(_ls_q,list) == _ls_oldhead) { \␊
243 _ls_q = NULL; \␊
244 } else { \␊
245 _ls_q = _NEXT(_ls_q,list); \␊
246 } \␊
247 _RS(list); \␊
248 if (!_ls_q) break; \␊
249 } \␊
250 _ls_qsize = _ls_insize; \␊
251 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
252 if (_ls_psize == 0) { \␊
253 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
254 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \␊
255 } else if (_ls_qsize == 0 || !_ls_q) { \␊
256 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
257 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \␊
258 } else if (cmp(_ls_p,_ls_q) <= 0) { \␊
259 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊
260 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \␊
261 } else { \␊
262 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊
263 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \␊
264 } \␊
265 if (_ls_tail) { \␊
266 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊
267 } else { \␊
268 _CASTASGN(list,_ls_e); \␊
269 } \␊
270 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \␊
271 _ls_tail = _ls_e; \␊
272 } \␊
273 _ls_p = _ls_q; \␊
274 } \␊
275 _CASTASGN(list->prev,_ls_tail); \␊
276 _CASTASGN(_tmp2,list); \␊
277 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \␊
278 if (_ls_nmerges <= 1) { \␊
279 _ls_looping=0; \␊
280 } \␊
281 _ls_insize *= 2; \␊
282 } \␊
283 } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊
284} while (0)␊
285␊
286/******************************************************************************␊
287 * singly linked list macros (non-circular) *␊
288 *****************************************************************************/␊
289#define LL_PREPEND(head,add) \␊
290do { \␊
291 (add)->next = head; \␊
292 head = add; \␊
293} while (0)␊
294␊
295#define LL_CONCAT(head1,head2) \␊
296do { \␊
297 LDECLTYPE(head1) _tmp; \␊
298 if (head1) { \␊
299 _tmp = head1; \␊
300 while (_tmp->next) { _tmp = _tmp->next; } \␊
301 _tmp->next=(head2); \␊
302 } else { \␊
303 (head1)=(head2); \␊
304 } \␊
305} while (0)␊
306␊
307#define LL_APPEND(head,add) \␊
308do { \␊
309 LDECLTYPE(head) _tmp; \␊
310 (add)->next=NULL; \␊
311 if (head) { \␊
312 _tmp = head; \␊
313 while (_tmp->next) { _tmp = _tmp->next; } \␊
314 _tmp->next=(add); \␊
315 } else { \␊
316 (head)=(add); \␊
317 } \␊
318} while (0)␊
319␊
320#define LL_DELETE(head,del) \␊
321do { \␊
322 LDECLTYPE(head) _tmp; \␊
323 if ((head) == (del)) { \␊
324 (head)=(head)->next; \␊
325 } else { \␊
326 _tmp = head; \␊
327 while (_tmp->next && (_tmp->next != (del))) { \␊
328 _tmp = _tmp->next; \␊
329 } \␊
330 if (_tmp->next) { \␊
331 _tmp->next = ((del)->next); \␊
332 } \␊
333 } \␊
334} while (0)␊
335␊
336/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */␊
337#define LL_APPEND_VS2008(head,add) \␊
338do { \␊
339 if (head) { \␊
340 (add)->next = head; /* use add->next as a temp variable */ \␊
341 while ((add)->next->next) { (add)->next = (add)->next->next; } \␊
342 (add)->next->next=(add); \␊
343 } else { \␊
344 (head)=(add); \␊
345 } \␊
346 (add)->next=NULL; \␊
347} while (0)␊
348␊
349#define LL_DELETE_VS2008(head,del) \␊
350do { \␊
351 if ((head) == (del)) { \␊
352 (head)=(head)->next; \␊
353 } else { \␊
354 char *_tmp = (char*)(head); \␊
355 while ((head)->next && ((head)->next != (del))) { \␊
356 head = (head)->next; \␊
357 } \␊
358 if ((head)->next) { \␊
359 (head)->next = ((del)->next); \␊
360 } \␊
361 { \␊
362 char **_head_alias = (char**)&(head); \␊
363 *_head_alias = _tmp; \␊
364 } \␊
365 } \␊
366} while (0)␊
367#ifdef NO_DECLTYPE␊
368#undef LL_APPEND␊
369#define LL_APPEND LL_APPEND_VS2008␊
370#undef LL_DELETE␊
371#define LL_DELETE LL_DELETE_VS2008␊
372#undef LL_CONCAT /* no LL_CONCAT_VS2008 */␊
373#undef DL_CONCAT /* no DL_CONCAT_VS2008 */␊
374#endif␊
375/* end VS2008 replacements */␊
376␊
377#define LL_FOREACH(head,el) \␊
378 for(el=head;el;el=(el)->next)␊
379␊
380#define LL_FOREACH_SAFE(head,el,tmp) \␊
381 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)␊
382␊
383#define LL_SEARCH_SCALAR(head,out,field,val) \␊
384do { \␊
385 LL_FOREACH(head,out) { \␊
386 if ((out)->field == (val)) break; \␊
387 } \␊
388} while(0) ␊
389␊
390#define LL_SEARCH(head,out,elt,cmp) \␊
391do { \␊
392 LL_FOREACH(head,out) { \␊
393 if ((cmp(out,elt))==0) break; \␊
394 } \␊
395} while(0) ␊
396␊
397/******************************************************************************␊
398 * doubly linked list macros (non-circular) *␊
399 *****************************************************************************/␊
400#define DL_PREPEND(head,add) \␊
401do { \␊
402 (add)->next = head; \␊
403 if (head) { \␊
404 (add)->prev = (head)->prev; \␊
405 (head)->prev = (add); \␊
406 } else { \␊
407 (add)->prev = (add); \␊
408 } \␊
409 (head) = (add); \␊
410} while (0)␊
411␊
412#define DL_APPEND(head,add) \␊
413do { \␊
414 if (head) { \␊
415 (add)->prev = (head)->prev; \␊
416 (head)->prev->next = (add); \␊
417 (head)->prev = (add); \␊
418 (add)->next = NULL; \␊
419 } else { \␊
420 (head)=(add); \␊
421 (head)->prev = (head); \␊
422 (head)->next = NULL; \␊
423 } \␊
424} while (0) ␊
425␊
426#define DL_CONCAT(head1,head2) \␊
427do { \␊
428 LDECLTYPE(head1) _tmp; \␊
429 if (head2) { \␊
430 if (head1) { \␊
431 _tmp = (head2)->prev; \␊
432 (head2)->prev = (head1)->prev; \␊
433 (head1)->prev->next = (head2); \␊
434 (head1)->prev = _tmp; \␊
435 } else { \␊
436 (head1)=(head2); \␊
437 } \␊
438 } \␊
439} while (0) ␊
440␊
441#define DL_DELETE(head,del) \␊
442do { \␊
443 assert((del)->prev != NULL); \␊
444 if ((del)->prev == (del)) { \␊
445 (head)=NULL; \␊
446 } else if ((del)==(head)) { \␊
447 (del)->next->prev = (del)->prev; \␊
448 (head) = (del)->next; \␊
449 } else { \␊
450 (del)->prev->next = (del)->next; \␊
451 if ((del)->next) { \␊
452 (del)->next->prev = (del)->prev; \␊
453 } else { \␊
454 (head)->prev = (del)->prev; \␊
455 } \␊
456 } \␊
457} while (0) ␊
458␊
459␊
460#define DL_FOREACH(head,el) \␊
461 for(el=head;el;el=(el)->next)␊
462␊
463/* this version is safe for deleting the elements during iteration */␊
464#define DL_FOREACH_SAFE(head,el,tmp) \␊
465 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)␊
466␊
467/* these are identical to their singly-linked list counterparts */␊
468#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR␊
469#define DL_SEARCH LL_SEARCH␊
470␊
471/******************************************************************************␊
472 * circular doubly linked list macros *␊
473 *****************************************************************************/␊
474#define CDL_PREPEND(head,add) \␊
475do { \␊
476 if (head) { \␊
477 (add)->prev = (head)->prev; \␊
478 (add)->next = (head); \␊
479 (head)->prev = (add); \␊
480 (add)->prev->next = (add); \␊
481 } else { \␊
482 (add)->prev = (add); \␊
483 (add)->next = (add); \␊
484 } \␊
485(head)=(add); \␊
486} while (0)␊
487␊
488#define CDL_DELETE(head,del) \␊
489do { \␊
490 if ( ((head)==(del)) && ((head)->next == (head))) { \␊
491 (head) = 0L; \␊
492 } else { \␊
493 (del)->next->prev = (del)->prev; \␊
494 (del)->prev->next = (del)->next; \␊
495 if ((del) == (head)) (head)=(del)->next; \␊
496 } \␊
497} while (0) ␊
498␊
499#define CDL_FOREACH(head,el) \␊
500 for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) ␊
501␊
502#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \␊
503 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \␊
504 (el) && ((tmp2)=(el)->next, 1); \␊
505 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))␊
506␊
507#define CDL_SEARCH_SCALAR(head,out,field,val) \␊
508do { \␊
509 CDL_FOREACH(head,out) { \␊
510 if ((out)->field == (val)) break; \␊
511 } \␊
512} while(0) ␊
513␊
514#define CDL_SEARCH(head,out,elt,cmp) \␊
515do { \␊
516 CDL_FOREACH(head,out) { \␊
517 if ((cmp(out,elt))==0) break; \␊
518 } \␊
519} while(0) ␊
520␊
521#endif /* UTLIST_H */␊
522␊
523

Archive Download this file

Revision: HEAD