jack/jslist.h

   1 /*
   2     Based on gslist.c from glib-1.2.9 (LGPL).
   3
   4     Adaption to JACK, Copyright (C) 2002 Kai Vehmanen.
   5       - replaced use of gtypes with normal ANSI C types
   6       - glib's memery allocation routines replaced with
   7         malloc/free calls
   8
   9     This program is free software; you can redistribute it and/or modify
  10     it under the terms of the GNU Lesser General Public License as published by
  11     the Free Software Foundation; either version 2.1 of the License, or
  12     (at your option) any later version.
  13
  14     This program is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU Lesser General Public License for more details.
  18
  19     You should have received a copy of the GNU Lesser General Public License
  20     along with this program; if not, write to the Free Software
  21     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  22
  23 */
  24
  25 #ifndef __jack_jslist_h__
  26 #define __jack_jslist_h__
  27
  28 #include <stdlib.h>
  29
  30 typedef struct _JSList JSList;
  31
  32 typedef int             (*JCompareFunc)         (void*  a,
  33                                                  void*  b);
  34 struct _JSList
  35 {
  36   void *data;
  37   JSList *next;
  38 };
  39
  40 static __inline__
  41 JSList*
  42 jack_slist_alloc (void)
  43 {
  44   JSList *new_list;
  45
  46   new_list = malloc(sizeof(JSList));
  47   new_list->data = NULL;
  48   new_list->next = NULL;
  49
  50   return new_list;
  51 }
  52
  53 static __inline__
  54 JSList*
  55 jack_slist_prepend (JSList   *list,
  56                     void     *data)
  57 {
  58   JSList *new_list;
  59
  60   new_list = malloc(sizeof(JSList));
  61   new_list->data = data;
  62   new_list->next = list;
  63
  64   return new_list;
  65 }
  66
  67 #define jack_slist_next(slist)  ((slist) ? (((JSList *)(slist))->next) : NULL)
  68 static __inline__
  69 JSList*
  70 jack_slist_last (JSList *list)
  71 {
  72   if (list)
  73     {
  74       while (list->next)
  75         list = list->next;
  76     }
  77
  78   return list;
  79 }
  80
  81 static __inline__
  82 JSList*
  83 jack_slist_remove_link (JSList *list,
  84                      JSList *link)
  85 {
  86   JSList *tmp;
  87   JSList *prev;
  88
  89   prev = NULL;
  90   tmp = list;
  91
  92   while (tmp)
  93     {
  94       if (tmp == link)
  95         {
  96           if (prev)
  97             prev->next = tmp->next;
  98           if (list == tmp)
  99             list = list->next;
 100
 101           tmp->next = NULL;
 102           break;
 103         }
 104
 105       prev = tmp;
 106       tmp = tmp->next;
 107     }
 108
 109   return list;
 110 }
 111
 112 static __inline__
 113 void
 114 jack_slist_free (JSList *list)
 115 {
 116   while (list)
 117     {
 118             JSList *next = list->next;
 119             free(list);
 120             list = next;
 121     }
 122 }
 123
 124 static __inline__
 125 void
 126 jack_slist_free_1 (JSList *list)
 127 {
 128   if (list)
 129     {
 130       free(list);
 131     }
 132 }
 133
 134 static __inline__
 135 JSList*
 136 jack_slist_remove (JSList   *list,
 137                    void     *data)
 138 {
 139   JSList *tmp;
 140   JSList *prev;
 141
 142   prev = NULL;
 143   tmp = list;
 144
 145   while (tmp)
 146     {
 147       if (tmp->data == data)
 148         {
 149           if (prev)
 150             prev->next = tmp->next;
 151           if (list == tmp)
 152             list = list->next;
 153
 154           tmp->next = NULL;
 155           jack_slist_free (tmp);
 156
 157           break;
 158         }
 159
 160       prev = tmp;
 161       tmp = tmp->next;
 162     }
 163
 164   return list;
 165 }
 166
 167 static __inline__
 168 unsigned int
 169 jack_slist_length (JSList *list)
 170 {
 171   unsigned int length;
 172
 173   length = 0;
 174   while (list)
 175     {
 176       length++;
 177       list = list->next;
 178     }
 179
 180   return length;
 181 }
 182
 183 static __inline__
 184 JSList*
 185 jack_slist_find (JSList   *list,
 186                  void     *data)
 187 {
 188   while (list)
 189     {
 190       if (list->data == data)
 191         break;
 192       list = list->next;
 193     }
 194
 195   return list;
 196 }
 197
 198 static __inline__
 199 JSList*
 200 jack_slist_copy (JSList *list)
 201 {
 202   JSList *new_list = NULL;
 203
 204   if (list)
 205     {
 206       JSList *last;
 207
 208       new_list = jack_slist_alloc ();
 209       new_list->data = list->data;
 210       last = new_list;
 211       list = list->next;
 212       while (list)
 213         {
 214           last->next = jack_slist_alloc ();
 215           last = last->next;
 216           last->data = list->data;
 217           list = list->next;
 218         }
 219     }
 220
 221   return new_list;
 222 }
 223
 224 static __inline__
 225 JSList*
 226 jack_slist_append (JSList   *list,
 227                    void     *data)
 228 {
 229   JSList *new_list;
 230   JSList *last;
 231
 232   new_list = jack_slist_alloc ();
 233   new_list->data = data;
 234
 235   if (list)
 236     {
 237       last = jack_slist_last (list);
 238       last->next = new_list;
 239
 240       return list;
 241     }
 242   else
 243       return new_list;
 244 }
 245
 246 static __inline__
 247 JSList*
 248 jack_slist_sort_merge  (JSList      *l1,
 249                         JSList      *l2,
 250                         JCompareFunc compare_func)
 251 {
 252   JSList list, *l;
 253
 254   l=&list;
 255
 256   while (l1 && l2)
 257     {
 258       if (compare_func(l1->data,l2->data) < 0)
 259         {
 260           l=l->next=l1;
 261           l1=l1->next;
 262         }
 263       else
 264         {
 265           l=l->next=l2;
 266           l2=l2->next;
 267         }
 268     }
 269   l->next= l1 ? l1 : l2;
 270
 271   return list.next;
 272 }
 273
 274 static __inline__
 275 JSList*
 276 jack_slist_sort (JSList       *list,
 277                  JCompareFunc compare_func)
 278 {
 279   JSList *l1, *l2;
 280
 281   if (!list)
 282     return NULL;
 283   if (!list->next)
 284     return list;
 285
 286   l1 = list;
 287   l2 = list->next;
 288
 289   while ((l2 = l2->next) != NULL)
 290     {
 291       if ((l2 = l2->next) == NULL)
 292         break;
 293       l1=l1->next;
 294     }
 295   l2 = l1->next;
 296   l1->next = NULL;
 297
 298   return jack_slist_sort_merge (jack_slist_sort (list, compare_func),
 299                                 jack_slist_sort (l2,   compare_func),
 300                                 compare_func);
 301 }
 302
 303 #endif /* __jack_jslist_h__ */