6155bf83a57be4b33d2e72881e4b97c15b82499d
[blender.git] / source / blender / blenlib / intern / listbase.c
1 /* util.c
2  *
3  * various string, file, list operations.
4  *
5  *
6  *
7  * ***** BEGIN GPL LICENSE BLOCK *****
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  * 
32  */
33
34 /** \file blender/blenlib/intern/listbase.c
35  *  \ingroup bli
36  */
37
38
39 #include <string.h>
40 #include <stdlib.h>
41
42
43 #include "MEM_guardedalloc.h"
44
45 #include "DNA_listBase.h"
46
47 #include "BLI_listbase.h"
48
49
50 /* implementation */
51
52 /* Ripped this from blender.c */
53 void BLI_movelisttolist(ListBase *dst, ListBase *src)
54 {
55         if (src->first==NULL) return;
56
57         if (dst->first==NULL) {
58                 dst->first= src->first;
59                 dst->last= src->last;
60         }
61         else {
62                 ((Link *)dst->last)->next= src->first;
63                 ((Link *)src->first)->prev= dst->last;
64                 dst->last= src->last;
65         }
66         src->first= src->last= NULL;
67 }
68
69 void BLI_addhead(ListBase *listbase, void *vlink)
70 {
71         Link *link= vlink;
72
73         if (link == NULL) return;
74         if (listbase == NULL) return;
75
76         link->next = listbase->first;
77         link->prev = NULL;
78
79         if (listbase->first) ((Link *)listbase->first)->prev = link;
80         if (listbase->last == NULL) listbase->last = link;
81         listbase->first = link;
82 }
83
84
85 void BLI_addtail(ListBase *listbase, void *vlink)
86 {
87         Link *link= vlink;
88
89         if (link == NULL) return;
90         if (listbase == NULL) return;
91
92         link->next = NULL;
93         link->prev = listbase->last;
94
95         if (listbase->last) ((Link *)listbase->last)->next = link;
96         if (listbase->first == NULL) listbase->first = link;
97         listbase->last = link;
98 }
99
100
101 void BLI_remlink(ListBase *listbase, void *vlink)
102 {
103         Link *link= vlink;
104
105         if (link == NULL) return;
106         if (listbase == NULL) return;
107
108         if (link->next) link->next->prev = link->prev;
109         if (link->prev) link->prev->next = link->next;
110
111         if (listbase->last == link) listbase->last = link->prev;
112         if (listbase->first == link) listbase->first = link->next;
113 }
114
115 int BLI_remlink_safe(ListBase *listbase, void *vlink)
116 {
117         if(BLI_findindex(listbase, vlink) != -1) {
118                 BLI_remlink(listbase, vlink);
119                 return 1;
120         }
121         else {
122                 return 0;
123         }
124 }
125
126
127 void BLI_freelinkN(ListBase *listbase, void *vlink)
128 {
129         Link *link= vlink;
130
131         if (link == NULL) return;
132         if (listbase == NULL) return;
133
134         BLI_remlink(listbase,link);
135         MEM_freeN(link);
136 }
137
138
139 void BLI_insertlink(ListBase *listbase, void *vprevlink, void *vnewlink)
140 {
141         Link *prevlink= vprevlink;
142         Link *newlink= vnewlink;
143
144         /* newlink comes after prevlink */
145         if (newlink == NULL) return;
146         if (listbase == NULL) return;
147         
148         /* empty list */
149         if (listbase->first == NULL) { 
150                 
151                 listbase->first= newlink;
152                 listbase->last= newlink;
153                 return;
154         }
155         
156         /* insert before first element */
157         if (prevlink == NULL) { 
158                 newlink->next= listbase->first;
159                 newlink->prev= NULL;
160                 newlink->next->prev= newlink;
161                 listbase->first= newlink;
162                 return;
163         }
164
165         /* at end of list */
166         if (listbase->last== prevlink) 
167                 listbase->last = newlink;
168
169         newlink->next= prevlink->next;
170         prevlink->next= newlink;
171         if (newlink->next) newlink->next->prev= newlink;
172         newlink->prev= prevlink;
173 }
174
175 /* This uses insertion sort, so NOT ok for large list */
176 void BLI_sortlist(ListBase *listbase, int (*cmp)(void *, void *))
177 {
178         Link *current = NULL;
179         Link *previous = NULL;
180         Link *next = NULL;
181         
182         if (cmp == NULL) return;
183         if (listbase == NULL) return;
184
185         if (listbase->first != listbase->last)
186         {
187                 for( previous = listbase->first, current = previous->next; current; current = next )
188                 {
189                         next = current->next;
190                         previous = current->prev;
191                         
192                         BLI_remlink(listbase, current);
193                         
194                         while(previous && cmp(previous, current) == 1)
195                         {
196                                 previous = previous->prev;
197                         }
198                         
199                         BLI_insertlinkafter(listbase, previous, current);
200                 }
201         }
202 }
203
204 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
205 {
206         Link *prevlink= vprevlink;
207         Link *newlink= vnewlink;
208
209         /* newlink before nextlink */
210         if (newlink == NULL) return;
211         if (listbase == NULL) return;
212
213         /* empty list */
214         if (listbase->first == NULL) { 
215                 listbase->first= newlink;
216                 listbase->last= newlink;
217                 return;
218         }
219         
220         /* insert at head of list */
221         if (prevlink == NULL) { 
222                 newlink->prev = NULL;
223                 newlink->next = listbase->first;
224                 ((Link *)listbase->first)->prev = newlink;
225                 listbase->first = newlink;
226                 return;
227         }
228
229         /* at end of list */
230         if (listbase->last == prevlink) 
231                 listbase->last = newlink;
232
233         newlink->next = prevlink->next;
234         newlink->prev = prevlink;
235         prevlink->next = newlink;
236         if (newlink->next) newlink->next->prev = newlink;
237 }
238
239 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
240 {
241         Link *nextlink= vnextlink;
242         Link *newlink= vnewlink;
243
244         /* newlink before nextlink */
245         if (newlink == NULL) return;
246         if (listbase == NULL) return;
247
248         /* empty list */
249         if (listbase->first == NULL) { 
250                 listbase->first= newlink;
251                 listbase->last= newlink;
252                 return;
253         }
254         
255         /* insert at end of list */
256         if (nextlink == NULL) { 
257                 newlink->prev= listbase->last;
258                 newlink->next= NULL;
259                 ((Link *)listbase->last)->next= newlink;
260                 listbase->last= newlink;
261                 return;
262         }
263
264         /* at beginning of list */
265         if (listbase->first== nextlink) 
266                 listbase->first = newlink;
267
268         newlink->next= nextlink;
269         newlink->prev= nextlink->prev;
270         nextlink->prev= newlink;
271         if (newlink->prev) newlink->prev->next= newlink;
272 }
273
274
275 void BLI_freelist(ListBase *listbase)
276 {
277         Link *link, *next;
278
279         if (listbase == NULL) 
280                 return;
281         
282         link= listbase->first;
283         while (link) {
284                 next= link->next;
285                 free(link);
286                 link= next;
287         }
288         
289         listbase->first= NULL;
290         listbase->last= NULL;
291 }
292
293 void BLI_freelistN(ListBase *listbase)
294 {
295         Link *link, *next;
296
297         if (listbase == NULL) return;
298         
299         link= listbase->first;
300         while (link) {
301                 next= link->next;
302                 MEM_freeN(link);
303                 link= next;
304         }
305         
306         listbase->first= NULL;
307         listbase->last= NULL;
308 }
309
310
311 int BLI_countlist(const ListBase *listbase)
312 {
313         Link *link;
314         int count = 0;
315         
316         if (listbase) {
317                 link = listbase->first;
318                 while (link) {
319                         count++;
320                         link= link->next;
321                 }
322         }
323         return count;
324 }
325
326 void *BLI_findlink(const ListBase *listbase, int number)
327 {
328         Link *link = NULL;
329
330         if (number >= 0) {
331                 link = listbase->first;
332                 while (link != NULL && number != 0) {
333                         number--;
334                         link = link->next;
335                 }
336         }
337
338         return link;
339 }
340
341 void *BLI_rfindlink(const ListBase *listbase, int number)
342 {
343         Link *link = NULL;
344
345         if (number >= 0) {
346                 link = listbase->last;
347                 while (link != NULL && number != 0) {
348                         number--;
349                         link = link->prev;
350                 }
351         }
352
353         return link;
354 }
355
356 int BLI_findindex(const ListBase *listbase, void *vlink)
357 {
358         Link *link= NULL;
359         int number= 0;
360         
361         if (listbase == NULL) return -1;
362         if (vlink == NULL) return -1;
363         
364         link= listbase->first;
365         while (link) {
366                 if (link == vlink)
367                         return number;
368                 
369                 number++;
370                 link= link->next;
371         }
372         
373         return -1;
374 }
375
376 void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
377 {
378         Link *link= NULL;
379         const char *id_iter;
380
381         if (listbase == NULL) return NULL;
382
383         for (link= listbase->first; link; link= link->next) {
384                 id_iter= ((const char *)link) + offset;
385
386                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
387                         return link;
388                 }
389         }
390
391         return NULL;
392 }
393 /* same as above but find reverse */
394 void *BLI_rfindstring(const ListBase *listbase, const char *id, const int offset)
395 {
396         Link *link= NULL;
397         const char *id_iter;
398
399         if (listbase == NULL) return NULL;
400
401         for (link= listbase->last; link; link= link->prev) {
402                 id_iter= ((const char *)link) + offset;
403
404                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
405                         return link;
406                 }
407         }
408
409         return NULL;
410 }
411
412 void *BLI_findstring_ptr(const ListBase *listbase, const char *id, const int offset)
413 {
414         Link *link= NULL;
415         const char *id_iter;
416
417         if (listbase == NULL) return NULL;
418
419         for (link= listbase->first; link; link= link->next) {
420                 /* exact copy of BLI_findstring(), except for this line */
421                 id_iter= *((const char **)(((const char *)link) + offset));
422
423                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
424                         return link;
425                 }
426         }
427
428         return NULL;
429 }
430 /* same as above but find reverse */
431 void *BLI_rfindstring_ptr(const ListBase *listbase, const char *id, const int offset)
432 {
433         Link *link= NULL;
434         const char *id_iter;
435
436         if (listbase == NULL) return NULL;
437
438         for (link= listbase->last; link; link= link->prev) {
439                 /* exact copy of BLI_rfindstring(), except for this line */
440                 id_iter= *((const char **)(((const char *)link) + offset));
441
442                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
443                         return link;
444                 }
445         }
446
447         return NULL;
448 }
449
450 int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset)
451 {
452         Link *link= NULL;
453         const char *id_iter;
454         int i= 0;
455
456         if (listbase == NULL) return -1;
457
458         link= listbase->first;
459         while (link) {
460                 id_iter= ((const char *)link) + offset;
461
462                 if(id[0] == id_iter[0] && strcmp(id, id_iter)==0)
463                         return i;
464                 i++;
465                 link= link->next;
466         }
467
468         return -1;
469 }
470
471 void BLI_duplicatelist(ListBase *dst, const ListBase *src)
472 {
473         struct Link *dst_link, *src_link;
474
475         /* in this order, to ensure it works if dst == src */
476         src_link= src->first;
477         dst->first= dst->last= NULL;
478
479         while(src_link) {
480                 dst_link= MEM_dupallocN(src_link);
481                 BLI_addtail(dst, dst_link);
482
483                 src_link= src_link->next;
484         }
485 }
486
487 /* create a generic list node containing link to provided data */
488 LinkData *BLI_genericNodeN (void *data)
489 {
490         LinkData *ld;
491         
492         if (data == NULL)
493                 return NULL;
494                 
495         /* create new link, and make it hold the given data */
496         ld= MEM_callocN(sizeof(LinkData), "BLI_genericNodeN()");
497         ld->data= data;
498         
499         return ld;
500