#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif
#include "x-list.h"
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>
#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;
if (length < 2)
return lst;
mid_point = length / 2;
ptr = lst;
for (i = mid_point - 1; i > 0; i--)
ptr = ptr->next;
mid = ptr->next;
ptr->next = NULL;
lst = list_sort_1 (lst, mid_point, less);
mid = list_sort_1 (mid, length - mid_point, less);
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);
}