Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /* x-list.c |
2 | * | |
3 | * Copyright (c) 2002-2012 Apple Inc. All rights reserved. | |
4 | * | |
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: | |
12 | * | |
13 | * The above copyright notice and this permission notice shall be | |
14 | * included in all copies or substantial portions of the Software. | |
15 | * | |
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. | |
24 | * | |
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. | |
29 | */ | |
30 | ||
31 | #ifdef HAVE_DIX_CONFIG_H | |
32 | #include <dix-config.h> | |
33 | #endif | |
34 | ||
35 | #include "x-list.h" | |
36 | #include <stdlib.h> | |
37 | #include <assert.h> | |
38 | #include <pthread.h> | |
39 | ||
40 | /* Allocate in ~4k blocks */ | |
41 | #define NODES_PER_BLOCK 508 | |
42 | ||
43 | typedef struct x_list_block_struct x_list_block; | |
44 | ||
45 | struct x_list_block_struct { | |
46 | x_list l[NODES_PER_BLOCK]; | |
47 | }; | |
48 | ||
49 | static x_list *freelist; | |
50 | ||
51 | static pthread_mutex_t freelist_lock = PTHREAD_MUTEX_INITIALIZER; | |
52 | ||
53 | static inline void | |
54 | list_free_1(x_list *node) | |
55 | { | |
56 | node->next = freelist; | |
57 | freelist = node; | |
58 | } | |
59 | ||
60 | X_EXTERN void | |
61 | X_PFX(list_free_1) (x_list * node) { | |
62 | assert(node != NULL); | |
63 | ||
64 | pthread_mutex_lock(&freelist_lock); | |
65 | ||
66 | list_free_1(node); | |
67 | ||
68 | pthread_mutex_unlock(&freelist_lock); | |
69 | } | |
70 | ||
71 | X_EXTERN void | |
72 | X_PFX(list_free) (x_list * lst) { | |
73 | x_list *next; | |
74 | ||
75 | pthread_mutex_lock(&freelist_lock); | |
76 | ||
77 | for (; lst != NULL; lst = next) { | |
78 | next = lst->next; | |
79 | list_free_1(lst); | |
80 | } | |
81 | ||
82 | pthread_mutex_unlock(&freelist_lock); | |
83 | } | |
84 | ||
85 | X_EXTERN x_list * | |
86 | X_PFX(list_prepend) (x_list * lst, void *data) { | |
87 | x_list *node; | |
88 | ||
89 | pthread_mutex_lock(&freelist_lock); | |
90 | ||
91 | if (freelist == NULL) { | |
92 | x_list_block *b; | |
93 | int i; | |
94 | ||
95 | b = malloc(sizeof(x_list_block)); | |
96 | assert(b != NULL); | |
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 | x_list *head = lst; | |
119 | ||
120 | if (lst == NULL) | |
121 | return X_PFX(list_prepend) (NULL, data); | |
122 | ||
123 | while (lst->next != NULL) | |
124 | lst = lst->next; | |
125 | ||
126 | lst->next = X_PFX(list_prepend) (NULL, data); | |
127 | ||
128 | return head; | |
129 | } | |
130 | ||
131 | X_EXTERN x_list * | |
132 | X_PFX(list_reverse) (x_list * lst) { | |
133 | x_list *head = NULL, *next; | |
134 | ||
135 | while (lst != NULL) | |
136 | { | |
137 | next = lst->next; | |
138 | lst->next = head; | |
139 | head = lst; | |
140 | lst = next; | |
141 | } | |
142 | ||
143 | return head; | |
144 | } | |
145 | ||
146 | X_EXTERN x_list * | |
147 | X_PFX(list_find) (x_list * lst, void *data) { | |
148 | for (; lst != NULL; lst = lst->next) { | |
149 | if (lst->data == data) | |
150 | return lst; | |
151 | } | |
152 | ||
153 | return NULL; | |
154 | } | |
155 | ||
156 | X_EXTERN x_list * | |
157 | X_PFX(list_nth) (x_list * lst, int n) { | |
158 | while (n-- > 0 && lst != NULL) | |
159 | lst = lst->next; | |
160 | ||
161 | return lst; | |
162 | } | |
163 | ||
164 | X_EXTERN x_list * | |
165 | X_PFX(list_pop) (x_list * lst, void **data_ret) { | |
166 | void *data = NULL; | |
167 | ||
168 | if (lst != NULL) { | |
169 | x_list *tem = lst; | |
170 | data = lst->data; | |
171 | lst = lst->next; | |
172 | X_PFX(list_free_1) (tem); | |
173 | } | |
174 | ||
175 | if (data_ret != NULL) | |
176 | *data_ret = data; | |
177 | ||
178 | return lst; | |
179 | } | |
180 | ||
181 | X_EXTERN x_list * | |
182 | X_PFX(list_filter) (x_list * lst, | |
183 | int (*pred)(void *item, void *data), void *data) { | |
184 | x_list *ret = NULL, *node; | |
185 | ||
186 | for (node = lst; node != NULL; node = node->next) { | |
187 | if ((*pred)(node->data, data)) | |
188 | ret = X_PFX(list_prepend) (ret, node->data); | |
189 | } | |
190 | ||
191 | return X_PFX(list_reverse) (ret); | |
192 | } | |
193 | ||
194 | X_EXTERN x_list * | |
195 | X_PFX(list_map) (x_list * lst, | |
196 | void *(*fun)(void *item, void *data), void *data) { | |
197 | x_list *ret = NULL, *node; | |
198 | ||
199 | for (node = lst; node != NULL; node = node->next) { | |
200 | X_PFX(list_prepend) (ret, fun(node->data, data)); | |
201 | } | |
202 | ||
203 | return X_PFX(list_reverse) (ret); | |
204 | } | |
205 | ||
206 | X_EXTERN x_list * | |
207 | X_PFX(list_copy) (x_list * lst) { | |
208 | x_list *copy = NULL; | |
209 | ||
210 | for (; lst != NULL; lst = lst->next) { | |
211 | copy = X_PFX(list_prepend) (copy, lst->data); | |
212 | } | |
213 | ||
214 | return X_PFX(list_reverse) (copy); | |
215 | } | |
216 | ||
217 | X_EXTERN x_list * | |
218 | X_PFX(list_remove) (x_list * lst, void *data) { | |
219 | x_list **ptr, *node; | |
220 | ||
221 | for (ptr = &lst; *ptr != NULL;) { | |
222 | node = *ptr; | |
223 | ||
224 | if (node->data == data) { | |
225 | *ptr = node->next; | |
226 | X_PFX(list_free_1) (node); | |
227 | } | |
228 | else | |
229 | ptr = &((*ptr)->next); | |
230 | } | |
231 | ||
232 | return lst; | |
233 | } | |
234 | ||
235 | X_EXTERN unsigned int | |
236 | X_PFX(list_length) (x_list * lst) { | |
237 | unsigned int n; | |
238 | ||
239 | n = 0; | |
240 | for (; lst != NULL; lst = lst->next) | |
241 | n++; | |
242 | ||
243 | return n; | |
244 | } | |
245 | ||
246 | X_EXTERN void | |
247 | X_PFX(list_foreach) (x_list * lst, | |
248 | void (*fun)(void *data, void *user_data), | |
249 | void *user_data) { | |
250 | for (; lst != NULL; lst = lst->next) { | |
251 | (*fun)(lst->data, user_data); | |
252 | } | |
253 | } | |
254 | ||
255 | static x_list * | |
256 | list_sort_1(x_list *lst, int length, | |
257 | int (*less)(const void *, const void *)) | |
258 | { | |
259 | x_list *mid, *ptr; | |
260 | x_list *out_head, *out; | |
261 | int mid_point, i; | |
262 | ||
263 | /* This is a standard (stable) list merge sort */ | |
264 | ||
265 | if (length < 2) | |
266 | return lst; | |
267 | ||
268 | /* Calculate the halfway point. Split the list into two sub-lists. */ | |
269 | ||
270 | mid_point = length / 2; | |
271 | ptr = lst; | |
272 | for (i = mid_point - 1; i > 0; i--) | |
273 | ptr = ptr->next; | |
274 | mid = ptr->next; | |
275 | ptr->next = NULL; | |
276 | ||
277 | /* Sort each sub-list. */ | |
278 | ||
279 | lst = list_sort_1(lst, mid_point, less); | |
280 | mid = list_sort_1(mid, length - mid_point, less); | |
281 | ||
282 | /* Then merge them back together. */ | |
283 | ||
284 | assert(lst != NULL && mid != NULL); | |
285 | ||
286 | if ((*less)(mid->data, lst->data)) | |
287 | out = out_head = mid, mid = mid->next; | |
288 | else | |
289 | out = out_head = lst, lst = lst->next; | |
290 | ||
291 | while (lst != NULL && mid != NULL) | |
292 | { | |
293 | if ((*less)(mid->data, lst->data)) | |
294 | out = out->next = mid, mid = mid->next; | |
295 | else | |
296 | out = out->next = lst, lst = lst->next; | |
297 | } | |
298 | ||
299 | if (lst != NULL) | |
300 | out->next = lst; | |
301 | else | |
302 | out->next = mid; | |
303 | ||
304 | return out_head; | |
305 | } | |
306 | ||
307 | X_EXTERN x_list * | |
308 | X_PFX(list_sort) (x_list * lst, int (*less)(const void *, const void *)) { | |
309 | int length; | |
310 | ||
311 | length = X_PFX(list_length) (lst); | |
312 | ||
313 | return list_sort_1(lst, length, less); | |
314 | } |