aboutsummaryrefslogtreecommitdiff
path: root/xorg-server/hw/xquartz/xpr/x-list.c
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2009-06-28 22:07:26 +0000
committermarha <marha@users.sourceforge.net>2009-06-28 22:07:26 +0000
commit3562e78743202e43aec8727005182a2558117eca (patch)
tree8f9113a77d12470c5c851a2a8e4cb02e89df7d43 /xorg-server/hw/xquartz/xpr/x-list.c
downloadvcxsrv-3562e78743202e43aec8727005182a2558117eca.tar.gz
vcxsrv-3562e78743202e43aec8727005182a2558117eca.tar.bz2
vcxsrv-3562e78743202e43aec8727005182a2558117eca.zip
Checked in the following released items:
xkeyboard-config-1.4.tar.gz ttf-bitstream-vera-1.10.tar.gz font-alias-1.0.1.tar.gz font-sun-misc-1.0.0.tar.gz font-sun-misc-1.0.0.tar.gz font-sony-misc-1.0.0.tar.gz font-schumacher-misc-1.0.0.tar.gz font-mutt-misc-1.0.0.tar.gz font-misc-misc-1.0.0.tar.gz font-misc-meltho-1.0.0.tar.gz font-micro-misc-1.0.0.tar.gz font-jis-misc-1.0.0.tar.gz font-isas-misc-1.0.0.tar.gz font-dec-misc-1.0.0.tar.gz font-daewoo-misc-1.0.0.tar.gz font-cursor-misc-1.0.0.tar.gz font-arabic-misc-1.0.0.tar.gz font-winitzki-cyrillic-1.0.0.tar.gz font-misc-cyrillic-1.0.0.tar.gz font-cronyx-cyrillic-1.0.0.tar.gz font-screen-cyrillic-1.0.1.tar.gz font-xfree86-type1-1.0.1.tar.gz font-adobe-utopia-type1-1.0.1.tar.gz font-ibm-type1-1.0.0.tar.gz font-bitstream-type1-1.0.0.tar.gz font-bitstream-speedo-1.0.0.tar.gz font-bh-ttf-1.0.0.tar.gz font-bh-type1-1.0.0.tar.gz font-bitstream-100dpi-1.0.0.tar.gz font-bh-lucidatypewriter-100dpi-1.0.0.tar.gz font-bh-100dpi-1.0.0.tar.gz font-adobe-utopia-100dpi-1.0.1.tar.gz font-adobe-100dpi-1.0.0.tar.gz font-util-1.0.1.tar.gz font-bitstream-75dpi-1.0.0.tar.gz font-bh-lucidatypewriter-75dpi-1.0.0.tar.gz font-adobe-utopia-75dpi-1.0.1.tar.gz font-bh-75dpi-1.0.0.tar.gz bdftopcf-1.0.1.tar.gz font-adobe-75dpi-1.0.0.tar.gz mkfontscale-1.0.6.tar.gz openssl-0.9.8k.tar.gz bigreqsproto-1.0.2.tar.gz xtrans-1.2.2.tar.gz resourceproto-1.0.2.tar.gz inputproto-1.4.4.tar.gz compositeproto-0.4.tar.gz damageproto-1.1.0.tar.gz zlib-1.2.3.tar.gz xkbcomp-1.0.5.tar.gz freetype-2.3.9.tar.gz pthreads-w32-2-8-0-release.tar.gz pixman-0.12.0.tar.gz kbproto-1.0.3.tar.gz evieext-1.0.2.tar.gz fixesproto-4.0.tar.gz recordproto-1.13.2.tar.gz randrproto-1.2.2.tar.gz scrnsaverproto-1.1.0.tar.gz renderproto-0.9.3.tar.gz xcmiscproto-1.1.2.tar.gz fontsproto-2.0.2.tar.gz xextproto-7.0.3.tar.gz xproto-7.0.14.tar.gz libXdmcp-1.0.2.tar.gz libxkbfile-1.0.5.tar.gz libfontenc-1.0.4.tar.gz libXfont-1.3.4.tar.gz libX11-1.1.5.tar.gz libXau-1.0.4.tar.gz libxcb-1.1.tar.gz xorg-server-1.5.3.tar.gz
Diffstat (limited to 'xorg-server/hw/xquartz/xpr/x-list.c')
-rw-r--r--xorg-server/hw/xquartz/xpr/x-list.c337
1 files changed, 337 insertions, 0 deletions
diff --git a/xorg-server/hw/xquartz/xpr/x-list.c b/xorg-server/hw/xquartz/xpr/x-list.c
new file mode 100644
index 000000000..3596dd355
--- /dev/null
+++ b/xorg-server/hw/xquartz/xpr/x-list.c
@@ -0,0 +1,337 @@
+/* x-list.c
+
+ 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. */
+
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#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);
+}