Blender  V3.3
BLI_linklist.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
12 #include <stdlib.h>
13 
14 #include "MEM_guardedalloc.h"
15 
16 #include "BLI_linklist.h"
17 #include "BLI_memarena.h"
18 #include "BLI_mempool.h"
19 #include "BLI_utildefines.h"
20 
21 #include "BLI_strict_flags.h"
22 
23 int BLI_linklist_count(const LinkNode *list)
24 {
25  int len;
26 
27  for (len = 0; list; list = list->next) {
28  len++;
29  }
30 
31  return len;
32 }
33 
34 int BLI_linklist_index(const LinkNode *list, void *ptr)
35 {
36  int index;
37 
38  for (index = 0; list; list = list->next, index++) {
39  if (list->link == ptr) {
40  return index;
41  }
42  }
43 
44  return -1;
45 }
46 
48 {
49  int i;
50 
51  for (i = 0; list; list = list->next, i++) {
52  if (i == index) {
53  return list;
54  }
55  }
56 
57  return NULL;
58 }
59 
61 {
62  if (list) {
63  while (list->next) {
64  list = list->next;
65  }
66  }
67  return list;
68 }
69 
71 {
72  LinkNode *rhead = NULL, *cur = *listp;
73 
74  while (cur) {
75  LinkNode *next = cur->next;
76 
77  cur->next = rhead;
78  rhead = cur;
79 
80  cur = next;
81  }
82 
83  *listp = rhead;
84 }
85 
86 void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index)
87 {
88  LinkNode *lnk, *lnk_psrc = NULL, *lnk_pdst = NULL;
89  int i;
90 
91  if (new_index == curr_index) {
92  return;
93  }
94 
95  if (new_index < curr_index) {
96  for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
97  if (i == new_index - 1) {
98  lnk_pdst = lnk;
99  }
100  else if (i == curr_index - 1) {
101  lnk_psrc = lnk;
102  break;
103  }
104  }
105 
106  if (!(lnk_psrc && lnk_psrc->next && (!lnk_pdst || lnk_pdst->next))) {
107  /* Invalid indices, abort. */
108  return;
109  }
110 
111  lnk = lnk_psrc->next;
112  lnk_psrc->next = lnk->next;
113  if (lnk_pdst) {
114  lnk->next = lnk_pdst->next;
115  lnk_pdst->next = lnk;
116  }
117  else {
118  /* destination is first element of the list... */
119  lnk->next = *listp;
120  *listp = lnk;
121  }
122  }
123  else {
124  for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) {
125  if (i == new_index) {
126  lnk_pdst = lnk;
127  break;
128  }
129  if (i == curr_index - 1) {
130  lnk_psrc = lnk;
131  }
132  }
133 
134  if (!(lnk_pdst && (!lnk_psrc || lnk_psrc->next))) {
135  /* Invalid indices, abort. */
136  return;
137  }
138 
139  if (lnk_psrc) {
140  lnk = lnk_psrc->next;
141  lnk_psrc->next = lnk->next;
142  }
143  else {
144  /* source is first element of the list... */
145  lnk = *listp;
146  *listp = lnk->next;
147  }
148  lnk->next = lnk_pdst->next;
149  lnk_pdst->next = lnk;
150  }
151 }
152 
153 void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
154 {
155  nlink->link = ptr;
156  nlink->next = *listp;
157  *listp = nlink;
158 }
159 
160 void BLI_linklist_prepend(LinkNode **listp, void *ptr)
161 {
162  LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
163  BLI_linklist_prepend_nlink(listp, ptr, nlink);
164 }
165 
167 {
168  LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
169  BLI_linklist_prepend_nlink(listp, ptr, nlink);
170 }
171 
172 void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
173 {
174  LinkNode *nlink = BLI_mempool_alloc(mempool);
175  BLI_linklist_prepend_nlink(listp, ptr, nlink);
176 }
177 
178 void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink)
179 {
180  nlink->link = ptr;
181  nlink->next = NULL;
182 
183  if (list_pair->list) {
184  BLI_assert((list_pair->last_node != NULL) && (list_pair->last_node->next == NULL));
185  list_pair->last_node->next = nlink;
186  }
187  else {
188  BLI_assert(list_pair->last_node == NULL);
189  list_pair->list = nlink;
190  }
191 
192  list_pair->last_node = nlink;
193 }
194 
195 void BLI_linklist_append(LinkNodePair *list_pair, void *ptr)
196 {
197  LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
198  BLI_linklist_append_nlink(list_pair, ptr, nlink);
199 }
200 
202 {
203  LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
204  BLI_linklist_append_nlink(list_pair, ptr, nlink);
205 }
206 
207 void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool)
208 {
209  LinkNode *nlink = BLI_mempool_alloc(mempool);
210  BLI_linklist_append_nlink(list_pair, ptr, nlink);
211 }
212 
213 void *BLI_linklist_pop(struct LinkNode **listp)
214 {
215  /* intentionally no NULL check */
216  void *link = (*listp)->link;
217  void *next = (*listp)->next;
218 
219  MEM_freeN(*listp);
220 
221  *listp = next;
222  return link;
223 }
224 
225 void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool)
226 {
227  /* intentionally no NULL check */
228  void *link = (*listp)->link;
229  void *next = (*listp)->next;
230 
231  BLI_mempool_free(mempool, (*listp));
232 
233  *listp = next;
234  return link;
235 }
236 
238 {
239  LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__);
240  LinkNode *node = *listp;
241 
242  nlink->link = ptr;
243 
244  if (node) {
245  nlink->next = node->next;
246  node->next = nlink;
247  }
248  else {
249  nlink->next = NULL;
250  *listp = nlink;
251  }
252 }
253 
255 {
256  while (list) {
257  LinkNode *next = list->next;
258 
259  if (freefunc) {
260  freefunc(list->link);
261  }
262  MEM_freeN(list);
263 
264  list = next;
265  }
266 }
267 
268 void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool)
269 {
270  while (list) {
271  LinkNode *next = list->next;
272 
273  if (freefunc) {
274  freefunc(list->link);
275  }
276  BLI_mempool_free(mempool, list);
277 
278  list = next;
279  }
280 }
281 
283 {
284  while (list) {
285  LinkNode *next = list->next;
286 
287  MEM_freeN(list->link);
288  MEM_freeN(list);
289 
290  list = next;
291  }
292 }
293 
294 void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
295 {
296  for (; list; list = list->next) {
297  applyfunc(list->link, userdata);
298  }
299 }
300 
301 /* -------------------------------------------------------------------- */
302 /* Sort */
303 #define SORT_IMPL_LINKTYPE LinkNode
304 #define SORT_IMPL_LINKTYPE_DATA link
305 
306 /* regular call */
307 #define SORT_IMPL_FUNC linklist_sort_fn
308 #include "list_sort_impl.h"
309 #undef SORT_IMPL_FUNC
310 
311 /* re-entrant call */
312 #define SORT_IMPL_USE_THUNK
313 #define SORT_IMPL_FUNC linklist_sort_fn_r
314 #include "list_sort_impl.h"
315 #undef SORT_IMPL_FUNC
316 #undef SORT_IMPL_USE_THUNK
317 
318 #undef SORT_IMPL_LINKTYPE
319 #undef SORT_IMPL_LINKTYPE_DATA
320 
321 LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *))
322 {
323  if (list && list->next) {
324  list = linklist_sort_fn(list, cmp);
325  }
326  return list;
327 }
328 
330  int (*cmp)(void *, const void *, const void *),
331  void *thunk)
332 {
333  if (list && list->next) {
334  list = linklist_sort_fn_r(list, cmp, thunk);
335  }
336  return list;
337 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
Read Guarded memory(de)allocation.
OperationNode * node
int len
Definition: draw_manager.c:108
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static ulong * next
LinkNode * last_node
Definition: BLI_linklist.h:34
LinkNode * list
Definition: BLI_linklist.h:34
void * link
Definition: BLI_linklist.h:24
struct LinkNode * next
Definition: BLI_linklist.h:23
PointerRNA * ptr
Definition: wm_files.c:3480