3 * Copyright (c) 2002-2012 Apple Inc. All rights reserved.
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation files
7 * (the "Software"), to deal in the Software without restriction,
8 * including without limitation the rights to use, copy, modify, merge,
9 * publish, distribute, sublicense, and/or sell copies of the Software,
10 * and to permit persons to whom the Software is furnished to do so,
11 * subject to the following conditions:
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
20 * HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
23 * DEALINGS IN THE SOFTWARE.
25 * Except as contained in this notice, the name(s) of the above
26 * copyright holders shall not be used in advertising or otherwise to
27 * promote the sale, use or other dealings in this Software without
28 * prior written authorization.
31 #ifdef HAVE_DIX_CONFIG_H
32 #include <dix-config.h>
40 /* Allocate in ~4k blocks */
41 #define NODES_PER_BLOCK 508
43 typedef struct x_list_block_struct x_list_block
;
45 struct x_list_block_struct
{
46 x_list l
[NODES_PER_BLOCK
];
49 static x_list
*freelist
;
51 static pthread_mutex_t freelist_lock
= PTHREAD_MUTEX_INITIALIZER
;
54 list_free_1(x_list
*node
)
56 node
->next
= freelist
;
61 X_PFX(list_free_1
) (x_list
* node
) {
64 pthread_mutex_lock(&freelist_lock
);
68 pthread_mutex_unlock(&freelist_lock
);
72 X_PFX(list_free
) (x_list
* lst
) {
75 pthread_mutex_lock(&freelist_lock
);
77 for (; lst
!= NULL
; lst
= next
) {
82 pthread_mutex_unlock(&freelist_lock
);
86 X_PFX(list_prepend
) (x_list
* lst
, void *data
) {
89 pthread_mutex_lock(&freelist_lock
);
91 if (freelist
== NULL
) {
95 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
) {
121 return X_PFX(list_prepend
) (NULL
, data
);
123 while (lst
->next
!= NULL
)
126 lst
->next
= X_PFX(list_prepend
) (NULL
, data
);
132 X_PFX(list_reverse
) (x_list
* lst
) {
133 x_list
*head
= NULL
, *next
;
147 X_PFX(list_find
) (x_list
* lst
, void *data
) {
148 for (; lst
!= NULL
; lst
= lst
->next
) {
149 if (lst
->data
== data
)
157 X_PFX(list_nth
) (x_list
* lst
, int n
) {
158 while (n
-- > 0 && lst
!= NULL
)
165 X_PFX(list_pop
) (x_list
* lst
, void **data_ret
) {
172 X_PFX(list_free_1
) (tem
);
175 if (data_ret
!= NULL
)
182 X_PFX(list_filter
) (x_list
* lst
,
183 int (*pred
)(void *item
, void *data
), void *data
) {
184 x_list
*ret
= NULL
, *node
;
186 for (node
= lst
; node
!= NULL
; node
= node
->next
) {
187 if ((*pred
)(node
->data
, data
))
188 ret
= X_PFX(list_prepend
) (ret
, node
->data
);
191 return X_PFX(list_reverse
) (ret
);
195 X_PFX(list_map
) (x_list
* lst
,
196 void *(*fun
)(void *item
, void *data
), void *data
) {
197 x_list
*ret
= NULL
, *node
;
199 for (node
= lst
; node
!= NULL
; node
= node
->next
) {
200 X_PFX(list_prepend
) (ret
, fun(node
->data
, data
));
203 return X_PFX(list_reverse
) (ret
);
207 X_PFX(list_copy
) (x_list
* lst
) {
210 for (; lst
!= NULL
; lst
= lst
->next
) {
211 copy
= X_PFX(list_prepend
) (copy
, lst
->data
);
214 return X_PFX(list_reverse
) (copy
);
218 X_PFX(list_remove
) (x_list
* lst
, void *data
) {
221 for (ptr
= &lst
; *ptr
!= NULL
;) {
224 if (node
->data
== data
) {
226 X_PFX(list_free_1
) (node
);
229 ptr
= &((*ptr
)->next
);
235 X_EXTERN
unsigned int
236 X_PFX(list_length
) (x_list
* lst
) {
240 for (; lst
!= NULL
; lst
= lst
->next
)
247 X_PFX(list_foreach
) (x_list
* lst
,
248 void (*fun
)(void *data
, void *user_data
),
250 for (; lst
!= NULL
; lst
= lst
->next
) {
251 (*fun
)(lst
->data
, user_data
);
256 list_sort_1(x_list
*lst
, int length
,
257 int (*less
)(const void *, const void *))
260 x_list
*out_head
, *out
;
263 /* This is a standard (stable) list merge sort */
268 /* Calculate the halfway point. Split the list into two sub-lists. */
270 mid_point
= length
/ 2;
272 for (i
= mid_point
- 1; i
> 0; i
--)
277 /* Sort each sub-list. */
279 lst
= list_sort_1(lst
, mid_point
, less
);
280 mid
= list_sort_1(mid
, length
- mid_point
, less
);
282 /* Then merge them back together. */
284 assert(lst
!= NULL
&& mid
!= NULL
);
286 if ((*less
)(mid
->data
, lst
->data
))
287 out
= out_head
= mid
, mid
= mid
->next
;
289 out
= out_head
= lst
, lst
= lst
->next
;
291 while (lst
!= NULL
&& mid
!= NULL
)
293 if ((*less
)(mid
->data
, lst
->data
))
294 out
= out
->next
= mid
, mid
= mid
->next
;
296 out
= out
->next
= lst
, lst
= lst
->next
;
308 X_PFX(list_sort
) (x_list
* lst
, int (*less
)(const void *, const void *)) {
311 length
= X_PFX(list_length
) (lst
);
313 return list_sort_1(lst
, length
, less
);