[xbuild] Exec task - add support for custom error/warning regex.
[mono.git] / eglib / src / glist.c
1 /*
2  * glist.c: Doubly-linked list implementation
3  *
4  * Authors:
5  *   Duncan Mak (duncan@novell.com)
6  *   Raja R Harinath (rharinath@novell.com)
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining
9  * a copy of this software and associated documentation files (the
10  * "Software"), to deal in the Software without restriction, including
11  * without limitation the rights to use, copy, modify, merge, publish,
12  * distribute, sublicense, and/or sell copies of the Software, and to
13  * permit persons to whom the Software is furnished to do so, subject to
14  * the following conditions:
15  * 
16  * The above copyright notice and this permission notice shall be
17  * included in all copies or substantial portions of the Software.
18  * 
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
23  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
24  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
25  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26  *
27  * (C) 2006 Novell, Inc.
28  */
29 #include <stdio.h>
30 #include <glib.h>
31
32 GList*
33 g_list_alloc ()
34 {
35         return g_new0 (GList, 1);
36 }
37
38 static inline GList*
39 new_node (GList *prev, gpointer data, GList *next)
40 {
41         GList *node = g_list_alloc ();
42         node->data = data;
43         node->prev = prev;
44         node->next = next;
45         if (prev)
46                 prev->next = node;
47         if (next)
48                 next->prev = node;
49         return node;
50 }
51
52 static inline GList*
53 disconnect_node (GList *node)
54 {
55         if (node->next)
56                 node->next->prev = node->prev;
57         if (node->prev)
58                 node->prev->next = node->next;
59         return node;
60 }
61
62 GList *
63 g_list_prepend (GList *list, gpointer data)
64 {
65         return new_node (list ? list->prev : NULL, data, list);
66 }
67
68 void
69 g_list_free_1 (GList *list)
70 {
71         g_free (list);
72 }
73
74 void
75 g_list_free (GList *list)
76 {
77         while (list){
78                 GList *next = list->next;
79                 g_list_free_1 (list);
80                 list = next;
81         }
82 }
83
84 GList*
85 g_list_append (GList *list, gpointer data)
86 {
87         GList *node = new_node (g_list_last (list), data, NULL);
88         return list ? list : node;
89 }
90
91 GList *
92 g_list_concat (GList *list1, GList *list2)
93 {
94         if (list1 && list2) {
95                 list2->prev = g_list_last (list1);
96                 list2->prev->next = list2;
97         }
98         return list1 ? list1 : list2;
99 }
100
101 guint
102 g_list_length (GList *list)
103 {
104         guint length = 0;
105
106         while (list) {
107                 length ++;
108                 list = list->next;
109         }
110
111         return length;
112 }
113
114 GList*
115 g_list_remove (GList *list, gconstpointer data)
116 {
117         GList *current = g_list_find (list, data);
118         if (!current)
119                 return list;
120
121         if (current == list)
122                 list = list->next;
123         g_list_free_1 (disconnect_node (current));
124
125         return list;
126 }
127
128 GList*
129 g_list_remove_link (GList *list, GList *link)
130 {
131         if (list == link)
132                 list = list->next;
133
134         disconnect_node (link);
135         link->next = NULL;
136         link->prev = NULL;
137
138         return list;
139 }
140
141 GList*
142 g_list_delete_link (GList *list, GList *link)
143 {
144         list = g_list_remove_link (list, link);
145         g_list_free_1 (link);
146
147         return list;
148 }
149
150 GList*
151 g_list_find (GList *list, gconstpointer data)
152 {
153         while (list){
154                 if (list->data == data)
155                         return list;
156
157                 list = list->next;
158         }
159
160         return NULL;
161 }
162
163 GList*
164 g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func)
165 {
166         if (!func)
167                 return NULL;
168         
169         while (list) {
170                 if (func (list->data, data) == 0)
171                         return list;
172                 
173                 list = list->next;
174         }
175         
176         return NULL;
177 }
178
179 GList*
180 g_list_reverse (GList *list)
181 {
182         GList *reverse = NULL;
183
184         while (list) {
185                 reverse = list;
186                 list = reverse->next;
187
188                 reverse->next = reverse->prev;
189                 reverse->prev = list;
190         }
191
192         return reverse;
193 }
194
195 GList*
196 g_list_first (GList *list)
197 {
198         if (!list)
199                 return NULL;
200
201         while (list->prev)
202                 list = list->prev;
203
204         return list;
205 }
206
207 GList*
208 g_list_last (GList *list)
209 {
210         if (!list)
211                 return NULL;
212
213         while (list->next)
214                 list = list->next;
215
216         return list;
217 }
218
219 GList*
220 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
221 {
222         GList *prev = NULL;
223         GList *current;
224         GList *node;
225
226         if (!func)
227                 return list;
228
229         /* Invariant: !prev || func (prev->data, data) <= 0) */
230         for (current = list; current; current = current->next) {
231                 if (func (current->data, data) > 0)
232                         break;
233                 prev = current;
234         }
235
236         node = new_node (prev, data, current);
237         return list == current ? node : list;
238 }
239
240 GList*
241 g_list_insert_before (GList *list, GList *sibling, gpointer data)
242 {
243         if (sibling) {
244                 GList *node = new_node (sibling->prev, data, sibling);
245                 return list == sibling ? node : list;
246         }
247         return g_list_append (list, data);
248 }
249
250 void
251 g_list_foreach (GList *list, GFunc func, gpointer user_data)
252 {
253         while (list){
254                 (*func) (list->data, user_data);
255                 list = list->next;
256         }
257 }
258
259 gint
260 g_list_index (GList *list, gconstpointer data)
261 {
262         gint index = 0;
263
264         while (list){
265                 if (list->data == data)
266                         return index;
267
268                 index ++;
269                 list = list->next;
270         }
271
272         return -1;
273 }
274
275 GList*
276 g_list_nth (GList *list, guint n)
277 {
278         for (; list; list = list->next) {
279                 if (n == 0)
280                         break;
281                 n--;
282         }
283         return list;
284 }
285
286 gpointer
287 g_list_nth_data (GList *list, guint n)
288 {
289         GList *node = g_list_nth (list, n);
290         return node ? node->data : NULL;
291 }
292
293 GList*
294 g_list_copy (GList *list)
295 {
296         GList *copy = NULL;
297
298         if (list) {
299                 GList *tmp = new_node (NULL, list->data, NULL);
300                 copy = tmp;
301
302                 for (list = list->next; list; list = list->next)
303                         tmp = new_node (tmp, list->data, NULL);
304         }
305
306         return copy;
307 }
308
309 typedef GList list_node;
310 #include "sort.frag.h"
311
312 GList*
313 g_list_sort (GList *list, GCompareFunc func)
314 {
315         GList *current;
316         if (!list || !list->next)
317                 return list;
318         list = do_sort (list, func);
319
320         /* Fixup: do_sort doesn't update 'prev' pointers */
321         list->prev = NULL;
322         for (current = list; current->next; current = current->next)
323                 current->next->prev = current;
324
325         return list;
326 }