diff options
author | Søren Sandmann Pedersen <ssp@redhat.com> | 2011-04-27 12:07:16 -0400 |
---|---|---|
committer | Søren Sandmann Pedersen <ssp@redhat.com> | 2012-06-02 07:54:48 -0400 |
commit | a3ae88b71b9d2dfc53303963157ecce4b29f0486 (patch) | |
tree | 8b6ee57e337e4bc1abceaad7a9b6aec4ba2e2923 | |
parent | c2230fe2aff709de21cc2ee3fa27c3f7578e7f9d (diff) |
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.
-rw-r--r-- | pixman/pixman-compiler.h | 4 | ||||
-rw-r--r-- | pixman/pixman-private.h | 45 |
2 files changed, 49 insertions, 0 deletions
diff --git a/pixman/pixman-compiler.h b/pixman/pixman-compiler.h index ffd51720..a978accf 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 f4ca6321..76d65e2b 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 */ |