synfig-osx/launcher/x-list.c

   1 /* x-list.c
   2    $Id: x-list.c,v 1.16 2003/07/18 00:52:19 jharper Exp $
   3
   4    Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
   5
   6    Permission is hereby granted, free of charge, to any person
   7    obtaining a copy of this software and associated documentation files
   8    (the "Software"), to deal in the Software without restriction,
   9    including without limitation the rights to use, copy, modify, merge,
  10    publish, distribute, sublicense, and/or sell copies of the Software,
  11    and to permit persons to whom the Software is furnished to do so,
  12    subject to the following conditions:
  13
  14    The above copyright notice and this permission notice shall be
  15    included in all copies or substantial portions of the Software.
  16
  17    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20    NONINFRINGEMENT.  IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
  21    HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  23    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24    DEALINGS IN THE SOFTWARE.
  25
  26    Except as contained in this notice, the name(s) of the above
  27    copyright holders shall not be used in advertising or otherwise to
  28    promote the sale, use or other dealings in this Software without
  29    prior written authorization. */
  30
  31 #include "x-list.h"
  32 #include <stdlib.h>
  33 #include <assert.h>
  34 #include <pthread.h>
  35
  36 /* Allocate in ~4k blocks */
  37 #define NODES_PER_BLOCK 508
  38
  39 typedef struct x_list_block_struct x_list_block;
  40
  41 struct x_list_block_struct {
  42     x_list l[NODES_PER_BLOCK];
  43 };
  44
  45 static x_list *freelist;
  46
  47 static pthread_mutex_t freelist_lock = PTHREAD_MUTEX_INITIALIZER;
  48
  49 static inline void
  50 list_free_1 (x_list *node)
  51 {
  52     node->next = freelist;
  53     freelist = node;
  54 }
  55
  56 X_EXTERN void
  57 X_PFX (list_free_1) (x_list *node)
  58 {
  59     assert (node != NULL);
  60
  61     pthread_mutex_lock (&freelist_lock);
  62
  63     list_free_1 (node);
  64
  65     pthread_mutex_unlock (&freelist_lock);
  66 }
  67
  68 X_EXTERN void
  69 X_PFX (list_free) (x_list *lst)
  70 {
  71     x_list *next;
  72
  73     pthread_mutex_lock (&freelist_lock);
  74
  75     for (; lst != NULL; lst = next)
  76     {
  77         next = lst->next;
  78         list_free_1 (lst);
  79     }
  80
  81     pthread_mutex_unlock (&freelist_lock);
  82 }
  83
  84 X_EXTERN x_list *
  85 X_PFX (list_prepend) (x_list *lst, void *data)
  86 {
  87     x_list *node;
  88
  89     pthread_mutex_lock (&freelist_lock);
  90
  91     if (freelist == NULL)
  92     {
  93         x_list_block *b;
  94         int i;
  95
  96         b = malloc (sizeof (x_list_block));
  97
  98         for (i = 0; i < NODES_PER_BLOCK - 1; i++)
  99             b->l[i].next = &(b->l[i+1]);
 100         b->l[i].next = NULL;
 101
 102         freelist = b->l;
 103     }
 104
 105     node = freelist;
 106     freelist = node->next;
 107
 108     pthread_mutex_unlock (&freelist_lock);
 109
 110     node->next = lst;
 111     node->data = data;
 112
 113     return node;
 114 }
 115
 116 X_EXTERN x_list *
 117 X_PFX (list_append) (x_list *lst, void *data)
 118 {
 119     x_list *head = lst;
 120
 121     if (lst == NULL)
 122         return X_PFX (list_prepend) (NULL, data);
 123
 124     while (lst->next != NULL)
 125         lst = lst->next;
 126
 127     lst->next = X_PFX (list_prepend) (NULL, data);
 128
 129     return head;
 130 }
 131
 132 X_EXTERN x_list *
 133 X_PFX (list_reverse) (x_list *lst)
 134 {
 135     x_list *head = NULL, *next;
 136
 137     while (lst != NULL)
 138     {
 139         next = lst->next;
 140         lst->next = head;
 141         head = lst;
 142         lst = next;
 143     }
 144
 145     return head;
 146 }
 147
 148 X_EXTERN x_list *
 149 X_PFX (list_find) (x_list *lst, void *data)
 150 {
 151     for (; lst != NULL; lst = lst->next)
 152     {
 153         if (lst->data == data)
 154             return lst;
 155     }
 156
 157     return NULL;
 158 }
 159
 160 X_EXTERN x_list *
 161 X_PFX (list_nth) (x_list *lst, int n)
 162 {
 163     while (n-- > 0 && lst != NULL)
 164         lst = lst->next;
 165
 166     return lst;
 167 }
 168
 169 X_EXTERN x_list *
 170 X_PFX (list_pop) (x_list *lst, void **data_ret)
 171 {
 172     void *data = NULL;
 173
 174     if (lst != NULL)
 175     {
 176         x_list *tem = lst;
 177         data = lst->data;
 178         lst = lst->next;
 179         X_PFX (list_free_1) (tem);
 180     }
 181
 182     if (data_ret != NULL)
 183         *data_ret = data;
 184
 185     return lst;
 186 }
 187
 188 X_EXTERN x_list *
 189 X_PFX (list_filter) (x_list *lst,
 190                      int (*pred) (void *item, void *data), void *data)
 191 {
 192     x_list *ret = NULL, *node;
 193
 194     for (node = lst; node != NULL; node = node->next)
 195     {
 196         if ((*pred) (node->data, data))
 197             ret = X_PFX (list_prepend) (ret, node->data);
 198     }
 199
 200     return X_PFX (list_reverse) (ret);
 201 }
 202
 203 X_EXTERN x_list *
 204 X_PFX (list_map) (x_list *lst,
 205                   void *(*fun) (void *item, void *data), void *data)
 206 {
 207     x_list *ret = NULL, *node;
 208
 209     for (node = lst; node != NULL; node = node->next)
 210     {
 211         X_PFX (list_prepend) (ret, fun (node->data, data));
 212     }
 213
 214     return X_PFX (list_reverse) (ret);
 215 }
 216
 217 X_EXTERN x_list *
 218 X_PFX (list_copy) (x_list *lst)
 219 {
 220     x_list *copy = NULL;
 221
 222     for (; lst != NULL; lst = lst->next)
 223     {
 224         copy = X_PFX (list_prepend) (copy, lst->data);
 225     }
 226
 227     return X_PFX (list_reverse) (copy);
 228 }
 229
 230 X_EXTERN x_list *
 231 X_PFX (list_remove) (x_list *lst, void *data)
 232 {
 233     x_list **ptr, *node;
 234
 235     for (ptr = &lst; *ptr != NULL;)
 236     {
 237         node = *ptr;
 238
 239         if (node->data == data)
 240         {
 241             *ptr = node->next;
 242             X_PFX (list_free_1) (node);
 243         }
 244         else
 245             ptr = &((*ptr)->next);
 246     }
 247
 248     return lst;
 249 }
 250
 251 X_EXTERN unsigned int
 252 X_PFX (list_length) (x_list *lst)
 253 {
 254     unsigned int n;
 255
 256     n = 0;
 257     for (; lst != NULL; lst = lst->next)
 258         n++;
 259
 260     return n;
 261 }
 262
 263 X_EXTERN void
 264 X_PFX (list_foreach) (x_list *lst,
 265                       void (*fun) (void *data, void *user_data),
 266                       void *user_data)
 267 {
 268     for (; lst != NULL; lst = lst->next)
 269     {
 270         (*fun) (lst->data, user_data);
 271     }
 272 }
 273
 274 static x_list *
 275 list_sort_1 (x_list *lst, int length,
 276              int (*less) (const void *, const void *))
 277 {
 278     x_list *mid, *ptr;
 279     x_list *out_head, *out;
 280     int mid_point, i;
 281
 282     /* This is a standard (stable) list merge sort */
 283
 284     if (length < 2)
 285         return lst;
 286
 287     /* Calculate the halfway point. Split the list into two sub-lists. */
 288
 289     mid_point = length / 2;
 290     ptr = lst;
 291     for (i = mid_point - 1; i > 0; i--)
 292         ptr = ptr->next;
 293     mid = ptr->next;
 294     ptr->next = NULL;
 295
 296     /* Sort each sub-list. */
 297
 298     lst = list_sort_1 (lst, mid_point, less);
 299     mid = list_sort_1 (mid, length - mid_point, less);
 300
 301     /* Then merge them back together. */
 302
 303     assert (lst != NULL && mid != NULL);
 304
 305     if ((*less) (mid->data, lst->data))
 306         out = out_head = mid, mid = mid->next;
 307     else
 308         out = out_head = lst, lst = lst->next;
 309
 310     while (lst != NULL && mid != NULL)
 311     {
 312         if ((*less) (mid->data, lst->data))
 313             out = out->next = mid, mid = mid->next;
 314         else
 315             out = out->next = lst, lst = lst->next;
 316     }
 317
 318     if (lst != NULL)
 319         out->next = lst;
 320     else
 321         out->next = mid;
 322
 323     return out_head;
 324 }
 325
 326 X_EXTERN x_list *
 327 X_PFX (list_sort) (x_list *lst, int (*less) (const void *, const void *))
 328 {
 329     int length;
 330
 331     length = X_PFX (list_length) (lst);
 332
 333     return list_sort_1 (lst, length, less);
 334 }