Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/tkDList.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 69:33d812a61356
1 /*
2 * tkDList.h --
3 *
4 * A list is headed by pointers to first and last element. The elements
5 * are doubly linked so that an arbitrary element can be removed without
6 * a need to traverse the list. New elements can be added to the list
7 * before or after an existing element or at the head/tail of the list.
8 * A list may be traversed in the forward or backward direction.
9 *
10 * Copyright (c) 2018 by Gregor Cramer.
11 *
12 * See the file "license.terms" for information on usage and redistribution of
13 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
14 */
15
16 /*
17 * Note that this file will not be included in header files, it is the purpose
18 * of this file to be included in source files only. Thus we are not using the
19 * prefix "Tk_" here for functions, because all the functions have private scope.
20 */
21
22 /*
23 * -------------------------------------------------------------------------------
24 * Use the double linked list in the following way:
25 * -------------------------------------------------------------------------------
26 * typedef struct MyListEntry { TK_DLIST_LINKS(MyListEntry); int value; } MyListEntry;
27 * TK_DLIST_DEFINE(MyList, MyListEntry);
28 * MyList listHdr = TK_DLIST_LIST_INITIALIZER; // or MyList_Init(&listHdr)
29 * MyListEntry *p;
30 * int i = 0;
31 * MyList_Append(&listHdr, ckalloc(sizeof(MyListEntry)));
32 * MyList_Append(&listHdr, ckalloc(sizeof(MyListEntry)));
33 * TK_DLIST_FOREACH(p, &listHdr) { p->value = i++; }
34 * // ...
35 * MyList_RemoveHead(&listHdr);
36 * MyList_RemoveHead(&listHdr);
37 * MyList_Clear(MyListEntry, &listHdr); // invokes ckfree() for each element
38 * -------------------------------------------------------------------------------
39 * IMPORTANT NOTE: TK_DLIST_LINKS must be used at start of struct!
40 */
41
42 #ifndef TK_DLIST_DEFINED
43 #define TK_DLIST_DEFINED
44
45 #include "tkInt.h"
46
47 /*
48 * List definitions.
49 */
50
51 #define TK_DLIST_LINKS(ElemType) \
52 struct { \
53 struct ElemType *prev; /* previous element */ \
54 struct ElemType *next; /* next element */ \
55 } _dl_
56
57 #define TK_DLIST_LIST_INITIALIZER { NULL, NULL }
58 #define TK_DLIST_ELEM_INITIALIZER { NULL, NULL }
59
60 /*************************************************************************/
61 /*
62 * DList_Init: Initialize list header. This can also be used to clear the
63 * list.
64 *
65 * See also: DList_Clear()
66 */
67 /*************************************************************************/
68 /*
69 * DList_ElemInit: Initialize a list element.
70 */
71 /*************************************************************************/
72 /*
73 * DList_InsertAfter: Insert 'elem' after 'listElem'. 'elem' must not
74 * be linked, but 'listElem' must be linked.
75 */
76 /*************************************************************************/
77 /*
78 * DList_InsertBefore: Insert 'elem' before 'listElem'. 'elem' must not
79 * be linked, but 'listElem' must be linked.
80 */
81 /*************************************************************************/
82 /*
83 * DList_Prepend: Insert 'elem' at start of list. This element must not
84 * be linked.
85 *
86 * See also: DList_Append()
87 */
88 /*************************************************************************/
89 /*
90 * DList_Append: Append 'elem' to end of list. This element must not
91 * be linked.
92 *
93 * See also: DList_Prepend()
94 */
95 /*************************************************************************/
96 /*
97 * DList_Move: Append all list items of 'src' to end of 'dst'.
98 */
99 /*************************************************************************/
100 /*
101 * DList_Remove: Remove 'elem' from list. This element must be linked.
102 *
103 * See also: DList_Free()
104 */
105 /*************************************************************************/
106 /*
107 * DList_Free: Remove 'elem' from list and free it. This element must
108 * be linked.
109 *
110 * See also: DList_Remove()
111 */
112 /*************************************************************************/
113 /*
114 * DList_RemoveHead: Remove first element from list. The list must
115 * not be empty.
116 *
117 * See also: DList_FreeHead()
118 */
119 /*************************************************************************/
120 /*
121 * DList_RemoveTail: Remove last element from list. The list must
122 * not be empty.
123 *
124 * See also: DList_FreeTail()
125 */
126 /*************************************************************************/
127 /*
128 * DList_FreeHead: Remove first element from list and free it.
129 * The list must not be empty.
130 *
131 * See also: DList_RemoveHead()
132 */
133 /*************************************************************************/
134 /*
135 * DList_FreeTail: Remove last element from list and free it.
136 * The list must not be empty.
137 *
138 * See also: DList_RemoveTail()
139 */
140 /*************************************************************************/
141 /*
142 * DList_SwapElems: Swap positions of given elements 'lhs' and 'rhs'.
143 * Both elements must be linked, and must belong to same list.
144 */
145 /*************************************************************************/
146 /*
147 * DList_Clear: Clear whole list and free all elements.
148 *
149 * See also: DList_Init
150 */
151 /*************************************************************************/
152 /*
153 * DList_Traverse: Iterate over all elements in list from first to last.
154 * Call given function func(head, elem) for each element. The function has
155 * to return the next element in list to traverse, normally this is
156 * DList_Next(elem).
157 *
158 * See also: TK_DLIST_FOREACH, TK_DLIST_FOREACH_REVERSE
159 */
160 /*************************************************************************/
161 /*
162 * DList_First: Return pointer of first element in list, maybe it's NULL.
163 */
164 /*************************************************************************/
165 /*
166 * DList_Last: Return pointer of last element in list, maybe it's NULL.
167 */
168 /*************************************************************************/
169 /*
170 * DList_Next: Return pointer of next element after 'elem', maybe it's NULL.
171 *
172 * See also: DList_Prev()
173 */
174 /*************************************************************************/
175 /*
176 * DList_Prev: Return pointer of previous element before 'elem', maybe it's
177 * NULL.
178 *
179 * See also: DList_Next()
180 */
181 /*************************************************************************/
182 /*
183 * DList_IsEmpty: Test whether given list is empty.
184 */
185 /*************************************************************************/
186 /*
187 * DList_IsLinked: Test whether given element is linked.
188 */
189 /*************************************************************************/
190 /*
191 * DList_IsFirst: Test whether given element is first element in list.
192 * Note that 'elem' must be linked.
193 *
194 * See also: DList_IsLast(), DList_IsLinked()
195 */
196 /*************************************************************************/
197 /*
198 * DList_IsLast: Test whether given element is last element in list.
199 * Note that 'elem' must be linked.
200 *
201 * See also: DList_IsFirst(), DList_IsLinked()
202 */
203 /*************************************************************************/
204 /*
205 * DList_Size: Count number of elements in given list.
206 */
207 /*************************************************************************/
208 /*
209 * TK_DLIST_FOREACH: Iterate over all elements in list from first to last.
210 * 'var' is the name of the variable which points to current element.
211 *
212 * See also: TK_DLIST_FOREACH_REVERSE, DList_Traverse()
213 */
214 /*************************************************************************/
215 /*
216 * TK_DLIST_FOREACH_REVERSE: Iterate over all elements in list from last
217 * to first (backwards). 'var' is the name of the variable which points to
218 * current element.
219 */
220 /*************************************************************************/
221
222 #if defined(__GNUC__) || defined(__clang__)
223 # define __TK_DLIST_UNUSED __attribute__((unused))
224 #else
225 # define __TK_DLIST_UNUSED
226 #endif
227
228 #define TK_DLIST_DEFINE(LT, ElemType) /* LT = type of head/list */ \
229 /* ------------------------------------------------------------------------- */ \
230 typedef struct LT { \
231 struct ElemType *first; /* first element */ \
232 struct ElemType *last; /* last element */ \
233 } LT; \
234 \
235 typedef struct ElemType *(LT##_Func)(LT *head, struct ElemType *elem); \
236 \
237 __TK_DLIST_UNUSED \
238 static void \
239 LT##_Init(LT *head) \
240 { \
241 assert(head); \
242 head->first = NULL; \
243 head->last = NULL; \
244 } \
245 \
246 __TK_DLIST_UNUSED \
247 static void \
248 LT##_ElemInit(struct ElemType *elem) \
249 { \
250 assert(elem); \
251 elem->_dl_.next = NULL; \
252 elem->_dl_.prev = NULL; \
253 } \
254 \
255 __TK_DLIST_UNUSED \
256 static int \
257 LT##_IsEmpty(LT *head) \
258 { \
259 assert(head); \
260 return head->first == NULL; \
261 } \
262 \
263 __TK_DLIST_UNUSED \
264 static int \
265 LT##_IsLinked(struct ElemType *elem) \
266 { \
267 assert(elem); \
268 return elem->_dl_.next && elem->_dl_.prev; \
269 } \
270 \
271 __TK_DLIST_UNUSED \
272 static int \
273 LT##_IsFirst(struct ElemType *elem) \
274 { \
275 assert(LT##_IsLinked(elem)); \
276 return elem->_dl_.prev->_dl_.prev == elem; \
277 } \
278 \
279 __TK_DLIST_UNUSED \
280 static int \
281 LT##_IsLast(struct ElemType *elem) \
282 { \
283 assert(LT##_IsLinked(elem)); \
284 return elem->_dl_.next->_dl_.next == elem; \
285 } \
286 \
287 __TK_DLIST_UNUSED \
288 static struct ElemType * \
289 LT##_First(LT *head) \
290 { \
291 assert(head); \
292 return head->first; \
293 } \
294 \
295 __TK_DLIST_UNUSED \
296 static struct ElemType * \
297 LT##_Last(LT *head) \
298 { \
299 assert(head); \
300 return head->last; \
301 } \
302 \
303 __TK_DLIST_UNUSED \
304 static struct ElemType * \
305 LT##_Next(struct ElemType *elem) \
306 { \
307 assert(elem); \
308 return LT##_IsLast(elem) ? NULL : elem->_dl_.next; \
309 } \
310 \
311 __TK_DLIST_UNUSED \
312 static struct ElemType * \
313 LT##_Prev(struct ElemType *elem) \
314 { \
315 assert(elem); \
316 return LT##_IsFirst(elem) ? NULL : elem->_dl_.prev; \
317 } \
318 \
319 __TK_DLIST_UNUSED \
320 static unsigned \
321 LT##_Size(const LT *head) \
322 { \
323 const struct ElemType *elem; \
324 unsigned size = 0; \
325 assert(head); \
326 if ((elem = head->first)) { \
327 for ( ; elem != (void *) head; elem = elem->_dl_.next) { \
328 ++size; \
329 } \
330 } \
331 return size; \
332 } \
333 \
334 __TK_DLIST_UNUSED \
335 static void \
336 LT##_InsertAfter(struct ElemType *listElem, struct ElemType *elem) \
337 { \
338 assert(listElem); \
339 assert(elem); \
340 elem->_dl_.next = listElem->_dl_.next; \
341 elem->_dl_.prev = listElem; \
342 listElem->_dl_.next->_dl_.prev = elem; \
343 listElem->_dl_.next = elem; \
344 } \
345 \
346 __TK_DLIST_UNUSED \
347 static void \
348 LT##_InsertBefore(struct ElemType *listElem, struct ElemType *elem) \
349 { \
350 assert(listElem); \
351 assert(elem); \
352 elem->_dl_.next = listElem; \
353 elem->_dl_.prev = listElem->_dl_.prev;; \
354 listElem->_dl_.prev->_dl_.next = elem; \
355 listElem->_dl_.prev = elem; \
356 } \
357 \
358 __TK_DLIST_UNUSED \
359 static void \
360 LT##_Prepend(LT *head, struct ElemType *elem) \
361 { \
362 assert(head); \
363 assert(elem); \
364 elem->_dl_.prev = (void *) head; \
365 if (!head->first) { \
366 elem->_dl_.next = (void *) head; \
367 head->last = elem; \
368 } else { \
369 elem->_dl_.next = head->first; \
370 head->first->_dl_.prev = elem; \
371 } \
372 head->first = elem; \
373 } \
374 \
375 __TK_DLIST_UNUSED \
376 static void \
377 LT##_Append(LT *head, struct ElemType *elem) \
378 { \
379 assert(head); \
380 assert(elem); \
381 elem->_dl_.next = (void *) head; \
382 if (!head->first) { \
383 elem->_dl_.prev = (void *) head; \
384 head->first = elem; \
385 } else { \
386 elem->_dl_.prev = head->last; \
387 head->last->_dl_.next = elem; \
388 } \
389 head->last = elem; \
390 } \
391 \
392 __TK_DLIST_UNUSED \
393 static void \
394 LT##_Move(LT *dst, LT *src) \
395 { \
396 assert(dst); \
397 assert(src); \
398 if (src->first) { \
399 if (dst->first) { \
400 dst->last->_dl_.next = src->first; \
401 src->first->_dl_.prev = dst->last; \
402 dst->last = src->last; \
403 } else { \
404 *dst = *src; \
405 dst->first->_dl_.prev = (void *) dst; \
406 } \
407 dst->last->_dl_.next = (void *) dst; \
408 LT##_Init(src); \
409 } \
410 } \
411 \
412 __TK_DLIST_UNUSED \
413 static void \
414 LT##_Remove(struct ElemType *elem) \
415 { \
416 int isFirst, isLast; \
417 assert(LT##_IsLinked(elem)); \
418 isFirst = LT##_IsFirst(elem); \
419 isLast = LT##_IsLast(elem); \
420 if (isFirst && isLast) { \
421 ((LT *) elem->_dl_.prev)->first = NULL; \
422 ((LT *) elem->_dl_.next)->last = NULL; \
423 } else { \
424 if (isFirst) { \
425 ((LT *) elem->_dl_.prev)->first = elem->_dl_.next; \
426 } else { \
427 elem->_dl_.prev->_dl_.next = elem->_dl_.next; \
428 } \
429 if (isLast) { \
430 ((LT *) elem->_dl_.next)->last = elem->_dl_.prev; \
431 } else { \
432 elem->_dl_.next->_dl_.prev = elem->_dl_.prev; \
433 } \
434 } \
435 LT##_ElemInit(elem); \
436 } \
437 \
438 __TK_DLIST_UNUSED \
439 static void \
440 LT##_Free(struct ElemType *elem) \
441 { \
442 LT##_Remove(elem); \
443 ckfree((void *) elem); \
444 } \
445 \
446 __TK_DLIST_UNUSED \
447 static void \
448 LT##_RemoveHead(LT *head) \
449 { \
450 assert(!LT##_IsEmpty(head)); \
451 LT##_Remove(head->first); \
452 } \
453 \
454 __TK_DLIST_UNUSED \
455 static void \
456 LT##_RemoveTail(LT *head) \
457 { \
458 assert(!LT##_IsEmpty(head)); \
459 LT##_Remove(head->last); \
460 } \
461 \
462 __TK_DLIST_UNUSED \
463 static void \
464 LT##_FreeHead(LT *head) \
465 { \
466 assert(!LT##_IsEmpty(head)); \
467 LT##_Free(head->first); \
468 } \
469 \
470 __TK_DLIST_UNUSED \
471 static void \
472 LT##_FreeTail(LT *head) \
473 { \
474 assert(!LT##_IsEmpty(head)); \
475 LT##_Free(head->last); \
476 } \
477 \
478 __TK_DLIST_UNUSED \
479 static void \
480 LT##_SwapElems(struct ElemType *lhs, struct ElemType *rhs) \
481 { \
482 assert(lhs); \
483 assert(rhs); \
484 if (lhs != rhs) { \
485 struct ElemType tmp; \
486 if (LT##_IsFirst(lhs)) { \
487 ((LT *) lhs->_dl_.prev)->first = rhs; \
488 } else if (LT##_IsFirst(rhs)) { \
489 ((LT *) rhs->_dl_.prev)->first = lhs; \
490 } \
491 if (LT##_IsLast(lhs)) { \
492 ((LT *) lhs->_dl_.next)->last = rhs; \
493 } else if (LT##_IsLast(rhs)) { \
494 ((LT *) rhs->_dl_.next)->last = lhs; \
495 } \
496 tmp._dl_ = lhs->_dl_; \
497 lhs->_dl_ = rhs->_dl_; \
498 rhs->_dl_ = tmp._dl_; \
499 } \
500 } \
501 \
502 __TK_DLIST_UNUSED \
503 static void \
504 LT##_Clear(LT *head) \
505 { \
506 struct ElemType *p; \
507 struct ElemType *next; \
508 assert(head); \
509 for (p = head->first; p; p = next) { \
510 next = LT##_Next(p); \
511 ckfree((void *) p); \
512 } \
513 LT##_Init(head); \
514 } \
515 \
516 __TK_DLIST_UNUSED \
517 static void \
518 LT##_Traverse(LT *head, LT##_Func func) \
519 { \
520 struct ElemType *next; \
521 struct ElemType *p; \
522 assert(head); \
523 for (p = head->first; p; p = next) { \
524 next = func(head, p); \
525 } \
526 } \
527 /* ------------------------------------------------------------------------- */
528
529 #define TK_DLIST_FOREACH(var, head) \
530 assert(head); \
531 for (var = head->first ? head->first : (void *) head; var != (void *) head; var = var->_dl_.next)
532
533 #define TK_DLIST_FOREACH_REVERSE(var, head) \
534 assert(head); \
535 for (var = head->last ? head->last : (void *) head; var != (void *) head; var = var->_dl_.prev)
536
537 #endif /* TK_DLIST_DEFINED */
538
539 /*
540 * Local Variables:
541 * mode: c
542 * c-basic-offset: 4
543 * fill-column: 105
544 * End:
545 * vi:set ts=8 sw=4:
546 */