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_reverse (GSList *list)
 260 {
 261   GSList *tmp;
 262   GSList *prev;
 263   GSList *last;
 264
 265   last = NULL;
 266   prev = NULL;
 267
 268   while (list)
 269     {
 270       last = list;
 271
 272       tmp = list->next;
 273       list->next = prev;
 274
 275       prev = list;
 276       list = tmp;
 277     }
 278
 279   return last;
 280 }
 281
 282 GSList*
 283 g_slist_nth (GSList *list,
 284              guint   n)
 285 {
 286   while ((n-- > 0) && list)
 287     list = list->next;
 288
 289   return list;
 290 }
 291
 292 gpointer
 293 g_slist_nth_data (GSList   *list,
 294                   guint     n)
 295 {
 296   while ((n-- > 0) && list)
 297     list = list->next;
 298
 299   return list ? list->data : NULL;
 300 }
 301
 302 GSList*
 303 g_slist_find (GSList   *list,
 304               gpointer  data)
 305 {
 306   while (list)
 307     {
 308       if (list->data == data)
 309         break;
 310       list = list->next;
 311     }
 312
 313   return list;
 314 }
 315
 316 GSList*
 317 g_slist_find_custom (GSList      *list,
 318                      gpointer     data,
 319                      GCompareFunc func)
 320 {
 321   g_return_val_if_fail (func != NULL, list);
 322
 323   while (list)
 324     {
 325       if (! func (list->data, data))
 326         return list;
 327       list = list->next;
 328     }
 329
 330   return NULL;
 331 }
 332
 333 gint
 334 g_slist_position (GSList *list,
 335                   GSList *link)
 336 {
 337   gint i;
 338
 339   i = 0;
 340   while (list)
 341     {
 342       if (list == link)
 343         return i;
 344       i++;
 345       list = list->next;
 346     }
 347
 348   return -1;
 349 }
 350
 351 gint
 352 g_slist_index (GSList   *list,
 353                gpointer data)
 354 {
 355   gint i;
 356
 357   i = 0;
 358   while (list)
 359     {
 360       if (list->data == data)
 361         return i;
 362       i++;
 363       list = list->next;
 364     }
 365
 366   return -1;
 367 }
 368
 369 GSList*
 370 g_slist_last (GSList *list)
 371 {
 372   if (list)
 373     {
 374       while (list->next)
 375         list = list->next;
 376     }
 377
 378   return list;
 379 }
 380
 381 guint
 382 g_slist_length (GSList *list)
 383 {
 384   guint length;
 385
 386   length = 0;
 387   while (list)
 388     {
 389       length++;
 390       list = list->next;
 391     }
 392
 393   return length;
 394 }
 395
 396 void
 397 g_slist_foreach (GSList   *list,
 398                  GFunc     func,
 399                  gpointer  user_data)
 400 {
 401   while (list)
 402     {
 403       (*func) (list->data, user_data);
 404       list = list->next;
 405     }
 406 }
 407
 408 GSList*
 409 g_slist_insert_sorted (GSList       *list,
 410                        gpointer      data,
 411                        GCompareFunc  func)
 412 {
 413   GSList *tmp_list = list;
 414   GSList *prev_list = NULL;
 415   GSList *new_list;
 416   gint cmp;
 417
 418   g_return_val_if_fail (func != NULL, list);
 419
 420   if (!list)
 421     {
 422       new_list = g_slist_alloc();
 423       new_list->data = data;
 424       return new_list;
 425     }
 426
 427   cmp = (*func) (data, tmp_list->data);
 428
 429   while ((tmp_list->next) && (cmp > 0))
 430     {
 431       prev_list = tmp_list;
 432       tmp_list = tmp_list->next;
 433       cmp = (*func) (data, tmp_list->data);
 434     }
 435
 436   new_list = g_slist_alloc();
 437   new_list->data = data;
 438
 439   if ((!tmp_list->next) && (cmp > 0))
 440     {
 441       tmp_list->next = new_list;
 442       return list;
 443     }
 444
 445   if (prev_list)
 446     {
 447       prev_list->next = new_list;
 448       new_list->next = tmp_list;
 449       return list;
 450     }
 451   else
 452     {
 453       new_list->next = list;
 454       return new_list;
 455     }
 456 }