| 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 | } |