+++ /dev/null
-/* x-list.c
- $Id: x-list.c,v 1.16 2003/07/18 00:52:19 jharper Exp $
-
- Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
-
- Permission is hereby granted, free of charge, to any person
- obtaining a copy of this software and associated documentation files
- (the "Software"), to deal in the Software without restriction,
- including without limitation the rights to use, copy, modify, merge,
- publish, distribute, sublicense, and/or sell copies of the Software,
- and to permit persons to whom the Software is furnished to do so,
- subject to the following conditions:
-
- The above copyright notice and this permission notice shall be
- included in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- NONINFRINGEMENT. IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
- HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
- DEALINGS IN THE SOFTWARE.
-
- Except as contained in this notice, the name(s) of the above
- copyright holders shall not be used in advertising or otherwise to
- promote the sale, use or other dealings in this Software without
- prior written authorization. */
-
-#include "x-list.h"
-#include <stdlib.h>
-#include <assert.h>
-#include <pthread.h>
-
-/* Allocate in ~4k blocks */
-#define NODES_PER_BLOCK 508
-
-typedef struct x_list_block_struct x_list_block;
-
-struct x_list_block_struct {
- x_list l[NODES_PER_BLOCK];
-};
-
-static x_list *freelist;
-
-static pthread_mutex_t freelist_lock = PTHREAD_MUTEX_INITIALIZER;
-
-static inline void
-list_free_1 (x_list *node)
-{
- node->next = freelist;
- freelist = node;
-}
-
-X_EXTERN void
-X_PFX (list_free_1) (x_list *node)
-{
- assert (node != NULL);
-
- pthread_mutex_lock (&freelist_lock);
-
- list_free_1 (node);
-
- pthread_mutex_unlock (&freelist_lock);
-}
-
-X_EXTERN void
-X_PFX (list_free) (x_list *lst)
-{
- x_list *next;
-
- pthread_mutex_lock (&freelist_lock);
-
- for (; lst != NULL; lst = next)
- {
- next = lst->next;
- list_free_1 (lst);
- }
-
- pthread_mutex_unlock (&freelist_lock);
-}
-
-X_EXTERN x_list *
-X_PFX (list_prepend) (x_list *lst, void *data)
-{
- x_list *node;
-
- pthread_mutex_lock (&freelist_lock);
-
- if (freelist == NULL)
- {
- x_list_block *b;
- int i;
-
- b = malloc (sizeof (x_list_block));
-
- for (i = 0; i < NODES_PER_BLOCK - 1; i++)
- b->l[i].next = &(b->l[i+1]);
- b->l[i].next = NULL;
-
- freelist = b->l;
- }
-
- node = freelist;
- freelist = node->next;
-
- pthread_mutex_unlock (&freelist_lock);
-
- node->next = lst;
- node->data = data;
-
- return node;
-}
-
-X_EXTERN x_list *
-X_PFX (list_append) (x_list *lst, void *data)
-{
- x_list *head = lst;
-
- if (lst == NULL)
- return X_PFX (list_prepend) (NULL, data);
-
- while (lst->next != NULL)
- lst = lst->next;
-
- lst->next = X_PFX (list_prepend) (NULL, data);
-
- return head;
-}
-
-X_EXTERN x_list *
-X_PFX (list_reverse) (x_list *lst)
-{
- x_list *head = NULL, *next;
-
- while (lst != NULL)
- {
- next = lst->next;
- lst->next = head;
- head = lst;
- lst = next;
- }
-
- return head;
-}
-
-X_EXTERN x_list *
-X_PFX (list_find) (x_list *lst, void *data)
-{
- for (; lst != NULL; lst = lst->next)
- {
- if (lst->data == data)
- return lst;
- }
-
- return NULL;
-}
-
-X_EXTERN x_list *
-X_PFX (list_nth) (x_list *lst, int n)
-{
- while (n-- > 0 && lst != NULL)
- lst = lst->next;
-
- return lst;
-}
-
-X_EXTERN x_list *
-X_PFX (list_pop) (x_list *lst, void **data_ret)
-{
- void *data = NULL;
-
- if (lst != NULL)
- {
- x_list *tem = lst;
- data = lst->data;
- lst = lst->next;
- X_PFX (list_free_1) (tem);
- }
-
- if (data_ret != NULL)
- *data_ret = data;
-
- return lst;
-}
-
-X_EXTERN x_list *
-X_PFX (list_filter) (x_list *lst,
- int (*pred) (void *item, void *data), void *data)
-{
- x_list *ret = NULL, *node;
-
- for (node = lst; node != NULL; node = node->next)
- {
- if ((*pred) (node->data, data))
- ret = X_PFX (list_prepend) (ret, node->data);
- }
-
- return X_PFX (list_reverse) (ret);
-}
-
-X_EXTERN x_list *
-X_PFX (list_map) (x_list *lst,
- void *(*fun) (void *item, void *data), void *data)
-{
- x_list *ret = NULL, *node;
-
- for (node = lst; node != NULL; node = node->next)
- {
- X_PFX (list_prepend) (ret, fun (node->data, data));
- }
-
- return X_PFX (list_reverse) (ret);
-}
-
-X_EXTERN x_list *
-X_PFX (list_copy) (x_list *lst)
-{
- x_list *copy = NULL;
-
- for (; lst != NULL; lst = lst->next)
- {
- copy = X_PFX (list_prepend) (copy, lst->data);
- }
-
- return X_PFX (list_reverse) (copy);
-}
-
-X_EXTERN x_list *
-X_PFX (list_remove) (x_list *lst, void *data)
-{
- x_list **ptr, *node;
-
- for (ptr = &lst; *ptr != NULL;)
- {
- node = *ptr;
-
- if (node->data == data)
- {
- *ptr = node->next;
- X_PFX (list_free_1) (node);
- }
- else
- ptr = &((*ptr)->next);
- }
-
- return lst;
-}
-
-X_EXTERN unsigned int
-X_PFX (list_length) (x_list *lst)
-{
- unsigned int n;
-
- n = 0;
- for (; lst != NULL; lst = lst->next)
- n++;
-
- return n;
-}
-
-X_EXTERN void
-X_PFX (list_foreach) (x_list *lst,
- void (*fun) (void *data, void *user_data),
- void *user_data)
-{
- for (; lst != NULL; lst = lst->next)
- {
- (*fun) (lst->data, user_data);
- }
-}
-
-static x_list *
-list_sort_1 (x_list *lst, int length,
- int (*less) (const void *, const void *))
-{
- x_list *mid, *ptr;
- x_list *out_head, *out;
- int mid_point, i;
-
- /* This is a standard (stable) list merge sort */
-
- if (length < 2)
- return lst;
-
- /* Calculate the halfway point. Split the list into two sub-lists. */
-
- mid_point = length / 2;
- ptr = lst;
- for (i = mid_point - 1; i > 0; i--)
- ptr = ptr->next;
- mid = ptr->next;
- ptr->next = NULL;
-
- /* Sort each sub-list. */
-
- lst = list_sort_1 (lst, mid_point, less);
- mid = list_sort_1 (mid, length - mid_point, less);
-
- /* Then merge them back together. */
-
- assert (lst != NULL && mid != NULL);
-
- if ((*less) (mid->data, lst->data))
- out = out_head = mid, mid = mid->next;
- else
- out = out_head = lst, lst = lst->next;
-
- while (lst != NULL && mid != NULL)
- {
- if ((*less) (mid->data, lst->data))
- out = out->next = mid, mid = mid->next;
- else
- out = out->next = lst, lst = lst->next;
- }
-
- if (lst != NULL)
- out->next = lst;
- else
- out->next = mid;
-
- return out_head;
-}
-
-X_EXTERN x_list *
-X_PFX (list_sort) (x_list *lst, int (*less) (const void *, const void *))
-{
- int length;
-
- length = X_PFX (list_length) (lst);
-
- return list_sort_1 (lst, length, less);
-}
projects / synfig.git / blobdiff