Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
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 }