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 #include "xmmsclientpriv/xmmsclient_util.h"
00031
00032 #include <stdlib.h>
00033
00034 #define _x_list_alloc x_list_alloc
00035 x_list_t *
00036 x_list_alloc (void)
00037 {
00038 x_list_t *list;
00039
00040 list = calloc (1, sizeof (x_list_t));
00041
00042 return list;
00043 }
00044
00045 void
00046 x_list_free (x_list_t *list)
00047 {
00048 x_list_t *last;
00049
00050 while (list) {
00051 last = list;
00052 list = list->next;
00053 free (last);
00054 }
00055 }
00056
00057 #define _x_list_free_1 x_list_free_1
00058 void
00059 x_list_free_1 (x_list_t *list)
00060 {
00061 free (list);
00062 }
00063
00064 x_list_t*
00065 x_list_append (x_list_t *list, void *data)
00066 {
00067 x_list_t *new_list;
00068 x_list_t *last;
00069
00070 new_list = _x_list_alloc ();
00071 new_list->data = data;
00072
00073 if (list) {
00074 last = x_list_last (list);
00075
00076 last->next = new_list;
00077 new_list->prev = last;
00078
00079 return list;
00080 } else {
00081 return new_list;
00082 }
00083 }
00084
00085 x_list_t*
00086 x_list_prepend (x_list_t *list, void *data)
00087 {
00088 x_list_t *new_list;
00089
00090 new_list = _x_list_alloc ();
00091 new_list->data = data;
00092
00093 if (list) {
00094 if (list->prev) {
00095 list->prev->next = new_list;
00096 new_list->prev = list->prev;
00097 }
00098 list->prev = new_list;
00099 new_list->next = list;
00100 }
00101
00102 return new_list;
00103 }
00104
00105 x_list_t*
00106 x_list_insert (x_list_t *list, void *data, int position)
00107 {
00108 x_list_t *new_list;
00109 x_list_t *tmp_list;
00110
00111 if (position < 0) {
00112 return x_list_append (list, data);
00113 } else if (position == 0) {
00114 return x_list_prepend (list, data);
00115 }
00116
00117 tmp_list = x_list_nth (list, position);
00118 if (!tmp_list)
00119 return x_list_append (list, data);
00120
00121 new_list = _x_list_alloc ();
00122 new_list->data = data;
00123
00124 if (tmp_list->prev) {
00125 tmp_list->prev->next = new_list;
00126 new_list->prev = tmp_list->prev;
00127 }
00128 new_list->next = tmp_list;
00129 tmp_list->prev = new_list;
00130
00131 if (tmp_list == list) {
00132 return new_list;
00133 } else {
00134 return list;
00135 }
00136 }
00137
00138 x_list_t*
00139 x_list_insert_before (x_list_t *list, x_list_t *sibling, void *data)
00140 {
00141 if (!list) {
00142 list = x_list_alloc ();
00143 list->data = data;
00144 assert (sibling);
00145 return list;
00146 } else if (sibling) {
00147 x_list_t *node;
00148
00149 node = x_list_alloc ();
00150 node->data = data;
00151 if (sibling->prev) {
00152 node->prev = sibling->prev;
00153 node->prev->next = node;
00154 node->next = sibling;
00155 sibling->prev = node;
00156 return list;
00157 } else {
00158 node->next = sibling;
00159 sibling->prev = node;
00160 assert (sibling);
00161 return node;
00162 }
00163 } else {
00164 x_list_t *last;
00165
00166 last = list;
00167 while (last->next) {
00168 last = last->next;
00169 }
00170
00171 last->next = x_list_alloc ();
00172 last->next->data = data;
00173 last->next->prev = last;
00174
00175 return list;
00176 }
00177 }
00178
00179 x_list_t *
00180 x_list_concat (x_list_t *list1, x_list_t *list2)
00181 {
00182 x_list_t *tmp_list;
00183
00184 if (list2) {
00185 tmp_list = x_list_last (list1);
00186 if (tmp_list) {
00187 tmp_list->next = list2;
00188 } else {
00189 list1 = list2;
00190 }
00191 list2->prev = tmp_list;
00192 }
00193
00194 return list1;
00195 }
00196
00197 x_list_t*
00198 x_list_remove (x_list_t *list, const void *data)
00199 {
00200 x_list_t *tmp;
00201
00202 tmp = list;
00203 while (tmp) {
00204 if (tmp->data != data) {
00205 tmp = tmp->next;
00206 } else {
00207 if (tmp->prev)
00208 tmp->prev->next = tmp->next;
00209 if (tmp->next)
00210 tmp->next->prev = tmp->prev;
00211
00212 if (list == tmp)
00213 list = list->next;
00214
00215 _x_list_free_1 (tmp);
00216
00217 break;
00218 }
00219 }
00220 return list;
00221 }
00222
00223 x_list_t*
00224 x_list_remove_all (x_list_t *list, const void * data)
00225 {
00226 x_list_t *tmp = list;
00227
00228 while (tmp) {
00229 if (tmp->data != data) {
00230 tmp = tmp->next;
00231 } else {
00232 x_list_t *next = tmp->next;
00233
00234 if (tmp->prev) {
00235 tmp->prev->next = next;
00236 } else {
00237 list = next;
00238 }
00239 if (next) {
00240 next->prev = tmp->prev;
00241 }
00242
00243 _x_list_free_1 (tmp);
00244 tmp = next;
00245 }
00246 }
00247 return list;
00248 }
00249
00250 static inline x_list_t*
00251 _x_list_remove_link (x_list_t *list, x_list_t *link)
00252 {
00253 if (link) {
00254 if (link->prev)
00255 link->prev->next = link->next;
00256 if (link->next)
00257 link->next->prev = link->prev;
00258
00259 if (link == list)
00260 list = list->next;
00261
00262 link->next = NULL;
00263 link->prev = NULL;
00264 }
00265
00266 return list;
00267 }
00268
00269 x_list_t*
00270 x_list_remove_link (x_list_t *list, x_list_t *link)
00271 {
00272 return _x_list_remove_link (list, link);
00273 }
00274
00275 x_list_t*
00276 x_list_delete_link (x_list_t *list, x_list_t *link)
00277 {
00278 list = _x_list_remove_link (list, link);
00279 _x_list_free_1 (link);
00280
00281 return list;
00282 }
00283
00284 x_list_t*
00285 x_list_copy (x_list_t *list)
00286 {
00287 x_list_t *new_list = NULL;
00288
00289 if (list) {
00290 x_list_t *last;
00291
00292 new_list = _x_list_alloc ();
00293 new_list->data = list->data;
00294 last = new_list;
00295 list = list->next;
00296 while (list) {
00297 last->next = _x_list_alloc ();
00298 last->next->prev = last;
00299 last = last->next;
00300 last->data = list->data;
00301 list = list->next;
00302 }
00303 }
00304
00305 return new_list;
00306 }
00307
00308 x_list_t*
00309 x_list_reverse (x_list_t *list)
00310 {
00311 x_list_t *last;
00312
00313 last = NULL;
00314 while (list) {
00315 last = list;
00316 list = last->next;
00317 last->next = last->prev;
00318 last->prev = list;
00319 }
00320
00321 return last;
00322 }
00323
00324 x_list_t*
00325 x_list_nth (x_list_t *list, unsigned int n)
00326 {
00327 while ((n-- > 0) && list)
00328 list = list->next;
00329
00330 return list;
00331 }
00332
00333 x_list_t*
00334 x_list_nth_prev (x_list_t *list, unsigned int n)
00335 {
00336 while ((n-- > 0) && list)
00337 list = list->prev;
00338
00339 return list;
00340 }
00341
00342 void *
00343 x_list_nth_data (x_list_t *list, unsigned int n)
00344 {
00345 while ((n-- > 0) && list)
00346 list = list->next;
00347
00348 return list ? list->data : NULL;
00349 }
00350
00351 x_list_t*
00352 x_list_find (x_list_t *list, const void *data)
00353 {
00354 while (list) {
00355 if (list->data == data)
00356 break;
00357 list = list->next;
00358 }
00359
00360 return list;
00361 }
00362
00363 x_list_t*
00364 x_list_find_custom (x_list_t *list, const void *data, XCompareFunc func)
00365 {
00366 assert (func != NULL);
00367
00368 while (list) {
00369 if (! func (list->data, data))
00370 return list;
00371 list = list->next;
00372 }
00373
00374 return NULL;
00375 }
00376
00377
00378 int
00379 x_list_position (x_list_t *list, x_list_t *link)
00380 {
00381 int i;
00382
00383 i = 0;
00384 while (list) {
00385 if (list == link)
00386 return i;
00387 i++;
00388 list = list->next;
00389 }
00390
00391 return -1;
00392 }
00393
00394 int
00395 x_list_index (x_list_t *list, const void *data)
00396 {
00397 int i;
00398
00399 i = 0;
00400 while (list) {
00401 if (list->data == data)
00402 return i;
00403 i++;
00404 list = list->next;
00405 }
00406
00407 return -1;
00408 }
00409
00410 x_list_t*
00411 x_list_last (x_list_t *list)
00412 {
00413 if (list) {
00414 while (list->next)
00415 list = list->next;
00416 }
00417
00418 return list;
00419 }
00420
00421 x_list_t*
00422 x_list_first (x_list_t *list)
00423 {
00424 if (list) {
00425 while (list->prev)
00426 list = list->prev;
00427 }
00428
00429 return list;
00430 }
00431
00432 unsigned int
00433 x_list_length (x_list_t *list)
00434 {
00435 unsigned int length;
00436
00437 length = 0;
00438 while (list) {
00439 length++;
00440 list = list->next;
00441 }
00442
00443 return length;
00444 }
00445
00446 void
00447 x_list_foreach (x_list_t *list, XFunc func, void *user_data)
00448 {
00449 while (list) {
00450 x_list_t *next = list->next;
00451 (*func) (list->data, user_data);
00452 list = next;
00453 }
00454 }
00455
00456
00457 x_list_t*
00458 x_list_insert_sorted (x_list_t *list, void *data, XCompareFunc func)
00459 {
00460 x_list_t *tmp_list = list;
00461 x_list_t *new_list;
00462 int cmp;
00463
00464 assert (func != NULL);
00465
00466 if (!list) {
00467 new_list = _x_list_alloc ();
00468 new_list->data = data;
00469 return new_list;
00470 }
00471
00472 cmp = (*func) (data, tmp_list->data);
00473
00474 while ((tmp_list->next) && (cmp > 0)) {
00475 tmp_list = tmp_list->next;
00476 cmp = (*func) (data, tmp_list->data);
00477 }
00478
00479 new_list = _x_list_alloc ();
00480 new_list->data = data;
00481
00482 if ((!tmp_list->next) && (cmp > 0)) {
00483 tmp_list->next = new_list;
00484 new_list->prev = tmp_list;
00485 return list;
00486 }
00487
00488 if (tmp_list->prev) {
00489 tmp_list->prev->next = new_list;
00490 new_list->prev = tmp_list->prev;
00491 }
00492 new_list->next = tmp_list;
00493 tmp_list->prev = new_list;
00494
00495 if (tmp_list == list)
00496 return new_list;
00497 else
00498 return list;
00499 }