mono/eglib/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_all (GList *list, gconstpointer data)
 130 {
 131         GList *current = g_list_find (list, data);
 132
 133         if (!current)
 134                 return list;
 135
 136         while (current) {
 137                 if (current == list)
 138                         list = list->next;
 139                 g_list_free_1 (disconnect_node (current));
 140
 141                 current = g_list_find (list, data);
 142         }
 143
 144         return list;
 145 }
 146
 147 GList*
 148 g_list_remove_link (GList *list, GList *link)
 149 {
 150         if (list == link)
 151                 list = list->next;
 152
 153         disconnect_node (link);
 154         link->next = NULL;
 155         link->prev = NULL;
 156
 157         return list;
 158 }
 159
 160 GList*
 161 g_list_delete_link (GList *list, GList *link)
 162 {
 163         list = g_list_remove_link (list, link);
 164         g_list_free_1 (link);
 165
 166         return list;
 167 }
 168
 169 GList*
 170 g_list_find (GList *list, gconstpointer data)
 171 {
 172         while (list){
 173                 if (list->data == data)
 174                         return list;
 175
 176                 list = list->next;
 177         }
 178
 179         return NULL;
 180 }
 181
 182 GList*
 183 g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func)
 184 {
 185         if (!func)
 186                 return NULL;
 187
 188         while (list) {
 189                 if (func (list->data, data) == 0)
 190                         return list;
 191
 192                 list = list->next;
 193         }
 194
 195         return NULL;
 196 }
 197
 198 GList*
 199 g_list_reverse (GList *list)
 200 {
 201         GList *reverse = NULL;
 202
 203         while (list) {
 204                 reverse = list;
 205                 list = reverse->next;
 206
 207                 reverse->next = reverse->prev;
 208                 reverse->prev = list;
 209         }
 210
 211         return reverse;
 212 }
 213
 214 GList*
 215 g_list_first (GList *list)
 216 {
 217         if (!list)
 218                 return NULL;
 219
 220         while (list->prev)
 221                 list = list->prev;
 222
 223         return list;
 224 }
 225
 226 GList*
 227 g_list_last (GList *list)
 228 {
 229         if (!list)
 230                 return NULL;
 231
 232         while (list->next)
 233                 list = list->next;
 234
 235         return list;
 236 }
 237
 238 GList*
 239 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
 240 {
 241         GList *prev = NULL;
 242         GList *current;
 243         GList *node;
 244
 245         if (!func)
 246                 return list;
 247
 248         /* Invariant: !prev || func (prev->data, data) <= 0) */
 249         for (current = list; current; current = current->next) {
 250                 if (func (current->data, data) > 0)
 251                         break;
 252                 prev = current;
 253         }
 254
 255         node = new_node (prev, data, current);
 256         return list == current ? node : list;
 257 }
 258
 259 GList*
 260 g_list_insert_before (GList *list, GList *sibling, gpointer data)
 261 {
 262         if (sibling) {
 263                 GList *node = new_node (sibling->prev, data, sibling);
 264                 return list == sibling ? node : list;
 265         }
 266         return g_list_append (list, data);
 267 }
 268
 269 void
 270 g_list_foreach (GList *list, GFunc func, gpointer user_data)
 271 {
 272         while (list){
 273                 (*func) (list->data, user_data);
 274                 list = list->next;
 275         }
 276 }
 277
 278 gint
 279 g_list_index (GList *list, gconstpointer data)
 280 {
 281         gint index = 0;
 282
 283         while (list){
 284                 if (list->data == data)
 285                         return index;
 286
 287                 index ++;
 288                 list = list->next;
 289         }
 290
 291         return -1;
 292 }
 293
 294 GList*
 295 g_list_nth (GList *list, guint n)
 296 {
 297         for (; list; list = list->next) {
 298                 if (n == 0)
 299                         break;
 300                 n--;
 301         }
 302         return list;
 303 }
 304
 305 gpointer
 306 g_list_nth_data (GList *list, guint n)
 307 {
 308         GList *node = g_list_nth (list, n);
 309         return node ? node->data : NULL;
 310 }
 311
 312 GList*
 313 g_list_copy (GList *list)
 314 {
 315         GList *copy = NULL;
 316
 317         if (list) {
 318                 GList *tmp = new_node (NULL, list->data, NULL);
 319                 copy = tmp;
 320
 321                 for (list = list->next; list; list = list->next)
 322                         tmp = new_node (tmp, list->data, NULL);
 323         }
 324
 325         return copy;
 326 }
 327
 328 typedef GList list_node;
 329 #include "sort.frag.h"
 330
 331 GList*
 332 g_list_sort (GList *list, GCompareFunc func)
 333 {
 334         GList *current;
 335         if (!list || !list->next)
 336                 return list;
 337         list = do_sort (list, func);
 338
 339         /* Fixup: do_sort doesn't update 'prev' pointers */
 340         list->prev = NULL;
 341         for (current = list; current->next; current = current->next)
 342                 current->next->prev = current;
 343
 344         return list;
 345 }