XMMS2
src/lib/xmmstypes/xlist.c
Go to the documentation of this file.
00001 /* GLIB - Library of useful routines for C programming
00002  *  Copyright (C) 2003-2011 XMMS2 Team
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Lesser General Public
00006  * License as published by the Free Software Foundation; either
00007  * version 2 of the License, or (at your option) any later version.
00008  *
00009  * This library is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * Lesser General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Lesser General Public
00015  * License along with this library; if not, write to the
00016  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017  * Boston, MA 02111-1307, USA.
00018  */
00019 
00020 /*
00021  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
00022  * file for a list of people on the GLib Team.  See the ChangeLog
00023  * files for a list of changes.  These files are distributed with
00024  * GLib at ftp://ftp.gtk.org/pub/gtk/.
00025  */
00026 
00027 #include <assert.h>
00028 
00029 #include "xmmspriv/xmms_list.h"
00030 
00031 #include <stdlib.h>
00032 
00033 #define _x_list_alloc x_list_alloc
00034 x_list_t *
00035 x_list_alloc (void)
00036 {
00037     x_list_t *list;
00038 
00039     list = calloc (1, sizeof (x_list_t));
00040 
00041     return list;
00042 }
00043 
00044 void
00045 x_list_free (x_list_t *list)
00046 {
00047     x_list_t *last;
00048 
00049     while (list) {
00050         last = list;
00051         list = list->next;
00052         free (last);
00053     }
00054 }
00055 
00056 #define _x_list_free_1 x_list_free_1
00057 void
00058 x_list_free_1 (x_list_t *list)
00059 {
00060      free (list);
00061 }
00062 
00063 x_list_t*
00064 x_list_append (x_list_t *list, void *data)
00065 {
00066     x_list_t *new_list;
00067     x_list_t *last;
00068 
00069     new_list = _x_list_alloc ();
00070     new_list->data = data;
00071 
00072     if (list) {
00073         last = x_list_last (list);
00074         /* g_assert (last != NULL); */
00075         last->next = new_list;
00076         new_list->prev = last;
00077 
00078         return list;
00079     } else {
00080         return new_list;
00081     }
00082 }
00083 
00084 x_list_t*
00085 x_list_prepend (x_list_t *list, void *data)
00086 {
00087     x_list_t *new_list;
00088 
00089     new_list = _x_list_alloc ();
00090     new_list->data = data;
00091 
00092     if (list) {
00093         if (list->prev) {
00094             list->prev->next = new_list;
00095             new_list->prev = list->prev;
00096         }
00097         list->prev = new_list;
00098         new_list->next = list;
00099     }
00100 
00101     return new_list;
00102 }
00103 
00104 x_list_t*
00105 x_list_insert (x_list_t *list, void *data, int position)
00106 {
00107     x_list_t *new_list;
00108     x_list_t *tmp_list;
00109 
00110     if (position < 0) {
00111         return x_list_append (list, data);
00112     } else if (position == 0) {
00113         return x_list_prepend (list, data);
00114     }
00115 
00116     tmp_list = x_list_nth (list, position);
00117     if (!tmp_list)
00118         return x_list_append (list, data);
00119 
00120     new_list = _x_list_alloc ();
00121     new_list->data = data;
00122 
00123     if (tmp_list->prev) {
00124         tmp_list->prev->next = new_list;
00125         new_list->prev = tmp_list->prev;
00126     }
00127     new_list->next = tmp_list;
00128     tmp_list->prev = new_list;
00129 
00130     if (tmp_list == list) {
00131         return new_list;
00132     } else {
00133         return list;
00134     }
00135 }
00136 
00137 x_list_t*
00138 x_list_insert_before (x_list_t *list, x_list_t *sibling, void *data)
00139 {
00140     if (!list) {
00141         list = x_list_alloc ();
00142         list->data = data;
00143         assert (sibling);
00144         return list;
00145     } else if (sibling) {
00146         x_list_t *node;
00147 
00148         node = x_list_alloc ();
00149         node->data = data;
00150         if (sibling->prev) {
00151             node->prev = sibling->prev;
00152             node->prev->next = node;
00153             node->next = sibling;
00154             sibling->prev = node;
00155             return list;
00156         } else {
00157             node->next = sibling;
00158             sibling->prev = node;
00159             assert (sibling);
00160             return node;
00161         }
00162     } else {
00163         x_list_t *last;
00164 
00165         last = list;
00166         while (last->next) {
00167             last = last->next;
00168         }
00169 
00170         last->next = x_list_alloc ();
00171         last->next->data = data;
00172         last->next->prev = last;
00173 
00174         return list;
00175     }
00176 }
00177 
00178 x_list_t *
00179 x_list_concat (x_list_t *list1, x_list_t *list2)
00180 {
00181     x_list_t *tmp_list;
00182 
00183     if (list2) {
00184         tmp_list = x_list_last (list1);
00185         if (tmp_list) {
00186             tmp_list->next = list2;
00187         } else {
00188             list1 = list2;
00189         }
00190         list2->prev = tmp_list;
00191     }
00192 
00193     return list1;
00194 }
00195 
00196 x_list_t*
00197 x_list_remove (x_list_t *list, const void *data)
00198 {
00199     x_list_t *tmp;
00200 
00201     tmp = list;
00202     while (tmp) {
00203         if (tmp->data != data) {
00204             tmp = tmp->next;
00205         } else {
00206             if (tmp->prev)
00207                 tmp->prev->next = tmp->next;
00208             if (tmp->next)
00209                 tmp->next->prev = tmp->prev;
00210 
00211             if (list == tmp)
00212                 list = list->next;
00213 
00214             _x_list_free_1 (tmp);
00215 
00216             break;
00217         }
00218     }
00219     return list;
00220 }
00221 
00222 x_list_t*
00223 x_list_remove_all (x_list_t *list, const void * data)
00224 {
00225     x_list_t *tmp = list;
00226 
00227     while (tmp) {
00228         if (tmp->data != data) {
00229             tmp = tmp->next;
00230         } else {
00231             x_list_t *next = tmp->next;
00232 
00233             if (tmp->prev) {
00234                 tmp->prev->next = next;
00235             } else {
00236                 list = next;
00237             }
00238             if (next) {
00239                 next->prev = tmp->prev;
00240             }
00241 
00242             _x_list_free_1 (tmp);
00243             tmp = next;
00244         }
00245     }
00246     return list;
00247 }
00248 
00249 static inline x_list_t*
00250 _x_list_remove_link (x_list_t *list, x_list_t *link)
00251 {
00252     if (link) {
00253         if (link->prev)
00254             link->prev->next = link->next;
00255         if (link->next)
00256             link->next->prev = link->prev;
00257 
00258         if (link == list)
00259             list = list->next;
00260 
00261         link->next = NULL;
00262         link->prev = NULL;
00263     }
00264 
00265     return list;
00266 }
00267 
00268 x_list_t*
00269 x_list_remove_link (x_list_t *list, x_list_t *link)
00270 {
00271     return _x_list_remove_link (list, link);
00272 }
00273 
00274 x_list_t*
00275 x_list_delete_link (x_list_t *list, x_list_t *link)
00276 {
00277     list = _x_list_remove_link (list, link);
00278     _x_list_free_1 (link);
00279 
00280     return list;
00281 }
00282 
00283 x_list_t*
00284 x_list_copy (x_list_t *list)
00285 {
00286     x_list_t *new_list = NULL;
00287 
00288     if (list) {
00289         x_list_t *last;
00290 
00291         new_list = _x_list_alloc ();
00292         new_list->data = list->data;
00293         last = new_list;
00294         list = list->next;
00295         while (list) {
00296             last->next = _x_list_alloc ();
00297             last->next->prev = last;
00298             last = last->next;
00299             last->data = list->data;
00300             list = list->next;
00301         }
00302     }
00303 
00304     return new_list;
00305 }
00306 
00307 x_list_t*
00308 x_list_reverse (x_list_t *list)
00309 {
00310     x_list_t *last;
00311 
00312     last = NULL;
00313     while (list) {
00314         last = list;
00315         list = last->next;
00316         last->next = last->prev;
00317         last->prev = list;
00318     }
00319 
00320     return last;
00321 }
00322 
00323 x_list_t*
00324 x_list_nth (x_list_t *list, unsigned int n)
00325 {
00326     while ((n-- > 0) && list)
00327         list = list->next;
00328 
00329     return list;
00330 }
00331 
00332 x_list_t*
00333 x_list_nth_prev (x_list_t *list, unsigned int n)
00334 {
00335     while ((n-- > 0) && list)
00336         list = list->prev;
00337 
00338     return list;
00339 }
00340 
00341 void *
00342 x_list_nth_data (x_list_t *list, unsigned int n)
00343 {
00344     while ((n-- > 0) && list)
00345         list = list->next;
00346 
00347     return list ? list->data : NULL;
00348 }
00349 
00350 x_list_t*
00351 x_list_find (x_list_t *list, const void *data)
00352 {
00353     while (list) {
00354         if (list->data == data)
00355             break;
00356         list = list->next;
00357     }
00358 
00359     return list;
00360 }
00361 
00362 x_list_t*
00363 x_list_find_custom (x_list_t *list, const void *data, XCompareFunc func)
00364 {
00365     assert (func != NULL);
00366 
00367     while (list) {
00368         if (! func (list->data, data))
00369             return list;
00370         list = list->next;
00371     }
00372 
00373     return NULL;
00374 }
00375 
00376 
00377 int
00378 x_list_position (x_list_t *list, x_list_t *link)
00379 {
00380     int i;
00381 
00382     i = 0;
00383     while (list) {
00384         if (list == link)
00385             return i;
00386         i++;
00387         list = list->next;
00388     }
00389 
00390     return -1;
00391 }
00392 
00393 int
00394 x_list_index (x_list_t *list, const void *data)
00395 {
00396     int i;
00397 
00398     i = 0;
00399     while (list) {
00400         if (list->data == data)
00401             return i;
00402         i++;
00403         list = list->next;
00404     }
00405 
00406     return -1;
00407 }
00408 
00409 x_list_t*
00410 x_list_last (x_list_t *list)
00411 {
00412     if (list) {
00413         while (list->next)
00414             list = list->next;
00415     }
00416 
00417     return list;
00418 }
00419 
00420 x_list_t*
00421 x_list_first (x_list_t *list)
00422 {
00423     if (list) {
00424         while (list->prev)
00425             list = list->prev;
00426     }
00427 
00428     return list;
00429 }
00430 
00431 unsigned int
00432 x_list_length (x_list_t *list)
00433 {
00434     unsigned int length;
00435 
00436     length = 0;
00437     while (list) {
00438         length++;
00439         list = list->next;
00440     }
00441 
00442     return length;
00443 }
00444 
00445 void
00446 x_list_foreach (x_list_t *list, XFunc func, void *user_data)
00447 {
00448     while (list) {
00449         x_list_t *next = list->next;
00450         (*func) (list->data, user_data);
00451         list = next;
00452     }
00453 }
00454 
00455 
00456 x_list_t*
00457 x_list_insert_sorted (x_list_t *list, void *data, XCompareFunc func)
00458 {
00459     x_list_t *tmp_list = list;
00460     x_list_t *new_list;
00461     int cmp;
00462 
00463     assert (func != NULL);
00464 
00465     if (!list) {
00466         new_list = _x_list_alloc ();
00467         new_list->data = data;
00468         return new_list;
00469     }
00470 
00471     cmp = (*func) (data, tmp_list->data);
00472 
00473     while ((tmp_list->next) && (cmp > 0)) {
00474         tmp_list = tmp_list->next;
00475         cmp = (*func) (data, tmp_list->data);
00476     }
00477 
00478     new_list = _x_list_alloc ();
00479     new_list->data = data;
00480 
00481     if ((!tmp_list->next) && (cmp > 0)) {
00482         tmp_list->next = new_list;
00483         new_list->prev = tmp_list;
00484         return list;
00485     }
00486 
00487     if (tmp_list->prev) {
00488         tmp_list->prev->next = new_list;
00489         new_list->prev = tmp_list->prev;
00490     }
00491     new_list->next = tmp_list;
00492     tmp_list->prev = new_list;
00493 
00494     if (tmp_list == list)
00495         return new_list;
00496     else
00497         return list;
00498 }