1/* GLIB - Library of useful routines for C programming 2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public 15 * License along with this library; if not, write to the 16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 * Boston, MA 02111-1307, USA. 18 */ 19 20/* 21 * Modified by the GLib Team and others 1997-1999. See the AUTHORS 22 * file for a list of people on the GLib Team. See the ChangeLog 23 * files for a list of changes. These files are distributed with 24 * GLib at ftp://ftp.gtk.org/pub/gtk/. 25 */ 26 27/* 28 * MT safe 29 */ 30 31#include "glib.h" 32 33 34struct _GAllocator /* from gmem.c */ 35{ 36 gchar *name; 37 guint16 n_preallocs; 38 guint is_unused : 1; 39 guint type : 4; 40 GAllocator *last; 41 GMemChunk *mem_chunk; 42 GSList *free_lists; /* implementation specific */ 43}; 44 45G_LOCK_DEFINE_STATIC (current_allocator); 46static GAllocator *current_allocator = NULL; 47 48/* HOLDS: current_allocator_lock */ 49static void 50g_slist_validate_allocator (GAllocator *allocator) 51{ 52 g_return_if_fail (allocator != NULL); 53 g_return_if_fail (allocator->is_unused == TRUE); 54 55 if (allocator->type != G_ALLOCATOR_SLIST) 56 { 57 allocator->type = G_ALLOCATOR_SLIST; 58 if (allocator->mem_chunk) 59 { 60 g_mem_chunk_destroy (allocator->mem_chunk); 61 allocator->mem_chunk = NULL; 62 } 63 } 64 65 if (!allocator->mem_chunk) 66 { 67 allocator->mem_chunk = g_mem_chunk_new (allocator->name, 68 sizeof (GSList), 69 sizeof (GSList) * allocator->n_preallocs, 70 G_ALLOC_ONLY); 71 allocator->free_lists = NULL; 72 } 73 74 allocator->is_unused = FALSE; 75} 76 77void 78g_slist_push_allocator (GAllocator *allocator) 79{ 80 G_LOCK (current_allocator); 81 g_slist_validate_allocator (allocator); 82 allocator->last = current_allocator; 83 current_allocator = allocator; 84 G_UNLOCK (current_allocator); 85} 86 87void 88g_slist_pop_allocator (void) 89{ 90 G_LOCK (current_allocator); 91 if (current_allocator) 92 { 93 GAllocator *allocator; 94 95 allocator = current_allocator; 96 current_allocator = allocator->last; 97 allocator->last = NULL; 98 allocator->is_unused = TRUE; 99 } 100 G_UNLOCK (current_allocator); 101} 102 103GSList* 104g_slist_alloc (void) 105{ 106 GSList *list; 107 108 G_LOCK (current_allocator); 109 if (!current_allocator) 110 { 111 GAllocator *allocator = g_allocator_new ("GLib default GSList allocator", 112 128); 113 g_slist_validate_allocator (allocator); 114 allocator->last = NULL; 115 current_allocator = allocator; 116 } 117 if (!current_allocator->free_lists) 118 { 119 list = g_chunk_new (GSList, current_allocator->mem_chunk); 120 list->data = NULL; 121 } 122 else 123 { 124 if (current_allocator->free_lists->data) 125 { 126 list = current_allocator->free_lists->data; 127 current_allocator->free_lists->data = list->next; 128 list->data = NULL; 129 } 130 else 131 { 132 list = current_allocator->free_lists; 133 current_allocator->free_lists = list->next; 134 } 135 } 136 G_UNLOCK (current_allocator); 137 138 list->next = NULL; 139 140 return list; 141} 142 143void 144g_slist_free (GSList *list) 145{ 146 if (list) 147 { 148 list->data = list->next; 149 G_LOCK (current_allocator); 150 list->next = current_allocator->free_lists; 151 current_allocator->free_lists = list; 152 G_UNLOCK (current_allocator); 153 } 154} 155 156void 157g_slist_free_1 (GSList *list) 158{ 159 if (list) 160 { 161 list->data = NULL; 162 G_LOCK (current_allocator); 163 list->next = current_allocator->free_lists; 164 current_allocator->free_lists = list; 165 G_UNLOCK (current_allocator); 166 } 167} 168 169GSList* 170g_slist_append (GSList *list, 171 gpointer data) 172{ 173 GSList *new_list; 174 GSList *last; 175 176 new_list = g_slist_alloc (); 177 new_list->data = data; 178 179 if (list) 180 { 181 last = g_slist_last (list); 182 /* g_assert (last != NULL); */ 183 last->next = new_list; 184 185 return list; 186 } 187 else 188 return new_list; 189} 190 191GSList* 192g_slist_prepend (GSList *list, 193 gpointer data) 194{ 195 GSList *new_list; 196 197 new_list = g_slist_alloc (); 198 new_list->data = data; 199 new_list->next = list; 200 201 return new_list; 202} 203 204GSList* 205g_slist_insert (GSList *list, 206 gpointer data, 207 gint position) 208{ 209 GSList *prev_list; 210 GSList *tmp_list; 211 GSList *new_list; 212 213 if (position < 0) 214 return g_slist_append (list, data); 215 else if (position == 0) 216 return g_slist_prepend (list, data); 217 218 new_list = g_slist_alloc (); 219 new_list->data = data; 220 221 if (!list) 222 return new_list; 223 224 prev_list = NULL; 225 tmp_list = list; 226 227 while ((position-- > 0) && tmp_list) 228 { 229 prev_list = tmp_list; 230 tmp_list = tmp_list->next; 231 } 232 233 if (prev_list) 234 { 235 new_list->next = prev_list->next; 236 prev_list->next = new_list; 237 } 238 else 239 { 240 new_list->next = list; 241 list = new_list; 242 } 243 244 return list; 245} 246 247GSList * 248g_slist_concat (GSList *list1, GSList *list2) 249{ 250 if (list2) 251 { 252 if (list1) 253 g_slist_last (list1)->next = list2; 254 else 255 list1 = list2; 256 } 257 258 return list1; 259} 260 261GSList* 262g_slist_remove (GSList *list, 263 gpointer data) 264{ 265 GSList *tmp; 266 GSList *prev; 267 268 prev = NULL; 269 tmp = list; 270 271 while (tmp) 272 { 273 if (tmp->data == data) 274 { 275 if (prev) 276 prev->next = tmp->next; 277 if (list == tmp) 278 list = list->next; 279 280 tmp->next = NULL; 281 g_slist_free (tmp); 282 283 break; 284 } 285 286 prev = tmp; 287 tmp = tmp->next; 288 } 289 290 return list; 291} 292 293GSList* 294g_slist_remove_link (GSList *list, 295 GSList *link) 296{ 297 GSList *tmp; 298 GSList *prev; 299 300 prev = NULL; 301 tmp = list; 302 303 while (tmp) 304 { 305 if (tmp == link) 306 { 307 if (prev) 308 prev->next = tmp->next; 309 if (list == tmp) 310 list = list->next; 311 312 tmp->next = NULL; 313 break; 314 } 315 316 prev = tmp; 317 tmp = tmp->next; 318 } 319 320 return list; 321} 322 323GSList* 324g_slist_copy (GSList *list) 325{ 326 GSList *new_list = NULL; 327 328 if (list) 329 { 330 GSList *last; 331 332 new_list = g_slist_alloc (); 333 new_list->data = list->data; 334 last = new_list; 335 list = list->next; 336 while (list) 337 { 338 last->next = g_slist_alloc (); 339 last = last->next; 340 last->data = list->data; 341 list = list->next; 342 } 343 } 344 345 return new_list; 346} 347 348GSList* 349g_slist_reverse (GSList *list) 350{ 351 GSList *prev = NULL; 352 353 while (list) 354 { 355 GSList *next = list->next; 356 357 list->next = prev; 358 359 prev = list; 360 list = next; 361 } 362 363 return prev; 364} 365 366GSList* 367g_slist_nth (GSList *list, 368 guint n) 369{ 370 while ((n-- > 0) && list) 371 list = list->next; 372 373 return list; 374} 375 376gpointer 377g_slist_nth_data (GSList *list, 378 guint n) 379{ 380 while ((n-- > 0) && list) 381 list = list->next; 382 383 return list ? list->data : NULL; 384} 385 386GSList* 387g_slist_find (GSList *list, 388 gpointer data) 389{ 390 while (list) 391 { 392 if (list->data == data) 393 break; 394 list = list->next; 395 } 396 397 return list; 398} 399 400GSList* 401g_slist_find_custom (GSList *list, 402 gpointer data, 403 GCompareFunc func) 404{ 405 g_return_val_if_fail (func != NULL, list); 406 407 while (list) 408 { 409 if (! func (list->data, data)) 410 return list; 411 list = list->next; 412 } 413 414 return NULL; 415} 416 417gint 418g_slist_position (GSList *list, 419 GSList *link) 420{ 421 gint i; 422 423 i = 0; 424 while (list) 425 { 426 if (list == link) 427 return i; 428 i++; 429 list = list->next; 430 } 431 432 return -1; 433} 434 435gint 436g_slist_index (GSList *list, 437 gpointer data) 438{ 439 gint i; 440 441 i = 0; 442 while (list) 443 { 444 if (list->data == data) 445 return i; 446 i++; 447 list = list->next; 448 } 449 450 return -1; 451} 452 453GSList* 454g_slist_last (GSList *list) 455{ 456 if (list) 457 { 458 while (list->next) 459 list = list->next; 460 } 461 462 return list; 463} 464 465guint 466g_slist_length (GSList *list) 467{ 468 guint length; 469 470 length = 0; 471 while (list) 472 { 473 length++; 474 list = list->next; 475 } 476 477 return length; 478} 479 480void 481g_slist_foreach (GSList *list, 482 GFunc func, 483 gpointer user_data) 484{ 485 while (list) 486 { 487 (*func) (list->data, user_data); 488 list = list->next; 489 } 490} 491 492GSList* 493g_slist_insert_sorted (GSList *list, 494 gpointer data, 495 GCompareFunc func) 496{ 497 GSList *tmp_list = list; 498 GSList *prev_list = NULL; 499 GSList *new_list; 500 gint cmp; 501 502 g_return_val_if_fail (func != NULL, list); 503 504 if (!list) 505 { 506 new_list = g_slist_alloc(); 507 new_list->data = data; 508 return new_list; 509 } 510 511 cmp = (*func) (data, tmp_list->data); 512 513 while ((tmp_list->next) && (cmp > 0)) 514 { 515 prev_list = tmp_list; 516 tmp_list = tmp_list->next; 517 cmp = (*func) (data, tmp_list->data); 518 } 519 520 new_list = g_slist_alloc(); 521 new_list->data = data; 522 523 if ((!tmp_list->next) && (cmp > 0)) 524 { 525 tmp_list->next = new_list; 526 return list; 527 } 528 529 if (prev_list) 530 { 531 prev_list->next = new_list; 532 new_list->next = tmp_list; 533 return list; 534 } 535 else 536 { 537 new_list->next = list; 538 return new_list; 539 } 540} 541 542static GSList* 543g_slist_sort_merge (GSList *l1, 544 GSList *l2, 545 GCompareFunc compare_func) 546{ 547 GSList list, *l; 548 549 l=&list; 550 551 while (l1 && l2) 552 { 553 if (compare_func(l1->data,l2->data) < 0) 554 { 555 l=l->next=l1; 556 l1=l1->next; 557 } 558 else 559 { 560 l=l->next=l2; 561 l2=l2->next; 562 } 563 } 564 l->next= l1 ? l1 : l2; 565 566 return list.next; 567} 568 569GSList* 570g_slist_sort (GSList *list, 571 GCompareFunc compare_func) 572{ 573 GSList *l1, *l2; 574 575 if (!list) 576 return NULL; 577 if (!list->next) 578 return list; 579 580 l1 = list; 581 l2 = list->next; 582 583 while ((l2 = l2->next) != NULL) 584 { 585 if ((l2 = l2->next) == NULL) 586 break; 587 l1=l1->next; 588 } 589 l2 = l1->next; 590 l1->next = NULL; 591 592 return g_slist_sort_merge (g_slist_sort (list, compare_func), 593 g_slist_sort (l2, compare_func), 594 compare_func); 595} 596