Merging r58196 through r58265 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / blenlib / intern / BLI_linklist.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  * Support for linked lists.
27  */
28
29 /** \file blender/blenlib/intern/BLI_linklist.c
30  *  \ingroup bli
31  */
32
33
34 #include "MEM_guardedalloc.h"
35 #include "BLI_linklist.h"
36 #include "BLI_memarena.h"
37
38 int BLI_linklist_length(LinkNode *list)
39 {
40         if (0) {
41                 return list ? (1 + BLI_linklist_length(list->next)) : 0;
42         }
43         else {
44                 int len;
45
46                 for (len = 0; list; list = list->next)
47                         len++;
48         
49                 return len;
50         }
51 }
52
53 int BLI_linklist_index(LinkNode *list, void *ptr)
54 {
55         int index;
56         
57         for (index = 0; list; list = list->next, index++)
58                 if (list->link == ptr)
59                         return index;
60         
61         return -1;
62 }
63
64 LinkNode *BLI_linklist_find(LinkNode *list, int index)
65 {
66         int i;
67         
68         for (i = 0; list; list = list->next, i++)
69                 if (i == index)
70                         return list;
71
72         return NULL;
73 }
74
75 void BLI_linklist_reverse(LinkNode **listp)
76 {
77         LinkNode *rhead = NULL, *cur = *listp;
78         
79         while (cur) {
80                 LinkNode *next = cur->next;
81                 
82                 cur->next = rhead;
83                 rhead = cur;
84                 
85                 cur = next;
86         }
87         
88         *listp = rhead;
89 }
90
91 void BLI_linklist_prepend(LinkNode **listp, void *ptr)
92 {
93         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
94         nlink->link = ptr;
95         
96         nlink->next = *listp;
97         *listp = nlink;
98 }
99
100 void BLI_linklist_append(LinkNode **listp, void *ptr)
101 {
102         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
103         LinkNode *node = *listp;
104         
105         nlink->link = ptr;
106         nlink->next = NULL;
107         
108         if (node == NULL) {
109                 *listp = nlink;
110         }
111         else {
112                 while (node->next != NULL) {
113                         node = node->next;   
114                 }
115                 node->next = nlink;
116         }
117 }
118
119 void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
120 {
121         LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
122         nlink->link = ptr;
123         
124         nlink->next = *listp;
125         *listp = nlink;
126 }
127
128 void BLI_linklist_insert_after(LinkNode **listp, void *ptr)
129 {
130         LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
131         LinkNode *node = *listp;
132
133         nlink->link = ptr;
134
135         if (node) {
136                 nlink->next = node->next;
137                 node->next = nlink;
138         }
139         else {
140                 nlink->next = NULL;
141                 *listp = nlink;
142         }
143 }
144
145 void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
146 {
147         while (list) {
148                 LinkNode *next = list->next;
149                 
150                 if (freefunc)
151                         freefunc(list->link);
152                 MEM_freeN(list);
153                 
154                 list = next;
155         }
156 }
157
158 void BLI_linklist_freeN(LinkNode *list)
159 {
160         while (list) {
161                 LinkNode *next = list->next;
162
163                 MEM_freeN(list->link);
164                 MEM_freeN(list);
165
166                 list = next;
167         }
168 }
169
170 void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata)
171 {
172         for (; list; list = list->next)
173                 applyfunc(list->link, userdata);
174 }