opensync/opensync_list.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 Lesser 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  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser 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-2000.  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  * Modified for OpenSync by Armin Bauer (armin.bauer@desscon.com)
  27  */
  28
  29 /*
  30  * MT safe
  31  */
  32
  33 #include <glib/gmem.h>
  34 #include "opensync_list.h"
  35 #include "opensync_internals.h"
  36
  37 #define _osync_list_alloc()         g_slice_new (OSyncList)
  38 #define _osync_list_alloc0()        g_slice_new0 (OSyncList)
  39 #define _osync_list_free1(list)     g_slice_free (OSyncList, list)
  40
  41 OSyncList*
  42 osync_list_alloc (void)
  43 {
  44   return _osync_list_alloc0 ();
  45 }
  46
  47 void
  48 osync_list_free (OSyncList *list)
  49 {
  50   g_slice_free_chain (OSyncList, list, next);
  51 }
  52
  53 void
  54 osync_list_free_1 (OSyncList *list)
  55 {
  56   _osync_list_free1 (list);
  57 }
  58
  59 OSyncList*
  60 osync_list_append (OSyncList    *list,
  61                void *    data)
  62 {
  63   OSyncList *new_list;
  64   OSyncList *last;
  65
  66   new_list = _osync_list_alloc ();
  67   new_list->data = data;
  68   new_list->next = NULL;
  69
  70   if (list)
  71     {
  72       last = osync_list_last (list);
  73       /* osync_assert (last != NULL); */
  74       last->next = new_list;
  75       new_list->prev = last;
  76
  77       return list;
  78     }
  79   else
  80     {
  81       new_list->prev = NULL;
  82       return new_list;
  83     }
  84 }
  85
  86 OSyncList*
  87 osync_list_prepend (OSyncList    *list,
  88                 void *  data)
  89 {
  90   OSyncList *new_list;
  91
  92   new_list = _osync_list_alloc ();
  93   new_list->data = data;
  94   new_list->next = list;
  95
  96   if (list)
  97     {
  98       new_list->prev = list->prev;
  99       if (list->prev)
 100         list->prev->next = new_list;
 101       list->prev = new_list;
 102     }
 103   else
 104     new_list->prev = NULL;
 105
 106   return new_list;
 107 }
 108
 109 OSyncList*
 110 osync_list_insert (OSyncList    *list,
 111                void *    data,
 112                int       position)
 113 {
 114   OSyncList *new_list;
 115   OSyncList *tmp_list;
 116
 117   if (position < 0)
 118     return osync_list_append (list, data);
 119   else if (position == 0)
 120     return osync_list_prepend (list, data);
 121
 122   tmp_list = osync_list_nth (list, position);
 123   if (!tmp_list)
 124     return osync_list_append (list, data);
 125
 126   new_list = _osync_list_alloc ();
 127   new_list->data = data;
 128   new_list->prev = tmp_list->prev;
 129   if (tmp_list->prev)
 130     tmp_list->prev->next = new_list;
 131   new_list->next = tmp_list;
 132   tmp_list->prev = new_list;
 133
 134   if (tmp_list == list)
 135     return new_list;
 136   else
 137     return list;
 138 }
 139
 140 OSyncList*
 141 osync_list_insert_before (OSyncList   *list,
 142                       OSyncList   *sibling,
 143                       void * data)
 144 {
 145   if (!list)
 146     {
 147       list = osync_list_alloc ();
 148       list->data = data;
 149       g_return_val_if_fail (sibling == NULL, list);
 150       return list;
 151     }
 152   else if (sibling)
 153     {
 154       OSyncList *node;
 155
 156       node = _osync_list_alloc ();
 157       node->data = data;
 158       node->prev = sibling->prev;
 159       node->next = sibling;
 160       sibling->prev = node;
 161       if (node->prev)
 162         {
 163           node->prev->next = node;
 164           return list;
 165         }
 166       else
 167         {
 168           g_return_val_if_fail (sibling == list, node);
 169           return node;
 170         }
 171     }
 172   else
 173     {
 174       OSyncList *last;
 175
 176       last = list;
 177       while (last->next)
 178         last = last->next;
 179
 180       last->next = _osync_list_alloc ();
 181       last->next->data = data;
 182       last->next->prev = last;
 183       last->next->next = NULL;
 184
 185       return list;
 186     }
 187 }
 188
 189 OSyncList *
 190 osync_list_concat (OSyncList *list1, OSyncList *list2)
 191 {
 192   OSyncList *tmp_list;
 193
 194   if (list2)
 195     {
 196       tmp_list = osync_list_last (list1);
 197       if (tmp_list)
 198         tmp_list->next = list2;
 199       else
 200         list1 = list2;
 201       list2->prev = tmp_list;
 202     }
 203
 204   return list1;
 205 }
 206
 207 OSyncList*
 208 osync_list_remove (OSyncList         *list,
 209                void *  data)
 210 {
 211   OSyncList *tmp;
 212
 213   tmp = list;
 214   while (tmp)
 215     {
 216       if (tmp->data != data)
 217         tmp = tmp->next;
 218       else
 219         {
 220           if (tmp->prev)
 221             tmp->prev->next = tmp->next;
 222           if (tmp->next)
 223             tmp->next->prev = tmp->prev;
 224
 225           if (list == tmp)
 226             list = list->next;
 227
 228           _osync_list_free1 (tmp);
 229
 230           break;
 231         }
 232     }
 233   return list;
 234 }
 235
 236 OSyncList*
 237 osync_list_remove_all (OSyncList        *list,
 238                    void * data)
 239 {
 240   OSyncList *tmp = list;
 241
 242   while (tmp)
 243     {
 244       if (tmp->data != data)
 245         tmp = tmp->next;
 246       else
 247         {
 248           OSyncList *next = tmp->next;
 249
 250           if (tmp->prev)
 251             tmp->prev->next = next;
 252           else
 253             list = next;
 254           if (next)
 255             next->prev = tmp->prev;
 256
 257           _osync_list_free1 (tmp);
 258           tmp = next;
 259         }
 260     }
 261   return list;
 262 }
 263
 264 static inline OSyncList*
 265 _osync_list_remove_link (OSyncList *list,
 266                      OSyncList *link)
 267 {
 268   if (link)
 269     {
 270       if (link->prev)
 271         link->prev->next = link->next;
 272       if (link->next)
 273         link->next->prev = link->prev;
 274
 275       if (link == list)
 276         list = list->next;
 277
 278       link->next = NULL;
 279       link->prev = NULL;
 280     }
 281
 282   return list;
 283 }
 284
 285 OSyncList*
 286 osync_list_remove_link (OSyncList *list,
 287                     OSyncList *link)
 288 {
 289   return _osync_list_remove_link (list, link);
 290 }
 291
 292 OSyncList*
 293 osync_list_delete_link (OSyncList *list,
 294                     OSyncList *link)
 295 {
 296   list = _osync_list_remove_link (list, link);
 297   _osync_list_free1 (link);
 298
 299   return list;
 300 }
 301
 302 OSyncList*
 303 osync_list_copy (OSyncList *list)
 304 {
 305   OSyncList *new_list = NULL;
 306
 307   if (list)
 308     {
 309       OSyncList *last;
 310
 311       new_list = _osync_list_alloc ();
 312       new_list->data = list->data;
 313       new_list->prev = NULL;
 314       last = new_list;
 315       list = list->next;
 316       while (list)
 317         {
 318           last->next = _osync_list_alloc ();
 319           last->next->prev = last;
 320           last = last->next;
 321           last->data = list->data;
 322           list = list->next;
 323         }
 324       last->next = NULL;
 325     }
 326
 327   return new_list;
 328 }
 329
 330 OSyncList*
 331 osync_list_reverse (OSyncList *list)
 332 {
 333   OSyncList *last;
 334
 335   last = NULL;
 336   while (list)
 337     {
 338       last = list;
 339       list = last->next;
 340       last->next = last->prev;
 341       last->prev = list;
 342     }
 343
 344   return last;
 345 }
 346
 347 OSyncList*
 348 osync_list_nth (OSyncList *list,
 349             unsigned int  n)
 350 {
 351   while ((n-- > 0) && list)
 352     list = list->next;
 353
 354   return list;
 355 }
 356
 357 OSyncList*
 358 osync_list_nth_prev (OSyncList *list,
 359                  unsigned int  n)
 360 {
 361   while ((n-- > 0) && list)
 362     list = list->prev;
 363
 364   return list;
 365 }
 366
 367 void *
 368 osync_list_nth_data (OSyncList     *list,
 369                  unsigned int      n)
 370 {
 371   while ((n-- > 0) && list)
 372     list = list->next;
 373
 374   return list ? list->data : NULL;
 375 }
 376
 377 OSyncList*
 378 osync_list_find (OSyncList         *list,
 379              void *  data)
 380 {
 381   while (list)
 382     {
 383       if (list->data == data)
 384         break;
 385       list = list->next;
 386     }
 387
 388   return list;
 389 }
 390
 391 OSyncList*
 392 osync_list_find_custom (OSyncList         *list,
 393                     void *  data,
 394                     OSyncCompareFunc   func)
 395 {
 396   g_return_val_if_fail (func != NULL, list);
 397
 398   while (list)
 399     {
 400       if (! func (list->data, data))
 401         return list;
 402       list = list->next;
 403     }
 404
 405   return NULL;
 406 }
 407
 408
 409 int
 410 osync_list_position (OSyncList *list,
 411                  OSyncList *link)
 412 {
 413   int i;
 414
 415   i = 0;
 416   while (list)
 417     {
 418       if (list == link)
 419         return i;
 420       i++;
 421       list = list->next;
 422     }
 423
 424   return -1;
 425 }
 426
 427 int
 428 osync_list_index (OSyncList         *list,
 429               void *  data)
 430 {
 431   int i;
 432
 433   i = 0;
 434   while (list)
 435     {
 436       if (list->data == data)
 437         return i;
 438       i++;
 439       list = list->next;
 440     }
 441
 442   return -1;
 443 }
 444
 445 OSyncList*
 446 osync_list_last (OSyncList *list)
 447 {
 448   if (list)
 449     {
 450       while (list->next)
 451         list = list->next;
 452     }
 453
 454   return list;
 455 }
 456
 457 OSyncList*
 458 osync_list_first (OSyncList *list)
 459 {
 460   if (list)
 461     {
 462       while (list->prev)
 463         list = list->prev;
 464     }
 465
 466   return list;
 467 }
 468
 469 unsigned int
 470 osync_list_length (const OSyncList *list)
 471 {
 472   unsigned int length;
 473
 474   length = 0;
 475   while (list)
 476     {
 477       length++;
 478       list = list->next;
 479     }
 480
 481   return length;
 482 }
 483
 484 void
 485 osync_list_foreach (OSyncList    *list,
 486                 OSyncFunc         func,
 487                 void *  user_data)
 488 {
 489   while (list)
 490     {
 491       OSyncList *next = list->next;
 492       (*func) (list->data, user_data);
 493       list = next;
 494     }
 495 }
 496
 497 static OSyncList*
 498 osync_list_insert_sorted_real (OSyncList    *list,
 499                            void *  data,
 500                            OSyncFunc     func,
 501                            void *  user_data)
 502 {
 503   OSyncList *tmp_list = list;
 504   OSyncList *new_list;
 505   int cmp;
 506
 507   g_return_val_if_fail (func != NULL, list);
 508
 509   if (!list)
 510     {
 511       new_list = _osync_list_alloc0 ();
 512       new_list->data = data;
 513       return new_list;
 514     }
 515
 516   cmp = ((OSyncCompareDataFunc) func) (data, tmp_list->data, user_data);
 517
 518   while ((tmp_list->next) && (cmp > 0))
 519     {
 520       tmp_list = tmp_list->next;
 521
 522       cmp = ((OSyncCompareDataFunc) func) (data, tmp_list->data, user_data);
 523     }
 524
 525   new_list = _osync_list_alloc0 ();
 526   new_list->data = data;
 527
 528   if ((!tmp_list->next) && (cmp > 0))
 529     {
 530       tmp_list->next = new_list;
 531       new_list->prev = tmp_list;
 532       return list;
 533     }
 534
 535   if (tmp_list->prev)
 536     {
 537       tmp_list->prev->next = new_list;
 538       new_list->prev = tmp_list->prev;
 539     }
 540   new_list->next = tmp_list;
 541   tmp_list->prev = new_list;
 542
 543   if (tmp_list == list)
 544     return new_list;
 545   else
 546     return list;
 547 }
 548
 549 OSyncList*
 550 osync_list_insert_sorted (OSyncList        *list,
 551                       void *      data,
 552                       OSyncCompareFunc  func)
 553 {
 554   return osync_list_insert_sorted_real (list, data, (OSyncFunc) func, NULL);
 555 }
 556
 557 OSyncList*
 558 osync_list_insert_sorted_with_data (OSyncList            *list,
 559                                 void *          data,
 560                                 OSyncCompareDataFunc  func,
 561                                 void *          user_data)
 562 {
 563   return osync_list_insert_sorted_real (list, data, (OSyncFunc) func, user_data);
 564 }
 565
 566 static OSyncList *
 567 osync_list_sort_merge (OSyncList     *l1,
 568                    OSyncList     *l2,
 569                    OSyncFunc     compare_func,
 570                    void *  user_data)
 571 {
 572   OSyncList list, *l, *lprev;
 573   int cmp;
 574
 575   l = &list;
 576   lprev = NULL;
 577
 578   while (l1 && l2)
 579     {
 580       cmp = ((OSyncCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 581
 582       if (cmp <= 0)
 583         {
 584           l->next = l1;
 585           l1 = l1->next;
 586         }
 587       else
 588         {
 589           l->next = l2;
 590           l2 = l2->next;
 591         }
 592       l = l->next;
 593       l->prev = lprev;
 594       lprev = l;
 595     }
 596   l->next = l1 ? l1 : l2;
 597   l->next->prev = l;
 598
 599   return list.next;
 600 }
 601
 602 static OSyncList*
 603 osync_list_sort_real (OSyncList    *list,
 604                   OSyncFunc     compare_func,
 605                   void *  user_data)
 606 {
 607   OSyncList *l1, *l2;
 608
 609   if (!list)
 610     return NULL;
 611   if (!list->next)
 612     return list;
 613
 614   l1 = list;
 615   l2 = list->next;
 616
 617   while ((l2 = l2->next) != NULL)
 618     {
 619       if ((l2 = l2->next) == NULL)
 620         break;
 621       l1 = l1->next;
 622     }
 623   l2 = l1->next;
 624   l1->next = NULL;
 625
 626   return osync_list_sort_merge (osync_list_sort_real (list, compare_func, user_data),
 627                             osync_list_sort_real (l2, compare_func, user_data),
 628                             compare_func,
 629                             user_data);
 630 }
 631
 632 OSyncList *
 633 osync_list_sort (OSyncList        *list,
 634              OSyncCompareFunc  compare_func)
 635 {
 636   return osync_list_sort_real (list, (OSyncFunc) compare_func, NULL);
 637
 638 }
 639
 640 OSyncList *
 641 osync_list_sort_with_data (OSyncList            *list,
 642                        OSyncCompareDataFunc  compare_func,
 643                        void *          user_data)
 644 {
 645   return osync_list_sort_real (list, (OSyncFunc) compare_func, user_data);
 646 }