eglib/src/glist.c

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