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