eglib/src/glist.c

   1 /*
   2  * glist.c: Doubly-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 #include <stdio.h>
  30 #include <glib.h>
  31
  32 GList*
  33 g_list_alloc ()
  34 {
  35         return g_new0 (GList, 1);
  36 }
  37
  38 static inline GList*
  39 new_node (GList *prev, gpointer data, GList *next)
  40 {
  41         GList *node = g_list_alloc ();
  42         node->data = data;
  43         node->prev = prev;
  44         node->next = next;
  45         if (prev)
  46                 prev->next = node;
  47         if (next)
  48                 next->prev = node;
  49         return node;
  50 }
  51
  52 static inline GList*
  53 disconnect_node (GList *node)
  54 {
  55         if (node->next)
  56                 node->next->prev = node->prev;
  57         if (node->prev)
  58                 node->prev->next = node->next;
  59         return node;
  60 }
  61
  62 GList *
  63 g_list_prepend (GList *list, gpointer data)
  64 {
  65         return new_node (list ? list->prev : NULL, data, list);
  66 }
  67
  68 void
  69 g_list_free_1 (GList *list)
  70 {
  71         g_free (list);
  72 }
  73
  74 void
  75 g_list_free (GList *list)
  76 {
  77         while (list){
  78                 GList *next = list->next;
  79                 g_list_free_1 (list);
  80                 list = next;
  81         }
  82 }
  83
  84 GList*
  85 g_list_append (GList *list, gpointer data)
  86 {
  87         GList *node = new_node (g_list_last (list), data, NULL);
  88         return list ? list : node;
  89 }
  90
  91 GList *
  92 g_list_concat (GList *list1, GList *list2)
  93 {
  94         if (list1 && list2) {
  95                 list2->prev = g_list_last (list1);
  96                 list2->prev->next = list2;
  97         }
  98         return list1 ? list1 : list2;
  99 }
 100
 101 guint
 102 g_list_length (GList *list)
 103 {
 104         guint length = 0;
 105
 106         while (list) {
 107                 length ++;
 108                 list = list->next;
 109         }
 110
 111         return length;
 112 }
 113
 114 GList*
 115 g_list_remove (GList *list, gconstpointer data)
 116 {
 117         GList *current = g_list_find (list, data);
 118         if (!current)
 119                 return list;
 120
 121         if (current == list)
 122                 list = list->next;
 123         g_list_free_1 (disconnect_node (current));
 124
 125         return list;
 126 }
 127
 128 GList*
 129 g_list_remove_link (GList *list, GList *link)
 130 {
 131         if (list == link)
 132                 list = list->next;
 133
 134         disconnect_node (link);
 135         link->next = NULL;
 136         link->prev = NULL;
 137
 138         return list;
 139 }
 140
 141 GList*
 142 g_list_delete_link (GList *list, GList *link)
 143 {
 144         list = g_list_remove_link (list, link);
 145         g_list_free_1 (link);
 146
 147         return list;
 148 }
 149
 150 GList*
 151 g_list_find (GList *list, gconstpointer data)
 152 {
 153         while (list){
 154                 if (list->data == data)
 155                         return list;
 156
 157                 list = list->next;
 158         }
 159
 160         return NULL;
 161 }
 162
 163 GList*
 164 g_list_reverse (GList *list)
 165 {
 166         GList *reverse = NULL;
 167
 168         while (list) {
 169                 reverse = list;
 170                 list = reverse->next;
 171
 172                 reverse->next = reverse->prev;
 173                 reverse->prev = list;
 174         }
 175
 176         return reverse;
 177 }
 178
 179 GList*
 180 g_list_first (GList *list)
 181 {
 182         if (!list)
 183                 return NULL;
 184
 185         while (list->prev)
 186                 list = list->prev;
 187
 188         return list;
 189 }
 190
 191 GList*
 192 g_list_last (GList *list)
 193 {
 194         if (!list)
 195                 return NULL;
 196
 197         while (list->next)
 198                 list = list->next;
 199
 200         return list;
 201 }
 202
 203 GList*
 204 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
 205 {
 206         GList *prev = NULL;
 207         GList *current;
 208
 209         if (!func)
 210                 return list;
 211
 212         /* Invariant: !prev || func (prev->data, data) <= 0) */
 213         for (current = list; current; current = current->next) {
 214                 if (func (current->data, data) > 0)
 215                         break;
 216                 prev = current;
 217         }
 218
 219         GList *node = new_node (prev, data, current);
 220         return list == current ? node : list;
 221 }
 222
 223 GList*
 224 g_list_insert_before (GList *list, GList *sibling, gpointer data)
 225 {
 226         if (sibling) {
 227                 GList *node = new_node (sibling->prev, data, sibling);
 228                 return list == sibling ? node : list;
 229         }
 230         return g_list_append (list, data);
 231 }
 232
 233 void
 234 g_list_foreach (GList *list, GFunc func, gpointer user_data)
 235 {
 236         while (list){
 237                 (*func) (list->data, user_data);
 238                 list = list->next;
 239         }
 240 }
 241
 242 gint
 243 g_list_index (GList *list, gconstpointer data)
 244 {
 245         gint index = 0;
 246
 247         while (list){
 248                 if (list->data == data)
 249                         return index;
 250
 251                 index ++;
 252                 list = list->next;
 253         }
 254
 255         return -1;
 256 }
 257
 258 GList*
 259 g_list_nth (GList *list, guint n)
 260 {
 261         for (; list; list = list->next) {
 262                 if (n == 0)
 263                         break;
 264                 n--;
 265         }
 266         return list;
 267 }
 268
 269 gpointer
 270 g_list_nth_data (GList *list, guint n)
 271 {
 272         GList *node = g_list_nth (list, n);
 273         return node ? node->data : NULL;
 274 }
 275
 276 GList*
 277 g_list_copy (GList *list)
 278 {
 279         GList *copy = NULL;
 280
 281         if (list) {
 282                 GList *tmp = new_node (NULL, list->data, NULL);
 283                 copy = tmp;
 284
 285                 for (list = list->next; list; list = list->next)
 286                         tmp = new_node (tmp, list->data, NULL);
 287         }
 288
 289         return copy;
 290 }
 291
 292 typedef GList list_node;
 293 #include "sort.frag.h"
 294
 295 GList*
 296 g_list_sort (GList *list, GCompareFunc func)
 297 {
 298         GList *current;
 299         if (!list || !list->next)
 300                 return list;
 301         list = do_sort (list, func);
 302
 303         /* Fixup: do_sort doesn't update 'prev' pointers */
 304         list->prev = NULL;
 305         for (current = list; current->next; current = current->next)
 306                 current->next->prev = current;
 307
 308         return list;
 309 }