XMMS2
xlist.c
Go to the documentation of this file.
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 2003-2011 XMMS2 Team
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library 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 GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19 
20 /*
21  * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22  * file for a list of people on the GLib Team. See the ChangeLog
23  * files for a list of changes. These files are distributed with
24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
25  */
26 
27 #include <assert.h>
28 
29 #include "xmmspriv/xmms_list.h"
30 
31 #include <stdlib.h>
32 
33 #define _x_list_alloc x_list_alloc
34 x_list_t *
36 {
37  x_list_t *list;
38 
39  list = calloc (1, sizeof (x_list_t));
40 
41  return list;
42 }
43 
44 void
46 {
47  x_list_t *last;
48 
49  while (list) {
50  last = list;
51  list = list->next;
52  free (last);
53  }
54 }
55 
56 #define _x_list_free_1 x_list_free_1
57 void
59 {
60  free (list);
61 }
62 
63 x_list_t*
64 x_list_append (x_list_t *list, void *data)
65 {
66  x_list_t *new_list;
67  x_list_t *last;
68 
69  new_list = _x_list_alloc ();
70  new_list->data = data;
71 
72  if (list) {
73  last = x_list_last (list);
74  /* g_assert (last != NULL); */
75  last->next = new_list;
76  new_list->prev = last;
77 
78  return list;
79  } else {
80  return new_list;
81  }
82 }
83 
84 x_list_t*
85 x_list_prepend (x_list_t *list, void *data)
86 {
87  x_list_t *new_list;
88 
89  new_list = _x_list_alloc ();
90  new_list->data = data;
91 
92  if (list) {
93  if (list->prev) {
94  list->prev->next = new_list;
95  new_list->prev = list->prev;
96  }
97  list->prev = new_list;
98  new_list->next = list;
99  }
100 
101  return new_list;
102 }
103 
104 x_list_t*
105 x_list_insert (x_list_t *list, void *data, int position)
106 {
107  x_list_t *new_list;
108  x_list_t *tmp_list;
109 
110  if (position < 0) {
111  return x_list_append (list, data);
112  } else if (position == 0) {
113  return x_list_prepend (list, data);
114  }
115 
116  tmp_list = x_list_nth (list, position);
117  if (!tmp_list)
118  return x_list_append (list, data);
119 
120  new_list = _x_list_alloc ();
121  new_list->data = data;
122 
123  if (tmp_list->prev) {
124  tmp_list->prev->next = new_list;
125  new_list->prev = tmp_list->prev;
126  }
127  new_list->next = tmp_list;
128  tmp_list->prev = new_list;
129 
130  if (tmp_list == list) {
131  return new_list;
132  } else {
133  return list;
134  }
135 }
136 
137 x_list_t*
138 x_list_insert_before (x_list_t *list, x_list_t *sibling, void *data)
139 {
140  if (!list) {
141  list = x_list_alloc ();
142  list->data = data;
143  assert (sibling);
144  return list;
145  } else if (sibling) {
146  x_list_t *node;
147 
148  node = x_list_alloc ();
149  node->data = data;
150  if (sibling->prev) {
151  node->prev = sibling->prev;
152  node->prev->next = node;
153  node->next = sibling;
154  sibling->prev = node;
155  return list;
156  } else {
157  node->next = sibling;
158  sibling->prev = node;
159  assert (sibling);
160  return node;
161  }
162  } else {
163  x_list_t *last;
164 
165  last = list;
166  while (last->next) {
167  last = last->next;
168  }
169 
170  last->next = x_list_alloc ();
171  last->next->data = data;
172  last->next->prev = last;
173 
174  return list;
175  }
176 }
177 
178 x_list_t *
180 {
181  x_list_t *tmp_list;
182 
183  if (list2) {
184  tmp_list = x_list_last (list1);
185  if (tmp_list) {
186  tmp_list->next = list2;
187  } else {
188  list1 = list2;
189  }
190  list2->prev = tmp_list;
191  }
192 
193  return list1;
194 }
195 
196 x_list_t*
197 x_list_remove (x_list_t *list, const void *data)
198 {
199  x_list_t *tmp;
200 
201  tmp = list;
202  while (tmp) {
203  if (tmp->data != data) {
204  tmp = tmp->next;
205  } else {
206  if (tmp->prev)
207  tmp->prev->next = tmp->next;
208  if (tmp->next)
209  tmp->next->prev = tmp->prev;
210 
211  if (list == tmp)
212  list = list->next;
213 
214  _x_list_free_1 (tmp);
215 
216  break;
217  }
218  }
219  return list;
220 }
221 
222 x_list_t*
223 x_list_remove_all (x_list_t *list, const void * data)
224 {
225  x_list_t *tmp = list;
226 
227  while (tmp) {
228  if (tmp->data != data) {
229  tmp = tmp->next;
230  } else {
231  x_list_t *next = tmp->next;
232 
233  if (tmp->prev) {
234  tmp->prev->next = next;
235  } else {
236  list = next;
237  }
238  if (next) {
239  next->prev = tmp->prev;
240  }
241 
242  _x_list_free_1 (tmp);
243  tmp = next;
244  }
245  }
246  return list;
247 }
248 
249 static inline x_list_t*
250 _x_list_remove_link (x_list_t *list, x_list_t *link)
251 {
252  if (link) {
253  if (link->prev)
254  link->prev->next = link->next;
255  if (link->next)
256  link->next->prev = link->prev;
257 
258  if (link == list)
259  list = list->next;
260 
261  link->next = NULL;
262  link->prev = NULL;
263  }
264 
265  return list;
266 }
267 
268 x_list_t*
270 {
271  return _x_list_remove_link (list, link);
272 }
273 
274 x_list_t*
276 {
277  list = _x_list_remove_link (list, link);
278  _x_list_free_1 (link);
279 
280  return list;
281 }
282 
283 x_list_t*
285 {
286  x_list_t *new_list = NULL;
287 
288  if (list) {
289  x_list_t *last;
290 
291  new_list = _x_list_alloc ();
292  new_list->data = list->data;
293  last = new_list;
294  list = list->next;
295  while (list) {
296  last->next = _x_list_alloc ();
297  last->next->prev = last;
298  last = last->next;
299  last->data = list->data;
300  list = list->next;
301  }
302  }
303 
304  return new_list;
305 }
306 
307 x_list_t*
309 {
310  x_list_t *last;
311 
312  last = NULL;
313  while (list) {
314  last = list;
315  list = last->next;
316  last->next = last->prev;
317  last->prev = list;
318  }
319 
320  return last;
321 }
322 
323 x_list_t*
324 x_list_nth (x_list_t *list, unsigned int n)
325 {
326  while ((n-- > 0) && list)
327  list = list->next;
328 
329  return list;
330 }
331 
332 x_list_t*
333 x_list_nth_prev (x_list_t *list, unsigned int n)
334 {
335  while ((n-- > 0) && list)
336  list = list->prev;
337 
338  return list;
339 }
340 
341 void *
342 x_list_nth_data (x_list_t *list, unsigned int n)
343 {
344  while ((n-- > 0) && list)
345  list = list->next;
346 
347  return list ? list->data : NULL;
348 }
349 
350 x_list_t*
351 x_list_find (x_list_t *list, const void *data)
352 {
353  while (list) {
354  if (list->data == data)
355  break;
356  list = list->next;
357  }
358 
359  return list;
360 }
361 
362 x_list_t*
363 x_list_find_custom (x_list_t *list, const void *data, XCompareFunc func)
364 {
365  assert (func != NULL);
366 
367  while (list) {
368  if (! func (list->data, data))
369  return list;
370  list = list->next;
371  }
372 
373  return NULL;
374 }
375 
376 
377 int
379 {
380  int i;
381 
382  i = 0;
383  while (list) {
384  if (list == link)
385  return i;
386  i++;
387  list = list->next;
388  }
389 
390  return -1;
391 }
392 
393 int
394 x_list_index (x_list_t *list, const void *data)
395 {
396  int i;
397 
398  i = 0;
399  while (list) {
400  if (list->data == data)
401  return i;
402  i++;
403  list = list->next;
404  }
405 
406  return -1;
407 }
408 
409 x_list_t*
411 {
412  if (list) {
413  while (list->next)
414  list = list->next;
415  }
416 
417  return list;
418 }
419 
420 x_list_t*
422 {
423  if (list) {
424  while (list->prev)
425  list = list->prev;
426  }
427 
428  return list;
429 }
430 
431 unsigned int
433 {
434  unsigned int length;
435 
436  length = 0;
437  while (list) {
438  length++;
439  list = list->next;
440  }
441 
442  return length;
443 }
444 
445 void
446 x_list_foreach (x_list_t *list, XFunc func, void *user_data)
447 {
448  while (list) {
449  x_list_t *next = list->next;
450  (*func) (list->data, user_data);
451  list = next;
452  }
453 }
454 
455 
456 x_list_t*
457 x_list_insert_sorted (x_list_t *list, void *data, XCompareFunc func)
458 {
459  x_list_t *tmp_list = list;
460  x_list_t *new_list;
461  int cmp;
462 
463  assert (func != NULL);
464 
465  if (!list) {
466  new_list = _x_list_alloc ();
467  new_list->data = data;
468  return new_list;
469  }
470 
471  cmp = (*func) (data, tmp_list->data);
472 
473  while ((tmp_list->next) && (cmp > 0)) {
474  tmp_list = tmp_list->next;
475  cmp = (*func) (data, tmp_list->data);
476  }
477 
478  new_list = _x_list_alloc ();
479  new_list->data = data;
480 
481  if ((!tmp_list->next) && (cmp > 0)) {
482  tmp_list->next = new_list;
483  new_list->prev = tmp_list;
484  return list;
485  }
486 
487  if (tmp_list->prev) {
488  tmp_list->prev->next = new_list;
489  new_list->prev = tmp_list->prev;
490  }
491  new_list->next = tmp_list;
492  tmp_list->prev = new_list;
493 
494  if (tmp_list == list)
495  return new_list;
496  else
497  return list;
498 }
x_list_t * x_list_copy(x_list_t *list)
Definition: xlist.c:284
x_list_t * x_list_insert_sorted(x_list_t *list, void *data, XCompareFunc func)
Definition: xlist.c:457
x_list_t * x_list_first(x_list_t *list)
Definition: xlist.c:421
x_list_t * x_list_find_custom(x_list_t *list, const void *data, XCompareFunc func)
Definition: xlist.c:363
x_list_t * x_list_alloc(void)
Definition: xlist.c:35
x_list_t * x_list_append(x_list_t *list, void *data)
Definition: xlist.c:64
void x_list_free(x_list_t *list)
Definition: xlist.c:45
int x_list_position(x_list_t *list, x_list_t *link)
Definition: xlist.c:378
x_list_t * x_list_prepend(x_list_t *list, void *data)
Definition: xlist.c:85
x_list_t * x_list_delete_link(x_list_t *list, x_list_t *link)
Definition: xlist.c:275
x_list_t * x_list_find(x_list_t *list, const void *data)
Definition: xlist.c:351
#define _x_list_free_1
Definition: xlist.c:56
x_list_t * next
Definition: xmms_list.h:41
void * data
Definition: xmms_list.h:40
x_list_t * x_list_remove_link(x_list_t *list, x_list_t *link)
Definition: xlist.c:269
unsigned int x_list_length(x_list_t *list)
Definition: xlist.c:432
x_list_t * x_list_insert(x_list_t *list, void *data, int position)
Definition: xlist.c:105
void * x_list_nth_data(x_list_t *list, unsigned int n)
Definition: xlist.c:342
x_list_t * x_list_remove_all(x_list_t *list, const void *data)
Definition: xlist.c:223
x_list_t * x_list_remove(x_list_t *list, const void *data)
Definition: xlist.c:197
x_list_t * x_list_last(x_list_t *list)
Definition: xlist.c:410
x_list_t * x_list_reverse(x_list_t *list)
Definition: xlist.c:308
x_list_t * x_list_nth_prev(x_list_t *list, unsigned int n)
Definition: xlist.c:333
x_list_t * prev
Definition: xmms_list.h:42
void x_list_foreach(x_list_t *list, XFunc func, void *user_data)
Definition: xlist.c:446
x_list_t * x_list_nth(x_list_t *list, unsigned int n)
Definition: xlist.c:324
#define _x_list_alloc
Definition: xlist.c:33
x_list_t * x_list_insert_before(x_list_t *list, x_list_t *sibling, void *data)
Definition: xlist.c:138
x_list_t * x_list_concat(x_list_t *list1, x_list_t *list2)
Definition: xlist.c:179
int x_list_index(x_list_t *list, const void *data)
Definition: xlist.c:394
void x_list_free_1(x_list_t *list)
Definition: xlist.c:58