common/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 memory 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 #include <jack/systemdeps.h>
  30
  31 #ifdef sun
  32 #define __inline__
  33 #endif
  34
  35 typedef struct _JSList JSList;
  36
  37 typedef int     (*JCompareFunc) (void* a, void* b);
  38 struct _JSList
  39 {
  40     void *data;
  41     JSList *next;
  42 };
  43
  44 static __inline__
  45 JSList*
  46 jack_slist_alloc (void)
  47 {
  48     JSList *new_list;
  49
  50     new_list = (JSList*)malloc(sizeof(JSList));
  51     if (new_list) {
  52         new_list->data = NULL;
  53         new_list->next = NULL;
  54     }
  55
  56     return new_list;
  57 }
  58
  59 static __inline__
  60 JSList*
  61 jack_slist_prepend (JSList* list, void* data)
  62 {
  63     JSList *new_list;
  64
  65     new_list = (JSList*)malloc(sizeof(JSList));
  66     if (new_list) {
  67         new_list->data = data;
  68         new_list->next = list;
  69     }
  70
  71     return new_list;
  72 }
  73
  74 #define jack_slist_next(slist)  ((slist) ? (((JSList *)(slist))->next) : NULL)
  75 static __inline__
  76 JSList*
  77 jack_slist_last (JSList *list)
  78 {
  79     if (list) {
  80         while (list->next)
  81             list = list->next;
  82     }
  83
  84     return list;
  85 }
  86
  87 static __inline__
  88 JSList*
  89 jack_slist_remove_link (JSList *list,
  90                         JSList *link)
  91 {
  92     JSList *tmp;
  93     JSList *prev;
  94
  95     prev = NULL;
  96     tmp = list;
  97
  98     while (tmp) {
  99         if (tmp == link) {
 100             if (prev)
 101                 prev->next = tmp->next;
 102             if (list == tmp)
 103                 list = list->next;
 104
 105             tmp->next = NULL;
 106             break;
 107         }
 108
 109         prev = tmp;
 110         tmp = tmp->next;
 111     }
 112
 113     return list;
 114 }
 115
 116 static __inline__
 117 void
 118 jack_slist_free (JSList *list)
 119 {
 120     while (list) {
 121         JSList *next = list->next;
 122         free(list);
 123         list = next;
 124     }
 125 }
 126
 127 static __inline__
 128 void
 129 jack_slist_free_1 (JSList *list)
 130 {
 131     if (list) {
 132         free(list);
 133     }
 134 }
 135
 136 static __inline__
 137 JSList*
 138 jack_slist_remove (JSList *list,
 139                    void *data)
 140 {
 141     JSList *tmp;
 142     JSList *prev;
 143
 144     prev = NULL;
 145     tmp = list;
 146
 147     while (tmp) {
 148         if (tmp->data == data) {
 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         length++;
 176         list = list->next;
 177     }
 178
 179     return length;
 180 }
 181
 182 static __inline__
 183 JSList*
 184 jack_slist_find (JSList *list,
 185                  void *data)
 186 {
 187     while (list) {
 188         if (list->data == data)
 189             break;
 190         list = list->next;
 191     }
 192
 193     return list;
 194 }
 195
 196 static __inline__
 197 JSList*
 198 jack_slist_copy (JSList *list)
 199 {
 200     JSList *new_list = NULL;
 201
 202     if (list) {
 203         JSList *last;
 204
 205         new_list = jack_slist_alloc ();
 206         new_list->data = list->data;
 207         last = new_list;
 208         list = list->next;
 209         while (list) {
 210             last->next = jack_slist_alloc ();
 211             last = last->next;
 212             last->data = list->data;
 213             list = list->next;
 214         }
 215     }
 216
 217     return new_list;
 218 }
 219
 220 static __inline__
 221 JSList*
 222 jack_slist_append (JSList *list,
 223                    void *data)
 224 {
 225     JSList *new_list;
 226     JSList *last;
 227
 228     new_list = jack_slist_alloc ();
 229     new_list->data = data;
 230
 231     if (list) {
 232         last = jack_slist_last (list);
 233         last->next = new_list;
 234
 235         return list;
 236     } else
 237         return new_list;
 238 }
 239
 240 static __inline__
 241 JSList*
 242 jack_slist_sort_merge (JSList *l1,
 243                        JSList *l2,
 244                        JCompareFunc compare_func)
 245 {
 246     JSList list, *l;
 247
 248     l = &list;
 249
 250     while (l1 && l2) {
 251         if (compare_func(l1->data, l2->data) < 0) {
 252             l = l->next = l1;
 253             l1 = l1->next;
 254         } else {
 255             l = l->next = l2;
 256             l2 = l2->next;
 257         }
 258     }
 259     l->next = l1 ? l1 : l2;
 260
 261     return list.next;
 262 }
 263
 264 static __inline__
 265 JSList*
 266 jack_slist_sort (JSList *list,
 267                  JCompareFunc compare_func)
 268 {
 269     JSList *l1, *l2;
 270
 271     if (!list)
 272         return NULL;
 273     if (!list->next)
 274         return list;
 275
 276     l1 = list;
 277     l2 = list->next;
 278
 279     while ((l2 = l2->next) != NULL) {
 280         if ((l2 = l2->next) == NULL)
 281             break;
 282         l1 = l1->next;
 283     }
 284     l2 = l1->next;
 285     l1->next = NULL;
 286
 287     return jack_slist_sort_merge (jack_slist_sort (list, compare_func),
 288                                   jack_slist_sort (l2, compare_func),
 289                                   compare_func);
 290 }
 291
 292 #endif /* __jack_jslist_h__ */
 293