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 new macros:

    OFFSET_OF(type, member)
    CONTAINER_OF(type, member, data);

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

2 files changed, 56 insertions, 0 deletions

diff --git a/pixman/pixman-compiler.h b/pixman/pixman-compiler.h
index ffd51720..9bdbc6ec 100644
--- a/pixman/pixman-compiler.h
+++ b/pixman/pixman-compiler.h
@@ -89,6 +89,18 @@
 #   define PIXMAN_EXPORT
 #endif
 
+/* member offsets */
+#if defined(__GNUC__) && __GNUC__ >= 4
+#   define OFFSET_OF(type, member)					\
+    ((unsigned long)__builtin_offsetof(type, member))
+#else
+#   define OFFSET_OF(type, member)					\
+    ((unsigned long)(&(((type *)0)->member))
+#endif
+
+#define CONTAINER_OF(type, member, data)				\
+    ((type *)(((uint8_t *)data) - OFFSET_OF(type, member)))
+
 /* TLS */
 #if defined(PIXMAN_NO_TLS)
 
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index f4ca6321..b5dcc14f 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -736,6 +736,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 */