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