Merged changes in the trunk up to revision 45619.
[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                 for (previous = listbase->first, current = previous->next; current; current = next) {
187                         next = current->next;
188                         previous = current->prev;
189                         
190                         BLI_remlink(listbase, current);
191                         
192                         while (previous && cmp(previous, current) == 1)
193                         {
194                                 previous = previous->prev;
195                         }
196                         
197                         BLI_insertlinkafter(listbase, previous, current);
198                 }
199         }
200 }
201
202 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
203 {
204         Link *prevlink= vprevlink;
205         Link *newlink= vnewlink;
206
207         /* newlink before nextlink */
208         if (newlink == NULL) return;
209         if (listbase == NULL) return;
210
211         /* empty list */
212         if (listbase->first == NULL) { 
213                 listbase->first= newlink;
214                 listbase->last= newlink;
215                 return;
216         }
217         
218         /* insert at head of list */
219         if (prevlink == NULL) { 
220                 newlink->prev = NULL;
221                 newlink->next = listbase->first;
222                 ((Link *)listbase->first)->prev = newlink;
223                 listbase->first = newlink;
224                 return;
225         }
226
227         /* at end of list */
228         if (listbase->last == prevlink) 
229                 listbase->last = newlink;
230
231         newlink->next = prevlink->next;
232         newlink->prev = prevlink;
233         prevlink->next = newlink;
234         if (newlink->next) newlink->next->prev = newlink;
235 }
236
237 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
238 {
239         Link *nextlink= vnextlink;
240         Link *newlink= vnewlink;
241
242         /* newlink before nextlink */
243         if (newlink == NULL) return;
244         if (listbase == NULL) return;
245
246         /* empty list */
247         if (listbase->first == NULL) { 
248                 listbase->first= newlink;
249                 listbase->last= newlink;
250                 return;
251         }
252         
253         /* insert at end of list */
254         if (nextlink == NULL) { 
255                 newlink->prev= listbase->last;
256                 newlink->next= NULL;
257                 ((Link *)listbase->last)->next= newlink;
258                 listbase->last= newlink;
259                 return;
260         }
261
262         /* at beginning of list */
263         if (listbase->first== nextlink) 
264                 listbase->first = newlink;
265
266         newlink->next= nextlink;
267         newlink->prev= nextlink->prev;
268         nextlink->prev= newlink;
269         if (newlink->prev) newlink->prev->next= newlink;
270 }
271
272
273 void BLI_freelist(ListBase *listbase)
274 {
275         Link *link, *next;
276
277         if (listbase == NULL) 
278                 return;
279         
280         link= listbase->first;
281         while (link) {
282                 next= link->next;
283                 free(link);
284                 link= next;
285         }
286         
287         listbase->first= NULL;
288         listbase->last= NULL;
289 }
290
291 void BLI_freelistN(ListBase *listbase)
292 {
293         Link *link, *next;
294
295         if (listbase == NULL) return;
296         
297         link= listbase->first;
298         while (link) {
299                 next= link->next;
300                 MEM_freeN(link);
301                 link= next;
302         }
303         
304         listbase->first= NULL;
305         listbase->last= NULL;
306 }
307
308
309 int BLI_countlist(const ListBase *listbase)
310 {
311         Link *link;
312         int count = 0;
313         
314         if (listbase) {
315                 link = listbase->first;
316                 while (link) {
317                         count++;
318                         link= link->next;
319                 }
320         }
321         return count;
322 }
323
324 void *BLI_findlink(const ListBase *listbase, int number)
325 {
326         Link *link = NULL;
327
328         if (number >= 0) {
329                 link = listbase->first;
330                 while (link != NULL && number != 0) {
331                         number--;
332                         link = link->next;
333                 }
334         }
335
336         return link;
337 }
338
339 void *BLI_rfindlink(const ListBase *listbase, int number)
340 {
341         Link *link = NULL;
342
343         if (number >= 0) {
344                 link = listbase->last;
345                 while (link != NULL && number != 0) {
346                         number--;
347                         link = link->prev;
348                 }
349         }
350
351         return link;
352 }
353
354 int BLI_findindex(const ListBase *listbase, void *vlink)
355 {
356         Link *link= NULL;
357         int number= 0;
358         
359         if (listbase == NULL) return -1;
360         if (vlink == NULL) return -1;
361         
362         link= listbase->first;
363         while (link) {
364                 if (link == vlink)
365                         return number;
366                 
367                 number++;
368                 link= link->next;
369         }
370         
371         return -1;
372 }
373
374 void *BLI_findstring(const ListBase *listbase, const char *id, const int offset)
375 {
376         Link *link= NULL;
377         const char *id_iter;
378
379         if (listbase == NULL) return NULL;
380
381         for (link= listbase->first; link; link= link->next) {
382                 id_iter= ((const char *)link) + offset;
383
384                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
385                         return link;
386                 }
387         }
388
389         return NULL;
390 }
391 /* same as above but find reverse */
392 void *BLI_rfindstring(const ListBase *listbase, const char *id, const int offset)
393 {
394         Link *link= NULL;
395         const char *id_iter;
396
397         if (listbase == NULL) return NULL;
398
399         for (link= listbase->last; link; link= link->prev) {
400                 id_iter= ((const char *)link) + offset;
401
402                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
403                         return link;
404                 }
405         }
406
407         return NULL;
408 }
409
410 void *BLI_findstring_ptr(const ListBase *listbase, const char *id, const int offset)
411 {
412         Link *link= NULL;
413         const char *id_iter;
414
415         if (listbase == NULL) return NULL;
416
417         for (link= listbase->first; link; link= link->next) {
418                 /* exact copy of BLI_findstring(), except for this line */
419                 id_iter= *((const char **)(((const char *)link) + offset));
420
421                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
422                         return link;
423                 }
424         }
425
426         return NULL;
427 }
428 /* same as above but find reverse */
429 void *BLI_rfindstring_ptr(const ListBase *listbase, const char *id, const int offset)
430 {
431         Link *link= NULL;
432         const char *id_iter;
433
434         if (listbase == NULL) return NULL;
435
436         for (link= listbase->last; link; link= link->prev) {
437                 /* exact copy of BLI_rfindstring(), except for this line */
438                 id_iter= *((const char **)(((const char *)link) + offset));
439
440                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0) {
441                         return link;
442                 }
443         }
444
445         return NULL;
446 }
447
448 int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset)
449 {
450         Link *link= NULL;
451         const char *id_iter;
452         int i= 0;
453
454         if (listbase == NULL) return -1;
455
456         link= listbase->first;
457         while (link) {
458                 id_iter= ((const char *)link) + offset;
459
460                 if (id[0] == id_iter[0] && strcmp(id, id_iter)==0)
461                         return i;
462                 i++;
463                 link= link->next;
464         }
465
466         return -1;
467 }
468
469 void BLI_duplicatelist(ListBase *dst, const ListBase *src)
470 {
471         struct Link *dst_link, *src_link;
472
473         /* in this order, to ensure it works if dst == src */
474         src_link= src->first;
475         dst->first= dst->last= NULL;
476
477         while (src_link) {
478                 dst_link= MEM_dupallocN(src_link);
479                 BLI_addtail(dst, dst_link);
480
481                 src_link= src_link->next;
482         }
483 }
484
485 /* create a generic list node containing link to provided data */
486 LinkData *BLI_genericNodeN (void *data)
487 {
488         LinkData *ld;
489         
490         if (data == NULL)
491                 return NULL;
492                 
493         /* create new link, and make it hold the given data */
494         ld= MEM_callocN(sizeof(LinkData), "BLI_genericNodeN()");
495         ld->data= data;
496         
497         return ld;
498