BLI_math_rotation: properly name the quaternion power function.
[blender.git] / source / blender / blenlib / intern / listbase.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program 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
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  */
28
29 /** \file blender/blenlib/intern/listbase.c
30  *  \ingroup bli
31  *
32  * Manipulations on double-linked list (#ListBase structs).
33  *
34  * For single linked lists see 'BLI_linklist.h'
35  */
36
37 #include <string.h>
38 #include <stdlib.h>
39
40
41 #include "MEM_guardedalloc.h"
42
43 #include "DNA_listBase.h"
44
45 #include "BLI_listbase.h"
46
47 #include "BLI_strict_flags.h"
48
49 /* implementation */
50
51 /**
52  * moves the entire contents of \a src onto the end of \a dst.
53  */
54 void BLI_movelisttolist(ListBase *dst, ListBase *src)
55 {
56         if (src->first == NULL) return;
57
58         if (dst->first == NULL) {
59                 dst->first = src->first;
60                 dst->last = src->last;
61         }
62         else {
63                 ((Link *)dst->last)->next = src->first;
64                 ((Link *)src->first)->prev = dst->last;
65                 dst->last = src->last;
66         }
67         src->first = src->last = NULL;
68 }
69
70 /**
71  * moves the entire contents of \a src at the begining of \a dst.
72  */
73 void BLI_movelisttolist_reverse(ListBase *dst, ListBase *src)
74 {
75         if (src->first == NULL) return;
76
77         if (dst->first == NULL) {
78                 dst->first = src->first;
79                 dst->last = src->last;
80         }
81         else {
82                 ((Link *)src->last)->next = dst->first;
83                 ((Link *)dst->first)->prev = src->last;
84                 dst->first = src->first;
85         }
86
87         src->first = src->last = NULL;
88 }
89
90 /**
91  * Prepends \a vlink (assumed to begin with a Link) onto listbase.
92  */
93 void BLI_addhead(ListBase *listbase, void *vlink)
94 {
95         Link *link = vlink;
96
97         if (link == NULL) return;
98
99         link->next = listbase->first;
100         link->prev = NULL;
101
102         if (listbase->first) ((Link *)listbase->first)->prev = link;
103         if (listbase->last == NULL) listbase->last = link;
104         listbase->first = link;
105 }
106
107
108 /**
109  * Appends \a vlink (assumed to begin with a Link) onto listbase.
110  */
111 void BLI_addtail(ListBase *listbase, void *vlink)
112 {
113         Link *link = vlink;
114
115         if (link == NULL) return;
116
117         link->next = NULL;
118         link->prev = listbase->last;
119
120         if (listbase->last) ((Link *)listbase->last)->next = link;
121         if (listbase->first == NULL) listbase->first = link;
122         listbase->last = link;
123 }
124
125
126 /**
127  * Removes \a vlink from \a listbase. Assumes it is linked into there!
128  */
129 void BLI_remlink(ListBase *listbase, void *vlink)
130 {
131         Link *link = vlink;
132
133         if (link == NULL) return;
134
135         if (link->next) link->next->prev = link->prev;
136         if (link->prev) link->prev->next = link->next;
137
138         if (listbase->last == link) listbase->last = link->prev;
139         if (listbase->first == link) listbase->first = link->next;
140 }
141
142 /**
143  * Checks that \a vlink is linked into listbase, removing it from there if so.
144  */
145 bool BLI_remlink_safe(ListBase *listbase, void *vlink)
146 {
147         if (BLI_findindex(listbase, vlink) != -1) {
148                 BLI_remlink(listbase, vlink);
149                 return true;
150         }
151         else {
152                 return false;
153         }
154 }
155
156 /**
157  * Swaps \a vlinka and \a vlinkb in the list. Assumes they are both already in the list!
158  */
159 void BLI_listbase_swaplinks(ListBase *listbase, void *vlinka, void *vlinkb)
160 {
161         Link *linka = vlinka;
162         Link *linkb = vlinkb;
163
164         if (!linka || !linkb)
165                 return;
166
167         if (linkb->next == linka) {
168                 SWAP(Link *, linka, linkb);
169         }
170
171         if (linka->next == linkb) {
172                 linka->next = linkb->next;
173                 linkb->prev = linka->prev;
174                 linka->prev = linkb;
175                 linkb->next = linka;
176         }
177         else {  /* Non-contiguous items, we can safely swap. */
178                 SWAP(Link *, linka->prev, linkb->prev);
179                 SWAP(Link *, linka->next, linkb->next);
180         }
181
182         /* Update neighbors of linka and linkb. */
183         if (linka->prev) linka->prev->next = linka;
184         if (linka->next) linka->next->prev = linka;
185         if (linkb->prev) linkb->prev->next = linkb;
186         if (linkb->next) linkb->next->prev = linkb;
187
188         if (listbase->last == linka) listbase->last = linkb;
189         else if (listbase->last == linkb) listbase->last = linka;
190         if (listbase->first == linka) listbase->first = linkb;
191         else if (listbase->first == linkb) listbase->first = linka;
192 }
193
194 /**
195  * Swaps \a vlinka and \a vlinkb from their respective lists. Assumes they are both already in their lista!
196  */
197 void BLI_listbases_swaplinks(ListBase *listbasea, ListBase *listbaseb, void *vlinka, void *vlinkb)
198 {
199         Link *linka = vlinka;
200         Link *linkb = vlinkb;
201         Link linkc = {NULL};
202
203         if (!linka || !linkb) {
204                 return;
205         }
206
207         /* Temporary link to use as placeholder of the links positions */
208         BLI_insertlinkafter(listbasea, linka, &linkc);
209
210         /* Bring linka into linkb position */
211         BLI_remlink(listbasea, linka);
212         BLI_insertlinkafter(listbaseb, linkb, linka);
213
214         /* Bring linkb into linka position */
215         BLI_remlink(listbaseb, linkb);
216         BLI_insertlinkafter(listbasea, &linkc, linkb);
217
218         /* Remove temporary link */
219         BLI_remlink(listbasea, &linkc);
220 }
221
222 /**
223  * Removes the head from \a listbase and returns it.
224  */
225 void *BLI_pophead(ListBase *listbase)
226 {
227         Link *link;
228         if ((link = listbase->first)) {
229                 BLI_remlink(listbase, link);
230         }
231         return link;
232 }
233
234
235 /**
236  * Removes the tail from \a listbase and returns it.
237  */
238 void *BLI_poptail(ListBase *listbase)
239 {
240         Link *link;
241         if ((link = listbase->last)) {
242                 BLI_remlink(listbase, link);
243         }
244         return link;
245 }
246
247 /**
248  * Removes \a vlink from listbase and disposes of it. Assumes it is linked into there!
249  */
250 void BLI_freelinkN(ListBase *listbase, void *vlink)
251 {
252         Link *link = vlink;
253
254         if (link == NULL) return;
255
256         BLI_remlink(listbase, link);
257         MEM_freeN(link);
258 }
259
260 /**
261  * Assigns all #Link.prev pointers from #Link.next
262  */
263 static void listbase_double_from_single(Link *iter, ListBase *listbase)
264 {
265         Link *prev = NULL;
266         listbase->first = iter;
267         do {
268                 iter->prev = prev;
269                 prev = iter;
270         } while ((iter = iter->next));
271         listbase->last = prev;
272 }
273
274 #define SORT_IMPL_LINKTYPE Link
275
276 /* regular call */
277 #define SORT_IMPL_FUNC listbase_sort_fn
278 #include "list_sort_impl.h"
279 #undef SORT_IMPL_FUNC
280
281 /* reentrant call */
282 #define SORT_IMPL_USE_THUNK
283 #define SORT_IMPL_FUNC listbase_sort_fn_r
284 #include "list_sort_impl.h"
285 #undef SORT_IMPL_FUNC
286 #undef SORT_IMPL_USE_THUNK
287
288 #undef SORT_IMPL_LINKTYPE
289
290 /**
291  * Sorts the elements of listbase into the order defined by cmp
292  * (which should return 1 if its first arg should come after its second arg).
293  * This uses insertion sort, so NOT ok for large list.
294  */
295 void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *))
296 {
297         if (listbase->first != listbase->last) {
298                 Link *head = listbase->first;
299                 head = listbase_sort_fn(head, cmp);
300                 listbase_double_from_single(head, listbase);
301         }
302 }
303
304 void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk)
305 {
306         if (listbase->first != listbase->last) {
307                 Link *head = listbase->first;
308                 head = listbase_sort_fn_r(head, cmp, thunk);
309                 listbase_double_from_single(head, listbase);
310         }
311 }
312
313 /**
314  * Inserts \a vnewlink immediately following \a vprevlink in \a listbase.
315  * Or, if \a vprevlink is NULL, puts \a vnewlink at the front of the list.
316  */
317 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
318 {
319         Link *prevlink = vprevlink;
320         Link *newlink = vnewlink;
321
322         /* newlink before nextlink */
323         if (newlink == NULL) return;
324
325         /* empty list */
326         if (listbase->first == NULL) {
327                 listbase->first = newlink;
328                 listbase->last = newlink;
329                 return;
330         }
331
332         /* insert at head of list */
333         if (prevlink == NULL) {
334                 newlink->prev = NULL;
335                 newlink->next = listbase->first;
336                 newlink->next->prev = newlink;
337                 listbase->first = newlink;
338                 return;
339         }
340
341         /* at end of list */
342         if (listbase->last == prevlink) {
343                 listbase->last = newlink;
344         }
345
346         newlink->next = prevlink->next;
347         newlink->prev = prevlink;
348         prevlink->next = newlink;
349         if (newlink->next) {
350                 newlink->next->prev = newlink;
351         }
352 }
353
354 /**
355  * Inserts \a vnewlink immediately preceding \a vnextlink in listbase.
356  * Or, if \a vnextlink is NULL, puts \a vnewlink at the end of the list.
357  */
358 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
359 {
360         Link *nextlink = vnextlink;
361         Link *newlink = vnewlink;
362
363         /* newlink before nextlink */
364         if (newlink == NULL) return;
365
366         /* empty list */
367         if (listbase->first == NULL) {
368                 listbase->first = newlink;
369                 listbase->last = newlink;
370                 return;
371         }
372
373         /* insert at end of list */
374         if (nextlink == NULL) {
375                 newlink->prev = listbase->last;
376                 newlink->next = NULL;
377                 ((Link *)listbase->last)->next = newlink;
378                 listbase->last = newlink;
379                 return;
380         }
381
382         /* at beginning of list */
383         if (listbase->first == nextlink) {
384                 listbase->first = newlink;
385         }
386
387         newlink->next = nextlink;
388         newlink->prev = nextlink->prev;
389         nextlink->prev = newlink;
390         if (newlink->prev) {
391                 newlink->prev->next = newlink;
392         }
393 }
394
395
396 /**
397  * Insert a link in place of another, without changing it's position in the list.
398  *
399  * Puts `vnewlink` in the position of `vreplacelink`, removing `vreplacelink`.
400  * - `vreplacelink` *must* be in the list.
401  * - `vnewlink` *must not* be in the list.
402  */
403 void BLI_insertlinkreplace(ListBase *listbase, void *vreplacelink, void *vnewlink)
404 {
405         Link *l_old = vreplacelink;
406         Link *l_new = vnewlink;
407
408         /* update adjacent links */
409         if (l_old->next != NULL) {
410                 l_old->next->prev = l_new;
411         }
412         if (l_old->prev != NULL) {
413                 l_old->prev->next = l_new;
414         }
415
416         /* set direct links */
417         l_new->next = l_old->next;
418         l_new->prev = l_old->prev;
419
420          /* update list */
421         if (listbase->first == l_old) {
422                 listbase->first = l_new;
423         }
424         if (listbase->last == l_old) {
425                 listbase->last = l_new;
426         }
427 }
428
429 /**
430  * Reinsert \a vlink relative to its current position but offset by \a step. Doesn't move
431  * item if new position would exceed list (could optionally move to head/tail).
432  *
433  * \param step: Absolute value defines step size, sign defines direction. E.g pass -1
434  *              to move \a vlink before previous, or 1 to move behind next.
435  * \return If position of \a vlink has changed.
436  */
437 bool BLI_listbase_link_move(ListBase *listbase, void *vlink, int step)
438 {
439         Link *link = vlink;
440         Link *hook = link;
441         const bool is_up = step < 0;
442
443         if (step == 0) {
444                 return false;
445         }
446         BLI_assert(BLI_findindex(listbase, link) != -1);
447
448         /* find link to insert before/after */
449         for (int i = 0; i < ABS(step); i++) {
450                 hook = is_up ? hook->prev : hook->next;
451                 if (!hook) {
452                         return false;
453                 }
454         }
455
456         /* reinsert link */
457         BLI_remlink(listbase, vlink);
458         if (is_up) {
459                 BLI_insertlinkbefore(listbase, hook, vlink);
460         }
461         else {
462                 BLI_insertlinkafter(listbase, hook, vlink);
463         }
464         return true;
465 }
466
467
468 /**
469  * Removes and disposes of the entire contents of listbase using direct free(3).
470  */
471 void BLI_freelist(ListBase *listbase)
472 {
473         Link *link, *next;
474
475         link = listbase->first;
476         while (link) {
477                 next = link->next;
478                 free(link);
479                 link = next;
480         }
481
482         BLI_listbase_clear(listbase);
483 }
484
485 /**
486  * Removes and disposes of the entire contents of \a listbase using guardedalloc.
487  */
488 void BLI_freelistN(ListBase *listbase)
489 {
490         Link *link, *next;
491
492         link = listbase->first;
493         while (link) {
494                 next = link->next;
495                 MEM_freeN(link);
496                 link = next;
497         }
498
499         BLI_listbase_clear(listbase);
500 }
501
502 /**
503  * Returns the number of elements in \a listbase, up until (and including count_max)
504  *
505  * \note Use to avoid redundant looping.
506  */
507 int BLI_listbase_count_at_most(const ListBase *listbase, const int count_max)
508 {
509         Link *link;
510         int count = 0;
511
512         for (link = listbase->first; link && count != count_max; link = link->next) {
513                 count++;
514         }
515
516         return count;
517 }
518
519 /**
520  * Returns the number of elements in \a listbase.
521  */
522 int BLI_listbase_count(const ListBase *listbase)
523 {
524         Link *link;
525         int count = 0;
526
527         for (link = listbase->first; link; link = link->next) {
528                 count++;
529         }
530
531         return count;
532 }
533
534 /**
535  * Returns the nth element of \a listbase, numbering from 0.
536  */
537 void *BLI_findlink(const ListBase *listbase, int number)
538 {
539         Link *link = NULL;
540
541         if (number >= 0) {
542                 link = listbase->first;
543                 while (link != NULL && number != 0) {
544                         number--;
545                         link = link->next;
546                 }
547         }
548
549         return link;
550 }
551
552 /**
553  * Returns the nth-last element of \a listbase, numbering from 0.
554  */
555 void *BLI_rfindlink(const ListBase *listbase, int number)
556 {
557         Link *link = NULL;
558
559         if (number >= 0) {
560                 link = listbase->last;
561                 while (link != NULL && number != 0) {
562                         number--;
563                         link = link->prev;
564                 }
565         }
566
567         return link;
568 }
569
570 /**
571  * Returns the position of \a vlink within \a listbase, numbering from 0, or -1 if not found.
572  */
573 int BLI_findindex(const ListBase *listbase, const void *vlink)
574 {
575         Link *link = NULL;
576         int number = 0;
577
578         if (vlink == NULL) return -1;
579
580         link = listbase->first;
581         while (link) {
582                 if (link == vlink)
583                         return number;
584
585                 number++;
586                 link = link->next;
587         }
588
589         return -1;
590 }
591
592 /**
593  * Finds the first element of \a listbase which contains the null-terminated
594  * string \a id at the specified offset, returning NULL if not found.
595  */
596 void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
597 {
598         Link *link = NULL;
599         const char *id_iter;
600
601         if (id == NULL)
602                 return NULL;
603
604         for (link = listbase->first; link; link = link->next) {
605                 id_iter = ((const char *)link) + offset;
606
607                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
608                         return link;
609                 }
610         }
611
612         return NULL;
613 }
614 /* same as above but find reverse */
615 /**
616  * Finds the last element of \a listbase which contains the
617  * null-terminated string \a id at the specified offset, returning NULL if not found.
618  */
619 void *BLI_rfindstring(const ListBase *listbase, const char *id, const int offset)
620 {
621         Link *link = NULL;
622         const char *id_iter;
623
624         for (link = listbase->last; link; link = link->prev) {
625                 id_iter = ((const char *)link) + offset;
626
627                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
628                         return link;
629                 }
630         }
631
632         return NULL;
633 }
634
635 /**
636  * Finds the first element of \a listbase which contains a pointer to the
637  * null-terminated string \a id at the specified offset, returning NULL if not found.
638  */
639 void *BLI_findstring_ptr(const ListBase *listbase, const char *id, const int offset)
640 {
641         Link *link = NULL;
642         const char *id_iter;
643
644         for (link = listbase->first; link; link = link->next) {
645                 /* exact copy of BLI_findstring(), except for this line */
646                 id_iter = *((const char **)(((const char *)link) + offset));
647
648                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
649                         return link;
650                 }
651         }
652
653         return NULL;
654 }
655 /* same as above but find reverse */
656 /**
657  * Finds the last element of \a listbase which contains a pointer to the
658  * null-terminated string \a id at the specified offset, returning NULL if not found.
659  */
660 void *BLI_rfindstring_ptr(const ListBase *listbase, const char *id, const int offset)
661 {
662         Link *link = NULL;
663         const char *id_iter;
664
665         for (link = listbase->last; link; link = link->prev) {
666                 /* exact copy of BLI_rfindstring(), except for this line */
667                 id_iter = *((const char **)(((const char *)link) + offset));
668
669                 if (id[0] == id_iter[0] && STREQ(id, id_iter)) {
670                         return link;
671                 }
672         }
673
674         return NULL;
675 }
676
677 /**
678  * Finds the first element of listbase which contains the specified pointer value
679  * at the specified offset, returning NULL if not found.
680  */
681 void *BLI_findptr(const ListBase *listbase, const void *ptr, const int offset)
682 {
683         Link *link = NULL;
684         const void *ptr_iter;
685
686         for (link = listbase->first; link; link = link->next) {
687                 /* exact copy of BLI_findstring(), except for this line */
688                 ptr_iter = *((const void **)(((const char *)link) + offset));
689
690                 if (ptr == ptr_iter) {
691                         return link;
692                 }
693         }
694
695         return NULL;
696 }
697 /* same as above but find reverse */
698 /**
699  * Finds the last element of listbase which contains the specified pointer value
700  * at the specified offset, returning NULL if not found.
701  */
702 void *BLI_rfindptr(const ListBase *listbase, const void *ptr, const int offset)
703 {
704         Link *link = NULL;
705         const void *ptr_iter;
706
707         for (link = listbase->last; link; link = link->prev) {
708                 /* exact copy of BLI_rfindstring(), except for this line */
709                 ptr_iter = *((const void **)(((const char *)link) + offset));
710
711                 if (ptr == ptr_iter) {
712                         return link;
713                 }
714         }
715
716         return NULL;
717 }
718
719 /**
720  * Finds the first element of listbase which contains the specified bytes
721  * at the specified offset, returning NULL if not found.
722  */
723 void *BLI_listbase_bytes_find(const ListBase *listbase, const void *bytes, const size_t bytes_size, const int offset)
724 {
725         Link *link = NULL;
726         const void *ptr_iter;
727
728         for (link = listbase->first; link; link = link->next) {
729                 ptr_iter = (const void *)(((const char *)link) + offset);
730
731                 if (memcmp(bytes, ptr_iter, bytes_size) == 0) {
732                         return link;
733                 }
734         }
735
736         return NULL;
737 }
738 /* same as above but find reverse */
739 /**
740  * Finds the last element of listbase which contains the specified bytes
741  * at the specified offset, returning NULL if not found.
742  */
743 void *BLI_listbase_bytes_rfind(const ListBase *listbase, const void *bytes, const size_t bytes_size, const int offset)
744 {
745         Link *link = NULL;
746         const void *ptr_iter;
747
748         for (link = listbase->last; link; link = link->prev) {
749                 ptr_iter = (const void *)(((const char *)link) + offset);
750
751                 if (memcmp(bytes, ptr_iter, bytes_size) == 0) {
752                         return link;
753                 }
754         }
755
756         return NULL;
757 }
758
759 /**
760  * Returns the 0-based index of the first element of listbase which contains the specified
761  * null-terminated string at the specified offset, or -1 if not found.
762  */
763 int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset)
764 {
765         Link *link = NULL;
766         const char *id_iter;
767         int i = 0;
768
769         link = listbase->first;
770         while (link) {
771                 id_iter = ((const char *)link) + offset;
772
773                 if (id[0] == id_iter[0] && STREQ(id, id_iter))
774                         return i;
775                 i++;
776                 link = link->next;
777         }
778
779         return -1;
780 }
781
782 /**
783  * Sets dst to a duplicate of the entire contents of src. dst may be the same as src.
784  */
785 void BLI_duplicatelist(ListBase *dst, const ListBase *src)
786 {
787         struct Link *dst_link, *src_link;
788
789         /* in this order, to ensure it works if dst == src */
790         src_link = src->first;
791         dst->first = dst->last = NULL;
792
793         while (src_link) {
794                 dst_link = MEM_dupallocN(src_link);
795                 BLI_addtail(dst, dst_link);
796
797                 src_link = src_link->next;
798         }
799 }
800
801 void BLI_listbase_reverse(ListBase *lb)
802 {
803         struct Link *curr = lb->first;
804         struct Link *prev = NULL;
805         struct Link *next = NULL;
806         while (curr) {
807                 next = curr->next;
808                 curr->next = prev;
809                 curr->prev = next;
810                 prev = curr;
811                 curr = next;
812         }
813
814         /* swap first/last */
815         curr = lb->first;
816         lb->first = lb->last;
817         lb->last = curr;
818 }
819
820 /**
821  * \param vlink: Link to make first.
822  */
823 void BLI_listbase_rotate_first(ListBase *lb, void *vlink)
824 {
825         /* make circular */
826         ((Link *)lb->first)->prev = lb->last;
827         ((Link *)lb->last)->next = lb->first;
828
829         lb->first = vlink;
830         lb->last = ((Link *)vlink)->prev;
831
832         ((Link *)lb->first)->prev = NULL;
833         ((Link *)lb->last)->next = NULL;
834 }
835
836 /**
837  * \param vlink: Link to make last.
838  */
839 void BLI_listbase_rotate_last(ListBase *lb, void *vlink)
840 {
841         /* make circular */
842         ((Link *)lb->first)->prev = lb->last;
843         ((Link *)lb->last)->next = lb->first;
844
845         lb->first = ((Link *)vlink)->next;
846         lb->last = vlink;
847
848         ((Link *)lb->first)->prev = NULL;
849         ((Link *)lb->last)->next = NULL;
850 }
851
852 /* create a generic list node containing link to provided data */
853 LinkData *BLI_genericNodeN(void *data)
854 {
855         LinkData *ld;
856
857         if (data == NULL)
858                 return NULL;
859
860         /* create new link, and make it hold the given data */
861         ld = MEM_callocN(sizeof(LinkData), __func__);
862         ld->data = data;
863
864         return ld;
865 }