eglib/src/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 guint
 185 g_slist_length (GSList *list)
 186 {
 187         guint length = 0;
 188
 189         while (list) {
 190                 length ++;
 191                 list = list->next;
 192         }
 193
 194         return length;
 195 }
 196
 197 GSList*
 198 g_slist_remove (GSList *list, gconstpointer data)
 199 {
 200         GSList *prev = find_prev (list, data);
 201         GSList *current = prev ? prev->next : list;
 202
 203         if (current) {
 204                 if (prev)
 205                         prev->next = current->next;
 206                 else
 207                         list = current->next;
 208                 g_slist_free_1 (current);
 209         }
 210
 211         return list;
 212 }
 213
 214 GSList*
 215 g_slist_remove_all (GSList *list, gconstpointer data)
 216 {
 217         GSList *next = list;
 218         GSList *prev = NULL;
 219         GSList *current;
 220
 221         while (next) {
 222                 GSList *tmp_prev = find_prev (next, data);
 223                 if (tmp_prev)
 224                         prev = tmp_prev;
 225                 current = prev ? prev->next : list;
 226
 227                 if (!current)
 228                         break;
 229
 230                 next = current->next;
 231
 232                 if (prev)
 233                         prev->next = next;
 234                 else
 235                         list = next;
 236                 g_slist_free_1 (current);
 237         }
 238
 239         return list;
 240 }
 241
 242 GSList*
 243 g_slist_remove_link (GSList *list, GSList *link)
 244 {
 245         GSList *prev = find_prev_link (list, link);
 246         GSList *current = prev ? prev->next : list;
 247
 248         if (current) {
 249                 if (prev)
 250                         prev->next = current->next;
 251                 else
 252                         list = current->next;
 253                 current->next = NULL;
 254         }
 255
 256         return list;
 257 }
 258
 259 GSList*
 260 g_slist_delete_link (GSList *list, GSList *link)
 261 {
 262         list = g_slist_remove_link (list, link);
 263         g_slist_free_1 (link);
 264
 265         return list;
 266 }
 267
 268 GSList*
 269 g_slist_reverse (GSList *list)
 270 {
 271         GSList *prev = NULL;
 272         while (list){
 273                 GSList *next = list->next;
 274                 list->next = prev;
 275                 prev = list;
 276                 list = next;
 277         }
 278
 279         return prev;
 280 }
 281
 282 GSList*
 283 g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
 284 {
 285         GSList *prev = NULL;
 286
 287         if (!func)
 288                 return list;
 289
 290         if (!list || func (list->data, data) > 0)
 291                 return g_slist_prepend (list, data);
 292
 293         /* Invariant: func (prev->data, data) <= 0) */
 294         for (prev = list; prev->next; prev = prev->next)
 295                 if (func (prev->next->data, data) > 0)
 296                         break;
 297
 298         /* ... && (prev->next == 0 || func (prev->next->data, data) > 0)) */
 299         insert_after (prev, data);
 300         return list;
 301 }
 302
 303 typedef GSList list_node;
 304 #include "sort.frag.h"
 305
 306 GSList*
 307 g_slist_sort (GSList *list, GCompareFunc func)
 308 {
 309         if (!list || !list->next)
 310                 return list;
 311         return do_sort (list, func);
 312 }