2 $Id: x-list.c,v 1.16 2003/07/18 00:52:19 jharper Exp $
4 Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
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:
14 The above copyright notice and this permission notice shall be
15 included in all copies or substantial portions of the Software.
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.
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. */
36 /* Allocate in ~4k blocks */
37 #define NODES_PER_BLOCK 508
39 typedef struct x_list_block_struct x_list_block;
41 struct x_list_block_struct {
42 x_list l[NODES_PER_BLOCK];
45 static x_list *freelist;
47 static pthread_mutex_t freelist_lock = PTHREAD_MUTEX_INITIALIZER;
50 list_free_1 (x_list *node)
52 node->next = freelist;
57 X_PFX (list_free_1) (x_list *node)
59 assert (node != NULL);
61 pthread_mutex_lock (&freelist_lock);
65 pthread_mutex_unlock (&freelist_lock);
69 X_PFX (list_free) (x_list *lst)
73 pthread_mutex_lock (&freelist_lock);
75 for (; lst != NULL; lst = next)
81 pthread_mutex_unlock (&freelist_lock);
85 X_PFX (list_prepend) (x_list *lst, void *data)
89 pthread_mutex_lock (&freelist_lock);
96 b = malloc (sizeof (x_list_block));
98 for (i = 0; i < NODES_PER_BLOCK - 1; i++)
99 b->l[i].next = &(b->l[i+1]);
106 freelist = node->next;
108 pthread_mutex_unlock (&freelist_lock);
117 X_PFX (list_append) (x_list *lst, void *data)
122 return X_PFX (list_prepend) (NULL, data);
124 while (lst->next != NULL)
127 lst->next = X_PFX (list_prepend) (NULL, data);
133 X_PFX (list_reverse) (x_list *lst)
135 x_list *head = NULL, *next;
149 X_PFX (list_find) (x_list *lst, void *data)
151 for (; lst != NULL; lst = lst->next)
153 if (lst->data == data)
161 X_PFX (list_nth) (x_list *lst, int n)
163 while (n-- > 0 && lst != NULL)
170 X_PFX (list_pop) (x_list *lst, void **data_ret)
179 X_PFX (list_free_1) (tem);
182 if (data_ret != NULL)
189 X_PFX (list_filter) (x_list *lst,
190 int (*pred) (void *item, void *data), void *data)
192 x_list *ret = NULL, *node;
194 for (node = lst; node != NULL; node = node->next)
196 if ((*pred) (node->data, data))
197 ret = X_PFX (list_prepend) (ret, node->data);
200 return X_PFX (list_reverse) (ret);
204 X_PFX (list_map) (x_list *lst,
205 void *(*fun) (void *item, void *data), void *data)
207 x_list *ret = NULL, *node;
209 for (node = lst; node != NULL; node = node->next)
211 X_PFX (list_prepend) (ret, fun (node->data, data));
214 return X_PFX (list_reverse) (ret);
218 X_PFX (list_copy) (x_list *lst)
222 for (; lst != NULL; lst = lst->next)
224 copy = X_PFX (list_prepend) (copy, lst->data);
227 return X_PFX (list_reverse) (copy);
231 X_PFX (list_remove) (x_list *lst, void *data)
235 for (ptr = &lst; *ptr != NULL;)
239 if (node->data == data)
242 X_PFX (list_free_1) (node);
245 ptr = &((*ptr)->next);
251 X_EXTERN unsigned int
252 X_PFX (list_length) (x_list *lst)
257 for (; lst != NULL; lst = lst->next)
264 X_PFX (list_foreach) (x_list *lst,
265 void (*fun) (void *data, void *user_data),
268 for (; lst != NULL; lst = lst->next)
270 (*fun) (lst->data, user_data);
275 list_sort_1 (x_list *lst, int length,
276 int (*less) (const void *, const void *))
279 x_list *out_head, *out;
282 /* This is a standard (stable) list merge sort */
287 /* Calculate the halfway point. Split the list into two sub-lists. */
289 mid_point = length / 2;
291 for (i = mid_point - 1; i > 0; i--)
296 /* Sort each sub-list. */
298 lst = list_sort_1 (lst, mid_point, less);
299 mid = list_sort_1 (mid, length - mid_point, less);
301 /* Then merge them back together. */
303 assert (lst != NULL && mid != NULL);
305 if ((*less) (mid->data, lst->data))
306 out = out_head = mid, mid = mid->next;
308 out = out_head = lst, lst = lst->next;
310 while (lst != NULL && mid != NULL)
312 if ((*less) (mid->data, lst->data))
313 out = out->next = mid, mid = mid->next;
315 out = out->next = lst, lst = lst->next;
327 X_PFX (list_sort) (x_list *lst, int (*less) (const void *, const void *))
331 length = X_PFX (list_length) (lst);
333 return list_sort_1 (lst, length, less);