Blender V5.3
BLI_linklist.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
12
13#include <cstdlib>
14
15#include "MEM_guardedalloc.h"
16
17#include "BLI_assert.hh"
18#include "BLI_linklist.hh"
19#include "BLI_memarena.hh"
20#include "BLI_mempool.hh"
21
22#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
23
24namespace blender {
25
27{
28 int len;
29
30 for (len = 0; list; list = list->next) {
31 len++;
32 }
33
34 return len;
35}
36
37int BLI_linklist_index(const LinkNode *list, const void *ptr)
38{
39 int index;
40
41 for (index = 0; list; list = list->next, index++) {
42 if (list->link == ptr) {
43 return index;
44 }
45 }
47 return -1;
48}
51{
52 int i;
53
54 for (i = 0; list; list = list->next, i++) {
55 if (i == index) {
56 return list;
57 }
58 }
60 return nullptr;
61}
63LinkNode *BLI_linklist_find_last(LinkNode *list)
64{
65 if (list) {
66 while (list->next) {
67 list = list->next;
68 }
69 }
70 return list;
74{
75 LinkNode *rhead = nullptr, *cur = *listp;
76
77 while (cur) {
78 LinkNode *next = cur->next;
79
80 cur->next = rhead;
81 rhead = cur;
82
83 cur = next;
84 }
85
86 *listp = rhead;
87}
88
89void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index)
90{
91 LinkNode *lnk, *lnk_psrc = nullptr, *lnk_pdst = nullptr;
92 int i;
93
94 if (new_index == curr_index) {
95 return;
96 }
97
98 if (new_index < curr_index) {
99 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
100 if (i == new_index - 1) {
101 lnk_pdst = lnk;
102 }
103 else if (i == curr_index - 1) {
104 lnk_psrc = lnk;
105 break;
106 }
107 }
108
109 if (!(lnk_psrc && lnk_psrc->next && (!lnk_pdst || lnk_pdst->next))) {
110 /* Invalid indices, abort. */
111 return;
112 }
113
114 lnk = lnk_psrc->next;
115 lnk_psrc->next = lnk->next;
116 if (lnk_pdst) {
117 lnk->next = lnk_pdst->next;
118 lnk_pdst->next = lnk;
119 }
120 else {
121 /* destination is first element of the list... */
122 lnk->next = *listp;
123 *listp = lnk;
125 }
126 else {
127 for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
128 if (i == new_index) {
129 lnk_pdst = lnk;
130 break;
131 }
132 if (i == curr_index - 1) {
133 lnk_psrc = lnk;
134 }
136
137 if (!(lnk_pdst && (!lnk_psrc || lnk_psrc->next))) {
138 /* Invalid indices, abort. */
139 return;
140 }
141
142 if (lnk_psrc) {
143 lnk = lnk_psrc->next;
144 lnk_psrc->next = lnk->next;
145 }
146 else {
147 /* source is first element of the list... */
148 lnk = *listp;
149 *listp = lnk->next;
150 }
151 lnk->next = lnk_pdst->next;
152 lnk_pdst->next = lnk;
154}
155
156void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
157{
158 nlink->link = ptr;
159 nlink->next = *listp;
160 *listp = nlink;
161}
162
163void BLI_linklist_prepend(LinkNode **listp, void *ptr)
164{
165 LinkNode *nlink = MEM_new_uninitialized<LinkNode>(__func__);
166 BLI_linklist_prepend_nlink(listp, ptr, nlink);
167}
168
169void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
170{
172 BLI_linklist_prepend_nlink(listp, ptr, nlink);
173}
174
175void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
176{
177 LinkNode *nlink = BLI_mempool_alloc<LinkNode>(mempool);
178 BLI_linklist_prepend_nlink(listp, ptr, nlink);
179}
180
181void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink)
182{
183 nlink->link = ptr;
184 nlink->next = nullptr;
185
186 if (list_pair->list) {
187 BLI_assert((list_pair->last_node != nullptr) && (list_pair->last_node->next == nullptr));
188 list_pair->last_node->next = nlink;
189 }
190 else {
191 BLI_assert(list_pair->last_node == nullptr);
192 list_pair->list = nlink;
193 }
194
195 list_pair->last_node = nlink;
196}
197
198void BLI_linklist_append(LinkNodePair *list_pair, void *ptr)
199{
200 LinkNode *nlink = MEM_new_uninitialized<LinkNode>(__func__);
201 BLI_linklist_append_nlink(list_pair, ptr, nlink);
202}
203
204void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, MemArena *ma)
205{
207 BLI_linklist_append_nlink(list_pair, ptr, nlink);
208}
209
210void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool)
211{
212 LinkNode *nlink = BLI_mempool_alloc<LinkNode>(mempool);
213 BLI_linklist_append_nlink(list_pair, ptr, nlink);
214}
215
217{
218 /* intentionally no nullptr check */
219 void *link = (*listp)->link;
220 LinkNode *next = (*listp)->next;
221
222 MEM_delete(*listp);
224 *listp = next;
225 return link;
226}
227
229{
230 /* intentionally no nullptr check */
231 void *link = (*listp)->link;
232 LinkNode *next = (*listp)->next;
233
234 BLI_mempool_free(mempool, (*listp));
235
236 *listp = next;
237 return link;
238}
239
240void BLI_linklist_insert_after(LinkNode **listp, void *ptr)
241{
242 LinkNode *nlink = MEM_new_zeroed<LinkNode>(__func__);
243 LinkNode *node = *listp;
244
245 nlink->link = ptr;
246
247 if (node) {
248 nlink->next = node->next;
249 node->next = nlink;
250 }
251 else {
252 nlink->next = nullptr;
253 *listp = nlink;
254 }
255}
256
258{
259 while (list) {
260 LinkNode *next = list->next;
261
262 if (freefunc) {
263 freefunc(list->link);
264 }
265 MEM_delete(list);
266
267 list = next;
269}
270
272{
273 while (list) {
274 LinkNode *next = list->next;
275
276 if (freefunc) {
277 freefunc(list->link);
278 }
279 BLI_mempool_free(mempool, list);
280
281 list = next;
282 }
283}
284
286{
287 while (list) {
288 LinkNode *next = list->next;
289
290 MEM_delete_void(list->link);
291 MEM_delete(list);
292
293 list = next;
294 }
295}
296
297void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
298{
299 for (; list; list = list->next) {
300 applyfunc(list->link, userdata);
301 }
302}
303
304/* -------------------------------------------------------------------- */
305/* Sort */
306#define SORT_IMPL_LINKTYPE LinkNode
307#define SORT_IMPL_LINKTYPE_DATA link
308
309/* regular call */
310#define SORT_IMPL_FUNC linklist_sort_fn
311#include "list_sort_impl.h"
312#undef SORT_IMPL_FUNC
313
314/* re-entrant call */
315#define SORT_IMPL_USE_THUNK
316#define SORT_IMPL_FUNC linklist_sort_fn_r
317#include "list_sort_impl.h"
318#undef SORT_IMPL_FUNC
319#undef SORT_IMPL_USE_THUNK
320
321#undef SORT_IMPL_LINKTYPE
322#undef SORT_IMPL_LINKTYPE_DATA
323
324LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *))
325{
326 if (list && list->next) {
327 list = linklist_sort_fn(list, cmp);
328 }
329 return list;
330}
331
333 int (*cmp)(void *, const void *, const void *),
334 void *thunk)
335{
336 if (list && list->next) {
337 list = linklist_sort_fn_r(list, cmp, thunk);
338 }
339 return list;
340}
341
342} // namespace blender
Read Blender memory allocation and freeing.
#define BLI_assert(a)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
void void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
LinkNode * BLI_linklist_sort(LinkNode *list, int(*cmp)(const void *, const void *)) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2)
void void void * BLI_linklist_pop(LinkNode **listp) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void void void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink) ATTR_NONNULL(1
void(*) LinkNodeApplyFP(void *link, void *userdata)
void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
LinkNode * BLI_linklist_sort_r(LinkNode *list, int(*cmp)(void *, const void *, const void *), void *thunk) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2)
void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index) ATTR_NONNULL(1)
void(*) LinkNodeFreeFP(void *link)
void void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1
void MEM_delete_void(void *vmemh)
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
int BLI_linklist_index(const LinkNode *list, const void *ptr) ATTR_WARN_UNUSED_RESULT
void BLI_linklist_freeN(LinkNode *list)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void void BLI_linklist_insert_after(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) ATTR_NONNULL(1
void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
LinkNode * BLI_linklist_find_last(LinkNode *list) ATTR_WARN_UNUSED_RESULT
LinkNode * BLI_linklist_find(LinkNode *list, int index) ATTR_WARN_UNUSED_RESULT
void * BLI_linklist_pop_pool(LinkNode **listp, struct BLI_mempool *mempool) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
void void void void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) ATTR_NONNULL(1)
void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
void BLI_linklist_reverse(LinkNode **listp) ATTR_NONNULL(1)
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
int BLI_linklist_count(const LinkNode *list) ATTR_WARN_UNUSED_RESULT
void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
struct LinkNode * next