svn merge -r 21041:21301 https://svn.blender.org/svnroot/bf-blender/branches/blender2...
[blender.git] / source / blender / blenlib / intern / listbase.c
1 /* util.c
2  *
3  * various string, file, list operations.
4  *
5  *
6  * $Id$
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software Foundation,
22  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
23  *
24  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
25  * All rights reserved.
26  *
27  * The Original Code is: all of this file.
28  *
29  * Contributor(s): none yet.
30  *
31  * ***** END GPL LICENSE BLOCK *****
32  * 
33  */
34
35 #include <string.h>
36 #include <stdlib.h>
37
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_listBase.h"
42
43 #include "BLI_listbase.h"
44
45
46 /* implementation */
47
48 /* Ripped this from blender.c */
49 void addlisttolist(ListBase *list1, ListBase *list2)
50 {
51         if (list2->first==0) return;
52
53         if (list1->first==0) {
54                 list1->first= list2->first;
55                 list1->last= list2->last;
56         }
57         else {
58                 ((Link *)list1->last)->next= list2->first;
59                 ((Link *)list2->first)->prev= list1->last;
60                 list1->last= list2->last;
61         }
62         list2->first= list2->last= 0;
63 }
64
65 void BLI_addhead(ListBase *listbase, void *vlink)
66 {
67         Link *link= vlink;
68
69         if (link == NULL) return;
70         if (listbase == NULL) return;
71
72         link->next = listbase->first;
73         link->prev = NULL;
74
75         if (listbase->first) ((Link *)listbase->first)->prev = link;
76         if (listbase->last == NULL) listbase->last = link;
77         listbase->first = link;
78 }
79
80
81 void BLI_addtail(ListBase *listbase, void *vlink)
82 {
83         Link *link= vlink;
84
85         if (link == NULL) return;
86         if (listbase == NULL) return;
87
88         link->next = NULL;
89         link->prev = listbase->last;
90
91         if (listbase->last) ((Link *)listbase->last)->next = link;
92         if (listbase->first == 0) listbase->first = link;
93         listbase->last = link;
94 }
95
96
97 void BLI_remlink(ListBase *listbase, void *vlink)
98 {
99         Link *link= vlink;
100
101         if (link == NULL) return;
102         if (listbase == NULL) return;
103
104         if (link->next) link->next->prev = link->prev;
105         if (link->prev) link->prev->next = link->next;
106
107         if (listbase->last == link) listbase->last = link->prev;
108         if (listbase->first == link) listbase->first = link->next;
109 }
110
111
112 void BLI_freelinkN(ListBase *listbase, void *vlink)
113 {
114         Link *link= vlink;
115
116         if (link == NULL) return;
117         if (listbase == NULL) return;
118
119         BLI_remlink(listbase,link);
120         MEM_freeN(link);
121 }
122
123
124 void BLI_insertlink(ListBase *listbase, void *vprevlink, void *vnewlink)
125 {
126         Link *prevlink= vprevlink;
127         Link *newlink= vnewlink;
128
129         /* newlink comes after prevlink */
130         if (newlink == NULL) return;
131         if (listbase == NULL) return;
132         
133         /* empty list */
134         if (listbase->first == NULL) { 
135                 
136                 listbase->first= newlink;
137                 listbase->last= newlink;
138                 return;
139         }
140         
141         /* insert before first element */
142         if (prevlink == NULL) { 
143                 newlink->next= listbase->first;
144                 newlink->prev= 0;
145                 newlink->next->prev= newlink;
146                 listbase->first= newlink;
147                 return;
148         }
149
150         /* at end of list */
151         if (listbase->last== prevlink) 
152                 listbase->last = newlink;
153
154         newlink->next= prevlink->next;
155         prevlink->next= newlink;
156         if (newlink->next) newlink->next->prev= newlink;
157         newlink->prev= prevlink;
158 }
159
160 /* This uses insertion sort, so NOT ok for large list */
161 void BLI_sortlist(ListBase *listbase, int (*cmp)(void *, void *))
162 {
163         Link *current = NULL;
164         Link *previous = NULL;
165         Link *next = NULL;
166         
167         if (cmp == NULL) return;
168         if (listbase == NULL) return;
169
170         if (listbase->first != listbase->last)
171         {
172                 for( previous = listbase->first, current = previous->next; current; current = next )
173                 {
174                         next = current->next;
175                         previous = current->prev;
176                         
177                         BLI_remlink(listbase, current);
178                         
179                         while(previous && cmp(previous, current) == 1)
180                         {
181                                 previous = previous->prev;
182                         }
183                         
184                         BLI_insertlinkafter(listbase, previous, current);
185                 }
186         }
187 }
188
189 void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
190 {
191         Link *prevlink= vprevlink;
192         Link *newlink= vnewlink;
193
194         /* newlink before nextlink */
195         if (newlink == NULL) return;
196         if (listbase == NULL) return;
197
198         /* empty list */
199         if (listbase->first == NULL) { 
200                 listbase->first= newlink;
201                 listbase->last= newlink;
202                 return;
203         }
204         
205         /* insert at head of list */
206         if (prevlink == NULL) { 
207                 newlink->prev = NULL;
208                 newlink->next = listbase->first;
209                 ((Link *)listbase->first)->prev = newlink;
210                 listbase->first = newlink;
211                 return;
212         }
213
214         /* at end of list */
215         if (listbase->last == prevlink) 
216                 listbase->last = newlink;
217
218         newlink->next = prevlink->next;
219         newlink->prev = prevlink;
220         prevlink->next = newlink;
221         if (newlink->next) newlink->next->prev = newlink;
222 }
223
224 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
225 {
226         Link *nextlink= vnextlink;
227         Link *newlink= vnewlink;
228
229         /* newlink before nextlink */
230         if (newlink == NULL) return;
231         if (listbase == NULL) return;
232
233         /* empty list */
234         if (listbase->first == NULL) { 
235                 listbase->first= newlink;
236                 listbase->last= newlink;
237                 return;
238         }
239         
240         /* insert at end of list */
241         if (nextlink == NULL) { 
242                 newlink->prev= listbase->last;
243                 newlink->next= 0;
244                 ((Link *)listbase->last)->next= newlink;
245                 listbase->last= newlink;
246                 return;
247         }
248
249         /* at beginning of list */
250         if (listbase->first== nextlink) 
251                 listbase->first = newlink;
252
253         newlink->next= nextlink;
254         newlink->prev= nextlink->prev;
255         nextlink->prev= newlink;
256         if (newlink->prev) newlink->prev->next= newlink;
257 }
258
259
260 void BLI_freelist(ListBase *listbase)
261 {
262         Link *link, *next;
263
264         if (listbase == NULL) 
265                 return;
266         
267         link= listbase->first;
268         while (link) {
269                 next= link->next;
270                 free(link);
271                 link= next;
272         }
273         
274         listbase->first= NULL;
275         listbase->last= NULL;
276 }
277
278 void BLI_freelistN(ListBase *listbase)
279 {
280         Link *link, *next;
281
282         if (listbase == NULL) return;
283         
284         link= listbase->first;
285         while (link) {
286                 next= link->next;
287                 MEM_freeN(link);
288                 link= next;
289         }
290         
291         listbase->first= NULL;
292         listbase->last= NULL;
293 }
294
295
296 int BLI_countlist(ListBase *listbase)
297 {
298         Link *link;
299         int count = 0;
300         
301         if (listbase) {
302                 link = listbase->first;
303                 while (link) {
304                         count++;
305                         link= link->next;
306                 }
307         }
308         return count;
309 }
310
311 void *BLI_findlink(ListBase *listbase, int number)
312 {
313         Link *link = NULL;
314
315         if (number >= 0) {
316                 link = listbase->first;
317                 while (link != NULL && number != 0) {
318                         number--;
319                         link = link->next;
320                 }
321         }
322
323         return link;
324 }
325
326 int BLI_findindex(ListBase *listbase, void *vlink)
327 {
328         Link *link= NULL;
329         int number= 0;
330         
331         if (listbase == NULL) return -1;
332         if (vlink == NULL) return -1;
333         
334         link= listbase->first;
335         while (link) {
336                 if (link == vlink)
337                         return number;
338                 
339                 number++;
340                 link= link->next;
341         }
342         
343         return -1;
344 }
345
346 void BLI_duplicatelist(ListBase *list1, ListBase *list2)  /* copy from 2 to 1 */
347 {
348         struct Link *link1, *link2;
349         
350         list1->first= list1->last= 0;
351         
352         link2= list2->first;
353         while(link2) {
354                 
355                 link1= MEM_dupallocN(link2);
356                 BLI_addtail(list1, link1);
357                 
358                 link2= link2->next;
359         }       
360 }
361