From a3ae88b71b9d2dfc53303963157ecce4b29f0486 Mon Sep 17 00:00:00 2001
From: =?utf8?q?S=C3=B8ren=20Sandmann=20Pedersen?= <ssp@redhat.com>
Date: Wed, 27 Apr 2011 12:07:16 -0400
Subject: [PATCH] Add doubly linked lists

This commit adds some new inline functions to maintain a doubly linked
list.

The way to use them is to embed a pixman_link_t into the structures
that should be linked, and use a pixman_list_t as the head of the
list.

The new functions are

    pixman_list_init (pixman_list_t *list);
    pixman_list_prepend (pixman_list_t *list, pixman_link_t *link);
    pixman_list_move_to_front (pixman_list_t *list, pixman_link_t *link);

There are also a new macro:

    CONTAINER_OF(type, member, data);

that can be used to get from a pointer to a member to the containing
structure.

V2: Use the C89 macro offsetof() instead of rolling our own -
suggested by Alan Coopersmith.
---
 pixman/pixman-compiler.h |  4 ++++
 pixman/pixman-private.h  | 45 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+)

diff --git a/pixman/pixman-compiler.h b/pixman/pixman-compiler.h
index ffd5172..a978acc 100644
--- a/pixman/pixman-compiler.h
+++ b/pixman/pixman-compiler.h
@@ -89,6 +89,10 @@
 #   define PIXMAN_EXPORT
 #endif
 
+/* member offsets */
+#define CONTAINER_OF(type, member, data)				\
+    ((type *)(((uint8_t *)data) - offsetof (type, member)))
+
 /* TLS */
 #if defined(PIXMAN_NO_TLS)
 
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index f4ca632..76d65e2 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -13,6 +13,7 @@
 #include <assert.h>
 #include <stdio.h>
 #include <string.h>
+#include <stddef.h>
 
 #include "pixman-compiler.h"
 
@@ -736,6 +737,50 @@ pixman_bool_t
 pixman_region16_copy_from_region32 (pixman_region16_t *dst,
                                     pixman_region32_t *src);
 
+/* Doubly linked lists */
+typedef struct pixman_link_t pixman_link_t;
+struct pixman_link_t
+{
+    pixman_link_t *next;
+    pixman_link_t *prev;
+};
+
+typedef struct pixman_list_t pixman_list_t;
+struct pixman_list_t
+{
+    pixman_link_t *head;
+    pixman_link_t *tail;
+};
+
+static force_inline void
+pixman_list_init (pixman_list_t *list)
+{
+    list->head = (pixman_link_t *)list;
+    list->tail = (pixman_link_t *)list;
+}
+
+static force_inline void
+pixman_list_prepend (pixman_list_t *list, pixman_link_t *link)
+{
+    link->next = list->head;
+    link->prev = (pixman_link_t *)list;
+    list->head->prev = link;
+    list->head = link;
+}
+
+static force_inline void
+pixman_list_unlink (pixman_link_t *link)
+{
+    link->prev->next = link->next;
+    link->next->prev = link->prev;
+}
+
+static force_inline void
+pixman_list_move_to_front (pixman_list_t *list, pixman_link_t *link)
+{
+    pixman_list_unlink (link);
+    pixman_list_prepend (list, link);
+}
 
 /* Misc macros */
 
-- 
2.7.4