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_find_custom (GList *list, gconstpointer data, GCompareFunc func)
 165 {
 166         if (!func)
 167                 return NULL;
 168
 169         while (list) {
 170                 if (func (list->data, data) == 0)
 171                         return list;
 172
 173                 list = list->next;
 174         }
 175
 176         return NULL;
 177 }
 178
 179 GList*
 180 g_list_reverse (GList *list)
 181 {
 182         GList *reverse = NULL;
 183
 184         while (list) {
 185                 reverse = list;
 186                 list = reverse->next;
 187
 188                 reverse->next = reverse->prev;
 189                 reverse->prev = list;
 190         }
 191
 192         return reverse;
 193 }
 194
 195 GList*
 196 g_list_first (GList *list)
 197 {
 198         if (!list)
 199                 return NULL;
 200
 201         while (list->prev)
 202                 list = list->prev;
 203
 204         return list;
 205 }
 206
 207 GList*
 208 g_list_last (GList *list)
 209 {
 210         if (!list)
 211                 return NULL;
 212
 213         while (list->next)
 214                 list = list->next;
 215
 216         return list;
 217 }
 218
 219 GList*
 220 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
 221 {
 222         GList *prev = NULL;
 223         GList *current;
 224         GList *node;
 225
 226         if (!func)
 227                 return list;
 228
 229         /* Invariant: !prev || func (prev->data, data) <= 0) */
 230         for (current = list; current; current = current->next) {
 231                 if (func (current->data, data) > 0)
 232                         break;
 233                 prev = current;
 234         }
 235
 236         node = new_node (prev, data, current);
 237         return list == current ? node : list;
 238 }
 239
 240 GList*
 241 g_list_insert_before (GList *list, GList *sibling, gpointer data)
 242 {
 243         if (sibling) {
 244                 GList *node = new_node (sibling->prev, data, sibling);
 245                 return list == sibling ? node : list;
 246         }
 247         return g_list_append (list, data);
 248 }
 249
 250 void
 251 g_list_foreach (GList *list, GFunc func, gpointer user_data)
 252 {
 253         while (list){
 254                 (*func) (list->data, user_data);
 255                 list = list->next;
 256         }
 257 }
 258
 259 gint
 260 g_list_index (GList *list, gconstpointer data)
 261 {
 262         gint index = 0;
 263
 264         while (list){
 265                 if (list->data == data)
 266                         return index;
 267
 268                 index ++;
 269                 list = list->next;
 270         }
 271
 272         return -1;
 273 }
 274
 275 GList*
 276 g_list_nth (GList *list, guint n)
 277 {
 278         for (; list; list = list->next) {
 279                 if (n == 0)
 280                         break;
 281                 n--;
 282         }
 283         return list;
 284 }
 285
 286 gpointer
 287 g_list_nth_data (GList *list, guint n)
 288 {
 289         GList *node = g_list_nth (list, n);
 290         return node ? node->data : NULL;
 291 }
 292
 293 GList*
 294 g_list_copy (GList *list)
 295 {
 296         GList *copy = NULL;
 297
 298         if (list) {
 299                 GList *tmp = new_node (NULL, list->data, NULL);
 300                 copy = tmp;
 301
 302                 for (list = list->next; list; list = list->next)
 303                         tmp = new_node (tmp, list->data, NULL);
 304         }
 305
 306         return copy;
 307 }
 308
 309 typedef GList list_node;
 310 #include "sort.frag.h"
 311
 312 GList*
 313 g_list_sort (GList *list, GCompareFunc func)
 314 {
 315         GList *current;
 316         if (!list || !list->next)
 317                 return list;
 318         list = do_sort (list, func);
 319
 320         /* Fixup: do_sort doesn't update 'prev' pointers */
 321         list->prev = NULL;
 322         for (current = list; current->next; current = current->next)
 323                 current->next->prev = current;
 324
 325         return list;
 326 }