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 }