eglib/src/gslist.c

   1 /*
   2  * gslist.c: Singly-linked list implementation
   3  *
   4  * Author:
   5  *   Duncan Mak (duncan@novell.com)
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files (the
   9  * "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  22  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  * (C) 2006 Novell, Inc.
  27  */
  28
  29 #include <stdio.h>
  30 #include <glib.h>
  31
  32 GSList*
  33 g_slist_alloc (void)
  34 {
  35         return g_new0 (GSList, 1);
  36 }
  37
  38 void
  39 g_slist_free_1 (GSList *list)
  40 {
  41         g_free (list);
  42 }
  43
  44 GSList*
  45 g_slist_append (GSList *list, gpointer data)
  46 {
  47         return g_slist_concat (list, g_slist_prepend (NULL, data));
  48 }
  49
  50 /* This is also a list node constructor. */
  51 GSList*
  52 g_slist_prepend (GSList *list, gpointer data)
  53 {
  54         GSList *head = g_slist_alloc ();
  55         head->data = data;
  56         head->next = list;
  57
  58         return head;
  59 }
  60
  61 void
  62 g_slist_free (GSList *list)
  63 {
  64         GSList *next;
  65         while (list) {
  66                 next = list->next;
  67                 g_slist_free_1 (list);
  68                 list = next;
  69         }
  70 }
  71
  72 GSList*
  73 g_slist_copy (GSList *list)
  74 {
  75         GSList *copy, *tmp;
  76
  77         if (!list)
  78                 return NULL;
  79
  80         copy = g_slist_prepend (NULL, list->data);
  81         tmp = copy;
  82
  83         while (list->next) {
  84                 tmp->next = g_slist_prepend (NULL, list->next->data);
  85
  86                 tmp = tmp->next;
  87                 list = list->next;
  88         }
  89
  90         return copy;
  91 }
  92
  93 GSList*
  94 g_slist_concat (GSList *list1, GSList *list2)
  95 {
  96         if (list1)
  97                 g_slist_last (list1)->next = list2;
  98         else
  99                 list1 = list2;
 100
 101         return list1;
 102 }
 103
 104 void
 105 g_slist_foreach (GSList *list, GFunc func, gpointer user_data)
 106 {
 107         while (list) {
 108                 (*func) (list->data, user_data);
 109                 list = list->next;
 110         }
 111 }
 112
 113 GSList*
 114 g_slist_last (GSList *list)
 115 {
 116         if (!list)
 117                 return NULL;
 118
 119         while (list->next)
 120                 list = list->next;
 121
 122         return list;
 123 }
 124
 125 GSList*
 126 g_slist_find (GSList *list, gconstpointer data)
 127 {
 128         while (list){
 129                 if (list->data == data)
 130                         return list;
 131
 132                 list = list->next;
 133         }
 134
 135         return NULL;
 136 }
 137
 138 guint
 139 g_slist_length (GSList *list)
 140 {
 141         guint length = 0;
 142
 143         while (list) {
 144                 length ++;
 145                 list = list->next;
 146         }
 147
 148         return length;
 149 }
 150
 151 GSList*
 152 g_slist_remove (GSList *list, gconstpointer data)
 153 {
 154         GSList *prev = NULL;
 155         GSList *current = NULL;
 156
 157         if (!list)
 158                 return NULL;
 159
 160         if (list->data == data)
 161                 return list->next;
 162
 163         prev = list;
 164         current = list->next;
 165
 166         while (current) {
 167                 if (current->data == data){
 168                         prev->next = current->next;
 169                         g_slist_free_1 (current);
 170
 171                         break;
 172                 }
 173                 prev = current;
 174                 current = current->next;
 175         }
 176
 177         return list;
 178 }
 179
 180
 181 GSList*
 182 g_slist_remove_link (GSList *list, GSList *link)
 183 {
 184         GSList *prev = NULL;
 185         GSList *current = NULL;
 186
 187         if (!list)
 188                 return NULL;
 189
 190         if (list == link) {
 191                 GSList *next = list->next;
 192                 list->next = NULL;
 193                 return next;
 194         }
 195
 196         prev = list;
 197         current = list->next;
 198
 199         while (current){
 200                 if (current == link){
 201                         prev->next = current->next;
 202                         current->next = NULL;
 203                         break;
 204                 }
 205
 206                 prev = current;
 207                 current = current->next;
 208         }
 209
 210         return list;
 211 }
 212
 213 GSList*
 214 g_slist_delete_link (GSList *list, GSList *link)
 215 {
 216         list = g_slist_remove_link (list, link);
 217         g_slist_free_1 (link);
 218
 219         return list;
 220 }
 221
 222 GSList*
 223 g_slist_reverse (GSList *list)
 224 {
 225         GSList *prev = NULL;
 226         while (list){
 227                 GSList *next = list->next;
 228                 list->next = prev;
 229                 prev = list;
 230                 list = next;
 231         }
 232
 233         return prev;
 234 }
 235
 236 GSList*
 237 g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
 238 {
 239         GSList *current = NULL;
 240         GSList *prev = NULL;
 241
 242         if (!func)
 243                 return list;
 244
 245         if (!list)
 246                 return g_slist_prepend (NULL, data);
 247
 248         if (func (list->data, data) > 0)
 249                 return g_slist_prepend (list, data);
 250
 251         prev = list;
 252         current = list->next;
 253
 254         while (current){
 255                 if (func (current->data, data) > 0){
 256                         prev->next = g_slist_prepend (current, data);
 257                         break;
 258                 }
 259
 260                 if (current->next == NULL){
 261                         g_slist_append (list, data);
 262                         break;
 263                 }
 264
 265                 prev = current;
 266                 current = current->next;
 267         }
 268
 269         return list;
 270 }