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         GList *node;
 209
 210         if (!func)
 211                 return list;
 212
 213         /* Invariant: !prev || func (prev->data, data) <= 0) */
 214         for (current = list; current; current = current->next) {
 215                 if (func (current->data, data) > 0)
 216                         break;
 217                 prev = current;
 218         }
 219
 220         node = new_node (prev, data, current);
 221         return list == current ? node : list;
 222 }
 223
 224 GList*
 225 g_list_insert_before (GList *list, GList *sibling, gpointer data)
 226 {
 227         if (sibling) {
 228                 GList *node = new_node (sibling->prev, data, sibling);
 229                 return list == sibling ? node : list;
 230         }
 231         return g_list_append (list, data);
 232 }
 233
 234 void
 235 g_list_foreach (GList *list, GFunc func, gpointer user_data)
 236 {
 237         while (list){
 238                 (*func) (list->data, user_data);
 239                 list = list->next;
 240         }
 241 }
 242
 243 gint
 244 g_list_index (GList *list, gconstpointer data)
 245 {
 246         gint index = 0;
 247
 248         while (list){
 249                 if (list->data == data)
 250                         return index;
 251
 252                 index ++;
 253                 list = list->next;
 254         }
 255
 256         return -1;
 257 }
 258
 259 GList*
 260 g_list_nth (GList *list, guint n)
 261 {
 262         for (; list; list = list->next) {
 263                 if (n == 0)
 264                         break;
 265                 n--;
 266         }
 267         return list;
 268 }
 269
 270 gpointer
 271 g_list_nth_data (GList *list, guint n)
 272 {
 273         GList *node = g_list_nth (list, n);
 274         return node ? node->data : NULL;
 275 }
 276
 277 GList*
 278 g_list_copy (GList *list)
 279 {
 280         GList *copy = NULL;
 281
 282         if (list) {
 283                 GList *tmp = new_node (NULL, list->data, NULL);
 284                 copy = tmp;
 285
 286                 for (list = list->next; list; list = list->next)
 287                         tmp = new_node (tmp, list->data, NULL);
 288         }
 289
 290         return copy;
 291 }
 292
 293 typedef GList list_node;
 294 #include "sort.frag.h"
 295
 296 GList*
 297 g_list_sort (GList *list, GCompareFunc func)
 298 {
 299         GList *current;
 300         if (!list || !list->next)
 301                 return list;
 302         list = do_sort (list, func);
 303
 304         /* Fixup: do_sort doesn't update 'prev' pointers */
 305         list->prev = NULL;
 306         for (current = list; current->next; current = current->next)
 307                 current->next->prev = current;
 308
 309         return list;
 310 }