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