rlib
Convenience library for useful things
Loading...
Searching...
No Matches
rlist-internal.h
1/* RLIB - Convenience library for useful things
2 * Copyright (C) 2018 Haakon Sporsheim <haakon.sporsheim@gmail.com>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 3.0 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library.
16 * See the COPYING file at the root of the source repository.
17 */
18#ifndef __R_LIST_INTERNAL_H__
19#define __R_LIST_INTERNAL_H__
20
21#include <rlib/rtypes.h>
22#include <rlib/rmem.h>
23
24R_BEGIN_DECLS
25
26/******************************************************************************/
27/* Doubly linked list */
28/*----------------------------------------------------------------------------*/
29/* R__LIST_DECL (RList, r_list, rpointer, static inline) */
30/* R__LIST_IMPL (RList, r_list, rpointer, r_direct_equal, &, static inline) */
31/******************************************************************************/
32#define R__LIST_DECL(RTYPE, RTYPE_LOW, RDATA, FUNCSPECS) \
33typedef struct _##RTYPE RTYPE; \
34FUNCSPECS RTYPE * RTYPE_LOW##_first (RTYPE * lst); \
35FUNCSPECS RTYPE * RTYPE_LOW##_last (RTYPE * lst); \
36FUNCSPECS RTYPE * RTYPE_LOW##_nth (RTYPE * lst, rsize n); \
37FUNCSPECS rsize RTYPE_LOW##_len (RTYPE * lst); \
38FUNCSPECS rboolean RTYPE_LOW##_contains_full (RTYPE * lst, RDATA data); \
39FUNCSPECS void RTYPE_LOW##_foreach (RTYPE * lst, RFunc func, rpointer user); \
40FUNCSPECS RTYPE * RTYPE_LOW##_alloc0 (void) R_ATTR_MALLOC; \
41FUNCSPECS RTYPE * RTYPE_LOW##_alloc_copy (RDATA data) R_ATTR_MALLOC; \
42FUNCSPECS RTYPE * RTYPE_LOW##_prepend_link (RTYPE * lst, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
43FUNCSPECS RTYPE * RTYPE_LOW##_append_link (RTYPE * lst, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
44FUNCSPECS RTYPE * RTYPE_LOW##_prepend_copy (RTYPE * lst, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
45FUNCSPECS RTYPE * RTYPE_LOW##_append_copy (RTYPE * lst, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
46FUNCSPECS RTYPE * RTYPE_LOW##_insert_after (RTYPE * head, RTYPE * entry, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
47FUNCSPECS RTYPE * RTYPE_LOW##_insert_before (RTYPE * head, RTYPE * entry, RDATA data) R_ATTR_WARN_UNUSED_RESULT;\
48FUNCSPECS void RTYPE_LOW##_free1 (RTYPE * lst); \
49FUNCSPECS void RTYPE_LOW##_free1_full (RTYPE * lst, RDestroyNotify notify); \
50FUNCSPECS RTYPE * RTYPE_LOW##_remove (RTYPE * head, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
51FUNCSPECS RTYPE * RTYPE_LOW##_remove_link (RTYPE * head, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
52FUNCSPECS RTYPE * RTYPE_LOW##_destroy_link (RTYPE * head, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
53FUNCSPECS void RTYPE_LOW##_destroy (RTYPE * head); \
54FUNCSPECS void RTYPE_LOW##_destroy_full (RTYPE * head, RDestroyNotify notify);\
55struct _##RTYPE { \
56 RDATA data; \
57 RTYPE * next; \
58 RTYPE * prev; \
59};
60
61#define R__LIST_IMPL(RTYPE, RTYPE_LOW, RDATA, RREF, FUNCSPECS) \
62FUNCSPECS RTYPE * RTYPE_LOW##_first (RTYPE * lst) \
63{ \
64 if (lst != NULL) while (lst->prev != NULL) lst = lst->prev; \
65 return lst; \
66} \
67FUNCSPECS RTYPE * RTYPE_LOW##_last (RTYPE * lst) \
68{ \
69 if (lst != NULL) while (lst->next != NULL) lst = lst->next; \
70 return lst; \
71} \
72FUNCSPECS RTYPE * RTYPE_LOW##_nth (RTYPE * lst, rsize n) \
73{ \
74 while (n-- > 0 && lst != NULL) lst = lst->next; \
75 return lst; \
76} \
77FUNCSPECS rsize RTYPE_LOW##_len (RTYPE * lst) \
78{ \
79 rsize ret = 0; \
80 if (lst != NULL) { \
81 RTYPE * it; \
82 for (it = lst->next; it != NULL; it = it->next) ret++; \
83 for (it = lst->prev; it != NULL; it = it->prev) ret++; \
84 ret++; \
85 } \
86 return ret; \
87} \
88FUNCSPECS rboolean RTYPE_LOW##_contains_full (RTYPE * lst, RDATA data) \
89{ \
90 if (lst != NULL) { \
91 RTYPE * it; \
92 for (it = lst; it != NULL; it = it->next) { \
93 if (RTYPE_LOW##_data_equal (&it->data, &data)) \
94 return TRUE; \
95 } \
96 for (it = lst->prev; it != NULL; it = it->prev) { \
97 if (RTYPE_LOW##_data_equal (&it->data, &data)) \
98 return TRUE; \
99 } \
100 } \
101 return FALSE; \
102} \
103FUNCSPECS void RTYPE_LOW##_foreach (RTYPE * lst, RFunc func, rpointer user) \
104{ \
105 for (; lst != NULL; lst = lst->next) \
106 func (RREF lst->data, user); \
107} \
108FUNCSPECS RTYPE * RTYPE_LOW##_alloc0 (void) \
109{ \
110 return r_mem_new0 (RTYPE); \
111} \
112FUNCSPECS RTYPE * RTYPE_LOW##_alloc_copy (RDATA data) \
113{ \
114 RTYPE * ret; \
115 if ((ret = r_mem_new (RTYPE)) != NULL) { \
116 ret->data = data; \
117 ret->next = ret->prev = NULL; \
118 } \
119 return ret; \
120} \
121FUNCSPECS RTYPE * RTYPE_LOW##_prepend_link (RTYPE * lst, RTYPE * entry) \
122{ \
123 if ((entry->next = RTYPE_LOW##_first (lst)) != NULL) \
124 entry->next->prev = entry; \
125 return entry; \
126} \
127FUNCSPECS RTYPE * RTYPE_LOW##_append_link (RTYPE * lst, RTYPE * entry) \
128{ \
129 if (lst != NULL) { \
130 RTYPE * last = RTYPE_LOW##_last (lst); \
131 last->next = entry; \
132 entry->prev = last; \
133 entry = lst; \
134 } \
135 return entry; \
136} \
137FUNCSPECS RTYPE * RTYPE_LOW##_prepend_copy (RTYPE * lst, RDATA data) \
138{ \
139 return RTYPE_LOW##_prepend_link (lst, RTYPE_LOW##_alloc_copy (data)); \
140} \
141FUNCSPECS RTYPE * RTYPE_LOW##_append_copy (RTYPE * lst, RDATA data) \
142{ \
143 return RTYPE_LOW##_append_link (lst, RTYPE_LOW##_alloc_copy (data)); \
144} \
145FUNCSPECS RTYPE * RTYPE_LOW##_insert_after (RTYPE * head, RTYPE * entry, RDATA data) \
146{ \
147 RTYPE * lst = RTYPE_LOW##_alloc_copy (data); \
148 if (R_UNLIKELY (head == NULL)) return lst; \
149 if (entry == NULL) entry = head; \
150 lst->next = entry->next; \
151 lst->prev = entry; \
152 if (entry->next != NULL) entry->next->prev = lst; \
153 entry->next = lst; \
154 return head; \
155} \
156FUNCSPECS RTYPE * RTYPE_LOW##_insert_before (RTYPE * head, RTYPE * entry, RDATA data) \
157{ \
158 RTYPE * lst = RTYPE_LOW##_alloc_copy (data); \
159 if (head != NULL && entry != NULL && entry != head) { \
160 lst->prev = entry->prev; \
161 lst->next = entry; \
162 entry->prev->next = lst; \
163 entry->prev = lst; \
164 } else { \
165 head = RTYPE_LOW##_prepend_link (head, lst); \
166 } \
167 return head; \
168} \
169FUNCSPECS void RTYPE_LOW##_free1 (RTYPE * lst) \
170{ \
171 RTYPE_LOW##_clear (lst); \
172 r_free (lst); \
173} \
174FUNCSPECS void RTYPE_LOW##_free1_full (RTYPE * lst, RDestroyNotify notify) \
175{ \
176 if (lst != NULL) { \
177 if (notify != NULL) notify (RREF lst->data); \
178 RTYPE_LOW##_free1 (lst); \
179 } \
180} \
181FUNCSPECS RTYPE * RTYPE_LOW##_remove (RTYPE * head, RDATA data) \
182{ \
183 RTYPE * it; \
184 for (it = head; it != NULL; it = it->next) { \
185 if (RTYPE_LOW##_data_equal (&it->data, &data)) \
186 return RTYPE_LOW##_destroy_link (head, it); \
187 } \
188 return head; \
189} \
190FUNCSPECS RTYPE * RTYPE_LOW##_remove_link (RTYPE * head, RTYPE * entry) \
191{ \
192 if (entry != NULL) { \
193 RTYPE * next = entry->next; \
194 RTYPE * prev = entry->prev; \
195 if (head == entry) head = head->next; \
196 if (prev != NULL) prev->next = entry->next; \
197 if (next != NULL) next->prev = entry->prev; \
198 } \
199 return head; \
200} \
201FUNCSPECS RTYPE * RTYPE_LOW##_destroy_link (RTYPE * head, RTYPE * entry) \
202{ \
203 head = RTYPE_LOW##_remove_link (head, entry); \
204 RTYPE_LOW##_free1 (entry); \
205 return head; \
206} \
207FUNCSPECS void RTYPE_LOW##_destroy (RTYPE * head) \
208{ \
209 if (head != NULL) { \
210 RTYPE * it, * next; \
211 for (it = head->next; it != NULL; it = next) { \
212 next = it->next; \
213 RTYPE_LOW##_free1 (it); \
214 } \
215 for (it = head->prev; it != NULL; it = next) { \
216 next = it->prev; \
217 RTYPE_LOW##_free1 (it); \
218 } \
219 RTYPE_LOW##_free1 (head); \
220 } \
221} \
222FUNCSPECS void RTYPE_LOW##_destroy_full (RTYPE * head, RDestroyNotify notify) \
223{ \
224 if (head != NULL) { \
225 RTYPE * it, * next; \
226 for (it = head->next; it != NULL; it = next) { \
227 next = it->next; \
228 RTYPE_LOW##_free1_full (it, notify); \
229 } \
230 for (it = head->prev; it != NULL; it = next) { \
231 next = it->prev; \
232 RTYPE_LOW##_free1_full (it, notify); \
233 } \
234 RTYPE_LOW##_free1_full (head, notify); \
235 } \
236} \
237
238/******************************************************************************/
239/* Singly linked list */
240/******************************************************************************/
241#define R__SLIST_DECL(RTYPE, RTYPE_LOW, RDATA, FUNCSPECS) \
242typedef struct _##RTYPE RTYPE; \
243FUNCSPECS RTYPE * RTYPE_LOW##_last (RTYPE * lst); \
244FUNCSPECS RTYPE * RTYPE_LOW##_nth (RTYPE * lst, rsize n); \
245FUNCSPECS RTYPE * RTYPE_LOW##_copy (RTYPE * lst); \
246FUNCSPECS RTYPE * RTYPE_LOW##_merge (RTYPE * a, RTYPE * b); \
247FUNCSPECS rsize RTYPE_LOW##_len (RTYPE * lst); \
248FUNCSPECS rboolean RTYPE_LOW##_contains_full (RTYPE * lst, RDATA data); \
249FUNCSPECS void RTYPE_LOW##_foreach (RTYPE * lst, RFunc func, rpointer user); \
250FUNCSPECS rsize RTYPE_LOW##_foreach_remove (RTYPE ** head, \
251 RFuncReturn func, rpointer user); \
252FUNCSPECS RTYPE * RTYPE_LOW##_alloc0 (void) R_ATTR_MALLOC; \
253FUNCSPECS RTYPE * RTYPE_LOW##_alloc_copy (RDATA data) R_ATTR_MALLOC; \
254FUNCSPECS RTYPE * RTYPE_LOW##_prepend_link (RTYPE * lst, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
255FUNCSPECS RTYPE * RTYPE_LOW##_append_link (RTYPE * lst, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
256FUNCSPECS RTYPE * RTYPE_LOW##_prepend_copy (RTYPE * lst, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
257FUNCSPECS RTYPE * RTYPE_LOW##_append_copy (RTYPE * lst, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
258FUNCSPECS RTYPE * RTYPE_LOW##_insert_after (RTYPE * head, RTYPE * entry, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
259FUNCSPECS void RTYPE_LOW##_free1 (RTYPE * lst); \
260FUNCSPECS void RTYPE_LOW##_free1_full (RTYPE * lst, RDestroyNotify notify); \
261FUNCSPECS RTYPE * RTYPE_LOW##_remove (RTYPE * head, RDATA data) R_ATTR_WARN_UNUSED_RESULT; \
262FUNCSPECS RTYPE * RTYPE_LOW##_remove_link (RTYPE * head, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
263FUNCSPECS RTYPE * RTYPE_LOW##_destroy_link (RTYPE * head, RTYPE * entry) R_ATTR_WARN_UNUSED_RESULT; \
264FUNCSPECS void RTYPE_LOW##_destroy (RTYPE * head); \
265FUNCSPECS void RTYPE_LOW##_destroy_full (RTYPE * head, RDestroyNotify notify);\
266struct _##RTYPE { \
267 RDATA data; \
268 RTYPE * next; \
269};
270
271#define R__SLIST_IMPL(RTYPE, RTYPE_LOW, RDATA, RREF, FUNCSPECS) \
272FUNCSPECS RTYPE * RTYPE_LOW##_last (RTYPE * lst) \
273{ \
274 if (lst != NULL) while (lst->next != NULL) lst = lst->next; \
275 return lst; \
276} \
277FUNCSPECS RTYPE * RTYPE_LOW##_nth (RTYPE * lst, rsize n) \
278{ \
279 while (n-- > 0 && lst != NULL) lst = lst->next; \
280 return lst; \
281} \
282FUNCSPECS RTYPE * RTYPE_LOW##_copy (RTYPE * lst) \
283{ \
284 RTYPE * ret, * last; \
285 if (R_UNLIKELY (lst == NULL)) return NULL; \
286 ret = last = RTYPE_LOW##_alloc_copy (lst->data); \
287 for (lst = lst->next; lst != NULL; lst = lst->next, last = last->next) \
288 last->next = RTYPE_LOW##_alloc_copy (lst->data); \
289 return ret; \
290} \
291FUNCSPECS RTYPE * RTYPE_LOW##_merge (RTYPE * a, RTYPE * b) \
292{ \
293 if (a != NULL) \
294 RTYPE_LOW##_last (a)->next = b; \
295 else \
296 a = b; \
297 return a; \
298} \
299FUNCSPECS rsize RTYPE_LOW##_len (RTYPE * lst) \
300{ \
301 rsize ret = 0; \
302 for (; lst != NULL; lst = lst->next) ret++; \
303 return ret; \
304} \
305FUNCSPECS rboolean RTYPE_LOW##_contains_full (RTYPE * lst, RDATA data) \
306{ \
307 for (; lst != NULL; lst = lst->next) { \
308 if (RTYPE_LOW##_data_equal (&lst->data, &data)) \
309 return TRUE; \
310 } \
311 return FALSE; \
312} \
313FUNCSPECS void RTYPE_LOW##_foreach (RTYPE * lst, RFunc func, rpointer user) \
314{ \
315 for (; lst != NULL; lst = lst->next) \
316 func (RREF lst->data, user); \
317} \
318FUNCSPECS RTYPE * RTYPE_LOW##_alloc0 (void) \
319{ \
320 return r_mem_new0 (RTYPE); \
321} \
322FUNCSPECS RTYPE * RTYPE_LOW##_alloc_copy (RDATA data) \
323{ \
324 RTYPE * ret; \
325 if ((ret = r_mem_new (RTYPE)) != NULL) { \
326 ret->data = data; \
327 ret->next = NULL; \
328 } \
329 return ret; \
330} \
331FUNCSPECS RTYPE * RTYPE_LOW##_prepend_link (RTYPE * lst, RTYPE * entry) \
332{ \
333 entry->next = lst; \
334 return entry; \
335} \
336FUNCSPECS RTYPE * RTYPE_LOW##_append_link (RTYPE * lst, RTYPE * entry) \
337{ \
338 if (lst != NULL) { \
339 RTYPE * last = RTYPE_LOW##_last (lst); \
340 last->next = entry; \
341 entry = lst; \
342 } \
343 return entry; \
344} \
345FUNCSPECS RTYPE * RTYPE_LOW##_prepend_copy (RTYPE * lst, RDATA data) \
346{ \
347 return RTYPE_LOW##_prepend_link (lst, RTYPE_LOW##_alloc_copy (data)); \
348} \
349FUNCSPECS RTYPE * RTYPE_LOW##_append_copy (RTYPE * lst, RDATA data) \
350{ \
351 return RTYPE_LOW##_append_link (lst, RTYPE_LOW##_alloc_copy (data)); \
352} \
353FUNCSPECS RTYPE * RTYPE_LOW##_insert_after (RTYPE * head, RTYPE * entry, RDATA data) \
354{ \
355 RTYPE * lst = RTYPE_LOW##_alloc_copy (data); \
356 if (R_UNLIKELY (head == NULL)) return lst; \
357 if (entry == NULL) entry = head; \
358 lst->next = entry->next; \
359 entry->next = lst; \
360 return head; \
361} \
362FUNCSPECS void RTYPE_LOW##_free1 (RTYPE * lst) \
363{ \
364 RTYPE_LOW##_clear (lst); \
365 r_free (lst); \
366} \
367FUNCSPECS void RTYPE_LOW##_free1_full (RTYPE * lst, RDestroyNotify notify) \
368{ \
369 if (lst != NULL) { \
370 if (notify != NULL) notify (RREF lst->data); \
371 RTYPE_LOW##_free1 (lst); \
372 } \
373} \
374FUNCSPECS RTYPE * RTYPE_LOW##_remove (RTYPE * head, RDATA data) \
375{ \
376 RTYPE * ret = head, * prev; \
377 for (prev = NULL; head != NULL; head = head->next) { \
378 if (RTYPE_LOW##_data_equal (&head->data, &data)) { \
379 if (ret == head) ret = ret->next; \
380 if (prev != NULL) prev->next = head->next; \
381 RTYPE_LOW##_free1 (head); \
382 break; \
383 } \
384 prev = head; \
385 } \
386 return ret; \
387} \
388FUNCSPECS RTYPE * RTYPE_LOW##_remove_link (RTYPE * head, RTYPE * entry) \
389{ \
390 RTYPE * it; \
391 if (R_UNLIKELY (head == NULL || entry == NULL)) return head; \
392 if (head == entry) return head->next; \
393 for (it = head; it->next != NULL; it = it->next) { \
394 if (it->next == entry) { \
395 it->next = entry->next; \
396 break; \
397 } \
398 } \
399 return head; \
400} \
401FUNCSPECS rsize RTYPE_LOW##_foreach_remove (RTYPE ** head, \
402 RFuncReturn func, rpointer user) \
403{ \
404 rsize ret = 0; \
405 RTYPE * it, * prev; \
406 for (it = *head, prev = NULL; it != NULL; prev = it, it = it->next) { \
407 if (func (RREF it->data, user)) { \
408 if (prev != NULL) \
409 prev->next = it->next; \
410 else \
411 head = &it->next; \
412 RTYPE_LOW##_free1 (it); \
413 ret++; \
414 } \
415 } \
416 return ret; \
417} \
418FUNCSPECS RTYPE * RTYPE_LOW##_destroy_link (RTYPE * head, RTYPE * entry) \
419{ \
420 head = RTYPE_LOW##_remove_link (head, entry); \
421 RTYPE_LOW##_free1 (entry); \
422 return head; \
423} \
424FUNCSPECS void RTYPE_LOW##_destroy (RTYPE * head) \
425{ \
426 RTYPE * next; \
427 for (; head != NULL; head = next) { \
428 next = head->next; \
429 RTYPE_LOW##_free1 (head); \
430 } \
431} \
432FUNCSPECS void RTYPE_LOW##_destroy_full (RTYPE * head, RDestroyNotify notify) \
433{ \
434 RTYPE * next; \
435 for (; head != NULL; head = next) { \
436 next = head->next; \
437 RTYPE_LOW##_free1_full (head, notify); \
438 } \
439} \
440
441
442R_END_DECLS
443
444#endif /* __R_LIST_INTERNAL_H__ */
R_BEGIN_DECLS
#define R_BEGIN_DECLS
Open an extern "C" block under C++ (no-op in C).
Definition rmacros.h:196
rmem.h
Memory allocation, byte-buffer operations, and pattern scanning.
rtypes.h
Foundational type aliases used by every rlib header.