gslist.c

   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 #include "glib.h"
  20
  21
  22 typedef struct _GRealListAllocator GRealListAllocator;
  23
  24 struct _GRealListAllocator
  25 {
  26   GMemChunk *list_mem_chunk;
  27   GSList    *free_list;
  28 };
  29
  30
  31 static GRealListAllocator *default_allocator = NULL;
  32 static GRealListAllocator *current_allocator = NULL;
  33
  34 GListAllocator*
  35 g_slist_set_allocator (GListAllocator* fallocator)
  36 {
  37   GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
  38   GRealListAllocator* old_allocator = current_allocator;
  39
  40   if (allocator)
  41     current_allocator = allocator;
  42   else
  43     {
  44       if (!default_allocator)
  45         default_allocator = (GRealListAllocator*) g_list_allocator_new ();
  46       current_allocator = default_allocator;
  47     }
  48
  49   if (!current_allocator->list_mem_chunk)
  50     current_allocator->list_mem_chunk = g_mem_chunk_new ("slist mem chunk",
  51                                                          sizeof (GSList),
  52                                                          1024,
  53                                                          G_ALLOC_ONLY);
  54
  55   return (GListAllocator*) (old_allocator == default_allocator ? NULL : old_allocator);
  56 }
  57
  58
  59 GSList*
  60 g_slist_alloc (void)
  61 {
  62   GSList *new_list;
  63
  64   g_slist_set_allocator (NULL);
  65   if (current_allocator->free_list)
  66     {
  67       new_list = current_allocator->free_list;
  68       current_allocator->free_list = current_allocator->free_list->next;
  69     }
  70   else
  71     {
  72       new_list = g_chunk_new (GSList, current_allocator->list_mem_chunk);
  73     }
  74
  75   new_list->data = NULL;
  76   new_list->next = NULL;
  77
  78   return new_list;
  79 }
  80
  81 void
  82 g_slist_free (GSList *list)
  83 {
  84   GSList *last;
  85
  86   if (list)
  87     {
  88       last = g_slist_last (list);
  89       last->next = current_allocator->free_list;
  90       current_allocator->free_list = list;
  91     }
  92 }
  93
  94 void
  95 g_slist_free_1 (GSList *list)
  96 {
  97   if (list)
  98     {
  99       list->next = current_allocator->free_list;
 100       current_allocator->free_list = list;
 101     }
 102 }
 103
 104 GSList*
 105 g_slist_append (GSList   *list,
 106                 gpointer  data)
 107 {
 108   GSList *new_list;
 109   GSList *last;
 110
 111   new_list = g_slist_alloc ();
 112   new_list->data = data;
 113
 114   if (list)
 115     {
 116       last = g_slist_last (list);
 117       /* g_assert (last != NULL); */
 118       last->next = new_list;
 119
 120       return list;
 121     }
 122   else
 123       return new_list;
 124 }
 125
 126 GSList*
 127 g_slist_prepend (GSList   *list,
 128                  gpointer  data)
 129 {
 130   GSList *new_list;
 131
 132   new_list = g_slist_alloc ();
 133   new_list->data = data;
 134   new_list->next = list;
 135
 136   return new_list;
 137 }
 138
 139 GSList*
 140 g_slist_insert (GSList   *list,
 141                 gpointer  data,
 142                 gint      position)
 143 {
 144   GSList *prev_list;
 145   GSList *tmp_list;
 146   GSList *new_list;
 147
 148   if (position < 0)
 149     return g_slist_append (list, data);
 150   else if (position == 0)
 151     return g_slist_prepend (list, data);
 152
 153   new_list = g_slist_alloc ();
 154   new_list->data = data;
 155
 156   if (!list)
 157     return new_list;
 158
 159   prev_list = NULL;
 160   tmp_list = list;
 161
 162   while ((position-- > 0) && tmp_list)
 163     {
 164       prev_list = tmp_list;
 165       tmp_list = tmp_list->next;
 166     }
 167
 168   if (prev_list)
 169     {
 170       new_list->next = prev_list->next;
 171       prev_list->next = new_list;
 172     }
 173   else
 174     {
 175       new_list->next = list;
 176       list = new_list;
 177     }
 178
 179   return list;
 180 }
 181
 182 GSList *
 183 g_slist_concat (GSList *list1, GSList *list2)
 184 {
 185   if (list2)
 186     {
 187       if (list1)
 188         g_slist_last (list1)->next = list2;
 189       else
 190         list1 = list2;
 191     }
 192
 193   return list1;
 194 }
 195
 196 GSList*
 197 g_slist_remove (GSList   *list,
 198                 gpointer  data)
 199 {
 200   GSList *tmp;
 201   GSList *prev;
 202
 203   prev = NULL;
 204   tmp = list;
 205
 206   while (tmp)
 207     {
 208       if (tmp->data == data)
 209         {
 210           if (prev)
 211             prev->next = tmp->next;
 212           if (list == tmp)
 213             list = list->next;
 214
 215           tmp->next = NULL;
 216           g_slist_free (tmp);
 217
 218           break;
 219         }
 220
 221       prev = tmp;
 222       tmp = tmp->next;
 223     }
 224
 225   return list;
 226 }
 227
 228 GSList*
 229 g_slist_remove_link (GSList *list,
 230                      GSList *link)
 231 {
 232   GSList *tmp;
 233   GSList *prev;
 234
 235   prev = NULL;
 236   tmp = list;
 237
 238   while (tmp)
 239     {
 240       if (tmp == link)
 241         {
 242           if (prev)
 243             prev->next = tmp->next;
 244           if (list == tmp)
 245             list = list->next;
 246
 247           tmp->next = NULL;
 248           break;
 249         }
 250
 251       prev = tmp;
 252       tmp = tmp->next;
 253     }
 254
 255   return list;
 256 }
 257
 258 GSList*
 259 g_slist_copy (GSList *list)
 260 {
 261   GSList *new_list = NULL;
 262
 263   if (list)
 264     {
 265       GSList *last;
 266
 267       new_list = g_slist_alloc ();
 268       new_list->data = list->data;
 269       last = new_list;
 270       list = list->next;
 271       while (list)
 272         {
 273           last->next = g_slist_alloc ();
 274           last = last->next;
 275           last->data = list->data;
 276           list = list->next;
 277         }
 278     }
 279
 280   return new_list;
 281 }
 282
 283 GSList*
 284 g_slist_reverse (GSList *list)
 285 {
 286   GSList *tmp;
 287   GSList *prev;
 288   GSList *last;
 289
 290   last = NULL;
 291   prev = NULL;
 292
 293   while (list)
 294     {
 295       last = list;
 296
 297       tmp = list->next;
 298       list->next = prev;
 299
 300       prev = list;
 301       list = tmp;
 302     }
 303
 304   return last;
 305 }
 306
 307 GSList*
 308 g_slist_nth (GSList *list,
 309              guint   n)
 310 {
 311   while ((n-- > 0) && list)
 312     list = list->next;
 313
 314   return list;
 315 }
 316
 317 gpointer
 318 g_slist_nth_data (GSList   *list,
 319                   guint     n)
 320 {
 321   while ((n-- > 0) && list)
 322     list = list->next;
 323
 324   return list ? list->data : NULL;
 325 }
 326
 327 GSList*
 328 g_slist_find (GSList   *list,
 329               gpointer  data)
 330 {
 331   while (list)
 332     {
 333       if (list->data == data)
 334         break;
 335       list = list->next;
 336     }
 337
 338   return list;
 339 }
 340
 341 GSList*
 342 g_slist_find_custom (GSList      *list,
 343                      gpointer     data,
 344                      GCompareFunc func)
 345 {
 346   g_return_val_if_fail (func != NULL, list);
 347
 348   while (list)
 349     {
 350       if (! func (list->data, data))
 351         return list;
 352       list = list->next;
 353     }
 354
 355   return NULL;
 356 }
 357
 358 gint
 359 g_slist_position (GSList *list,
 360                   GSList *link)
 361 {
 362   gint i;
 363
 364   i = 0;
 365   while (list)
 366     {
 367       if (list == link)
 368         return i;
 369       i++;
 370       list = list->next;
 371     }
 372
 373   return -1;
 374 }
 375
 376 gint
 377 g_slist_index (GSList   *list,
 378                gpointer data)
 379 {
 380   gint i;
 381
 382   i = 0;
 383   while (list)
 384     {
 385       if (list->data == data)
 386         return i;
 387       i++;
 388       list = list->next;
 389     }
 390
 391   return -1;
 392 }
 393
 394 GSList*
 395 g_slist_last (GSList *list)
 396 {
 397   if (list)
 398     {
 399       while (list->next)
 400         list = list->next;
 401     }
 402
 403   return list;
 404 }
 405
 406 guint
 407 g_slist_length (GSList *list)
 408 {
 409   guint length;
 410
 411   length = 0;
 412   while (list)
 413     {
 414       length++;
 415       list = list->next;
 416     }
 417
 418   return length;
 419 }
 420
 421 void
 422 g_slist_foreach (GSList   *list,
 423                  GFunc     func,
 424                  gpointer  user_data)
 425 {
 426   while (list)
 427     {
 428       (*func) (list->data, user_data);
 429       list = list->next;
 430     }
 431 }
 432
 433 GSList*
 434 g_slist_insert_sorted (GSList       *list,
 435                        gpointer      data,
 436                        GCompareFunc  func)
 437 {
 438   GSList *tmp_list = list;
 439   GSList *prev_list = NULL;
 440   GSList *new_list;
 441   gint cmp;
 442
 443   g_return_val_if_fail (func != NULL, list);
 444
 445   if (!list)
 446     {
 447       new_list = g_slist_alloc();
 448       new_list->data = data;
 449       return new_list;
 450     }
 451
 452   cmp = (*func) (data, tmp_list->data);
 453
 454   while ((tmp_list->next) && (cmp > 0))
 455     {
 456       prev_list = tmp_list;
 457       tmp_list = tmp_list->next;
 458       cmp = (*func) (data, tmp_list->data);
 459     }
 460
 461   new_list = g_slist_alloc();
 462   new_list->data = data;
 463
 464   if ((!tmp_list->next) && (cmp > 0))
 465     {
 466       tmp_list->next = new_list;
 467       return list;
 468     }
 469
 470   if (prev_list)
 471     {
 472       prev_list->next = new_list;
 473       new_list->next = tmp_list;
 474       return list;
 475     }
 476   else
 477     {
 478       new_list->next = list;
 479       return new_list;
 480     }
 481 }
 482
 483 static GSList*
 484 g_slist_sort_merge  (GSList      *l1,
 485                      GSList      *l2,
 486                      GCompareFunc compare_func)
 487 {
 488   GSList list, *l;
 489
 490   l=&list;
 491
 492   while (l1 && l2)
 493     {
 494       if (compare_func(l1->data,l2->data) < 0)
 495         {
 496           l=l->next=l1;
 497           l1=l1->next;
 498         }
 499       else
 500         {
 501           l=l->next=l2;
 502           l2=l2->next;
 503         }
 504     }
 505   l->next= l1 ? l1 : l2;
 506
 507   return list.next;
 508 }
 509
 510 GSList*
 511 g_slist_sort (GSList       *list,
 512               GCompareFunc compare_func)
 513 {
 514   GSList *l1, *l2;
 515
 516   if (!list)
 517     return NULL;
 518   if (!list->next)
 519     return list;
 520
 521   l1 = list;
 522   l2 = list->next;
 523
 524   while ((l2 = l2->next) != NULL)
 525     {
 526       if ((l2 = l2->next) == NULL)
 527         break;
 528       l1=l1->next;
 529     }
 530   l2 = l1->next;
 531   l1->next = NULL;
 532
 533   return g_slist_sort_merge (g_slist_sort (list, compare_func),
 534                              g_slist_sort (l2,   compare_func),
 535                              compare_func);
 536 }