XMMS2
|
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 }