mono/eglib/gslist.c

   1 /*
   2  * gslist.c: Singly-linked list implementation
   3  *
   4  * Authors:
   5  *   Duncan Mak (duncan@novell.com)
   6  *   Raja R Harinath (rharinath@novell.com)
   7  *
   8  * Permission is hereby granted, free of charge, to any person obtaining
   9  * a copy of this software and associated documentation files (the
  10  * "Software"), to deal in the Software without restriction, including
  11  * without limitation the rights to use, copy, modify, merge, publish,
  12  * distribute, sublicense, and/or sell copies of the Software, and to
  13  * permit persons to whom the Software is furnished to do so, subject to
  14  * the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be
  17  * included in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26  *
  27  * (C) 2006 Novell, Inc.
  28  */
  29
  30 #include <stdio.h>
  31 #include <glib.h>
  32
  33 GSList*
  34 g_slist_alloc (void)
  35 {
  36         return g_new0 (GSList, 1);
  37 }
  38
  39 void
  40 g_slist_free_1 (GSList *list)
  41 {
  42         g_free (list);
  43 }
  44
  45 GSList*
  46 g_slist_append (GSList *list, gpointer data)
  47 {
  48         return g_slist_concat (list, g_slist_prepend (NULL, data));
  49 }
  50
  51 /* This is also a list node constructor. */
  52 GSList*
  53 g_slist_prepend (GSList *list, gpointer data)
  54 {
  55         GSList *head = g_slist_alloc ();
  56         head->data = data;
  57         head->next = list;
  58
  59         return head;
  60 }
  61
  62 /*
  63  * Insert the given data in a new node after the current node.
  64  * Return new node.
  65  */
  66 static inline GSList *
  67 insert_after (GSList *list, gpointer data)
  68 {
  69         list->next = g_slist_prepend (list->next, data);
  70         return list->next;
  71 }
  72
  73 /*
  74  * Return the node prior to the node containing 'data'.
  75  * If the list is empty, or the first node contains 'data', return NULL.
  76  * If no node contains 'data', return the last node.
  77  */
  78 static inline GSList*
  79 find_prev (GSList *list, gconstpointer data)
  80 {
  81         GSList *prev = NULL;
  82         while (list) {
  83                 if (list->data == data)
  84                         break;
  85                 prev = list;
  86                 list = list->next;
  87         }
  88         return prev;
  89 }
  90
  91 /* like 'find_prev', but searches for node 'link' */
  92 static inline GSList*
  93 find_prev_link (GSList *list, GSList *link)
  94 {
  95         GSList *prev = NULL;
  96         while (list) {
  97                 if (list == link)
  98                         break;
  99                 prev = list;
 100                 list = list->next;
 101         }
 102         return prev;
 103 }
 104
 105 GSList*
 106 g_slist_insert_before (GSList *list, GSList *sibling, gpointer data)
 107 {
 108         GSList *prev = find_prev_link (list, sibling);
 109
 110         if (!prev)
 111                 return g_slist_prepend (list, data);
 112
 113         insert_after (prev, data);
 114         return list;
 115 }
 116
 117 void
 118 g_slist_free (GSList *list)
 119 {
 120         while (list) {
 121                 GSList *next = list->next;
 122                 g_slist_free_1 (list);
 123                 list = next;
 124         }
 125 }
 126
 127 GSList*
 128 g_slist_copy (GSList *list)
 129 {
 130         GSList *copy, *tmp;
 131
 132         if (!list)
 133                 return NULL;
 134
 135         copy = g_slist_prepend (NULL, list->data);
 136         tmp = copy;
 137
 138         for (list = list->next; list; list = list->next)
 139                 tmp = insert_after (tmp, list->data);
 140
 141         return copy;
 142 }
 143
 144 GSList*
 145 g_slist_concat (GSList *list1, GSList *list2)
 146 {
 147         if (!list1)
 148                 return list2;
 149
 150         g_slist_last (list1)->next = list2;
 151         return list1;
 152 }
 153
 154 void
 155 g_slist_foreach (GSList *list, GFunc func, gpointer user_data)
 156 {
 157         while (list) {
 158                 (*func) (list->data, user_data);
 159                 list = list->next;
 160         }
 161 }
 162
 163 GSList*
 164 g_slist_last (GSList *list)
 165 {
 166         if (!list)
 167                 return NULL;
 168
 169         while (list->next)
 170                 list = list->next;
 171
 172         return list;
 173 }
 174
 175 GSList*
 176 g_slist_find (GSList *list, gconstpointer data)
 177 {
 178         for (; list; list = list->next)
 179                 if (list->data == data)
 180                         break;
 181         return list;
 182 }
 183
 184 GSList *
 185 g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func)
 186 {
 187         if (!func)
 188                 return NULL;
 189
 190         while (list) {
 191                 if (func (list->data, data) == 0)
 192                         return list;
 193
 194                 list = list->next;
 195         }
 196
 197         return NULL;
 198 }
 199
 200 guint
 201 g_slist_length (GSList *list)
 202 {
 203         guint length = 0;
 204
 205         while (list) {
 206                 length ++;
 207                 list = list->next;
 208         }
 209
 210         return length;
 211 }
 212
 213 GSList*
 214 g_slist_remove (GSList *list, gconstpointer data)
 215 {
 216         GSList *prev = find_prev (list, data);
 217         GSList *current = prev ? prev->next : list;
 218
 219         if (current) {
 220                 if (prev)
 221                         prev->next = current->next;
 222                 else
 223                         list = current->next;
 224                 g_slist_free_1 (current);
 225         }
 226
 227         return list;
 228 }
 229
 230 GSList*
 231 g_slist_remove_all (GSList *list, gconstpointer data)
 232 {
 233         GSList *next = list;
 234         GSList *prev = NULL;
 235         GSList *current;
 236
 237         while (next) {
 238                 GSList *tmp_prev = find_prev (next, data);
 239                 if (tmp_prev)
 240                         prev = tmp_prev;
 241                 current = prev ? prev->next : list;
 242
 243                 if (!current)
 244                         break;
 245
 246                 next = current->next;
 247
 248                 if (prev)
 249                         prev->next = next;
 250                 else
 251                         list = next;
 252                 g_slist_free_1 (current);
 253         }
 254
 255         return list;
 256 }
 257
 258 GSList*
 259 g_slist_remove_link (GSList *list, GSList *link)
 260 {
 261         GSList *prev = find_prev_link (list, link);
 262         GSList *current = prev ? prev->next : list;
 263
 264         if (current) {
 265                 if (prev)
 266                         prev->next = current->next;
 267                 else
 268                         list = current->next;
 269                 current->next = NULL;
 270         }
 271
 272         return list;
 273 }
 274
 275 GSList*
 276 g_slist_delete_link (GSList *list, GSList *link)
 277 {
 278         list = g_slist_remove_link (list, link);
 279         g_slist_free_1 (link);
 280
 281         return list;
 282 }
 283
 284 GSList*
 285 g_slist_reverse (GSList *list)
 286 {
 287         GSList *prev = NULL;
 288         while (list){
 289                 GSList *next = list->next;
 290                 list->next = prev;
 291                 prev = list;
 292                 list = next;
 293         }
 294
 295         return prev;
 296 }
 297
 298 GSList*
 299 g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
 300 {
 301         GSList *prev = NULL;
 302
 303         if (!func)
 304                 return list;
 305
 306         if (!list || func (list->data, data) > 0)
 307                 return g_slist_prepend (list, data);
 308
 309         /* Invariant: func (prev->data, data) <= 0) */
 310         for (prev = list; prev->next; prev = prev->next)
 311                 if (func (prev->next->data, data) > 0)
 312                         break;
 313
 314         /* ... && (prev->next == 0 || func (prev->next->data, data) > 0)) */
 315         insert_after (prev, data);
 316         return list;
 317 }
 318
 319 gint
 320 g_slist_index (GSList *list, gconstpointer data)
 321 {
 322         gint index = 0;
 323
 324         while (list) {
 325                 if (list->data == data)
 326                         return index;
 327
 328                 index++;
 329                 list = list->next;
 330         }
 331
 332         return -1;
 333 }
 334
 335 GSList*
 336 g_slist_nth (GSList *list, guint n)
 337 {
 338         for (; list; list = list->next) {
 339                 if (n == 0)
 340                         break;
 341                 n--;
 342         }
 343         return list;
 344 }
 345
 346 gpointer
 347 g_slist_nth_data (GSList *list, guint n)
 348 {
 349         GSList *node = g_slist_nth (list, n);
 350         return node ? node->data : NULL;
 351 }
 352
 353 typedef GSList list_node;
 354 #include "sort.frag.h"
 355
 356 GSList*
 357 g_slist_sort (GSList *list, GCompareFunc func)
 358 {
 359         if (!list || !list->next)
 360                 return list;
 361         return do_sort (list, func);
 362 }